Двойственная задача линейного программирования
Составление двойственной задачи линейного программирования
Для каждой задачи линейного программирования по определённым правилам можно составить соответствующую задачу, называемую двойственной задачей.
Рассмотрим прямую задачу линейного программирования и двойственную задачу.
Прямая задача.
Максимизировать функцию
при ограничениях
Двойственная задача.
Минимизировать функцию
при ограничениях
Эти задачи обладают следующими свойствами:
- В прямой задаче ищется максимум функции цели (линейной формы), а в двойственной задаче - минимум.
- Коэффициенты при переменных в функции цели прямой задачи являются свободными членами системы ограничений двойственной задачи, и наоборот, свободные члены системы ограничений прямой задачи - коэффициентами при переменных в функции цели двойственной задачи.
- В каждой задаче система ограничений задаётся в виде неравенств, причём все они одного смысла, а именно: при нахождении максимума функции цели (прямая задача) эти неравенства записываются со знаком "меньше или равно", а при нахождении минимума (двойственная задача) - со знаком "больше или равно".
- Коэффициенты при переменных в системах ограничений описываются матрицами
и
которые являются транспонированными относительно друг друга. - Число неравенств в системе ограничений прямой задачи совпадает с числом переменных двойственной задачи.
- Условия неотрицательности переменных сохраняются как в прямой, так и в двойственной задаче.
Две задачи линейного программирования, удовлетворяющие указанным выше условиям, называются симметричными взаимно-двойственными задачами.
Мы обусловимся называть их просто взаимно-двойственными задачами.
Прямая и двойственная ей задача, взятые вместе, образуют пару взаимно двойственных задач, причём любую из них можно рассматривать как исходную, тогда другая окажется двойственной ей.
Итак мы рассмотрели соответствие между прямой и двойственной задачей линейного программирования, правда, пока только для задач, записанных в канонической форме. Сформулируем пока правила составления задачи, двойственной по отношению к исходной для канонической задачи (а позже перейдём к задаче, записанной в общей форме):
- Приводят все неравенства системы ограничений исходной задачи к неравенствам одного смысла(то есть с одним и тем же знаком): если в исходной задаче ищется максимум функции цели (линейной формы) - они записываются со знаком "меньше или равно", если же минимум - со знаком "больше или равно". Для этого неравенства, в которых это требование не выполняется, умножают на минус единицу.
- Выписывают матрицу A коэффициентов при переменных исходной задачи, полученых после преобразований, описанных в предыдущем пункте, и составляют матрицу A', транспонированную относительно матрицы A.
- Составляют систему ограничений двойственной задачи, взяв в качестве коэффициентов при переменных элементы матрицы A', а в качестве свободных членов - коэффициенты при переменных в функци цели исходной задачи и записывают неравенства противоположного смысла (то есть меняют знак) по сравнению с неравенствами, полученными в пункте 1.
- Составляют функцию цели (линейную форму) двойственной задачи, приняв за коэффициенты при переменных свободные члены системы ограничений исходной задачи, полученные в пункте 1.
- Указывают, что необходимо найти при решении двойственной задачи, а именно: минимум функции цели, если в исходной задаче ищется максимум, и максимум, если в исходной задаче ищется минимум.
- Записывают условие неотрицательности переменных двойственной задачи.
Пример 1. Составить задачу, двойственную следующей: найти максимум
функции 
при ограничениях
Решение. Третье неравенство системы исходной задачи не удовлетворяет пункту 1 правил составления двойственной задачи. Поэтому умножим его на минус единицу:
Для облегчения составления двойственной задачи лучше пользоваться расширенной матрицей B, в которую наряду с коэффициентами при переменных системы ограничений исходной задачи запишем свободные члены и коэффициенты при переменных в функции цели, выделив для этой цели дополнительные столбец (отделён чертой) и строку (выделена красным цветом). Матрицу B транспонируем и, используя транспонированную матрицу B', составляем задачу, двойственную исходной. Матрицы B и B' имеют вид
,
Таким образом, двойственная задача линейного программирования сводится к нахождению минимума функции
при ограничениях
Перейдём теперь к случаю составления двойственной задачи, когда прямая задача записана в общей форме (в системе ограничений могут быть неравенства с разными знаками, а также уравнения, условие неотрицательности переменных не обязательно). Для таких задач правила следующие:
- Свободные члены в прямой задаче - коэффициенты функции цели в двойственной задаче.
- Коэффициенты функции цели в прямой задаче - свободные члены в двойственной задаче.
- Расширенная матрица в прямой задаче - транспонированная расширенная матрица в двойственной задаче.
- j-й неизвестный в прямой задаче неотрицательный - j-е неравенство в двойственной задаче со знаком "больше или равно".
- j-й неизвестный в прямой задаче без ограничения знака - j-е ограничение в двойственной задаче в виде уравнения.
- j-й неизвестный в прямой задаче неположительный - j-е неравенство в двойственной задаче со знаком "меньше или равно".
- i-е неравенство в прямой задаче со знаком "меньше или равно" - i-е неизвестный в двойственной задаче неотрицательный.
- i-е ограничение в прямой задаче в виде уравнения - i-й неизвестный в двойственной задаче без ограничения знака.
- i-е неравенство в прямой задаче со знаком "больше или равно" - i-й неизвестный в двойственной задаче неположительный.
Пример 2. Составить задачу, двойственную следующей: найти минимум
функции 
при ограничениях
Решение. Как видим, прямая задача записана в общей форме. Это будем учитывать при расстановке знаков в условиях двойственной задачи. А пока, как и в предыдущем примере, произведём универсальное действие - составим матрицу B прямой задачи и транспонированную матрицу B' двойственной задачи:
,
Таким образом, двойственная задача линейного программирования сводится к нахождению максимума функции
при ограничениях
Основные теоремы двойственности
Теория двойственности в линейном программировании строится на двух основных теоремах.
Теорема 1. Для прямой и двойственной задач в силе одно и только одно из следующих утверждений. 1. Если одна из задач линейного программирования имеет конечный оптимум, то и двойственная к ней задача также имеет конечный оптимум, причём оптимальные значения линейных форм обеих задач совпадают, т. е. Fmax = Zmin или Fmin = Zmax. 2. Если линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы. 3. Обе задачи не имеют решения, так как системы ограничений противоречивы.
Прежде чем сформулировать следующую теорему, установим соответствия между переменными в исходной и двойственной задачах. Приготовьтесь: последует игра формул, которую с первого раза не каждый поймёт, но после ознакомления с примером 2 должны понять все.
При решении симплекс-методом исходной задачи для сведения системы неравенств к эквивалентной ей системе уравнений нужно ввести m добавочных неотрицательных переменных (по числу неравенств в системе ограничений) xn+1, xn+2, ..., xn+i, ..., xn+m, где i = 1, 2, ..., m означает номер неравенства, в которое была введена добавочная переменная xn+i.
Система ограничений двойственной задачи состоит из n неравенств, содержащих m переменных. Если решать эту задачу симплекс-методом, то следует ввести n добавочных неотрицательных переменных ym+1, ym+2, ..., ym+j, ..., ym+n, где j = 1, 2, ..., n означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная ym+j.
Всё вышесказанное было приведено для того, чтобы установить следующее соответствие между переменными в исходной и двойственной задачах линейного программирования:
x1 ↔ ym+1
x2 ↔ ym+2
...
xj ↔ ym+j
...
xn ↔ ym+n
xn+1 ↔ y1
xn+2 ↔ y2
...
xn+i ↔ yi
...
xn+m ↔ ym
То есть, основные переменные исходной задачи, в порядке их следования, соответствуют добавочным переменным двойственной задачи, тоже в порядке их следования. В свою очередь добавочные переменные исходной задачи, в порядке их следования, соответствуют основным переменным двойственной задачи, также в порядке их следования.
Иными словами, каждой первоначальной переменной исходной задачи xj (j = 1, 2, ..., n) ставится в соответствие добавочная переменная ym+j, введённая в j-е неравенство двойственной задачи, а каждой добавочной переменной xn+i исходной задачи (i = 1, 2, ..., m), введённой в i-е неравенство исходной задачи, - первоначальная переменная yi двойственной задачи.
Всё вышесказанное, как уже было отмечено, станет более понятным из примера 2, который будет вскоре после Теоремы 2.
Теорема 2. Компоненты оптимального решения одной из задач (прямой или двойственной) равны абсолютным величинам коэффициентов при соответствующих переменных в выражении функции цели (линейной формы) другой задачи (двойственной или прямой) при достижении ею оптимума и при условии, что полученное оптимальное решение не является вырожденным.
Из теорем 1 и 2 следует, что если решить одну из взаимно двойственных задач линейного программирования, то есть найти её оптимальное решение и оптимум функции цели, то можно записать оптимальное решение и оптимум функции цели другой задачи. Теперь пример, который поможет разложить всё вышеизложенное по полочкам.
Пример 3. На основании решений прямой и двойственной задач линейного программирования из примера 1 убедиться в справедливости теорем 1 и 2.
В примере 1 была дана исходная задача: найти максимум
функции при ограничениях
Мы составили двойственную ей задачу: найти минимум функции
при ограничениях
Для решения прямой задачи симплекс-методом система ограничений-неравенств сводится к системе уравнений путём введения добавочных неотрицательных переменных x3, x4, x5, x6:
Читатель может проверить, решив задачу симплекс-методом, что она имеет следующие решения:
а максимум целевой функции Fmax = 13,
при этом сама целевая функция выражается как
Система ограничений двойственной задачи сводится к системе уравнений путём введения добавочных переменных y5, y6:
Решение двойственной задачи симплекс-методом даёт следующий ответ:
а минимум целевой функции Zmin = 13,
при этом сама целевая функция выражается как
.
Решив двойственную задачу, убеждаемся в справедливости первой части теоремы 1: двойственная задача тоже имеет конечный оптимум, причём Zmin = Fmax = 13.
Убедимся, что справедливо также и утверждение теоремы 2. Для этого запишем переменные прямой и двойственной задачи, соблюдая их соответствие:
x1 ↔ y5
x2 ↔ y6
x3 ↔ y1
x4 ↔ y2
x5 ↔ y3
x6 ↔ y4
Как видим, основные переменные исходной задачи, в порядке их следования, соответствуют добавочным переменным двойственной задачи, тоже в порядке их следования. В свою очередь добавочные переменные исходной задачи, в порядке их следования, соответствуют основным переменным двойственной задачи, также в порядке их следования.
Функцию цели, полученную на последнем шаге решения двойственной задачи, выразим через все переменные этой задачи:
Рассматривая коэффициенты при переменных yj в этой функции цели и учитывая их соответствие коэффициентам при переменных xi, получим решение (4; 1; 0; 5; 4; 0), совпадающее с решением прямой задачи.
Замечание. Решив прямую задачу, можно сразу получить решение двойственной задачи линейного программирования. Если выразить функцию цели, полученную при решении прямой задачи, через все переменные задачи, то получим
.
На основании теоремы 2, учитывая соответствие между переменными в прямой и двойственной задачах и взяв абсолютную величину коэффициентов при переменных, найдём оптимальное решение двойственной задачи (2/3; 0; 0; 7/3; 0; 0). При этом Zmin = Fmax = 13.
Пример 4. Убедиться в том, что системы ограничений прямой задачи
и двойственной задачи
.
несовместны.
Решение. Вычтем из второго уравнения системы ограничений прямой задачи первое
уравнение той же системы. Получим 
.
Это уравнение не имеет решения, так как 
.
Таким образом, система ограничений прямой задачи несовместна.
Сложим первые два неравенства системы ограничений двойственной задачи. Получим
, что невозможно.
Таким образом, системы ограничений и прямой, и двойственной задачи несовместны. Согласно части 3 теоремы 1
двойственности, обе задачи не имеют решений.
Экономическая интерпретация двойственной задачи линейного программирования
Посмотрим ещё раз на прямую задачу линейного программирования и двойственную задачу рядом.
Прямая задача.
Максимизировать функцию
при ограничениях
Двойственная задача.
Минимизировать функцию
при ограничениях
В этих задачах a - расходы сырья определённого вида на производство одного вида продукции, b запасы сырья определённого вида, c - прибыль от реализации единицы продукции определённого вида. В прямой задаче x - количество единиц выпускаемой продукции определённого вида. А в двойственной задаче b - цены сырья соответствующего вида. А целевая функция Z - общие затраты на приобретение сырья, которые требуется минимизировать.
Предположим, мастерская выпускает столы и шкафы, расходую на эти цели определённые виды сырья (древесины). Допустим, мастерская решила не производить продукцию, а продать сырьё - древесину, желая при этом получить выручку, не меньшую максимальной прибыли от реализации продукции. По каким ценам нужно продавать каждый вид древесины?
Максимальную прибыль определяет решение прямой задачи. Путём же решения двойственной задачи линейного программирования находятся цены y, точнее говоря, объективно обусловленные оценки. Они являются компонентами оптимального решения двойственной задачи линейного программирования.
| Назад<<< | Листать | Вперёд>>> |
Поделиться с друзьями
