Фирма производит два вида продуктов K1 и K2. Для изготовления продуктов применяются машины A,B,C,D. Время необходимое для изготовления продуктов K1 и K2 на равных машинах, допустимое время использования машин, а также прибыль от продажи продуктов приведены в таблице:
Машины Допустимое время (в часах) Необходимое время (вчасах)
А 16 0 1
B 19 4 1
C 17 2 1
D 22 6 1
Прибыль от продажи продуктов, тыс. руб,.
22 16
а) Какое количество каждого продукта необходимо произвести, чтобы прибыль была максимальной? Решить задачу геометрическим способом.
б) Решить задачу симплекс методом.
в) Для задачи написать двойственную задачу линейного программирования.
Математическая модель имеет вид:
Fx=22×1+16×2→max
x2≤16 (L1)4×1+x2≤19(L2)2×1+x2≤17(L3)6×1+x2≤22(L4)x1,x2≥0x1,x2 ϵ ZРешим задачу графическим методом:
Приведем задачу к канонической форме:
x2≤16 (L1) 2) 4×1+x2≤19(L2)
x2=16 4×1+x2=19
x1
0
x2
16
x1
4.75 0
x2
0 19
x1194+x219=1
3)2×1+x2≤17L3 4) 6×1+x2≤22(L4)
2×1+x2=17 6×1+x2=22
x1172+x217=1 x1226+x222=1
x1
3.66(6) 0
x2
0 22
x1
8.5 0
x2
0 17
Вектор-градиент: GradF(x) = (22;16)
Построим график и отметим на нем область ограничений и вектор градиент.
Область решений – пятиугольник ABCDEF.
т. Max – является т. С. Найдем координаты т. С.
В т. С пересекаются прямые ( L1) и ( L3)
x2=162×1+x2=17; x1=12×2=16 ; C (12;16)
Максимальное значение целефой функции:
Fmaxx=22*12+16*16=267,
Т.к. значения не целочисленные, опустим прямую до целого значения.
Т.е. – это точка D с координатами (1,15).
Fmaxx=22*1+16*15=262.
Решение:
необходимо произвести 1 единицу продукта первого вида и 15 единиц продукта второго вида. При этом максимальная прибыль будет составлять 262 ден. ед.
Решение задачи симплекс-методом
Fx=22×1+16×2→max
x2≤16 4×1+x2≤192×1+x2≤176×1+x2≤22×1,x2≥0x1,x2 ϵ Z
Перейдем к канонической форме:
Fx=22×1+16×2→max
x2+x3=16 4×1+x2+x4=192×1+x2+x5=176×1+x2+x6=22×1-6≥0x1-6 ϵ Z
Составим симплекс-таблицу
Базис x1
x2
x3
x4
x5
x6
Своб. премен. ϴ
x3
0 1 1 0 0 0 16 ∞
x4
4 1 0 1 0 0 19 19/4
x5
2 1 0 0 1 0 17 17/2
x6
6 1 0 0 0 1 22 22/6
F(x0) -22 -16 0 0 0 0 0
Составлена первоначальная симплекс-таблица. F(x0) =0, X 0=0,0,16,19,17,22. План не оптимален, т.к в строке F(x0) присутствуют отрицательные значения. Улучшим план.
Базис x1
x2
x3
x4
x5
x6
Своб. премен. ϴ
x3
0 1 1 0 0 0 16 16
x4
0 1/3 0 1 0 -2/3 13/3 13
x5
0 2/3 0 0 1 -1/3 29/3 29/2
x1
1 1/6 0 0 0 1/6 11/3 22
F(x1) 0 -37/3 0 0 0 11/3 242/3
F(x1) = 2423, X 1=113,0,16,133,293,0. План не оптимален, т.к в строке F(x1) присутствуют отрицательные значения. Улучшим план.
Базис x1
x2
x3
x4
x5
x6
Своб. премен. ϴ
x3
0 0 1 -3 0 2 3 3/2
x2
0 1 0 3 0 -2 13 -13/2
x5
0 0 0 -2 1 1 1 1
x1
1 0 0 -1/2 0 1/2 3/2 3
F(x2) 0 0 0 37 0 -21 241
F(x2) = 241, X 2=32,13,3,0,1,0. План не оптимален, т. к в строке F(x2) присутствуют отрицательные значения. Улучшим план.
Базис x1
x2
x3
x4
x5
x6
Своб. премен. ϴ
x3
0 0 1 1 -2 0 1 1
x2
0 1 0 -1 2 0 15 -15
x6
0 0 0 -2 1 1 1 -1/2
x1
1 0 0 1/2 -1/2 0 1 2
F(x3) 0 0 0 -5 21 0 262
F(x3) = 262, X 3=1,15,1,0,0,1. План не оптимален, т.к в строке F(x3) присутствуютотрицательные значения. Улучшим план.
Базис x1
x2
x3
x4
x5
x6
Своб. премен.
x4
0 0 1 1 -2 0 1
x2
0 1 1 0 0 0 16
x6
0 0 2 0 -3 1 3
x1
1 0 -1/2 0 1/2 0 1/2
F(x4) 0 0 5 0 11 0 267
F(x4) = 262, X 4=12,16,0,1,0,3. План оптимален.
Оптимальный план:
x1=12, x2=16
Fmaxx=22*12+16*16=267
Т.к x1 – не целочисленное значение, то воспользуемся методом Гомори.
Составляем дополнительное ограничение: q4 – q41*x1 – q42*x2 – q43*x3 – q44*x4 – q45*x5 – q46*x6 ≤0q4 = b4 – [b4] = 1/2 – 0 = 1/2q41 = a41 – [a41] = 1 – 1 = 0a42 = a42 – [a42] = 0 – 0 = 0a43 = a43 – [a43] = -1/2 + 1 = 1/2a44 = a44 – [a44] = 0 – 0 = 0a45 = a45 – [a45] = 1/2 – 0 = 1/2a46 = a46 – [a46] = 0 – 0 = 0.
Дополнительное ограничение имеет вид:12 – 12×3- 1 2×5 ≤ 0
Преобразуем полученное неравенство в уравнение:12 – 12×3- 1 2×5 + x7 = 0
Составим симплекс-таблицу:
Базис x1
x2
x3
x4
x5
x6
x7
Своб. премен.
x4 0 0 1 1 -2 0 0 1
x2 0 1 1 0 0 0 0 16
x6 0 0 2 0 -3 1 0 3
x1 1 0 -1/2 0 1/2 0 0 1/2
x7 0 0 -1/2 0 -1/2 0 1 -1/2
F(X0) 0 0 -5 0 -11 0 0 -267
ϴ – – 10 – 22 0 0
Составлена первоначальная симплекс-таблица. F(x0) =0, X 0=12,16,0,1,0,-12. План не оптимален, т.к в строке F(x0) присутствуют отрицательные значения. Улучшим план.
Базис x1
x2
x3
x4
x5
x6
x7
Своб. премен.
x4 0 0 0 1 -3 0 2 0
x2 0 1 0 0 -1 0 2 15
x6 0 0 0 0 -5 1 4 1
x1 1 0 0 0 1 0 -1 1
x3 0 0 1 0 1 0 -2 1
F(X1) 0 0 0 0 -6 0 -10 -262
F(x1) =-262, X 1=1,15,1,0,0,1. План оптимален.
F(x) = -F(X).
Оптимальный план:
x1=1, x2=15
Fmaxx=22*1+16*15=262
Двойственная задача
Zy=16y1+19y2+17y3+22y4→min
4y2+2y3+6y4≥22y1+y2+y3+y4≥16y1-4≥0
2082165301625По результатам симплекс-таблицы можем найти решение двойственной задачи:
Базис x1
x2
x3
x4
x5
x6
Своб. премен.
x4
0 0 1 1 -2 0 1
x2
0 1 1 0 0 0 16
x6
0 0 2 0 -3 1 3
x1
1 0 -1/2 0 1/2 0 1/2
F(x4) 0 0 5 0 11 0 267
-11811083185Y5 Y6Y1 Y2 Y3 Y4
Составим таблицу соответствия основных и вспомогательных переменных оптимальных планов взаимно двойственных задач и применим 2-ю теорему двойственности.
вспомогательные основные
Yопт. Y5 = 0 Y6 = 0 Y1=5 Y2 = 0 Y3 = 11 Y4 = 0
Xопт. X1 = 1/2 X2 = 16 X3 =0 X4=1 X5 = 0 X6 = 3
основные вспомогательные
Y5,0,11,0,0,0 ; Zmin(Y) = 16*5 + 19*0 + 17*11 + 22*0 = 267
Между переменной и двойственной задачей существует связь:
x1 x2 x3 x4 x5 x6
10534653873500615315666750014630404762500197739038100002472690381000029584653810000
y5 y6 y1 y2 y3 y4
Следовательно, Y min5,0,11,0,0,0; Zmin(Y) =267
Xmax12,16,0,1,0,3; Zmax(Y)=267.
