Метод минимального элемента
Этот метод является вариантом метода северо-западного угла, учитывающим специфику матрицы транспортных затрат С= . В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план, сокращая общее количество итераций по его дальнейшей оптимизации. Формальное описание алгоритма. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х0. Пусть элементом с минимальным порядковым номером оказался . Возможные три случая: а) если , то оставшуюся часть -й строки заполняем нулями; б) если , то оставшуюся часть -го столбца заполняем нулями; в) если , то оставшуюся часть -й строки и -го столбца заполняем нулями. Дале этот процесс повторяют с незаполненной частью матрицы Х1. Пример 1. Найти начальный базисный план методом минимального элемента для Табл. 3. следующей задачи. Таблица. 3.
Цифры в скобках указывают порядок заполнения элементов в матрице Х0 (табл. 3.4). Соответствующее значение целевой функции равно
3*8 + 1*5 + 3*7 + 5*2 + 6*4 + 8*1 = 92 Таблица 4
Решение транспортной задачи при вырожденном опорном плане Опорный план называется вырожденным, если число его ненулевых перевозок k меньше ранга матрицы ограничений. В процессе построения начального плана или при его улучшении очередной план может оказаться вырожденным. Рассмотрим два случая. 1. Вырожденный план является начальным Х0. Тогда выбирают некоторые нулевые элементы матрицы Х0 в качестве базисных так, чтобы при этом не нарушалось условие базисного плана. Число этих элементов равняется . Далее данные элементы заменяют на (где – произвольное, бесконечно малое число) и рассматривают их как обычные базисные элементы плана. Задачу решают как невырожденную, а в последнем оптимальном плане Хk вместо пишут нули. 2. Вырожденный план получается при построении плана Хk+1 на базе Хk, если цепочка в плане Хk содержит не менее двух минимальных нечетных элементов. В таком случае в матрице Хk+1 полагают равным нулю только один из этих элементов, а остальные заменяют на , и далее решают задачу как невырожденную. Если на k-м шаге , то при переходе от Хk к Хk+1 значение целевой функции не изменяется, а в базис вводится элемент , для которого перевозка станет равной . Пример 2. Решим Т-задачу со следующими условиями (см. Табл.6) Проверим условие баланса Предварительный этап. Методом минимального элемента строим начальный базисный план Х0 (Табл. 5) Таблица 5
Так как m + n – 1 = 6; k = 4, то план х0 – вырожденный; l = m+ n -1 – k = 2. Два нулевых элемента Х0 делаем базисными так, чтобы не нарушить условие опорности. Выберем в качестве базисных элементов , и положим их равными . Схема перевозок для плана Х0 показана на рис. 6.
Рис. 6.
Для вычисления предварительных потенциалов выберем начальный пункт А1 и допустим, что . Потенциалы всех остальных пунктов вычисляем по формулам
, Для проверки оптимальности плана х0 строим матрицу С1, элементы которой вычисляем по соотношению
Так как в матрице С1 элемент С23 = – 3 < 0, то план Х0 – неоптимальный.
Первая итерация. Второй этап.
В результате построения Х1 в базис вводим . План Х1 является вырожденным (в цепочке есть два минимальных элемента). Поэтому один из этих элементов, например , в плане Х1 заменяем на .
Вторая итерация. Первый этап
Второй этап.
Третья итерация. Первый этап.
Так как в матрице С3 нет отрицательных элементов, план Х2 – оптимальный.
Популярное: Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (301)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |