Теория графов 3 (стр. 3 из 3)
Присвоим первому поставщику потенциал U1 =0. От первого поставщика продукт направляют первому и второму потребителям, следовательно, V1=U1+c11=0+3=3; V2=0+5=5. Зная потенциал второго потребителя, найдем потенциал второго поставщика U2=V2.-c22=5-4=1. потенциал третьего потребителя V3=1+7=8. потенциал третьего поставщика U3= 8-6=2. Потенциал четвертого потребителя V4= 2+5=7. Вычислить потенциалы, помещаем в ( табл.3).
Проверим первоначальный план на оптимальность. План считывается оптимальным, если для всех свободных ячеек выполняется условие:
Осуществляем проверку:
U1+с13=0+6=6<8 – не выполняется, т.е. если бы продукт отправлялся от первого поставщика к третьему потребителю, то его цена у первого поставщика была бы ниже, чем в первоначальном плане.
Рассчитанные значения заносятся в свободные ячейки (табл.3).
таблицы 3
Итерация 1. целевая функция=2590.
| Поставщики | Потребитель | Запас | ||||
| 1 | 2 | 3 | 4 | |||
| V1=3 | V2=0 | V3=3 | V4=2 | |||
| 1 | U1=0 | 3   150 | 5 5 | 6 6 | 2  20 | 170 |
| 2 | U2=-4 |  6 2 | 4 230 |  4 20 | 5 1 | 250 |
| 3 | U3=-3 | 5 2 | 4 1 | 6  140 | 5 40 | 180 |
| Спрос | 150 | 230 | 160 | 60 | 600 | |
Для улучшения плана (целевая функция = 2690) необходимо переместить перевозку в ячейку, где условие оптимальности нарушено больше всего, т.е. разность Vj-(Ui+cij) максимальна (ячейка 1.4).
Перемещение производится та, чтобы по отношению к выбранной ячейки образоваться связку. Для этого необходимо провести замкнутую ломанную линию, состоящею из горизонтальных и вертикальных линий, в которой одной из вершин полученного многоугольника является свободная ячейка, а остальные вершины должны находиться в занятых ячейках.
Далее каждое ячейке в связке поочередно присваивается знаки плюс и минус, начиная со свободной. Из ячеек со знаком минус перемещаем перевозки в ячейки со знаком плюс. Чтобы не получить отрицательных перевозок, перемещаем наименьшее количество продукта, которое находится в ячейках связки со знаком минус.
Последовательное улучшение плана в таблицах 3-5.
таблицы 4
Итерация 2. целевая функция=2570.
| Поставщики | Потребитель | Запас | ||||
| 1 | 2 | 3 | 4 | |||
| V1=3 | V2=1 | V3=3 | V4=2 | |||
| 1 | U1=0 | 3  130 | 5 5 | 6 6 | 2 40 | 170 |
| 2 | U2=-3 | 6 20 | 4 230 | 7 4 | 5 2 | 250 |
| 3 | U3=-3 |  5 2 | 4 1 | 6 160 | 5 20 | 180 |
| Спрос | 150 | 230 | 160 | 60 | 600 | |
таблицы 5
Итерация 3. целевая функция=2550.
| Поставщики | Потребитель | Запас | ||||
| 1 | 2 | 3 | 4 | |||
| V1=3 | V2=1 | V3=4 | V4=2 | |||
| 1 | U1=0 | 3 110 | 5 5 | 6 6 | 2 60 | 170 |
| 2 | U2=-3 | 6 20 | 4 230 | 7 4 | 5 2 | 250 |
| 3 | U3=-2 | 5 2 | 4 2 | 6 160 | 5 3 | 180 |
| Спрос | 150 | 230 | 160 | 60 | 600 | |