Пусть необходимо изготовить продукции Р1 – х1, продукции Р2 – х2, тогда ограничения:
по сырью S1: 3x1+x2≤21,по сырью S2:2x1+3x2≤30,
по неотрицательности переменных:
x1 ≥ 0,
x2 ≥ 0.
Доход определяется как F=3x1+2x2, который необходимо максимизировать.
Математическая модель задачи имеет вид:
F = 3x1+2x2 →
3x1+x2≤21,2x1+3x2≤30,
x1 ≥ 0,
x2 ≥ 0.
Решение
Необходимо найти максимальное значение целевой функции F = 3x1+2x2 при системе ограничений:
3x1+x2≤21, (1)2x1+3x2≤30, (2)x1 ≥ 0, (3)x2 ≥ 0, (4)
Строим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
Строим прямую 3x1+x2 = 21.
х1 0 7
х2 21 0
Определяем полуплоскость, которая задается неравенством. Выбираем точку (0; 0), определяем знак неравенства в полуплоскости:3 ∙ 0 + 1 ∙ 0 - 21 ≤ 0, т.е. 3x1+x2 - 21≤ 0 в полуплоскости ниже прямой.
Построим уравнение 2x1+3x2 = 30 по двум точкам.
х1 0 15
х2 10 0
Определяем полуплоскость, которая задается неравенством. Выбираем точку (0; 0), определяем знак неравенства в полуплоскости: 2 ∙ 0 + 3 ∙ 0 - 30 ≤ 0, т.е. 2x1+3x2 - 30≤ 0 в полуплоскости ниже прямой.
Пересечением полуплоскостей будет являться область, координаты точек которой удовлетворяют условиям неравенств системы ограничений задачи.
Рассмотрим целевую функцию задачи F = 3x1+2x2 → max.
Построим прямую, которая отвечает значению функции F = 3x1+2x2 = 0.
Вектор-градиент, который составлен из коэффициентов целевой функции, указывает направление максимизации F(X)
. Начало вектора – точка (0; 0), конец – точка (3; 2). Двигаем прямую l0 параллельным образом. Т.к. нас интересует максимальное решение, то двигаем прямую l0 до последнего касания обозначенной области – l.
Прямая l пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
3x1+x2=212x1+3x2=30
Решив систему уравнений, получаем: x1 = 4,7143, x2 = 6,8571.
Находим максимальное значение целевой функции:
F(x) = 3∙4,7143 + 2∙6,8571 = 27,8571.
Таким образом, для получения максимального дохода 27,8571 необходимо изготовить продукции Р1 – 4,7143, продукции Р2 – 6,8571.
Решим ЗЛП симплекс-методом с использованием симплекс-таблицы.
Для построения опорного плана 1 систему неравенств приводим к системе уравнений путем введения дополнительных переменных (переходим к канонической форме).
В 1-м неравенстве смысла (≤) введем неотрицательную базисную переменную x3, во 2-м неравенстве смысла (≤) введем неотрицательную базисную переменную x4.
3x1+x2+x3 = 21
2x1+3x2+x4 = 30
Матрица коэффициентов A = a(ij) этой системы уравнений принимает вид:
A = 3 1 1 0
2 3 0 1
Решим систему уравнений относительно базисных переменных: x3, x4
Полагаем, что свободные переменные равны 0, получим опорный план 1: X0 = (0,0,21,30)
Базис B x1 x2 x3 x4
x3 21 3 1 1 0
x4 30 2 3 0 1
F(X0) 0 -3 -2 0 0
Переходим к симплекс-преобразованиям.
Ключевой столбец выбираем по наименьшему отрицательному элементу индексной строки.
Ключевую строку выбираем по наименьшему отношению частного от деления: bi / aij.
Ключевой элемент находится на пересечении ключевого столбца и ключевой строки.
Все вычисления сводим в симплекс-таблицы.
Переход от одной симплекс-таблицы к другой проводим по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, расположенные в вершинах прямоугольника и всегда включающие ключевой элемент КЭ.
НЭ = СтЭ - (А∙В)/КЭ
СтЭ – элемент старого плана,
КЭ – ключевой элемент,
А и В – элементы старого плана, образующие прямоугольник с элементами СтЭ и КЭ.
БП B x1 x2 x3 x4 min
x3 21 3 1 1 0 7
x4 30 2 3 0 1 15
∆ 0 -3 -2 0 0
БП B x1 x2 x3 x4 min
x1 7 1 1/3 1/3 0 21
x4 16 0 7/3 -2/3 1 48/7
∆ 21 0 -1 1 0
БП B x1 x2 x3 x4
x1 33/7 1 0 3/7 -1/7
x2 48/7 0 1 -2/7 3/7
∆ 195/7 0 0 5/7 3/7
Т.к
Задать вопрос
на новый заказ в Автор24.
