Двойственность в линейном программировании. Нахождение допустимых базисных решений. Двойственная задача линейного программирования, ее структура и свойства. Общий случай двойственности.

2. Двойственная задача линейного программирования

2.1. Структура и свойства двойственной задачи

Задачу максимизации ЛП с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b1,.,bm между различными потребителями, например между определенными технологическими процессами, которые представляются столбцами A1,.,An матрицы ограничений задачи.

Любое допустимое решение задачи ЛП x1,.,xn дает конкретное распределение, которое указывает ту долю каждого из ресурсов, которая должна быть использована при осуществлении соответствующего технологического процесса.

Рассмотрим пример. Предприятие производит три вида продукции x1, x2 и x3, каждый из которых проходит обработку на токарном, фрезеровальном и сверлильном станках. Общий фонд машинного времени для каждого из станков ограничен. Пусть c1, c2 и c3 - прибыль от реализации единицы соответствующего вида продукции. Необходимо определить, какое количество продукции каждого вида следует производить каждую неделю, чтобы обеспечить максимальную прибыль.

Эта задача имеет такой вид:$$\text{максимизировать} \; c_1 x_1 + c_2 x_2 + c_3 x_3$$ при ограничениях$$\begin{align*} a_{11} x_1 + a_{12} x_2 + \ldots + a_{13} x_3 \leq b_1 ; \\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{23} x_3 \leq b_2 ; \\ a_{31} x_1 + a_{32} x_2 + \ldots + a_{33} x_3 \leq b_3 . \end{align*}$$ где a1j, a2j, a3j - время, необходимое для обработки единицы j -го вида продукции на токарном, фрезеровальном и сверлильном станках соответственно (j=1, 2 ,3), b1, b2, b3 - недельный ресурс машинного времени для группы токарных, фрезеровальных и сверлильных станков соответственно.

Обозначим через y1, y2, y3 - цену единицы времени работы токарного, сверлильного и фрезеровального оборудования.

Тогда a11y1 + a21y2 + a31y3 можно трактовать как затраты на изготовление единицы продукции первого вида;

Предположим, что цены ресурсов y1, y2, y3 выбраны так, что выполняются соотношения$$\begin{align*} a_{11}y_1 + a_{12}y_2 + . + a_{13}y_3 \geq c_1 ;\\ a_{21}y_1 + a_{22}y_2 + . + a_{23}y_3 \geq c_2 ;\\ a_{31}y_1 + a_{32}y_2 + . + a_{33}y_3 \geq c_3 . \end{align*}$$

Поскольку b1, b2, b3 - общий использованный ресурс машинного времени для каждого из станков, то b1y1+b2y2+b3y3 - общие затраты на производство (общая стоимость использованных ресурсов).

Тогда можно сформулировать следующую задачу.

Требуется определить цены y1, y2, y3, удовлетворяющие условиям (2.1.3), при которых минимизируются суммарные затраты на производство, а именно:$$\text{минимизировать} \; g(y_1,y_2,y_3)= b_1y_1+b_2y_2+b_3y_3$$ при ограничениях (2.1.3) и$$y_1 \geq 0, y_2 \geq 0, y_3 \geq 0.$$

Задачу (2.1.3), (2.1.4) называют двойственной относительно задачи (2.1.1), называемой прямой.

Запишем прямую и двойственную задачи в общем виде.

Прямая задача:$$\text{максимизировать} \; \sum_{j=1}^n c_j x_j$$ при ограничениях$$\sum_{j=1}^n a_{ij} x_j , i=1,2,.,m,$$ $$x_j \geq 0, \; j=1,2,.,n.$$

Двойственная задача:$$\text{минимизировать} \; \sum_{i=1}^m b_i y_i$$ при ограничениях$$\sum_{i=1}^m a_{ij} y_i \geq c_j, \; j=1,2,.,n ,$$ $$y_i \geq 0, \; i=1,2,.,m.$$

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

Прямая задача:$$\text{максимизировать} c^T x$$ при ограничениях$$Ax \leq b;$$ $$x \geq 0$$

