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

Если через aijобозначить норму расходования в единицу времени i-ого производственного фактора при использовании j-го технологического способа производства продукта, тогда общее использование i-го производственного фактора в сфере производства (левая часть неравенства (1.2)) не должно превышать его запаса (величины bi).

Таким образом, задача (1.1)–(1.3) является линейной математической моделью проблемы составления оптимального плана (x1,x2,...,xn) использования различных технологических способов, который позволяет при заданных запасах производственных факторов (b1,b2,...,bm) получить максимальное количество выпускаемого однородного продукта.

Допустим теперь, что необходимо, оставаясь в рамках рассматриваемого производства, оценить каждый из используемых факторов. В качестве меры значимости единицы i-го производственного фактора введем оценку yi³ 0, . yi=0 означает, что i-ый фактор имеется в избытке и не влияет на выпуск однородного продукта. Чем более значимым (дефицитным) является i-ый фактор для данного производства, тем больше будет численная величина его оценки. Следует иметь в виду, что оценки yi являются относительными. Изменение условий производства (увеличение или уменьшение запасов используемых факторов, норм расхода факторов, появление новых технологических способов и пр.) приводит к необходимости переоценки важности этих факторов для производства. Кроме того одни и те же производственные факторы для разных предприятий представляют различную ценность.

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

Проанализируем j-ый технологический способ с точки зрения расходов и доходов в единицу времени.

Доход от j-го производства (j-ой технологии) в единицу времени (в стоимостном выражении) равен произведению стоимости единицы однородного продукта на выпуск этого продукта за единицу времени.

(1.4)

Общий расход (в единицах стоимости выпускаемого продукта) при использовании j-го способа производства ( j-ой технологии) в единицу времени равен стоимости всех затраченных при этом производственных факторов:

(1.5)

При правильно выбранных оценках факторов производства оценка суммарных расходов (1.5) не может быть меньше оценки полученной продукции (1.1), ибо в противном случае часть продукции была бы создана из "ничего".

Следовательно, вектор оценок должен удовлетворять условиям

(1.6)

Чем меньше непроизводительные затраты по j-ой технологии, тем меньше левая часть неравенства (1.6) отличается от параметра сj. При "безотходной технологии", когда непроизводительные затраты полностью отсутствуют, стоимость общих затрат по j-ой технологии равняется стоимости произведенного по ней продукта:

(1.7)

В рассматриваемой экономической интерпретации задачи (1.1)–(1.3) параметры aij являются неотрицательными числами, поэтому всегда можно подобрать достаточно большие числа y1,y2,...ym, так, чтобы система неравенств (1.6) удовлетворялась. Однако, необоснованное завышение оценок меры важности производственных факторов может привести к тому, что они не будут отражать особенности рассматриваемого производственного процесса. В связи с этим возникает необходимость в условии, не допускающем необоснованное завышение оценок факторов производства. Потребуем, чтобы совокупность оценок {yi} соответствовала минимальной суммарной оценке запасов по всем производственным факторам

(1.8)

Таким образом, задача выбора оценок меры важности факторов производства свелась к следующей задаче (1.9)–(1.11) линейного программирования:

(1.9)

(1.10)

(1.11)

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

2.2. Методика построения двойственных задач

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

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

Прямая задача ЛП в общей форме записывается следующим образом:

(2.1)

(2.2)

(2.3)

(2.4)

xjне ограничена в знаке, (2.5)

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

1)  все ограничения - неравенства исходной модели должны быть одного типа (все типа £ , или все типа ³);

2)  если исходная модель имеет ограничения-неравенства типа £, то целевая функция этой задачи должна максимизироваться и наоборот, если ограничения-неравенства типа ³, целевая функция должна минимизироваться.

Несоблюдение названных условий может привести к нарушению условий двойственности.

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

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

2)  каждой переменной прямой задачи соответствует ограничение двойственной задачи (причем, неотрицательной переменной соответствует ограничение типа неравенства, а переменной, не ограниченной в знаке – ограничение-равенство);

3)  матрицы системы ограничений прямой и двойственной задач являются транспонированными по отношению друг к другу;

4)  свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи, а коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;

5)  максимизации целевой функции в исходной задаче соответствует минимизация целевой функции в двойственной задаче;

6)  задача максимизации имеет ограничения-неравенства типа £ , задача минимизации - типа ³.

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

Двойственная задача имеет k ограничений типа неравенств и (n-k) ограничений-равенств .

Сформулируем двойственную задачу:

(2.6)

(2.7)

(2.8)

(2.9)

yi не ограничена в знаке, (2.10)

Пример 1

x5 – не ограничена в знаке.

Преобразуем модель исходной задачи:

1)  Заменим второе ограничение исходной задачи (неравенство типа ³) неравенством типа £.

2)  Заменим минимизацию целевой функции максимизацией.

Прямая задача x5- не ограничена в знаке
Двойственная задача y3 – не ограничена в знаке
Пример 2 Прямая задача
Двойственная задача y1 не ограничена в знаке y2 не ограничена в знаке

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