Дана транспортная задача в сетевой постановке. Задача изображена в виде неориентированного связанного графа. На ребрах записаны значения удельных стоимостей cr, на вершинах (в кружках) – значения запасов–потребителей bi. Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.
Решение.
Сущность данной транспортной задачи в сетевой постановке состоит в следующем:
– для каждого пункта сети задан объем производства в нем ;
– для каждой коммуникации задана стоимость перевозки единицы продукта по ней ;
– сеть называется сбалансированной, если суммарный объем производства во всех пунктах равен нулю;
– потоком называется совокупность перевозок по сети ( – перевозка по коммуникации ); соответствующая коммуникация называется базисной;
– необходимо сформировать такой поток по сбалансированной сети, при котором разница между количеством вывозимого и ввозимого в каждый пункт продукта равна объему производства в нем (условие допустимости), а суммарные транспортные расходы минимальны;
– количество перевозок должно быть на одну меньше количества пунктов в сети (условие невырожденности);
– в каждый пункт должна входить (или из каждого пункта должна выходить) хотя бы одна перевозка.
Наша задача является сбалансированной, так как суммарное производство (положительные значения 20+70+15+60+10+15=190) равно суммарному потреблению (отрицательные значения 40+50+40+60=190).
Решение:
70 70 8 0 – 70
2 20 20 3 0 – 20
3 15 35 5 20 2 15
4 60 60 5 0 – 60
5 10 100+5 6,7 60+35 4,3 10
6 –60 40 9 100 5 –60
7 0 5 10 5 5 0
8 –40 30 10 70 1 –40
9 –40 0 – 40 6 –40
10 –50 0 – 5+30+15 7,8,11 –50
11 15 15 10 0 – 15
Из каждого пункта продукт вывозится и/или ввозится. Следовательно, начальный допустимый невырожденный план построен. Перечень перевозок и их оценка представлены в таблице:
Перевозка Начальный пункт Конечный пункт Объем перевозки Удельная стоимость перевозки Общая стоимость перевозки
x18 1 8 70 12 840
x23 2 3 20 3 60
x35 3 5 35 4 140
x45 4 5 60 5 300
x56 5 6 100 3 300
x57 5 7 5 2 10
x69 6 9 40 8 320
x7,10 7 10 5 4 20
x8,10 8 10 30 3 90
x11,10 11 10 15 8 120
Сумма: 2200
Общая стоимость перевозок начального плана равна 2200.
Проверяем полученный начальный план на оптимальность. Для этого вычисляются потенциалы пунктов. Начальный потенциал выбирается произвольно и он назначается произвольному пункту. Через базисные звенья определяются потенциалы каждого последующего пункта: к потенциалу начального пункта прибавляется удельная стоимость перевозки, если перевозка попутная, и вычитается, если перевозка встречная.
Назначаем потенциал пункта 1 равным нулю. Отсюда последовательно получаем:
V1 = 0;
V8 = V1 + c18 = 0 + 12 = 12;
V10 = V8 + c8,10 = 12 + 3 = 15;
V11 = V10 – c11,10 = 15 – 8 = 7;
V7 = V10 – c7,10 = 15 – 4 = 11;
V5 = V7 – c57 = 11 – 2 = 9;
V6 = V5 + c56 = 9 + 3 = 12;
V9 = V6 + c69 = 12 + 8 = 20;
V4 = V5 – c45 = 9 – 5 = 4;
V3 = V5 – c35 = 9 – 4 = 5;
V2 = V3 – c23 = 5 – 3 = 2.
Проверка оптимальности заключается в том, что для небазисных (свободных) звеньев модуль разности потенциалов начального и конечного пунктов не должен превышать соответствующую удельную стоимость перевозки.
Получаем:
1) звено 1-4; |0–4|=4<6; условие оптимальности выполняется;
2) звено 1-11; |0–7|=7<11; условие оптимальности выполняется;
3) звено 2-7; |2–11|=9<15; условие оптимальности выполняется;
4) звено 3-6; |5–12|=7<17; условие оптимальности выполняется;
5) звено 6-7; |12–11|=1<3; условие оптимальности выполняется;
6) звено 6-10; |12–15|=3<6; условие оптимальности выполняется;
7) звено 8-11; |12–7|=5<11; условие оптимальности выполняется;
8) звено 9-10; |20–15|=5<20; условие оптимальности выполняется.
Начальный опорный план оказался оптимальным. В дальнейшей оптимизации методом потенциалов нет необходимости. Общая стоимость перевозок оптимального плана равна 2200.
