Открытая транспортная задача
При нарушении условия транспортная задача называется открытой. Возможны случаи, когда
1) . Задача сводится к закрытой задаче введением фиктивного поставщика с запасом груза =. Груз, соответствующий поставкам от , останется недополученным потребителями.
2) . Задача сводится к закрытой задаче введением фиктивного потребителя с потребностями в грузе =. Соответствующие ему значения в оптимальном плане будут означать оставшийся не отправленным груз поставщиков.
При введении фиктивных поставщиков и потребителей, соответствующие им цены единичных перевозок принимаются равными нулю, если нет других ограничений.
Пример 2. Имеется 3 поставщика и 3 потребителя, запасы грузов и потребности в них, а также цены единичной перевозки указаны в таблице. Требуется составить план перевозок, при котором суммарные транспортные затраты будут минимальными.
|
60 |
60 |
50 |
50 |
3 |
3 |
2 |
70 |
4 |
3 |
2 |
60 |
6 |
7 |
4 |
Прежде всего проверим, является ли поставленная задача закрытой.
50+70+60=180; 60+60+50=170, ,следовательно, это открытая задача второго типа. Введем фиктивного потребителя =В4, потребность в грузе которого примем равной =180 –170=10, цены единичных перевозок от поставщиков фиктивному потребителю считаем равными нулю, т.е. . Задача становится закрытой, ей соответствует таблица 12.
Составим начальный план методом наименьшей стоимости.
Делаем поставку в клетку (1;3) x13=50, исключаем из рассмотрения первую строку и третий столбец (можно было сделать эту поставку и в (2;4)). Для клетки (2;2) x22=60, во
втором столбце ставим прочерк, у остается 10 единиц груза. Отдаем их , x21=10. У остается потребность 50 единиц, запишем их в (1;1), x31=50. Тогда оставшиеся 10
Таблица 12.
180 180 |
|||||
60 |
60 |
50 |
10 |
||
|
50 |
3
|
3
|
2 |
0
|
|
70 |
4 |
3 |
2 |
0 |
|
60 |
6 |
7 |
4 |
0 |
единиц у пойдут , x34=10. Начальный план записан в таблице 13.
Таблица 13. План.
|
|||||
|
3 — + |
3 — |
2 -50 |
0 — |
0 |
|
4 10 - |
3 60 |
2 +0 |
0 — |
0 |
|
6 50 |
7 — |
4 — |
0 10 |
2 |
Vj |
4 |
3 |
2 |
-2 |
|
F(Х1)=
Проверим количество заполненных клеток. Для нашей задачи их число должно составлять 3+4–1=6, а в нашем плане только 5, т.е. план вырожден. Поставим 0 в любую пустую клетку, не образующую цикла с уже заполненными клетками, например в (2;3). (Нельзя заполнить нулем клетки (2;4), т.к. образуется цикл (2;4) (3;4) (3;1) (2;1) (2;4) или (2;3) цикл (3;2) (3;1) (2;1) (2;2) (3;2))
Проверим оптимальность полученного плана.
Определим потенциалы, полагая U1 =0. Для заполненных клеток:
(1;3): , V3=2;
(3;2): U2+2= 2, U2 = 0;
(2;2): 0+ V2= 3, V2= 3;
(2;1): 0+ V1=4, V1=4;
(3;1): U3 +4= 6, U3= 2;
(4;1): U4+2 = 0, U4= –2.
Найдем оценки пустых клеток:
Поскольку среди оценок есть отрицательная, план может быть улучшен.
Для клетки (1;1) строим цикл пересчета, расставляем знаки в вершинах цикла. Определяем =min{10;60}=10, прибавляем это значение к перевозкам в клетках, помеченных знаком «+», вычитаем из перевозок в клетках, имеющих знак «–». Получаем новый план X2, представленный в таблице 14.
Таблица 14. План X2.
|
|||||
|
3 10 + |
3 — |
2 - 40 |
0 — |
0 |
|
4 — |
3 60 |
2 10 |
0 — |
0 |
|
6 50 - |
7 — |
4 + — |
0 10 |
3 |
Vj |
3 |
3 |
2 |
-3 |
|
=+=620+10(-1)=610.
Проверим оптимальность плана X2.
Для заполненных клеток, считая U1 =0, определяем потенциалы:
(1;1): 0+V1=3, V1=3;
(1;3): , V3=2;
(3;2): U2+2= 2, U2 = 0;
(2;2): 0+ V2= 3, V2= 3;
(3;1): U3 +3= 6, U3= 3;
(4;1): U4+3 = 0, U4= –3.
Для пустых клеток найдем оценки:
Поскольку одна из оценок отрицательна, план может быть улучшен.
Строим цикл для клетки (3;3). =min{40;50}=40. План представлен в табл.15.
Таблица 15. План .
|
|||||
|
3 50 |
3 — |
2 — |
0 — |
0 |
|
4 — |
3 60 |
2 10 |
0 — |
1 |
|
6 10 |
7 — |
4 40 |
0 10 |
3 |
Vj |
3 |
2 |
1 |
-3 |
|
=+=610+40(-1)=570.
Проверим оптимальность плана X3.
Найдем потенциалы: U1 =0,
(1;1): 0+V1=3, V1=3;
(3;1): U3 +3= 6, U3= 3;
(3;3): 3+ V3= 4, V3= 1;
(3;4): 3+V4=0, V4=3;
(2;3): U2+1=2, U2=1;
(2;1): 1+V2 = 3, V2=2.
Оценки пустых клеток:
Для плана X3 условие оптимальности (8) выполняется, следовательно, план X3 является оптимальным.
Запишем ответ задачи:
X3=.
Поскольку последний столбец оптимального плана соответствует фиктивному потребителю, из окончательного ответа он должен быть исключен. Отброшенное значение x34=10 означает, что 10 единиц груза поставщика А3 останутся нераспределенными. Окончательный ответ —
, F (X*)=570.