Для изготовления цемента двух видов используется сырье трех видов.

Пример 1:

Для изготовления цемента двух видов используется сырье трех видов. Запасы сырья известны и равны соответственно: 264, 136 и 266 тонн. Количество сырья каждого вида, необходимое для производства единицы цемента первого вида соответственно равны: 12, 4 и 3 тонны. Для цемента второго вида: 3, 5 и 14 тонн. Прибыль от реализации цемента первого вида составляет 6 условных единиц, от цемента второго вида — 4 условные единицы. Составить план, обеспечивающий наибольшую прибыль производству.

а) записать математическую модель;

б) решить задачу графическим методом;

в) решить задачу симплекс-методом;

г) к исходной задаче записать двойственную и решить её, используя соотношение двойственности и решение исходной.

Решение от преподавателя:

Необходимо найти максимальное значение целевой функции F = 6x₁+4x₂ → max, при системе ограничений:
12x₁+3x₂≤264, (1)
4x₁+5x₂≤136, (2)
3x₁+14x₂≤266, (3)
x₁ ≥ 0, (4)
x₂ ≥ 0, (5)
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).



Рассмотрим целевую функцию задачи F = 6x₁+4x₂ → max. 
Построим прямую, отвечающую значению функции F = 6x₁+4x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (6;4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
12x₁+3x₂=264
4x₁+5x₂=136
Решив систему уравнений, получим: x₁ = 19, x₂ = 12
Откуда найдем максимальное значение целевой функции:
F(X) = 6*19 + 4*12 = 162

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
12x₁+3x₂+x₃ = 264
4x₁+5x₂+x₄ = 136
3x₁+14x₂+x₅ = 266
Решим систему уравнений относительно базисных переменных: x₃, x₄, x₅
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,264,136,266)

Базис	B	x1	x2	x3	x4	x5
x3	264	12	3	1	0	0
x4	136	4	5	0	1	0
x5	266	3	14	0	0	1
F(X0)	0	-6	-4	0	0	0

Переходим к основному алгоритму симплекс-метода.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i1
и из них выберем наименьшее:
min (264 : 12 , 136 : 4 , 266 : 3 ) = 22
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (12) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x3	264	12	3	1	0	0	22
x4	136	4	5	0	1	0	34
x5	266	3	14	0	0	1	88.667
F(X1)	0	-6	-4	0	0	0

Формируем следующую часть симплексной таблицы. Вместо переменной x₃ в план 1 войдет переменная x₁.

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x1	22	1	0.25	0.083	0	0
x4	48	0	4	-0.333	1	0
x5	200	0	13.25	-0.25	0	1
F(X1)	132	0	-2.5	0.5	0	0

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2
и из них выберем наименьшее:
min (22 : 0.25 , 48 : 4 , 200 : 13.25 ) = 12
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x1	22	1	0.25	0.083	0	0	88
x4	48	0	4	-0.333	1	0	12
x5	200	0	13.25	-0.25	0	1	15.094
F(X2)	132	0	-2.5	0.5	0	0

Формируем следующую часть симплексной таблицы. Вместо переменной x₄ в план 2 войдет переменная x₂.
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x1	19	1	0	0.104	-0.063	0
x2	12	0	1	-0.083	0.25	0
x5	41	0	0	0.854	-3.313	1
F(X2)	162	0	0	0.292	0.625	0

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5
x1	19	1	0	0.104	-0.063	0
x2	12	0	1	-0.083	0.25	0
x5	41	0	0	0.854	-3.313	1
F(X3)	162	0	0	0.292	0.625	0

Оптимальный план можно записать так:
x₁ = 19, x₂ = 12
F(X) = 6*19 + 4*12 = 162

Исходная задача I		Двойственная задача II
x1 ≥ 0	↔	12y1+4y2+3y3≥6
x2 ≥ 0	↔	3y1+5y2+14y3≥4
6x1+4x2 → max	↔	264y1+136y2+266y3 → min
12x1+3x2≤264	↔	y1 ≥ 0
4x1+5x2≤136	↔	y2 ≥ 0
3x1+14x2≤266	↔	y3 ≥ 0

 

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
y₁=0.292, y₂=0.625, y₃=0
Это же решение можно получить, применив теоремы двойственности.
Из теоремы двойственности следует, что Y = C*A^-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

A = (A1, A2, A5) =

12 3 0 4 5 0 3 14 1

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

D = A-1 =

0,104 -0,063 0 -0,083 0,25 0 0,854 -3,313 1

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1расположена в столбцах дополнительных переменных.
Тогда Y = C*A^-1 = 

 

(6, 4, 0) x

0,104 -0,063 0 -0,083 0,25 0 0,854 -3,313 1

= (0,292;0,625;0)

Оптимальный план двойственной задачи равен:
y₁ = 0.292, y₂ = 0.625, y₃ = 0
Z(Y) = 264*0.292+136*0.625+266*0 = 162