Методы оптимальных решений (стр. 5 )

то в качестве ключевого элемента мы выбрали число 2. Это означает, что неизвестное х выводится из базиса. Разделив все элементы первой строки табл.1 на ключевой элемент 2, мы заполнили, и выделили ключевую строку в табл.2. Остальные элементы табл.2 (элементы второй строки и индексной строки) были подсчитаны по правилу двух перпендикуляров.

Вторая строка 12-4 × 2 =4; 4-4 × 1=0; 0 - 4× ½ = -2; 1-4 × 0=1; 4-4 × ½ =2.

Индексная строка

-23-(-12) × 2= 1; -12-(-12) × 1= 0; 0-(-12)× ½ = 6; 0-(-12) × 0= 0; -8-(-12) × ½ = -2 .

Индексную строку табл. 2, так же как и индексную строку табл.1, можно было бы подсчитать и по правилу цен, а именно:

4 × 2+(-3) × 4+5 =1; 4 × 1 + (-3) × 0 - 4 = 0; 4 × ½ + (-3) × (-2)-2 = 6

4× 0 +(-3) × 1 -(-3) = 0; 4 × ½ + (-3) × 2 - (-2) = -2

	A1	A2	A3	A4	A5	A6
A1	-	35	41	38	19	40
A2	51	-	43	27	24	31
A3	63	100	-	58	89	50
A4	32	27	44	-	71	33
A5	51	60	73	80	-	49
A6	49	38	505	44	50	-

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

В табл. 2 содержится базисный план Х2 = (2,0,4,0), для которого ¦(Х2) = 1. Так как в индексной строке табл. 2 есть отрицательный элемент -2, над которым имеются положительные элементы, то план еще раз можно улучшить, построив табл.3. В индексной строке табл. 3 нет отрицательных элементов, следовательно, план Х3*= (1,0,0,2) является оптимальным планом задачи (7) - (9)‚ а ¦(Х3*) = 5 есть максимальное значение целевой функции (9).

Пример 2. Решить симплекс-методом следующую задачу ЛП:

2х1 - 2х2 -х3 = -2,

-х1 + 3х2 -2х3 = 11, (10)

xj ³ 0 (j=1,2,3), (11)

¦(Х) = 2х1 - 3х2 + 4х3 ¾ max (12)

Задача (— основная, но не каноническая, так как система

уравнений (10) не является канонической (свободный член первого уравнения отрицателен и ни в одном из уравнений нет базисного неизвестного). Применим метод искусственного базиса. С этой целью составим вспомогательную задачу, так чтобы система уравнений оказалась канонической.

Умножив обе части первого уравнения на -1 и прибавив к левым частям обоих уравнений искусственные неизвестные z1 и z2, получим так называемую расширенную систему. Составим вспомогательную функцию, равную сумме искусственных не известных, и поставим своей целью минимизировать вспомогательную функцию на множестве планов расширенной системы.

Первый этап. Вспомогательная задача

-2x1 + 2x2 + x3 + z1 = 2 ,

-x1 + 3x2 - 2x3 + z2 = 11, (13)

xj ³ (j = 1,2,3), zi ³ 0 (i = 1,2) (14)

j(X) = z1 + z2 ¾ min. (15)

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

			0	0	0	0	1	1
		Баз.	x0	x1	x2	x3	z1	z2
	1	z1	2	-2	2	1	1	0	Табл. 1 q = min (2/2, 11/3) = 2/2
	1	z2	11	-1	3	-2	0	1
		j	13	-3	5	-1	0	0
®	0	x2	1	-1	1	1/2	1/2	0	Табл. 2 q= 8/2
	1	z2	8	2	0	-7/2	-3/2	1
		j	8	2	0	-7/2	-3/2	0
	0	x2	5	0	1	-5/4	-1/4	1/2	Табл. 3
®	0	x1	4	1	0	-7/4	-3/4	1/2
		j	0	0	0	0	-1	-1

Все элементы индексной строки табл.3 не положительные, следовательно, вспомогательная задача решена и получен ее оптимальный план, причем минимальное значение вспомогательной функции jmin = 0. отсюда следует, что существует каноническая система, равносильная исходной системе (10), которая содержится в завершающей симплексной таблице вспомогательной задачи (Выписав ее из табл.3 и присоединив к ней заданную целевую функцию (12), получим задачу, равносильную исходной основной задаче (, которая, как и вспомогательная задача, будет “почти канонической”.