18.1.1 问题的提法和几何表达

18.1.1.1 线性规划问题的形式

1. 目的

线性规划的目的是寻找有穷个变量的线性目标函数(OF) 在有穷个线性方程或不等式约束(CT) 限制下的最大值或最小值.

许多实际问题都可以直接叙述为线性规划问题, 或者用线性规划问题近似建模.

2. 一般形式线性规划问题的一般形式是

OF: $f\left(\underset{―}{\mathbf{x}}\right)=c_1{x}_1+\cdots +c_r{x}_r+c_{r+1}{x}_{r+1}+\cdots +c_n{x}_n=max$ ! (18.1a)

$$\begin{array}{ccccc}⋮& & ⋮& & ⋮\\ a_{1,1}{x}_1+\cdots +a_{1,r}{x}_r+a_{1,r+1}+\cdots +a_{1,n}{x}_n\le b_1,& & & & \\ ⋮& & ⋮& & ⋮\\ a_{s,1}{x}_1+\cdots +a_{s,r}{x}_r+a_{s,r+1}{x}_{r+1}+\cdots +a_{s,n}{x}_n\le b_s,& & & & \\ a_{s+1,1}{x}_1+\cdots +a_{s+1,r}{x}_r+a_{s+1,r+1}{x}_{r+1}+\cdots +a_{s+1,n}{x}_n=b_{s+1,r},& & & & \\ ⋮& & ⋮& & ⋮\\ a_{m,1}{x}_1+\cdots +a_{m,r}{x}_r+a_{m,r+1}{x}_{r+1}+\cdots +a_{m,n}{x}_n=b_{m,r},& & & & \\ ⋮& & ⋮& & \\ a_{m,1}{x}_1+\cdots +a_{m,r}{x}_r+a_{m,r+1}{x}_{r+1}+\cdots +a_{m,n}{x}_n=b_{m,r},& & & & \\ x_1\ge 0,& & \cdots & x_{m,r}\ge 0,x_{m+1,r}{x}_{m+2}=\cdots ,x_m\ge 0.& \end{array}\}$$

(18.1b)

采用更紧凑的向量记号, 上述问题可以写成

OF: $f\left(\underset{―}{\mathbf{x}}\right)={\underset{―}{\mathbf{c}}}^{1^{\mathrm{T}}}{\underset{―}{\mathbf{x}}}^1+{\underset{―}{\mathbf{c}}}^{2^{\mathrm{T}}}{\underset{―}{\mathbf{x}}}^2=max$ !(18.2a)

$$\begin{array}{}\text{(18.2b)}& \begin{array}{cc}\text{ CT: }& {\mathbf{A}}_{11}{\underset{―}{\mathbf{x}}}^1+{\mathbf{A}}_{12}{\underset{―}{\mathbf{x}}}^2\le {\underset{―}{\mathbf{b}}}^1,\\ & {\mathbf{A}}_{21}{\underset{―}{\mathbf{x}}}^1+{\mathbf{A}}_{22}{\underset{―}{\mathbf{x}}}^2={\underset{―}{\mathbf{b}}}^2,\\ & {\underset{―}{\mathbf{x}}}^1\ge \underset{―}{\mathbf{0}},{\underset{―}{\mathbf{x}}}^2\text{ 自由. }\end{array}\}\end{array}$$

这里使用如下记号:

