Симплекс-метод решения задачи линейного программирования с множеством переменных

Если задача линейного программирования содержит более двух переменных, то ее решение требует применения некоторого алгебраического метода. Принцип, лежащий в основе решения задачи с множеством переменных, достаточно прост. Предполагается, что оптимальному решению соответствует одна из крайних точек допустимого множества. Следовательно, необходимо провести оценку значений целевой функции во всех крайних точках допустимого множества и выбрать ту из них, в которой достигается оптимальное значение целевой функции. Нами используются методы матричной алгебры и такой алгоритм перехода от одной крайней точки допустимого множества к другой, при котором переход осуществляется только в случае, когда значение целевой функции улучшается. Если окажется, что некоторое базисное решение улучшить уже нельзя, то оно является оптимальным планом задачи. Этот алгоритм получил название симплекс-метода.

В обычном симплекс-методе принимается предпосылка о максимизации целевой функции задачи линейного программирования в условиях системы ограничений со знаком " ". Это означает, что при реализации данного алгоритма в качестве начальной крайней точки может быть выбрано начало координат. Поиск оптимального решения всегда начинается со значения целевой функции, равного нулю.

Симплекс-метод можно применять также и в решении задач минимизации, и в решении задач, система ограничений которых содержит ограничения со знаком " " или уравнения. Эта процедура предусматривает введение в задачу искусственных, а также избыточных и остаточных переменных. Мы не будем подробно останавливаться на подобных усложнениях, поскольку обычно задачи линейного программирования решаются с помощью пакетов прикладных программ, в которых указанные переменные вводятся в модель автоматически.

Базовую модель, с которой мы будем работать в дальнейшем, формально? можно представить следующим образом:

Максимизировать Z = с₁х₁ + с₂x₂ +... + с_nх_n.

Здесь с_i - константы. Данная функция максимизируется в условиях системы m линейных ограничений:

a₁₁х₁ + а₁₂x₂ + а₁₃x₃ + … + a_1nx_n b₁

a₂₁х₁ + а₂₂x₂ + а₂₃x₃ + … + a_2nx_n b₂

a₃₁х₁ + а₃₂x₂ + а₃₃x₃ + … + a_3nx_n b₃

....

a_m1х₁ + а_m2x₂ + а_m3x₃ + … + a_mnx_n b_m, x_i 0

Данная система содержит n переменных и m ограничений. Первая цифра двойных индексов коэффициентов в левой части системы ограничений соответствует номеру ограничения, вторая — номеру переменной. Например, a32 принадлежит ограничению 3 и является коэффициентом при переменной х₂. Проиллюстрируем применение симплекс-метода на примере простой задачи с двумя переменными, решение которой было получено нами ранее с помощью графического метода. Этот прием позволит нам сравнить решение, полученное графическим и алгебраическим методами.

Пример: Некоторая фирма производит два вида продуктов Х и Y в условиях ограничений на три вида сырья: RM1, RM2 и RM3. Целью фирмы является выбор такого ассортиментного набора, при котором достигается максимум прибыли в неделю. Задача линейного программирования имеет вид:

1. Выпускается х единиц продукта Х в неделю и у единиц продукта Y в неделю.

2. Максимизируется еженедельная прибыль Р (ф. ст.), где Р = 2 х + у.

3. Максимизация осуществляется в условиях ограничений:

RM1: 3 х 27 кг в неделю

RM2: 2 у 30 кг в неделю

RM3: х + у 20 кг в неделю

х, у 0.

4. Найти оптимальный ассортиментный набор и максимальную прибыль за неделю. Определить свободный запас каждого ресурса.

Решение

Графический метод. В каждое ограничение модели вводятся остаточные переменные si Максимизировать: Р = 2 х + у (ф. ст. в неделю) при ограничениях:

RM1: 3 х + s₁ = 27 кг в неделю;

RM2: 2 у + s₂ = 30 кг в неделю;

RM3: х + у + s₃ = 20 кг в неделю;

х, у, s 0.

Изобразим систему ограничений графически (см. рис. 3.1.)

Рис. 3.1. Задача линейного программирования для объемов выпуска продуктов X и Y в неделю

Точка с координатами х = 5, у = 5 принадлежит допустимому множеству.

Еженедельная прибыль в этой точке составит: Р=2*5+5=15 ф.ст.в неделю.

В качестве типичной линии уровня прибыли выберем прямую: 15 = 2 х + у (ф. ст. в неделю).

Точка с координатами х = 0, у = 15 также принадлежит этой прямой. Линия уровня изображена на приведенном выше графике пунктиром. Если осуществлять перемещение линии уровня параллельно ее начальному положению (отмеченному пунктиром), то легко можно убедиться, что оптимум находится в крайней точке А. Эта точка лежит на пересечении линий ограничений RM1 и RM3. Решение системы этих уравнений дает следующие результаты:

3 х = 27, следовательно, х = 9.

Подставив это значение во второе уравнение системы, получим: х + у = 20, следовательно, у = 11.

Оптимальным ассортиментным набором является производство 9 единиц продукта Х и 11 единиц продукта Y в неделю. Таким образом, максимальная прибыль, получаемая за неделю, составит:

Р _max = 2 * 9 + 11 = 29 ф. ст. в неделю.

Сырье типа 1 и 3 используется полностью, однако существует свободный запас сырья типа 2, т.е. 2 х 11 +s2 =30, следовательно, s= 8 кг в неделю.