Оптимальное решение транспортной задачи.
Таблица 3 |
U1 U2 U3 |
Потребители | |||||
Поставщики | - | ||||
- | - | - | |||
- | - |
V1 V2 V3 V4 |
Каждому поставщику и потребителю ставится в соответствии переменная, называемая потенциалом.(Ui - для поставщика, Vj - для потребителя).
Для каждой заполненной клетки составляем уравнение вида Сij=Ui+Vj. Из полученной системы, методом подбора, определяются значения переменных Ui и Vj.
U1+ V2=13; U1=0, V2=13;
U1+ V3=6; U1=0, V3=6;
U1+ V4=11; U1=0, V4=11;
U2+ V2=2; U2=-11, V2=13;
U3+ V1=4; U3=-6, V1=10;
U3+ V2=7; U3=-6, V2=13.
Используя полученные значения переменных Ui и Vj для пустых клеток, определяется величина псевдостоимости Zij=Ui+Vj, а затем для этих пустых клеток вычисляем величина d, как разность между исходной стоимостью и найденной dij = Cij – Zij.
Z11=U1+ V1=10; δ11=C11-Z11=-5;
Z21=U2+ V1=-1; δ21=C21-Z21 =10;
Z23=U2+ V3=-5; δ23=C23-Z23=8;
Z33=U3+ V3=0; δ33=C33-Z33=12;
Z24=U2+ V4=0; δ24=C24-Z24=10;
Z34=U3+ V4=5; δ34=C34-Z34=3;
Если среди полученных dij нет отрицательных, то получено оптимальное решение, при этом L®min.
Так как в таблице 3 имеется отрицательное значение δ11=-5, то оптимальное решение не найдено, следовательно, строим цикл.
Цикл – это прямоугольный многоугольник, одна из вершин которого находится в выбранной незаполненной клетке, где dij имеет максимальное значение среди отрицательных, остальные вершины находятся в заполненных клетках.
|
|
Вершины цикла маркируются последовательно чередующимися знаками "+" и "-", начиная с исходной величины. В исходной вершине ставим знак "+".
Находим минимальный объем перевозимого груза Хij среди отрицательных величин. Эта величина груза списывается со всех отрицательных вершин и добавляется к положительным вершинам, при этом состав клеток изменяется.
Таблица 4 |
Потребители | |||||||
Поставщики |
- |
| |||||
- | - | - | |||||
|
| - | - |
Таблица 5 |
Потребители | |||||
| |||||
Поставщики | - | ||||
- | - | - | |||
- | - |
V1 V2 V3 V4 |
Для таблицы 5 повторяем шаги решения.
Составим уравнения Cij=Ui+Vj для каждой заполненной клетки и определим значения Ui и Vj:
U1+ V1=5; U1=0, V1=5;
U1+ V3=6; U1=0, V3=6;
U1+ V4=11; U1=0, V4=11;
U2+ V2=2; U2=-6, V2=8;
U3+ V1=4; U3=-1, V1=5;
U3+ V2=7; U3=-1, V2=8.
Используя полученные значения переменных, определим величины псевдо стоимости и значения δ для пустых клеток:
Z21=U2+ V1=-1; δ21=C21-Z21=10;
|
|
Z12=U1+ V2=8; δ12=C12-Z12 =5;
Z23=U2+ V3=0; δ23=C23-Z23=3;
Z33=U3+ V3=5; δ33=C33-Z33=7;
Z24=U2+ V4=5; δ24=C24-Z24=5;
Z34=U3+ V4=10; δ34=C34-Z34=-2;
Таблица 6 |
Потребители | |||||||
Поставщики |
| - |
| ||||
- | - | - | |||||
- 4 | - |
- |
Таблица 7 |
Потребители | |||||
| |||||
Поставщики | - | - | |||
- | - | - | |||
- |
V1 V2 V3 V4 V4 |
Для таблицы 7 повторяем шаги решения.
Составим уравнения Cij=Ui+Vj для каждой заполненной клетки и определим значения Ui и Vj:
U1+ V1=5; U1=0, V1=5
U1+ V3=6; U1=0, V3=6
U2+ V2=2; U2=-6, V2=8
U3+ V2=7; U3=-1, V2=8
U3+ V4=8; U3=-1, V4=9
Используя полученные значения переменных, определим величины псевдо стоимости и значения δ для пустых клеток:
Z21=U2+ V1=-1; δ21=C21-Z21=10;
Z12=U1+ V2=8; δ12=C12-Z12 =5;
Z23=U2+ V3=-7; δ23=C23-Z23=10;
Z33=U3+ V3=5; δ33=C33-Z33=7;
Z14=U1+ V4=9; δ14=C14-Z14=2;
Z24=U2+ V4=3; δ24=C24-Z24=7;
В таблице 7 все δ > 0, следовательно, она является оптимальным решением транспортной задачи.
Определим стоимость всего плана перевозок.
Вывод: оптимальный план перевозок обеспечивающий все потребности приемных пунктов при наименьших затратах, который составляет 655 ед., достигнут.
|
|
Дата добавления: 2016-01-03; просмотров: 18; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!