Двойственная задача:$$\text{максимизировать} b^T y$$ при условиях$$A^T y \geq c;$$ $$y \geq 0$$

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

Переменные y1,...,ym двойственной задачи иногда называют теневыми ценами.

Двойственную задачу выгоднее решать, чем прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений (m > n).

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

Теорема 2.1.1. Если x0 и y0 допустимые решения прямой и двойственной задач, то есть $$Ax_0 \leq b$$ и $$A^T y_0 \geq c$$, то$$c^T x_0 \leq b^T y_0,$$ то есть значения целевой функции прямой задачи никогда не превышают значения целевой функции двойственной задачи.

Доказательство. Умножим выражение (2.1.12) на $$y_0^T$$, получим$$y_0^T Ax_0 \leq y_0^T b.$$

Аналогично умножим (2.1.15) на $$x_0^T$$:$$x_0^T A^T y_0 \geq x_0^T c.$$

Но $$y_0^T Ax_0 = (y_0^T Ax_0)^T = x_0^T A^T y_0$$, а кроме того $$x_0^T c = c^T x_0$$.

Поэтому, сравнивая (2.1.19) и (2.1.18), получим$$y_0^T b \geq y_0^T Ax_0 \geq x_0^T c \; \text{или} \; c^T x_ 0 \leq b^T y_0.$$

Теорема доказана.

Теорема 2.1.2. (основная теорема двойственности). Если x0 и y0 допустимые решения прямой и двойственной задач и кроме того, если cTx0=bTy0, то x0 и y0 - оптимальные решения пары двойственных задач.

Доказательство. Согласно теореме 2.1.1 для всех допустимых решений х и у справедливо неравенство (2.1.17). В частности, для всех допустимых решений х справедливо $$c^T x \leq b^T y_0$$. Однако из условия теоремы cTx=bTy0 следует $$c^T x \leq c^T x_0$$. Следовательно, x0 - оптимальное решение.

Вторая часть теоремы доказывается аналогично.

В силу теоремы 2.1.1 для всех допустимых у справедливо $$c^T x_0 \leq b^T y$$. Но из условия $$c^T x_0=b^T y_0$$ следует, что $$b^T y \geq b^T y_0$$ для всех $$y \geq 0$$. Таким образом, y0 - оптимальное решение.

Теорема 2.1.3. Если в оптимальном решении прямой задачи (2.1.5) - (2.1.7) i - тое ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, то есть$$\textit{если} \; \sum_{j=1}^n a_{ij} x_{j \, \textit{опт}} = A^I x_{\, \textit{опт}} < b_i, \; \textit{то} \; y_{i \, \textit{опт}} = 0,$$ где Ai - i -я строка матрицы А.

Смысл теоремы 2.1.3 состоит в слeдующем. Если некоторый ресурс bi имеется в избытке, и і -тое ограничение при оптимальном решении выполняется как строгое неравенство, то это ограничение становится несущественным, и оптимальная цена соответствующего ресурса равна нулю.

Теорему 2.1.3. дополняет теорема 2.1.4, устанавливающая взаимосвязь между оптимальным решением прямой задачи и ограничениями двойственной.

Теорема 2.1.4. Если в оптимальном решении двойственной задачи ограничение j выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно нулю, то есть$$\textit{если} \; A-j^T y_{\, \textit{опт}} - c_j > 0, \; \textit{то} \; x_{j \, \textit{опт}} =0.$$

Дадим экономическую интерпретацию теоремы 2.1.4.

Поскольку величины yi (i=1,2,.,m) представляют собой цены соответствующих ресурсов, то $$A^T_j y = \sum_{i=1}^n a_{ij} y_i$$ - это затраты на j -й технологический процесс, а величина cj - прибыль от реализации единицы соответствующего продукта. Поэтому с экономической точки зрения теорема 2.1.4 означает следующее: если j -й технологический процесс оказывается строго невыгодным относительно оптимальных цен ресурсов yопт, то в оптимальном решении прямой задачи интенсивность использования данного технологического процесса должна быть равна нулю, и соответствующий вид продукции не выпускается как нерентабельный.

Таким образом, теорема 2.1.4 выражает принцип рентабельности для оптимально организованного производства.

Из этой теоремы вытекает также, что если $$x_{j \, \textit{опт}} > 0$$, то$$A_j^T y_{\, \textit{опт}} - c_j = 0$$

Предположим, что среди переменных x1, x2, ., xn прямой задачи есть множество из m переменных, которые в оптимальном решении прямой задачи имеют ненулевые значения. Пусть, например, такими переменными оказались первые по порядку m переменных.

Тогда на основании уравнения (2.1.22) получаем m условий рентабельности:$$\begin{align*} A^T_1 y_{\, \textit{опт}} – c_1 =0; \\ A^T_2 y_{\, \textit{опт}} – c_2 =0; \\ \ldots \ldots \ldots \ldots \ldots \\ A^T_m y_{\, \textit{опт}} – c_m =0; \end{align*}$$ где$$\begin{align*} A^T_1 = (a_{11}, a_{21}, . , a_{m1}); \\ \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\ A^T_m = (a_{1m}, a_{2m}, . , a_{mm}). \end{align*}$$

Доказательства теорем 2.1.3 и 2.1.4 проведем последовательно.

Пусть хопт и yопт - оптимальные решения прямой и двойственной задач. Поскольку эти решения допустимые, то$$Ax_{\, \textit{опт}} - b \leq 0;$$ $$A^T y_{\, \textit{опт}} - c \geq 0.$$

Умножив неравенство (2.1.24) на $$y^T_{\, \textit{опт}}$$, а неравенство (2.1.25) - на $$х^T_{\, \textit{опт}}$$, получим$$y^T_{\, \textit{опт}} \; Ax_{\, \textit{опт}} - y_{\, \textit{опт}} \; b \leq 0;$$ $$x^T_{\, \textit{опт}} \; A^T y_{\, \textit{опт}} - x^T_{\, \textit{опт}} \; c \geq 0.$$

Так как в силу теоремы 2.2 $$y^T_{\, \textit{опт}} b = x_{\, \textit{опт}} c$$ и $$y^T_{\, \textit{опт}} Ax_{\, \textit{опт}} = x^T_{\, \textit{опт}} A^T y{\, \textit{опт}}$$, то выражения (2.1.26), (2.1.27) строго равны нулю.

Расписав левую часть неравенства (2.1.26), получим$$\begin{align*} y^T_{\, \textit{опт}} \; (Ax_{\, \textit{опт}} \; - b) = y_{1 \, \textit{опт}} \; (A^{(1)} x_{\, \textit{опт}} \; - b_1) + y_{2 \, \textit{опт}} \; (A^{(2)} x_{\, \textit{опт}} \; - b_2) + \ldots + \\ +y_{m \, \textit{опт}} \; (A^{(m)} x_{\, \textit{опт}} \; - b_m) = 0 . \end{align*}$$

Поскольку $$y_{i \, \textit{опт}} \; \geq 0$$ и $$A^{(i)} x_{\, \textit{опт}} \; - b_i \leq 0$$ для всех i = 1, 2, ..., m, то левая часть уравнения (2.1.28) может быть равна 0 только в том случае, если каждое слагаемое в отдельности равно нулю.

Таким образом, для каждого i, при котором $$A^{(i)} x_{\, \textit{опт}} - b_i < 0$$, имеем $$y_{i \, \textit{опт}} = 0$$, что и требовалось доказать в теореме 2.1.3.

Рассмотрим теперь левую часть неравенства (2.1.27), предварительно расписав ее$$\begin{align*} x^T_{\, \textit{опт}} A^T y_{\, \textit{опт}} - x^T_{\, \textit{опт}} c = x^T_{\, \textit{опт}} (A^T y_{\, \textit{опт}} - c) = x_{1 \, \textit{опт}} (A^T_1 y_{\, \textit{опт}} - c_1) + \ldots + \\ + x_{2 \, \textit{опт}} (A^T_2 y_{\, \textit{опт}} - c_2) + \ldots + x_{n \, \textit{опт}} (A^T_n y_{\, \textit{опт}} - c_n) = 0, \end{align*}$$

