Просмотр кода страницы Двойственная задача линейного программирования

'''Двойственная задача'''<ref>Иногда используется термин '''Сопряжённая задача''', как, например, в книге Юдина и Гольштейна {{harv|Юдин, Гольштейн|1969|loc=149}} или в книге Лунгу {{harv|Лунгу|2005|loc=67}}. Во второй книге прямая задача именуется также '''основной задачей'''.</ref> для заданной задачи [[Линейное программирование|линейного программирования]] (ЛП, {{lang-en|Linear programming}}, LP) — это другая задача линейного программирования, которая получается из исходной ('''''прямой''''') задачи следующим образом:

* Каждая переменная в прямой задаче становится ограничением двойственной задачи;
* Каждое ограничение в прямой задаче становится переменной в двойственной задаче;
* Направление цели обращается – максимум в прямой задаче становится минимумом в двойственной, и наоборот.

Теорема о [[Слабая двойственность|слабой двойственности]] утверждает, что значение двойственной задачи для любого допустимого решения всегда ограничено значением прямой задачи для любого допустимого решения (верхняя или нижняя граница, в зависимости от того, это задача максимизации или минимизации).

Теорема о [[Сильная двойственность|сильной двойственности]] утверждает, что более того, если прямая задача имеет оптимальное решение, то двойственная задача имеет также оптимальное решение, ''и эти два оптимума равны''{{sfn|Gartner, Matousek|2006|с=81–104}}.

Эти теоремы принадлежат более широкому классу [[Двойственность (оптимизация)|теорем двойственности в оптимизации]]. Теорема о сильной двойственности является одним из случаев, в котором [[разрыв двойственности]] (разрыв между оптимумом прямой задачи и оптимумом двойственной) равен 0.

О геометрическом смысле двойственной задачи можно почитать в книге Юдина и Гольштейна{{sfn|Юдин, Гольштейн|1969|с=150-152 Пункт 5.2}}. Там же можно прочитать об экономическом смысле задачи{{sfn|Юдин, Гольштейн|1969|с=157-159 Пункт 5.5}}.

== Построение двойственной задачи ==
Если дана прямая задача линейного программирования, для построения двойственной задачи может быть использован следующий алгоритм{{sfn|Gartner, Matousek|2006|с=85}}.

Пусть прямая задача определена как:
* Дан набор из ''n'' переменных: <math>x_1 ,\ldots, x_n</math>.
* Для каждой переменной ''i'' определено ''ограничение на знак'' — она должна быть либо неотрицательной (<math>x_i \geqslant 0</math>), либо неположительной (<math>x_i \leqslant 0</math>), либо ограничение не задано  (<math>x_i \in \mathbb{R}</math>).
* Задана целевая функция: Максимизировать <math>c_1 x_1 +\cdots + c_n x_n</math>
* Задан список из ''m'' ограничений. Каждое ограничение ''j'' равно:   <math>a_{j 1} x_1 +\cdots + a_{j n} x_n \lesseqqgtr b_j</math>, где символ перед <math>b_j</math> может быть одним из трёх — <math>\geqslant</math>, <math>\leqslant</math> или <math>=</math>.

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

* Каждое ограничение прямой задачи становится двойственной переменной. Таким образом, получаем ''m'' переменных: <math>y_1 ,\ldots, y_m</math>.
* Знак ограничения каждой двойственной переменной «противоположен» знаку ограничения в прямой задаче. Таким образом, «<math>\geqslant b_j </math>» становится   <math>y_j \leqslant 0 </math>, «<math>\leqslant b_j </math>» превращается в  <math>y_j \geqslant 0 </math>, а «<math> = b_j </math>» превращается в <math>y_j \in \mathbb{R} </math>.
* Целевая функция двойственной задачи равна (минимизировать) <math> b_1 y_1 +\cdots + b_m y_m</math>
* Каждая переменная прямой задачи становится двойственным ограничением. Таким образом, получаем ''n'' ограничений.  Коэффициент двойственной переменной в двойственных ограничениях равен коэффициенту переменной из ограничения прямой задачи.  Таким образом, каждое ограничение ''i'' есть: <math>a_{1 i} y_1 +\cdots + a_{m i} y_m \lesseqqgtr c_i</math>, где символ перед <math>c_i</math> аналогичен ограничению на переменную ''i'' в прямой задаче. Так, <math>x_i \leqslant 0 </math> превращается в «<math>\leqslant c_i </math>», <math>x_i \geqslant 0 </math> превращается в  «<math>\geqslant c_i </math>», а <math>x_i \in \mathbb{R} </math> превращается в «<math>= c_i </math>».

