II. Метод наименьших затрат

Найдем методом наименьших затрат первоначальное распределение поставок задачи №5.1. Выберем клетку с наименьшим коэффициентом затрат – клетку (2,3). Клетке (2,3) соответствует коэффициент затрат II. Метод наименьших затрат - student2.ru . В эту клетку дадим максимально возможную поставку: II. Метод наименьших затрат - student2.ru .

Мощности поставщика II. Метод наименьших затрат - student2.ru полностью реализованы, поэтому вычеркнем вторую строку.

поставщики потребители запасы
II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru
II. Метод наименьших затрат - student2.ru  
II. Метод наименьших затрат - student2.ru  
II. Метод наименьших затрат - student2.ru  
потребности  

Клетка (1,1), из оставшихся клеток, имеет наименьший коэффициент затрат - II. Метод наименьших затрат - student2.ru . Дадим в клетку (1,1) максимально возможную поставку II. Метод наименьших затрат - student2.ru . В результате, чего потребности первого потребителя II. Метод наименьших затрат - student2.ru полностью удовлетворены. Вычеркнем из последующего рассмотрения первый столбец. Следующую поставку дадим в клетку (1,3): II. Метод наименьших затрат - student2.ru и вычеркнем третий столбец.

поставщики потребители запасы
II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru
II. Метод наименьших затрат - student2.ru
II. Метод наименьших затрат - student2.ru  
II. Метод наименьших затрат - student2.ru  
потребности  

Клетки (1,2) и (3,2) имеют равные коэффициенты затрат: II. Метод наименьших затрат - student2.ru . Выберем для поставки третьего поставщика II. Метод наименьших затрат - student2.ru , так как за счет него можно полностью удовлетворить запросы второго потребителя. В клетку (3,2) дадим поставку II. Метод наименьших затрат - student2.ru . Потребности потребителя II. Метод наименьших затрат - student2.ru полностью удовлетворены.

Дадим поставку в клетку (1,4): II. Метод наименьших затрат - student2.ru . На этом шаге выпадает из рассмотрения первая строка, мощности первого поставщика реализованы. Заполним последнюю клетку – клетку (3,4): II. Метод наименьших затрат - student2.ru .

поставщики потребители запасы
II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru
II. Метод наименьших затрат - student2.ru
II. Метод наименьших затрат - student2.ru  
II. Метод наименьших затрат - student2.ru  
потребности  

Число заполненных клеток в данном распределении оказалось равным II. Метод наименьших затрат - student2.ru .

Общие суммарные затраты на перевозку всего груза методом наименьших затрат будут равны: II. Метод наименьших затрат - student2.ru . Таким образом, первое опорное решение, построенное методом «наименьших затрат» дало лучший результат по сравнению с решением, построенным методом «северо-западного угла» (5200<5760). Но нельзя с уверенностью сказать, что полученное методом «наименьших затрат» решение будет оптимальным, то есть общая стоимость перевозок, равная 5200, будет наименьшей. Для проверки оптимальности полученного решения воспользуемся «методом потенциалов».

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

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

Критерий оптимальности: для того чтобы решение транспортной задачи было оптимальным, необходимо и достаточно, чтобы существовала система из II. Метод наименьших затрат - student2.ru чисел II. Метод наименьших затрат - student2.ru и II. Метод наименьших затрат - student2.ru , которые удовлетворяли бы следующим условиям:

1) II. Метод наименьших затрат - student2.ru для занятых клеток; (5.6)

2) II. Метод наименьших затрат - student2.ru для свободных клеток. (5.7)

Числа II. Метод наименьших затрат - student2.ru называются потенциалами пунктов отправления, числа II. Метод наименьших затрат - student2.ru называются потенциалами пунктов назначения.

Замечание: пункты отправления (пункты назначения) и соответствующие им потенциалы обозначим одними и теми же буквами II. Метод наименьших затрат - student2.ru ( II. Метод наименьших затрат - student2.ru ), чтобы не вводить новые обозначения.

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

Потенциалы II. Метод наименьших затрат - student2.ru и II. Метод наименьших затрат - student2.ru находим, решая систему уравнений (5.6).

Эта система содержит II. Метод наименьших затрат - student2.ru уравнений, ровно столько занятых клеток будет в опорном решении, а переменных II. Метод наименьших затрат - student2.ru и II. Метод наименьших затрат - student2.ru эта система содержит II. Метод наименьших затрат - student2.ru . Доказано, что система уравнений (5.6) является совместной неопределенной, ранг системы (5.6) равен II. Метод наименьших затрат - student2.ru . Найдем любое решение системы (5.6), зафиксировав значение одной из переменных (обычно потенциалу II. Метод наименьших затрат - student2.ru придают нулевое значение). После этого все остальные переменные определяются однозначно, причем решение имеет интересную особенность: зная значение одной переменной, сразу можно получить значение другой.

Вернемся к решению исходной транспортной задачи. Проверим опорное решение, полученное «методом наименьших затрат» на оптимальность.

Обнулим потенциал II. Метод наименьших затрат - student2.ru . По заданному II. Метод наименьших затрат - student2.ru , легко найдем потенциалы II. Метод наименьших затрат - student2.ru , II. Метод наименьших затрат - student2.ru и II. Метод наименьших затрат - student2.ru : II. Метод наименьших затрат - student2.ru ;

II. Метод наименьших затрат - student2.ru ;

II. Метод наименьших затрат - student2.ru .

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

поставщики потребители запасы
II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru
II. Метод наименьших затрат - student2.ru 5 5 + II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru 70 7 - II. Метод наименьших затрат - student2.ru 120
II. Метод наименьших затрат - student2.ru 2 3 II. Метод наименьших затрат - student2.ru 3 - 4 + II. Метод наименьших затрат - student2.ru 5
II. Метод наименьших затрат - student2.ru 5 6
потребности  

Зная, что II. Метод наименьших затрат - student2.ru , найдем потенциал II. Метод наименьших затрат - student2.ru :

II. Метод наименьших затрат - student2.ru .

Зная, что II. Метод наименьших затрат - student2.ru , а II. Метод наименьших затрат - student2.ru , найдем потенциалы II. Метод наименьших затрат - student2.ru и II. Метод наименьших затрат - student2.ru : II. Метод наименьших затрат - student2.ru ;

II. Метод наименьших затрат - student2.ru .

После того, как все потенциалы найдены, вычислим суммы соответствующих потенциалов для свободных клеток:

II. Метод наименьших затрат - student2.ru ;

II. Метод наименьших затрат - student2.ru ;

II. Метод наименьших затрат - student2.ru ;

II. Метод наименьших затрат - student2.ru ;

II. Метод наименьших затрат - student2.ru ;

II. Метод наименьших затрат - student2.ru .

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

В клетке (2,4) сумма потенциалов больше соответствующего коэффициента затрат, следовательно, построенный опорный план не является оптимальным.

Для того чтобы улучшить план, составим цикл перераспределения поставок. Возьмем ту клетку, где сумма потенциалов больше коэффициента затрат. Если таких клеток несколько, то рациональнее выбрать ту клетку, в которой сумма потенциалов превосходит стоимость поставок на большую величину. В нашей задаче это будет клетка (2,4). Из этой клетки необходимо "прошагать шахматной ладьей" по занятым клеткам так, чтобы снова вернуться в исходную клетку, причем после каждого шага надо поворачивать "с горизонтали на вертикаль" или наоборот. Для каждой свободной клетки цикл по приведенному правилу составляется единственным образом.

Построим для клетки (2,4) цикл перераспределения поставок. В клетке (2,4) поставим знак "+" и из этой клетки перейдем либо в занятую клетку (2,3), либо в одну из занятых клеток (1,4) или (3.4), то есть в клетку, расположенную либо в той же строке, либо в том же столбце, что и клетка (2,4).

