Транспортная задача с ограничениями на пропускную способность
Транспортная задача
Задача коммивояжера
Задача о назначениях
Метод Гомори
Симплекс-метод
Распределительный метод
Метод потенциалов
Метод Фогеля
Открытые и закрытые задачи

Распределительный метод. Пример решения транспортной задачи

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
 Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента.
 Прежде всего отыскивается какое-то решение задачи — исходный опорный план. Затем посредством специальных показателей опорный план проверяется на оптимальность. Если план оказывается не оптимальным, переходят к другому плану. При этом второй и последующие планы должны быть лучше предыдущего. Так за несколько последовательных переходов от не оптимального плана приходят к оптимальному.


 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2
 

 3
 

 150
 

 2
 

 3
 

 4
 

 5
 

 4
 

 250
 

 3
 

 2
 

 5
 

 6
 

 5
 

 230
 

 4
 

 1
 

 2
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Проверим необходимое и достаточное условие разрешимости задачи.
 ∑ a = 150 + 250 + 230 + 220 = 850
 ∑ b = 200 + 200 + 250 + 200 = 850
 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
 Занесем исходные данные в распределительную таблицу.

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2
 

 3
 

 150
 

 2
 

 3
 

 4
 

 5
 

 4
 

 250
 

 3
 

 2
 

 5
 

 6
 

 5
 

 230
 

 4
 

 1
 

 2
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность.
  Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(cij), способу Фогеля и по способу Лебедева-Тихомирова.
 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[180]
 

 5
 

 4[70]
 

 250
 

 3
 

 2
 

 5
 

 6[100]
 

 5[130]
 

 230
 

 4
 

 1[200]
 

 2[20]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
 2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
 Значение целевой функции для этого опорного плана равно:
 F(x) = 2*150 + 4*180 + 4*70 + 6*100 + 5*130 + 1*200 + 2*20  = 2790
  Проверка опорного плана на оптимальность. Чтобы установить является ли опорный план оптимальным, надо проверить, как повлияет на величину целевой функции любое возможное перераспределение поставок.
 План распределения поставок будет оптимальным лишь в том случае, когда целевая функция имеет минимальное значение, т.е. когда дальнейшее уменьшение затрат на поставку будет невозможно.
 Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина Δ ij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки х ij=1 от поставщика Аi к потребителю В j.
 При этом должно быть произведено такое изменение остальных поставок, чтобы получившаяся совокупность поставок не нарушала баланса спроса и поставок транспортной задачи.
 Величина Δ ij называется оценкой свободной клетки (или характеристика).
 В исходном решении задачи имеются клетки свободные от поставок.
 Необходимо вычислить значение оценок Δij для этих свободных от поставок клеток. С этой целью для каждой свободной клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.).
  Под циклом пересчета (цепью) понимается замкнутая ломаная линия. Вершинами цикла (цепи) являются клетки таблицы, проще – вершины лежат в клетках таблицы.
 Причем одна из вершин находится в свободной от поставки клетке, в той, для которой определяется оценка Δij . Все другие вершины находятся в базисных клетках, т.е. клетках, занятых поставками.
 Вершины, в которых поставки при перераспределении увеличиваются, отмечаются плюсом и называются положительными вершинами и, наоборот, вершины, в которых поставки при перераспределении уменьшаются отмечаются минусом и называются отрицательными вершинами.
 В цикле знаки по вершинам расставляют начиная с вершины, лежащей в свободной клетке, для которой определяется Δij . В нее записывают знак плюс, затем знаки по вершинам чередуются: минус, плюс , минус, плюс и т. д., независимо от того, расставляют ли их по часовой стрелке или в обратном направлении. Таким образом, в цикле всегда насчитывается одинаковое число положительных и отрицательных вершин.
 Следующий этап решения транспортной задачи заключается в улучшении опорного плана.
 Если при каком-то опорном плане оказывается несколько свободных клеток с отрицательными оценками Δij, то за один переход к лучшему плану можно занять поставкой только одну клетку – ту, которая обеспечивает наибольшее снижение целевой функции.
 4. Определяем оценку для каждой свободной клетки.
 В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5[+]
 

 3
 

 2[150][-]
 

 3
 

 150
 

 2
 

 3
 

 4[180][-]
 

 5
 

 4[70][+]
 

 250
 

 3
 

 2
 

 5
 

 6[100][+]
 

 5[130][-]
 

 230
 

 4
 

 1[200][-]
 

 2[20][+]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (1,1; 1,3; 3,3; 3,4; 2,4; 2,2; 4,2; 4,1; ).
 Оценка свободной клетки равна Δ11 = (5) - (2) + (6) - (5) + (4) - (4) + (2) - (1) = 5
 В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3[+]
 

 2[150][-]
 

 3
 

 150
 

 2
 

 3
 

 4[180][-]
 

 5
 

 4[70][+]
 

 250
 

 3
 

 2
 

 5
 

 6[100][+]
 

 5[130][-]
 

 230
 

 4
 

 1[200]
 

 2[20]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (1,2; 1,3; 3,3; 3,4; 2,4; 2,2; ).
 Оценка свободной клетки равна Δ12 = (3) - (2) + (6) - (5) + (4) - (4) = 2
 В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150][-]
 

 3[+]
 

 150
 

 2
 

 3
 

 4[180]
 

 5
 

 4[70]
 

 250
 

 3
 

 2
 

 5
 

 6[100][+]
 

 5[130][-]
 

 230
 

 4
 

 1[200]
 

 2[20]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (1,4; 1,3; 3,3; 3,4; ).
 Оценка свободной клетки равна Δ14 = (3) - (2) + (6) - (5) = 2
 В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3[+]
 

 4[180][-]
 

 5
 

 4[70]
 

 250
 

 3
 

 2
 

 5
 

 6[100]
 

 5[130]
 

 230
 

 4
 

 1[200][-]
 

 2[20][+]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (2,1; 2,2; 4,2; 4,1; ).
 Оценка свободной клетки равна Δ21 = (3) - (4) + (2) - (1) = 0
 В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[180]
 

 5[+]
 

 4[70][-]
 

 250
 

 3
 

 2
 

 5
 

 6[100][-]
 

 5[130][+]
 

 230
 

 4
 

 1[200]
 

 2[20]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (2,3; 2,4; 3,4; 3,3; ).
 Оценка свободной клетки равна Δ23 = (5) - (4) + (5) - (6) = 0
 В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[180][-]
 

 5
 

 4[70][+]
 

 250
 

 3
 

 2[+]
 

 5
 

 6[100]
 

 5[130][-]
 

 230
 

 4
 

 1[200][-]
 

 2[20][+]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (3,1; 3,4; 2,4; 2,2; 4,2; 4,1; ).
 Оценка свободной клетки равна Δ31 = (2) - (5) + (4) - (4) + (2) - (1) = -2
 В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[180][-]
 

 5
 

 4[70][+]
 

 250
 

 3
 

 2
 

 5[+]
 

 6[100]
 

 5[130][-]
 

 230
 

 4
 

 1[200]
 

 2[20]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (3,2; 3,4; 2,4; 2,2; ).
 Оценка свободной клетки равна Δ32 = (5) - (5) + (4) - (4) = 0
 В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[180][+]
 

 5
 

 4[70][-]
 

 250
 

 3
 

 2
 

 5
 

 6[100][-]
 

 5[130][+]
 

 230
 

 4
 

 1[200]
 

 2[20][-]
 

 3[+]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (4,3; 4,2; 2,2; 2,4; 3,4; 3,3; ).
 Оценка свободной клетки равна Δ43 = (3) - (2) + (4) - (4) + (5) - (6) = 0
 В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[180][+]
 

 5
 

 4[70][-]
 

 250
 

 3
 

 2
 

 5
 

 6[100]
 

 5[130]
 

 230
 

 4
 

 1[200]
 

 2[20][-]
 

 3
 

 6[+]
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (4,4; 4,2; 2,2; 2,4; ).
 Оценка свободной клетки равна Δ44 = (6) - (2) + (4) - (4) = 4
 Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (3,1;) равные: (-2).
  Переход от неоптимального опорного плана к лучшему .
  Переход от неоптимального опорного плана к лучшему . Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (3;1) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.
 Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 130. Прибавляем 130 к объемам грузов, стоящих в плюсовых клетках и вычитаем 130 из Х ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[130]
 

 5
 

 6[100]
 

 5
 

 230
 

 4
 

 1[70]
 

 2[150]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 F(x) = 2*150 + 4*50 + 4*200 + 2*130 + 6*100 + 1*70 + 2*150  = 2530
 4. Определяем оценку для каждой свободной клетки.
 В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5[+]
 

 3
 

 2[150][-]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[130][-]
 

 5
 

 6[100][+]
 

 5
 

 230
 

 4
 

 1[70]
 

 2[150]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (1,1; 1,3; 3,3; 3,1; ).
 Оценка свободной клетки равна Δ11 = (5) - (2) + (6) - (2) = 7
 В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3[+]
 

 2[150][-]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[130][-]
 

 5
 

 6[100][+]
 

 5
 

 230
 

 4
 

 1[70][+]
 

 2[150][-]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (1,2; 1,3; 3,3; 3,1; 4,1; 4,2; ).
 Оценка свободной клетки равна Δ12 = (3) - (2) + (6) - (2) + (1) - (2) = 4
 В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150][-]
 

 3[+]
 

 150
 

 2
 

 3
 

 4[50][+]
 

 5
 

 4[200][-]
 

 250
 

 3
 

 2[130][-]
 

 5
 

 6[100][+]
 

 5
 

 230
 

 4
 

 1[70][+]
 

 2[150][-]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (1,4; 1,3; 3,3; 3,1; 4,1; 4,2; 2,2; 2,4; ).
 Оценка свободной клетки равна Δ14 = (3) - (2) + (6) - (2) + (1) - (2) + (4) - (4) = 4
 В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3[+]
 

 4[50][-]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[130]
 

 5
 

 6[100]
 

 5
 

 230
 

 4
 

 1[70][-]
 

 2[150][+]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (2,1; 2,2; 4,2; 4,1; ).
 Оценка свободной клетки равна Δ21 = (3) - (4) + (2) - (1) = 0
 В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50][-]
 

 5[+]
 

 4[200]
 

 250
 

 3
 

 2[130][+]
 

 5
 

 6[100][-]
 

 5
 

 230
 

 4
 

 1[70][-]
 

 2[150][+]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (2,3; 2,2; 4,2; 4,1; 3,1; 3,3; ).
 Оценка свободной клетки равна Δ23 = (5) - (4) + (2) - (1) + (2) - (6) = -2
 В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[130][-]
 

 5[+]
 

 6[100]
 

 5
 

 230
 

 4
 

 1[70][+]
 

 2[150][-]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (3,2; 3,1; 4,1; 4,2; ).
 Оценка свободной клетки равна Δ32 = (5) - (2) + (1) - (2) = 2
 В свободную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50][+]
 

 5
 

 4[200][-]
 

 250
 

 3
 

 2[130][-]
 

 5
 

 6[100]
 

 5[+]
 

 230
 

 4
 

 1[70][+]
 

 2[150][-]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (3,4; 3,1; 4,1; 4,2; 2,2; 2,4; ).
 Оценка свободной клетки равна Δ34 = (5) - (2) + (1) - (2) + (4) - (4) = 2
 В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[130][+]
 

 5
 

 6[100][-]
 

 5
 

 230
 

 4
 

 1[70][-]
 

 2[150]
 

 3[+]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (4,3; 4,1; 3,1; 3,3; ).
 Оценка свободной клетки равна Δ43 = (3) - (1) + (2) - (6) = -2
 В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50][+]
 

 5
 

 4[200][-]
 

 250
 

 3
 

 2[130]
 

 5
 

 6[100]
 

 5
 

 230
 

 4
 

 1[70]
 

 2[150][-]
 

 3
 

 6[+]
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (4,4; 4,2; 2,2; 2,4; ).
 Оценка свободной клетки равна Δ44 = (6) - (2) + (4) - (4) = 4
 Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (2,3;4,3;) равные: (-2).
 Поскольку имеются оценки клеток с одинаковыми по величине значениями, то для перехода к лучшему плану практически может быть занята любая клетка из этих двух.
 Однако, если придерживаться принципа достижения наибольшего снижения целевой функции за один очередной переход, то в данном случае надо проанализировать, каково будет это общее снижение при занятии поставкой каждой клетки.
  Переход от неоптимального опорного плана к лучшему .
  Переход от неоптимального опорного плана к лучшему . Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (2;3) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.
 Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij , стоящих в минусовых клетках. В результате получим новый опорный план.

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4
 

 5[50]
 

 4[200]
 

 250
 

 3
 

 2[180]
 

 5
 

 6[50]
 

 5
 

 230
 

 4
 

 1[20]
 

 2[200]
 

 3
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 F(x) = 2*150 + 5*50 + 4*200 + 2*180 + 6*50 + 1*20 + 2*200  = 2430
  Переход от неоптимального опорного плана к лучшему . Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (4;3) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.
 Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 1) = 70. Прибавляем 70 к объемам грузов, стоящих в плюсовых клетках и вычитаем 70 из Хij , стоящих в минусовых клетках. В результате получим новый опорный план.

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[200]
 

 5
 

 6[30]
 

 5
 

 230
 

 4
 

 1
 

 2[150]
 

 3[70]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 F(x) = 2*150 + 4*50 + 4*200 + 2*200 + 6*30 + 2*150 + 3*70  = 2390
 Выбираем из альтернативных вариантов (2,3;4,3;) тот, чья функция затрат будет минимальной: Fx = 2390.
 4. Определяем оценку для каждой свободной клетки.
 В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5[+]
 

 3
 

 2[150][-]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[200][-]
 

 5
 

 6[30][+]
 

 5
 

 230
 

 4
 

 1
 

 2[150]
 

 3[70]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (1,1; 1,3; 3,3; 3,1; ).
 Оценка свободной клетки равна Δ11 = (5) - (2) + (6) - (2) = 7
 В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3[+]
 

 2[150][-]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[200]
 

 5
 

 6[30]
 

 5
 

 230
 

 4
 

 1
 

 2[150][-]
 

 3[70][+]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (1,2; 1,3; 4,3; 4,2; ).
 Оценка свободной клетки равна Δ12 = (3) - (2) + (3) - (2) = 2
 В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150][-]
 

 3[+]
 

 150
 

 2
 

 3
 

 4[50][+]
 

 5
 

 4[200][-]
 

 250
 

 3
 

 2[200]
 

 5
 

 6[30]
 

 5
 

 230
 

 4
 

 1
 

 2[150][-]
 

 3[70][+]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (1,4; 1,3; 4,3; 4,2; 2,2; 2,4; ).
 Оценка свободной клетки равна Δ14 = (3) - (2) + (3) - (2) + (4) - (4) = 2
 В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3[+]
 

 4[50][-]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[200][-]
 

 5
 

 6[30][+]
 

 5
 

 230
 

 4
 

 1
 

 2[150][+]
 

 3[70][-]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (2,1; 2,2; 4,2; 4,3; 3,3; 3,1; ).
 Оценка свободной клетки равна Δ21 = (3) - (4) + (2) - (3) + (6) - (2) = 2
 В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50][-]
 

 5[+]
 

 4[200]
 

 250
 

 3
 

 2[200]
 

 5
 

 6[30]
 

 5
 

 230
 

 4
 

 1
 

 2[150][+]
 

 3[70][-]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (2,3; 2,2; 4,2; 4,3; ).
 Оценка свободной клетки равна Δ23 = (5) - (4) + (2) - (3) = 0
 В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[200]
 

 5[+]
 

 6[30][-]
 

 5
 

 230
 

 4
 

 1
 

 2[150][-]
 

 3[70][+]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (3,2; 3,3; 4,3; 4,2; ).
 Оценка свободной клетки равна Δ32 = (5) - (6) + (3) - (2) = 0
 В свободную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50][+]
 

 5
 

 4[200][-]
 

 250
 

 3
 

 2[200]
 

 5
 

 6[30][-]
 

 5[+]
 

 230
 

 4
 

 1
 

 2[150][-]
 

 3[70][+]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (3,4; 3,3; 4,3; 4,2; 2,2; 2,4; ).
 Оценка свободной клетки равна Δ34 = (5) - (6) + (3) - (2) + (4) - (4) = 0
 В свободную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50]
 

 5
 

 4[200]
 

 250
 

 3
 

 2[200][-]
 

 5
 

 6[30][+]
 

 5
 

 230
 

 4
 

 1[+]
 

 2[150]
 

 3[70][-]
 

 6
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (4,1; 4,3; 3,3; 3,1; ).
 Оценка свободной клетки равна Δ41 = (1) - (3) + (6) - (2) = 2
 В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 5
 

 3
 

 2[150]
 

 3
 

 150
 

 2
 

 3
 

 4[50][+]
 

 5
 

 4[200][-]
 

 250
 

 3
 

 2[200]
 

 5
 

 6[30]
 

 5
 

 230
 

 4
 

 1
 

 2[150][-]
 

 3[70]
 

 6[+]
 

 220
 

 Потребности
 

 200
 

 200
 

 250
 

 200
 

 
 

 Цикл приведен в таблице (4,4; 4,2; 2,2; 2,4; ).
 Оценка свободной клетки равна Δ44 = (6) - (2) + (4) - (4) = 4
 Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции Fx невозможно, поскольку она достигла минимального значения.
 Таким образом, последний опорный план является оптимальным.
 Минимальные затраты составят:
 F(x) = 2*150 + 4*50 + 4*200 + 2*200 + 6*30 + 2*150 + 3*70  = 2390
 Если в оптимальном решении задачи имеется несколько оценок равных нулю, то это является свидетельством того, что среди бесчисленного множества решений этой задачи существуют еще решения, являющиеся также оптимальными, поскольку значение целевой функции остается одинаковым — минимальным. Их принято называть альтернативными.
  Примечание. Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп—(m+n—1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 — 361 цикл.
Новое на сайте