Метод наименьшей стоимости
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую. И в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Алгоритм: · Из таблицы тарифов выбирают наименьшую стоимость. И в клетку, которая ей соответствует, вписывают меньшее из чисел. · Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются. · Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п.1, в противном случае задача решена. Метод потенциалов Наиболее простым методом ТЗ является метод потенциалов. Потенциалами называются условные числа Ui ,Vj , приписанные определённым образом каждому поставщику и потребителю. Теорема(условия оптимального плана): Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых клеток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток
Опорный план должен быть не вырожденным (r=m+n-1 – невырожденный план) Алгоритм решения: 1. Строим начальные планы методом северо-западного угла и методом наименьшей стоимости из них выбираем лучший 2. Находим потенциалы поставщика и потребителя, пользуясь первым условием оптимальности плана Ui + Vj < Cij 3. Проверяем второе условие оптимальности плана для свободных клеток
Если оно выполнено, то план оптимален, если нет то улучшаем план. 4. Улучшение плана: a. При не выполнении второго условия в клетку заносим нарушение со знаком плюс. Такие клетки называются потенциальными. b. Среди всех потенциальных клеток выбираем клетку с наибольшим нарушением. c. Строим для выбранной клетки замкнутый контур, состоящий из вертикальных и горизонтальных отрезков прямой, причем вершины контура лежат в занятых клетках. За исключением той клетки, для которой строится контур d. Вершины контура поочерёдно помечаем знаками плюс и минус, начиная с клетки, для которой строится контур. e. Среди клеток помеченных знаком минус выбираем наименьшею перевозку и на эту величину увеличиваем перевозку в клетках помеченных знаком плюс и уменьшаем в клетках помеченных знаком минус в результатах переназначения освобождается одна клетка. 5. Вновь полученный план проверяем на оптимальность.
Популярное: Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (224)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |