Для производства двух видов изделий А и Б предприятие использует три вида сырья: 1, 2 и 3. На изготовление единицы изделия А расходуется 12 единиц сырья 1; 4 единицы сырья 2; 3 единицы сырья 3; изделия Б – 4 единицы сырья 1; 4 единицы сырья 2; 12 единиц сырья 3. На предприятии имеется 300 единиц сырья 1; 120 единиц сырья 2; 252 единицы сырья 3. Прибыль от реализации одного изделия А составляет 30 рублей, изделия Б – 40 рублей. Составить план выпуска изделий А и Б, при котором прибыль от реализации будет максимальной.
Решение
Пусть необходимо выпустить изделий А – х1, изделий Б – х2, тогда ограничения
по сырью 1:12x1+4x2≤300,по сырью 2:4x1+4x2≤120,по сырью 3:3x1+12x2≤252,
по неотрицательности переменных:x1 ≥ 0,x2 ≥ 0.
Прибыль определяется как F=30x1+40x2, которую необходимо максимизировать.
Математическая модель задачи имеет вид:
F = 30x1+40x2 → max
12x1+4x2≤300,4x1+4x2≤120,3x1+12x2≤252,x1 ≥ 0,x2 ≥ 0.
Необходимо найти максимальное значение целевой функции F = 30x1+40x2 при системе ограничений:
12x1+4x2≤300,(1)4x1+4x2≤120, (2)3x1+12x2≤252, (3)x1 ≥ 0, (4)x2 ≥ 0, (5)
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
Построим уравнение 12x1+4x2 = 300 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 75. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 25. Соединяем точку (0;75) с (25;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:12 ∙ 0 + 4 ∙ 0 - 300 ≤ 0, т.е. 12x1+4x2 - 300≤ 0 в полуплоскости ниже прямой.
Построим уравнение 4x1+4x2 = 120 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 30. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 30. Соединяем точку (0;30) с (30;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:4 ∙ 0 + 4 ∙ 0 - 120 ≤ 0, т.е. 4x1+4x2 - 120≤ 0 в полуплоскости ниже прямой.
Построим уравнение 3x1+12x2 = 252 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 21. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 84. Соединяем точку (0;21) с (84;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:3 ∙ 0 + 12 ∙ 0 - 252 ≤ 0, т.е
. 3x1+12x2 - 252≤ 0 в полуплоскости ниже прямой.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 30x1+40x2 → max.Построим прямую, отвечающую значению функции F = 30x1+40x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (30;40). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области.
Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
4x1+4x2=1203x1+12x2=252
Решив систему уравнений, получим: x1 = 12, x2 = 18
Откуда найдем максимальное значение целевой функции:
F(x) = 30∙12 + 40∙18 = 1080.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
12x1+4x2+x3 = 3004x1+4x2+x4 = 1203x1+12x2+x5 = 252Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 12 4 1 0 0
4 4 0 1 0
3 12 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,300,120,252)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5
x3 300 12 4 1 0 0
x4 120 4 4 0 1 0
x5 252 3 12 0 0 1
F(X0) 0 -30 -40 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1
Задать вопрос
на новый заказ в Автор24.
