Решение транспортных задач методами линейного программирования

Первой вершине присваивается  потенциал V₁ = 100 ( см. рис. 2).

3.Через занятые базисные звенья определяют потенциалы каждой последующей вершины V_j+1, связанной с предыдущей вершиной V_j по формулам:

перевозка “попутная”

V_j+1 = V_j + c_j,j+1,              (11)

перевозка “встречная”

V_j+1 = V_j - c_j,j+1,               (12)

где c_j,j+1 – критерий расстояния (или другой показатель критерия оптимизации) на заданном звене.

4. Пункт 3 повторяется до тех пор, пока всем вершинам сети не будет присвоен потенциал. Это возможно, если выполняется условие «вырождения» К_з = S – 1. Звенья с фиктивными перевозками рассматриваются как занятые.

Исходя из формулы (11), потенциал  вершины 5 будет равен V₅ = 100 + 15 =115, а потенциал вершины 2 равен V₂ = 100 + 17 = 117. Далее присваиваются потенциалы от вершин 5 и 2. Вершина 5 не имеет связующих (занятых) звеньев ни с одной из вершин сети. Вершина 2 связана с вершиной 6 (V₆ = 117+17 = 134), вершиной 8 (V₈ = 117 + 11 =128), вершиной 11 (V₁₁ = 117+18 = 135) и вершиной 9 (V₉ = 117 +11 = 128). От вершины 11 по формуле (12) определяется потенциал вершины 4 (V₄ = 135 – 25 =110). От вершины 9 определяется потенциал вершины 3 (V₃ = 128 – 9 = 119). От вершины 3 определяются потенциалы вершины 10 (V₁₀ = 119 + 17 = 136) и вершины 7 (V₇ = 119 + 16 = 135). Присвоенные потенциалы обозначены подчеркнутой цифрой около вершины (рис.2).

5. Полученный начальный план проверяется на оптимальность. План считается оптимальным, если соблюдаются следующие условия:

/V_j+1 – V_j /≤ c_j,j+1, при x_j,j+1 = 0 (звено свободно),               (13)

/ V_j+1 – V_j /= c_j,j+1, при x_j,j+1 > 0 (по звену назначена перевозка).

В нашем примере  для звена 5–2 условие оптимальности  выполняется (/115 – 117/ = 2 < 24), а для  звена 5–6 – не выполняется (/134 – 115/ = 19 > 12) и нарушение составляет 7. Аналогично, имеются нарушения на звене 1–7 (/135 – 100/ = 35 > 28) и звене 8–4 (/110 – 128/ = 18 > 16). Нарушения соответственно 7 и 2. Для остальных звеньев условие оптимальности выполняется. Данный план не является оптимальным, так как имеются нарушения условия оптимальности [см. формулу (13)].

6. Корректировка плана производится в следующей последовательности:

а) строится замкнутый контур, состоящий  из звена с наибольшим нарушением, и базисных звеньев: (5–6) – (6–2) – (2–1) – (1–5);

б) выбирается направление  движения по контуру от вершины звена с нарушением, имеющей меньший потенциал, к вершине с большим потенциалом (от вершины 5 к вершине 6) и далее по выбранному контуру;

в) определяется минимальная встречная перевозка  в данном контуре: min {50;30} = 30 в звене (1–2). Это значение принимается для дальнейшей корректировки;

г) “обходится”  контур по выбранному направлению и  вычитается найденное значение из всех встречных потоков, прибавляется к  попутным. При этом звено 2–1 освобождается  от перевозки, а на звеньях вне  контура перевозки остаются без изменений (рис. 3).16 20 50 18

Рис. 3. Скорректированный  план перевозок (первая корректировка)

Значение целевой  функции составит

L = 100· 15 + 30·  12 + 20· 17 + 30· 11 + 30· 11 + 40· 18 + 50·  25 + 20· 9 + 70· 17 +  60· 16 = =7160 ваг-км.

Согласно алгоритму решения транспортной задачи, представленной в сетевой форме, методом потенциалов (пункты 1–5), данный скорректированный план также проверяется на оптимальность [формулы (10–13)].

В данном плане  имеется нарушение условия оптимальности [см. формулы (13)] в звене 4–8 (/121 – 103/ = 18 > 16). Поэтому согласно пункту 6 алгоритма решения транспортной задачи, представленной в сети, методом потенциалов корректируется план перевозок (рис. 4).

 

Рис. 4. Скорректированный  план перевозок (вторая корректировка)

После проверки по условиям оптимальности видно, что  данный план является оптимальным (отсутствуют  нарушения условий оптимальности).

Конечное значение целевой функции составит

L_кон = 100· 15 + 30· 12 + 20·17 + 30· 11 + 70· 18 + 30· 16 + 2· 25 + 20· 9 + 70· 17 + 60· 16 = 7100 ваг-км.

Как видно из расчетов, итоговый план перевозок  улучшен по сравнению с исходным на 270 ваг-км (L_нач – L_кон = 7370 – 7100).

ревозок) относительно начального плана на 20 ваг-км (5790 – 5770 = 20).

 

 

Пример № 3.

Транспортная задача закрытого типа, представленная в матричной форме, с ограничениями пропускной способности

Транспортные задачи без ограничений на практике встречаются  редко. Гораздо чаще, при решении  транспортных задач, приходится иметь  дело с ограничениями пропускной способности в тех или иных клетках (в задачах, представленных в матричной форме) или звеньев (в задачах, представленных в сетевой форме).

Пропускной способностью клеток или звеньев называется максимально  возможное количество перевозок, которое  можно перевести в данной клетке или по звену.

Решение транспортных задач  с ограничениями производится аналогично решению задачи без ограничений. Однако имеется ряд особенностей. Рассмотрим это на примере.

 

Для транспортной задачи, представленной в матричной  форме с ограничениями пропускной способности, необходимо найти оптимальный план, при котором будет выполняться условие наименьшего суммарного объема тонно-километровой работы. Для этого необходимо выполнить следующие действия:

• составить математическую модель задачи;
• составить начальный план, проверить по условию “вырождения”, рассчитать суммарный объем тонно-километровой работы;
• решить задачу методом потенциалов, рассчитать суммарный объем тонно-километровой работы оптимального плана;
• сравнить начальный и оптимальный варианты.

Исходные данные к задаче приведены в табл.11.

Таблица 11

Объем отправления  и потребления грузов

Станция отправления	Ресурсы, тыс. т	Станция назначения
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс. т
		90	90	190	130	170	80	100	100	50
А1	200	70	40	105	65	200	75	20* 60**	80	45
А2	250	25	30	45	40	25	65	30	15 60	25
А3	100	75	35	75	120	80	40	70	20 40	80
А4	250	15 55	45	10	20	65	110	75	30	20
А5	200	15 25	15	15	20 35	25	80	20	70	85

Примечания: 20* – расстояние перевозки от i-й  станции отправления до j-й станции  назначения, км, 60** – ограничение пропускной способности.

Решение начинается с составления математической модели задачи. Целевой функцией является минимальная тонно-километровая работа, которая определяется по формуле

min ,

где l_ij — расстояние перевозки от i-й станции отправления до j-й станции назначения;

x_ij — объем перевозки от i-й станции отправления до j-й станции назначения.

 

Система ограничений для  данной задачи

, (i = 1,2,...,5), 

 

, (j = 1,2,...,9),

x_ij > = 0, (i = 1,2,...,5; j = 1,2,...,9).

 

 

Для решения  задачи составляется начальный план. Исходный опорный план составляется с помощью одного из методов (см. пример № 1).

 

Таблица 12

Исходный опорный  план

Станция отправления	Ресурсы, тыс. т	Станция назначения
		В1	В2		В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс. т
		90	90	190		130	170	80	100	100	50
А1	200	70	40 90	105		65	200	75	20 60 60	80	45 50
А2	250	25 90	30	45		40	25 100	65	30	15 60 60	25
А3	100	75	35	75		120	80	40 60	70	20 40 40	80
А4	250	15 55	45	10 190		20 60	65	110	75	30	20
А5	200	15 25	15	15		20 35 70	25 70	80 20	20 40	70	85

В данном примере  воспользуемся методом наименьшего критерия в строке. Назначенные перевозки записываются в правом нижнем углу клетки и подчеркиваются. В клетке с ограничением пропускной способности не может быть записана перевозка большая, чем само ограничение (клетки A₁B₇, A₂B₈, A₃B₈, A₅B₄). Исходный опорный план, полученный с помощью этого метода представлен в табл.12.

В полученном плане в клетке A₅B₄ назначенная перевозка превышает пропускную способность (70 > 35). Эта перевозка была назначена для того, чтобы удовлетворить потребность столбца B_4. Следовательно, данный план необходимо скорректировать. Строится контур корректировки (A₅B₃ – A₅B₄ – A₄B₄ – A₄B₃). В данном контуре необходимо снять лишнюю перевозку в размере 35 в клетке A₅B₄. Для этого значения назначенных перевозок в клетках вершин контура изменяют на необходимую величину (35), поочередно отнимая и прибавляя выбранное значение к существующим значениям перевозок в клетках вершин контура. Получаем скорректированный исходный опорный план (табл.13).

Таблица 13

Скорректированный исходный опорный план

Станция отправления	Ресурсы, тыс. т	Станция назначения
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс. т
		90	90	190	130	170	80	100	100	50
А1	200	70	40 90	105	65	200	75	20 60 60	80	45 50
А2	250	25 90	30	45	40	25 100	65	30	15 60 60	25
А3	100	75	35	75	120	80	40 60	70	20 40 40	80
А4	250	15 55	45	10 155	20 95	65	110	75	30	20
А5	200	15 25	15	15 35	20 35 35	25 70	80 20	20 40	70	85