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

Некоторый однородный продукт, сосредоточенный у m поставщиков А_i в количестве а_i единиц (i = 1,..., m) соответственно, необходимо доставить n потребителям В_j в количестве b_j единиц (j = 1,..., n). Известна стоимость с_ij перевозки единицы груза от i-го поставщика к j-му потребителю.

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

Обозначим через х_ij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю запланировано к перевозке х_ij единиц груза, то стоимость перевозки составит с_ijx_ij.

Стоимость всех перевозок выразится двойной суммой

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть перевезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

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

(1.26)

при ограничениях:

(1.27)

(1.28)

x_ij ³ 0, i = 1,…,m; j = 1,…,n; (1.29)

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

(1.30)

Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется условие (1.30), называется закрытой моделью; в противном случае – открытой. Для открытой модели может быть два случая:

а) Суммарные запасы превышают суммарные потребности

б) Суммарные потребности превышают суммарные запасы

Открытая модель решается приведением к закрытой модели.

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель В_{n + 1}, потребность которого

В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик А_{m + 1}, запасы которого

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

Транспортная задача имеет n + m уравнений с mn неизвестными.

Матрицу Х = (х_ij)_m,n, удовлетворяющую условиям (1.26)-(1.29), называют планом перевозок транспортной задачи (х_ij – перевозками).

Определение. План Х*, при котором целевая функция (1.26) обращается в минимум, называется оптимальным.

Теорема 1.9 Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие баланса

План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов (i = 1.. m, j = 1.. n), где – векторы при переменных х_ij (i = 1.. m, j = 1.. n) в матрице системы ограничений (1.27)-(1.28).

Теорема 1.10 Существует план, содержащий не более m + n – 1 положительных перевозок, при этом система векторов , соответствующая таким перевозкам (х_ij > 0), линейно-независима.

Таким образом, опорный план транспортной задачи содержит m + n – 1 положительных перевозок. Дадим другое определение опорного плана.

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

Методы составления первоначальных опорных планов

Метод северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.

Схема метода:

1) Полагают верхний левый элемент матрицы Х

х₁₁ = min(a₁,b₁).

Возможны три случая:

а) если a₁ < b₁, то х₁₁ = а₁ и всю первую строку, начиная со второго элемента, заполняют нулями.

б) если a₁ > b₁, то х₁₁ = b₁, а все оставшиеся элементы первого столбца заполняют нулями.

в) если a₁ = b₁, то х₁₁ = а₁ = b₁, и все оставшиеся элементы первых столбца и строки заполняют нулями.

На этом один шаг метода заканчивается.

2) Пусть проделано k шагов, -й шаг состоит в следующем.

Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это элемент .

Тогда полагают где

и

Если , то заполняют нулями -ю строку начиная с -го элемента.
В противном случае заполняют нулями оставшуюся часть -го столбца.

Метод минимального элемента позволяет построить начальный опорный план транспортной задачи и является вариантом метода северо-западного угла, учитывающим специфику матрицы С = (с_ij)_mxn. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план и сокращает общее количество итераций по его оптимизации.

Схема метода: элементы матрицы С нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х⁰.

Пусть элементом с минимальным порядковым номером оказался элемент х_ij⁰.

Тогда полагают х_ij⁰ = min(a_i, b_j)

Возможны три случая:

а) если min(a_i, b_j) = a_i, то оставшуюся часть i-й строки заполняют нулями;

б) если min(a_i, b_j) = b_j, то оставшуюся часть j-го столбца заполняют нулями.

в) если а_i = b_j, то оставшуюся часть строки и столбца заполняют нулями.

Далее этот процесс повторяют с незаполненной частью матрицы.

Пусть элементом с k-м порядковым номером оказался .

Тогда , где

Возможны три случая:

а) , тогда и оставшуюся часть строки заполняют нулями;

б) , тогда и остаток столбца заполняют нулями;

в) , тогда оставшуюся часть строки и столбца заполняют нулями.

