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

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

Предприятие выпускает три вида изделий (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

Решение: Запишем математическую модель задачи.

Определим вектор , который удовлетворяет условиям

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

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных x₄, x₅, x₆:

Полагая, что свободные переменные x₁=0, x₂=0, x₃=0, получим первый опорный план  , в котором базисные переменные

x₄=      , x₅=       , x₆=           .

Следовательно, изделия не производятся, доход равен нулю, а ресурсы не используются. Полученный первый опорный план запишем в симплексную таблицу.

План

СЗ

БП

ЗБП

Значение коэффициентов при

X1

X2

X3

X4

X5

X6

I

Индексная строка

=

Первый опорный план_________________, так как в индексной строке ______________отрицательные коэффициенты:

За ведущий столбец выберем столбец, соответствующий переменной____, так как, сравнивая по модулю, имеем: _________________________

Вычислим значения  по строкам как частное от деления  и из них выберем наименьшее:

Следовательно, ведущая строка- _______.

Разрешающий элемент равен РЭ=______ и находится на пересечении ведущего столбца и ведущей строки и выделен в таблице.

Формируем следующую часть симплексной таблице. Вместо переменной ___  в план II войдет переменная ____. Строка, соответствующая переменной ____в плане II, получена в результате деления всех элементов строки ____плана I на разрешающий элемент РЭ=____. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столба _____ плана II записываем нули.

Таким образом, в новом плане II заполнены строки ___и столбец ____. Все остальные элементы нового плана II, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=2.

                                 

Все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам, равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны 0. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную.

Построим вторую симплекс-таблицу:

План

СЗ

БП

ЗБП

Значение коэффициентов при

X1

X2

X3

X4

X5

X6

II

Индексная строка

=

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

План

СЗ

БП

ЗБП

Значение коэффициентов при

X1

X2

X3

X4

X5

X6

III

Индексная строка

=

Оптимальный план можно записать так:

Вывод: ___________________________________________________________________________

__________________________________________________________________________________

________________________________________________________________________________________________________________________________________________________________________