![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод потенциалов
Построенный одним из описанных выше методов исходный план можно довести до оптимального с помощью симплекс-метода. В силу особенностей модели транспортной задачи (ограничения имеют вид равенств, каждая неизвестная, входит только в два уравнения, коэффициенты при неизвестных единицы) процесс ее решения симплекс-методом является громоздким. Поэтому для нахождения оптимального плана транспортной задачи созданы специальные методы, самым распространенным из которых считается метод потенциалов.
Рассмотрим алгоритм, реализующий этот метод. Шаг 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. В каждой клетке цикла, начиная с незаполненной, проставляются поочередно знаки «+» и «—» (обычно они ставятся в правом нижнем углу клетки). В клетках со знаком «—» выбирается минимальная величина. Новый базисный план получается путем сложения выбранной величины с величинами, стоящими в клетках цикла со знаком «+», и вычитания этой величины из величин, стоящих в клетках со знаком «—». Выбранная минимальная величина будет соответствовать переменной, выводимой из базиса. Если таких величин более одной, то из базиса выводится любая из соответствующих им переменных. Значения переменных, Замечание. Метод потенциалов обеспечивает монотонное убывание значений целевой функции и позволяет за конечное число шагов найти ее минимум.
|