$$\begin{array}{}\text{(18.2c)}& {\underset{―}{\mathbf{c}}}^1=\left[\begin{array}{c}{c}_1\\ c_2\\ ⋮\\ c_r\end{array}\right],{\underset{―}{\mathbf{c}}}^2=\left[\begin{array}{c}{c}_{r+1}\\ c_{r+2}\\ ⋮\\ c_n\end{array}\right],{\underset{―}{\mathbf{x}}}^1=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_r\end{array}\right],{\underset{―}{\mathbf{x}}}^2=\left[\begin{array}{c}{x}_{r+1}\\ x_{r+2}\\ ⋮\\ x_n\end{array}\right],\end{array}$$$${\mathbf{A}}_{11}=\left[\begin{array}{cccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,r}\\ a_{2,1}& a_{2,2}& \cdots & a_{2,r}\\ ⋮& ⋮& & ⋮\\ a_{s,1}& a_{s,2}& \cdots & a_{s,r}\end{array}\right]$$$$\begin{array}{}\text{(18.2d)}& {\mathbf{A}}_{12}=\left[\begin{array}{cccc}{a}_{1,r+1}& a_{1,r+2}& \cdots & a_{1,n}\\ a_{2,r+1}& a_{2,r+2}& \cdots & a_{2,n}\\ ⋮& ⋮& & ⋮\\ a_{s,r+1}& a_{s,r+2}& \cdots & a_{s,n}\end{array}\right],\end{array}$$$${\mathbf{A}}_{21}=\left[\begin{array}{cccc}{a}_{s+1,1}& a_{s+1,2}& \cdots & a_{s+1,r}\\ a_{s+2,1}& a_{s+2,2}& \cdots & a_{s+2,r}\\ ⋮& ⋮& & ⋮\\ a_{m,1}& a_{m,2}& \cdots & a_{m,r}\end{array}\right]$$$$\begin{array}{}\text{(18.2e)}& {\mathbf{A}}_{22}=\left[\begin{array}{cccc}{a}_{s+1,r+1}& a_{s+1,r+2}& \cdots & a_{s+1,n}\\ a_{s+2,r+1}& a_{s+2,r+2}& \cdots & a_{s+2,n}\\ ⋮& ⋮& & ⋮\\ a_{m,r+1}& a_{m,r+2}& \cdots & a_{m,n}\end{array}\right].\end{array}$$

3. 约束

对于不等号 “ $\ge$ ” 的约束,只要乘以(-1),就变成上面形式的约束.

4. 极小问题

对于极小问题 $f\left(\underset{―}{x}\right)=min$ !,通过目标函数乘以(-1),就变成等价的极大问题

$$\begin{array}{}\text{(18.3)}& -f\left(\underset{―}{\mathbf{x}}\right)=max!\end{array}$$

5. 整数规划

有时候某些变量仅限于取整数值. 这里我们不讨论这样的离散问题.

6. 仅含非负变量和松弛变量情形的表达

在应用某些解法时, 仅仅考虑非负变量, 以及以等式形式给出的约束 (18.1b) 和 (18.2b).

$$\begin{array}{}\text{(18.4a)}& \text{OF:}f\left(\underset{―}{\mathbf{x}}\right)=c_1{x}_1+\cdots +c_r{x}_r+c_{r+1}{x}_{r+1}+\cdots +c_n{x}_n=max\text{!}\end{array}$$$$\begin{array}{}\text{(18.4b)}& \begin{array}{c}{a}_{1,1}{x}_1+\cdots +a_{1,n}{x}_n=b_1,\\ ⋮\\ a_{m,1}{x}_1+\cdots +a_{m,n}{x}_n=b_m,\\ x_1\ge 0,\cdots ,x_n\ge 0.\end{array}\}\end{array}$$

每个自由变量 $x_k$ 必须分解成两个非负变量之差 $x_k=x_k^1-x_k^2$ . 通过增加非负变量, 不等式变成等式; 这些新增的变量称作松弛变量. 这就是说, 问题可以在 (18.4a, 18.4b) 给出的形式下进行研究,这里 $n$ 是增加了的变量数. 写成向量形式为

OF: $f\left(\underset{―}{\mathbf{x}}\right)={\underset{―}{\mathbf{c}}}^{\mathrm{T}}\underset{―}{\mathbf{x}}=max$ !(18.5a)

CT: $\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}},\underset{―}{\mathbf{x}}\ge \underset{―}{\mathbf{0}}$ .(18.5b)

一般可以假定 $m\le n$ ,否则,方程组会包含线性相关或相互矛盾的方程.

7. 可行集

所有满足 (18.2b) 的向量集合称作原问题的可行集. 如果自由变量做如上改写, 每个形如 “ $\le$ ” 的不等式都改写成如 (18.4a) 和 (18.4b) 的等式,于是所有满足约束条件的非负向量 $\underset{―}{x}\ge \underset{―}{0}$ 的向量的集合称作可行集 $M$ :

$$\begin{array}{}\text{(18.6a)}& M=\left\{\underset{―}{\mathbf{x}}\in {\mathbb{R}}^n:\underset{―}{\mathbf{x}}\ge \underset{―}{\mathbf{0}},\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}\right\}.\end{array}$$

如果点 ${\underset{―}{x}}^{\ast }\in M$ 满足

$$\begin{array}{}\text{(18.6b)}& f\left({\underset{―}{\mathbf{x}}}^{\ast }\right)\ge f\left(\underset{―}{\mathbf{x}}\right),\mathrm{\forall }\underset{―}{\mathbf{x}}\in M,\end{array}$$

则 ${\underset{―}{x}}^{\ast }$ 称作线性规划问题的极大点或解点. 显然, ${\underset{―}{x}}^{\ast }$ 的非松弛变量分量构成原问题的解.

18.1.1.2 例子和图解法

1. 生产两个产品的例子

假定为了生产两个产品 $E_1$ 和 $E_2$ 需要原材料 $R_1,R_2$ 和 $R_3$ . 表 18.1 表明为了生产 $E_1$ 和 $E_2$ 每一个单位产品需要多少单位的原材料,并且还给出了可利用的原材料总数.

表 18.1

	$R_1/E_i$	$R_2/E_i$	$R_3/E_i$
$E_1$	12	8	0
$E_2$	6	12	10
总数	630	620	350

售出一个单位 $E_1$ 或 $E_2$ 产品分别可以获得 20 或 60 单位利润 (PR). 要求确定一个生产计划,使得在至少生产 10 个单位 $E_1$ 产品的前提下,获得最大利润.

现在设 $x_1$ 和 $x_2$ 表示生产产品 $E_1$ 和 $E_2$ 的单位数,问题就是

OF: $f\left(\underset{―}{\mathbf{x}}\right)=20x_1+60x_2=max$ !

$$12x_1+6x_2\le 630,$$$$8x_1+12x_2\le 620,$$$$10x_2\le 350,$$$$x_1\ge 10\text{.}$$

引入松弛变量 $x_3,x_4,x_5,x_6$ ,得到

$$\text{OF:}f\left(\underset{―}{\mathbf{x}}\right)=20x_1+60x_2+0\cdot x_3+0\cdot x_4+0\cdot x_5+0\cdot x_6=max\text{!}$$

CT:

$$12x_1+6x_2+x_3=630,$$$$8x_1+12x_2+x_4=620,$$$$10x_2+x_5=350,$$$$-x_1+x_6=-10.$$

2. 线性规划问题的性质

基于这个例子, 可以用图表示法来说明线性规划问题的某些性质. 这里不考虑松弛变量, 仅使用原始变量.

a) 直线 $a_1{x}_1+a_2{x}_2=b$ 把 $x_1,x_2$ 平面分成两个半平面. 满足不等式 $a_1{x}_1+$ $a_2{x}_2\le b$ 的点 $\left(x_1,x_2\right)$ 在其中的一个半平面中. 在笛卡儿坐标下,可以通过直线作出这个点集的图表示. 箭头表示包含该不等式解的半平面. 可行解集 $M$ ,即满足所有不等式的点集是这些半平面的交 (图 18.1). 在这个例子中, $M$ 的点构成一多边形区域. $M$ 无界或为空集都是有可能的. 如果有多于两条边界直线通过这个多边形的一个顶点, 则此顶点就称作退化的 (图 18.2).

b) $x_1,x_2$ 平面中满足等式 $f\left(x\right)=20x_1+60x_2=c_0$ 的每个点都在一条直线上,即与值 $c_0$ 相关的水平线上. 选择不同的 $c_0$ ,就得到一族平行的直线,在其每一条直线上, 目标函数的值是常数. 几何上, 规划问题的解应该是这样一些点, 它们属于可行集 $M$ ,也位于水平线 $20x_1+60x_2=c_0,c_0$ 为最大值. 在这个例子中,解点是 $\left(x_1,x_2\right)=\left(25,35\right)$ ,位于直线 $20x_1+60x_2=2600$ . 水平线示于图 18.3 中,这里箭头指向目标函数值增加的方向.

显然,如果可行集 $M$ 有界,那么至少有一个顶点使得目标函数取到最大值. 如果可行集 $M$ 无界,则有可能目标函数也无界.