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

Значение Z увеличилось с 12 до 12 2/3. Т. к. в строке Z нет ни одного отрицательного коэффициента, это значит, что нет свободных переменных, увеличение которых ( введение их в базисные ) увеличит Z. Таким образом, мы достигли оптимума.

В примере мы рассматривали вариант поиска максимума. Если бы искался минимум, то в строке Z искались бы максимальные положительные коэффициенты.

2.6.4. Искусственное начальное решение.

В рассмотренном примере П. О.П. получился очень просто – в качестве базисных были выбраны остаточные (£) переменные, а переменные

исходной задачи были объявлены свободными и приравнены к нулю.

В случае, если исходные ограничения содержат знаки (³) или (=), могут возникнуть сложности в расчетах.

Пример: Z = 4X1 + X2 ®min

3X1 + X2 = 3

4X1 + 3X2 ³ 6

X1 + 2X2 £ 4

X1 , X2 ³ 0

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

Z = 4X1 + X2 ®min

3X1 + X2 = 3

4X1 + 3X2 – Õ3 = 6

X1 + 2X2 +Х4 = 4

X1 , X2, Х3, Х4 ³ 0

Мы получили задачу с n=4 переменными и m=3 уравнениями ограничений ; n–m переменных должно быть выбрано свободными и приравненными нулю; приравняем нулю Х1.

Тогда из 1 уравнения Х2 = 3

из 2 Х3 = ( 9 – 6 ) = 3

из 3 Х4 = 4 – 2 * 3 = –2

Т. к. Х4 < 0, то мы получили промежуточное решение.

Конечно, для выбора свободных переменных можно применить метод проб и ошибок, однако на практике применяются другие, более эффективные методы:

а) М – метод ( метод больших штрафов )

В соответствии с М–методом, в каждое уравнение, не содержащее остаточных переменных (т. е. в уравнения типа(=) и типа (³)), добавляются искусственные переменные R,

например П. О.П.

3X1 + X2 + R1 = 3 X1, X2, Х3 =0

4X1 + 3X2 – Х3 + R2 = 6 Х4 = 4, R1 = 3, R2 = 6;

X1 + 2X2 +Х4 = 4

X1, X2, Х3, Х4, R1, R2 ³ 0

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

Z = 4X1 + X2 + MR1 + MR2 ®min

При поиске максимума М< 0, минимума М > 0; М – штраф, который “накладывается” за использование ненулевых значений R1 и R2 (отсюда название метода ). Штраф “заставит”

метод оптимизации превратить R1 и R2 в нули. При подстановке в симплекс-таблицу обязательно делается подстановка; в целевую функцию вместо R1 и R2 ставят R1 = 3 – 3X1 – X2, R2 = 6 – 4X1 – 3X2 + Х3 и приводят подобные члены.

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

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

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

1-й этап.

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

2-й этап.

Оптимальное решение, полученное на 1-м этапе, используют как П. О.П.

Пример

1-й этап

r = R1 +R2 = 3–3X1–X2 +6 –4X1 – 3X2 + Х3 = – 7X1 – 4X2 + Х3 + 9 min

3X1 + X2 + R1 = 3 X1, X2, Õ3, Õ4, R1, R2 ³ 0

4X1 + 3X2 – Õ3 + R2 = 6

X1 + 2X2 +Х4 = 4

Получаем начальную симплекс-таблицу:

Базисные переменные	X1	X2	Õ3	R1	R2	Õ4	Решение
r	7	4	-1	0	0	0	9
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
Õ4	1	2	0	0	0	1	4

Базисные переменные	X1	X2	Õ3	R1	R2	Õ4	Решение
r	0	5/3	-1	-7/3	0	0	2
X1	1	1/3	0	1/3	0	0	1
R2	0	5/3	-1	-4/3	1	0	2
Õ4	0	5/3	0	-1/3	0	1	3

Базисные переменные	X1	X2	Õ3	R1	R2	Õ4	Решение
r	0	0	0	-1	-1	0	0
X1	1	0	1/5	3/5	-1/5	0	3/5
X2	0	1	-3/5	-4/5	3/5	0	6/5
Õ4	0	0	1	1	-1	1	1

т. к. в r-функции все коэффициенты <0, то процесс завершен.

2-й этап

На первом этапе мы получили преобразованную задачу ЛП:

Z = 4X1 + X2

X1 + 1/5Х3 = 3/5

X2 +3/5Х3 = 6/5

Х3 + Х4 = 1

X1, X2, Х3, Х4 ³ 0 R1 = 3, R2 = 6, поэтому их исключили из решения задачи.

Занесем новые данные в симплекс-таблицу

ЛЕКЦИЯ 6

Продолжение ...

При этом, так же как и в М - методе и на 1-м этапе базисные переменные исключаются из целевой функции методом подстановки :

x1=(3/5) - (1/5)x3 ; x2=(6/5)+(3/5)x3

Z =4*((3/5) - (1/5 )x3) + ((6/5)+(3/5)x3) = -(1/5)x3 + 18/5 ;

Б	x1 x2	x3	x4	решение	i
Z	0 0	1/5	0	18/5
x1 x2	1 0 0 1	1/5 -3/5	0 0	3/5 6/5	3 -2
x4	0 0	1	1	1	1

Z	/5	17/5
x1	/5	2/5
x2	/5	9/5
x3		1	1