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

Таблица 1

Исходная задача (2.1)–(2.5)		Двойственная задача (2.6)–(2.10)
число ограничений -m		число переменных -m
число переменных - n		число ограничений - n
константы в правых частях ограничений		коэффициенты целевой функции
коэффициенты целевой функции		константы в правых частях ограничений
max F		min T
j-ый столбец матрицы условий		j-ая строка матрицы условий
i-ая строка матрицы условий		i-ый столбец матрицы условий
j-ая неотрицательная переменная		j-ое ограничение неравенство типа ³
j-ая переменная, не имеющая ограничения в знаке		j-ое ограничение-равенство
i-ое ограничение неравенство типа £		i-ая неотрицательная переменная
i-ое ограничение - равенство		i-ая переменная, не ограниченная в знаке

3. ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ ТЕОРИИ ДВОЙСТВЕННОСТИ

Рассмотрим пару взаимно-двойственных задач

(3.1) (3.4)

(3.2) (3.5)

(3.3) (3.6)

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

Лемма 1. Двойственная задача к двойственной задаче линейного программирования (3.4)–(3.6) есть исходная задача ЛП (3.1)–(3.3).

Таким образом, прямая задача (3.1)–(3.3) является сопряженной к двойственной задаче (3.4)–(3.6). В связи с этим задачи (3.1)–(3.3) и (3.4)–(3.6) называют двойственной или взаимносопряженной парой.

Лемма 2. (основное неравенство теории двойственности)

Если и – произвольные планы (допустимые решения) задач (3.1)–(3.3) и (3.4)–(3.6) соответственно, то

(3.7)

то есть критерий задачи максимизации не превосходит критерия задачи минимизации.

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

Лемма 3. Если для некоторых планов и задач (3.1)–(3.3) и (3.4)–(3.6) соответственно выполняется равенство:

(3.8)

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

Лемма 3 устанавливает достаточность условия (3.8) для оптимальности допустимых решений двойственных задач. Условие (3.8) является также и необходимым условием оптимальности планов и .

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

Лемма 4. Если линейная форма одной из задач двойственной пары не ограничена на множестве своих планов, то другая задача не имеет ни одного плана.

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

Теорема 1. (первая теорема двойственности)

Если одна из задач ЛП двойственной пары (3.1)–(3.3) и (3.4)–(3.6) имеет оптимальное решение, то другая задача также разрешима. При этом для оптимальных планов и имеет место равенство

(3.9)

Первая теорема двойственности имеет следующий экономический смысл.

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

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

Теорема 2. Для разрешимости одной из задач двойственной пары (3.1)–(3.3) и (3.4)–(3.6) необходимо и достаточно, чтобы множество планов каждой из задач было не пусто.

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

а) обе задачи имеют планы

б) планы имеются только у одной задачи

в) для каждой задачи двойственной пары множество планов пусто.

Из теоремы 2 вытекает, что условия случая а) эквивалентны предположению о разрешимости обеих задач двойственной пары. Случай б) равносилен требованию неограниченности линейной формы одной из задач на множестве ее планов (лемма 4).

Теорема 3. (вторая теорема двойственности)

Для того, чтобы планы и задач ЛП двойственной пары (3.1)–(3.3) и (3.4)–(3.6) были оптимальными, необходимо и достаточно, чтобы эти планы удовлетворяли условиям дополняющей нежесткости

(3.10)

(3.11)

Условия (3.10) и (3.11) означают следующее:

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

а) еслиxj*> 0 для некоторогоj, то (3.12)

б) если , то xj*=0 (3.13)

в) если yi*> 0 для некоторогоi, то (3.14)

г) если , то yi*= 0 (3.15)

Соотношения (3.12)-(3.15) имеют следующий экономический смысл.

Оптимальный план характеризует эффективность отдельных технологических способов производства: б) если j-ая технология является "нерентабельной" (затраты в единицу времени превышают стоимость произведенного по этой технологии продукта), то она не используется в оптимальном плане (xj* = 0); а) если j-ый технологический способ используется в оптимальном плане (xj*> 0), то стоимость затраченных по этой технологии производственных факторов будет равна стоимости производственного продукта, т. е. j - ая технология будет "безотходной технологией".