рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Особые случаи, возникающие при применении двухэтапного мтода

Особые случаи, возникающие при применении двухэтапного мтода - раздел Информатика, МетодичЕСКИЕ УКАЗАНИЯ по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии   Рассмотрим Примеры Особых Случаев, Которые Встречаются При Ре...

 

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

Пример 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)

– Рис.4.12.2
(12.4)
(12.2)
(12.3)
x2
x1
(2.3)
(2.4)
(2.2)
x2
x1

 

Этап 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)

(3.4)
(3.2)
768аоо3.3)
x2
x1
– Рис. 4.12.3

 

Очевидно, что задача уже имеет каноническую форму.

Этап 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.

– Конец работы –

Эта тема принадлежит разделу:

МетодичЕСКИЕ УКАЗАНИЯ по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ... КиЕвский ПолИтехнИчЕСКий Институт... Симплекс метод...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Особые случаи, возникающие при применении двухэтапного мтода

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Формы ЗЛП
Задача математического программирования вида: называется задачей линейного программирования (ЗЛП). Основн

Эквивалентность различных форм ЗЛП
Все перечисленные формы ЗЛП являются эквивалентными в том смысле, что простыми преобразова­ниями задачу, имеющую одну из форм, легко привести к задаче, имеющей одну из оставшихся форм, причем по оп

Решение
Так как первое ограничение имеет знак “≥”, то в левую часть ограничения вводим избыточную переменную s1. Данное ограничение будет иметь вид: x1 + 2x2

Решение
В этом случае на переменную x2 не накладывается ограничение неотрицательности. Введя две новые неотрицательные переменные x2+≥0, x2–X

Упражнения
1) Укажите, какая из ниже приведенных форм задач является канонической? а) б)

Основные свойства ЗЛП
Для ЗЛП справедлива следующая теорема. Теорема (о существовании решения). Если допустимое множество X ЗЛП не пусто, а значение её конечно, то эта задача имеет решение.  

Способ перехода от одного ДБР к другому
Пусть ДБР x0 соответствует преобразованной задаче (13)-(15). Перейдем от него к новому ДБР x1. При этом рассмотрим возможность того, что только одна небазисная переменн

Условие оптимальности ДБР
Определение. Вектор-строка, на которую умножается слева xN в уравнении для ЦФ (13), называется век­тором относительных оценок, т.к. он указывает, в какую сторону

Табличный симплекс-метод
Пусть для исходной ЗЛП задано начальное ДБР, базис которого образуют первые m столбцов матри­цы A. Введем новую переменную z и с помощью элементарных преобразований Жордана-Гаусса преобразуем расши

Z-строка.
Текущая z-строка:(-1 –3/2 0 0 0 0 | 0) –(–3/2) × Новая ведущая строка:(-3 3/2 3/2 0 0 0 | 3) =Новая z-строка:(-4 0 3/2 0 0 0 | 3) БП

М - метод
Вернемся к введенной в примере 11.1 линейной модели. В первом и во втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из уравнений по одной искусственно

Двухэтапный метод
Исторически первым появился М-метод, но он имеет существенный недостаток: возможность появления ошибок в вычислениях, обусловленных очень боль­шой величиной коэффициента М. Например: М=100

Отсутствие допустимых решений
Если ограничения модели одновременно выполняться не могут, то задача не имеет допустимых решений. Такое решение всегда существует, когда все ограничения типа "≤", поскольку введение

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги