Лемма Фаркаса
Теорема разрешимости конечных систем линейных неравенств

В математике лемма Фаркаша — это теорема о разрешимости конечной системы линейных неравенств . Первоначально она была доказана венгерским математиком Дьюлой Фаркашем . [1] Лемма Фаркаша — это ключевой результат, лежащий в основе двойственности линейного программирования , и сыграла центральную роль в развитии математической оптимизации (альтернативно, математического программирования ). Она используется, среди прочего, в доказательстве теоремы Каруша–Куна–Таккера в нелинейном программировании . [2] Примечательно, что в области основ квантовой теории лемма также лежит в основе полного набора неравенств Белла в форме необходимых и достаточных условий для существования локальной теории скрытых переменных , учитывая данные из любого конкретного набора измерений. [3]

Обобщения леммы Фаркаша касаются теоремы разрешимости выпуклых неравенств, [4] т. е. бесконечной системы линейных неравенств. Лемма Фаркаша относится к классу утверждений, называемых «теоремы альтернативы»: теорема, утверждающая, что ровно одна из двух систем имеет решение. [5]

Утверждение леммы

В литературе имеется ряд несколько отличающихся (но эквивалентных) формулировок леммы. Приведенная здесь формулировка принадлежит Гейлу, Куну и Такеру (1951). [6]

Лемма Фаркаша  —  Пусть и Тогда верно ровно одно из следующих двух утверждений: А ∈ Р м × н {\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n}} б ∈ Р м . {\displaystyle \mathbf {b} \in \mathbb {R} ^{m}.}

  1. Существует такое, что и х ∈ Р н {\displaystyle \mathbf {x} \in \mathbb {R} ^{n}} А х = б {\displaystyle \mathbf {Ax} =\mathbf {b} } х ≥ 0. {\displaystyle \mathbf {x} \geq 0.}
  2. Существует такое, что и у ∈ Р м {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}} А ⊤ у ≥ 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0} б ⊤ у < 0. {\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}

Здесь обозначение означает, что все компоненты вектора неотрицательны. х ≥ 0 {\displaystyle \mathbf {x} \geq 0} х {\displaystyle \mathbf {x} }

Пример

Пусть m , n = 2 , и Лемма гласит, что ровно одно из следующих двух утверждений должно быть верным (в зависимости от b 1 и b 2 ): А = [ 6 4 3 0 ] , {\displaystyle \mathbf {A} ={\begin{bmatrix}6&4\\3&0\end{bmatrix}},} б = [ б 1 б 2 ] . {\displaystyle \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\end{bmatrix}}.}

  1. Существуют x 1 ≥ 0 , x 2 ≥ 0 такие, что 6 x 1 + 4 x 2 = b 1 и 3 x 1 = b 2 , или
  2. Существуют y 1 , y 2 такие, что 6 y 1 + 3 y 2 ≥ 0 , 4 y 1 ≥ 0 и b 1 y 1 + b 2 y 2 < 0 .

Вот доказательство леммы в этом частном случае:

  • Если b 2 ≥ 0 и b 1 − 2 b 2 ≥ 0 , то вариант 1 верен, так как решение линейных уравнений равно , а вариант 2 ложен, так как если правая часть положительна, то левая часть тоже должна быть положительной. х 1 = б 2 3 {\displaystyle x_{1}={\tfrac {b_{2}}{3}}} х 2 = б 1 − 2 б 2 4 . {\displaystyle x_{2}={\tfrac {b_{1}-2b_{2}}{4}}.} б 1 у 1 + б 2 у 2 ≥ б 2 ( 2 у 1 + у 2 ) = б 2 6 у 1 + 3 у 2 3 , {\displaystyle b_{1}y_{1}+b_{2}y_{2}\geq b_{2}(2y_{1}+y_{2})=b_{2}{\frac {6y_{1} +3y_{2}}{3}},}
  • В противном случае вариант 1 неверен, так как единственное решение линейных уравнений не является слабоположительным. Но в этом случае вариант 2 верен:
    • Если b 2 < 0 , то можно взять, например, y 1 = 0 и y 2 = 1 .
    • Если b 1 − 2 b 2 < 0 , то для некоторого числа B > 0 b 1 = 2 b 2 − B , так что: Таким образом, мы можем взять, например, y 1 = 1 , y 2 = −2 . б 1 у 1 + б 2 у 2 = 2 б 2 у 1 + б 2 у 2 − Б у 1 = б 2 6 у 1 + 3 у 2 3 − Б у 1 . {\displaystyle b_{1}y_{1}+b_{2}y_{2}=2b_{2}y_{1}+b_{2}y_{2}-By_{1}=b_{2}{\frac {6y_{1}+3y_{2}}{3}}-By_{1}.}

Геометрическая интерпретация

Рассмотрим замкнутый выпуклый конус , натянутый на столбцы A ; то есть, С ( А ) {\displaystyle C(\mathbf {A} )}

С ( А ) = { А х ∣ х ≥ 0 } . {\displaystyle C(\mathbf {A})=\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \geq 0\}.}

Заметим, что есть множество векторов b, для которых выполняется первое утверждение в формулировке леммы Фаркаша. С другой стороны, вектор y во втором утверждении ортогонален гиперплоскости , которая разделяет b и Лемма следует из наблюдения, что b принадлежит тогда и только тогда, когда нет гиперплоскости, которая разделяет его с С ( А ) {\displaystyle C(\mathbf {A} )} С ( А ) . {\displaystyle C(\mathbf {A}).} С ( А ) {\displaystyle C(\mathbf {A} )} С ( А ) . {\displaystyle C(\mathbf {A}).}

Точнее, пусть обозначают столбцы матрицы A. В терминах этих векторов лемма Фаркаша утверждает, что верно ровно одно из следующих двух утверждений: а 1 , … , а н ∈ Р м {\displaystyle \mathbf {a} _{1},\dots ,\mathbf {a} _{n}\in \mathbb {R} ^{m}}

  1. Существуют неотрицательные коэффициенты, такие что х 1 , … , х н ∈ Р {\displaystyle x_{1},\dots ,x_{n}\in \mathbb {R} } б = х 1 а 1 + ⋯ + х н а н . {\displaystyle \mathbf {b} =x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}.}
  2. Существует вектор такой, что для и у ∈ Р м {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}} а я ⊤ у ≥ 0 {\displaystyle \mathbf {a} _{i}^{\top }\mathbf {y} \geq 0} я = 1 , … , н , {\displaystyle i=1,\точки ,n,} б ⊤ у < 0. {\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}

Суммы с неотрицательными коэффициентами образуют конус, натянутый на столбцы матрицы A. Следовательно, первое утверждение говорит, что b принадлежит х 1 а 1 + ⋯ + х н а н {\displaystyle x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}} х 1 , … , х н {\displaystyle x_{1},\точки ,x_{n}} С ( А ) . {\displaystyle C(\mathbf {A}).}

Второе утверждение говорит о том, что существует вектор y такой, что угол y с векторами a i не превышает 90°, а угол y с вектором b больше 90°. Гиперплоскость, нормальная к этому вектору, имеет векторы a i с одной стороны и вектор b с другой стороны. Следовательно, эта гиперплоскость отделяет конус, натянутый на , от вектора b . а 1 , … , а н {\displaystyle \mathbf {a} _{1},\dots ,\mathbf {a} _{n}}

Например, пусть n , m = 2 , a 1 = (1, 0) T , и a 2 = (1, 1) T . Выпуклый конус, натянутый на a 1 и a 2 , можно рассматривать как клиновидный срез первого квадранта в плоскости xy . Теперь предположим, что b = (0, 1) . Конечно, b не находится в выпуклом конусе a 1 x 1 + a 2 x 2 . Следовательно, должна быть разделяющая гиперплоскость. Пусть y = (1, −1) T . Мы можем видеть, что a 1 · y = 1 , a 2 · y = 0 , и b · y = −1 . Следовательно, гиперплоскость с нормалью y действительно отделяет выпуклый конус a 1 x 1 + a 2 x 2 от b .

