2018-02-13
330
Рассмотрим следующую задачу:
Фабрике мягких игрушек для изготовления плюшевых медведей и зайцев требуется соответственно: 500 и 300 г плюша, 200 и 100 г меховой обивки. При этом запасы плюша 20 кг, а меха необходимо использовать минимум 10 кг, для избежания истечения срока годности. Медведей продают по 70 руб, а зайцев по 50 руб. Необходимо найти, сколько произвести мягких игрушек каждого типа (x1 и x2). Для достижения максимальной прибыли.
Запишем ограничения:
Ограничение по плюшу:
x1[шт]*500[г]+ x2[шт]*300[г]≤20000[г] (19)
Ограничение по меху:
x1[шт]*200[г]+ x2[шт]*100[г]≥10000[г] (20)
Как видно из рис. 6. в данном случае область пересечения плоскостей отсутствует, а значит и отсутствует область допустимых значений.
Ответ: решений нет
|
10. Метод искусственного базиса
Если в исходной системе ограничений присутствовали знаки = или ≥, то применять симплекс метод нельзя, т.к. все значения переменных по условию должны быть ≥ 0. Но можно добавить еще несколько искусственных переменных и решать задачу через вспомогательную задачу.
Разберем это на примере:
Заводу торгового оборудования для производства прилавков и витрин требуется соответственно: 4 и 6 м2 ДСП, 1 и 3 м2 стекла, 1 и 2 погонных метра трубы, 30 и 40 шт шурупов. На складе имеется 600 м2 ДСП, 200 м2 стекла. При этом необходимо использовать для производства не менее 150 погонных метров трубы и не менее 2000 шурупов. Стоимость прилавка 2000 руб. витрины- 4000 руб. Необходимо найти, сколько произвести продукции каждого типа (x1 и x2). Для достижения максимальной прибыли.
Тогда ограничение по ДСП ([м2]) запишется так:
x1[шт]*4[м2]+ x2[шт]*6[м2]≤600[м2] (21)
Ограничение по стеклу ([м2]) запишется так:
x1[шт]*1[м2]+ x2[шт]*3[м2]≤200[л] (22)
Ограничение по трубам ([м]) запишется так:
x1[шт]*1[м]+ x2[шт]*2[м]≥150[м] (23)
Ограничение по шурупам ([шт]) запишется так:
x1[шт]*30[шт]+ x2[шт]*40[шт]≥2000[шт] (24)
Как видно на рис. 7 данная задача имеет область допустимых значений и оптимальное решение.
|
Графическим методом можно найти оптимальное решение:
x1=100 прилавков x2=33,(3) витрин. Теоретическая максимальная прибыль F=333333.(3) руб. Но в реальности количество витрин не может быть дробным.
F=2000[руб]*x1[шт]+4000[руб]*x2[шт]
Опустим размерности и приведем систему к каноническому виду:
x1*4+ x2*6+x3=600
x1*1+ x2*3+x4=200
x1*1+ x2*2-x5=150 (25)
x1*30+ x2*40-x6=2000
xi≥0 i=1..6
Видим, что к данной системе нельзя применить симплекс метод, так как у нас нет единичного столбца. Получить его с помощью операций над уравнениями, не нарушая условия неотрицательности свободных членов невозможно. А значит, мы не можем найти первый опорный план.
Для решения этой проблемы введем в третье и четвертое уравнения системы (25) дополнительные искусственные переменные x7 и x8
Получим новую вспомогательную систему:
x1*4+ x2*6+x3=600
x1*1+ x2*3+x4=200
x1*1+ x2*2-x5+x7=150 (26)
x1*30+ x2*40-x6+x8=2000
xi≥0 i=1..8
Тогда критерий F’ для вспомогательной задачи будет равен: F’= x7+x8→min исходя из того, что вспомогательные переменные x7 и x8 необходимо обратить в ноль. В случае, если вспомогательные искусственные переменные нельзя обратить в 0, то общая задача не имеет решения.
Запишем симплекс таблицу для вспомогательной задачи:
1. Первый опорный план x’(1)=(0,0,600,200,0,0,150,2000)
| Cb | БП | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | b |
| 0 0 1 1 | x3 x4 x7 x8 | 4 1 1 30 | 6 3 2 40 | 1 0 0 0 | 0 1 0 0 | 0 0 -1 0 | 0 0 0 -1 | 0 0 1 0 | 0 0 0 1 | 600 200 150 2000 |
| ƒ’ | 31 | 42 | 0 | 0 | -1 | -1 | 0 | 0 | 2150 |
Определяем первую замену: x8 на x2
2. Второй опорный план x’(2)=(0,50,300,50,0,0,50,0)
| Cb | БП | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | b |
| 0 0 1 0 | x3 x4 x7 x2 | -0.5 -1.25 -0.5 0.75 | 0 0 0 1 | 1 0 0 0 | 0 1 0 0 | 0 0 -1 0 | 0.15 0.075 0.05 -0.025 | 0 0 1 0 | -0.15 -0.075 -0.05 0.025 | 300 50 50 50 |
| ƒ’ | -0.5 | 0 | 0 | 0 | -1 | 0.05 | 0 | -1.05 | 50 |
Определяем вторую замену: x4 на x6
3. Третий опорный план x’(3)=(0,66.(6),200,0,0,666.(6),16.(6),0)
| Cb | БП | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | b |
| 0 0 1 0 | x3 x6 x7 x2 | 2 -16.(6) 0.(3) 0.(3) | 0 0 0 1 | 1 0 0 0 | -2 13.(3) -0.(6) 0.(3) | 0 0 -1 0 | 0 1 0 0 | 0 0 1 0 | 0 -1 0 0 | 200 666.(6) 16.(6) 66.(6) |
| ƒ’ | 0.(3) | 0 | 0 | -0.(6) | -1 | 0 | 0 | -1 | 16.(6) |
Определяем третью замену: x7 на x1
4. Четвертый опорный план x’*=(50,50,100,0,0,1500,0,0)
| Cb | БП | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | b |
| 0 0 0 0 | x3 x6 x1 x2 | 0 0 1 0 | 0 0 0 1 | 1 0 0 0 | 2 -20 -2 1 | 6 -50 -3 1 | 0 1 0 0 | -6 50 3 -1 | 0 -1 0 0 | 100 1500 50 50 |
| ƒ’ | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 0 |
Данный опорный план оптимален для вспомогательной задачи, т.к. коэффициенты в критерии ≤0 (для min)
Перейдем обратно к первоначальной задаче от вспомогательной:
Уберем столбцы искусственных переменных x7 и x8 и вернем старый критерий: F=2000*x1+4000*x2
5. Первый опорный план для прямой задачи x(1)=(50,50,100,0,0,1500)
| Cb | БП | x1 | x2 | x3 | x4 | x5 | x6 | b |
| 0 0 2000 4000 | x3 x6 x1 x2 | 0 0 1 0 | 0 0 0 1 | 1 0 0 0 | 2 -20 -2 1 | 6 -50 -3 1 | 0 1 0 0 | 100 1500 50 50 |
| ƒ | 0 | 0 | 0 | 0 | -2000 | 0 | 300000 |
Определяем первую замену для прямой задачи: x3 на x5
6. Опорный план x*=(100,33.(3),0,0,16.(6),2333.(3))
| Cb | БП | x1 | x2 | x3 | x4 | x5 | x6 | b |
| 0 0 2000 4000 | x5 x6 x1 x2 | 0 0 1 0 | 0 0 0 1 | 0.1(6) 8.(3) 0.5 -0.(6) | 0.(3) -3.(3) -1 0.(6) | 1 0 0 0 | 0 1 0 0 | 16.(6) 2333.(3) 100 33.(3) |
| ƒ | 0 | 0 | 333.(3) | 666.(6) | 0 | 0 | 333333.(3) |
Теперь все оценки ≥0, значит, мы нашли оптимальный критерий прямой задачи (для max).
Решение симплекс методом (используя искусственный базис) дало то же самое оптимальное решение:
x1=100 прилавков x2=33,(3) витрин. Максимальная прибыль F=333333.(3) руб.
Порядок печати:
1,2:
22,3:4,21
20,5:6,19
18,7:8,17
16,9:10,15
14,11:12,13
