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

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

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

Отсутствие допустимых решений, с практической точки зрения означает, что модель построена не корректно, так как введенные ограничения оказались противоречивыми, иногда следует построить модель, имеющую другую структуру, в которой используются, например ограничения типа «или-или», которые не требуют одновременного выполнения ограничений.

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

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

R =12 -3 × х₁-4 × х₂+х₄, так как решается задача maх f₀ вычтем из целевой функции штраф: f = 3х₁ + 2х₂ - M × R = 3х₁ + 2х₂ - M × (12 -3 × х₁-4 × х₂+х₄ )= ‑12M - Mх + х × (3 +3M) + х × (2 + 4M) ® maх

Таблица 25

№ итер.	базис	х1	х2	х3	х4	R	Знач	отнош	формула
N=0 х2 ввод., х3 искл.	f ур	-3-3 M	-2-4 M	0	M	0	-12 M
	х3	2	1	1	0	0	2	2:1=2
	R	3	4	0	-1	1	12	12:4=3
N=1 псевдо- оптимум	f ур	1+5 M	0	2+4 M	M	0	4-4 M		fyp=fyp+(2 + 4M) × x2
	х2	2	1	1	0	0	2		x 2 = x 3:1
	R	-5	0	-4	-1	1	4		R=R-4 × x2

 

 

Рис.25

Так как в f₀ -уравнении нет больше отрицательных коэффициентов при небазисных переменных, то симплекс метод завершается. Поскольку искусственная переменная в псевдооптимуме R=4 >0, то в методе больших штрафов это означает, что задача не имеет допустимых решений.

Первый этап двух этапного метода.

 

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

Таблица 26

№ Итер.	базис.	х1	х2	х3	х4	R 1	знач	Отнош.	формула
N=0 х2 ввод., х3 искл.	f ур	3	4	0	-1	0	12
	х3	2	1	1	0	0	2	2:1=2
	R1	3	4	0	-1	1	12	12:4=3
N=1 псевдо- оптимум	f ур	-5	0	-4	-1	0	4		f ур = f ур -4 × x2
	х2	2	1	1	0	0	2		x 2 = x 3:1
	R 1	-5	0	-4	-1	1	4		R 1 =R 1 -4x 2

 

Оптимальное значение целевой функции f =4>0, что в полученном результате 1-го этапа двух этапного метода свидетельствует об отсутствии допустимых решений.