Постановка транспортной задачи общего вида

Классическая постановка транспортной задачи общего вида такова.
Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:
a_i – объемы производства i -го поставщика, i = 1, …, m;

в_j – спрос j -го потребителя, j = 1,…, n;

с_ij – стоимость перевозки одной единицы продукции из пункта A_i – i- го поставщика, в пункт В_j – j -го потребителя.

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

Потребители Поставщики	В 1	В 2	…	Вn	запасы
А 1	С 11	C12		C 1 n	а 1
А 2	С 21	C22		C 2 n	а 2
…
Am	Cm 1	Cm 2		Cmn	аm
Потребности	в 1	в 2		вn

Требуется найти план перевозок, при котором бы полностью удовлетворялся спрос всех потребителей, при этом хватало бы запасов поставщиков и суммарные транспортные расходы были бы минимальными.
Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i- го поставщика к j- му потребителю. Для построения математической модели задачи необходимо ввести m·n штук переменных х_ij, i = 1,…, n, j = 1, …, m, каждая переменная х_ij обозначает объем перевозок из пункта A_i в пункт В_j. Набор переменных X = {x_ij} и будет планом, который необходимо найти, исходя из постановки задачи.

Ограничения задачи примут вид:

Это условие для решения закрытых и открытых транспортных задач (ЗТЗ).
Очевидно, что для разрешимости задачи 1 необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков:

Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же , то задача называется «закрытой» транспортной задачей, и будет иметь вид (2):

– условие сбалансированности.

Это условие для решения закрытых транспортных задач (ЗТЗ).

В силу ограничений (2) нетрудно увидеть, что ЗТЗ является задачей ЛП и может быть решена симплекс-методом после приведения ее к специальному виду. Но структура системы ограничений имеет некоторою специфику, а именно: каждая переменная х_ij входит ровно два раза в неравенства системы, и все переменные входят в неравенства системы с коэффициентом 1. В силу этой специфики существует более простой метод решения, называемый методом потенциалов, который, по сути, является некоторой модификацией симплекс-метода. По-прежнему идеей является переход от одного опорного плана к другому, обязательно «лучшему» с точки зрения значения целевой функции. Каждому опорному плану также соответствует своя распределительная таблица. Переход осуществляется от одного плана к другому, пока полученный план не будет удовлетворять условию оптимальности. Необходимо научиться строить первоначальный опорный план. В качестве первоначального плана годится любое решение системы уравнений (2). Заметим, что это система линейных уравнений, состоящая из m + n уравнений с m*n неизвестными. Можно доказать, что линейно независимых уравнений в системе (2) m + n – 1, ввиду условия сбалансированности, т.е. базисных переменных должно быть m + n – 1. Итак, в качестве плана будем представлять себе таблицу размера m ∙ n, в которой должно быть занято m + n – 1 клеток, отвечающих базисным переменным x_ij.

Транспортные задачи с неправильным балансом

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

Такая задача называется задачей с правильным балансом, а ее модель — закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой. Решение задачи с неправильным балансом сводится к решению задачи с правильным балансом введением в ее математическую модель фиктивного поставщика или фиктивного потребителя. Тарифы на перевозку грузов от таких поставщиков или к таким потребителям полагаются равными 0 (т.е. фактически соответствующие перевозки не производятся). В случае превышения общего запаса продукции над потребностью, т.е. если

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

и тарифами на перевозку c_{i(k +1)}=0. Если же то вводится фиктивный поставщик, запасы которого равны

с тарифами на перевозку c_{(n +1)j}=0. Этим приемом задача сводится к закрытой транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. Заметим, что при составлении начального опорного решения для ускорения вычислений в последнюю очередь следует (хотя и не обязательно) распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствуют наименьшие тарифы на перевозку (равные 0).

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

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА И ФОРМАЛЬНАЯ МОДЕЛЬ ТЗЛП

Пусть имеется m пунктов производства однородной или взаимозаменяемой продукции. Каждый из пунктов производства обозначим через, где i= 1,...,m. Через будем обозначать объем продукции, производимой в пункте. И пусть имеется n пунктов потребления (назначения) данной продукции, каждый из которых будем обозначать, где j=1,...,n, а через будем обозначать объем потребления (спроса) продукции в пункте. Стоимость перевозки единицы продукции от i-го производителя к j-му потребителю составляет (i=1,...,m, j=1,...,n). Предполагается, что транспортные расходы на перевозки между любой парой пунктов пропорциональны объему перевозимого продукта. Требуется установить такие объемы перевозок от каждого производителя к каждому потребителю, чтобы суммарные затраты на перевозки были минимальными и потребности всех потребителей были бы удовлетворены (если только объем возможных поставок покрывает общий объем потребления). Представим транспортную модель в виде сети. В ней: вершины соответствуют пунктам производства и потребления, дуги, соединяющие вершины, представляют собой маршруты, по которым перевозится продукция, вес дуги – расстояние между соотв. пунктами.

16. Методы построения первого опорного плана транспортной задачи: метод северо-западного угла, метод минимальных элементов, метод штрафов (алгоритм Фогеля).

1)Метод северо-западного угла. Следуя этому методу, начинают с того, что приписывают неизвестной (расположенной в северо-западном углу таблицы) максимальное значение, допускаемое ограничениями на спрос и объем производства. После этого вычеркивают соответствующий столбец (или строку), фиксируя этим, что остальные неизвестные вычеркнутого столбца (строки) полагаются равными нулю. Если ограничения, представляемые столбцом и строкой, выполняются одновременно, то можно вычеркнуть либо столбец, либо строку (это условие автоматически гарантирует обнаружение нулевых базисных переменных, если таковые встречаются). После того спрос и объем производства во всех невычеркнутых строках и столбцах, приведены в соответствие с установленным значением переменной, максимально допустимое значение приписывается первому невычеркнутому элементу нового столбца (строки). Процесс завершается, когда остается невычеркнутой в точности одна строка (или один столбец).

Пусть условия транспортной задачи заданы таблице 2.3.
Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя B1 за счет запаса поставщика А₁. Для этого сравниваем a₁ = 100 с b_i = 200, a₁< b₁ меньший из объемов, т. е. = 100 ед. записываем в левый нижний угол клетки А₁B₁. Запасы первого поставщика полностью израсходованы, по этому остальные клетки первой строки прочеркиваем. Потребности В остались неудовлетворенными на 200–100=100 ед. Сравниваем этот остаток с запасами поставщика А₂: так как 100<250, то 100 ед. записываем в клетку А₂ .B₁, чем полностью удовлетворяем потребности потребителя B₁, а оставшиеся клетки в первом столбце прочеркиваем.

Таблица 2.3

У поставщика А₂ осталось 150 ед. груза. Удовлетворяем потребителя B₂ за счет оставшегося у поставщика А₂ груза. Для этого сравниваем этот остаток с потребностями потребителя B₂: 150<200, записываем 150 ед. в клетку А₂B₂ и, так как запасы А₂ полностью израсходованы, прочеркиваем остальные клетки второй строки. Потребности B₂ остались неудовлетворенными на 50 ед. Удовлетворяем их за счет поставщика А₃ и переходим к удовлетворению B₃ за счет остатка, имеющегося у поставщика А₃, и т. д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного плана заканчивается.
Таким образом, в табл. в правых верхних углах клеток стоят числа, определяющие стоимость перевозки единицы грузов, а в левых нижних углах — числа, определяющие план перевозок, так как их сумма по строкам равна запасам соответствующего поставщика, а сумма по столбцам — потребности соответствующего потребителя.
Проверим, является ли план, построенный в табл. 2.2, опорным. Видим, что, начиная движение от занятой клетки A1B1, вернуться не только в нее, но и в любую другую занятую клетку, двигаясь только по занятым ячейкам, невозможно. Следовательно, план является опорным. В то же время план невырожденный, так как содержит точно m + n -1 = 4 + 5 - 1 = 8 занятых клеток.
При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Поэтому рассмотренный метод используется при вычислениях-с помощью ЭВМ.

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

Z = 100 *10 + 100*2 + 150 *7+ 50 *5 + 100*3 + 50*2 + 50*16+ 250*13 = 6950 (eд. стоимости)
Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то, очевидно, план будет значительно ближе к оптимальному.

2) Метод наименьшей стоимости.

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

Составим с помощью этого метода опорный план уже рассмотренной задачи. Запишем ее условие в таблицу (табл. 2.5). Выбираем в таблице наименьшую стоимость (это стоимость, помещенная в клетке A₁, B₄) так как A₁ = b₄, 100 ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке A₂ , B₁ и в клетке A₃ , B₅. Заполняем любую из них, например A₂ , B₁. Имеем 200 < 250, следовательно, записываем в нее 200 и исключаем из рассмотрения столбец B₁. В клетку A₃ , B₅ записываем 200 ед. и исключаем из рассмотрения строку A₃ . В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. В результате получен план
X = (X₁₄ = 100; X₂₁ = 200; X₂₂ = 50; X₃₅= 200, X₄₂ = 150; X₄₃ = 100; X₄₅ = 50),
остальные значения переменных равны нулю.

Таблица 2.5

План не содержит циклов и состоит из семи положительных перевозок, следовательно, является вырожденным опорным планом. Определим его стоимость:
Z = 100*1+200*2+50*7+200*2+150*8+100*12+50*13= 4300 (ед)
Стоимость плана перевозок значительно меньше, следовательно, он ближе к оптимальному.

3).Метод аппроксимации Фогеля

Данный метод состоит в следующем:

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

находят max Δc_ij и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

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

На первом шаге заполняем клетку A₃ B₁ (max Δc = 5 и min c_ij = 6), исключаем 1-ый столбец, отметив в дополнительной строке буквой «В» факт выполнения заказа пункта B₁ . Находим новые разности минимальных тарифов по строкам (в столбцах они не изменились) и max Δc = 2 в 1-ой строке и в 4-ом столбце. Заполняем клетку A₁B₄ и исключаем 4-й столбец и т.д. В конце остается последовательно заполнить клетки 3-го столбца остатками запасов в A₁ , A₃ , A₂ . Составленный опорный план дает значение Z₃ = 909 < Z₂.

Распределительный метод

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

Пусть для транспортной задачи найдено начальное опорное решение Х₁ и вычислено значение целевой функции на этом решении F(Х₁). По доказанной выше теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Обозначив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину можно получить новое опорное решение Х₂.

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l,m), приращение целевой функции Δ_lm равно разности двух сумм:

где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком “+”; - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком “-”.
В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки (l, m) меньше нуля, т.е. Δ _lm< 0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θ • Δ_lm, т.е. опорное решение можно улучшить. Если же величины Δ_lm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, m) построить цикл и вычислить оценку Δ_lm. Если оценка неотрицательная, переходят к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину . В результате получится новое опорное решение.

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

ПРИМЕР. Решить распределительным методом транспортную задачу, исходные данные которой приведены в таблице:

		b1	b2	b3
		20	40	40
a1	20		1		3		2
a2	30		4		5		7
a3	50		6		8		15

Решение. Строим начальное опорное решение методом минимальной стоимости:

Затем вычисляем значение целевой функции на нем: F(X₁) = 20∙1 + 30∙5 + 10∙8 + 40∙15 = 850.
Таблица

Находим цикл для свободной клетки (1, 2) таблицы, он включает клетки (1, 2), (1, 3), (3, 3), (3, 2). Вычисляем оценку Δ₁₂ = (3 + 15) - (2 + 8) = 8. Так как Δ₁₂ = 8 > 0, переходим к следующей свободной клетке (2, 1). Для нее цикл таков: (2, 1), (1, 1), (1,3), (3, 3), (3, 2), (2, 2) (см. табл.). Оценка Δ₂₁ = (4 + 2 + 8) - (1 + 15 + 5) =14 - 21 = -7. Так как Δ₂₁| = -7 < 0, определяем величину груза, перераспределяемого по циклу, Приращение целевой функции ΔF=-7∙20=-140. Получим новое опорное решение X₂. Значение целевой функции на нем F(X₂)=20∙2+20∙4+10∙5+30∙8+20∙15=710.

Вычисляем Δ₁₁ = (1 + 15 + 5) - (2 + 8 + 4) =7>0, Δ₁₂= (3 + 15) - (2 + 8) =8>0, Δ ₂₃ = (7 + 8) - (5 + 15)=-5<0, Δ₃₁= (6 + 5) - (8 + 4) =-1<0. Оценки можно вычислять до первой отрицательной. Так как Δ₂₃ =-5<0, осуществляем сдвиг по циклу (2,3), (3,3), (3,2), (2,2) на величину . Приращение целевой функции ΔF=-5∙10=-50. Получаем третье опорное решение X₃. Значение целевой функции на нем F(X₃)=20∙2+20∙4+10∙7+40∙8+10∙15=660.

Вычисляем оценки для свободных клеток Δ₁₁ = (1 + 7) - (2 + 4) =2>0, Δ₁₂ = (3 + 15) - (2 + 8) =8>0, Δ₂₂ =(5 + 15) - (7 + 8) =5>0, Δ₃₁ = (6 + 7) - (4 + 15) =-6<0. Так как Δ₃₁=-6<0, осуществляем сдвиг по циклу (3,1), (2,1), (2,3), (3,3), на величину Приращение целевой функции ΔFm=-6∙10=-60. Получаем четвертое опорное решение X₄ Значение целевой функции на нем F(X₄)=20 ∙2+10∙4+20∙7+10∙6+40∙8=600.

Вычисляем оценки для свободных клеток Δ₁₁ = (1 + 7) - (2 + 4) =2>0, Δ₁₂ = (3 + 7+ 6) - (2 +4+ 8) =2>0, Δ₂₂ =(5 + 6) - (4 + 8) =-1<0. Так как Δ₂₂ =-1<0, осуществляем сдвиг по циклу (2,2), (3,2), (3,1), (2,1), на величину Приращение целевой функции ΔF=-1∙10=-10. Получаем пятое опорное решение X₅.

Значение целевой функции на нем F(X₅)=20 ∙2+10∙5+20∙7+20∙6+30∙8=590. Вычисляем оценки для свободных клеток Δ₁₁ = (1 + 7) - (2 + 4) =2>0, Δ₁₂ = (3 + 7) - (2 +5) =3>0, Δ₃₃ =(15 + 5) - (7 + 8) =5>0. Все оценки для свободных клеток положительные, следовательно, последнее опорное решение оптимально.