Исследование операций (стр. 5 )

Так как в функции Z нет положительных козффициэнтов, то опорные план :

{ x1=2/5; x2=9/5; x3=1; x4=0 }- оптимальный

Отметим, что двух этапный метод имеет то же множество итераций (таблиц), что и М-метод, но более точен.

2.7 Врожденные решения задачи Л. П.

Пример

Z=3x1+9x2 max

x1+4x2 < 8,

x1+2x2 < 4, x1, x2 > 0 .

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

x1+4x2 + x3 = 8,

x1+2x2 + x4 = 4 .

... и решаем :

Б	x1	x2	x3 x4	решение	i
Z	-3	-9	0 0	0
x3	1	4	1 0	8	2
x4	1	2	0 1	4	2

Z	-3/4	0	-3/4 0	18
x2	1/4	1	1/4 0	2	8
x4	1/4	0	-1/2 1	0	0

Z	0 0 3/2 3/2	18
x2	0 1 1/2 -1/2	2
x1		0

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

Причиной появления вырожденных решений является переопределенность :

то есть одно из ограничений задачи является избыточным.

Это легко увидеть на геометрической интерепретации задачи :

вырожденное решение

 

x1+4x2 < 8

 

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

2.8 Альтернативные решения задачи Л. П.

Пример : Z=2x1+4x2 max

x1+2x2 < 5

x1+2x2 < 4 ; x1, x2 > 0

если попытаться ввести такую переменную в базис, это не изменит целе- вую функцию

x2

Z=2x1+4x2

x1+x2 < 4

x1+2x2 < 5

D

C

B

A

x1

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

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

А   Б	x1	x2	x3 x4	решение
Z	-2	-4	0 0	0
x3	1	2	1 0	5	5/2
x4	1	1	0 1	4	4

В

Z	0	0 2 0	10
x2	1/2	1 1/2 0	5/2	5
x4	1/2	0 -1/2 1	3/2	3

С

Z		10
x2		1
x1		3

Любое решение, принадлежащее (ВС) можно определить как положительное среднее взвешанное от координат точек В ( x1=0,x2=5/2) и С ( x1=3,x2=1) .

где a принадлежит отрезку (0,1)

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

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

Неограниченность решения задачи Л. П. свидетельствует о том, что разработанная модель неточна, например :

- не учтены какие-либо ограничения,

- неправильно заданны коэффициэнты ограничений.

Как проявляется неограниченность при решении задачи симплекс-методом можно увидеть на примере :

Z=2x1+x2 max

2x1+x2< 10

2x1 < 40 x1, x2 > 0

Б	x1 x2 x3 x4	решение
Z	-2	0
x3 x4	1	10 40

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

Если же, кроме того коэффициэнт в строке Z отрицательный (положительный) и имеется max (min), то целевая функция так же неограниченна.

целевая функция неограниченна	пространство неограниченно но целевая функция ограниченна и есть решение

x2

x1

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

Это ситуации, когда уравнения ограничений несовместны. Здесь заслуживает внимания методы получения первоначальных решений, использующие искусственные переменные R. Симплекс-метод в этих случаях дает “псевдооптимальное” - то есть неверное решение. Узнать об этом можно потому, что в результате итерации, приводящей к оптимуму, по крайней мере 1 из R переменных будет положительна .

2.11 Интерпретация симплекс-таблиц. Анализ на чувствительность.

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

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

1) оптимального решения;

2) статуса ресурсов;

3) ценности каждого ресурса;

4) чувствительности решения к изменению запасов ресурсов и изменению коэффициэнтов целевой функции.

Для иллюстрации методов получения этой информации мы воспользуемся заключительной симплекс-таблицей задачи о краске :

Z=3xH+2xB max

xH + 2xB + S1 = 6 ( продукт А )

2xH + xB + S2 = 8 ( продукт В )

- xH + xB + S3 = 1 ( сырье )

2xB + S4 = 2 ( сырье )

xН ,xВ, S1,...,S4 > 0

Б	xН	xB	S1	S2	S3	S4	решение
Z	0	0	1/3	4/3	0	0	12(2/3)
xB	0	1	2/3	-1/3	0	0	1(1/3)
xН	1	0	-1/3	2/3	0	0	3(1/3)
S3	0	0	-1	1	1	0	3
S4	0	0	-2/3	1/3	0	1	2/3

1) Оптимальное решение.