Из этого алгоритма легко видеть, что двойственная задача двойственной задачи совпадает с прямой задачей.

== Векторные формулировки ==
Если все ограничения имеют один и тот же знак, можно представить вышеизложенный метод в более короткой форме с помощью векторов и матриц. Следующая таблица представляет связи между различными видами прямых и двойственных задач.
{| class="wikitable"
!Прямая
!Двойственная
!Примечания
|-
|Максимизировать <math>\mathbf{c}^T\mathbf{x}</math>  при ограничениях <math>\mathbf{A}\mathbf{x} \leqslant \mathbf{b}, \mathbf{x} \geqslant 0</math>
| Минимизировать <math>\mathbf{b}^T\mathbf{y}</math>  при ограничениях <math>\mathbf{A}^T\mathbf{y} \geqslant \mathbf{c}, \mathbf{y} \geqslant 0</math>
|Такая задача называется «симметричной» двойственной задачей
|-
| Максимизировать <math>\mathbf{c}^T\mathbf{x}</math> при ограничениях <math>\mathbf{Ax} \leqslant \mathbf{b}</math>
| Минимизировать <math>\mathbf{b}^T\mathbf{y}</math> при ограничениях <math>\mathbf{A}^T\mathbf{y} = \mathbf{c}, \mathbf{y} \geqslant 0</math>
| Такая задача называется «асимметричной» двойственной задачей
|-
| Максимизировать <math>\mathbf{c}^T\mathbf{x}</math>  при ограничениях <math>\mathbf{Ax} = \mathbf{b}, \mathbf{x} \geqslant 0</math>
|Минимизировать  <math>\mathbf{b}^T\mathbf{y}</math>  при ограничениях <math>\mathbf{A}^T\mathbf{y} \geqslant \mathbf{c}</math>
|
|}

== Теоремы двойственности ==
Ниже мы предполагаем, что прямая задача поставлена как «Максимизировать <math>\mathbf{c}^T\mathbf{x}</math> при ограничениях [ограничения]», а двойственная задача поставлена как «Минимизировать <math>\mathbf{b}^T\mathbf{y}</math> при ограничениях [ограничения]».

=== Слабая двойственность ===

'''Теорема о слабой двойственности''' утверждает, что для каждого допустимого решения '''x''' прямой задачи и каждого допустимого решения '''y''' двойственной задачи: <math>\mathbf{c}^T\mathbf{x} \leqslant \mathbf{b}^T\mathbf{y}</math>. Другими словами, значение целевой функции для каждого допустимого решения двойственной задачи является верхней границей целевой функции прямой задачи, а значение целевой функции любого допустимого решения прямой задачи является нижней границей для целевой функции двойственной задачи. Из этого следует, что <blockquote><math>\max_{\mathbf{x}} \mathbf{c}^T\mathbf{x} \leqslant  \min_{\mathbf{y}} \mathbf{b}^T\mathbf{y}</math></blockquote> В частности, если прямая задача не ограничена (сверху), то двойственная задача не имеет допустимого решения, а если не ограничена двойственная задача (снизу), то не имеет допустимого решения прямая задача.

