Математические методы в коммерческой деятельности. Буравлева О.Ю. - 23 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

На этом способе уменьшения стоимости в дальнейшем и будет основан алгоритм оптимизации
плана перевозок. Циклом в транспортной задаче мы будем называть несколько занятых клеток, соеди-
ненных замкнутой ломанной линей, которая в каждой клетке совершает поворот на 90°.
1) 2) 3)
Рис. 5.1 Варианты цикла
Нетрудно убедиться, что каждый цикл имеет четное число вершин и значит, четное число звеньев
(стрелок). Условимся отмечать знаком «+» те вершины цикла, в которых перевозки необходимо умень-
шить. Цикл с отмеченными вершинами будем называть «означенными». Перенести какое-то количество
единиц груза по означенному циклу – это значит увеличить перевозки, стоящие в положительных вер-
шинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на
то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и
заявками не меняется: по-прежнему сумма перевозок в каждой строке равна запасам этой строки, а
сумма перевозок в каждом столбце – заявке этого столбца. Таким образом, при любом циклическом пе-
реносе, оставляющем перевозки неотрицательными допустимый план остается допустимым. Стоимость
же плана при этом может меняться: увеличиваться или уменьшаться. Назовем ценой цикла увеличение
стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно цена
цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, причем стоящие в положи-
тельных вершинах берутся со знаком «+», а в отрицательных со знаком «–». Обозначим цену цикла че-
рез γ. При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину
γ. При перемещении по нему k единиц груза стоимость перевозок увеличится на kγ. Очевидно, для улуч-
шения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Ка-
ждый раз, когда нам удается совершить такое перемещение стоимость плана уменьшается на соответст-
вующую величину kγ. Так как перевозки не могут быть отрицательными, мы будем пользоваться только
такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положи-
тельные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что
дальнейшее улучшение плана невозможно, оптимальный план достигнут.
Метод последовательного улучшения плана перевозок и состоит в том, что в таблице отыскиваются
циклы с отрицательной ценой, по ним перемещаются перевозки, и план улучшается до тех пор, пока
циклов с отрицательной ценой уже не останется. При улучшении плана циклическими переносами, как
правило, пользуются приемом, заимствованным из симплекс-метода: при каждом шаге (цикле) заменя-
ют одну свободную переменную на базисную, то есть заполняют одну свободную клетку и взамен того
освобождают одну из базисных клеток. При этом общее число базисных клеток остается неизменным и
равным m + n – 1. Этот метод удобен тем, что для него легче находить подходящие циклы.
Можно доказать, что для любой свободной клетки транспортной таблицы всегда существует цикл, и
притом единственный, одна из вершин которого лежит в этой свободной клетке, а все остальные в ба-
зисных клетках. Если цена такого цикла с плюсом в свободной клетке, отрицательна, то план можно
улучшить перемещением перевозок по данному циклу. Количество единиц груза k которое можно пе-
реместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цик-
ла (если переместить большее число единиц груза, возникнут отрицательные перевозки).
Примененный выше метод отыскания оптимального решения транспортной задачи называется рас-
пределенным; он состоит в непосредственном отыскании свободных клеток с отрицательной ценой
цикла и в перемещении перевозок по этому циклу.
Распределен метод решения транспортной задачи, с которым мы познакомились обладает
одним недостатком: нужно отыскивать циклы для всех свободных клеток и находить их цены.
От этой трудоемкой работы нас избавляет специальный метод решения транспортной задачи,
который называется методом потенциалов.
Пример. Решить распределенным методом транспортную задачу, исходные данные которой приве-
дены в табл. 5.6.
Таблица 5.6

Страницы