Предприятие производит 2 вида стульев. Для производства стульев каждого вида необходимы обивка, наполнитель, древесина.
Нормы затрат ресурсов на единицу продукции каждого вида (кг/шт) и запасы ресурсов (кг) приведены в таблице:
I вид II вид Запасы
обивка 1 1 100
наполнитель 2 3 330
древесина 2 4 400
Стулья первого вида реализуются по стоимости 300 руб. за единицу товара, второго вида – 400 руб. за единицу товара. Найти план производства, обеспечивающий наибольший доход.
Выполнить анализ чувствительности оптимального решения к изменению запасов продуктов.
Решение
Переход к составлению задачи линейного программирования.
В соответствии с условиями задачи составим функцию и ограничения:F(X) = 300x1+400x2 → max при ограничениях: x1+x2≤100 2x1+3x2≤330 2x1+4x2≤400 x1 ≥ 0, x2 ≥ 0 F(X) = 300x1+400x2 В 1-м неравенстве вводим базисную переменную x3. В 2-м неравенстве вводим базисную переменную x4. В 3-м неравенстве вводим базисную переменную x5.
x1+x2+x3 = 100 2x1+3x2+x4 = 330 2x1+4x2+x5 = 400
2. Переход к составлению симплекс-задачи линейного программирования.Расширенная матрица системы ограничений-равенств данной задачи:
1 1 1 0 0 100
2 3 0 1 0 330
2 4 0 0 1 400
1. В качестве базовой переменной можно выбрать x3. 2. В качестве базовой переменной можно выбрать x4. 3. В качестве базовой переменной можно выбрать x5. Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5). Соответствующие уравнения имеют вид: x1+x2+x3 = 100 2x1+3x2+x4 = 330 2x1+4x2+x5 = 400 Выразим базисные переменные через остальные: x3 = -x1-x2+100 x4 = -2x1-3x2+330 x5 = -2x1-4x2+400 Подставим их в целевую функцию: F(X) = 300x1+400x2 или F(X) = 300x1+400x2 → max Система неравенств: -x1-x2+100 ≥ 0 -2x1-3x2+330 ≥ 0 -2x1-4x2+400 ≥ 0 Приводим систему неравенств к следующему виду: x1+x2 ≤ 100 2x1+3x2 ≤ 330 2x1+4x2 ≤ 400 F(X) = 300x1+400x2 → max Упростим систему. x1+x2 ≤ 100 2x1+3x2 ≤ 330 2x1+4x2 ≤ 400 F(X) = 300x1+400x2 → max Если задача ЛП решается на поиск min-го значения, то стандартная форма будет иметь следующий вид: -x1-x2 ≤ -100 -2x1-3x2 ≤ -330 -2x1-4x2 ≤ -400 F(X) = -300x1-400x2 → min Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 300x1+400x2 при следующих условиях-ограничений. x1+x2+x3+100=100 2x1+3x2+x4+330=330 2x1+4x2+x5+400=400 Расширенная матрица системы ограничений-равенств данной задачи:
1 1 1 0 0 100
2 3 0 1 0 330
2 4 0 0 1 400
1. В качестве базовой переменной можно выбрать x3. 2. В качестве базовой переменной можно выбрать x4. 3. В качестве базовой переменной можно выбрать x5. Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5). Выразим базисные переменные через остальные: x3 = -x1-x2+100 x4 = -2x1-3x2+330 x5 = -2x1-4x2+400 Подставим их в целевую функцию: F(X) = 300x1+400x2 x1+x2+x3=100 2x1+3x2+x4=330 2x1+4x2+x5=400 Решим систему уравнений относительно базисных переменных: x3, x4, x5 Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,100,330,400)
Базис B x1 x2 x3 x4 x5
x3 100 1 1 1 0 0
x4 330 2 3 0 1 0
x5 400 2 4 0 0 1
F(X0) 0 -300 -400 0 0 0
Переходим к основному алгоритму симплекс-метода
. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (100 : 1 , 330 : 3 , 400 : 4 ) = 100 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x3 100 1 1 1 0 0 100
x4 330 2 3 0 1 0 110
x5 400 2 4 0 0 1 100
F(X1) 0 -300 -400 0 0 0 0
Поскольку в последнем столбце присутствует несколько минимальных элементов 100, то номер строки выбираем по правилу Креко. Метод Креко заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения min=100, делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам. Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x2. Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5
x3 0 1/2 0 1 0 -1/4
x4 30 1/2 0 0 1 -3/4
x2 100 1/2 1 0 0 1/4
F(X1) 40000 -100 0 0 0 100
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (0 : 1/2 , 30 : 1/2 , 100 : 1/2 ) = 0 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1/2) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x3 0 1/2 0 1 0 -1/4 0
x4 30 1/2 0 0 1 -3/4 60
x2 100 1/2 1 0 0 1/4 200
F(X2) 40000 -100 0 0 0 100 0
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 2 войдет переменная x1
Задать вопрос
на новый заказ в Автор24.