Теорему о слабой двойственности относительно легко доказать<ref>Доказательство очень близкого утверждения, из которого вытекает данная теорема можно найти в книге Юдина и Гольштейна {{harv|Юдин, Гольштейн|1969|loc=159, Лемма 5.1}}</ref>. Предположим, что прямая задача линейного программирования звучит как «Максимизировать <math>\mathbf{c}^T\mathbf{x}</math> при ограничениях <math>\mathbf{Ax} \leqslant \mathbf{b}, \mathbf{x} \geqslant 0</math>». Предположим, что мы создаём линейную комбинацию ограничений с положительными коэффициентами, такую, что коэффициенты при '''x''' не меньше <math>\mathbf{c}^T</math>. Эта линейная комбинация даёт нам верхнюю грань для целевой функции. Переменные '''y''' двойственной задачи являются коэффициентами этой линейной комбинации. Двойственная задача пытается найти такие коэффициенты, которые минимизируют результирующую правую часть. Это даёт задачу линейного программирования «Минимизировать <math>\mathbf{b}^T\mathbf{y}</math>  при ограничениях <math>\mathbf{A}^T\mathbf{y} \geqslant \mathbf{c}, \mathbf{y} \geqslant 0</math>»{{sfn|Gartner, Matousek|2006|с=81–83}}.   См. «Простой пример» ниже.

=== Сильная двойственность ===

'''Теорема о сильной двойственности''' утверждает, что границы, определяемые теоремой о слабой двойственности жёсткие, то есть <blockquote><math>\max_{\mathbf{x}} \mathbf{c}^T\mathbf{x}  =  \min_{\mathbf{y}} \mathbf{b}^T\mathbf{y}</math></blockquote> Теорему о сильной двойственности существенно труднее доказать. Обычно доказательство использует теорему о слабой двойственности в качестве леммы<ref>Доказательство можно найти в книге Юдина и Гольштейна, где она именуется «первой теоремой двойственности» {{harv|Юдин, Гольштейн|1969|loc=164, Теорема 6.1}}</ref>.

Одно доказательство использует [[симплекс-метод]] и опирается на доказательство того, что, при подходящем правиле выбора выводимого столбца, он даёт правильное решение. Доказательство устанавливает, что, когда симплекс-метод завершается решением прямой задачи линейного программирования, можно из конечной таблицы прочесть решение двойственной задачи. Таким образом, после прогона симплекс-алгоритма мы получим решения как прямой, так и двойственной задачи одновременно{{sfn|Gartner, Matousek|2006|с=87–89}}.

Другое доказательство использует [[Лемма Фаркаша|лемму Фаркаша]]{{sfn|Gartner, Matousek|2006|с=81–94}}

=== Теоретическое приложение ===
Слабая двойственность имеет интересное теоретическое приложение — она показывает, что нахождение ''отдельного'' допустимого решения настолько же трудно, насколько нахождение ''оптимального'' допустимого решения. Предположим, что мы имеем систему предсказывания, что данная задача линейного программирования находит произвольное допустимое решение (если оно существует). Если задача звучит как «Максимизировать <math>\mathbf{c}^\mathbf{x}</math>  при ограничениях <math>\mathbf{Ax} \leqslant \mathbf{b}, \mathbf{x} \geqslant 0</math>», мы можем построить другую задачу путём комбинирования её с двойственной ей задачей. Комбинированная задача имеет как '''x''', так и '''y''' в качестве переменных:<blockquote> Максимизировать '''1''' </blockquote><blockquote> при ограничениях <math>\mathbf{Ax} \leqslant \mathbf{b},  \mathbf{A}^T\mathbf{y} \geqslant \mathbf{c},    \mathbf{c}^T\mathbf{x} \geqslant \mathbf{b}^T\mathbf{y},  \mathbf{x} \geqslant 0,  \mathbf{y} \geqslant 0</math></blockquote>Если комбинированная задача имеет допустимое решение ('''x''','''y'''), то по слабой двойственности <math>\mathbf{c}^T\mathbf{x} = \mathbf{b}^T\mathbf{y}</math>. Таким образом, '''x''' должно быть максимальным решением прямой задачи, а '''y''' должно быть минимальным решением двойственной задачи. Если комбинированная задача не имеет допустимого решения, то и прямая задача допустимого решения не имеет.

== Примеры ==

=== Простой пример ===

Рассмотрим прямую задачу с двумя переменными и одним ограничением:

: Максимизировать <math>3 x_1 + 4 x_2 </math>
: При условиях
:<math>\begin{align}& 5 x_1 + 6 x_2 = 7
\\ & x_1\geqslant 0, x_2\geqslant 0\end{align}</math>

Применив вышеизложенный рецепт построения двойственной задачи, получим задачу с одной переменной и двумя ограничениями:

: Минимизировать  <math>7 y_1</math>
: При условиях
<math>\begin{align}&& 5 y_1 \geqslant 3
\\ && 6 y_1 \geqslant 4
\\ && y_1\in \mathbb{R}
\end{align}</math>

Легко видеть, что максимум прямой задачи достигается, когда переменная ''x''<sub>1</sub> минимизируется до её нижней границы (0), а переменная ''x''<sub>2</sub> максимизируется до её верхней границы, заданной ограничением (7/6). Максимум равен <math>4 \cdot 7/6 = 14/3</math>.

Аналогично, минимум двойственной задачи достигается, когда ''y''<sub>1</sub> минимизируется до его нижнего значения при ограничениях: первое ограничение даёт значение 3/5, в то время как второе даёт более строгую границу 4/6, так что фактический минимум равен 4/6 и минимум целевой функции равен <math>7 \cdot 4/6 = 14/3</math>.

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

Мы используем этот пример для иллюстрации доказательства теоремы о слабой двойственности. Предположим, что в прямой задаче линейного программирования мы хотим получить верхнюю границу целевой функции <math>3 x_1 + 4 x_2</math>.  Мы можем использовать ограничение, умноженное на некоторый коэффициент, скажем, <math>y_1</math>. Для любого <math>y_1</math> мы имеем: <math>y_1\cdot (5 x_1 + 6 x_2) = 7 y_1</math>.  Теперь, если <math>y_1\cdot 5 x_1 \geqslant 3 x_1</math> и  <math>y_1\cdot 6 x_2 \geqslant 4 x_2</math>, то <math>y_1\cdot (5 x_1 + 6 x_2) \geqslant 3 x_1 + 4 x_2</math>, так что <math>7 y_1 \geqslant 3 x_1 + 4 x_2</math>. Следовательно, целевая функция двойственной задачи является верхней границей целевой функции прямой задачи.

=== Пример фермера ===
Рассмотрим фермера, который может выращивать пшеницу и ячмень на площади ''L'', используя удобрения ''F'' и пестициды ''P''.
Чтобы вырастить одну единицу пшеницы на единице площади, нужно использовать <math>F_1</math> единиц удобрений и <math>P_1</math> единиц пестицидов.

Прямой задачей будет решение фермера, сколько пшеницы (<math>x_1</math>) и ячменя (<math>x_2</math>) выращивать, если их продажные цены равны <math>S_1</math> и <math>S_2</math> за единицу.

: Максимизировать:
:<math>S_1 \cdot x_1 + S_2 \cdot x_2</math> (максимизировать доход от выращивания пшеницы и ячменя)
: при ограничениях:
:<math>x_1 + x_2 \leqslant L</math> (фермер не может использовать больше земли, чем у него есть)
:<math>F_1 \cdot x_1 + F_2 \cdot x_2 \leqslant F</math> (фермер не может использовать больше удобрений, чем есть в наличии)
:<math>P_1 \cdot x_1 + P_2 \cdot x_2 \leqslant P</math> (фермер не может использовать больше пестицидов, чем у него есть)
:<math>x_1, x_2 \geqslant 0</math> (нельзя вырастить отрицательную величину зерна).

Для двойственной задачи предположим, что ''y'' единиц цены для каждой из этих видов продукта (входы) представлены группой планирования. Задачей группы планирования является минимизация полной стоимости производство продукции при заданных величинах потребления ресурсов с определением стоимости единицы ресурса (выход). Это соответствует следующей задаче линейного программирования:
: Минимизировать
: <math>L\cdot y_L + F\cdot y_F + P\cdot y_P</math> (минимизировать полную стоимость производства продукции как «целевая функция»)
: при ограничениях:
:<math>y_L+F_1\cdot y_F+P_1\cdot y_P\geqslant S_1</math> (фермер должен получить не менее ''S''<sub>1</sub> за единицу пшеницы)
:<math>y_L+F_2\cdot y_F+P_2\cdot y_P\geqslant S_2</math> (фермер должен получить не менее ''S''<sub>2</sub> за единицу ячменя)
:<math>y_L, y_F, y_P\geqslant 0</math> (цены не могут быть отрицательными).

