2. Симплекс метод

2.1 Решение задач на составление смеси решение типовых задач

Имеются продукты А, В, С, 1 г каждого из которых содержит следующее количество микроэлементов М и N:

Продукты	Содержание микроэлементов, мг
	M	N
A B C	10 30 30	20 10 20

Стоимость 1 г продукта А составляет 14 у. е., продукта В – 15 у. е., продукта С – 18 у. е. Составьте смесь продуктов А, В и С, содержащую не менее 200 мг. Микроэлемента М и 300 мг. Микроэлемента N при условии минимальных затрат на приобретение ее составляющих.

Решение. Обозначим через x₁ количество продукта А в составляемой смеси, через x₂ – количество продукта В, через x₃ – количество продукта С. Тогда стоимость смеси

f=14x₁+15x₂+18x₃ min

а ограничения запишем в виде

Имеем задачу на отыскание минимума. Преобразуем ее к виду, при котором требуется найти максимум целевой функции. Для этого рассмотрим функцию

f^*=-f=-14x₁-15x₂-18x₃.

Естественно, что при имеем . Для того чтобы в ограничениях можно было использовать знак « », умножим два первых неравенства системы на -1. в результате получим:

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

Для применения симплекс-метода строим первую симплекс-таблицу (табл.2.1).

Таблица 2.1

Базис	св	аi0	-14	-15	-18	0	0
			x1	x2	x3	x4	x5
x4 x5	0 0	-200 -300	-10 -20	-30 -10	-30 -20	1 0	0 1
Индексная cтрока		0	14	15	18	0	0

Как видно из таблицы, в индексной строке нет отрицательных элементов, однако они имеются в столбце свободных членов а_10. Для решения таких задач используются двойственный симплекс-метод. В этом случае в качестве разрешающей строки выбирают строку с наибольшим по модулю отрицательным свободным членом (в нашем примере строку x₅).

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

min(14/20, 15/10, 18/20)=min(7/10, 15/10, 9/10)=0,7

Следовательно, разрешающим будет столбец x₁. Определим также разрешающий элемент. Он находится на пересечении выбранных нами строки x₅ и столбца x₁ и равен -20.

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

Таблица 2.2

Базис	св	аi0	-14	-15	-18	0	0
			x1	x2	x3	x4	x5
x4 x1	0 -14	-50 15	0 1	-20 -25 1/2	1	1 0	-1/2 -1/20
Индексная cтрока		-210	0	8	4	0	14/20

В табл. 2.2 в столбце а_i0 имеется отрицательный элемент, следовательно, полученный план не является оптимальным. Для его дальнейшего улучшения находим разрешающий элемент в строке с отрицательным свободным членом (в строке x₄).

мin(8/25, 4/20, (14/20)/(1/2))=min(32/100, 20/100, 140/100)=0.2

Таким образом, разрешающий элемент равен -20. вновь преобразуя симплекс-таблицу по описанным выше правилам, получим табл. 2.3

Таблица 2.3

Базис	св	аi0	-14	-15	-18	0	0
			x1	x2	x3	x4	x5
x3 x1	-18 -14	2,5 12,5	0 1	5/4 -3/4	1 0	-1/20 1/20	1/40 -3/40
Индексная cтрока		-220	0	3	0	4/20	12/20

Так как все а_i0 >0, найденное решение x₁=12,5, x₂=0, x₃=2,5, x₄=0, x₅=0 является оптимальным. Значение целевой функции

(у.е).