Пример.
Необходимо перевезти грузы из 3-х пунктов отправления (А1, А2, А3) к 4-м пунктам назначения (В1, В2, В3, В4). В трех пунктах отправления имеются грузы в объемах: в первом – 400 т, во втором – 700 т, в третьем – 1200 т. Потребности четырех пунктов назначения следующие: первого – 700 т, второго – 200 т, третьего – 600 и четвертого – 800 т.
Известны стоимости перевозок грузов от каждого пункта отправления к каждому пункту назначения (Таблица 1).
Таблица 1 - Стоимость перевозки грузов, ден. ед.
|
Пункты отправления. |
Пункты назначения |
|||
|
В1 |
В2 |
В3 |
В4 |
|
|
А1 |
18 |
12 |
13 |
7 |
|
А2 |
17 |
10 |
11 |
13 |
|
А3 |
15 |
11 |
10 |
9 |
Необходимо составить оптимальный план грузоперевозок с наименьшими затратами.
Пункт, отправляющий груз, называют поставщиком, а пункт, принимающий груз, - потребителем.
Составим экономико-математическую модель задачи.
Проверяют, является задачи открытой или закрытой. Для этого суммируют объемы отправления груза и объемы приемки груза. То есть проверяют равенство:
Возможности поставщиков и потребности потребителей в данной задаче равны и составляют 2300 т. Задача является закрытой.
Далее оформляют задачу в виде специальной таблицы (Таблица 2)
Таблица 2 – Таблица транспортной задачи.
|
2300 |
700 |
200 |
600 |
800 |
|
400 |
18 х11 |
12 х12 |
13 х13 |
7 х14 |
|
700 |
17 х21 |
10 х22 |
11 х23 |
13 х24 |
|
1200 |
15 х31 |
11 х32 |
10 х33 |
9 х34 |
Целевая функция:
Z = 18х1+ 12х12+ 13х13+ 7х14+ 17х21+ 10х22+ 11х23+
+ 13х24+ 15х31+ 11х32+ 10х33+ 9х34 → min
Ограничения:
1. Груз, расположенный в каждом пукнте отправления должен быть вывезен в полном объеме.
х11+ х12 + х13 + х14 = 400
х21+ х22 + х23 + х24 = 700
х31 + х32+ х33 + х34 = 1200
2. Потребности каждого пункта назначения дожны быть удовлетворены в полном объеме.
х11 + х21 + х31 = 700
х12 + х22 + х32 = 200
х13 + х23+ х33 = 600
х14 + х24+ х34 = 800
3. Условие неотрицательности переменных.
Построим первый базисный план методом наименьшего элемента в таблице.
Составление опорного плана начинают с клетки с наименьшей оценкой. Это клетка (1:4), которая находтся на пересечении первой строки и четвертого столбца. Записывают в нее максимально возможную величину груза – 400. Мощность первого поставщика полностью исчерпана, следовательно первую строку исключают из дальнейшего рассмотрения.
Далее среди оставшихся оценок находят минимальный элемент и делают туда поставку. Это клетка (3:4) с оценкой 9. Объем поставки составляет 400, и так далее делают распределение, не нарушая балансы по строкам и столбцам (Таблица 3).
Таблица 3 – Первая транспортная таблица
|
2300 |
700 |
200 |
600 |
800 |
|
400 |
18
|
12
|
13
|
7 400 |
|
700 |
17 500 |
10 200 |
11
|
13
|
|
1200 |
15 200 |
11
|
10 600 |
9 400 |
Проверяют число занятых клеток: (m+n-1)=4+3-1= 6.
Подсчитывают значение Z, т.е. величину затрат:
Z = 7*400 + 17*500 + 10*200 + 15*200 + 10*600 + 9*400 =
= 2800 + 8500 + 2000 + 3000 + 6000 + 3600 = 25900 т/км
Полученный первый план проверяют на оптимальность. Для этого поочередно рассматривают клетки, не вошедние в план, т. е свободные клетки.
Для них вычисляют характеристики, для чего строят замкнутые контуры. Одно вершина контура находится в свободной клетке, другие - в занятых вершинах. Вершину в свободной клетке помечают знаком «+», а остальные вершины поочередно знаками «-», «+».
Характеристики свободных клеток вычисляются с помощью оценок клеток, находящихся в вершинах построенного контура с учетом знаком.
Вычисленные характеристик должны удовлетворять условию:
lij. ≥ 0.
При нарушении условия, в клетку с наименьшим отрицательным значением следует сделать перераспределение груза.
Так, в таблице с первым базисным планом первая свободная клетка (1:1). Вычисляем для нее характеристику:
l11 = 18-7+9-15 = 5
Далее для других свободных клеток:
l12 = 12-7+9-15+17-10 = 6
l13 = 13-7+9-10 = 5
l23 = 11-10+15-17 = -1
l24 = 13-9+15-17 = 2
l32 = 11-15+17-10 = 3
В клетке (2:3) нарушается условие, поэтому в эту клетку необходимо сделать перераспределение.
В новую таблицу заносят полученный путем перераспределения план (Таблица 4).
Таблица 4 - Вторая транспортная таблица
|
2300 |
700 |
200 |
600 |
800 |
|
400 |
18
|
12
|
13
|
7 400 |
|
700 |
17
|
10 200 |
11 500 |
13
|
|
1200 |
15 700 |
11
|
10 100 |
9 400 |
Подсчитывают значение целевой функции при новом плане:
Z = 7*400 + 10*200 + 11*500 + 15*700 + 10*100 + 9*400 =
= 2800 + 2000 + 5500 + 10500 + 1000 + 3600 = 25400 т/км
Проверяют новый план на оптимальность.
l11 = 18-7+9-15 = 5
l12 = 12-7+9-10+11-10 = 5
l13 = 13-7+9-10 = 5
l21 = 17-11+10-15 = 1
l24 = 13-9+10-11 = 3
l32 = 11-10+11-10 = 2.
Все характеристики являются положительными. Следовательно, на этом этапе получен оптимальный план.
Решение данной задачи будет следующим:
х14 = 400
х22 = 200
х23 = 500
х31 = 700
х33 = 100
х34 = 400
Z = 25400 т/км
