Предприятие строит дома двух проектов А и В и использует три вида основных стройматериалов. На строительство дома по проекту А требуется 5 куб. м кирпича, 10 куб. м — пиломатериалов и 1 т – цемента, а по проекту В соответственно 6 куб. м – кирпича, 7 куб. м – пиломатериалов и 2 т – цемента. На плановый период предприятие обеспечено кирпичем в количестве 30 куб.м, пиломатериалами в количестве 49 куб.м. Из-за трудностей с хранением и большими запасами цемента, его расход не должен быть менее 6 т. Строительство одного дома по проекту А дает предприятию 4 млн. руб прибыли, а – по проекту В – 3 млн. руб прибыли.
Составить план работы предприятия по строительству домов, максимизирующий его общую прибыль, если оно может само выбирать, сколько и по каким проектам строить домов, и незавершенное строительство подлежит оплате пропорциональной выполненным работам.
Решение:
Обозначим х1, х2 количество домов по проекту А и В соответственно, тогда максимальное значение целевой функции F(X) = 4x1 + 3x2 доставляет максимум прибыли при следующих условиях-ограничений.
5x1 + 6x2≤30
10x1 + 7x2≤49
x1 + 2x2≥6
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
5x1 + 6x2 + 1x3 + 0x4 + 0x5 = 30
10x1 + 7x2 + 0x3 + 1x4 + 0x5 = 49
1x1 + 2x2 + 0x3 + 0x4-1x5 = 6
Введем искусственные переменные x: в 3-м равенстве вводим переменную x6;
5x1 + 6x2 + 1x3 + 0x4 + 0x5 + 0x6 = 30
10x1 + 7x2 + 0x3 + 1x4 + 0x5 + 0x6 = 49
1x1 + 2x2 + 0x3 + 0x4-1x5 + 1x6 = 6
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 4x1+3x2 — Mx6 → max
Из уравнений выражаем искусственные переменные:
x6 = 6-x1-2x2+x5
которые подставим в целевую функцию:
F(X) = 4x1 + 3x2 — M(6-x1-2x2+x5) → max
или
F(X) = (4+M)x1+(3+2M)x2+(-M)x5+(-6M) → max
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | min |
| x3 | 30 | 5 | 6 | 1 | 0 | 0 | 0 | 5 |
| x4 | 49 | 10 | 7 | 0 | 1 | 0 | 0 | 7 |
| x6 | 6 | 1 | 2 | 0 | 0 | -1 | 1 | 3 |
| F(X1) | -6M | -4-M | -3-2M | 0 | 0 | M | 0 | 0 |
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | min |
| x3 | 12 | 2 | 0 | 1 | 0 | 3 | -3 | 6 |
| x4 | 28 | 61/2 | 0 | 0 | 1 | 31/2 | -31/2 | 44/13 |
| x2 | 3 | 1/2 | 1 | 0 | 0 | -1/2 | 1/2 | 6 |
| F(X2) | 9 | -21/2 | 0 | 0 | 0 | -11/2 | 11/2+M | 0 |
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | min |
| x3 | 35/13 | 0 | 0 | 1 | -4/13 | 112/13 | -112/13 | 119/25 |
| x1 | 44/13 | 1 | 0 | 0 | 2/13 | 7/13 | -7/13 | 8 |
| x2 | 11/13 | 0 | 1 | 0 | -1/13 | -10/13 | 10/13 | — |
| F(X3) | 1910/13 | 0 | 0 | 0 | 5/13 | -2/13 | 2/13+M | 0 |
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | |
| x5 | 44/25 | 0 | 0 | 13/25 | -4/25 | 1 | -1 | |
| x1 | 84/25 | 1 | 0 | -7/25 | 6/25 | 0 | 0 | |
| x2 | 11/5 | 0 | 1 | 2/5 | -1/5 | 0 | 0 | |
| F(X3) | 201/25 | 0 | 0 | 2/25 | 9/25 | 0 | M |
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Оптимальный план можно записать так:
x1 = 39/25
x2 = 21/5
F(X) = 4•39/25 + 3•21/5 = 201/25 млн рублей