П.5. Алгоритм метода потенциалов.
1. проверяется тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой; 2. находится опорный план перевозок путем составления 1-й таблицы одним из способов - северо-западного угла или наименьшей стоимости; 3. проверяем план (таблицу) на удовлетворение системе уравнений и на невыражденность; в случае вырождения плана добавляем условно заполненные клетки с помощью « 0 »; 4. для опорного плана определяются потенциалы ui и vj, соответствующие базисным клеткам, по условию: ui + vj = cij Таких уравнений будет m + n - 1 , а переменных будет m + n. Для их определения одну из переменных полагают равной любому постоянному значению. Обычно принимают u1 = 0. После этого для небазисных клеток опорного плана определяются оценки , где При этом если £0, то опорный план оптимален, если же среди окажется хотя бы один положительный элемент, то опорный план можно улучшить. Улучшение опорного плана осуществляется путем целенаправленного переноса из клетки в клетку транспортной таблицы отдельных перевозок без нарушения баланса по некоторому замкнутому циклу. Циклом транспортной таблицы называется последовательное соединение замкнутой ломаной линией некоторых клеток, расположенных в одном ряду (строке, столбце), причем число клеток в одном ряду должно быть равно двум. Каждый цикл имеет четное число вершин, одна из которых в клетке с небазисной переменной, другие вершины в клетках с базисными переменными. Клетки отмечаются знаком «+», если перевозки в данной клетке увеличиваются и знаком «–» в противном случае. Цикл начинается и заканчивается на выбранной небазисной переменной и отмечается знаком «+». Далее знаки чередуются. Количество единиц продукта, перемещаемого из клетки в клетку по циклу, постоянно, поэтому сумма перевозок в каждой строке и в каждом столбце остаются неизменными. Стоимость всего плана изменяется на цену цикла. Цена цикла – это стоимость перевозки единицы продукта по циклу с учетом знаков вершин. Улучшение опорного плана осуществляется путем нахождения цикла с отрицательной ценой. 5. Если критерий оптимальности не выполняется, то переходим к следующему шагу. Для этого: а) в качестве начальной небазисной переменной принимается та, у которой оценка имеет максимальное значение; б) составляется цикл пересчета; в) находится число перерасчета по циклу: число X=min{Xij}, где Xij - числа в заполненных клетках со знаком « - »; г) составляется новая таблица, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла; 6. Возвращаются к пункту 3 и т.д. 7. Через конечное число шагов (циклов) обязательно приходят к ответу, так как транспортная задача всегда имеет решение.
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (160)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |