Основы исследования операций (стр. 5 )

Оптимальные оценки мер важности производственных факторов характеризуют "дефицитность" их запасов: в) если мера важности i-ого фактора положительна (yi*> 0), то весь его запас полностью используется в оптимальном плане производства, т. е. этот фактор является "дефицитным". г) Если i-ый фактор в процессе производства используется не полностью, т. е. этот фактор является "недефицитным", то мера его важности имеет нулевую оценку (yi*= 0).

Теорема 4 (третья теорема двойственности, теорема об оценках).

Значения переменных yi* в оптимальном решении двойственной задачи (3.4)–(3.6) представляют собой оценки влияния свободных членов ограничений системы (3.2) на оптимальное значение целевой функции (3.1) исходной задачи, т. е.

(3.16)

Предполагается, что задача (3.1)–(3.3) невырождена. Теорема об оценках используется для анализа решения задачи ЛП на чувствительность к изменению свободных членов ограничений. Если правые части ограничений (3.2) подвергать некоторым изменениям, то значение целевой функции будет также меняться. Если при изменении bi вектор оценок остается неизменным, справедливо соотношение Вопрос об устойчивости вектора оценок рассмотрен в работах [2, 4, 12].

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

4. ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ ВЗАИМОСВЯЗИ ОПТИМАЛЬНЫХ РЕШЕНИЙ ЗАДАЧ ДВОЙСТВЕННОЙ ПАРЫ

4.1. Определение оптимального решения одной из задач двойственной пары по оптимальному решению другой задачи

Пример 1. По известному оптимальному решению = (11/5, 19/5, 0) задачи ЛП (4.1)–(4.3) определить оптимальное решение двойственной задачи.

(4.1)

(4.2)

(4.3)

Построим к задаче (4.1)–(4.3) двойственную.

Так как целевая функция (4.1) максимизируется, все ограничения-неравенства задачи должны быть типа £. Умножим первое ограничение на (-1): Воспользуемся правилами построения двойственных задач, приведенными в разделе 2.

(4.4)

(4.5)

(4.6)

Задача (4.4)–(4.6) двойственная к задаче (4.1)–(4.3).

Для нахождения решения задачи (4.4)–(4.6) используем 2-ю теорему двойственности. Подставим = (11/5, 19/5, 0) в ограничения (4.2) исходной задачи:

Видим, что второе ограничение исходной задачи выполняется как строгое неравенство. Тогда согласно условиям (3.15) второй теоремы двойственности соответствующая этому ограничению переменная y2 равна нулю.

Так как в оптимальном решении исходной задачи = (11/5,19/5,0) первые две компоненты положительны, то в соответствии с условиями (3.12) первые два ограничения двойственной задачи оптимальным решением должны обращаться в равенства:

Так как y2 = 0, то для определения оптимального решения двойственной задачи имеем следующую систему уравнений

Решением этой системы являются y1 = 0, y3= 1. Тогда оптимальным решением двойственной задачи является вектор = (0, 0, 1). Проконтролировать правильность полученного результата можно по 1 теореме двойственности. Для этого нужно убедиться, что решения = (11/5, 19/5, 0) и = (0, 0, 1) являются допустимыми решениями (планами) своих задач, а значения критериев совпадают .

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

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

2.  Записать в виде равенств те ограничения двойственной задачи, которым соответствуют ненулевые компоненты вектора решений исходной задачи.

3.  Полученные ограничения-равенства вместе с линейными уравнениями, содержащимися в условиях двойственной задачи составляют систему линейных уравнений для нахождения оптимального решения двойственной задачи.

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

Пример 2. Решить задачу.

(4.7)

(4.8)

(4.9)

Построим двойственную задачу

(4.10)

(4.11)

y2 не ограничена в знаке (4.12)

Задача (4.10)–(4.12) допускает графическое решение, представленное на рис.1.

Оптимальное решение находится в точке =(1, -1).

Для определения оптимального решения исходной задачи (4.7)–(4.9) используем 2-ю теорему двойственности:

1) Подставим =(1, -1) в ограничения (4.11)

Так как первое и четвертое ограничения обращаются в строгие неравенства, переменные x1 и x4 в оптимальном решении задачи (4.7)–(4.9) обращаются в нуль, x1 = 0, x4= 0.

2) Так как обе переменные в оптимальном решении двойственной задачи ненулевые, то ограничения исходной задачи на оптимальном решении обращаются в равенство:

Решаем эту систему при условии, что x1= x4= 0.

Находим, что x2= 1/2, x3 = 5/2.

Тогда = (0, 1/2, 5/2, 0) - оптимальное решение исходной задачи.

4.2. Двойственный признак оптимальности решения задачи линейного программирования

При решении задач линейного программирования важно знать способы, позволяющие проверять планы задачи на оптимальность, то есть уметь ответить на вопрос, является ли данный план оптимальным или нет.

Мы уже знаем один признак оптимальности – это условие неотрицательности (для задачи максимизации) оценок свободных переменных в симплекс-таблице опорного решения. Этот признак используется в симплекс-методе в процессе поиска оптимального решения. Если же не требуется определить оптимальное решение, а только выяснить, является уже данный план оптимальным, использование этого признака неэффективно, так как требует больших вычислительных затрат на построение симплекс-таблицы и расчет оценок. Кроме того, он позволяет определить оптимальность только опорного плана (угловой точки множества допустимых решений) и не может быть применен к произвольному допустимому решению.

Определить оптимальность произвольного допустимого решения (плана) позволяет следующее следствие второй теоремы двойственности:

Теорема 5 (Двойственный признак оптимальности).

Для того, чтобы допустимое решение задачи линейного программирования (3.1)–(3.3) было оптимальным, необходимо и достаточно, чтобы среди решений системы уравнений

для xj¹0

yi =0, для (4.13)

существовало хотя бы одно допустимое решение двойственной задачи (3.4)–(3.6).

Признак справедлив не только для задач линейного программирования в симметричной форме, но и для задач произвольного вида.

Пример 3.

Определить, является ли вектор оптимальным решением следующей задачи

(4.14)