Фирма производит три вида продукции (А, В, С), для выпуска каждого из которых требуется

Фирма производит три вида продукции (А, В, С), для выпуска каждого из которых требуется определённое время обработки на всех четырёх устройствах I, II, III, IV. m-2, n-2, k-5 Вид продукции Время обработки Прибыль, дол. I II III IV А 3 3 6 2 5 В 6 3 3 3 8 С 3 3 2 4 9 Пусть время работы устройства, соответственно, 80, 40, 26 и 42 часа. Определите, какую продукцию и в каких количествах следует производить. Рынок сбыта для каждого продукта неограничен. Временем, требуемым для переключения устройства в зависимости от вида продукции, можно пренебречь. Рассмотреть задачу максимизации прибыли.

Составим математическую модель задачи
Переменные:
x1 – объем производства продукции А;
x2 – объем производства продукции В;
x3 – объем производства продукции А.
Тогда:
3x1+6x2+3x3 – время обработки продукции на устройстве I;
3x1+3x2+3x3 – время обработки продукции на устройстве II;
6x1+3x2+2x3 – время обработки продукции на устройстве III;
2x1+3x2+4x3 – время обработки продукции на устройстве IV.
Время работы устройств равно 80, 40, 26, и 42 часа соответственно, поэтому должны выполняться неравенства:
3x1+6x2+3x3≤80
3x1+3x2+3x3≤40
6x1+3x2+2x3≤26
2x1+3x2+4x3≤42
По смыслу задачи переменные x1, x2, x3 должны быть неотрицательными.
Прибыль от реализации продукции будет равна:
F=5x1+8x2+9x3
Получим математическую модель задачи:
Найти максимальное значение функции:
F=5x1+8x2+9x3→max
при ограничениях:
3x1+6x2+3x3≤803x1+3x2+3x3≤406x1+3x2+2x3≤262x1+3x2+4x3≤42x1, x2, x3≥0
Решение задачи симплекс-методом
Запишем задачу в форме основной задачи линейного программирования. В системе ограничений перейдем от неравенств к равенствам, для чего введем дополнительные переменные x4,x5, x6,x7 ≥0.
Система ограничений примет вид:
3x1+6x2+3x3+x4=803x1+3x2+3x3+x5=406x1+3x2+2x3+x6=262x1+3x2+4x3+x7=42xi≥0, i=1,7
Целевая функция примет вид:
FX=5x1+8x2+9x3+0∙x4+0∙x5+0∙x6+0∙x7→max
Переменные x4,x5, x6,x7 – базисные. Они определяют начальный опорный план
X1=(0;0;0;80;40;26;42).
Составим первую симплекс-таблицу.
Таблица 1
№ Базис Сб
Р0
Переменные
x6
x7
5 8 9 0 0 0 0
1 x4
0 80 3 6 3 1 0 0 0
2 x5
0 40 3 3 3 0 1 0 0
3 x6
0 26 6 3 2 0 0 1 0
4 x7
0 42 2 3 4 0 0 0 1
F=0 –5 –8 -9 0 0 0 0
X1=(0;0;0;80;40;26;42).
F=0∙1095+0∙865+0∙1080=0
Найдем оценки:
∆j=i=13ciaij-cj
где cj – коэффициенты при неизвестных целевой функции,
aij – коэффициенты при неизвестных в системе ограничений, ci – коэффициенты при базисных переменных.
Оценки в столбцах базисных переменных равны 0: ∆4=∆5=∆6=∆7=0.
∆1=0∙3+0∙3+0∙6+0∙2-5=-5
∆2=0∙6+0∙3+0∙3+0∙3-8=-8
∆3=0∙3+0∙3+0∙2+0∙4-9=-9
Поскольку среди есть отрицательные оценки, то опорный план не является оптимальным

. Среди коэффициентов при переменных в соответствующих столбцах есть положительные, поэтому можно перейти к новому базису и другому опорному плану.
В качестве переменной, вводимой в базис, возьмем переменную x3 (отрицательная оценка по модулю максимальна). Столбец переменной x3 – ключевой.
Для определения переменной, подлежащей исключению из базиса, составим отношения элементов столбца Р0 к соответствующим положительным значениям ключевого столбца и найдем среди них минимальное:
min803; 403;261;424=424
Значит, из базиса выводим переменную x7. Четвертая строка – ключевая, a43=4 – разрешающий элемент.
Перейдем ко второй симплекс-таблице.
Таблица 2
№ Базис Сб
Р0
Переменные
x6
x7
5 8 9 0 0 0 0
1 x4
0 48,5 1,5 3,75 0 1 0 0 -0,75
2 x5
0 8,5 1,5 0,75 0 0 1 0 -0,75
3 x6
0 5 5 1,5 0 0 0 1 -0,5
4 x3
9 10,5 0,5 0,75 1 0 0 0 0,25
F=94,5 -0,5 -1,25 0 0 0 0 -1,25
X2=(0;0;10,5;48,5;8,5;5;0).
Заполнение второй симплекс-таблицы:
В столбцах переменных, входящих в базис, на пересечении строк и столбцов одноименных переменных проставляются 1, а остальные элементы этих столбцов равны 0.
Элементы столбцов Р0 и в строке переменной, вводимой в базис, получаем делением соответствующих элементов исходной таблицы на разрешающий элемент.
Остальные элементы столбцов Р0 и находим по правилу треугольника