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

Начальное значение целевой функции (суммарный объем тонно-километровой работы) составит

F_нач = f (x) = 90 · 40 + 60 · 20 + 50 · 45 + 90 · 25 + 100 · 25 + 60 · 15 + 60 · 40 + 40 · 20 +155 ·10 + 95 · 20 + 35 · 15 + 35 · 20 + 70 · 25 + 20 · 80 + 40· 20 = 24725 тыс. ткм.

Полученный исходный план проверяется на условие “вырождения” [см. формулу (6)]:

N_з £ n + m – 1, где N_з – число занятых базисных клеток.

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

В полученном плане количество клеток N_з = 11, а суммарное число строк и столбцов m + n – 1 = 5 + 9 – 1 = 13. Задача “вырожденная”, необходимо назначить две фиктивные перевозки (в примере – в клетки A₅B₂ и A₄B₈). Клетки с фиктивными перевозками считаются базисными.

Полученный исходный план проверяется на оптимальность. Для этого всем строкам и столбцам присваиваются потенциалы (табл.14).

Таблица 14

Присвоение потенциалов

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

V_j – U_i ≤ c_ij, при x_ij = 0 (клетка свободна),

V_j – U_i = c_ij,  (14)

при a _ij > x_ij > 0 (базисная клетка),

V_j – U_i ≥ c_ij, при x_ij = a _ij (перевозка в клетке равна ограничению), где V_j – потенциал j–го столбца; U_i – потенциал i-й строки; a _ij – ограничение пропускной способности.

В данном исходном плане имеются три клетки с  нарушением условий оптимальности [см. формулу (14)]. Для клетки А₁В₆ разность потенциалов V₆ – U₁ = 180 – 75 = 105, что больше стоимости перевозки в данной клетке, равной 75 единиц. Нарушение первого условия оптимальности составляет Н₁₆ = 105 – 75 = 30. Записываем его в правом верхнем углу матрицы перевозок (табл.14). Аналогично, для клетки А₂В₆ разность потенциалов V₆ – U₂ = 180 – 100 = 80, при стоимости перевозки 65, нарушение первого условия оптимальности составляет Н₂₆ = 80 – 65 = 15. В клетке А₃В₈ определено нарушение третьего условия оптимальности, которое составляет Н₃₈ = 25.

Так как данный исходный план не является оптимальным, он может быть улучшен за счет клеток с нарушениями. Для улучшения  плана выбирается клетка с наибольшим нарушением А₁В₆ (нарушение 30).

Следуя формальному  правилу улучшения плана (см.пример №1), “ходом шахматной ладьи” строится контур корректировки с вершинами  в выбранной клетке с нарушением и в базисных клетках (А₁В₂ – А₁В₆ – – А₅В₂ – А₅В₆). Вершины контура нумеруются начиная с клетки с нарушением. Определяется минимальная перевозка в четных вершинах контура min{20; 90} = 20 в клетке А₅В₆. Данная перевозка “переносится” по контуру, в нечетные клетки найденное значение прибавляется, из четных – вычитается. Получается новый скорректированный улучшенный план (табл.15).

Таблица 15

Итоговый план перевозок

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

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

F_кон = f (x) = 70· 40 + 20· 75 + 60· 20 + 50· 45 + 90· 25 + 100· 25 + 60· 15 + 60· 40 + + 40· 20 + 155· 10 + 95· 20 + 20· 15 + 35· 15 + 35· 20 + 70· 25 + 40· 20 = 24125 тыс. ткм.

Полученный  скорректированный план перевозок  проверяется на оптимальность по формуле (14).

В данном плане  отсутствуют нарушения условий оптимальности для всех клеток, следовательно, план оптимален и итоговый план перевозок улучшен по сравнению с исходным на 600 ткм (F_нач – F_кон = 24725 – 24125).

Пример № 4.

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

Перед рассмотрением  транспортных задач открытого типа необходимо заметить, что такие задачи на практике встречаются чаще, чем  задачи закрытого типа.

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

 

Возможны два варианта транспортной задачи открытого типа. Если ,

 

 

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

min (max)

 

 

и следующую систему  ограничений:

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

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

.

 

Если , то система ограничений будет  записана иначе:

 

 

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

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

.

Решение транспортных задач  открытого типа можно производить методом потенциалов, если предварительно привести ее к “закрытому” типу. Это достигается введением дополнительного фиктивного потребителя Вфикт (поставщика Афикт) с объемом потребления (производства)   ( ).

 

 

 

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

Однако более удобным  при решении транспортных задач  открытого типа представляется метод  условно-оптимальных пленов, разработанный  А.Л. Лурье.

 

Рассмотрим решение транспортных задач открытого типа на примерах.

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

составить математическую модель задачи;

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

Данные по объему производства и потребления и  матрица себестоимостей перевозок  приведены в табл.16.

Таблица 16

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

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

 

 

Составляется  математическая модель задачи. Для  этого определяются суммарные ресурсы  станций отправления и суммарные  потребности станций назначения,

 

тыс. т,

 

тыс. т.

 

 

Суммарный объем  производства превышает суммарный  объем потребления на 50 тыс. т. Эта задача открытого типа.

Целевой функцией будет являться минимальная суммарная  себестоимость перевозок

,при следующих ограничениях, (i = 1,2,...,5),

 

 

 

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

 

 

Решение задачи методом условно-оптимальных планов начинается с составления исходного плана. Методика построения исходного плана перевозок вытекает из сущности метода условно-оптимальных планов, которая заключается в следующем.

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

При построении исходного плана в каждом j-м  столбце матрицы стоимостей находится  клетка с минимальным критерием  стоимости и в неё записывается перевозка, равная полной потребности  данного столбца, x_ij = b_j. При наличии нескольких клеток с минимальной стоимостью поставка b_j распределяется между ними произвольно. Так, для потребителя В₁ это будет клетка А₂В₁ с себестоимостью 10 руб./т, для потребителя В₂ это клетка А₄В₂ с себестоимостью 25 руб./т и т.д.

Исходный план перевозок представлен в табл.17

Таблица 17

Исходный план перевозок

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

C_нач = f (x) = 80· 10 + 90· 25 + 190· 10 + 130· 20 + 150· 30 + 160· 30 + 150· 20 = = 19850 тыс. руб.

Значение целевой функции  данного начального плана является минимальным, т.е. отвечает критерию оптимальности, но не отвечает существующей системе ограничений. Следовательно, необходимо продолжить решение. Задача решается методом условно-оптимальных планов.

Алгоритм решения транспортной задачи открытого типа методом условно-оптимальных планов

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

 

 

 

поставщиков и предусмотренными поставками по формуле 

(15)

 

 

Разности R_i называются избытками или недостатками в зависимости от знака, получаемого в результате математического действия. Так, в примере R₁ =200 – 0 = +200, R₂ = 250 – (80 + 150) = +20, R₃ = 100 – 160 = -60, R₄ = 250 – (90 + 190) = -30, R₅ = 200 – (130 + 150) = -80. Полученные значения разностей с сохранением знака записываем во вспомогательную графу матрицы (табл.17).

Проверка на оптимальность. Если в последней графе все  разности R_i имеют одинаковый знак или равны нулю, то решение считается законченным и план является оптимальным. В примере имеются строки с разнозначными разностями R_i, поэтому расчеты продолжаются.