2.2 线性规划模型

引例 某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素．生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如表 2-1-1所示．

表2-1-1某制药厂生产信息表

已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元．但根据市场需求调查的结果，甲药品每周的产量不应超过4吨．问该厂应如何安排两种药品的产量才能使每周获得的利润最大？

分析 设$x_1$、$x_2$分别为生产甲、乙药品的数量，问题的目标为总利润最大，即

$\max 5x_1+2x_2$，

约束条件为

每周资源总量的限制，即$30x_1+20x_2\le 160$，$5x_1+x_2\le 15$；

甲种药品每周产量不应超过4吨，即$x_1\le 4$；

生产数量非负，即决策变量 $x_1\ge 0,x_2\ge 0$．

那么优化模型可整理为

$\begin{array}{rl}& \max 5x_1+2x_2\\ & \text{s.t.}\{\begin{array}{l}30x_1+20x_2\le 160\\ 5x_1+x_2\le 15\\ x_1\le 4\\ x_1\ge 0,x_2\ge 0\end{array}\end{array}.$

通常情况下，线性规划模型的可表示为

$\begin{array}{rl}& \max (\min )z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n\\ & \text{s.t.}\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n\le (=,\ge )b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n\le (=,\ge )b_2\\ \cdots \cdots \\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n\le (=,\ge )b_m\\ x_i\ge 0,i=1,2,\cdots ,n\end{array}\end{array}$，

也可简记为

$$\begin{array}{rl}& \min (\max ){\mathbf{c}}^{\top }\mathbf{x}\\ & \text{s.t.}\{\begin{array}{l}\mathbf{Ax}\le (=,\ge )\mathbf{b}\\ \mathbf{x}\ge 0\end{array}\end{array}$$

其中$\mathbf{x}=\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right)$，$\mathbf{c}=\left(\begin{array}{c}{c}_1\\ c_2\\ ⋮\\ c_n\end{array}\right)$，$\mathbf{A}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ & \cdots & & \\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right)$，$\mathbf{b}=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right)$．

在大多数实际问题建立的线性规划模型中，要求变量是非负的，即$x_i\ge 0,i=1,2,\cdots ,n$，称此约束为非负性约束．