Метод минимального тарифа (ММТ)

При построении опорного плана этим методом сначала заполняется ячейка таблицы с минимальным тарифом(если таковых несколько, то можно начинать с любой из них; обычно по порядку – слева направо сверху вниз). При этом либо удовлетворяется заявка соответствующего потребителя, либо исчерпывается запас поставщика. Далее ячейки заполняются в порядке возрастания стоимостей.

Пример 2. Рассмотрим применение ММТ на решении той же ТЗ, что в п.2.1 (табл. 2 и 3), и будем поэтапно заполнять табл. 4.

Этап 1. Начинаем, например, с ячейки (4,1), в которой мы имеем одну из наименьших стоимостей перевозки (с ₄₁=0): х ₄₁=min(а ₄ ,b ₁)=min(10,45)=10. Закрыта 4-я строка. Переходим в следующую ячейку (табл.5).

Этап 2. Среди оставшихся ячеек заполняем ячейку (1,2), имеющую наименьшую стоимость (с ₁₂=1): х ₁₂=min(а ₁ ,b ₂)=min(40,35)=35. Закрыт 2-й столбец. Переходим в следующую ячейку.

Этап 3. Среди оставшихся ячеек заполняем, например, ячейку (1,3), имеющую одну из наименьших стоимостей (с 13=2): х 13=min(а 1 -b 2, b 3)=min(5,55)=5. Закрыта 1-я строка. Переходим в следующую ячейку. Этап 4. Среди оставшихся ячеек наименьшую стоимость имеет ячейка (3,4), с 34=2. Поэтому х 34=min(а 3 ,b 4)=min(90,65)=65. Закрыт 4-й столбец. Переходим в следующую ячейку.		Таблица 5
Вj Аi
	–			–
		–		–
	–	–
		–	–	–

Этап 5. Среди оставшихся ячеек заполняем ячейку (2,1), имеющую одну из наименьших стоимостей (с ₂₁=3): х ₂₁=min(60,35)=35. Закрыт 1-й столбец. Переходим в следующую ячейку стоимостей, с ₂₁=3,. х ₂₁=min(а ₂, b ₁ -а ₄)=min(60,35)=35. Закрыт 1-й столбец. Переходим в следующую ячейку.

Этап 6. Среди оставшихся ячеек заполняем ячейку (2,4), имеющую наименьшую стоимость (с ₂₄=3): х ₂₄=min(25, 50)=25. Закрыта 2-я строка. Переходим в следующую ячейку.

Этап 7. Осталась ячейка (3,3): х ₃₃=min(25, 25)=25. За к рыты 3-я строка и 3-й столбец.

Заполнение таблицы закончено. Число заполненных (базисных) клеток равно m+n -1=7, т.е. действительно построен опорный план перевозок.

Получен начальный опорный план с матрицей перевозок Х _н.ст=

(фиктивный поставщик в матрице перевозок не указан). По этому плану из пункта А ₁ завезено 35 ед. груза в В ₂ и 5 – в В ₄, из А ₂ –35 ед. груза в А ₁ и 25 – в В ₃, из А ₃ – 25 ед. груза в В ₃ и 65 – в В ₄. Те 10 ед. груза, «завезённые» из фиктивного пункта А ₄, на самом деле не довезены в В ₁. Затраты по плану Х _н.ст составляют z_н.ст= 1×35+2×5+3×35+3×25+5×25+2×65=480 (ден. ед.), что на 100 ед. меньше, чем в МСЗУ.

Для МНС также справедливо замечание 2 (о нулевом базисном элементе), только здесь изменяется понятие соседней ячейки. Ячейкой, соседней с данной, считается любая открытая ячейка в данной строке и в данном столбце.

 

2.3. Определение оптимального плана перевозок

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

При решении ТЗ, как и при решении любой задачи ЛП, осуществляется последовательный переход от одного опорного плана (если оно не оптимально) к другому. Для проверки оптимальности полученного плана воспользуемся теорией двойственности. Составим к ТЗ двойственную и запишем их в табл. 6.

Таблица 6

Прямая задача	Двойственная задача
z=	w=

Переменные ДЗ называются:

u_i – потенциал поставщика A_i, i= 1¸ m;

v_j –потенциал потребителя B_j, j= 1¸ n.

Сформулируем в терминах потенциалов критерий оптимальности плана перевозок.

Теорема 4. Пусть Х* = { } – план перевозок ТЗ. Для того, чтобы этот план был оптимальным, необходимо и достаточно, чтобы существовали потенциалы поставщиков u_i, i= 1¸ m, и потенциалы потребителей v_j, j= 1¸ n, удовлетворяющие условиям:

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

; (6)

– если по плану Х* имеет место перевозка от поставщика A_i потребителю B_j, то сумма их потенциалов равна соответствующей стоимости перевозки единицы груза, т.е. если >0, то

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

u_i+v_j=с_ij. (7)

Т.к. занятых ячеек (а, значит, и уравнений (7)) т + п- 1, а неизвестных потенциалов т + п, то одному из неизвестных нужно придать произвольное значение (обычно полагают u ₁=0), и тогда остальные потенциалы определяются однозначно. Затем для свободных ячеек проверяются условия (6), или

D _ij = u_i+v_j-с_ij≤ 0 (6¢)

(D _ij называется оценкой соответствующей ячейки). Если все эти неравенства выполняются, то, согласно приведённому выше критерию (теор. 4), план перевозок оптимальный. Если хотя бы одно из неравенств (6¢) не выполняется, то план не является оптимальным. В этом случае из свободных ячеек с положительной оценкой выбирается та, для которой эта оценка является наибольшей. Если наибольших оценок несколько, то выбирается та из ячеек, где меньше тариф.

В транспортной таблице для выбранной свободной ячейки проводится замкнутая ломаная прямая, звенья которой лежат только в строках или столбцах и соединяют какие-либо две ячейки, а вершины (кроме начальной) расположены в занятых ячейках. Такая ломаная прямая называется циклом. Для каждойячейки можно построить только один цикл. Вершинам цикла приписываются чередующиеся знаки «+» и «-», причём свободная ячейка снабжается знаком «+». В ячейках, соответствующих отрицательным вершинам цикла, отыскивается наименьшее значение объёма перевозок, α =min , которое перераспределяется по ячейкам цикла, т.е. прибавляется к переменным в ячейках со знаком «+» и вычитается от переменных в ячейках со знаком «-». В ячейках, не вошедших в цикл, переменные остаются неизменными. Ячейка «-», по которой определялась величина α (для неё х_ij = α), остаётся пустой. Если таковых ячеек несколько, то одна из них (желательно с большим тарифом) остаётся пустой, а в остальных проставляются нули.

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

В новом плане вновь определяются потенциалы поставщиков и потребителей, и
Рисунок1.

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

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: