<<
>>

Переход от одного опорного решения к другому

Наличие положительной оценки свободной клетки (Δij > 0) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению.

При этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток — свободной.

Для свободной клетки с Δij > 0 строится цикл (цепь, многоугольник), все вершины которого кроме одной находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (—) и (+). У вершин со знаком (—) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (—). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение.

Рассмотрим переход от одного опорного решения к другому на заданном примере.

Строим цикл для клетки (1,3), имеющей положительную оценку. У вершин цикла ставим знаки (+) и (—) и записываем грузы:

У вершин со знаком (—) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл:

Новое опорное решение:

Проверим полученное решение на оптимальность. Для этого запишем его в распределительную таблицу, найдем потенциалы занятых и оценки свободных клеток.

Имеем

Построим цикл для клетки с положительной оценкой Δ21 = 1:

Произведем перераспределение грузов:

Получим новое решение, которое занесем в таблицу.

Проверим его на оптимальность.

Получим

Все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Итак,

Стоимость транспортных расходов равна

По сравнению с исходным опорным решением транспортные расходы уменьшились на 1610 — 1280 = 330 усл. ед.

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

Еще по теме Переход от одного опорного решения к другому:

  1. IX. Общие итоги второго периода в истории науки уголовного права в России
  2. Глава IIIМЕНТАЛИТЕТ И ЯЗЫК
  3. Глава IVОСОБЕННОСТИ ЕДИНСТВА РУССКОЙ КУЛЬТУРЫ( Предварительные замечания)
  4. 7.2. Правила плавных переходов внутри одной сцены
  5. 4.4.1. Об организации внешних условий развития педагогической рефлексии: краткий обзор подходов и методов в практике обучения рефлексивному мышлению
  6. § 65. Симплекс-метод решения задач линейного программирования, М-метод
  7.   ПРОСТРАНСТВО  
  8. III. Маркс
  9. О СВЯЗИ ПРОЦЕССОВ РАЗВИТИЯ ЛИТЕРАТУРНОГО ЯЗЫКА И СТИЛЕЙ ХУДОЖЕСТВЕННОЙ ЛИТЕРАТУРЫ
  10. 3.7. Поликодовые тексты в учебно-педагогическом дискурсе
  11. Терминологический словарь
  12. Тема 3. Система государственною и местного управления в период Монголо-татарского ига и золотой орлы (ХІІІ-ХѴІ вв.)
  13. Переход от одного опорного решения к другому