Решение задачи симплекс-методом.

Для приведения системы к каноническому виду введем балансные неизвестные х₃ , х₄ , х_5.

35x₁+70x₂+х₃ =2450

50x₁+40x₂ + х₄ =2000 (1.5)

80x₁+35x₂ + х₅=2800

10х₁+15х₂ =F

Составим симплекс таблицу:

Таблица 1.

Базисные переменные	Оценки пер-х	Переменные	Свободные члены	Контр. столбец
х1	х2	х3	х4	х5
х3								2450×0=0
х4								2000×0=0
х5								2800×0=0
F							F
х2		1/2		1/70
х4				-4/7
х5		125/2		-1/2
F		5/2		-15/70			F-525
х2				5/210	-1/60
х1				-4/210	1/30
х5				29/42	-25/12
F				-1/6	-1/12		F -575

 

Шаг 1. В столбцы 1-6 и строки 1-4 записываем коэффициенты при неизвестных и свободные члены системы (1.5). В столбце базисных переменных записываем их обозначения. Так как к началу решения оценки базисных переменных неизвестных даем им значения равные нулю. Оценки свободных переменных (количество выпускаемой продукции) принимаются равными их значениям в целевой функции. Решение задачи линейного программирования в симплексной таблице находится в столбце свободных членов, то есть решения на первом шаге выглядит как:

х₁ =x₂=0; x₃=2450; x₄=2000; x₅=2800

Контрольный столбец служит для проверки правильности решения и представляет собой произведения коэффициентов столбца свободных членов на оценки соответствующих переменных. Сумма этих произведений дает значение целевой функции, в данном случае F (x)=0

Ведущий столбец – 2 (т.е максимальное значение целевой функции -15, которое принадлежит 2^му столбцу), ведущая строка – 1 (т.е. при делении коэффициентов в столбце свободных членов на соответствующие коэффициенты ведущего столбца, минимальное значение 35, принадлежащее 1 строке).

Шаг 2. Переход к новому опорному плану осуществляется в результате пересчета симплексной таблицы методом Жордана - Гаусса.

Разделим все элементы ведущей строки предыдущей симплексной таблицы на ведущий элемент и результаты деления занесем в строку следующей симплексной таблицы. В результате этого на месте разрешающего элемента в следующей симплексной таблице запишем 1, а в остальных клетках 2^го столбца, включая клетку столбца целевой функции, записываем нули.

Остальные коэффициенты пересчитываются по методу Жордана – Гаусса, т.е. по правилу прямоугольника следующим образом:

35 70

50=50 - (35×40)/70 = 30

50 40

Шаг 3. Аналогично заполняется таблице на 3 шаге. Получаем, что в этой таблице все коэффициенты в строке целевой функции отрицательные или равные нулю, т.е. полученный план оптимален, т.е. нет ни одной переменной, введение которой в план увеличилось бы значение целевой функции в 575 тыс.руб.

 

 

Решение двойственной задаче.

Составим и найдем решение двойственной задаче к задаче, решенной графическим и симплекс-методом.

Прямая задача:

Найти =(x₁, x₂), чтобы

F(x) =10x₁+15x₂→max, при

35x₁+70x₂≤2450

50x₁+40x₂≤2000

80x₁+35x₂≤2800

Решение прямой задачи:

x₁ =20; x₂=25

F(x) =575 тыс.руб.

Двойственная задача:

Найти =(u₁,u₂,u₃), чтобы

Z (u) = 2450u₁+2000u₂+2800u₃→min

35u₁+50u₂+80u₃≥10

70u₁+40u₂+35u₃≥15

Относительно рассматриваемого варианта задач соответствующие условия “дополняющей нежесткости” первой и второй группы выглядит следующим образом:

U₁↔(2450-35x₁-70x₂)=0;

U₂↔(2000-50x₁-40x₂)=0; (1.6)

U₃↔(2800-80x₁-35x₂)= 0.

X₁↔ (35u₁+50u₂+80u₃-10)=0; (1.7)

X₂↔ (70u₁+40u₂+35u₃-15)=0;

Из группы условий (1.6), так как 2800-80×20-35×25=325>0 следует, что ограничения по материалам не лимитирует оптимальную программу, т.е. u₃=0.

Таким образом, из решения след. системы уравнений следует, что:

35u₁+50u₂=10

70u₁+40u₂=15

u₁=1/6; u₂=1/12

При этом доход составит: 2450×1/6+2000×1/12=575 тыс.руб