Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




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

 

Рассмотрим алгоритм, реализующий этот метод.

Шаг 1. Каждому поставщику Ai; (т. е. каждой строке) поста­вим в соответствие некоторое число ui (i=l, m), называемое по­тенциалом Аi, а каждому потребителю Bj (т. е. каждому столбцу) поставим в соответствие некоторое число vj (j=1,n), называемое потенциалом Bj .

Для каждой заполненной клетки, т. е. для каждой базисной переменной, строится соотношение

ui+vj=cij

Полученная система должна содержать m+n—1 уравнений (так как количество базисных переменных равно т + п—1) с m + п не­известными. Как известно, такая система имеет множество реше­ний, и любое из них будет содержать искомые потенциалы. Что­бы найти одно из решений, значение одного потенциала в системе задается произвольно. Обычно считают, что ui = 0, и находят зна­чения остальных потенциалов. Значения потенциалов записывают справа и снизу таблицы против соответствующих строк и столб­цов.

Шаг 2. Для каждой незаполненной клетки, т. е. для каждой небазисной переменной, рассчитываются так называемые косвен­ные тарифы (с'ij) по формуле

c’ij=ui+vj

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

Шаг 3. Проверяем полученный план на оптимальность по критерию оптимальности плана транспортной задачи. Если для каждой незаполненной клетки выполняется условие

с'ij-cij ≤0,

то план является оптимальным.

В противном случае полученный план не оптимальный, и необходимо переходить к новому базисно­му плану путем перемещения перевозки в клетку, отвечающей условию max [с'ij—сij>0]. Если таких клеток более одной, то до­говоримся перемещать перевозку в первую по порядку. Выбран­ная клетка помечается в таблице. Переменная, стоящая в этой клетке, вводится в базис.

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



Замечание. После перевода незаполненной клетки в число за­полненных количество заполненных клеток становится равным m+n . Для такого количества клеток всегда можно построить цикл, и он будет единственным. Направление построения цикла (по часовой стрелке или против) несущественно.

Шаг 5. В каждой клетке цикла, начиная с незаполненной, про­ставляются поочередно знаки «+» и «—» (обычно они ставятся в правом нижнем углу клетки). В клетках со знаком «—» выбира­ется минимальная величина. Новый базисный план получается пу­тем сложения выбранной величины с величинами, стоящими в клетках цикла со знаком « + », и вычитания этой величины из величин, стоящих в клетках со знаком «—».

Выбранная минимальная величина будет соответствовать переменной, выводимой из базиса. Если таких величин более одной, то из базиса выводится любая из соответствующих им переменных. Значения переменных,
включенных в цикл, после описанной корректировки переносятся в новую таблицу. Все остальные перемен­ные записываются в новую таблицу без изменений. Осуществляется переход к шагу 1.

Замечание. Метод потенциалов обеспечивает монотонное убы­вание значений целевой функции и позволяет за конечное число шагов найти ее минимум.


.

mylektsii.ru - Мои Лекции - 2015-2019 год. (0.023 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал