Переход от одного опорного решения к другому
Наличие положительной оценки свободной клетки (Δij > 0) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению.
При этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток — свободной.Для свободной клетки с Δij > 0 строится цикл (цепь, многоугольник), все вершины которого кроме одной находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (—) и (+). У вершин со знаком (—) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (—). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение.
Рассмотрим переход от одного опорного решения к другому на заданном примере.
Строим цикл для клетки (1,3), имеющей положительную оценку. У вершин цикла ставим знаки (+) и (—) и записываем грузы:
У вершин со знаком (—) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл:
Новое опорное решение:
Проверим полученное решение на оптимальность. Для этого запишем его в распределительную таблицу, найдем потенциалы занятых и оценки свободных клеток.
Имеем
Построим цикл для клетки с положительной оценкой Δ21 = 1:
Произведем перераспределение грузов:
Получим новое решение, которое занесем в таблицу.
Проверим его на оптимальность.
Получим
Все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Итак,
Стоимость транспортных расходов равна
По сравнению с исходным опорным решением транспортные расходы уменьшились на 1610 — 1280 = 330 усл. ед.
Еще по теме Переход от одного опорного решения к другому:
- IX. Общие итоги второго периода в истории науки уголовного права в России
- Глава IIIМЕНТАЛИТЕТ И ЯЗЫК
- Глава IVОСОБЕННОСТИ ЕДИНСТВА РУССКОЙ КУЛЬТУРЫ( Предварительные замечания)
- 7.2. Правила плавных переходов внутри одной сцены
- 4.4.1. Об организации внешних условий развития педагогической рефлексии: краткий обзор подходов и методов в практике обучения рефлексивному мышлению
- § 65. Симплекс-метод решения задач линейного программирования, М-метод
- ПРОСТРАНСТВО
- III. Маркс
- О СВЯЗИ ПРОЦЕССОВ РАЗВИТИЯ ЛИТЕРАТУРНОГО ЯЗЫКА И СТИЛЕЙ ХУДОЖЕСТВЕННОЙ ЛИТЕРАТУРЫ
- 3.7. Поликодовые тексты в учебно-педагогическом дискурсе
- Терминологический словарь
- Тема 3. Система государственною и местного управления в период Монголо-татарского ига и золотой орлы (ХІІІ-ХѴІ вв.)
- Переход от одного опорного решения к другому