Метод северо-западного угла

Сущность этого метода становится понятной при рассмотрении следующеего примера. Пусть условия транспортной задачи заданы табл. 8.4

Таблица 8.4

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

У поставщика А₂ осталось 150 ед.груза. Частично удовлетворяем потребителя B₂ за счет оставшегося у поставщика А₂ груза. Для этого сравниваем этот остаток с потребностями потребителя В₂: 150 < 200, записываем 150 ед. в клетку А₂В₂, так как запасы А₂ полностью израсходованы, прочеркиваем остальные клетки второй строки. Читателю рекомендуется довести данный процесс до конца и получить табл. 8.4.

На этом построение первоначального опорного плана заканчивается.

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

Проверим, является ли план, построенный в табл. 8.4, опорным. Видим, что, начиная движение от занятой клетки A₁B₁, двигаясь только по занятым клеткам, вернуться в нее, невозможно. Аналогичная ситуация с другими начальными клетками. Следовательно, план является опорным, и в то же время он является невырожденным, поскольку содержит точно 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 (ед. стоимости).

Если при составлении опорного плана как-то учитывать стоимость перевозки единицы груза, то, очевидно, план будет значительно ближе к оптимальному.

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

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

Читателю рекомендуется с помощью этого метода составить опорный план уже рассмотренной задачи (табл. 8.5).

Таблица 8.5

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

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

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

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

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

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

, ;

,

(i=1,…,m; j=1,…,n)

Числа называются потенциалами соответственно поставщиков и, потребителей.

Действительно, условия

;

определяют m+n ограничений типа «равенство». Каждому равенству i соответствует двойственная переменная U_i. а равенству j - двойственная переменная V_j . В двойственной задаче ограничивающих условий столько, сколько переменных в основной задаче, т.е. mn. В правой части двойственного ограничения - C_ij.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: