Предприятие располагает двумя видами сырья S1 и S2 соответственно в количествах b1, b2 условных единиц. Из этого сырья может быть изготовлено два вида продукции Р1, Р2. Для изготовления единицы Pj-го вида продукции необходимо aij единиц Si-го (i=1,2) вида сырья. От реализации одной единицы каждого вида продукции предприятие получает доход ден. ед.
1. Найти оптимальный план геометрическим методом.
2. Найти оптимальный план симплексным методом.
3. Сформулировать экономически, записать и решить двойственную задачу. Пояснить экономический смысл полученных объективно обусловленных оценок.
С=(5,4)
Вид сырья Запас сырья Расход сырья на продукцию
Р1 Р2
S1 24 3 0
S2 36 2 3
Решение
Пусть продукции Р1 необходимо выпускать х1, продукции Р2 – х2, тогда ограничения по
сырью S1:3x1≤24,
сырью S2:2x1+3x2≤36,
по неотрицательности переменных:
x1 ≥ 0,
x2 ≥ 0.
Доход определяется как F=5x1+4x2, который необходимо максимизировать.
Математическая модель имеет вид:
F = 5x1+4x2 → max
3x1≤24, 2x1+3x2≤36,
x1 ≥ 0,
x2 ≥ 0.
Решим задачу графически.
Необходимо найти максимальное значение целевой функции F = 5x1+4x2 → max при системе ограничений:
3x1≤24, (1)
2x1+3x2≤36, (2)
x1 ≥ 0, (3)
x2 ≥ 0, (4)
Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение 3x1 = 24. Эта прямая проходит через точку x1 = 24/3 = 8 параллельно оси OX2. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 ∙ 0 - 24 ≤ 0, т.е. 3x1 - 24≤ 0 в полуплоскости левее прямой.
Построим уравнение 2x1+3x2 = 36 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 12. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 18. Соединяем точку (0;12) с (18;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:2 ∙ 0 + 3 ∙ 0 - 36 ≤ 0, т.е. 2x1+3x2 - 36≤ 0 в полуплоскости ниже прямой.
Шаг №2. Границы области допустимых решений.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Шаг №3. Рассмотрим целевую функцию задачи F = 5x1+4x2 → max.
Построим прямую, отвечающую значению функции F = 5x1+4x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (5;4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
3x1=242x1+3x2=36
Решив систему уравнений, получим: x1 = 8, x2 = 62/3.
Откуда найдем максимальное значение целевой функции:
F(X) = 5∙8 + 4∙62/3= 662/3.
Таким образом, для получения максимального дохода 662/3 ден
. ед. продукции Р1 необходимо выпускать 8, продукции Р2 – 62/3.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 5x1+4x2 при следующих условиях-ограничениях:
3x1≤242x1+3x2≤36
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4.
3x1+x3 = 24
2x1+3x2+x4 = 36
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 3 0 1 0
2 3 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3, x4
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,24,36)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4
x3 24 3 0 1 0
x4 36 2 3 0 1
F(X0) 0 -5 -4 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1и из них выберем наименьшее:
min (24 : 3 , 36 : 2 ) = 8
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 min
x3 24 3 0 1 0 8
x4 36 2 3 0 1 18
F(X1) 0 -5 -4 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=3
Задать вопрос
на новый заказ в Автор24.