Логическая интерпретация

Особенно наводящая на размышления и легко запоминающаяся версия такова: если набор линейных неравенств не имеет решения, то противоречие может быть получено из него с помощью линейной комбинации с неотрицательными коэффициентами. В формулах: если неразрешимо, то имеет решение. [7] Обратите внимание, что является комбинацией левых частей, комбинацией правых частей неравенств. Поскольку положительная комбинация дает нулевой вектор слева и −1 справа, противоречие очевидно. А х ≤ б {\displaystyle \mathbf {Ax} \leq \mathbf {b} } у ⊤ А = 0 , {\displaystyle \mathbf {y} ^{\top }\mathbf {A} =0,} у ⊤ б = − 1 , {\displaystyle \mathbf {y} ^{\top }\mathbf {b} =-1,} у ≥ 0 {\displaystyle \mathbf {y} \geq 0} у ⊤ А {\displaystyle \mathbf {y} ^{\top }\mathbf {A} } у ⊤ б {\displaystyle \mathbf {y} ^{\top }\mathbf {b} }

Таким образом, лемму Фаркаша можно рассматривать как теорему логической полноты : представляет собой набор «аксиом», линейные комбинации являются «правилами вывода», и лемма утверждает, что если набор аксиом противоречив, то его можно опровергнуть с помощью правил вывода. [8] : 92–94  А х ≤ б {\displaystyle \mathbf {Ax} \leq \mathbf {b} }

Последствия для теории сложности

Из леммы Фаркаша следует, что задача принятия решения «Дана система линейных уравнений, имеет ли она неотрицательное решение?» находится на пересечении NP и co-NP . Это потому, что, согласно лемме, как ответ «да», так и ответ «нет» имеют доказательство, которое может быть проверено за полиномиальное время. Задачи на пересечении также называются хорошо охарактеризованными задачами . Это давний открытый вопрос, равно ли P. В частности, вопрос о том, имеет ли система линейных уравнений неотрицательное решение, не был известен как находящийся в P, пока он не был доказан с помощью метода эллипсоида . [9] : 25  Н П ∩ с о Н П {\displaystyle NP\cap coNP} Н П ∩ с о Н П {\displaystyle NP\cap coNP}

Варианты

Лемма Фаркаша имеет несколько вариантов с различными ограничениями знака (первый из них является оригинальной версией): [8] : 92 

  • Либо имеет решение , либо имеет решение с А х = б {\displaystyle \mathbf {Ax} =\mathbf {b} } х ≥ 0 , {\displaystyle \mathbf {x} \geq 0,} А ⊤ у ≥ 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0} у ∈ Р м {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}} б ⊤ у < 0. {\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}
  • Либо имеет решение , либо имеет решение с А х ≤ б {\displaystyle \mathbf {Ax} \leq \mathbf {b} } х ≥ 0 , {\displaystyle \mathbf {x} \geq 0,} А ⊤ у ≥ 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0} у ≥ 0 {\displaystyle \mathbf {y} \geq 0} б ⊤ у < 0 {\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0}
  • Либо имеет решение , либо имеет решение с . А х ≤ б {\displaystyle \mathbf {Ax} \leq \mathbf {b} } х ∈ Р н , {\displaystyle \mathbf {x} \in \mathbb {R} ^{n},} А ⊤ у = 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0} у ≥ 0 {\displaystyle \mathbf {y} \geq 0} б ⊤ у < 0 {\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0}
  • Либо имеет решение , либо имеет решение с А х = б {\displaystyle \mathbf {Ax} =\mathbf {b} } х ∈ Р н , {\displaystyle \mathbf {x} \in \mathbb {R} ^{n},} А ⊤ у = 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0} у ∈ Р м {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}} б ⊤ у ≠ 0. {\displaystyle \mathbf {b} ^{\top }\mathbf {y} \neq 0.}

Последний вариант упомянут для полноты; на самом деле это не "лемма Фаркаса", поскольку она содержит только равенства. Ее доказательство — упражнение по линейной алгебре .

