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

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

Двухэтапный метод

Двухэтапный метод - раздел Информатика, Методические указания по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии Исторически Первым Появился М-Метод, Но Он Имеет Существенный Недостаток: Воз...

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

Например: М=100000. Тогда коэффициенты в z-уравнении примера 2: (-4+700000) и (-1+400000). Из-за большой величины М вклад исходных ко­эффициентов (4 и 1) оказывается ничтожным. Вследствие ошибок округления, свойственных всем ЭВМ, процесс вычислений может стать нечувствительным к значению исходных коэф­фициентов при x1 и x2. При этом возникает опасность того, что эти переменные будут ин­терпретироваться как переменные, фигурирующие в целевой функции с нулевыми коэффи­циен­тами.

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

Введение искусственных переменных может интерпретироваться как введение в модель полезных для нас изменений (невязок). При этом полупространство, которое соответствует ограничению “³”, “поворачивается” в противоположном направлении, а гиперплоскость превращается в полупространство. Полученная модель отличается от исходной в той мере, в какой искусственные переменные отличаются от ноля, поэтому на первом этапе выполняется минимизация этих отличий от исходной модели. При этом сумма искусственных переменных рассматривается как сумма невязок, которую нужно минимизировать.

Пусть имеем ЗЛП:

 
 


(26)

 

Сформулируем такую вспомагательную задачу:

(27)

 

Двухэтапный метод базируется на следующих утверждениях:

1. Если исходная задача (26) имеет допустимое решение, то в оптимальном решении задачи (27) компоненты вектора R равны нолю.

 

2. Если в оптимальном решении задачи (27) некоторые искусственные переменные больше чем ноль, то исходная задача (26) не имеет решений.

 

Этап 1.

1. Вводятся искусственные переменные, необходимые для получения начальной (стартовой) точки.

2. Записывается новая целевая функция, предусматривающая минимизацию суммы ис­кусственных переменных при исходных ограничениях, видоизмененных за счет введения ис­кусственных переменных.

3. Решается задача линейного программирования.

Если минимальное значение новой целевой функции равно нулю (то есть все искусст­венные переменные имеют в оптимуме нулевые значения), исходная задача имеет допустимое решение. Переход к этапу 2.

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

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

а) Если все искусственные переменные есть небазисными, то перейти к этапу 2. В текущей точке избыточных ограничений нет.

б) Если среди искусственных переменных есть базисная, то это означает, что в текущей точке есть избыточное ограничение. Если при этом в строке і, что соответствует искусственной переменной, есть коэффициент aij¹0, где j- столбец небазисной неискусственной переменной (), то мы можем вывести из базиса эту искусственную переменную и ввести в него переменную, которой соответствует индекс j.

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

б.2) Если такой процесс не выведет все искусственные переменные из базиса, тогда каждая строка и соответственная искусственная переменная, в которой aij=0 для всех неискусственных переменных (), соответствует избыточному ограничению, которое является линейной комбинацией одного или нескольких других ограничений. Удаляем эти ограничения и переходим к этапу 2.

 

Этап 2.

Оптимальное базисное решение, полученное на этапе 1, используется в качестве началь­ного решения исходной задачи.

 

 

Реализацию этого метода проиллюстрируем на ЗЛП из примера 11.1.

Этап 1.

Так как необходимо ввести искусственные переменные R1 и R2 в первое и второе ог­раничения соответственно, этап 1 сводится к решению задачи (при этом c -строкой поступаем так же, как и с остальными ограничениями):

Так как R1 и R2 фигурируют в начальном решении, следует подставить в целевую функ­цию их выражения, полученные из соответствующих ограничений

 


Итерация 0 (начало вычислений).

Таблица 15

БП x1 x2 x3 R1 R2 x4 Решение
r -1
z -4 -1
R1
R2 -1
x4


Согласно условию оптимальности переменная x1 вводится в базис. Согласно условию допустимости переменная R1 выводится из базиса.

Итерация 1.

Таблица 16

БП x1 x2 x3 R1 R2 x4 Решение
r 5/3 -1 -7/3
z 1/3 0 4/3 0
x1 1/3 1/3
R2 5/3 -1 -4/3
x4 5/3 -1/3

Согласно условию оптимальности переменная x2 вводится в базис. Согласно условию допустимости переменная R2 выводится из базиса.

Итерация 2.

Таблица 17

БП x1 x2 x3 R1 R2 x4 Решение
r -1 -1
z 1/5 8/5 -1/5 18/5
x1 1/5 3/5 -1/5 3/5
x2 -3/5 -4/5 3/5 6/5
x4 -1

 

Поскольку оптимальное значение функции r равно нулю, начальная задача имеет допустимое решение и можна перейти к этапу 2.

 

Этап 2.

В начале этого этапа исключаются искусственные переменные (удаляются соответствующие столбцы последней таблицы этапа 1) и -строка. Получаем:

Таблица 18

БП x1 x2 x3 x4 Решение
z 1/5 18/5
x1 1/5 3/5
x2 -3/5 6/5
x4

 

. Согласно теории симплекс метода строка z содержит компоненты вектора относительных оценок небазисных переменных соответствующего ДБР. Полученная таблица совпадает с таблицей 10. Дальнейшие результаты вычислений совпадают с результатами вычислений М-метода.

 

Отметим, что элементы -строки могут быть получены и другим способом. Для этого из последней симплекс-таблицы этапа 1 (в нашем примере - из таблицы 17) базисные переменные (x1, x2, x4) должны быть выражены через небазисные (x3):

Потом их выражения подставляются в начальную целевую функцию:

Заполняется симплекс-таблица, которая соответствует ДБР, найденному на этапе 1.

 

