Симплекс-метод решения задачи линейного программирования.
Составить математическую модель задачи, дав экономическую интерпретацию переменным, функции цели и системе ограничений.
Решить задачу симплекс-методом. В процессе решения дать экономическую интерпретацию каждого шага.
Решить задачу с использованием компьютера, сопроводив решение анализом полученного результата. Распечатать отчет по результатам.
Сырье Норма расхода сырья на единицу продукции Ресурсы (bi)
А В
1 4,5 1 2400
2 1 5 820
3 - 10 2000
Цена (cj) 10,5 3
Решение
Составить экономико-математическую модель задачи линейного программирования.
Обозначим через x1 количество произведенной продукции вида A, а через x2 количество произведенной продукции вида B.
Необходимо узнать максимальную прибыль, которую может получить фирма. Выразим через выбранные неизвестные суммарную прибыль от реализации всей продукции. Целевая функция включает в себя прибыль от реализации продукции вида А и продукции вида B. Тогда цель задачи (максимизация прибыли) запишется в виде:
Fx=10,5x1+3x2→max
Перейдем к формулировке ограничений. Структура всех трех ограничений одинакова:
расход ресурса ≤ запас ресурса
Теперь остается выразить полный расход ресурса через выбранные неизвестные x1 и x2.
Так, расход сырья первого вида на выпуск всей продукции типа A составит 4,5∙x1, а на выпуск всей продукции типа B составит 1,0∙x2. В сумме это даст полный расход сырья первого вида и ограничение примет вид линейного неравенства:
4,5x1+x2≤2400
Аналогично запишутся ограничения для остальных видов ресурсов
x1+5x2≤820
10x2≤2000
Объединяя их в систему, получим
4,5x1+x2≤2400x1+5x2≤820x2≤200
Далее, исходя из смысла введенных переменных, на них необходимо наложить условия не отрицательности: x1≥0 и x2≥0.
Окончательно запишем математическую модель задачи в форме ЗЛП:
Fx=10,5x1+3x2→max
4,5x1+x2≤2400;x1+5x2≤820;x2≤200; x1≥0; x2≥0.
Решим данную задачу симплекс-методом.
Введем дополнительные переменные x3, x4, x5, так чтобы система неравенств превратилась в систему равенств
. Ограничения примут вид:
4,5x1+x2+x3=2400;x1+5x2+x4=820;x2+x5=200; xi≥0; i=1,5.
Анализируя каноническую модель задачи, замечаем, что каждая из переменных x3, x4, x5 входит только в одно из уравнений системы, т. е. эти переменные входят в систему ограничений в предпочтительном виде и их можно взять в качестве базисных. Переменные x1, x2 будут свободными.
Составляем первую симплекс-таблицу:
БП 10,5 3 0 0 0 Bi
biaip
x1
x2
x3
x4
x5
x3
4,5 1 1 0 0 2400 240010,5=533,33
x4
1 5 0 1 0 820 8201=820
x5
0 1 0 0 1 200 -
FX0
-10,5 -3 0 0 0 0
Все элементы столбца свободных членов положительны. Следовательно, план будет равен X10=0;0;2400;820;200 и является опорным. Однако этот план не является оптимальным, т. к. в F-строке имеются отрицательные элементы.
Чтобы получить новый опорный план, более близкий к оптимальному плану, выполним симплексные преобразования первой симплексной таблицы. Наибольший по модулю отрицательный элемент F-строки указывает, что в новый базис следует ввести переменную x1.
Чтобы определить переменную, выводимую из базиса, составим симплексные отношения и выберем наименьшее из них:
min240010,5;8201;-=min533,33;820;-=533,33
Итак, из базиса исключаем переменную x3
Задать вопрос
на новый заказ в Автор24.
