Фирма производит три вида продукции (А, В, С), для выпуска каждого из которых требуется определённое время обработки на всех четырёх устройствах I, II, III, IV.
Вид продукции Время обработки Прибыль, дол.
I II III IV
А 5 3 3 2 7
В 5 4 3 3 9
С 3 3 2 4 6
Время работы устройства 76 39 23 42
Определите, какую продукцию и в каких количествах следует производить. Рынок сбыта для каждого продукта неограничен. Временем, требуемым для переключения устройства в зависимости от вида продукции, можно пренебречь. Рассмотреть задачу максимизации прибыли.
Ответ
по оптимальному плану необходимо произвести 7,667 ед. продукции вида В, при этом максимальная прибыль фирмы составит 69 дол.
Решение
Обозначим через Х=(х1,х2,х3) – план производства, показывающий количество произведенной продукции соответственно А, В и С. Общий объем прибыли – это целевая функция, которую необходимо максимизировать:
(1)
Составим систему ограничений на время работы устройств:
Чтобы искомый план был реален, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объемы xj выпуска продукции:
(3)
Таким образом (1)-(3) – математическая модель задачи о наилучшем использовании сырья.
Сведем задачу (1)-(3) к каноническому виду, добавив к левым частям неравенств дополнительные переменные х4, х5, х6, х7 ≥ 0. В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю.
Значит, каноническая форма задачи имеет вид:
Экономический смысл переменных:
хj (i=1,2,3) – количество произведенной продукции,
хj (i=4,5,6,7) – количество оставшегося ресурса.
Решаем задачу (1/)-(3/)/// симплекс-методом.
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6, x7
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,76,39,23,42)
Базисное решение является допустимым, поскольку оно неотрицательно
.
Базис
B x1 x2 x3 x4 x5 x6 x7
x4 76 5 5 5 1 0 0 0
x5 39 3 4 3 0 1 0 0
x6 23 3 3 2 0 0 1 0
x7 42 2 3 4 0 0 0 1
F(X0) 0 -7 -9 -6 0 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (76 : 5 , 39 : 4 , 23 : 3 , 42 : 3 ) = 7.667
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B x1 x2 x3 x4 x5 x6 x7 min
x4 76 5 5 5 1 0 0 0 15.2
x5 39 3 4 3 0 1 0 0 9.75
x6 23 3 3 2 0 0 1 0 7.667
x7 42 2 3 4 0 0 0 1 14
F(X0) 0 -7 -9 -6 0 0 0 0
Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы
Задать вопрос
на новый заказ в Автор24.
