В производстве пользующихся спросом двух изделий, А и В, принимают участие 3 цеха фирмы. На изготовление одного изделия А 1-й цех затрачивает 7 ч., 2-й цех – 6 ч., 3-й цех – 5 ч. На изготовление одного изделия В 1-й цех затрачивает 8 ч., 2-й цех – 3 ч., 3-й цех – 1 ч. На производство обоих изделий 1-й цех может затратить не более 476 ч., 2-й цех – не более 364 ч., 3-й цех – не более 319 ч.
От реализации одного изделия А фирма получает доход 11 тыс. руб., изделия В – 10 тыс. руб.
Определить оптимальный план производства изделий, обеспечивающий максимальный доход от реализации всех изделий А и В.
Решение
Пусть необходимо изготовить изделий А – х1, изделий В – х2, тогда ограничения
по цеху 1:7x1+8x2≤476,по цеху 2:6x1+3x2≤364,по цеху 3:5x1+x2≤319,
по неотрицательности переменных:x1 ≥ 0,x2 ≥ 0.
Необходимо найти максимальное значение целевой функции F = 11x1+10x2 → max при системе ограничений:
7x1+8x2≤476, (1)6x1+3x2≤364, (2)5x1+x2≤319, (3)x1 ≥ 0, (4)x2 ≥ 0, (5)
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
Строим прямую 7x1+8x2 = 476.
х1 0 68
х2 59,6 0
Определяем полуплоскость, которая задается неравенством. Выбираем точку (0; 0), определяем знак неравенства в полуплоскости:7 ∙ 0 + 8 ∙ 0 - 476 ≤ 0, т.е. 7x1+8x2 - 476≤ 0 в полуплоскости ниже прямой.
Строим прямую 6x1+3x2 = 364.
х1 0 60,67
х2 121,33 0
Определяем полуплоскость, которая задается неравенством. Выбираем точку (0; 0), определяем знак неравенства в полуплоскости:6 ∙ 0 + 3 ∙ 0 - 364 ≤ 0, т.е. 6x1+3x2 - 364≤ 0 в полуплоскости ниже прямой.
Строим прямую 5x1+x2 = 319.
х1 0 63,8
х2 319 0
Определяем полуплоскость, которая задается неравенством
. Выбираем точку (0; 0), определяем знак неравенства в полуплоскости:5 ∙ 0 + 1 ∙ 0 - 319 ≤ 0, т.е. 5x1+x2 - 319≤ 0 в полуплоскости ниже прямой.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Рассмотрим целевую функцию задачи F = 11x1+10x2 → max.
Построим прямую, которая отвечает значению функции F = 11x1+10x2 = 0. Вектор-градиент, который составлен из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (11; 10). Будем двигать прямую l0 параллельным образом. Т.к. нас интересует максимальное решение, то двигаем прямую l0 до последнего касания обозначенной области – l.
Прямая l пересекает область в точке C, которая получена в результате пересечения прямых (1) и (2), следовательно, ее координаты удовлетворяют уравнениям этих прямых:
7x1+8x2=4766x1+3x2=364
Решая систему уравнений, получаем: x1 = 54,963, x2 = 11,4074.
Находим максимальное значение целевой функции:
F(x) = 11∙54,963 + 10∙11,4074 = 718,6667.
Для построения опорного плана 1 систему неравенств приводим к системе уравнений путем введения дополнительных переменных (переходим к канонической форме).
В 1-м неравенстве смысла (≤) введем неотрицательную базисную переменную x3, во 2-м неравенстве смысла (≤)введем неотрицательную базисную переменную x4, в 3-м неравенстве смысла (≤) введем неотрицательную базисную переменную x5.
7x1+8x2+x3 = 4766x1+3x2+x4 = 3645x1+x2+x5 = 319
Матрица коэффициентов A = a(ij) системы уравнений принимает вид:
A = 7 8 1 0 0
6 3 0 1 0
5 1 0 0 1
Решаем систему уравнений относительно базисных переменных: x3, x4, x5
Полагаем, что свободные переменные равны 0, получим опорный план 1: X0 = (0,0,476,364,319)
Базис B x1 x2 x3 x4 x5
x3 476 7 8 1 0 0
x4 364 6 3 0 1 0
x5 319 5 1 0 0 1
F(X0) 0 -11 -10 0 0 0
Переходим к симплекс-преобразованиям.
Ключевой столбец выбираем по наименьшему отрицательному элементу индексной строки.
Ключевую строку выбираем по наименьшему отношению частного от деления: bi / aij.
Ключевой элемент находится на пересечении ключевого столбца и ключевой строки.
Все вычисления сводим в симплекс-таблицы.
Переход от одной симплекс-таблицы к другой проводим по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, расположенные в вершинах прямоугольника и всегда включающие ключевой элемент КЭ.
НЭ = СтЭ - (А∙В)/КЭ
СтЭ – элемент старого плана,
КЭ – ключевой элемент,
А и В – элементы старого плана, образующие прямоугольник с элементами СтЭ и КЭ.
Базис B x1↓ x2 x3 x4 x5 min
x3 476 7 8 1 0 0 68
←x4 364 6 3 0 1 0 182/3
x5 319 5 1 0 0 1 319/5
F(X1) 0 -11 -10 0 0 0
Базис B x1 x2↓ x3 x4 x5 min
←x3 154/3 0 9/2 1 -7/6 0 308/27
x1 182/3 1 1/2 0 1/6 0 364/3
x5 47/3 0 -3/2 0 -5/6 1 -
F(X2) 2002/3 0 -9/2 0 11/6 0
Базис B x1 x2 x3 x4 x5
x2 308/27 0 1 2/9 -7/27 0
x1 1484/27 1 0 -1/9 8/27 0
x5 295/9 0 0 1/3 -11/9 1
F(X2) 2156/3 0 0 1 2/3 0
Т.к
Задать вопрос
на новый заказ в Автор24.