Если пойти в клетку (3,4), то из нее затем необходимо будет перейти в клетку (3.2), из которой в занятую клетку уже не попадешь, так как во втором столбце занятых клеток больше нет. Поэтому пойдем в клетку (2,3), поставим в ней знак "-". Из клетки (2,3) можно перейти только в занятую клетку (1,3). Перейдем в клетку (1,3), поставим в ней знак "+". Из этой клетки можно перейти либо в занятую клетку (1,1), либо в занятую клетку (1,4). Если пойти в клетку (1,1), то из нее затем в занятую клетку перейти нельзя, так как в первом столбце занятых клеток больше нет, поэтому из клетки (1,3) перейдем в клетку (1,4), поставим в ней знак "-" (после каждого шага знаки чередуются). Из клетки (1,4) вернемся в исходную клетку (2,4). Цикл замкнулся, обозначим его пунктирной линией.

Среди отрицательных вершин цикла (в клетках, где стоят знаки "-") выберем клетку с наименьшей по величине поставкой II. Метод наименьших затрат - student2.ru .

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

В новом опорном плане клетка (1,4) стала свободной, а клетка (2,4) занятой, то есть переменную II. Метод наименьших затрат - student2.ru мы ввели в базис, а переменную II. Метод наименьших затрат - student2.ru вывели из базиса. Число занятых клеток осталось прежним II. Метод наименьших затрат - student2.ru . Для полученного опорного решения, положив II. Метод наименьших затрат - student2.ru , снова найдем потенциалы из системы (5.6). Значения потенциалов по мере вычисления будем заносить в таблицу поставок. Затем вычислим суммы потенциалов для свободных клеток и проверим с помощью системы неравенств (5.7), является ли полученное решение оптимальным. В клетке (3.1) критерий оптимальности не выполнен:

II. Метод наименьших затрат - student2.ru . Для клетки (3.1) построим замкнутый цикл перераспределения поставок. «Означим» цикл, начиная с клетки (3.1), присвоив ей знак «+», клетке (3.4) присвоим знак «-» и т. д.

поставщики потребители запасы
II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru
II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru 4 - 4 II. Метод наименьших затрат - student2.ru 5 + 7 6
II. Метод наименьших затрат - student2.ru 2 2 3 - II. Метод наименьших затрат - student2.ru 130 II. Метод наименьших затрат - student2.ru 4 +
II. Метод наименьших затрат - student2.ru 5 + II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru 6 7 8 -
потребности  

Среди отрицательных вершин цикла выберем клетку с наименьшей по величине поставкой II. Метод наименьших затрат - student2.ru .

Перераспределим 110 единиц груза по построенному циклу. В тех клетках, где стоит знак "+" прибавим 110 единиц груза, в тех клетках, где стоит знак "-" вычтем этот груз.

поставщики потребители запасы
II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru II. Метод наименьших затрат - student2.ru
II. Метод наименьших затрат - student2.ru 5 5 7 6
II. Метод наименьших затрат - student2.ru 2 3
II. Метод наименьших затрат - student2.ru 110 6 7
потребности  

В новом опорном плане клетка (3,4) стала свободной, а клетка (3,1) занятой, то есть переменную II. Метод наименьших затрат - student2.ru мы ввели в базис, а переменную II. Метод наименьших затрат - student2.ru вывели из базиса. Проверим на оптимальность, полученное опорное решение: положив II. Метод наименьших затрат - student2.ru , вычислим значения остальных потенциалов. Как видно из последней таблицы поставок неравенство II. Метод наименьших затрат - student2.ru выполнено для всех свободных клеток. Следовательно, полученное опорное решение является оптимальным. Общая стоимость всех перевозок для данного плана будет наименьшей из всех возможных: II. Метод наименьших затрат - student2.ru .

Ответ.Оптимальный план транспортировки груза:

II. Метод наименьших затрат - student2.ru ,

при котором транспортные расходы по обеспечению продуктом всех четырех пуктов потребления будут равны 4970.

Наши рекомендации