Двойственная задача
Функция цели:
Ограничения:
≤ 
или в канонической форме 
.
Знак неравенства преобразуется в равенство только в том случае, когда соответствующая неравенству переменная xij не равна нулю. Отсюда для клетки, где 
сумма Ui+ Vj= Cij.
В представленной постановке наглядно представлена физическая сущность двойственных переменных – это некоторые потенциалы узлов. При этом если есть транспорт груза (энергии) от узла i к узлу j, то сумма потенциалов смежных узлов равна цене перевозки по рассматриваемой связи.
Из теоремы следует: для того чтобы первоначальный опорный план был оптимальным, необходимо выполнение следующих условий:
a) для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозки, стоящей в этой клетке,
 ;
| (8.28) |
b) для каждой незанятой клетки сумма потенциалов должна быть меньше или равна стоимости единицы перевозки, стоящей в этой клетке
 .
| (8.29) |
Если хотя бы одна незанятая клетка не удовлетворяет условию (8.29), то опорный план является неоптимальным и его можно улучшить, вводя в базис вектор, соответствующий клетке, для которой нарушается условие оптимальности, (т.е. в клетку надо переместить некоторое количество единиц груза).
Дата добавления: 2020-07-18; просмотров: 438;
Поиск по сайту
Узнать еще
- N-канальная СМО с отказами (задача Эрланга)
- Анализ целевых сценариев в организационных задачах судостроения
- В задачах искусственного интеллекта.
- В следующих задачах связь между аффинными и однородными координатами считается как в задачах 2, 3.
- Вероятностный анализ рискообразующих факторов в организационных задачах судоремонта
- Вторая задача динамики
- Выбор способа получения заготовки сложная задача.
- Вырожденные случаи. Открытая транспортная задача.
Публикации по технике и механике
Публикации по биологии
Публикации по информатике
Публикации по строительству
Публикации по физике
Публикации по химии
Публикации по электронике
Публикации по искусству
Публикации по истории
Публикации по медицине
