Предприятие выпускает два вида продукции А1 и А2, используя при этом три вида сырья S1, S2 и S3. Известны запасы сырья равные b1, b2 и b3 соответственно. Расход сырья вида Si на производство единицы продукции Aj равен aij. Доход от реализации единицы продукции Aj составляет j c условных единиц. Требуется составить такой план производства продукции, при котором доход будет максимальным.
Решить задачу графическим методом; составить каноническую модель данной задачи и решить ее симплекс-методом. Найти двойственные оценки цен на сырье, из решения симметричной двойственной задачи.
Решение
Необходимо найти максимальное значение целевой функции F = 27x1+21x2 → max при системе ограничений:
21x1+6x2≤1188, (1)18x1+12x2≤1512, (2)18x1+27x2≤2862, (3)x1 ≥ 0, (4)x2 ≥ 0, (5)
Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение 21x1+6x2 = 1188 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 198. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 56.57. Соединяем точку (0; 198) с (56.57; 0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 21 ∙ 0 + 6 ∙ 0 - 1188 ≤ 0, т.е. 21x1+6x2 - 1188≤ 0 в полуплоскости ниже прямой.
Построим уравнение 18x1+12x2 = 1512 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 126. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 84. Соединяем точку (0; 126) с (84; 0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:18 ∙ 0 + 12 ∙ 0 - 1512 ≤ 0, т.е. 18x1+12x2 - 1512≤ 0 в полуплоскости ниже прямой.
Построим уравнение 18x1+27x2 = 2862 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 106. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 159. Соединяем точку (0; 106) с (159; 0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:18 ∙ 0 + 27 ∙ 0 - 2862 ≤ 0, т.е. 18x1+27x2 - 2862≤ 0 в полуплоскости ниже прямой.
Шаг №2. Границы области допустимых решений.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Шаг №3. Рассмотрим целевую функцию задачи F = 27x1+21x2 → max.
Построим прямую, отвечающую значению функции F = 27x1+21x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (27;21). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
18x1+12x2=151218x1+27x2=2862
Решив систему уравнений, получим: x1 = 24, x2 = 90.
Откуда найдем максимальное значение целевой функции:
F(X) = 27∙24 + 21∙90 = 2538.
Таким образом, для получения максимального дохода 2538 необходимо выпускать продукции А1 – 24, продукции А2 – 90.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3
. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
21x1+6x2+x3 = 118818x1+12x2+x4 = 151218x1+27x2+x5 = 2862
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 21 6 1 0 0
18 12 0 1 0
18 27 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,1188,1512,2862)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5
x3 1188 21 6 1 0 0
x4 1512 18 12 0 1 0
x5 2862 18 27 0 0 1
F(X0) 0 -27 -21 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1и из них выберем наименьшее:
min (1188 : 21 , 1512 : 18 , 2862 : 18 ) = 564/7
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (21) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x3 1188 21 6 1 0 0 396/7
x4 1512 18 12 0 1 0 84
x5 2862 18 27 0 0 1 159
F(X1) 0 -27 -21 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=21. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А∙В)/РЭ
СТЭ - элемент старого плана,
РЭ - разрешающий элемент (21),
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5
x1 396/7 1 2/7 1/21 0 0
x4 3456/7 0 48/7 -6/7 1 0
x5 12906/7 0 153/7 -6/7 0 1
F(X1) 10692/7 0 -93/7 9/7 0 0
Итерация №1.
1
Задать вопрос
на новый заказ в Автор24.
