Предприятие выпускает два вида продукции A1 и A2, используя при этом три вида сырья S1, S2 и S3. Известны запасы сырья равные b1, b2 и b3 соответственно. Расход сырья вида Si на производство единицы продукции Aj равен ai,j. Доход от реализации единицы продукции Aj составляет cj, при котором доход будет максимальным. Решить задачу графическим методом; составить каноническую модель данной задачи и решить ее симплекс-методом. Найти двойственные оценки цен на сырье, из решения симметричной двойственной задачи.
a=S+3=5+3=8;b=T+4=6+4=10.
Запишем M – матрицу коэффициентов ai,j и B – матрицу запасов сырья bi.
M=2∙b+a2∙a2∙b4∙a2∙b2∙b+3∙a=281620322044;B=40∙a∙b+12∙a256∙a∙b46∙a∙b+20∙b2=396844805680.
Коэффициенты функции цели c1=3b=30 и c2=2b+a=28.
Математическая модель задачи
fx=c1∙x1+c2∙x2→max
M∙x≤B,
x≥0.
Ответ
предприятию для получения максимального дохода в размере 5120 ден. ед. необходимо произвести 96 ед. продукции A1 и 80 ед. продукции A2.
Решение
Пусть x1 – количество продукции A1, ед.; x2 – количество продукции A2, ед. Подставим в математическую модель задачи числовые данные:
fx=30x1+28x2→max
28x1+16x2≤3968,20x1+32x2≤4480,20x1+44x2≤5680,
x1≥0, x2≥0.
Решим задачу графическим методом. С учетом системы ограничений построим множество допустимых решений. Строим в системе координат x1Ox2 прямые:
I:28x1+16x2=3968,
II:20x1+32x2=4480,
III: 20x1+44x2=5680.
Изобразим полуплоскости, определяемые системой ограничений. Находим множество допустимых решений как общую часть полученных полуплоскостей – многоугольник OABCD (обозначена серым). Вектор градиентного направления n=30;28.
Строим линию уровня целевой функции, перпендикулярную вектору градиентного направления и проходящую через начало координат. Перемещаем данную прямую в направлении вектора-градиента. В точке C целевая функция достигает максимума.
Координаты точки C – точки пересечения I и II:
28x1+16x2=3968,20x1+32x2=4480.⟹x1*=96x2*=80.
Целевая функция достигает наибольшего значения при x1*=96; x2*=80. Значение целевой функции
fmax=f96, 80=30∙96+28∙80=5120 ден. ед.
Составим каноническую модель данной задачи.
fx=0--30x1-28x2→max
28x1+16x2+x3=3968,20x1+32x2+x4=4480,20x1+44x2+x5=5680,xj≥0, j=1,5.
Примем дополнительные переменные x3, x4, x5 в качестве основных (базисных) переменных, тогда x1, x2 – свободные переменные, и при x3= x4= x5=0 получим начальное базисное решение x(0)=0, 0, 3968, 4480, 5680
. Составим первую симплекс-таблицу:
симплекс-таблица 1 (нулевое решение):
Базис B
x1
x2
x3
x4
x5
Отношение
x3
3968 28 16 1 0 0 3968/28=992/7
x4
4480 20 32 0 1 0 4480/20=224
x5
5680 20 44 0 0 1 5680/20=284
f(X)
0 -30 -28 0 0 0
В f(X)-строке среди оценок Δj есть отрицательные значения, следовательно, план X0 не является оптимальным (задача на максимум). Столбец x1, соответствующий наибольшему по модулю отрицательному значению (-30), выбираем в качестве ведущего. Для положительных элементов ведущего столбца находим наименьшее из симплексных отношений θ=9927, x3 – ведущая строка. Элемент 28 на пересечении ведущего столбца и ведущей строки – разрешающий элемент. В базис вводим переменную x1, выводим переменную x3. Переходим к следующей симплексной таблице.
симплекс-таблица 2 (первое решение):
Базис B
x1
x2
x3
x4
x5
Отношение
x1
992/7 1 4/7 1/28 0 0 992/7/(4/7)=248
x4
11520/7 0 144/7 -5/7 1 0 1520/7/(144/7)=80
x5
19920/7 0 228/7 -5/7 0 1 19920/7/(228/7)=1660/19
f(X)
29760/7 0 -76/7 15/14 0 0
В f(X)-строке среди оценок Δj есть отрицательное значение, следовательно, план X1 не является оптимальным (задача на максимум). Столбец x2, соответствующий отрицательному значению (-76/7), выбираем в качестве ведущего. Для положительных элементов ведущего столбца находим наименьшее из симплексных отношений θ=80, x4 – ведущая строка
Задать вопрос
на новый заказ в Автор24.
