4. Определение нового опорного плана.

Для перехода к новому опорному плану производится пересчет симплексной таблицы, методом Жордана – Гаусса. Сначала заменим переменные в базисе, т.е. вместо X в базис войдет переменная X , соответствующая направляющему столбцу.

Разделим все элементы направляющей строки r предыдущей симплексной таблицы на разрешающий элемент а и результаты деления занесем в строку r следующей симплексной таблицы, которая соответствует введенной в базис переменной X.В результате этого на месте разрешающего элемента новой симплексной таблицы будем иметь «I», а в остальных клетках столбца «к» накапливаем нули . Это равносильно исключению переменной X из всех строк таблицы (уравнений ), кроме строки r , соответствующей переменной X .

Преобразование остальных строк симплексной таблицы, включая индексную, рассмотрим на примере строки i (i ≠ r) . Для получения новых элементов i-той строки и к-го столбца и взятый с противоположным знаком, умножаем на элементы преобразованной направляющей строки r и складываем с соответствующими элементами i-й строки. Результаты заносим в i-ю строку новой симплексной таблицы. Если коэффициент, а =0 , то i-я строка переносится в следующую симплексную таблицу без изменений.

Полученный новый опорный план снова проверяется на оптимальность. Таким образом, осуществляем переход к этапу 2 симплексного алгоритма и продолжаем процесс до получения оптимального плана.

ЗАМЕЧАНИЯ.

1. При решении задачи линейного программирования на минимум целевой функции признаком оптимальности плана являются отрицательные значения всех коэффициентов индексной сроки симплексной таблицы. Если опорный план не оптимален, то максимальное положительное значение коэффициента индексной строки ∆ > 0 определяет выбор направляющего столбца.

2. Если в направляющем столбце все коэффициенты , ≤ 0, то функция цели L(X) →∞ и задача не имеет решения.

3. Если в столбце Ø симплексной таблицы содержится или несколько одинаковых наимненьших значений, то новый опорный план будет вырожденным ( одна или несколько базисных переменных станут равными нулю).

4. Если в оптимальный план вошла дополнительная переменная X , то это свидетельствует о недоиспользовании ресурса i-го вида в количестве значения этой переменной.

5. Если в индексной строке оптимальной симплексной таблице находится нуль, принадлежащий столбцу свободной переменной, не вошедший в базис, а среди коэффициентов данного столбца имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно ввести в базис, выполнив 3 и 4 этапы алгоритма. результате будет получен второй оптимальный план с другим набором базисных переменных, но с тем же значением функции цели. Согласно основной теореме линейного программирования, любая выпуклая комбинация этих планов также является оптимальным планом задачи.

ПРИМЕР.

Торговое предприятие при продаже трех групп товаров использует три вида ограниченных материально-денежных ресурсов. Нормы затрат ресурсов на реализацию еденицы товарооборота (тыс.руб.) , объем ресурсов и доход от реализации еденицы товарооборота приведены в технологической таблице 2 .Определить оптимальный план реализации товаров, обеспечивающий торговому предприятию максимальную прибыль ( числа условные) .

№ п/п	Виды материально-денежных ресурсов (i =1,3)	Единица измерения	Норма затрат ресурсов на реализацию 1 ед. товарооборота			Объем материально-денежных ресурсов (b )
			1 гр. (a )	2 гр. (a )	3 гр. ( a )
1.	Рабочее время продавцов	Чел.-ч.	2	1	6	240
2.	Площадь торговых залов	м²	3	3	9	540
3.	Площадь складских помещений	- ″-	2	1	2	120
Прибыль от реализации ед.т / о ( c )		Тыс.руб.	14	6	22	max

Запишем математическую модель задачи.

Определить X=( X ,X , X ), который удовлетворяет условиям

2 X + X + 6X ≤240,

3X + 3X +9X ≤540, (2.7)

2X + X +2X ≤120,

X ≥0,X ≥0,X ≥ 0. (2.8)

И доставляет максимальное значение целевой функции

L(X) = 14X + 6X +22X →max (2.9)

Задачу (2.7)+(2.90) решим симплексным методом.

Для получения первого опорного плана систему неравенств (2.7) приведем к системе уравнений.

2X +X + 6X +X =240,

3X + 3X + 9X + X =540, (2.10)

2X + X + 2X + X =120.

В системе уравнений X , X ,X -основные переменные, характерезующие объемы реализации 1, 2, и 3 групп товаров соответственно, X ,X , X – дополнительные переменные, определяющие объемы неиспользуемых ресурсов.

В матрице коэффициентов при переменных системы уравнений (2.10) А = (а )

2 1 6 1 0 0

А = 3 3 9 0 1 0

2 1 2 0 0 1

векторы А , А ,А -линейно не зависимы, так как определитель, составленный из компонент едентичных векторов, отличен от нуля. Соответствующие еденичным векторам переменные X ,X , X являются базисными.

Разрешим систему уравнений (2.10) относительно базисных переменных.

X =240 −(2X +X + 6X ),

X = 540−(3X + 3X +9X), (2.11)

X = 120−(2X + X +2X ).

Функцию цели запишем в виде:

L (X)= 0 − ( − 14 X −6X −22X ). (2.12)

Пологая, что свободные переменные X =X =X =0 , получим первый опорный план:

X º=( 0, 0, 0, 240, 540, 120), L(X º) =0,

В котором базисные переменные X =240, X =540, X = 120/

Первый опорный план заносим в симплексную таблицу ( смотрите таблицу 3.1). Этот план является не оптимальным, так как в индексной строке находятся отрицательные коэффициенты: −14, −6, −22. Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине. Так как |−22 | >{|−14| , |−6|}, то направляющий столбец соответствует переменной X . Тогда на следующей итерации переменная X перейдет из свободных в базисные. Элементы столбца свободных членов симплексной таблицы разделим на соответствующие положительные коэффициенты направляющего столбца:

240

6. =40 ;

Из трех значений столбца Ø выбираем min{40,60,60,}=40.

Строка симплексной таблицы, соответствующая минимальному значению Ø , является направляющей. Она определяет переменную X , которая на следующей итерации выйдет из базиса и станет свободной. На пересечении направляющих столбца и строки находится разрешающий элемент обведен кругом.

Формируем следующую симплексную таблицу 3.2. Вместо переменной X в таблицу 3.2 вошла переменная X . Строка, соответствующая переменной X получена в результате деления всех элементов направляющей строки ( строка переменной X таблицы 3.1 ) на разрешающий элемент 6 .На месте разрешающего элемента в таблице 3.2 получаем «1».В остальных клетках столбца X таблицы 3.2 накапливаем нули методом Жордана - Гаусса.

Рассмотрим преобразование второй строки симплексной таблицы, которая соответствует переменной X . Для получения новых значений элементов данной строки необходимо все элементы преобразованной направляющей строки таблицы 3.2 умножить на число, стоящее на пересечении строки X и столбца X таблицы 3.1. взятое с противоположным знаком, т.е. на ( −9). Результаты умножения сложить с соответствующими элементами строки X таблицы 3.1. и записать в строку X таблицы 3.2.

40 · (−9) +540=180; 1/3 ·(−9) + 3= 0; 1/6 ·(−9)+3 = 3/2;

1·(−9) + 9=0; 1/6 ·(− 9)+ 0= −3/2; 0 ·(−9) +1=1; 0·(−9) +0=0.

Аналогично проводятся расчеты по всем строкам таблицы, включая индексную.

Далее возвращяемся к этапу 2 алгоритма – проверка оптимального опорного плана. Выполняя последовательно все этапы алгоритма, заполняем таблицу 3.

На третей итерации а таблице 3.3 получен оптимальный план, так как все коэффициенты в индексной строке Δ ≥0, j =1,6.

Запишем оптимальный план:

X = ( 30, 0, 30, 0, 180, 0 ), L(X ) = 1080( тыс.руб.) .

Следовательно, для получения максимальной прибыли в размере 1080 тыс.руб. торговому предприятию необходимо продавать товары 1-й группы на 30 тыс.руб. (X =30) и товары 3-й группы на 30 тыс.руб. ( X = ).В оптимальный план вошла дополнительная переменная X =180. Это указывает на то, что ресурсы второго вида ( площади торговых залов ) недоиспользованы на 180 м², остальные ресурсы использованы полностью, так как X =X =0.

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

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

Таблица 3.

Базисные переменные	Свободные члены ( значения баз. переменных)	X	X	X	X	X	X	Ø
←X X X L(X) Таблица 3.1	240 540 120 0	2 3 2 −14	1 3 1 −6	6 9 2 −22↑	1 0 0 0	0 1 0 0	0 0 1 0	40 60 60
X X ←X L(X ) Таблица 3.2	40 180 40 880	1/3 0 4/3 −20/3	1/6 3/2 2/3 −7/3	1 0 0 0	1/6 −3/2 −1/3 11/3	0 1 0 0	0 0 1 0	120 − 30
X X X L(X) Таблица 3.3	30 180 30 1080	0 0 1 0	0 3/2 1/2 1	1 0 0 0	1/4 −3/2 −1/4 2	0 1 0 0	−1/4 0 3/4 5

КОНТРОЛЬНЫЕ ЗАДАНИЯ ( № 70 + 138)

Торговое предприятие при продаже трех групп товаров (j=1,3) использует три вида материально-денежных ресурсов ( i = 1,3) в количестве b едениц. Известны нормы затрат ресурсов на реализацию еденицы товарооборота −C . Требуется определить оптимальный план реализации товаров, обеспечивающий торговому предприятию максимальную прибыль.

Исходные данные по каждому варианту контрольного задания приведены в таблице 4.

Таблица 4.

№ задачи	a	a	a	a	a	a	a	a	a	b	b	b	c	c	c
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
70	1	4	0	0	3	1	2	0	5	36	50	80	12	16	25
71	4	2	7	1	5	7	2	0	3	150	90	75	16	20	49
72	6	5	0	4	0	1	5	3	3	120	32	70	16	12	10
73	2	4	1	0	3	4	8	1	2	100	120	50	14	13	20
74	3	4	1	1	6	2	0	2	1	104	172	64	10	30	11
75	7	0	2	0	1	2	2	4	1	50	49	56	10	33	17
76	5	2	6	0	3	1	7	1	2	186	92	68	25	12	32
77	3	6	5	3	4	3	2	7	0	165	95	35	15	34	15
78	5	4	3	4	7	0	1	2	1	124	133	64	18	34	21
79	7	1	2	0	3	4	4	5	0	100	68	32	24	12	20
80	3	4	1	3	0	2	1	2	4	72	30	78	12	14	16
81	3	5	2	1	2	3	4	2	0	60	42	48	17	14	15
82	2	7	3	2	2	3	1	2	5	110	70	70	11	10	27
83	6	2	1	2	4	4	8	1	2	100	64	106	26	22	20
84	5	4	3	3	0	1	1	4	5	100	23	124	33	40	38

85	7	1	2	0	3	4	4	5	0	100	68	32	24	12	20
86	1	3	2	0	2	5	2	1	0	60	100	36	14	15	25
87	1	2	4	5	0	2	3	4	1	112	40	90	15	6	20
88	2	5	1	6	1	0	0	2	3	100	88	20	18	13	9
89	1	0	4	0	3	1	3	2	2	60	85	74	16	12	24
90	3	6	4	4	2	4	2	3	1	200	100	80	8	5	5
91	2	1	3	1	2	1	6	4	2	600	500	900	2	2	3
92	1	2	3	2	1	2	4	6	2	900	400	200	6	5	5
93	2	4	2	4	2	6	4	2	1	50	100	200	2	2	3
94	2	1	6	1	1	3	2	1	2	360	600	200	10	4	14
95	10	3	3	4	3	3	2	1	2	100	140	120	8	6	4
96	2	2	2	2	1	3	6	4	6	300	500	750	6	5	7
97	2	1	2	2	3	6	2	3	4	240	200	160	5	6	5
98	2	5	4	3	1	0	0	1	2	112	60	40	10	20	26
99	3	5	9	0	3	2	4	1	1	127	64	56	30	16	15
100	10	10	3	4	3	2	3	4	3	180	120	220	7	8	6
101	6	3	2	2	1	2	3	3	1	600	300	200	3	4	3
102	2	1	2	3	2	1	3	3	2	480	470	520	6	7	6

103	3	0	2	2	2	3	0	4	3	42	52	60	14	22	18
104	2	3	4	0	1	2	3	0	1	104	50	20	20	21	33
105	5	6	3	3	3	2	5	3	4	620	300	900	6	5	5
106	2	3	1	2	1	2	3	6	4	60	80	110	6	6	5
107	1	3	5	0	4	4	5	0	3	32	32	35	30	36	33
108	2	4	0	0	4	5	4	2	1	20	40	60	4	4	5
109	3	2	1	2	1	3	1	1	1	300	400	280	5	3	4
110	4	2	8	2	4	3	6	8	0	1200	1600	2400	3	4	3
111	2	4	4	2	6	4	4	10	12	600	500	360	4	4	5
112	2	3	6	7	3	7	3	1	1	90	210	180	3	3	2
113	10	5	5	7	1	2	7	2	3	300	140	210	5	4	3
114	5	2	1	3	2	3	4	4	2	800	500	400	7	8	7
115	6	3	4	4	1	2	3	9	3	600	500	800	5	4	2
116	2	6	4	5	3	0	0	5	6	40	35	36	20	22	30
117	4	3	2	3	3	3	3	2	4	32	30	42	6	4	5
118	2	0	4	3	5	1	5	6	0	48	60	48	25	30	24
119	3	0	4	1	5	0	0	1	1	30	77	12	18	15	15
120	6	0	1	6	1	2	9	4	4	280	310	200	10	9	8

121	7	0	8	4	2	2	0	6	6	56	54	54	28	18	20
122	2	1	3	4	2	0	4	0	1	70	30	16	10	12	8
123	0	3	5	2	0	4	1	1	2	54	26	36	12	21	20
124	3	6	0	3	1	1	0	4	3	42	61	51	27	25	21
125	4	3	0	3	1	1	5	0	2	12	20	10	10	15	8
126	3	0	3	2	1	2	5	4	0	42	50	72	29	28	30
127	2	3	1	0	2	4	3	1	0	80	80	100	12	13	26
128	1	0	4	0	1	2	3	5	0	68	60	60	20	35	12
129	1	4	3	2	1	0	0	7	6	60	32	78	14	14	18
130	1	3	2	0	4	2	3	6	0	80	60	45	24	20	18
131	1	1	3	4	2	0	4	0	1	65	30	16	8	12	8
132	3	6	0	3	0	1	0	4	3	42	75	41	27	20	11
133	3	0	3	1	1	2	5	4	0	42	52	72	26	28	30
134	5	3	0	1	5	3	4	1	2	35	35	50	10	11	12
135	8	0	4	2	1	4	4	5	0	40	52	40	10	15	24
136	6	6	0	1	1	4	5	0	5	36	42	35	35	36	35
137	0	1	2	5	3	1	6	5	0	24	54	48	24	1430
138	1	0	5	0	5	5	6	8	0	78	60	60	18	17	15