1. Фирма производит два вида продуктов K1 и K2. Для изготовления продуктов применяются машины A,B,C,D. Время необходимое для изготовления продуктов K1 и K2 на равных машинах, допустимое время использования машин, а также прибыль от продажи продуктов приведены в таблице:
Машины Допустимое время (в часах) Необходимое время (в часах)
К1
К2
А 7 0 1
B 10 4 1
C 8 2 1
D 13 6 1
Прибыль от продажи продуктов, тыс. руб. 13 7
а) Какое количество каждого продукта необходимо произвести, чтобы прибыль была максимальной? Решить задачу геометрическим способом.
б) Решить задачу симплекс методом.
в) Для задачи написать двойственную задачу линейного программирования.
Решение:
Пусть х1 – кол-во продуктов К1, х2 – кол-во продуктов К2.
Целевая функция – прибыль с продаж:
F=13×1+7×2 → max
2540143280216Ограничения:
0x1+x2 ≤ 7
4×1+x2 ≤ 10
2×1+x2 ≤ 8
6×1+x2 ≤ 13
x1≥0, x2 ≥0.
а) Графический метод.
Строим область допустимых решений:
Строим градиент и линию уровня целевой функции:
13245251142070А
00А
81624046294512151951420689
Точка максимума – точка А:
2654146175400×1+x2 = 7
2×1+x2 = 8
Откуда:
x1 = 1/2; x2 = 7
Fmax=13*1/2+7*7 =55,5
Необходимо производить 0,5 ед. продукта К1 и 7 ед. продукта К2. Тогда суммарная прибыль будет максимальной и составит 55,5 тыс. руб.
б) Симплекс методом
23974652389950Канонический вид ограничений:
x2+x3 = 7
4×1+x2+x4 = 10
2×1+x2+x5 = 8
6×1+x2+x6 = 13
Симплекс-таблица:
Базис B x1 x2 x3 x4 x5 x6 bi/aij
x3 7 0 1 1 0 0 0 –
x4 10 4 1 0 1 0 0 2,5
x5 8 2 1 0 0 1 0 4
x6 13 6 1 0 0 0 1 2,167
F(X1) 0 -13 -7 0 0 0 0
x3 7 0 1 1 0 0 0 7
x4 1,333 0 0,33 0 1 0 -0,667 4
x5 3,667 0 0,67 0 0 1 -0,333 5,5
x1 2,167 1 0,17 0 0 0 0,167 13
F(X2) 28,167 0 -4,83 0 0 0 2,167
x3 3 0 0 1 -3 0 2 1,5
x2 4 0 1 0 3 0 -2 –
x5 1 0 0 0 -2 1 1 1
x1 1,5 1 0 0 -0,5 0 0,5 3
F(X3) 47,5 0 0 0 14,5 0 -7,5
x3 1 0 0 1 1 -2 0 1
x2 6 0 1 0 -1 2 0 –
x6 1 0 0 0 -2 1 1 –
x1 1 1 0 0 0,5 -0,5 0 2
F(X4) 55 0 0 0 -0,5 7,5 0
x4 1 0 0 1 1 -2 0
x2 7 0 1 1 0 0 0
x6 3 0 0 2 0 -3 1
x1 0,5 1 0 -0,5 0 0,5 0
F(X5) 55,5 0 0 0,5 0 6,5 0
Оптимальный план можно записать так:
x1 = 0.5, x2 = 7
Fmax = 13*0.5 + 7*7 = 55.5
в) Двойственная задача линейного программирования.
2077720294005Z=7y1+10y2+8y3+13y4 → min
4y2+2y3+6y4≥13
y1+y2+y3+y4≥7
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0
где y1, y2, y3, y4 – удельные (теневые) цены ресурсов – времени работы машин А, В, С, D соответственно.
2. Практическое
