Исследование систем управления деловыми организациями методами теории принятия решений

Полагаем U2=0, запишем это значение во вторую строку последнего столбца. Рассмотрим занятые клетки этой строки. Берем клетку Х23, для нее выполняется условие , Отсюда при U2=0 получаем V3=55. Записываем это значение в последнюю строку в третий столбец. Далее рассматриваем следующие клетки, где один из потенциалов известен:

Д

ля клетки (2;2): , ,то

Для клетки (2;4): , , то

Для клетки (3;4): , , то

Для клетки (1;2): , , то

Для клетки (1;1): , ,

Найденные значения потенциалов занесены в таблицу.

Вычисляем оценки свободных клеток:

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

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

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

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

Цикл имеет вид:

15 10

30

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

25

15 15

Новое опорное решение имеет вид:

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

 Скачать реферат