Метод минимальной стоимости

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел , или . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Составим с помощью этого метода опорный план уже рассмотренной задачи. Запишем ее условие в таблицу (табл. 2.4). Выбираем в таблице наименьшую стоимость (это стоимость, помещенная в клетке
, ) так как = , 100 ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке , и в клетке , . Заполняем любую из них, например , . Имеем , следовательно, записываем в нее  и исключаем из рассмотрения столбец
. В клетку , записываем  ед. и исключаем из рассмотрения строку . В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. В результате получен план
,
остальные значения переменных равны нулю.

Таблица 2.4

Поставщики	Потребители					Запасы
	10	7	4	1 100	4	100
	2 200	7 50	10	6	11	250
	8	5	3	2	2 200	200
	11	8 150	12 100	16	13 50	300
Потребности	200	200	100	100	250	850

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

Пример 2

Решим методом минимальной стоимости.
Опорный план по этому методу составлен в таблице 2.5.

Таблица 2.5

					Запасы
	13	7 15	11	5 15	30
	11	8 12	13 36	7	48
	6 18	10	12 6	9	24
Потребности	18	27	42	15	102

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

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

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

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

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

Таблица 2.6

					Запасы
	13	7 15	11	5 15	30	2,2,4,B
	11	8 12	13 36	7	48	1,1,5,B
	6 18	10	12 6	9	24	3,1,2,B
Потребности	18	27	42	15	102
	5,B	1,2,B	1,1,1,B	2,B

На первом шаге заполняем клетку
, исключаем 1-ый столбец, отметив в дополнительной строке буквой «В» факт выполнения заказа пункта . Находим новые разности минимальных тарифов по строкам (в столбцах они не изменились) и в 1-ой строке и в 4-ом столбце. Заполняем клетку и исключаем 4-й столбец и т.д. В конце остается последовательно заполнить клетки 3-го столбца остатками запасов в . Составленный опорный план дает значение .