Существуют также леммы типа Фаркаса для целочисленных программ. [9] : 12--14  Для систем уравнений лемма проста:

  • Предположим, что A и b имеют рациональные коэффициенты. Тогда либо имеет целочисленное решение , либо существует такое, что является целым и не является целым. А х = б {\displaystyle \mathbf {Ax} =\mathbf {b} } х ∈ З н , {\displaystyle \mathbf {x} \in \mathbb {Z} ^{n},} у ∈ Р н {\displaystyle \mathbf {y} \in \mathbb {R} ^{n}} А ⊤ у {\displaystyle \mathbf {A} ^{\top }\mathbf {y} } б ⊤ у {\displaystyle \mathbf {b} ^{\top }\mathbf {y} }

Для систем неравенств лемма гораздо сложнее. Она основана на следующих двух правилах вывода :

  1. При наличии неравенств и коэффициентов выведите неравенство . а 1 Т х ≤ б 1 , … , а м Т х ≤ б м {\displaystyle a_{1}^{T}x\leq b_{1},\ldots ,a_{m}^{T}x\leq b_{m}} ж 1 , … , ж м {\displaystyle w_{1},\ldots ,w_{m}} ( ∑ я = 1 м ж я а я Т ) х ≤ ∑ я = 1 м ж я б я {\displaystyle \left(\sum _{i=1}^{m}w_{i}a_{i}^{T}\right)x\leq \sum _{i=1}^{m}w_{i}b_{i}}
  2. Дано неравенство , выведите неравенство . а 1 х 1 + ⋯ + а м х м ≤ б {\displaystyle a_{1}x_{1}+\cdots +a_{m}x_{m}\leq b} ⌊ а 1 ⌋ х 1 + ⋯ + ⌊ а м ⌋ х м ≤ ⌊ б ⌋ {\displaystyle \lfloor a_{1}\rfloor x_{1}+\cdots +\lfloor a_{m}\rfloor x_{m}\leq \lfloor b\rfloor }

Лемма гласит, что:

  • Предположим, что A и b имеют рациональные коэффициенты. Тогда либо имеет целочисленное решение , либо можно вывести из конечного числа применений правил вывода 1,2 неравенство . A x ≤ b {\displaystyle \mathbf {Ax} \leq \mathbf {b} } x ∈ Z n , x ≥ 0 {\displaystyle \mathbf {x} \in \mathbb {Z} ^{n},x\geq 0} A x ≤ b {\displaystyle \mathbf {Ax} \leq \mathbf {b} } 0 T x ≤ − 1 {\displaystyle 0^{T}x\leq -1}

Варианты обобщены в таблице ниже.

СистемаОграничения по xАльтернативная системаОграничения по y
A x = b {\displaystyle \mathbf {Ax} =\mathbf {b} } x ∈ R n , x ≥ 0 {\displaystyle \mathbf {x} \in \mathbb {R} ^{n},x\geq 0} A ⊤ y ≥ 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0} , b ⊤ y < 0 {\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0} y ∈ R m {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}
A x ≤ b {\displaystyle \mathbf {Ax} \leq \mathbf {b} } x ∈ R n , x ≥ 0 {\displaystyle \mathbf {x} \in \mathbb {R} ^{n},x\geq 0} A ⊤ y ≥ 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0} , b ⊤ y < 0 {\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0} y ∈ R m {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}} , y ≥ 0 {\displaystyle \mathbf {y} \geq 0}
A x ≤ b {\displaystyle \mathbf {Ax} \leq \mathbf {b} } x ∈ R n {\displaystyle \mathbf {x} \in \mathbb {R} ^{n}} A ⊤ y = 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0} , b ⊤ y < 0 {\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0} y ∈ R m {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}} , y ≥ 0 {\displaystyle \mathbf {y} \geq 0}
A x = b {\displaystyle \mathbf {Ax} =\mathbf {b} } x ∈ R n {\displaystyle \mathbf {x} \in \mathbb {R} ^{n}} A ⊤ y = 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0} , b ⊤ y ≠ 0 {\displaystyle \mathbf {b} ^{\top }\mathbf {y} \neq 0} y ∈ R m {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}
A x = b {\displaystyle \mathbf {Ax} =\mathbf {b} } x ∈ Z n {\displaystyle \mathbf {x} \in \mathbb {Z} ^{n}} A ⊤ y {\displaystyle \mathbf {A} ^{\top }\mathbf {y} } интегральный, не интегральный b ⊤ y {\displaystyle \mathbf {b} ^{\top }\mathbf {y} } y ∈ R n {\displaystyle \mathbf {y} \in \mathbb {R} ^{n}}
A x ≤ b {\displaystyle \mathbf {Ax} \leq \mathbf {b} } x ∈ Z n , x ≥ 0 {\displaystyle \mathbf {x} \in \mathbb {Z} ^{n},x\geq 0} 0 T x ≤ − 1 {\displaystyle 0^{T}x\leq -1} можно сделать вывод из A x ≤ b {\displaystyle \mathbf {Ax} \leq \mathbf {b} }

Обобщения

Обобщенная лемма Фаркаша  —  Пусть — замкнутый выпуклый конус в , а двойственный конус — Если выпуклый конус замкнут, то верно ровно одно из следующих двух утверждений: A ∈ R m × n , {\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n},} b ∈ R m , {\displaystyle \mathbf {b} \in \mathbb {R} ^{m},} S {\displaystyle \mathbf {S} } R n , {\displaystyle \mathbb {R} ^{n},} S {\displaystyle \mathbf {S} } S ∗ = { z ∈ R n ∣ z ⊤ x ≥ 0 , ∀ x ∈ S } . {\displaystyle \mathbf {S} ^{*}=\{\mathbf {z} \in \mathbb {R} ^{n}\mid \mathbf {z} ^{\top }\mathbf {x} \geq 0,\forall \mathbf {x} \in \mathbf {S} \}.} C ( A ) = { A x ∣ x ∈ S } {\displaystyle C(\mathbf {A} )=\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \in \mathbf {S} \}}

  1. Существует такое, что и x ∈ R n {\displaystyle \mathbf {x} \in \mathbb {R} ^{n}} A x = b {\displaystyle \mathbf {Ax} =\mathbf {b} } x ∈ S . {\displaystyle \mathbf {x} \in \mathbf {S} .}
  2. Существует такое, что и y ∈ R m {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}} A ⊤ y ∈ S ∗ {\displaystyle \mathbf {A} ^{\top }\mathbf {y} \in \mathbf {S} ^{*}} b ⊤ y < 0. {\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}

Обобщенную лемму Фаркаша можно интерпретировать геометрически следующим образом: либо вектор находится в заданном замкнутом выпуклом конусе , либо существует гиперплоскость, отделяющая вектор от конуса; других возможностей нет. Условие замкнутости необходимо, см. Теорему разделения I в Теореме разделения гиперплоскости . Для исходной леммы Фаркаша — неотрицательный ортант , следовательно, условие замкнутости выполняется автоматически. Действительно, для многогранного выпуклого конуса, т. е. существует такое , что условие замкнутости выполняется автоматически. В выпуклой оптимизации различные виды квалификации ограничений, например, условие Слейтера , отвечают за замкнутость базового выпуклого конуса S {\displaystyle \mathbf {S} } R + n , {\displaystyle \mathbb {R} _{+}^{n},} B ∈ R n × k {\displaystyle \mathbf {B} \in \mathbb {R} ^{n\times k}} S = { B x ∣ x ∈ R + k } , {\displaystyle \mathbf {S} =\{\mathbf {B} \mathbf {x} \mid \mathbf {x} \in \mathbb {R} _{+}^{k}\},} C ( A ) . {\displaystyle C(\mathbf {A} ).}

Полагая и в обобщенной лемме Фаркаша, получаем следующее следствие о разрешимости конечной системы линейных равенств: S = R n {\displaystyle \mathbf {S} =\mathbb {R} ^{n}} S ∗ = { 0 } {\displaystyle \mathbf {S} ^{*}=\{0\}}

