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

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

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

Пример 2. 9. 1:

f₀ = 3х₁ + 9х₂ ® maх                                   

при ограничениях:       х₁ + 4х₂ + х₃ = 8                                             (1)

х₁ + 2х₂ + х₄ = 4                                                           (2)

х _i  0, i = 1,..,4

Таблица20

№ итер.	Базис	х1	х2	х3	х4	Знач	Отнош.	Формула
N=0 х2 ввод.   х3 искл.	f ур	-3	-9	0	0	0
	х3	1	4	1	0	8	8:4=2
	х4	1	2	0	1	4	4:2=2
N=1 х1 ввод., х4 искл.	fур	-3/4	0	9/4	0	18		fур=fyp+9x2
	х2	1/4	1	1/4	0	2	2:1/4=8	x2= x3/4
	х4	1/2	0	-1/2	1	0	0:1/2=0	x4= x4-2 x2
							(вырожденное	решение)
N=2 оптимум	fур	0	0	3/2	3/2	18		fур=fyp+3/4x1
	х2	0	1	1/2	-1/2	2		x2= x2-1/4 x1
	х1	1	0	-1	2	0		x 1 = x 4:1/2=х4^.2

 

max f =18 при плане Х* = (0;2;0;0).

Решим задачу графически. Через точку оптимума А проходят три прямые. Задача содержит только две переменные х₁ и х₂, поэтому для идентификации точки А достаточно 2-х прямых. Отсюда вывод: одно из ограничений является избыточным.

 

 

 

 

Рис. 20.

 

Информация, что некоторые ресурсы не нужны для достижения поставленной цели, оказывается полезной при практической реализации результатов исследования.

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

Теоретически, вырожденность может привести к зацикливанию.

Зацикливание.

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

Пример 2. 9. 1. Появление промежуточного вырожденного решения.

 Рассмотрим пример.

 

В стандартной форме	В канонической форме
f0 = 3х1 + 2х2 ® maх	fур                 - 3х1 - 2х2=0
при ограничениях	при ограничениях
4х1 + 3х2 £ 12                 (1)	4х1 + 3х2+х3=12
4х1 + х2 £ 8                         (2)	4х1 + х2+х4 =8
4х1 – х2 £ 8                          (3)	4х1–х2+х5= 8
х1, х2 ³ 0	х i ³ 0 i =1,2,...,5

n = 5; m = 3;  (n - m)= 2      число небазисных переменных

Таблица21

№ итер.	Базис	х1	х2	х3	х4	x5	Знач	Отнош	Формула
N=0   х1 ввод.,   х4 искл.	fур	-3	-2	0	0	0	0
	х3	4	3	1	0	0	12	12:3=4
	х4	4	1	0	1	0	8	8:4=2
	x5	4	-1	0	0	1	8	8:4=2
N=1   х2 ввод.,   х3 искл.	fур.	0	-5/4	0	¾	0	6		fyp = fyp + 3x1
	х3	0	2	1	-1	0	4	4:2=2	x 3 = x 3 -4 x 1
	х1	1	1/4	0	¼	0	2	2:1/4=8	x 1 = x 4:4
	х5	0	-2	0	-1	0	0		x 5 = x 5 -4 x 1
N=2 оптимум	fур	0	0	5/8	1/8	0	17/2		fyp = fyp+5/4x 2
	х2	0	1	1/2	-1/2	0	2		x 2 = x 3:2
	х1	1	0	-1/8	3/8	0	3/2		x 1 = x 1 -1/4 x 2
	х5	0	0	1	-2	1	4		X 5 = x 5 +2 x 2

 

В рассмотренном примере на второй итерации вырожденности нет, причем значение целевой функции возросло с 6 до . Из примера можно сделать следующий вывод: итерации симплекс - метода должны выполняться до тех пор, пока не будет выполнено условие оптимальности! Точка С переопределена (через нее проходят 3 прямые).

Рис. 21.