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

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

	B1	B2	B3
A1	3 800	5 v	6 v	800
A2	7 v	2 600	4 100	700
A3	4 200	3 v	5 800	1000
A4	6 v	1 500	7 v	500
	1000	1100	900	3000 3000

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

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

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

	B1	B2	B3		1	2	3	4	5
A1	3 800	5 v	6 v	800	2	2	3	–	–
A2	7 v	2 600	4 100	700	2	2	3	3	–
A3	4 200	3 v	5 800	1000	1	1	1	1	1
A4	6 v	1 500	7 v	500	5	–	–	–	–
	1000	1100	900	3000 3000
1	1	1	1
2	1	1	1
3	1	–	1
4	3	–	1
5	4	–	5

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

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

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

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

Теорема: Если план транспортной задачи является оптимальным, то ему соответствует система из 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	3 800	5 v	6 v	800	0
A2	7 v	2 600	4 100	700	0
A3	4 200	3 v	5 800	1000	1
A4	6 v	1 500	7 v	500	-1
	1000	1100	900	3000 3000
	3	2	4

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

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

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

290 290	20	80		90	60		40
40	7 v	3 v		5 v	4 v		2 40	-2
150	6 10	2 80		3 + v –	1 60		7 v	3
1 + 00	3 – 10	5 v		2 90	6 v		4 0	0
	3	-1		2	-2		4
=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. Прибавляя к загрузке в "положительных" ячейках и вычитая в "отрицательных", получим новую распределительную таблицу:

	20	80	90	60	40
40	7 v	3 v	5 v	4 v	2 40	-3
150	6 v	2 80	3 10	1 60	7 v	0
100	3 20	5 v	2 80	6 v	4 0	-1
	4	2	3	1	5

=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