Пример записи ЗЛП в допустимом каноническом виде:

min F 52x1 35x3		109	;
	3x1 x2 2x3 5		x1 0 x5 0
	x 3x x 9
	x1 1 4x3 3 x45	1

Найдем все опорные решения для следующей ЗЛП:

		F 3x1 5x2 max
x1		2x2	10	xi 0
	3x1	2x2	18

		x1 2x2 x3	10	xi 0
		3x1 2x2 x4 18

		Опорные решения
N		x1 x2	x3	x4	F
1	0	0	10	18	0
2	0	5	0	8	25
3	0	9	-8	0	Недопу-

стимое

4-10 0 0 48 Недопу-

стимое

5	6	0	16	0	18
6	2	6	0	0	36

Cтандартная форма

F c0 ( c1 x1 c2 x2 c3 x3 ) ;

x4 b1 (a11 x1 a12 x2 a13 x3 ) x5 b2 (a21x1 a22 x2 a23 x3 )

	x b (a x a x						a x )
	x6	b3	(a31	x1	a32	x2	a33 x3 )
	7	4	41	1	42	2	43	3

Лекция 17. Алгоритм симплекс-метода.

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

	Своб.	x1	x2 .......	xi
	член
F	11	12		1l
xi+1	21	22		2l
...	...	... ... ...		...
xn	k1	k2		kl

С учетом того, что rp - разрешающий элемент (r, q - строка, p, s - столбец)

	v 1				1
	qs
			rp
	v 1				qsv
	qs
					rp
	v 1				qsv
	qs
					rp

при q=r; s=p, (для разрешающего элемента)

при q=r; s p, (разрешающая строка)

при q r; s=p; (разрешающий столбец)

v 1	v	rsv qpv
qs	qs		для остальных элементов
		rp

Запишем ранее рассмотренную задачу в стандартной форме:

max F 12 ( 3x1 4x2 )

x3 12 (4x1 3x2 ) x4 6 ( 2x1 3x2 )

x5 2 ( x1 2x2 )

	Cв.	X1	X2		Cв.	X1	X5
	чл.				чл.
F	-12	-3	-4	F	-8	-5	2
X3	12	4	3	X3	9	11/2	-3/2
X4	-6	-2	-3	X4	-3	-7/2	3/2
X5	2	-1	2	X2	1	-1/2	1/2

	Cв.	X4	X5
	чл.
F	-26/7	-10/7	-1/7
X3	30/7	11/7	6/7
X1	6/7	-2/7	-3/7
X2	10/7	-1/7	2/7
F=2/11; x1		=18/11;	x2

	Cв.	X3	X5
	чл.
F	2/11	10/11	7/11
X4	30/11	7/11	6/11
X1	18/11	2/11	-3/11
X2	20/11	1/11	4/11
=20/11;	x3	=0;

x4 =30/11;

x5 =0.

Лекция 18 Постановка задачи целочисленного программирования