где A=[A1,A2,...,An].

Так как все $$x_{j \, \textit{опт}} \geq 0$$ и $$A_j^T y_{\, \textit{опт}} - c_j \geq 0$$ для всех j=1,.,n, то уравнение (2.1.29) строго равно нулю, если для каждого j, при котором $$(A_j^T y_{\, \textit{опт}} -c_j) > 0$$, соответствующая переменная $$x_{j \, \textit{опт}}$$ равна нулю.

Приведем еще две важные теоремы теории двойственности.

Теорема 2.1.5. ( теорема существования ). Прямая и двойственная задачи имеют оптимальные решения тогда и только тогда, когда обе они имеют допустимые решения.

Теорема 2.1.6. (теорема двойственности). Допустимый вектор x0 оптимальный тогда и только тогда, когда в двойственной задаче имеется такое допустимое решение y0, что$$c^T x_0 = b^T y_0.$$

Между оптимальными решениями прямой и двойственной задач и элементами индексных строк симплекс-таблиц, соответствующих этим решениям, существует следующая взаимосвязь:$$\begin{align*} \Delta_{n+1}^{\text{пр}} = y_{i \, \textit{опт}} , \\ -\Delta_{m+j}^{\text{дв}} = x_{j \, \textit{опт}} , \\ i= 1, 2, \ldots, m; \quad j= 1, 2, \ldots, n, \end{align*}$$ где n - количество переменных прямой задачи; m - количество ее ограничений;

$$\Delta_{n+1}^{\text{пр}}, \; \Delta_{m+j}^{\text{дв}}$$ - соответствующие элементы индексной строки симплекс-таблицы прямой и двойственной задач соответственно.

При этом, если n+i, где $$1 \leq i \leq m$$, больше числа векторов-столбцов матрицы ограничений расширенной формы соответствующей задачи, то элементы $$\Delta_{n+i} , \; \Delta_{m+j}$$ находятся путем циклической перестановки, начиная с элемента $$\Delta_1$$.

2.2. Общий случай двойственности

В предыдущем разделе были установлены основные соотношения для пары двойственных задач ЛП при ограничениях в форме неравенств. Обобщим эти результаты на случай произвольных ограничений.

Пусть прямая задача ЛП задана в виде$$\text{максимизировать} \; \sum_{j=1}^n c_j x_j$$ при условиях$$\sum_{j=1}^n a_{ij} x_j \leq b_i , \; i=1,2,\ldots,m_1 \leq m ;$$ $$\sum_{j=1}^n a_{ij} x_j = b_i , \; i = m_1 + 1, m_1 + 2, \ldots, m ;$$ $$x_j \geq 0, \; j = 1,2,\ldots,n_1 \leq n.$$

Тогда двойственная задача по отношению к задаче (2.2.1)-(2.2.3) записывается так:$$\text{минимизировать} \; \sum_{i=1}^m b_i y_i$$ при условиях$$\sum_{i=1}^m a_{ij} y_i \geq c_j, \; j = 1,2,\ldots, n_1 \leq n ;$$ $$\sum_{i=1}^m a_{ij} y_i = c_j, \; j = n_1+1,n_1+2,\ldots, n ;$$

Таким образом, задача, двойственная к задаче со смешанными ограничениями (неравенства-равенства), составляется согласно следующим правилам.

Аналогично связаны знаки переменных двойственной задачи yi и соответствующие им ограничения прямой задачи.

Заметим, что если положить m1=m и n1=n, то получим частный случай пары двойственных задач с ограничениями в форме неравенств.

Докажем справедливость соотношений (2.2.1) - (2.2.3) и (2.2.4) - (2.2.6), связывающих прямую и двойственную задачи.

