Notes on: Matousek, J., & Gaertner, B. (2007): Understanding and using linear programming¶

View on DouBan

@Book{Mato_lp_07,
  author    = {Matousek, J. and Gaertner, B.},
  title     = {Understanding and using linear programming},
  year      = 2007,
  publisher = {Springer},
  url       = {https://book.douban.com/subject/2883208/},
}

Duality of Linear Programming¶

Proposition 1 (Farkas lemma)

Let \(A\) be a real matrix with \(m\) rows and \(n\) columns, and let \(b \in \mathbb{R}^m\) be a vector. Then exactly one of the following two possibilities occurs:

There exists a vector \(x \in \mathbb{R}^n\) satisfying \(A x = b\) and \(x \geq 0\).
There exists a vector \(y \in \mathbb{R}^m\) such that \(y^{\mathrm{T}} A \geq 0\) and \(y^{\mathrm{T}} b < 0\).

Remark 2

A reader with a systematic mind may like to see the variants of the Farkas lemma summarized in a table:

	The system \(Ax\leq b\)	The system \(Ax=b\)
has a solution \(x\geq 0\) iff	\(y\geq 0, \text{ } y^{\mathrm{T}}A\geq 0\) \(\Rightarrow y^{\mathrm{T}}b\geq 0\)	\(y^{\mathrm{T}}A\geq 0\) \(\Rightarrow y^{\mathrm{T}}b\geq 0\)
has a solution \(x\in\mathbb{R}^n\) iff	\(y\geq 0, \text{ } y^{\mathrm{T}}A=0\) \(\Rightarrow y^{\mathrm{T}}b\geq 0\)	\(y^{\mathrm{T}}A=0\) \(\Rightarrow y^{\mathrm{T}}b=0\)