В матричной форме:

: Минимизировать: <math>\begin{bmatrix} L & F & P \end{bmatrix} \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} </math>
: при условиях: <math>\begin{bmatrix} 1 & F_1 & P_1 \\ 1 & F_2 & P_2 \end{bmatrix} \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} \geqslant \begin{bmatrix} S_1 \\ S_2 \end{bmatrix}, \, \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} \geqslant 0. </math>

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

Каждой переменной в пространстве прямой задачи соответствует неравенство в пространстве двойственной задачи. Каждому неравенству в пространстве прямой задачи соответствует переменная в пространстве двойственной задачи.

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

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

Поскольку каждое неравенство может быть заменено на равенство и дополнительную переменную, это означает, что каждая переменная прямой задачи соответствует двойственной дополнительной переменной, а каждая двойственная переменная соответствует прямой дополнительной переменной. Это отношение позволяет нам говорить о взаимодополнительности дополнительных переменных.

=== Недопустимая задача ===
Задача линейного программирования может также быть неограниченной или недопустимой. Теория двойственности говорит нам, что:

* Если прямая задача является неограниченной, то двойственная задача недопустима;
* Если двойственная задача является неограниченной, то прямая задача недопустима{{sfn|Юдин, Гольштейн|1969|с=162, Лемма 5.3}}.

Однако может быть, что обе задачи, как двойственная, так и прямая, недопустимы. Вот пример:
{|
|-
| colspan="2" | Максимизировать: <math>2x_1 -x_2</math>
|-
| При условиях:
|<math>x_1 -x_2 \leqslant 1</math>
|-
|
|<math>-x_1 +x_2 \leqslant -2</math>
|-
|
|<math>x_1, x_2 \geqslant 0.</math>
|}

== Приложения ==
Теорема о максимальном потоке и минимальном разрезе является специальным случаем теоремы о сильной двойственности — максимизация потока является прямой задачей линейного программирования, а минимизация разреза является двойственной задачей линейного программирования. См. [[Теорема Форда — Фалкерсона|теорему Форда — Фалкерсона]].

Другие теоремы, связанные с графами, могут быть доказаны с помощью теоремы о сильной двойственности, в частности, [[Теорема Кёнига (комбинаторика)|теорема Кёнига]]{{r|Ahmadi}}.

{{не переведено 5|Теорема о минимаксе (теория игр)|Теорема о минимаксе||Minimax theorem}} для игр с нулевой суммой может быть доказана с помощью теоремы о сильной двойственности{{sfn|Gartner, Matousek|2006|с=sub.8.1}}.

== Альтернативный алгоритм ==
Иногда можно найти более интуитивный способ получить двойственную задачу без применения матрицы задачи. Рассмотрим следующую задачу линейного программирования:
: Минимизировать <math> \sum_{i=1}^m c_i x_i + \sum_{j=1}^n d_j t_j </math>
: при условиях
:<math> \sum_{i=1}^m a_{ij} x_i + e_j t_j \geqslant g_j, 1 \leqslant j \leqslant n</math>
: <math> f_i x_i + \sum_{j=1}^n b_{ij} t_j \geqslant h_i, 1 \leqslant i \leqslant m </math>
:<math> x_i \geqslant 0,\, t_j \geqslant 0, 1 \leqslant i \leqslant m, 1 \leqslant j \leqslant n </math>

Мы имеем <math>m + n</math> условий и все переменные неотрицательны. Нам нужно определить <math>m + n</math> двойственных переменных: '''y'''<sub>j</sub> и '''s'''<sub>''i''</sub>. Мы получаем:
: Минимизировать <math> \sum_{i=1}^m c_i x_i + \sum_{j=1}^n d_j t_j </math>
: при условиях
:<math> \sum_{i=1}^m a_{ij} x_i  \cdot y_j + e_j t_j \cdot y_j \geqslant g_j \cdot y_j, 1 \leqslant j \leqslant n </math>
:<math> f_i x_i \cdot s_i + \sum_{j=1}^n b_{ij} t_j \cdot s_i \geqslant h_i \cdot s_i, 1 \leqslant i \leqslant m </math>
:<math> x_i \geqslant 0,\, t_j \geqslant 0, 1 \leqslant i \leqslant m, 1 \leqslant j \leqslant n </math>
: <math> y_j \geqslant 0,\, s_i \geqslant 0, 1 \leqslant j \leqslant n, 1 \leqslant i \leqslant m </math>

