Открытая и закрытая модели транспортной задачи

 

Формулировка и основные понятия для транспортной задачи представлены в вопросе 1.8.

Определение 1: Модель транспортной задачи называется закрытой, если суммарный объем груза имеющегося у поставщиков равен суммарному спросу потребителей т.е.

Определение 2: Если для транспортной задачи выполняется одно из условий:

или

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

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

;

все тарифы одинаковы, чаще всего равны нулю ().

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

;

все тарифы дополнительной строки распределительной таблицы равны нулю ().

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

Теорема 1: (о ранге матрицы) Ранг матрицы А транспортной задачи на единицу меньше чем числа уравнений r(A)=m+n-1.

Замечание: Эта теорема говорит о том, что при решении любой транспортной задачи в распределительной таблице должна быть заполнена m+n-1 ячейка.

 

3.3. Построение начального опорного плана. Правило "Северо-западного угла"

 

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

Заполнение распределительной таблицы начинается с верхнего левого угла, который еще называют северо-западным. В ячейку с координатами (1,1) записывается минимальное из чисел и .

Предположим, что это . Тогда товар первого поставщика полностью реализован и он может быть исключен из рассмотрения. Соответственная ему первая строка больше не заполняется. Следующей будем заполнять ячейку (2,1). В нее записываем наименьшее из чисел и . Предположим, что минимум это число . тогда потребности первого поставщика полностью удовлетворены. Первый столбик может быть исключен из рассмотрения. Далее будем рассматривать ячейку с номером (2,2).

Если же при первом сравнении получили, что наименьшее число , то процесс аналогичным образом продолжается, но рассматриваем мы ячейку с номером (1,2).

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

	B1	B2	B3
A1		v	v
A2			v
A3	v
A4	v	v

Модель транспортной задачи – закрытая. Символом v будем обозначать пустую ячейку. Заполненных ячеек 4+3-1=6.

Ответ: Z=11900

В некоторых случаях появляется необходимость вставки так называемой ноль-загрузки. Т.е. в ячейку проставляется 0 и она считается заполненной. Эта необходимость возникает только в том случае, когда одновременно из рассмотрения исключаются и строка и столбец одновременно. Ноль-загрузка в этом случае ставится в любую соседнюю свободную ячейку (справа или внизу).

 

3.4. Построение начального опорного плана. Правило минимального элемент

 

Сущность: рассматриваются тарифы в распределительной таблице и в первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику запасы которого полностью израсходованы, или столбец соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. Опорный план получаемый в результате данных содержащих m+n-1 загруженных клеток, но в процессе заполнения таблицы могут быть одновременно исключены строка и столбец. Поэтому в свободные клетки нужно записать число 0, условно считая такую клетку занятой.

	B1	B2	B3
A1		v	v
A2	v
A3		v
A4	v		v

Z=3*800+2*600+4*100+4*200+5*800+1*500=9300

 

3.5. Построение начального опорного плана. Метод Фогеля

 

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

	B1	B2	B3
A1		v	v					–	–
A2	v								–
A3		v
A4	v		v			–	–	–	–
		–
		–
		–

Заполненных ячеек 6.

Z=3*800+2*600+4*100+4*200+5*800+1*100=8900

 

Метод потенциалов

 

Для проверки оптимальности опорного плана используют следующую теорему:

Теорема: Если план транспортной задачи является оптимальным, то ему соответствует система из m+n чисел , , удовлетворяющих условиям:

· - для заполненных ячеек;

· - для свободных ячеек.

Эти, , называются потенциалами.

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

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

Заполненых ячеек в распределительной таблице m+n-1. Если составлять уравнения , получим m+n-1 уравнение с m+n неизвестными. n+m-1<n+m. Следовательно, система имеет бесконечно много решений. Нас устроит любое из них. Поэтому принято одну из или принимать равной 0.

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

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

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

Пример: Рассчитать потенциалы для примера в 3.4, 3.5, 3.6

	B1	B2	B3
A1		v	v
A2	v
A3		v
A4	v		v		-1

Вычислим оценки:

=5-(0+2)=3>0 =3-(1+2)=0=0

=6-(0+4)=2>0 =6-(3-1)=4>0

=7-(0+3)=4>0 =7-(4+1)=2>0

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

Ответ: Z=8900.

Ситуация, когда все оценки сразу получились неотрицательными, достаточна редка. Чаще всего план получается не оптимальным (особенно, если начальный опорный план составлять по правилу северо-западного угла.

Предположим, что. решая транспортную задачу и рассчитав оценки свободных ячеек, мы получили несколько отрицательных оценок. Выберем из них наименьшую. Пусть это будет . Тогда говорят, что ячейка с номером (k,p) потенциальна, т.е. ее необходимо заполнить.

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

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

1. Начальная вершина цикла – потенциальная ячейка.

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

3. Ребра в вершинах образуют прямой угол.

4. Ребра могут пересекаться. Однако, точка пересечения ребер не считается вершиной.

Построенный цикл для потенциальной ячейки – единственный. Далее необходимо перераспределить груз в ячейках в рамках цикла. При этом нельзя забывать, что количество заполненных ячеек не должно изменяться. Для этого маркируют вершины цикла знаками "+" и "–". Вершина цикла, находящаяся в потенциальной ячейке, всегда имеет знак "+". В остальных вершинах знаки чередуются ("–", "+", "–", "+", …). Из "отрицательных" ячеек выбираем ту, в которой минимальная загрузка. Эту ячейку и будем освобождать от груза. Маркируем ее как пустую ячейку. Далее, к загрузке в "положительных" ячейках прибавляем значение выбранной минимальной загрузки, в "отрицательных" – вычитаем это же значение. После данной процедуры получается новый опорный план, который необходимо проверить на оптимальность.

Алгоритм решения транспортной задачи:

1. Составляем начальный опорный план (по любому правилу и методу, лучше – методом минимального элемента).

2. Считаем потенциалы и .

3. Рассчитываем оценки свободных ячеек ().

4. Если все оценки - неотрицательны, то план оптимален. Задача решена. Считаем Z.

5. В противном случае, выбираем наименьшее отрицательное значение . Соответствующая ячейка будет называться потенциальной.

6. Строим цикл.

7. Маркируем вершины цикла знаками "+" и "–".

8. Выбираем наименьшую загрузку в "отрицательных" вершинах.

9. Выбранную ячейку считаем свободной.

10. Найденную минимальную загрузку прибавляем к загрузке "положительных" ячеек цикла и вычитаем из "отрицательных".

11. Получен новый опорный план. Переходим к пункту 2.

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

	v	v	v	v		-2
	6 10		+ 3 – v		v
+ 100	– 3 10	v		v
		-1		-2
=7-(3-2)=6>0 =3-(3+2)=-2<0 =5-(0-1)=6>0	=3-(-1-2)=6>0 =7-(4+3)=0=0 =6-(0-2)=4>0	=5-(-2-2)=9>0 =2-(4-2)=0=0

Потенциальная ячейка – (2,3). Построим цикл. Промаркировав его, получаем две "отрицательные" ячейки: (2,1) и (3,3). Минимальная загрузка в них равна 10. Прибавляя к загрузке в "положительных" ячейках и вычитая в "отрицательных", получим новую распределительную таблицу:

	v	v	v	v		-3
	v				v
		v		v		-1

 

=7-(-3+4)=6>0 =6-(4+0)=2>0 =5-(2-1)=4>0

=3-(-3+2)=4>0 =7-(5+0)=2>0 =6-(1-1)=6>0

=5-(3-3)=5>0 =2-(5-3)=0=0

Полученный план оптимален.

Ответ: Z=2*40+2*80+3*10+1*60+3*20+2*80+0*4=550