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

Задача

Предприятие планирует выпускать четыре вида продукции. Объемы ресурсов трех видов (в расчете на трудовую неделю), затраты каждого ресурса на изготовление единицы продукции и цена единицы продукции приведены в таблице. Найти, сколько продукции и какого вида необходимо производить, чтобы общая выручка от реализации всей выпущенной продукции была бы наибольшей. Построить модель прямой и двойственной задач. Найти оптимальные планы для обеих задач и экстремальные значения целевых функций. Дать экономическую интерпретацию основным и дополнительным переменным исходной и двойственной задач. Проанализировать рациональность расширения ассортимента продукции за счет включения новой продукции (П5).

	П1	П2	П3	П4	Объем	П5
Р1	8	10	8	10	3600	9
Р2	4	7	4	6	1850	5
Р3	4	3	3	5	1500	3
Цена	25	30	40	35		33

Решение.
Обозначим через x₁..x₄ число изготавливаемых продуктов. Тогда условие задачи может быть записано в следующем виде:

25x₁ + 30x₂ + 40x₃ + 35x₄ → max
8x₁ + 10x₂ + 8x₃ + 10x₄ ≤ 3600
4x₁ + 7x₂ + 4x₃ + 6x₄ ≤ 1850
4x₁ + 3x₂ + 3x₃ + 5x₄ ≤ 1500
x₁ ≥ 0
x₂ ≥ 0
x₃ ≥ 0
x₄ ≥ 0

Припишем каждому из видов сырья, используемых для производства продукции, двойственную оценку, соответственно равную y₁, y₂ и у₃. Тогда общая оценка сырья, используемого на производство продукции, составит

3600y₁ + 1850y₂+ 1500y₃ → min

Согласно условию, двойственные оценки должны быть такими, чтобы общая оценка сырья, используемого на производство единицы продукции каждого вида, была не меньше цены единицы продукции данного вида, т. е. y₁, y₂ и у₃ должны удовлетворять следующей системе неравенств:
8y₁ + 4y₂+ 4y₃ ≥ 25
10y₁ + 7y₂+ 3y₃ ≥ 30
8y₁ + 4y₂+ 3y₃ ≥ 40
10y₁ + 6y₂+ 5y₃ ≥ 35
y₁ ≥ 0
y₂ ≥ 0
y₃ ≥ 0

Как видно, данные задачи образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий, а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой–либо одной из них.

Приведем математическую модель задачи к каноническому виду.Для этого избавимся от знаков неравенств посредством ввода дополнительных переменных и замены знака неравенства на знак равенства. Дополнительная переменная добавляется для каждого неравенства, причем эта переменная указывается в целевой функции с нулевым коэффициентом. Правило ввода дополнительных переменных: при ">=" - переменная вводится в неравенство с коэффициентом (-1); при "<=" - с коэффициентом (+1).

25x₁ + 30x₂ + 40x₃ + 35x₄ - 0x₅ - 0x₆ - 0x₇ → max
8x₁ + 10x₂ + 8x₃ + 10x₄ + x₅ = 3600
4x₁ + 7x₂ + 4x₃ + 6x₄ + x₆ = 1850
4x₁ + 3x₂ + 3x₃ + 5x₄ + x₇ = 1500

Экономический смысл введенных дополнительных переменных - остатки соответствующих ресурсов каждого вида. Для решения задачи составим симплекс-таблицу.
Симплекс-таблица составляется так:
         В графе "Базис" записываются вектора переменных, принимаемые за базисные. На первом этапе это – A₅, A₆, A₇. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.
         В следующий столбец  записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов Аi при  i –й переменной. 

				25	30	40	35	0	0	0
i	Базис	C	B	A1	A2	A3	A4	A5	A6	A7
1	A5	0	3600	8	10	8	10	1	0	0
2	A6	0	1850	4	7	4	6	0	1	0
3	A7	0	1500	4	3	3	5	0	0	1
4	Fi-Ci		0	-25	-30	-40	-35	0	0	0