Свяжем с каждой ЛП - задачей вида (2.2.1) - (2.2.3) следующую задачу с ограничениями в форме неравенств:$$\text{максимизировать} \; \sum_{j=1}^{n_1} c_j x'_j + \sum_{j=n_1 +1}^n c_j (x'_j - x'_{j+n_1})$$ при условиях$$\sum_{j=1}^{n_1} a_{ij} x'_j + \sum_{j=n_1 + 1}^n a_{ij} (x'_j - x'_j+n_2) \leq b_i; \; i=1,2,\ldots,m ;$$ $$- \sum_{j=1}^{n_1} a_{ij} x'_j + \sum_{j=n_1 + 1}^n a_{ij} (x'_j - x'_j+n_1) \leq -b_i; \; i=m_1+1,m_1+2,\ldots,m ;$$ $$x'_j \geq 0; \; j=1,2,\ldots,n+n_2,$$ где n₂=n-n₁ - число переменных задачи (2.2.1) - (2.2.3), на которые не наложено условие неотрицательности.

Установим соответствие между переменными задач (2.2.1) - (2.2.3) и (2.2.7) - (2.2.10). Сравнивая формы их записи, убеждаемся, что n -мерный вектор х={x1,.,xn} и (n+n2) -мерный вектор $$x' = \{ x'_1, x'_2, .,x'_{n+n_2} \}$$ связаны соотношением$$x_j = \left\{ \begin{aligned} x'_j, \; j=1,2,\ldots,n_1 \\ x'_j - x'_{j+n_2}, \; j=n_1 + 1, n_1 + 2, \ldots, n \end{aligned} \right.$$

Очевидно, каждому (n+n2) -мерному вектору x' соответствует единственный n -мерный вектор x, и вместе с тем произвольному n -мерному вектору x соответствует целое семейство (n+n2) -мерных векторов х'.

Таким образом, соответствие, устанавливаемое формулой (2.2.11), является однозначным только в одну сторону.

Вместе с тем среди семейства векторов х', соответствующих x, всегда существуют векторы с неотрицательными компонентами.

Пусть вектор $$x'= \{ x'_1, x'_2, ., x'_{n+n_2} \}$$ - план задачи (2.2.7) -(2.2.10). Используя соотношение (2.2.11), можно легко получить, что соответствующий вектор x является планом задачи. И наоборот, если x - план задачи (2.2.1) - (2.2.3), то существует целое семейство планов x' задачи (2.4.38) - (2.4.41), среди которых имеются заведомо неотрицательные.

Одним из них является вектор $${\widetilde{x}}\,'$$ где

j = 1, 2, ., n1,
j = n1+1, n1+2, ., n,
j = n+1, n+2, ., n+n2.

$${\widetilde{x}}\,'_j = \left\{ \begin{aligned} x_j \\ \max (0, x_j) , \\ \max (0, -x_{j-n_2}) , \end{aligned} \right.$$

