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

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

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

в условиях системы из m линейных ограничений:

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

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

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

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

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

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

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

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

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

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

Решение

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

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

2. Используя формулировку прямой модели, построим двойственную модель: Минимизировать ст. в неделю)

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

Продукт ст. за единицу;

Продукт ст. за единицу;

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

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

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

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

Оптимальным решением задачи является точка А, лежащая на пересечении линии ограничения на сырье 1 и оси Чтобы получать максимальную прибыль, следует производить только продукт в количестве 3 кг. При этом будет использоваться полностью, — нет. Максимальная прибыль составит: ст. в неделю. Ниже приводится графическое решение двойственной задачи (рис. 12.29).

(кликните для просмотра скана)

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

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

следовательно, -

Минимальная стоимость ресурсов в двойственной задаче имеет вид:

Это значение совпадает со значением целевой функции прямой задачи.

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