Разделы

Авто
Бизнес
Болезни
Дом
Защита
Здоровье
Интернет
Компьютеры
Медицина
Науки
Обучение
Общество
Питание
Политика
Производство
Промышленность
Спорт
Техника
Экономика

М-Метод

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

Геометрический метод.

Имеется 2 предприятия, производящие 2 продукта.

  А В
Цена
Выпуск, т Х1 Х2

L = 3x1 + 5x2 → max

3x1 + 5x2 = 15

5x2 = –3x1 + 15

x1 ≥ 0

x2 ≥ 0

3x1 + 9x2 ≤ 75

x1 + x2 ≤ 10

x1 – x2 ≤3

ПОР –прямая опорных решений.

3x1 + 9x2 = 75

x1 + x2 = 10

x1 = 2,5, x2 = 7,5

L = 45

 

В задачах линейного программирования находится в ОДР.

 

R1, R2 – искусственные переменные, вводятся только в те ограничения, в которых нет остаточных переменных, т.е. имеющие знаки >=, =.

{ 1 + х2 + R1 = 3
1 + 3х2 - х3 + R2= 6
х1 + 2х2 + х4 = 4

х1, х2 , х3, х4 , R1, R2 ≥ 0

6-3=3

 

х1, х2 , х3 =0; х4 = 4; R1= 3; R2 = 6 – начальное допустимое базисное решение.

 

За использование искусственной переменной в составе целевой функции вводится «штраф»: достаточно большой положительный коэффициент М в задаче min и достаточно большой по абсолютному значению отрицательный коэффициент в задаче max.

 

Z = 4х1 + х2 + M R1 + M R2

 

Так как М достаточно большое положительное число, то в задаче минимизации, в оптимальном решении, переменные R1 и R2 обратятся в ноль.

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

Так как в целевой функции присутствуют базисные переменные R1 и R2 , их необходимо выразить через небазисные переменные , то есть из 1-го и2-го ограничений, и подставить в целевую функцию.

 

R1 =3 - 3х1 - х2

R2= 6 - 4х1 - 3х2 + х3

 

Z = 4х1 + х2 + M (3 - 3х1 - х2) + M (6 - 4х1 - 3х2 + х3) = (4 - 7M) х1 + (1 – 4M) х2 + + Mх3+ 9M

Z - (4 - 7M) х1 - (1 – 4M) х2 - Mх3 = 9M

Z+(-4+7M)x1+(-1+4M)x2-Mx3=9M

 

Итерация 0:

Баз. Пер. х1 х2 х3 R1 R2 х4 Решение
Z 7 М - 4 4 М - 1 - М 9 М
R1
R2 -1
х4

 

Итерация 3 - Оптимальная таблица:

Баз. Пер. х1 х2 х3 R1 R2 х4 Решение
Z 7/5 – М - М -1/5 17/5
х1 2/5 -1/5 2/5
х2 -1/5 3/5 9/5
х3 -1

х1 = 2/5 ; х2 = 9/5 ; x3=1; Z = 17/5 Значения R1, R2=0

 

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

 

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

Двухэтапный метод (не использует коэффициентов М)

 

1 этап: Вводятся искусственные переменные, записывается новая целевая функция, соответствующая минимизации суммы искусственных переменных. Задача решается симплекс-методом. Если полученное минимизированное решение новой целевой функции равно нулю, то исходная задача имеет допустимое решение. Переход к этапу 2. Если на первом этапе значение целевой функции не равно 0, то исходное задача не имеет допустимых решений, процесс вычисления заканчивается.

2 этап: полученное оптимальное решение на первом этапе используется в качестве начального решения на втором этапе при исходной целевой функции.

Рассмотрим тот же пример и решим двухэтапным методом.

 

min Z = 4 х1 + х2

 

{ 1 + х2 + R1 = 3
1 + 3х2 - х3 + R2= 6
х1 + 2х2 + х4 = 4

х1, х2 , х3 =0; х4 = 4; R1= 3; R2 = 6 – начальное допустимое базисное решение.

 

I этап:

r = R1+ R2

 

{ 1 + х2 + R1 = 3
1 + 3х2 - х3 + R2= 6
х1 + 2х2 + х4 = 4

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

r = R1 + R2 = 3 - 3х1 - х2 + 6 - 4х1 - 3х2 + х3 = - 7х1 - 4х2 + х3 + 9

r + 7х1 + 4х2 - х3 = 9

 

итерация 0:

Баз. Пер. Х1 х2 х3 R1 R2 х4 Решение
r - 1
R1
R2 -1
х4

 

Оптимальная таблица:

Баз. Пер. Х1 х2 х3 R1 R2 х4 Решение
r -1 -1
R1 1/5 3/5 -1/5 3/5
R2 -3/5 -4/5 3/5 6/5
х4 -1

Так как r=0, то переходим к этапу 2.

 

Этап II:

 

Min Z = 4x1+ x2

 

{ х1 + (1/5)х3 = 3/5
х2 – (3/5)х3 = 6/5
х3 + х4 = 1

х1, х2, х3, х4 ≥ 0

 

4 - 3=1, если

х3 = 0, то х1 = 3/5, х2 = 6/5, х4 = 1 – начальное допустимое базисное решение

Выразим базисные переменные через небазисные:

х1 =3/5 – (1/5) х3

х2= 6/5 + (3/5)х3

 

Z = 4 ( 3/5 – (1/5) х3 ) + ( 6/5 + (3/5) х3 ) = (-1/5) х3 + 18/5

Z + (1/5) х3 = 18/5

 

Баз. Пер. Х1 х2 х3 х4 Решение
Z 1/5 18/5
х1 1/5 3/5
х2 -3/5 6/5
х4

 

Оптимальную таблицу получим на следующей итерации:

х1 = 2/5, х2 = 9/5, Z = 17/5

 

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

Рассмотрим примеры:

Необходимо ли использование искусственных переменных для получения начального решения в следующих задачах?

1. Max z=x1+x2

2x1+3x2=5

7x1+2x2<=6

x1,x2>=0

2.min z=x1+x2+x3+x4

 
 


2x1+x2+x3=7

4x1+8x2+x4=8

 

X1,x2,x3,x4>=0

 

Особые случаи применения симплекс-метода

1. Вырожденность

2. Альтернативное оптимальное решение

3. Неограниченные решения

4. Отсутствие допустимых решений

 

Дата публикации:2014-01-23

Просмотров:209

Вернуться в оглавление:

Комментария пока нет...


Имя* (по-русски):
Почта* (e-mail):Не публикуется
Ответить (до 1000 символов):







...

 

2012-2017 lekcion.ru. За поставленную ссылку спасибо.