Для производства продуктов X и У в неделю

(в условиях снижения запаса ресурса RM1 на 2 кг)

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

Остаточные переменные, соответствующие ограничениям 1 и 3, принимают нулевые значения. Это значит, что данные ограничения являются лимитирующими. Макси­мальное значение прибыли за неделю равно 28,33 ф. ст. На рис. 12.27 представлено графическое решение данного варианта задачи.

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

ДВОЙСТВЕННАЯ МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Максимизировать

Z = с,х, + с₂х₂ +... + с„х„ в условиях системы из m линейных ограничений:

а_пх, + a_t2x₂ + а₁₃х₃ +... +а_1пх_п £ Ь,;

^а21^х1 ^{+ а}22^х2 ^{+ а}23*3 ⁺ — ^+а2п^хп ^S ^

а₃₁х, + аз2Х₂ + 833X3 +... + а_3пх„ £ Ь_3;

^amlXi ^{+ а}ш2^х2 ^{+ а}тЗ*3 ⁺ ••• + ЭтА * ^Ьп.=

X, SO.

Сформулированная выше задача линейного программирования является чей максимизации, а все ее ограничения имеют знак "£". К этому виду м

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

привести любую модель линейного программирования, а затем построить двойст­венную к ней, как это будет показано ниже. Двойственная модель имеет следую­щий вид:

Минимизировать

G = b,y, +b₂y₂ +... + b_my_m в условиях системы из п линейных ограничений:

^а11У1 ⁺ а₂,У₂ ^{+ а}31Уз ⁺ - ^+ат1Ут * ^с1! ^а12У1 ^{+ а}22У2 ^{+ а}32Уз ⁺ - +а,п2У_т * ^с2;.»13У| ^{+ И}23У2 ^{+ а}ЗЗУз ⁺ •• + атЗУт * ^с3!

• • • • •

^а1пУ| ^{+ а}2пУ2 ^{+ а}ЗпУз ⁺ - + ^пУт * ^сп!

у, ^ О

В этой задаче т двойственных переменных у, каждая из которых соответству­ет одному из m ограничений прямой задачи, и п ограничений, каждое из которых связано с одной из п переменных х прямой задачи. Коэффициенты целевой функции прямой задачи с и значения правой части ограничений Ь в двойственной задаче меняются местами. Строки коэффициентов левой части системы ограниче­ний прямой модели становятся столбцами в двойственной, а столбцы — строками. Двойственные переменные у являются теневыми ценами ресурсов в прямой задаче, и наоборот. В данном случае целевая функция двойственной задачи минимизиру­ется, а целевая функция прямой задачи — максимизируется. Если ограничения прямой задачи имеют знак "5", то ограничения двойственной задачи записываются со знаком "£".

□ Пример 12.10. Некоторая фирма выпускает два продукта R и Q, каждый из которых требует двух видов сырья RM1 и RM2. Для выпуска 1 кг продукта R необходимо 2 кг сырья RM1 и 3,5 кг сырья RM2. Производство 1 кг продукта Q требует 3 кг RM1 и 1,5 кг RM2. В распоряжении фирмы имеются 10 кг RM1 и 12 кг RM2 в неделю, трудовые ресурсы и производственные мощности - в неограниченном количестве, кроме того, фирма может реализовать всю произведенную продукцию. Прибыль от выпуска единицы продукта R составляет 5 ф. ст., а от выпуска единицы продукта Q - 8 ф. ст.

1. Для изложенной проблемы сформулируем задачу линейного програмирования, в которой максимизируется прибыль.

2. Построим двойственную модель линейного программирования.

3. Объясним взаимосвязи между моделями, построенными в п.1 и 2.

4. Для обеих моделей нужно найти оптимальное решение графическим методом.

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

Решение

1. Производится Xj кг продукта R и Хт кг продукта Q в неделю. Максимизируется
полученная за неделю прибыль Р (ф. ст.), где

Р = 5 Х(+ 8 Х2 (ф- ст. в неделю) в условиях следующей системы ограничений:

RM1: 2 X] + 3 Х2 й 10 кг в неделю; RM2: 3,5 x_t + 1,5 Х2 й 12 кг в неделю; Х[, х₂ £ 0.

2. Используя формулировку прямой модели, построим двойственную модель:
Минимизировать G = 10 у₍ + 12 у₂ (ф. ст. в неделю)

в условиях следующей системы ограничений:

Продукт R: 2 У| + 3,5 у₂ > 5 ф. ст. за единицу; Продукт Q: 3 y_t + 1,5 yj £ 8 ф. ст. за единицу; У1.У2 *°-

3. Прямая модель. Переменные модели — это количество каждого продукта,
которое необходимо производить каждую неделю. Целевая функция задачи —
это общая прибыль, получаемая в неделю от производства продуктов R и Q.
Кхкдое ограничение соответствует однолгу виду сырья. Левая часть каждого
ограничения представляет собой общее количество сырья одного вида, требуе­
мое для производства обоих продуктов. Правая часть ограничений содержит
общее количество сырья каждого вида, которое фирма может использовать в
течение недели.

Двойственная модель. Переменные модели — это теневые цены ресурсов для прямой модели, т.е. величины, на которые увеличилось бы значение целевой функции при росте имеющегося запаса сырья соответствующего вида на единицу. Теневые цены характеризуют стоимость единицы сырья каждого вида. Целевая функция задачи — это общая еженедельная стоимость всех видов сырья, используемых при производстве R и Q. Каждое ограничение связано с одним из продуктов. В левой части каждого ограничения дана общая стоимость всех видов сырья, используемых при выпуске 1 кг соответствующего продукта; в правой - прибыль от выпуска единицы соответствующего продукта. Обратимся вновь к формулировке двойственной мо­дели и попытаемся дать интерпретацию отдельным ее компонентам (см. стр. 447).

Из кхкдого ограничения следует, что общая стоимость сырья, используемого для производства данного продукта, должна быть больше либо равна прибыли от производства единицы этого продукта. Из решения прямой или двойственной модели можно получить решение обратной модели.

4. Графическое решение прямой задачи приведено на рис. 12.28.

Оптимальным решением задачи является точка А, лежащая на пересечении линии ограничения на сырье 1 и оси Q. Чтобы получать максимальную прибыль,

следует производить только продукт Q в количестве 3 г кг. При этом RM1 будет

использоваться полностью, a RM2 — нет. Максимальная прибыль составит:

3 - х 8 = 26,67 ф. ст. в неделю. Ниже приводится графическое решение двойственной

задачи (рис. 12.29).

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

RM2 3,5к, + 1,5х, - 12 Точка получения максимальной прибыли RM1 2х, + 3х, - 10

5 Выпуск продукта R, кг в неделю

Линия уровня У, ' прибыли /I

u&///sfy//Jf//s%

Выпуск продукта Q, х, кг в неделе

Рис. 12.28. Прямая модель

Допустимое множество

Линия уровня стоимости 10у, + 12у,-36 Точка минимального значения стоимости ресурсов ' L

Wj 3 Стоимость единицы RM1

Стоимость единицы RM2

Продукт Q Зу. + 1,5у, - 8

Рис. 12.29. Двойственная модель