Реферат Курсовая Конспект
Особые случаи, возникающие при применении двухэтапного мтода - раздел Информатика, МетодичЕСКИЕ УКАЗАНИЯ по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии Рассмотрим Примеры Особых Случаев, Которые Встречаются При Ре...
|
Рассмотрим примеры особых случаев, которые встречаются при решении задачи двухэтапным симплекс-методом.
Пример 12.3 (Вырожденность).
Пусть имеем математическую модель:
min z=x1+x2 (12.1)
-x1 + x2 ³ 1 (12.2)
2x1 + x2 £ 4 (12.3)
x2 ³ 1 (12.4)
x1,x2 ³0 (12.5)
Приведем задачу к канонической форме:
min z= x1 + x2 +0s1 +0s2 +0s3 (12.6)
-x1 + x2 -1s1 = 1 (12.7)
2x1+ x2 +1s2 = 4 (12.8)
x2 -1s3 =1 (12.9)
x1,x2 ,s1,s2,s3³0 (12.10)
|
|
|
|
|
|
|
|
|
|
|
Этап 1
1. Введем искусственные переменные в ограничения типа “³” и “=”. В нашей задаче это ограничения (12.2) и (12.4). Назовем искусственные переменные R1 и R2 соответственно. Тогда модель (12.6)-(12.10) будет иметь такой вид:
min z= x1+ x2 +0s1 +0s2 +0s3 +0R1 +0R2 (12.11)
-x1+ x2 -1s1 +R1 = 1 (12.12)
2x1+ x2 +1s2 = 4 (12.13)
x2 -1s3 +R2 = 1 (12.14)
x1,x2 ,s1,s2,s3³0 (12.15)
2. R1 и R2 выражазим из соответствующих уравнений (12.12), (12.14):
R1 = 1 + x1- x2 +1s1
R2= 1 - x2 +1s3
Получим такую целевую функцию:
r = R1 + R2 = 2 + x1 -2x2 +1s1 +1s3
Перепишем целевую функцию в виде:
r - 1x1 + 2x2 -1s1 -1s3 = 2
3. Построим начальную таблицу двухэтапного симплекс-метода.
Базисные переменные | x1 | x2 | s1 | s2 | s3 | R1 | R2 | Решение | |
r(min) | -1 | -1 | -1 | ||||||
z | -1 | -1 | |||||||
R1 | -1 | 1 | -1 | ||||||
R2 | -1 | ||||||||
s2 |
Согласно условию оптимальности вводим в базис переменную x2 . На данном этапе невозможно однозначно определить переменную, которою необходимо выводить из базиса согласно условию допустимости.
Мы можем вывести из базиса как переменную R1, так и переменную R2, потому что отношения коэффициентов столбца решений к положительным коэффициентам рабочего столбца одинаковы, и равны единице. Остановим свой выбор на переменной R1. В результате операции замещения получачим таблицу:
Базисные переменные | x1 | x2 | s1 | s2 | s3 | R1 | R2 | Решение | |
r(min) | -1 | -2 | |||||||
z | -2 | -1 | |||||||
x2 | -1 | -1 | |||||||
R2 | 1 | -1 | -1 | ||||||
s2 | -1 |
Одна из базисных переменных (R2) равна нулю. Это означает, что соответствующее решение является вырожденным. С практической точки зрения ситуация полностью объясняется присутствием в модели одного избыточного ограничения. Продолжаем решение задачи по алгоритму симплекс- метода.
Поскольку не все коэффициенты целевой функции отрицательные, то продолжаем выполнять итерации симплекс-метода. Согласно условию оптимальности вводим в базис переменную x1 и, согласно условию допустимости, выводим из базиса переменную R2. Получим таблицу:
Базисные переменные | x1 | x2 | s1 | s2 | s3 | R1 | R2 | Решение |
r(min) | -1 | -1 | ||||||
z | -2 | -1 | ||||||
x2 | -1 | |||||||
x1 | -1 | -1 | ||||||
s2 | -2 | -3 |
Поскольку из базиса выведены все искусственные переменные, то мы получили вырожденное допустимое решение исходной задачи. То есть в текущей точке присутствуют избыточные ограничения, и при этом среди них нет линейно-зависимых.
Итак, если в результате минимизации целевой функции r из базиса выводятся все искусственные переменные, и хотя бы одна из базисных переменных равна 0, то в текущей точке есть избыточное ограничение, и при этом среди них нет линейно-зависимых.
Этап 2
Выполним последнюю итерацию:
Базисные переменные | x1 | x2 | s1 | s2 | s3 | Решение |
z(min) | 1 | -2 | ||||
x2 | -1 | |||||
x1 | 1 | -1 | ||||
s2 | -2 |
Согласно условию оптимальности вводим в базис переменную s1 и согласно условию допустимости выводим из базиса переменную x1. Получаем таблицу:
Базисные переменные | x1 | x2 | s1 | s2 | s3 | Решение |
z(min) | -1 | -1 | ||||
x2 | -1 | |||||
s1 | -1 | |||||
s2 |
Данная таблица - оптимальная, потому что в строке z коэффициенты при небазисных переменных – отрицательные (условие оптимальности для задачи на минимум). Задача решена.
Ответ: x1=0, x2 =1, z = 1.
Пример 12.4 (Наличие избыточных ограничений, которые есть линейной комбинацией других ограничений.)
Пусть имеем математическую модель:
max z=x1+x2 (12.16)
x1 + x2 = 4 (12.17)
x2 =2 (12.18)
x1 + 2x2 = 6 (12.19)
x1,x2 ³0 (12.20)
|
|
|
|
|
|
Очевидно, что задача уже имеет каноническую форму.
Этап 1
1. Введем искусственные переменные в ограничения типа “³” и “=”. В нашей задачи это ограничения (12.17), (12.18) и (12.19). Назовем искуственные переменные R1 ,R2 и R3 соответственно. Тогда модель (12.16)-(12.20) будет иметь такой вид:
max z= x1+ x2 +0R1 +0R2 +0R3 (12.21)
x1+ x2 +R1 = 4 (12.22)
x2 + R2 = 2 (12.23)
x1+ 2x2 +R3 = 6 (12.24)
x1,x2 ³0 (12.25)
2. Переменные R1 ,R2 и R3 выразим из уравнений (12.22), (12.23), (12.24) соответствено:
R1 = 4 - x1- x2
R2= 2 - x2
R3 = 6 - x1- 2x2
Получаем такую целевую функцию:
r = R1 + R2 + R3 = 12 - 2x1 - 4x2
Перепишем целевую функцию в виде:
r + 2x1 + 4x2 = 12
3. Построим начальную таблицу двухэтапного симплекс-метода.
Базисные переменные | x1 | x2 | R1 | R2 | R3 | Решение | |
R(min) | |||||||
z | -1 | -1 | |||||
R1 | |||||||
R2 | 1 | ||||||
R3 |
Согласно условия оптимальности вводим в базис переменную x2, и, согласно условия допустимости, выводим из базиса переменную R2.
Получим таблицу:
Базисные переменные | x1 | x2 | R1 | R2 | R3 | Решение | |
r(min) | -4 | ||||||
z | -1 | ||||||
R1 | 1 | -1 | |||||
x2 | |||||||
R3 | -2 |
Поскольку не все коэффициенты целевой функции отрицательные, то продолжаем выполнять итерации симплекс-метода. Согласно условия оптимальности вводим в базис переменную x1, а согласно условия допустимости можно вывести из базиса как переменную R1 так и переменную R3, остановимся на переменной R1. Получим таблицу:
Базисные переменные | x1 | x2 | R1 | R2 | R3 | Решение | |
r(min) | -2 | -2 | |||||
z | |||||||
x1 | -1 | ||||||
x2 | |||||||
R3 | -1 | -1 |
Поскольку не выведены все искусственные переменные из базиса, а минимум функции r равен нолю, и при этом переменная R3 не может быть выведена из базиса, то R3-строка соответствует избыточному ограничению, которое является линейной комбинацией одного или нескольких других ограничений (в нашем случае двух других ограничений). Удаляем это ограничение и переходим к этапу 2.
Итак, если в результате минимизации целевой функции r из базиса не выводятся все искусственные переменные, и хотя бы одна из базисных переменных равна нолю, то в текущей точке есть избыточные ограничения, которые являютсялинейной комбинацией одного или несколькихкох других ограничений.
Этап 2
В результате удаления избыточного ограничения и столбиков, отвечающих исскуственным переменным, получили такую таблицу:
Базисные переменные | x1 | x2 | Решение | |
z(max) | ||||
x1 | ||||
x2 |
Очевидно, что данная таблица - оптимальна. Задача решена.
Ответ: x1=2, x2 =2, z = 4.
– Конец работы –
Эта тема принадлежит разделу:
НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ... КиЕвский ПолИтехнИчЕСКий Институт... Симплекс метод...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Особые случаи, возникающие при применении двухэтапного мтода
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов