Научная электронная библиотека

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

Прикладные методы оптимизации

Шукаев Д. Н.,

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 + … + c_nx_n;

a11x1 + a12x2 + … + a_1nx_n ≥ b1;

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

a_m1x₁ + a_m2y2 + … + a_mny_m ≥ b_m;

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

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

min z = b1y1 + b2y2 + … + bmym;

a11y1 + a₂₁y₂ + … + a_m1y_m ≥ c1;

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

a_1ny1 + a_2ny2 + … + a_mny_m ≥ cn;

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

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

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

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

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

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

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

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

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