Следствие  —  Пусть и Тогда верно только одно из следующих двух утверждений: A ∈ R m × n {\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n}} b ∈ R m . {\displaystyle \mathbf {b} \in \mathbb {R} ^{m}.}

  1. Существует такое, что x ∈ R n {\displaystyle \mathbf {x} \in \mathbb {R} ^{n}} A x = b . {\displaystyle \mathbf {Ax} =\mathbf {b} .}
  2. Существует такое, что и y ∈ R m {\displaystyle \mathbf {y} \in \mathbb {R} ^{m}} A ⊤ y = 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0} b ⊤ y ≠ 0. {\displaystyle \mathbf {b} ^{\top }\mathbf {y} \neq 0.}

Дальнейшие последствия

Лемму Фаркаша можно преобразовать во множество других теорем об альтернативах с помощью простых модификаций, [5] таких как теорема Гордана : либо имеет решение x , либо имеет ненулевое решение y с y ≥ 0 . A x < 0 {\displaystyle \mathbf {Ax} <0} A ⊤ y = 0 {\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0}

Распространенные приложения леммы Фаркаша включают доказательство теоремы сильной двойственности, связанной с линейным программированием , и условий Каруша–Куна–Таккера . Расширение леммы Фаркаша может быть использовано для анализа условий сильной двойственности для и построения двойственной для полуопределенной программы. Достаточно доказать существование условий Каруша–Куна–Таккера с помощью альтернативы Фредгольма, но для того, чтобы условие было необходимым, нужно применить теорему фон Неймана о минимаксе , чтобы показать, что уравнения, выведенные Коши, не нарушаются.

Смотрите также

Примечания

  1. ^ Фаркас, Юлиус (Дьюла) (1902), "Theorie der Einfachen Ungleichungen", Journal für die reine und angewandte Mathematik , 1902 (124): 1–27, doi : 10.1515/crll.1902.124.1, S2CID  115770124
  2. ^ Такаяма, Акира (1985). Математическая экономика (2-е изд.). Нью-Йорк: Cambridge University Press. стр. 48. ISBN 0-521-31498-4.
  3. ^ Гарг, Анупам ; Мермин, НД (1984), «Лемма Фаркаса и природа реальности: статистические следствия квантовых корреляций», Основы физики , 14 : 1–39, doi :10.1007/BF00741645, S2CID  123622613
  4. ^ Динь, Н.; Джеякумар, В. (2014), «Лемма Фаркаса о трех десятилетиях обобщений для математической оптимизации», TOP , 22 (1): 1–22, doi :10.1007/s11750-014-0319-y, S2CID  119858980
  5. ^ ab Border, KC (2013). "Альтернативные линейные неравенства" (PDF) . Получено 29.11.2021 .
  6. ^ Гейл, Дэвид ; Кун, Гарольд ; Такер, Альберт В. (1951), «Линейное программирование и теория игр — Глава XII» (PDF) , в Koopmans (ред.), Анализ деятельности по производству и распределению , Wiley. См. Лемму 1 на стр. 318.
  7. ^ Бойд, Стивен П.; Ванденберг, Ливен (2004), "Раздел 5.8.3" (pdf) , Выпуклая оптимизация , Cambridge University Press, ISBN 978-0-521-83378-3, получено 15 октября 2011 г..
  8. ^ аб Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8.Страницы 81–104.
  9. ^ аб Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер документа : 10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, г-н  1261419

Дальнейшее чтение

  • Goldman, AJ; Tucker, AW (1956). «Многогранные выпуклые конусы». В Kuhn, HW; Tucker, AW (ред.). Линейные неравенства и родственные системы . Princeton: Princeton University Press. стр. 19–40. ISBN 0691079994.
  • Рокафеллар, Р. Т. (1979). Выпуклый анализ . Princeton University Press. стр. 200.
  • Кутателадзе С.С. Еще раз о лемме Фаркаша // Сибирский математический журнал , 2010, т. 51, № 1, 78–87.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Farkas%27_lemma&oldid=1199983963"