В цехе имеется три группы станков В1, В2, В3 в количествах 19, 40 и 41 соответственно. Цех предполагает изготовлять изделия двух видов А1 и А2. Известно, что каждое изделие А1 обрабатывается на 1 станке группы В1, на 5 станках группы В2 и 4 станках группы B3. Каждое изделие А2 обрабатывается на 3 станках группы В1, на 2 станках группы В2 и 5 станках группы B3. Прибыль от реализации одного изделия вида A1 составляет 6 ден. ед., а изделия вида A2 10 ден. ед. Условия задачи можно кратко записать в виде следующей таблицы.
Таблица 1 – Исходные данные
Виды станков Вид
изделия Станочный
парк
A1 A2
B1 1 3 19
B2 5 2 40
B3 4 5 41
Прибыль, ден. ед. 6 10 max
Найти оптимальный план производства изделий, который должен обеспечивать получение наибольшей прибыли от их реализации.
Решение
Пусть – объем производства изделия вида А1, ед, а – объем производства изделия вида А2, ед.
В условии задачи сформулирована цель – добиться максимальной прибыли от реализации продукции, поэтому целевую функцию можно сформулировать следующим образом:
.
Ограничения на использование станков содержательно можно записать в виде:
x1+3x2 ≤ 19 - по использованию станков группы B1, ед.
5x1+2x2 ≤ 40 - по использованию станков группы B1, ед.
4x1+5x2 ≤ 41 - по использованию станков группы B3, ед.
При этом подразумевается, что объемы производства не могут принимать отрицательных значений, что записывается как:
.
Таким образом, математическая модель этой задачи имеет вид
1. Решение графическим методом.
1. Построим следующие прямые (рисунок 1).
Для этого вычислим координаты точек пересечения этих прямых с осями координат;
(2) (3)
После проведения штриховки допустимых полуплоскостей определяем, что ОДР - это многоугольник ABCDE.
Построим прямую, отвечающую значению функции F = 6x1+10x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (6;10). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Точка C - это последняя вершина многоугольника допустимых решений, через которую проходит целевая прямая, двигаясь по направлению вектора, т.е. С - это точка максимума целевой функции. Точка С находится на пересечении прямых (1) и (3).
,
Точка максимума (max) .
8) Таким образом, максимальное значение ЦФ равно:
.
C
D
(1)
(2)
(3)
А
E
N
B
Рисунок 1 – График решения задачи
Вывод: объем производства изделия А1 – 4 ед.; изделия А2 – 5 ед.; максимальный доход – 74 ден
. ед.
2. Решение симплекс методом.
Запишем условия задачи в виде модели задачи линейного программирования. Задачу можно сформулировать следующим образом: определим максимальное значение целевой функции:
При следующих ограничениях:
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных. В 1-м неравенстве вводим базисную переменную x3. В 2-м неравенстве вводим базисную переменную x4. В 3-м неравенстве вводим базисную переменную x5:
x1+3x2+x3=195x1+2x2+x4=404x1+5x2+x5=41xj≥0, J=1,5
Решим систему уравнений относительно базисных переменных:
x3=19-(x1+3x2)x4=40-(5x1+2x2)x5=41-(4x1+5x2)xj≥0, J=1,5
Функцию цели запишем в виде уравнения F(х) = 0 – (-6x1-10x2).
Получим первый опорный план. Предположим, что основные переменные в системе уравнений являются свободными и приравняем их к нулю (х1=0; х2=0 ). Тогда дополнительные переменные (базисные) будут равны объёмам ограничений (х3=19; х4=40; х5=41). Следовательно, товары не продаются, а ресурсы не используются, доход равен нулю: f(x)=0. Заносим этот план в первую симплексную таблицу.
Таблица 2 – Первая симплексная таблица
План Базисные переменные Свободные члены Основные переменные Дополнительные переменные
х1 х2 х3 х4 х5
I х3 19 1 3 1
х4 40 5 2 1
х5 41 4 5 1
Индексная строка f(x) 0 -6 -10
Опорный план, представленный в первой симплексной таблице, не оптимальный, т.к. в индексной строке находятся отрицательные коэффициенты: -6; -10.
Определяем новую базисную переменную. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю
Задать вопрос
на новый заказ в Автор24.
