Решение задачи ЛП симплекс-методом (опорный конспект в виде разобранного примера)

Пример решения задачи ЛП симплекс-методом

Предприятие выпускает три вида изделий (N1, N2, N3), используя три вида ресурсов (Р1, Р2, Р3). Запасы ресурсов (З) ограничены. Прибыль от реализации (П) единицы изделия и нормы расхода ресурсов представлены в таблице. Определить ассортимент и объемы выпуска продукции, получаемую прибыль, величину остатков. Найти решение задачи симплексным методом с представлением всех симплексных таблиц и проанализировать полученные результаты.

N1
N2
N3
З

Р1
1
3
4
42

Р2
4
2
2
54

Р3
3
2
2
80

П
2
1
3


Решение: Запишем математическую модель задачи.
Определим вектор 13 EMBED Equation.3 1415, который удовлетворяет условиям




и обеспечивает максимальное значение целевой функции


Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных x4, x5, x6:




Полагая, что свободные переменные x1=0, x2=0, x3=0, получим первый опорный план 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415, в котором базисные переменные
x4= , x5= , x6= .
Следовательно, изделия не производятся, доход равен нулю, а ресурсы не используются. Полученный первый опорный план запишем в симплексную таблицу.


План
СЗ
БП
ЗБП
Значение коэффициентов при
13 EMBED Equation.3 1415





X1
X2
X3
X4
X5
X6


I



































Индексная строка
13 EMBED Equation.3 1415=









Первый опорный план_________________, так как в индексной строке ______________отрицательные коэффициенты:
За ведущий столбец выберем столбец, соответствующий переменной____, так как, сравнивая по модулю, имеем: _________________________
Вычислим значения 13 EMBED Equation.3 1415 по строкам как частное от деления 13 EMBED Equation.3 1415 и из них выберем наименьшее:
Следовательно, ведущая строка- _______.
Разрешающий элемент равен РЭ=______ и находится на пересечении ведущего столбца и ведущей строки и выделен в таблице.
Формируем следующую часть симплексной таблице. Вместо переменной ___ в план II войдет переменная ____. Строка, соответствующая переменной ____в плане II, получена в результате деления всех элементов строки ____плана I на разрешающий элемент РЭ=____. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столба _____ плана II записываем нули.
Таким образом, в новом плане II заполнены строки ___и столбец ____. Все остальные элементы нового плана II, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=2.
13 EMBED Equation.3 1415
Все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам, равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны 0. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную.
Построим вторую симплекс-таблицу:

План
СЗ
БП
ЗБП
Значение коэффициентов при
13 EMBED Equation.3 1415





X1
X2
X3
X4
X5
X6


II



































Индексная строка
13 EMBED Equation.3 1415=









Получаем план II, который является ________________________, так как ____________________________________________________________________________

План
СЗ
БП
ЗБП
Значение коэффициентов при
13 EMBED Equation.3 1415





X1
X2
X3
X4
X5
X6


III



































Индексная строка
13 EMBED Equation.3 1415=








Оптимальный план можно записать так:
13 EMBED Equation.3 1415
Вывод: ___________________________________________________________________________
__________________________________________________________________________________
________________________________________________________________________________________________________________________________________________________________________