Студопедия

КАТЕГОРИИ:

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


Алгоритм метода потенциалов решения транспортной задачи.




 

1. Найти начальный план перевозок транспортной задачи методом «северо-западного угла» или методом минимальной стоимости. Число заполненных клеток должно быть равным .

2. Найти .

3. Найти потенциалы из системы уравнений: , составленной для занятых клеток.

4. Найти оценки для свободных клеток: .

5. Если среди чисел нет отрицательных значений, все , то найденный опорный план являетсяоптимальным.

6. Если же для некоторой свободной клетки , то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану , причем

Z( ) ≤ Z( )

7. Чтобы решение улучшить, выбирают среди отрицательных оценок наибольшую по абсолютной величине (при нескольких равных выбирают любую) и для соответствующей свободной клетки строим циклпересчета.

Цикл– это замкнутая ломаная, соединяющая несколько занятых клеток таблицы. Две последовательные вершины цикла лежат либо в одной строке, либо в одном столбце; в одной их них объем увеличивается (в клетке ставится знак «+»); в другой – уменьшается настолько же единиц (в клетке ставится знак «–»).

7. Среди клеток, имеющих знак «–» отыскивается та, которая содержит минимальную величину поставки. Эта величина прибавляется к содержимому клеток, имеющих знак «+» и вычитается из содержимого клеток, имеющих знак «–».

8. Для нового опорного плана заново рассчитываются потенциалы , и оценки(п.3)


Поделиться:

Дата добавления: 2015-07-26; просмотров: 77; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты