Тема 1.3. Симплексный метод нахождения оптимального управленческого решения



Поиск и нахождение оптимального решения симплексным методом

Общая идея симплексного метода. Симплексные преобразования. Нахождение исходного опорного и оптимального решений. Анализ этапов принятия управленческого решения.

Примеры решения типовых задач

Пример 3. Найти исходное опорное решение ЗЛП.

Запишем задачу в канонической форме, вводя в левую часть первого неравенства системы ограничений дополнительную переменную  со знаком «+», а в левую часть второго неравенства дополнительную переменную   со знаком «минус».

Заполним симплексную таблицу 10 ( -строку не заполняем, пока система не будет приведена к единичному базису). Система уравнений имеет две базисные переменные  и  (столбцы  и  содержат единицу и нули), отмечаем это в столбце «Базис».

Таблица 10

Базис с.о.
x4 x5 2 1 1 1 2 -1 -2 4 2 1 0 0 0 1 0 0 0 -1 24 22 10 12 22 10  
               

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

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

    Таблица 11

Базис
x4 x5 x1 0 0 1 3 3 -1 -6 2 2 1 0 0 0 1 0 2 1 -1 4 12 10
             

В таблице 8 имеется теперь три базисные переменные ,  и . Это означает, что система приведена к единичному базису .

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

Пример 4. Проверить, будет ли решение  оптимальным. Если нет, то можно ли его улучшить.

Решение

Заполним -строку. Для этого вверху таблицы запишем коэффициенты при переменных и свободный член из целевой функции, слева от таблицы – коэффициенты при базисных переменных в целевой функции. В -строке под базисными переменными  запишем нули.

       Таблица 12

    2 -3 6 1 0 0 0  
Базис с. о.
1 0 2 x4 x5 x1 0 0 1 3 3 -1 -6 2 2 1 0 0 0 1 0 2 1 -1 4 12 10  
                 

Вычислим оценки свободных переменных, значение целевой функции  по и заполним таблицу 10:

 

  

       Таблица 13

    2 -3 6 1 0 0 0  
Базис с. о.
1 0 2 x4 x5 x1 0 0 1 3 3 -1 -6 2 2 1 0 0 0 1 0 2 1 -1 4 12 10  
  0 4 -8 0 0 0 24  

 

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

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

Пример 5.Выполнить переход от решения  к улучшенному решению  и так далее до получения оптимального решения.

Решение

Рассмотрим симплексную таблицу 13, из которой следует решение .          Для построения нового опорного решения  нужно от базиса  перейти к новому базису .

1. Выберем наибольшую по абсолютной величине отрицательную оценку , следовательно, столбец переменной  станет разрешающим, а переменная  должна быть введена в базис.

2. Для положительных элементов разрешающего столбца  составим симплексные отношения  = 6;  = 5 (столбец с.о.), выбираем наименьшее из них – это 5, оно находится в третьей строке, которая и станет разрешающей строкой. Значит, базисная переменная этой строки  будет выведена из базиса и станет свободной. На пересечении разрешающих столбца и строки имеем разрешающий элемент .

3. Проведем в таблице итерацию симплексных преобразований с выбранным разрешающим элементом:

- разделим каждый элемент разрешающей строки на разрешающий элемент a33 = 2;

- в разрешающем столбце все элементы, кроме разрешающего элемента, заменим нулями;

- все остальные элементы таблицы, включая -строку, пересчитаем по правилу прямоугольника. Например, элемент  в новой таблице получится равным . В результате получим симплексную таблицу 14.

               Таблица 14

    2 -3 6 1 0 0 0  
  Базис с.о.
1 0 6 3 -1 1/2 0 4 -1/2 0 0 1 1 0 0 0 1 0 -1 2 -1/2 34 2 5 - 1 -
  4 3 0 0 0 - 4 64  

4. Запишем новое опорное решение . В этом решении свободные переменные равны нулю: x1 = 0, x2 = 0, x6 = 0, а базисные – свободным членам: x3 = 5; x4 = 34; x5 = 2.

Значение целевой функции находится в правом нижнем углу симплексной таблицы: . Оно также проверяется путем подстановки компонент решения  в целевую функцию .

5. Новое опорное решение  «лучше» предыдущего опорного решения , так как . Вычислим двумя способами приращение целевой функции при переходе от  к :

; .

Решение  не является оптимальным, поскольку в строке оценок симплексной таблицы есть отрицательная оценка . Но  можно улучшить, т.к. в столбце над этой оценкой имеется положительный элемент .

6. Отрицательная оценка  определяет переменную, вводимую в новый базис  - это . Определим, какую переменную следует вывести из базиса . Составим симплексные отношения для положительных элементов столбца над отрицательной оценкой . Такое отношение  является единственным и выполняется для второй строки, в которой базисной переменной является , она и выведется из базиса . Проведя итерацию симплексных преобразований с разрешающим элементом , получим симплексную таблицу 15 с базисом .

                Таблица 15

    2 -3 6 1 0 0 0  
  Базис с.о.
1 0 2 2,5 -0,5 0,25 2 2 0,5 0 0 1 1 0 0 0,5 0,5 0,25 0 1 0 35 1 5,5  
  2 11 0 0 2 0 68  

Опорное решение  «лучше» решения , так как . В -строке нет отрицательных оценок, поэтому решение  оптимальное, а значение  - наибольшее.

Ответ: ; .


Дата добавления: 2018-02-15; просмотров: 238; ЗАКАЗАТЬ РАБОТУ