Пример 11.2.

Пусть имеем ЗЛП:

min z=3x1+x2 (11.1)

2x1+x2 ³2 (11.2)

x1+2x2 ³2 (11.3)

x1,x2 ³0 (11.4)

Привидем задачу к канонической форме:

min z=3x1+ x2 +0s1 +0s2 (11.5)

2x1+ x2 -1s1 =2 (11.6)

x1+2x2 -1s2 =2 (11.7)

x1,x2 ,s1,s2³0 (11.8)

               
 
x2
 
   
x1
   
(11.3)
     
(11.2)
 
 


Рис 11. 1.

 

Этап 1.

1. Введем искусственные переменные в ограничения типа “³” и “=”. В нашей задаче это ограничения (11.2) и (11.3). Назовем искусственные переменные R1 и R2 соответственно. Тогда модели (11.5)-(11.8) будет соответствовать такая задача:

min z=3x1+ x2 +0s1 +0s2 +0R1 +0R2 (11.9)

2x1+ x2 -1s1 +R1 =2 (11.10)

x1+2x2 -1s2 +R2 =2 (11.11)

x1,x2 ,s1,s2³0 (11.12)

2. На первом этапе двухэтапного симплекс-метода необходимо минимизировать отличия от исходной математической модели. Сформулируем вспомогательную задачу:

Новая целевая функция в общем случае определяется выражением

r = ,

где – количество искуственных переменных.

В нашем случае : r = R1 + R2 .

Выразим R1 и R2 из уравнений (11.10), (11.11) соответственно:

R1 = 2 - 2x1- x2 +1s1

R2= 2 - x1 -2x2 +1s2

После подстановки получим такое выражение длс целевой функции:

r = R1 + R2 =4 - 3x1 -3x2 +1s1 +1s2

Перепишем целевую функцию в виде:

r + 3x1 +3x2 -1s1 -1s2 = 4

 

3. Построим начальную таблицу двухэтапного симплекс-метода.

Строку r заполняем в соответствии с выражением новой целевой функцией , которое было найдено на предыдущем шаге.

Строка z заполняется исходя из целевой функции (11.9) исходной задачи :

z -3x1 - x2 - 0s1 - 0s2 - 0R1 - 0R2=0.

В качестве базисных переменных выбираем те, которые в математической модели встречаются с коэффициентом 1 в одном уравнении, и 0 – в остальных. В нашем случае это будут переменные R1 и R2 .

 

Базисные переменные X1 x2 s1 s2 R1 R2 Решение  
r(min) -1 -1  
z -3 -1  
R1 -1
R2 2 -1

 

 

 

 

 


Теперь решим задачу табличным симплекс-методом, принимая строку r – строкой целевой функции, а над строкой z будем выполнять те же преобразования, что и над обычными ограничениями, это позволит нам при окончании этапа 1 получить полное начальное ДБР для этапа 2.

Согласно условию оптимальности в базис можно ввести как переменную так и , Введём в базис переменную , тогда согласно условию допустимости из базиса будет выведена переменная R2.. После выполнения операции замещения получим таблицу:

 

Базисные переменные x1 x2 s1 s2 R1 R2 Решение  
r(min) 3/2 -1 1/2 -3/2  
z -5/2 -1/2 ½  
←R1 3/2 -1 1/2 -1/2 2/3
x2 1/2 -1/2 1/2

s

Поскольку не все коэффициенты целевой функции r отрицательны, то продолжаем выполнять итерации симплекс-метода. Согласно условию оптимальности вводим в базис переменную x1 и, согласно условию допустимости, из базиса выводим переменную R1. Получаем таблицу:

 

Базисные переменные x1 x2 s1 s2 R1 R2 Решение
r(min) -1 -1
z -5/3 1/3 5/3 -1/3 8/3
x1 -2/3 1/3 2/3 -1/3 2/3
x2 1/3 -2/3 -1/3 1/3 2/3

 

 

В полученной таблице выполняется условие оптимальности для целевой функции r, то есть, мы получили решение, в котором эта функция достигает минимума. Поскольку оптимальное значение функции r равно нулю, начальная задача имеет допустимое решение и можна перейти к этапу 2. Согласно теории симплекс метода строка z содержит компоненты вектора относительных оценок небазисных переменных соответствующего ДБР. На этом первый этап метода заканчивается, столбцы R1 и R2 а также строка r удаляются из текущей таблицы и продолжаем решать задачу табличным симплекс-методом, для целевой функции z.

 

Этап 2

После выполнения первого этапа симплекс-метода получаем таблицу:

 

Базисные переменные x1 x2 s1 s2 Решение  
z(min) -5/3 1/3 8/3  
←x1 -2/3 1/3 2/3
x2 1/3 -2/3 2/3  

 

 

Согласно условию оптимальности вводим в базис переменную s2 и согласно условию допустимости выводим из базиса переменную x1. Получаем таблицу:

 

Базисные переменные x1 x2 s1 s2 Решение
z(min) -1 -1
s2 -2
x2 -1

 

 

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

Ответ: x1=0, x2 =2, z = 2

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

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

Методические указания по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии

Национальный технический университет Украины.. Киевский политехнический институт.. Симплекс метод..

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

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

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

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

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

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

Решение
Так как первое ограничение имеет знак “≥”, то в левую часть ограничения вводим избыточную переменную 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 линейной модели. В первом и во втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из уравнений по одной искусственно

Особые случаи, возникающие при применении двухэтапного мтода
  Рассмотрим примеры особых случаев, которые встречаются при решении задачи двухэтапным симплекс-методом. Пример 12.3 (Вырожденность). Пусть

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

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