В дальнейшем, что бы не загромождать таблицу, нули не пишем, оставляя пустыми клетки, которым соответствует x_ij = 0.

Проверка опорного плана на оптимальность. Метод потенциалов.

Для транспортной задачи (ТЗ), как и для любой ЗЛП, существует двойственная к ней задача.

Исходная задача

(1.26)

при ограничениях:

(1.27)

(1.28)

x_ij ³ 0, i = 1,…,m; j = 1,…,n; (1.29)

Обозначим двойственные переменные для каждого ограничения вида (1.27) через U_i (i = 1,...,m) и вида (1.28) – V_j (j = 1,...,n), тогда двойственная задача имеет вид

	(1.31)
	(1.32)

Переменные двойственной к транспортной задаче U_i и V_j называют потенциалами.

Теорема 1.11 Для оптимальности плана X = (X_ij)_mxn ТЗ необходимо и достаточно существования чисел (потенциалов) V₁, V₂,..., V_n и U₁, U₂,..., U_m таких, что

для i = 1,...,m, j = 1,...,n,

, если X_ij>0.

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

а) для каждой занятой клетки (отличного от нуля элемента матрицы Х) сумма потенциалов должна быть равна стоимости перевозки единицы груза

((1.33)

б) для каждой незанятой клетки (X_ij = 0) сумма потенциалов должна быть меньше или равна стоимости перевозки единицы груза

((1.34)

Таким образом, для проверки плана на оптимальность необходимо сначала построить систему потенциалов. Для построения системы потенциалов используем условие

, X_ij>0.

Систему потенциалов можно построить только для невырожденного опорного плана. Такой план содержит m + n – 1 занятых клеток, поэтому для него можно составить систему из m + n – 1 линейно-независимых уравнений вида (1.33) с неизвестными U_i и V_j. Уравнений на одно меньше, чем переменных, поэтому система является неопределенной и одному неизвестному (обычно U_i) придают нулевое значение. После этого остальные потенциалы определяются однозначно.

Затем для каждой незанятой клетки проверяем выполнения условия (1.34), т.е. суммируем потенциалы тех строк и столбцов, на пересечении которых стоит незанятая клетка. Если для всех незанятых клеток U_i + V_j ≤ C_ij, т.е. , то по теореме 1.11 проверяемый план является оптимальным. Если для некоторых клеток , то план не является оптимальным. Оценки всех клеток удобно записывать в отдельную оценочную матрицу.

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

Переход к новому плану перевозок

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

max((U_i + V_j) – C_ij).

Далее необходимо перераспределить груз. Это происходит по замкнутому циклу. Цикл представляет собой ломаную линию, вершинами которой могут быть только занятые клетки, а его начало в клетке, подлежащей загрузке. Соседние звенья ломаной должны образовывать прямой угол, т.е. если одно из звеньев располагалось вдоль горизонтального ряда, то следующее звено должно быть вдоль вертикального ряда. Такой цикл находится однозначно. Циклы могут выглядеть по-разному (рис. 1.22).

Рис.1.22. Примеры циклов

Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком «+», незанятую клетку, которую надо загрузить. Следующие клетки цикла поочередно отмечаем знаками «-» и «+». Затем находим r = min X_ij, где X_ij – перевозки, стоящие в вершинах цикла, отмеченной знаком «–». Эта величина определяет, сколько единиц груза можно перераспределить по найденному циклу. Записываем значение r в незанятую клетку, отмеченную знаком «+». Двигаясь по циклу, вычитаем r из объемов перевозок, расположенных в клетках, которые отмечены знаком «–», и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком «+». Если r соответствует несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было m + n – 1.

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

Пример 7. Решить транспортную задачу. В таблице 1.5 приведены стоимости перевозок ед. груза, запасы трех поставщиков и потребности четырех потребителей.

Таблица 1.5

	В1	В2	В3	В4	запасы
А1
А2
А3
потребности

Решение. Условие баланса выполнено: 200+300+100 = 150+150+250+50. Следовательно, имеем ТЗ закрытого типа.

Шаг 1. Находим исходный опорный план X° методом «минимального элемента». В правых верхних углах клеток находятся тарифы на перевозки с_ij, а по центру объемы перевозок x_ij.

Таблица 1.6

	В1	В2	В3	В4	запасы
А1					200 50 0
А2					300 150 0
А3					100 50 0
потребности	150 0	150 0	250 100 50 0	50 0

Сначала заполняются клетки с минимальным тарифом 1: в клетку (А₂,В₁) можно поместить min(300, 150) = 150, при этом выбывают из рассмотрения остальные клетки первого столбца, т.к. потребности первого потребителя удовлетворены полностью, а запасы второго поставщика корректируем, у него осталось 300 – 150 = 150 ед. груза.

Дале заполняем клетку (А₃,В₄) (порядок заполнения клеток с одинаковыми тарифами не существенен), туда поместим min(50, 100) = 50 ед. груза, при этом выбывают из рассмотрения остальные клетки четвертого столбца, т.к. потребности четвертого потребителя удовлетворены полностью, а запасы третьего поставщика корректируем, у него осталось 100 – 50 = 50 ед. груза.

Из оставшихся клеток минимальный тариф 2 в клетке (А₂,В₃), её можно загрузить min(150, 250) = 150 ед. груза, при этом выбывают из рассмотрения остальные клетки второй строчки, т.к. запасы второго поставщика исчерпаны, а потребности третьего потребителя корректируем, ему необходимо 250 – 150 = 100 ед. груза.

Из оставшихся клеток минимальный тариф 3 в клетках (А₃,В₂) и (А₃,В₃), загрузим клетку (А₃,В₃) min(50, 100) = 50 ед. груза, при этом выбывают из рассмотрения остальные клетки третьей строчки, т.к. запасы третьего поставщика исчерпаны, а потребности третьего потребителя корректируем, ему осталось поставить 100 – 50 = 50 ед. груза.

Из оставшихся клеток минимальный тариф 4 в клетке (А₁,В₂), её можно загрузить min(200, 150) = 150 ед. груза, при этом потребности второго потребителя удовлетворяются полностью, а запасы первого поставщика корректируем 200 – 150 = 50 ед. груза.

И оставшиеся 50 единиц груза проставляем в последнюю клетку (А₁,В₃). Получили опорный план перевозок.

Число занятых клеток равно 6 и совпадает с числом m + n – 1 = 3 + 4 – 1 = 6, значит, полученный план не вырожден.

Шаг 2. Для проверки полученного опорного плана на оптимальность находим систему потенциалов для занятых клеток (x_ij>0).

Для этого, например, полагаем V₃ = 0 (записываем V₃ = 0 в дополнительной строке табл. 1.7).

Таблица 1.7

		В1	В2	В3	В4	запасы
		V1 = -1	V2 = - 2	V3 = 0	V4 = -2
А1	U1 = 6
А2	U2 = 2
А3	U3 = 3
потребности

Далее, исходя из занятых клеток (1,3), (2,3) и (3,3) находим U₁ = 6 – 0 = 6, U₂ = 2 – 0 = 2, U₃ = 3 – 0 =3 (записываем слева в таблице). На основе базисной клетки (2,1) получаем V₁ = 1 – 2 = –1, затем по клетке (1,2) найдем V₂ = 4 – 6 = - 2; и по клетке (3,4) найдем V₄ = 1 – 3= –2.

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

=6 + (– 1) – 5 = 0; = 6 + (–2) – 3 = 1;

= 2 + (–2) – 10 = – 10; = 2 + (–2) – 1 = – 1;

= 3 + (–1) – 2 = 0; = 3 + (–2) – 3 = – 2.

Так как для клеток (1,4) критерий оптимальности (условие 1.34) не выполняется: U1 + V4 = 4 > 3, то полученный опорный план не оптимальный. Поскольку это единственная клетка с положительной оценкой, то она и подлежит загрузке. Строим для неё цикл: (1,4) → (3,4) → (3,3) → (1,3) → (1,4). Знаки + и – в клетках чередуются, начиная с клетки (1,4), которую помечаем +. Цикл можно нанести на заполненную таблицу с планом (табл. 1.7).

Рис.1.23. Цикл передвижения груза

Определим, сколько можно передвигать единиц груза по данному циклу: min(50; 50) = 50. Далее к грузам, стоящим в клетках с «+», прибавляем 50 ед. груза; из грузов, стоящих в клетках с «–», отнимаем 50 единиц груза. В данном случае в клетке (1,4) будет стоять 50; в клетках (3,4) и (1,3) пусто; в клетке (3,3) 50+50 = 100 единиц груза. Поскольку в новом плане должно быть по-прежнему 6 занятых клеток, что бы он не был вырожденным, то одну из двух освободившихся клеток будем считать занятой и поставим там 0. Целесообразнее нуль оставить в клетке с меньшей стоимостью перевозок, т.е. в клетке (3,4).

Остальные клетки, не задействованные в цикле, остаются без изменений. Новый опорный план X⁽¹⁾ приведен в таблице 1.8.

Таблица 1.8

		В1	В2	В3	В4	запасы
		V1 = -1	V2 = - 1	V3 = 0	V4 = -2
А1	U1 = 5
А2	U2 = 2
А3	U3 = 3
потребности

Шаг 3. Проверяем полученный план X⁽¹⁾ на оптимальность. Находим систему потенциалов. Они записаны в таблице 1.8 слева и сверху, вычисляем сумму потенциалов для свободных клеток:

=5 + (– 1) – 5 = – 1; = 5 + 0 – 6 = – 1;

= 2 + (–1) – 10 = – 9; = 2 + (–2) – 1 = – 1;

= 3 + (–1) – 2 = 0; = 3 + (–1) – 3 = – 1.

Так как все оценки свободных клеток оказались меньше либо равны 0, то мы получили оптимальный план перевозок

.

Стоимость перевозок будет при этом плане наименьшей Z () = 150*4+50*3+150*1+150*2+100*3 = 1500 у.е.

Замечание: Поскольку одна из оценок небазисной переменной равна 0 ( = 0), то данная задача будет иметь еще один оптимальный план перевозок с той же общей стоимостью перевозок 1500 у.е. Этот план можно найти, загрузив клетку (3,1).

Построим цикл: (3,1) → (2,1) → (2,3) → (3,3) → (3,1). По нему передвигаем min (150; 100) = 100 единиц груза. Новый план перевозок записан в табл. 1.9. Проверять его оптимальность нет необходимости, т.к. во вновь занятой клетке при той же системе потенциалов выполняется условие (1.33), а в освободившейся – условие (1.34).

Таблица 1.9

		В1	В2	В3	В4	запасы
		V1 = -1	V2 = - 1	V3 = 0	V4 = -2
А1	U1 = 5
А2	U2 = 2
А3	U3 = 3
потребности

Тогда еще один оптимальный план перевозок будет такой:

.

Общий ответ запишется, как выпуклая линейная комбинация двух оптимальных решений:

Пример 8. Решить транспортную задачу:

	В1	В2	В3	запасы
А1
А2
А3
потребности

Решение. Объем ресурсов: 80+60+60=200 превышает общие потребности: 30+70+60=160 на 40 ед., следовательно, ТЗ является задачей открытого типа. Вводим дополнительный (балансовый пункт) потребления с объемом потребностей b₄ = 40 и полагаем c₁₄ = c₂₄ = c₃₄ = 0. В результате получаем ТЗ закрытого типа.

Шаг 1. Находим исходный опорный план методом «минимального элемента» (см. таблицу 1.10). Клетки четвертого «фиктивного» потребителя заполняются по остаточному принципу. Сначала заполнили 60 ед. груза клетку (3,3), т.к. в ней самый маленький тариф, после чего из рассмотрения вышли сразу все остальные клетки третьей строки и третьего столбца. Затем клетку (1,2) заняли min (70, 80) = 70 единицами груза. И так далее. Последней была занята клетка (2,4) оставшимися 40 ед. груза.

Таблица 1.10

		В1	В2	В3	В4	запасы
		V1 = 7	V2 = 3	V3 = 4	V4 = 2
А1	U1 = 0					80 10 0
А2	U2 = - 2					60 40 0
А3	U3 = -2					60 0
потребности		30 20 0	70 0	60 0	40 0

Данный план является вырожденным, поэтому ставим «0» – перевозку в клетку с минимальным значением c_ij, но так, чтобы не образовалось замкнутого маршрута (цикла). В нашем примере c₁₄ = c₃₄ = 0, но занять клетку (1,4) нельзя, так как образуется цикл: (1,4) → (2,4) → (2,1) → (1,1) → (1,4). Поэтому ставим «0» в клетку (3,4).

Шаг 2. Проверяем план на оптимальность. Положив , находим потенциалы (см. таблицу). Далее находим оценки для свободных клеток:

Так как есть клетки с положительными оценками ( = 0 + 2 – 0 = 2; = – 2 + 7 – 3 = 2), то полученный опорный план не оптимален. Для клеток (1,4) и (3,1) оценки одинаковы, поэтому выбираем с минимальным тарифом – (1,4). Составляем для неё цикл, чередуя знаки «+» и «–»: (1,4) → (2,4) → (2,1) → (1,1) → (1,4) (изображен в табл. 1.10). По циклу можно передвинуть min (40; 10) = 10 ед. груза.

Новый опорный план представлен в таблице (1.11).

Таблица 1.11

		В1	В2	В3	В4	запасы
		V1 = 5	V2 = 3	V3 = 2	V4 = 0
А1	U1 = 0
А2	U2 = 0
А3	U3 = 0
потребности

Шаг 3. Поскольку новый опорный план не вырожден (6 занятых клеток), то находим систему потенциалов (см. слева и сверху табл. 1.11). Оценка свободных клеток:

.

Критерий оптимальности не выполняется для клетки (3,1): = 0 + 5 – 3 = 2 > 0.

Шаг 4. Составляем цикл для клетки (3,1): (3,1) → (2,1) → (2,4) → (3,4) → (3,1) (изображен в табл. 1.11). По циклу можно передвинуть min (30; 0) = 0 ед. груза. По сути, груз в данном случае не двигается, меняется фиктивно занятая клетка. Новый опорный план представлен в таблице (1.12).

Таблица 1.12

		В1	В2	В3	В4	запасы
		V1 = 5	V2 = 3	V3 = 4	– V4 = 0
А1	U1 = 0
А2	U2 = 0
А3	U3 = - 2
потребности

Проверяем его оптимальность. Вычисляем потенциалы по занятым клеткам и проверяем оценки свободных клеток.

Положительных оценок нет, поэтому получен оптимальный план

.

Транспортные издержки при нем составят 480 у.е. Так как четвертый потребитель фиктивный, то 10 ед. груза останутся не вывезенными у первого поставщика, 30 ед. – у второго.

Но этот план не единственен, т.к. есть нулевая оценка небазисной клетки: = 0 + 4 – 4 = 0. Перераспределим груз, переместив min (10; 30; 60) = 10 ед. груза в клетку (1,3) по циклу: (1,3) → (1,4) → (2,4) → (2,1) → (3,1) → (3,3) → (1,3) (изображен в табл. 1.12). Альтернативный план не нуждается в проверке на оптимальность.

.

При втором плане 40 единиц груза останутся не вывезенными у второго поставщика. Окончательный ответ является выпуклой линейной комбинацией полученных двух оптимальных планов: