Фирма производит три вида продукции (А, В, С), для выпуска каждого из которых требуется определённое время обработки на всех четырёх устройствах 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 и находим по правилу треугольника
Задать вопрос
на новый заказ в Автор24.
