Программирования с множеством переменных

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

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

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

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

Максимизировать Z = с,х, + с^ж.₂ +... + c_nx_n.

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

а„х, + а₁₂х₂ + а₁₃х₃ + ••• + a_1n^xn * ^Ь1

^а21*1 + «22*2 ⁺ «23^х3 ⁺ •" + ^а2п^хп * ^Ь2

^а31*1 ⁺ ^а32^х2 ⁺ ^а33^х3 ⁺ - ^+a3o^xn ^S ^Ь3
• • •

Гл. 12. Линейное программирование 431

«ЦтИ*! + a_m2x₂ + а^хз +... + а^х,, «; b_m

х,£0

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

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

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

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

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

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

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

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

х, у;>0.

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

Решение Графический метод. В каждое ограничение модели вводятся остаточные переменные s,. Максимизировать:

Р = 2 х + у (ф. ст. в неделю)

при ограничениях:

RM1 RM2 RM3

3 х + S| = 27 кг в неделю; 2 у + s₂ ^ш 30 кг в неделю; ⁺ у ⁺ S3 = 20 кг в неделю; х, у, s £ 0.

Изобразим систему ограничений графически (см. рис. 12.23) Точка с координатами х = 5, у = 5 принадлежит допустимому множеству. Еженедельная прибыль в этой точке составит:

Р = 2х5 + 5=15ф. ст. в неделю.

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

Ч. 4. Моделирование в бизнесе