Неотрицательность всех компонентов $${\widetilde{x}}\,'$$ очевидна, а соответствие векторов x и $${\widetilde{x}}\,'$$ следует из равенства$${\widetilde{x}}\,'_j - {\widetilde{x}}\,'_{j+n_2} = \max (0, x_j) - \max (0, -x_j) = \left\{ \begin{aligned} x_j - 0 = x_j, \textit{при} \; x_j \geq 0; \\ 0 - (-x_j) = x_j , \textit{при} \; x_j < 0; \end{aligned} \right.$$ где j=n1+1; n1+2,.,n...

Рассмотрим задачу (2.2.4) - (2.2.6), двойственную к задаче (2.2.1) - (2.2.3). Нетрудно показать, что она приводится к виду (2.2.1) - (2.2.3). Для этого достаточно положить $$\overline{c}_j = -c_j ; \; \overline{a}_{ij} = -a_{ij} ; \; \overline{b}_i = -b_i$$. При этом задача (2.2.4) - (2.2.6) переходит в задачу$$\text{минимизировать} \; \sum_{i=1}^m \overline{b}_i y_i$$ при условиях$$\sum_{i=1}^m \overline{a}_{ij} y_i \geq \overline{c}_j, \; j=1,2,.,n_1 ;$$ $$\sum_{i=1}^m \overline{a}_{ij} y_i = \overline{c}_j, \; j=n_1+1, n_1+2,.,n ;$$ $$y_i \ge 0; \; i=1,2,.,m_1.$$

Поэтому задаче (2.2.4) - (2.2.6) соответствует следующая задача с ограничениями в форме неравенств:$$\text{минимизировать} \; \sum_{i=1}^{m_1} b_i y'_i + \sum_{i=m_1 + 1}^m b_i (y'_i - y'_{i+m_1})$$ при условиях$$\sum^m_{i=1} \overline b_{ij}y_{ij}\ge \overline c_j \ j= 1,2 \ldots,n;$$ $$- \sum_{i=1}^{m_1} a_{ij} y'_i - \sum_{i=m_1+1}^m a_{ij}(y'_i - y'_{i+m_1}) \geq -c_j ; \; j=n_1+1; n_1+2,.,n.$$ $$y'_i \geq 0; \; i=1,2,.,m+m_2 \ldots$$ где m2 = m - m1 - число переменных yi, на которые не наложено условие неотрицательности.

Вектор y={y1,.,ym} и соответствующий ему (m+m2) мерный вектор $$y' = \{ y'_1,.,y'_{m+m_2} \}$$ связанны соотношением$$y_i = \left \{ \begin{aligned} y'_i, \; i=1,2,\ldots,m_1 ; \\ y'_i - y'_{i+m_1}, \; i=m_1 +1, m_1+2,\ldots,m. \end{aligned} \right.$$

Следовательно, каждому плану y' задачи (2.2.17) - (2.2.20) соответствует план у задачи (2.2.4) - (2.2.6), и наоборот: любой неотрицательный вектор, соответствующий плану (решению) задачи (2.2.4) - (2.2.6), является решением задачи (2.2.18) - (2.2.20). При этом, если у' и у - два соответствующих друг другу решения, то из оптимальности одного из них непосредственно следует оптимальность другого.

Запишем задачу, двойственную к (2.2.7) - (2.2.10). Непосредственной проверкой можно убедиться в том, что получим задачу в форме (2.2.17) - (2.2.20). Таким образом, задачи (2.2.7) - (2.2.10) и (2.2.17) -(2.2.20) с произвольными ограничениями (неравенства - равенства) также представляют собой двойственную пару.

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

Рассмотрим для примера теорему 2.2.1.

Если х и у - допустимые решения прямой (2.2.1) - (2.2.2) и двойственной (2.2.4) - (2.2.6) задачи и если при этом $$\sum_{j=1}^n c_j x_j = \sum_{i=1}^m b_i y_i$$, то х и у - оптимальные решения этих задач.

Доказательство. Допустим, что задача (2.2.1) - (2.2.2) разрешима и x -ее допустимое решение, а у - допустимое решение (план) задачи (2.2.4) - (2.2.6). Рассмотрим вектор $$х'={x'_1,.,x'_{n+n_2}}$$, связанный с вектором х соотношениями (2.2.11), с неотрицательными компонентами. По доказанному выше х' является решением задачи (2.2.7).

Воспользуемся тогда теоремой 2.2.1 для задач с ограничениями - неравенствами.

Согласно этой теореме, если х' и у' - допустимые решения пары двойственных задач и выполняется равенство$$\sum_{j=1}^{n_1} c_j x'_j + \sum_{j=n_1+1}^n c_j (x'_j - x'_{j+n_2}) = \sum_{i=1}^{m_1} b_i y'_i + \sum_{i=m_1+1}^m b_i (y'_i - y'_{i+m_2})$$

то х' и у' - оптимальные решения этой пары задач.

Используя соотношения (2.2.11), (2.2.21), связывающие соответствующие планы х' и х, у и у', получим$$\sum_{i=1}^{n_1} c_j x'_j + \sum_{j=n_1+1}^n c_j (x'_j - x'_{j+n_2}) = \sum_{j=1}^{n} c_j x_j ;$$

Таким образом, соотношения (2.2.22) и (2.2.23) - (2.2.24) - эквивалентны, поэтому планы х' и у' - оптимальны.

Но по доказанному выше каждому оптимальному х' соответствует единственный оптимальный план х, а каждому оптимальному плану у' соответствует единственный план у. Теорема доказана.

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