Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

2.4.1. Понятие двойственности в линейном программировании

С каждой задачей линейного программирования

max f;

Ax ≤ b;

x ≥ 0

связана другая линейная задача, называемая двойственной

min z = yb;

yA ≥ c;

y ≥ 0.

Первоначальная задача называется исходной. Для понятия сути этой связи рассмотрим задачу использования некоторых ресурсов b = (b1, b2, …, b3) для производства n видов продукций [25]. Для производства единицы j-й продукции стоимостью cj расходуется aij единиц i-го ресурса. Необходимо определить какое количество каждого вида продукции необходимо производить, чтобы получить максимальную суммарную стоимость всей продукции. Следовательно, исходная задача линейного программирования, в скалярной форме записи, будет иметь вид

max f = c1x1 + c2x2 + … + cnxn;

a11x1 + a12x2 + … + a1nxn ≥ b1;

…………………………............;

am1x1 + am2y2 + … + amnym ≥ bm;

xj ≥ 0, j = 1, …, m.

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

min z = b1y1 + b2y2 + … + bmym;

a11y1 + a21y2 + … + am1ym ≥ c1;

………………………….............;

a1ny1 + a2ny2 + … + amnym ≥ cn;

yj ≥ 0, i = 1, …, m.

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

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

а) несимметричные задачи

min f = cx;

Ax = b, x ≥ 0

max f = cx;

Ax = b, x ≥ 0

max z = yb;

yA ≤ c

min z = yb;

yA ≥ c

 

в) симметричные задачи

min f = cx;

Ax ≥ b, x ≥ 0

max f = cx;

Ax ≤ b, x ≥ 0

min z = yb;

yA ≤ c, y ≥ 0

min z = yb;

yA ≥ c, y ≥ 0

 

Теоретическим обоснованием связи между исходной и двойственной задачами являются следующие теоремы [21]:

Теорема 2.7. «Если для некоторых допустимых решений x* и y* взаимно двойственных задач выполняется равенство f(x*) = z(y*), то x* и y* являются оптимальными решениями для этих задач».

Теорема 2.8. «Если целевая функция исходной задачи не ограничена сверху, то двойственная к ней задача не имеет допустимого решения».

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


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074