Предприятие предполагает освоить производство двух видов изделий A1 и А2, обладая тремя видами ресурсов S1, S2 и S3 (сырье, рабочая сила и оборудование).
Условие задачи можно представить в виде таблицы.
Вид ресурса Расход ресурса на 1 ед. изделия Общее количество ресурса
А1 А2
S1 1 3 19
S2 5 2 40
S3 4 5 41
Прибыль на 1 изделие (усл. ед.) 6 10
Найти оптимальный план производства изделий, обеспечивающий максимальную прибыль.
Решение
Пусть необходимо выпускать изделий А1 – х1, изделий А2 – х2, тогда ограничения
по ресурсу S1:x1+3x2≤19,по ресурсу S2:5x1+2x2≤40,по ресурсу S3:4x1+5x2≤41,
по неотрицательности переменных:
х1>0,
х2>0.
Прибыль определяется как F=6x1+10x2, которую необходимо максимизировать.
Математическая модель задачи имеет вид:
F = 6x1+10x2 → max
x1+3x2≤19,5x1+2x2≤40,4x1+5x2≤41,
х1>0,
х2>0.
Необходимо найти максимальное значение целевой функции F = 6x1+10x2 при системе ограничений:
x1+3x2≤19, (1)5x1+2x2≤40, (2)4x1+5x2≤41, (3)x1 ≥ 0, (4)x2 ≥ 0, (5)
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
Построим уравнение x1+3x2 = 19 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 6.33. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 19. Соединяем точку (0;6.33) с (19;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 ∙ 0 + 3 ∙ 0 - 19 ≤ 0, т.е. x1+3x2 - 19≤ 0 в полуплоскости ниже прямой.
Построим уравнение 5x1+2x2 = 40 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 20. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 8. Соединяем точку (0;20) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:5 ∙ 0 + 2 ∙ 0 - 40 ≤ 0, т.е. 5x1+2x2 - 40≤ 0 в полуплоскости ниже прямой.
Построим уравнение 4x1+5x2 = 41 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 8.2. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 10.25. Соединяем точку (0;8.2) с (10.25;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 4 ∙ 0 + 5 ∙ 0 - 41 ≤ 0, т.е
. 4x1+5x2 - 41≤ 0 в полуплоскости ниже прямой.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 6x1+10x2 → max.
Построим прямую, отвечающую значению функции F = 6x1+10x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (6;10). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области.
Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
x1+3x2=194x1+5x2=41
Решив систему уравнений, получим: x1 = 4, x2 = 5.
Откуда найдем максимальное значение целевой функции:
F(x) = 6∙4 + 10∙5 = 74.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
x1+3x2+x3 = 195x1+2x2+x4 = 404x1+5x2+x5 = 41
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 1 3 1 0 0
5 2 0 1 0
4 5 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,19,40,41)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5
x3 19 1 3 1 0 0
x4 40 5 2 0 1 0
x5 41 4 5 0 0 1
F(X0) 0 -6 -10 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1
Задать вопрос
на новый заказ в Автор24.
