Материал: Учебное пособие Немирко Манило

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

при условиях

Λ′Pj ≥ λ′+1, j LA, Λ′Pj ≤ −λ′+1, j LB,

определяя затем величину θ из условия (1.31), а искомые коэффициенты – из (1.32). Правило разделения может быть сформулировано и непосредственно

по оптимальным значениям Λ′, λ′, λ′, а значение θ полезно только для установления меры «разделимости» или «неразделимости».

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

Известно, что каждой задаче линейного программирования можно определенным образом сопоставить другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной (прямой) задаче [13]. Дадим определение двойственной задачи по отноше-

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

при условиях

26

yi ≥ 0 (i =1,k, k ≤ m)

называется двойственной по отношению к задаче (1.34), (1.35). Двойственная задача составляется согласно следующим правилам [13]:

1. Если целевая функция F исходной задачи максимизируется, то целе-

вая функция F* двойственной задачи минимизируется. 2. Матрица

составленная из коэффициентов при неизвестных в системе ограничений (1.35) исходной задачи, и аналогичная матрица

в двойственной задаче (1.37) связаны операцией транспонирования.

27

3.Число переменных m в двойственной задаче равно числу ограничений в системе (1.35) исходной задачи, а число ограничений n в системе (1.37) – числу переменных в исходной задаче.

4.Коэффициентами при неизвестных в целевой функции F* двойственной задачи становятся свободные члены системы (1.35) исходной задачи, а в правой части каждого формируемого ограничения стоят коэффициенты при этой переменной в выражении целевой функции F исходной задачи.

5.Если переменная x j исходной задачи может принимать лишь положи-

тельные значения, то j -е условие в системе (1.37) двойственной задачи является неравенством. Если же переменная x j может принимать как положи-

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

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

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

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

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

28

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

Пример 1.3. Для задачи, состоящей в определении максимального значения функции F = 2x1 +7x2 при условиях

−2x1 +3x2 ≤14;

x1 + x2 ≤8,

где x1, x2 ≥ 0 , составить двойственную задачу и найти решение обеих задач. Решение. Двойственной задачей по отношению к исходной является задача, состоящая в определении минимального значения функции F* =14 y1 +

+8y2 при условиях

−2y1 + y2 ≥ 2;3y1 + y2 ≥ 7,

где y1, y2 ≥ 0 .

Как в исходной, так и в двойственной задаче число неизвестных равно двум. Следовательно, их решение можно найти, используя геометрическую интерпретацию задачи линейного программирования (рис. 1.6 и 1.7).

Как видно из рис. 1.6, максимальное значение целевая функцияF исходной задачи принимает в точке A. Следовательно, x* = (2, 6) является оптимальным

29

–2

Рис. 1.7

решением, при котором Fmax = 46 . Минимальное значение целевая функция

F* двойственной задачи принимает в точке B (рис. 1.7). Значит, y* = (1, 4) является оптимальным решением двойственной задачи. Значения целевой функции исходной и двойственной задач в этих точках равны между собой.

30