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

Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой):

Прямая задача (ПЗ)

Двойственная задача (ДЗ)

ДЗ по отношению к прямой составляют согласно правилам:

1) ЦФ ПЗ задаётся на max, тогда ЦФ ДЗ – на min, и наоборот;

2) матрица , составленная из коэффициентов в

системе ограничений ПЗ, и аналогичная матрица в ДЗ получаются друг из друга транспонированием;

3) число переменных в ДЗ (т) равно числу соотношений (ограничений) в ПЗ, а число ограничений ДЗ (п) – числу переменных в ПЗ;

4) коэффициенты при неизвестных в ЦФ ДЗ – свободные члены (b_i), а правые части в ограничениях ДЗ (c_j) – коэффициенты при неизвестных в ЦФ ПЗ;

5) если переменная x_j ПЗ может принимать только положительные значения (x_j ³ 0), то j-е условие ПЗ – условие неравенства вида «³». Если i-е соотношение в ПЗ – неравенство, то i-я переменная ДЗ z_i ³ 0.

Если ПЗ имеет решение, то и ДЗ тоже имеет решение, причём max(min) L₁ = min(max)L₂. Поэтому достаточно для отыскания оптимума решить одну какую-либо из задач двойственной пары, обычно решают ту, которая проще.

Оптимальный план двойственной задачи позволяет оценить степень дефицитности ресурсов, потребляемых при выполнении оптимального плана исходной задачи.

Пример 2.4. Для производства изделий А, В, С используются три различных вида ресурсов. Каждый из видов ресурсов может быть использован в количестве соответственно не большем 180, 210, 244 ед. Известны затраты каждого из видов ресурсов на единицу продукции и цена единицы продукции каждого вида (табл.2.10).

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

Таблица 2.10

Вид ресурса	Норма расхода ресурса (ед. изм.) на единицу продукции
А	В	С
Цена продукции

 

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

Решение.

ПЗ

ДЗ

Решение ПЗ даёт оптимальный план производства изделий А, В, СС, а решение ДЗ – оптимальную систему оценок ресурсов, используемых для производства этих изделий:

Исходя из анализа оптимальных двойственных оценок можно сделать следующие выводы.

§ Ресурсы первого и третьего вида используются полностью. Полному использованию этих ресурсов соответствуют полученные оптимальные оценки , отличные от нуля, т.е. положительные двойственные оценки имеют ресурсы, полностью потребляемые при оптимальном плане производства. Значит, ресурс второго вида недоиспользуется (на 80 ед.). Таким образом, двойственные оценки определяют дефицитность используемых ресурсов.

§ Более того, величина двойственной оценки показывает, на сколько возрастает максимальное значение ЦФ ПЗ при увеличении количество соответствующего ресурса на 1 ед. Так, увеличение количества ресурса первого вида на 1 ед. приведёт к тому, что появится возможность найти новый оптимальный план производства изделий, при которой общий доход возрастает на 5,75 д.е. и станет равным 1340+5,75=1345,75 д.е. Анализ полученных оптимальных значений новой ПЗ показывает, что это увеличение общего дохода достигается за счёт увеличения производства изделий В на 0,625 ед. и сокращения выпуска изделий С на 0,25 ед. Вследствие этого использование ресурса второго вида уменьшается на 0,125 ед.

Точно также увеличение на 1 ед. количества ресурсов третьего вида позволит перейти к новому оптимальному плану производства, при котором доход возрастает на 1,25 д.е. и составит 1340+1,25=1341,25 д.е., что достигается за счёт увеличения выпуска изделий С на 0,25 ед. и уменьшения выпуска В на 0,25 ед., причём объём используемого ресурса второго вида возрастает на 0,625 ед.

§ При подстановке оптимальных двойственных оценок в систему ограничений ДЗ получаем:

4 ´ 5,75 + 1,25 > 10;

2 ´ 5,75 + 1,25 = 14;

5,75 + 5 ´ 1,25 = 12.

Первое ограничение выполняется как строгое неравенство, т.е. двойственная оценка всех ресурсов на производство единицы изделия А выше цены этого изделия и, следовательно, выпускать его невыгодно. Его производство и не предусмотрено оптимальным планом ПЗ.

При одновременном измерении ресурсов всех видов на величину Db_i (i=1...m) можно оценить их суммарное влияние на значение ЦФ (при условии неизменности двойственных оценок в новой ДЗ относительно оценок в первоначальной ДЗ):

,

где Db_i – величина возможного (при сохранении оптимального плана первоначальной ДЗ) изменения (увеличения или уменьшения) ресурса i-го вида.

3. Методические указания по выполнению лабораторной работы

Перед выполнением лабораторной работы необходимо ознакомиться с её целью, основными теоретическими положениями, особенностями использования пакета прикладных программ (ППП) QSB и табличного процессора (ТП) Excel 7.0 при решении задач линейного программирования.

Каждый студент получает у преподавателя индивидуальное задание на выполнение лабораторной работы.

В процессе лабораторной работы необходимо:

1) на основе содержательных постановок задач линейного программирования разработать математические модели прямой и двойственной задачи линейного программирования;

2) провести (при необходимости) модификацию исходной задачи линейного программирования (сокращение числа переменных) и решить её графическим методом;

3) подготовить исходные данные для решения задачи линейного программирования с использованием ППП QSB и ТП Excel 7.0;

4) решить задачу линейного программирования при фиксированном варианте задания исходных данных;

5) провести исследование влияния изменения вариантов задания исходных данных на результаты решения задачи линейного программирования. При этом проводится изменение коэффициентов целевой функции, коэффициентов в системе ограничений, изменение числа ограничений и переменных.

На основе проведённых исследований определяются границы устойчивости полученных решений задачи линейного программирования.

Результаты расчётов и исследований выдаются на печать в виде соответствующих таблиц, номограмм и графиков. Отчётный материал предоставляется преподавателю и результаты выполненной работы защищаются.

4. форма отчётности по выполненной лабораторной работе

Отчёт должен содержать:

- титульный лист;

- содержательную и формальную постановку задачи линейного программирования (ЛП);

- формальную постановку двойственной задачи ЛП;

- графическое решение основной (прямой) задачи ЛП;

- распечатки результатов решения и исследования задач ЛП с использованием ППП QSB и ТП Excel 7.0;

- выводы по результатам решения и исследованию задач ЛП.

Отчёт о лабораторной работе представляется к моменту её защиты.