Сформулировать двойственную задачу и найти ее оптимальное решение
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Сформулировать двойственную задачу и найти ее оптимальное решение, используя теоремы двойственности.
Вариант 7.
Можно закупить корм видов 1 и 2 , при этом стоимость единиц корма вида 1 равна 2 ден. единицам, а вида 2 – 4 ден. единицы. В каждой единице корма 1 содержится одна единица витамина А две единицы витамина В и нет витамина С, а в каждой единице корма 2 – две единицы А, одна единица В и одна единица С. Животному в сутки необходимо не менее 10 единиц витамина А, 10 единиц витамина В и 4 единицы витамина С. Составить наиболее дешевый рацион питания животного в расчете на сутки.
Нужно полное решение этой работы?
Ответ
Fmin (3,4)=11, φmax(0;1/2;3/2)=11.
Решение
Построим математическую модель задачи.
Пусть х1-количество корма вида 1, ед, х2 - количество корма вида 2, ед запланированных к производству.
x1+2х2≥102x1+х2≥10x2≥4
По смыслу задачи переменные х1 ≥ 0, х2 ≥0.
F = 2х1 +4х 2. →min.
Решим задачу симплекс –методом
Каноническая форма:
x1 + 2 x2 -
s1
=
10
(1)
2 x1 +
x2
-
s2
=
10
(2)
x2
-
s3 =
4
(3)
x1, x2, s1, s2, s3 ≥ 0Введем по одной искусственной неотрицательной переменной ri в каждое уравнение системы ограничений.Получим следующую систему ограничений,
x1 + 2 x2 -
s1
+
r1
=
10
(1)
2 x1 +
x2
-
s2
+
r2
=
10
(2)
x2
-
s3
+
r3 =
4
(3)
x1, x2, s1, s2, s3, r1, r2, r3 ≥ 0с базисными переменными r1,r2,r3.
вспомогательную целевую функцию :
G =
r1 + r2 + r3
и проведем ее минимизацию в заданной системе ограничений
. Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого: - вычтем из функции G уравнение 1 - вычтем из функции G уравнение 2 - вычтем из функции G уравнение 3 Функция G примет вид :
G = - 3 x1 - 4 x2 + s1 + s2 + s3 + 24
Теперь мы можем сформировать начальную симплекс-таблицу.
БП x1 x2 s1 s2 s3 r1 r2 r3 Решение Отношение
r1 1 2 -1 0 0 1 0 0 10 10 / 2 = 5
r2 2 1 0 -1 0 0 1 0 10 10 / 1 = 10
r3 0 1 0 0 -1 0 0 1 4 4 / 1 = 4
F 1 2 0 0 0 0 0 0 0 --
G -3 -4 1 1 1 0 0 0 -24 --
БП x1 x2 s1 s2 s3 r1 r2 Решение Отношение
r1 1 0 -1 0 2 1 0 2 2 / 2 = 1
r2 2 0 0 -1 1 0 1 6 6 / 1 = 6
x2 0 1 0 0 -1 0 0 4 --
F 1 0 0 0 2 0 0 8 --
G -3 0 1 1 -3 0 0 -8 --
БП x1 x2 s1 s2 s3 r2 Решение Отношение
s3 1
2
0 -1
2
0 1 0 1 1 / 1
2
= 2
r2 3
2
0 1
2
-1 0 1 5 5 / 3
2
= 10
3
x2 1
2
1 -1
2
0 0 0 5 5 / 1
2
= 10
F 0 0 1 0 0 0 10 --
G -3
2
0 -1
2
1 0 0 -5 --
БП x1 x2 s1 s2 s3 r2 Решение Отношение
x1 1 0 -1 0 2 0 2 --
r2 0 0 2 -1 -3 1 2 2 / 2 = 1
x2 0 1 0 0 -1 0 4 --
F 0 0 1 0 0 0 10 --
G 0 0 -2 1 3 0 -2 --
БП x1 x2 s1 s2 s3 Решение Отношение
x1 1 0 0 -1
2
1
2
3 --
s1 0 0 1 -1
2
-3
2
1 --
x2 0 1 0 0 -1 4 --
F 0 0 0 1
2
3
2
11 --
G 0 0 0 0 0 0 --
Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к