Предприятие располагает двумя видами сырья S1 и S2 соответственно в количествах b1, b2, условных единиц. Из этого сырья может быть изготовлено два вида продукции Р1, Р2,. Для изготовления единицы Pj-го вида продукции необходимо ij a единиц Si-го (i=1,2) вида сырья. От реализации одной единицы каждого вида продукции предприятие получает доход ден. ед.
1.Найти оптимальный план геометрическим методом.
2.Найти оптимальный план симплексным методом.
3.Сформулировать экономически, записать и решить двойственную задачу. Пояснить экономический смысл полученных объективно обусловленных оценок.
Решение
Необходимо найти максимальное значение целевой функции F = 4x1+2x2 → max, при системе ограничений:3x1+x2≤21, (1)2x1+3x2≤30, (2)x1 ≥ 0, (3)x2 ≥ 0, (4)Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).Шаг №2. Границы области допустимых решений.Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.Обозначим границы области многоугольника решений.Шаг №3. Рассмотрим целевую функцию задачи F = 4x1+2x2 → max.Построим прямую, отвечающую значению функции F = 4x1+2x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (4;2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:3x1+x2=212x1+3x2=30Решив систему уравнений, получим: x1 = 4.7143, x2 = 6.8571Откуда найдем максимальное значение целевой функции:F(X) = 4*4.7143 + 2*6.8571 = 32.5714
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.Определим максимальное значение целевой функции F(X) = 4x1+2x2 при следующих условиях-ограничений.3x1+x2≤212x1+3x2≤30Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).3x1+x2+x3 = 212x1+3x2+x4 = 30Решим систему уравнений относительно базисных переменных: x3, x4Полагая, что свободные переменные равны 0, получим первый опорный план: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 -4 -2 0 0
Переходим к основному алгоритму симплекс-метода.Итерация №0.Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.Вычислим значения Di по строкам как частное от деления: bi / ai1и из них выберем наименьшее:min (21 : 3 , 30 : 2 ) = 7Следовательно, 1-ая строка является ведущей.Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 min
x3 21 3 1 1 0 7
x4 30 2 3 0 1 15
F(X1) 0 -4 -2 0 0
Формируем следующую часть симплексной таблицы
. Вместо переменной x3 в план 1 войдет переменная x1.Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4
x1 7 1 1/3 1/3 0
x4 16 0 7/3 -2/3 1
F(X1) 28 0 -2/3 4/3 0
Итерация №1.Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.Вычислим значения Di по строкам как частное от деления: bi / ai2и из них выберем наименьшее:min (7 : 1/3 , 16 : 21/3 ) = 66/7Следовательно, 2-ая строка является ведущей.Разрешающий элемент равен (21/3) и находится на пересечении ведущего столбца и ведущей строки.
Базис 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
F(X2) 28 0 -2/3 4/3 0
Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x2.Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4
x1 33/7 1 0 3/7 -1/7
x2 48/7 0 1 -2/7 3/7
F(X2) 228/7 0 0 8/7 2/7
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный планСреди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.Окончательный вариант симплекс-таблицы:
Базис B x1 x2 x3 x4
x1 33/7 1 0 3/7 -1/7
x2 48/7 0 1 -2/7 3/7
F(X3) 228/7 0 0 8/7 2/7
Оптимальный план можно записать так:x1 = 45/7, x2 = 66/7F(X) = 4*45/7 + 2*66/7 = 324/7
Построим двойственную задачу по следующим правилам.1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.3
Задать вопрос
на новый заказ в Автор24.
