Пример № 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** – ограничение пропускной способности.

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

m in ,

где 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

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

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).