Поскольку это задача минимизации, нам хотелось бы получить двойственную задачу, которая является нижней границей прямой задачи. Другими словами, нам хотелось бы, чтобы сумма всех правых частей ограничений была максимальной при условиях, что для каждой переменной прямой задачи сумма её [[коэффициент]]ов не превосходит коэффициента в линейной функции. Например, '''x'''<sub>1</sub> появляется в <math>n + 1</math> ограничениях. Если мы суммируем коэффициенты ограничения, мы получим <math>a_{1,1} \mathbf{y}_1 + a_{1,2} \mathbf{y}_2 + \dots  + a_{1,n} \mathbf{y}_n + f_1 \mathbf{s}_1</math>. Эта сумма должна не превосходить '''c'''<sub>1</sub>. Как результат мы получаем:

: Максимизировать <math> \sum_{j=1}^n g_j y_j + \sum_{i=1}^m h_i s_i </math>
: при ограничениях
:<math> \sum_{j=1}^n a_{ij} y_j + f_i s_i \leqslant c_i, 1 \leqslant i \leqslant m </math>
:<math> e_j y_j + \sum_{i=1}^m b_{ij} s_i \leqslant d_j, 1 \leqslant j \leqslant n </math>
:<math> y_j \geqslant 0,\, s_i \geqslant 0, 1 \leqslant j \leqslant n, 1 \leqslant i \leqslant m </math>

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

== Интерпретации в реальной жизни ==
Теорема двойственности имеет экономическую интерпретацию. Если мы интерпретируем прямую задачу линейного программирования как классическую задачу «распределения ресурсов», её двойственную задачу можно интерпретировать как задачу «оценки ресурсов»<ref>В книге Юдина и Гольштейна для теневых цен используется термин '''предварительные оценки''' (факторов производства).</ref>. См. статью {{нп4|Теневая цена|||Shadow price}}. Об экономической интерпретации двойственной задачи можно почитать также в книге Лунгу{{sfn|Лунгу|2005|с=68 Пункт 5.4}}.

Теорема двойственности имеет и физическую интерпретацию{{sfn|Gartner, Matousek|2006|с=86–87}}.

== Примечания ==
{{примечания|2|refs=
<ref name="Ahmadi">{{Cite web|url=http://www.princeton.edu/~amirali/Public/Teaching/ORF523/S16/ORF523_S16_Lec6_gh.pdf|title=Lecture 6: linear programming and matching|last=A. A. Ahmadi|first=|date=2016|website=Princeton University|archive-url=https://web.archive.org/web/20180921205336/http://www.princeton.edu/~amirali/Public/Teaching/ORF523/S16/ORF523_S16_Lec6_gh.pdf|archive-date=2018-09-21|dead-url=no|access-date=}}</ref>
}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{книга
|ref=Gartner, Matousek
|автор=Jiri Matousek, Bernd Gärtner
|серия=Universitext
|издательство=Springer
|ISBN=3-540-30697-8
|заглавие=Understanding and Using Linear Programming
|год=2006
|страницы=81–104
|ответственный=|издание=|место=|страниц=|isbn=|isbn2=}}
* {{книга
|автор=Юдин Д.Б., Гольштейн Е.Г.
|ref=Юдин, Гольштейн
|заглавие=Линейное программирование (теория, методы и приложения)
|издательство= «Наука»
|год=1969
|место=Москва
|ответственный=|издание=|страницы=|страниц=|isbn=|isbn2=}}
* {{книга
|автор=Лунгу К.Н.
|ref=Лунгу
|заглавие=Линейное программирование. Руководство к решению задач
|место=М.
|издательство=ФИЗМАТЛИТ
|год=2005
|isbn=5-9221-0631-7
|ответственный=|издание=|страницы=|страниц=|isbn2=}}
{{refend}}

{{rq|checktranslate|style}}

[[Категория:Линейное программирование]]