Preliminaries

1.1 Standard form LP

  关键元素：

1.$n$个variables：$x_1，x_2,\dots ,x_n$

2.1个objective function：$\mathbf{z}=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$

3.$m$个constraints：

$$\begin{array}{rl}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n=& b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n=& b_2\\ ⋮& \\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n=& b_m\end{array}$$

4.非负：$x_1\ge 0,x_2\ge 0,\dots ,x_n\ge 0,$

Explicit form

  Minimize $\mathbf{z}=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$

  subject to

$$\begin{array}{rl}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n=& b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n=& b_2\\ ⋮& \\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n=& b_m\end{array}$$ $$x_1\ge 0,x_2\ge 0,\dots ,x_n\ge 0$$

Matrix form

cost vector

$$\mathbf{c}=[\begin{array}{cccc}{c}_1& c_2& \cdots & c_n\end{array}{]}^T$$

solution vector

$$\mathbf{x}=[\begin{array}{cccc}{x}_1& x_2& \cdots & x_n\end{array}{]}^T$$

right-hand-side vector

$$\mathbf{b}=[\begin{array}{cccc}{b}_1& b_2& \cdots & b_n\end{array}{]}^T$$

constraint matrix

$$\mathbf{A}=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right]$$ $$\boxed{{\displaystyle \begin{array}{rl}\text{min}& {\mathbf{c}}^T\mathbf{x}\\ \text{s.t.}& \mathbf{Ax}=\mathbf{b}\\ & \mathbf{x}\ge 0.\end{array}}}$$

例-运输问题

一个管理问题：如何用最经济的方法满足顾客的要求？

LP模型：
— 要引入的决策变量有哪些？
— 目标函数是什么？
— 约束条件是什么？

1.2 Embedded assumptions in LP

1.Proportionality Assumption
— no discount
— 没有回收利用的经济效益

2.Additivity Assumption
— 总影响 = 各个变量的影响之和

3.Divisibility Assumption
— 所有的小数/分数都是允许的

3.Certainty Assumption
— 每个参数都是确定的

1.3 Converting to standard form

例

$$\begin{array}{rl}\text{maximize}& 3x_1-2x_2-4|x_3|\\ \text{s.t.}& -x_1+2x_2\le -5\\ & 3x_2-x_3\ge 6\\ & 2x_1+x_3=12\\ & x_1,x_2\ge 0\end{array}$$

Rule 1: Unrestricted (free) variables

$$x_i^{+}=\{\begin{array}{ll}{x}_i,& \text{if }{x}_i\ge 0\\ 0,& \text{otherwise}\end{array}{x}_i^{-}=\{\begin{array}{ll}0,& \text{if }{x}_i\ge 0\\ x_i,& \text{otherwise}\end{array}$$ $$x_i\in \mathcal{R}\iff x_i=x_i^{+}-x_i^{-}{x}_i^{+},x_i^{-}\ge 0$$

— By product: $|x_i|=x_i^{+}+x_i^{-}$

— Potential problem: 要求$x_i^{+}\times x_i^{-}=0$

$$\begin{array}{rl}\text{maximize}& 3x_1-2x_2-4(x_3^{+}+x_3^{-})\\ \text{s.t.}& -x_1+2x_2\le -5\\ & 3x_2-(x_3^{+}-x_3^{-})\ge 6\\ & 2x_1+(x_3^{+}-x_3^{-})=12\\ & x_1,x_2,x_3^{+},x_3^{-}\ge 0\end{array}$$

Rule 2: Inequality constraints

  引入松弛变量和剩余变量

$$\begin{array}{rl}\text{maximize}& 3x_1-2x_2-4(x_3^{+}+x_3^{-})\\ \text{s.t.}& -x_1+2x_2+x_4=-5\\ & 3x_2-(x_3^{+}-x_3^{-})-x_5=6\\ & 2x_1+(x_3^{+}-x_3^{-})=12\\ & x_1,x_2,x_3^{+},x_3^{-},x_4,x_5\ge 0\end{array}$$

Rule 3: Minimization of the objective function

$$\text{max }{\mathbf{c}}^T\mathbf{x}=-\text{min }(-{\mathbf{c}}^T\mathbf{x})$$ $$\begin{array}{rl}\text{minimize}& -3x_1+2x_2+4x_3^{+}+4x_3^{-}\\ \text{s.t.}& -x_1+2x_2+x_4=-5\\ & 3x_2-(x_3^{+}-x_3^{-})-x_5=6\\ & 2x_1+(x_3^{+}-x_3^{-})=12\\ & x_1,x_2,x_3^{+},x_3^{-},x_4,x_5\ge 0\end{array}$$

More on free variable and absolute value

  潜在问题：
1.丢失了二次型约束
2.维数增加
3.原本的一个解对应现在的多个解
4.$|x|$为凸函数，而$-|x|$为凹函数
5.当$\mathbf{c}$为正时，最大化$\mathbf{c}|\mathbf{x}|$可能会成为问题

Reference: ‘Linear' Programming with Absolute-Vaue Functionals. David F. Shanno, Roman L. Weil. Operations Research. Vol. 19. No. 1. (Jan - Feb. 1971). pp. 120-124.