线性规划是优化问题的特殊情形，其模型中的目标函数和约束条件均为决策变量的线性函数。

列1【合理下料问题】用长度为500厘米的条材，截成长度为98厘米和78厘米两种毛胚，要求长98厘米的毛胚1000根，78厘米长的毛胚2000更，应增氧才能使所用的原材料最少，试建立问题的数学模型。 解一根500厘米的条材截成98厘米和78厘米长度的毛胚有很多种方案，列出方案表如下：

设决策变量xi( 1 ≤ i ≤ 6 1\le i \le6 1≤i≤6)表示第i个方案所用的条材数。目标函数可以表示为： m i n z = x 1 + x 2 + x 3 + x 4 + x 5 + x 6 min z=x_1+x_2+x_3+x_4+x_5+x_6 minz=x1​+x2​+x3​+x4​+x5​+x6​ 约束条件就是 { x 2 + 2 x 3 + 3 x 4 + 4 x 5 + 5 x 6 ≥ 1000 6 x 1 + 5 x 2 + 3 x 3 + 2 x 4 + x 5 ≥ 2000 x 1 , x 2 , … , x 6 ≥ 0 且 取 整 数 \left\{ \begin{array}{c} x_2+2x_3+3x_4+4x_5+5x_6 \ge1000 \\ 6x_1+5x_2+3x_3+2x_4+x_5 \ge2000 \\ x_1,x_2,\ldots,x_6 \ge0且取整数 \end{array} \right. ⎩⎨⎧​x2​+2x3​+3x4​+4x5​+5x6​≥10006x1​+5x2​+3x3​+2x4​+x5​≥2000x1​,x2​,…,x6​≥0且取整数​ 由于是实际问题，决策变量应该取非负整数。

列2【0-1背包问题】一个旅行者要在背包里装一些最有用的旅行物品。背包容积为a，携带物品总质量最多为b。现有物品m件，第j件物品体积为aj，质量为bj（j=1,2,…,m）。为了比较物品的有用程度，假设第j件物品的价值是cj（j=1,2,…,m）。若每件物品只能携带整件，每件物品都能放入背包，并且不考虑放入背包里面的间隙。问旅行者应当携带那几件物品才能使得物品的总价值最大？试建立问题的数学模型。 解每件物品有被选择和不被选择两种可能，为此，设 x j x_j xj​为第j件物品装入的数量，则对应于m件物品引入m个0-1变量：

x j = { 1 , (携带第j件物品) 0 , (不携带第j件物品) （ j = 1 , 2 , . . . , m ） x_j= \begin{cases} 1, & \text{(携带第j件物品)} \\[2ex] 0, & \text{(不携带第j件物品)}（j=1,2,...,m） \end{cases} xj​=⎩⎨⎧​1,0,​(携带第j件物品)(不携带第j件物品)（j=1,2,...,m）​ 目标函数=物品携带的总价值 z = ∑ j = 1 m c j x j z=\sum_{j=1} ^m c_jx_j z=∑j=1m​cj​xj​ 约束条件，所携带的物品总体积不超过a，总质量不超过b 数学模型如下： z= ∑ j = 1 m c j x j \sum_{j=1} ^m c_jx_j ∑j=1m​cj​xj​ s . t . = { ∑ j = 1 m a j x j ≤ a ∑ j = 1 m b j x j ≤ b x j = 0 或 1 （ j = 1 , 2 , . . . , m ） s.t.=\left \{ \begin{array}{c} \sum_{j=1} ^m a_jx_j \le a \\ \\ \sum_{j=1} ^m b_jx_j \le b \\ \\ x_j=0或1（j=1,2,...,m） \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​∑j=1m​aj​xj​≤a∑j=1m​bj​xj​≤bxj​=0或1（j=1,2,...,m）​ 该模型决策变量x只能取0或1，成为0-1整数规划，简称0-1规划。

列3【运输问题】某公司有3个同类产品的工厂（简称产地Ai，i=1,2,3），生产的产品由4个销售点（简称销售地Bi，i=1,2,3,4）销售，各工厂的生产量（用ai表示），各销售点的销量（用bj表示）以及各工厂到销售点的单位产品运价（用cij表示）如表2.3表示。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总的运费最少？ 表2.3 产量、销量与单位产品运价关系表

解本问题中“如何制定调运方案”，就是指的安排一个产地和一个销地各应安排多大的运量，因此令从产地 Ai到销地Bj的运量为xij（i=1,2,3;j=1,2,3,4）作为本问题的决策变量。 目标函数=总运费= z = ∑ i = 1 3 ∑ j = 1 4 c i j x i j z=\sum_{i=1} ^3\sum_{j=1} ^4 c_{ij} x_{ij} z=∑i=13​∑j=14​cij​xij​ 约束条件：由表2.3可知，运输问题的总产量（7+4+9）=总销量（3+6+5+6），所以运输问题是平衡运输问题。第一个约束条件是：各产地运往某一销地的物品数量之和等于该销地的销量，即 ∑ i = 1 3 x i j = b j ( j = 1 , 2 , 3 , 4 ) \sum_{i=1} ^3x_{ij}=b_j(j=1,2,3,4) ∑i=13​xij​=bj​(j=1,2,3,4),第二个约束条件：某一产地运往各销售地的物品数量之和等于该地的产量，即 ∑ j = 1 4 x i j = a i ( i = 1 , 2 , 3 ) \sum_{j=1} ^4x_{ij}=a_i(i=1,2,3) ∑j=14​xij​=ai​(i=1,2,3)，第三个约束条件：决策变量为非负，即 x i j ≥ 0 ( i = 1 , 2 , 3 ; j = 1 , 2 , 3 , 4 ) x_{ij}\ge0(i=1,2,3;j=1,2,3,4) xij​≥0(i=1,2,3;j=1,2,3,4)。 因此数学模型可表述如下： m i n z = ∑ i = 1 3 ∑ j = 1 4 c i j x i j min z=\sum_{i=1} ^3\sum_{j=1} ^4 c_{ij} x_{ij} minz=∑i=13​∑j=14​cij​xij​ s . t . = { ∑ i = 1 3 x i j = b j ( j = 1 , 2 , 3 , 4 ) ∑ j = 1 4 x i j = a i ( i = 1 , 2 , 3 ) x i j ≥ 0 ( i = 1 , 2 , 3 ; j = 1 , 2 , 3 , 4 ) s.t.=\left \{ \begin{array}{c} \sum_{i=1} ^3x_{ij}=b_j(j=1,2,3,4) \\ \\ \sum_{j=1} ^4x_{ij}=a_i(i=1,2,3) \\ \\ x_{ij}\ge0(i=1,2,3;j=1,2,3,4) \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​∑i=13​xij​=bj​(j=1,2,3,4)∑j=14​xij​=ai​(i=1,2,3)xij​≥0(i=1,2,3;j=1,2,3,4)​

一般形式： m a x ( m i n ) z = c 1 x 1 + c 2 x 2 + … + c n x n max(min)z=c_1x_1+c_2x_2+\ldots+c_nx_n max(min)z=c1​x1​+c2​x2​+…+cn​xn​ s . t . = { a 11 x 1 + a 12 x 2 + … + a 1 n x n ≤ ( = , ≥ ) b 1 a 21 x 1 + a 22 x 2 + … + a 2 n x n ≤ ( = , ≥ ) b 2 . . . . . . a m 1 x 1 + a m 2 x 2 + … + a m n x n ≤ ( = , ≥ ) b 2 x 1 , x 2 , . . . , x n ≥ 0 s.t.=\left \{ \begin{array}{c} a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n \le(=,\ge) b_1 \\ \\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n \le(=,\ge) b_2 \\ \\ ......\\\\ a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n \le(=,\ge)b_2\\\\ x_1,x_2,...,x_n\ge0 \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​a11​x1​+a12​x2​+…+a1n​xn​≤(=,≥)b1​a21​x1​+a22​x2​+…+a2n​xn​≤(=,≥)b2​......am1​x1​+am2​x2​+…+amn​xn​≤(=,≥)b2​x1​,x2​,...,xn​≥0​ 标准形式(也就是把一般形式的不等式转换成等式，目标函数一般转化为min方便后面求解)： m i n z = ∑ j = 1 n c j x j min z=\sum_{j=1} ^n c_j x_j minz=∑j=1n​cj​xj​ s . t . = { ∑ j = 1 n a i j x j = b i ( i = 1... , m ) x j ≥ 0 ( j = 1 , . . . , n ) s.t.=\left \{ \begin{array}{c} \sum_{j=1} ^na_{ij}x_j=b_i(i=1...,m) \\ \\ x_j\ge0(j=1,...,n) \end{array} \right. s.t.=⎩⎨⎧​∑j=1n​aij​xj​=bi​(i=1...,m)xj​≥0(j=1,...,n)​ 转化方法： 首先先将x全部转化为 ≥ \ge ≥,之后转变约束条件：对于小于的不等式，加一个松弛变量，对于大于的不等式，减一个松弛变量，之后是：目标函数 m a x 变 m i n max变min max变min，整体乘-1就可以了。 例如：将下列线性规划转化为标准模型 m a x z = 5 x 1 − 2 x 2 + 3 x 3 max z=5x_1-2x_2+3x_3 maxz=5x1​−2x2​+3x3​ s . t . = { 2 x 1 − x 2 + 5 x 3 ≥ − 1 x 1 + x − 3 ≤ 2 x 1 ≤ 0 , x 2 ≥ 0 , x 3 无 约 束 s.t.=\left \{ \begin{array}{c} 2x_1-x_2+5x_3\ge-1 \\ \\ x_1+x-3\le2\\\\ x_1\le0,x_2\ge0,x_3无约束 \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​2x1​−x2​+5x3​≥−1x1​+x−3≤2x1​≤0,x2​≥0,x3​无约束​ 分析： x 1 ≤ 0 于 是 设 x 1 ′ ≥ 0 , x 1 = − x 1 ′ ; x 3 无 约 束 , 设 x 3 ′ , x 3 ′ ′ ≥ 0 , x 3 = x 3 ′ − x 3 ′ ′ x 4 , x 5 ≥ 0 作 为 两 个 不 等 式 的 松 弛 变 量 x_1\le0于是设x_1'\ge0,x_1=-x_1';\\ x_3无约束,设x_3',x_3''\ge0,x_3=x_3'-x_3''\\ x_4,x_5\ge0作为两个不等式的松弛变量 x1​≤0于是设x1′​≥0,x1​=−x1′​;x3​无约束,设x3′​,x3′′​≥0,x3​=x3′​−x3′′​x4​,x5​≥0作为两个不等式的松弛变量 转化标准型为： m i n z ′ = − z = − 5 x 1   + 2 x 2 − 3 x 3 min z' = -z =-5x_1~+2x_2-3x_3 minz′=−z=−5x1​ +2x2​−3x3​ s . t . = { 2 x 1 ′ + x 2 − 5 x 3 ′ + 5 x 3 ′ ′ + x 4 = 1 − x 1 ′ + x 3 ′ − x 3 ′ ′ + x 5 = 2 x 1 ′ , x 2 , x 3 ′ , x 3 ′ ′ , x 4 , x 5 ≥ 0 s.t.=\left \{ \begin{array}{c} 2x_1'+x_2-5x_3'+5x_3''+x_4=1 \\ \\ -x_1'+x_3'-x_3''+x_5=2\\\\ x_1',x_2,x_3',x_3'',x_4,x_5\ge0 \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​2x1′​+x2​−5x3′​+5x3′′​+x4​=1−x1′​+x3′​−x3′′​+x5​=2x1′​,x2​,x3′​,x3′′​,x4​,x5​≥0​

1）单纯形法 理论很复杂直接上题 列1单纯形法求解下列线性规划 m i n z = x 1 − 2 x 2 + x 3 min z=x_1-2x_2+x_3 minz=x1​−2x2​+x3​ s . t . = { x 1 + x 2 − 2 x 3 + x 4 = 10 2 x 1 − x 2 + 4 x 3 ≤ 8 − x 1 + 2 x 2 − 4 x 3 ≤ 4 x j ≥ 0 , j = 1 , 2 , 3 , 4 s.t.=\left \{ \begin{array}{c} x_1+x_2-2x_3+x_4=10 \\ \\ 2x_1-x_2+4x_3\le8\\\\ -x_1+2x_2-4x_3\le4\\\\ x_j\ge0,j=1,2,3,4 \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​+x2​−2x3​+x4​=102x1​−x2​+4x3​≤8−x1​+2x2​−4x3​≤4xj​≥0,j=1,2,3,4​ 解：A转化为标准形式： m i n z = x 1 − 2 x 2 + x 3 + 0 x 4 + 0 x 5 + 0 x 6 min z=x_1-2x_2+x_3+0x_4+0x_5+0x_6 minz=x1​−2x2​+x3​+0x4​+0x5​+0x6​ s . t . = { x 1 + x 2 − 2 x 3 + x 4 = 10 2 x 1 − x 2 + 4 x 3 + x 5 = 8 − x 1 + 2 x 2 − 4 x 3 + x 6 = 4 x j ≥ 0 , j = 1 , 2 , 3 , 4 , 5 , 6 s.t.=\left \{ \begin{array}{c} x_1+x_2-2x_3+x_4=10 \\ \\ 2x_1-x_2+4x_3+x_5=8\\\\ -x_1+2x_2-4x_3+x_6=4\\\\ x_j\ge0,j=1,2,3,4,5,6 \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​+x2​−2x3​+x4​=102x1​−x2​+4x3​+x5​=8−x1​+2x2​−4x3​+x6​=4xj​≥0,j=1,2,3,4,5,6​ B列出单纯形表如下：

Cj表示的是目标函数对应xj的系数，在系数行列式里面选取一个单位矩阵，得到的三个变量就是x4，x5，x6。 b表示的不等式右边的数字 最后一行 ∂ j \partial_j ∂j​是检验数，极小问题的结束条件就是检验数全部都是正数，极大问题的结束条件就是检验数全部都是负数。 ∂ 1 = C j − C B ∗ x 1 = 1 − ( 0 0 0 ) ( 2 − 1 − 1 ) = 1 \partial_1=C_j-C_B*x_1=1- \begin{pmatrix} 0\\ 0\\ 0\\ \end{pmatrix} \begin{pmatrix} 2\\ -1\\ -1\\ \end{pmatrix}=1 ∂1​=Cj​−CB​∗x1​=1−⎝⎛​000​⎠⎞​⎝⎛​2−1−1​⎠⎞​=1 C求解 由于检验数 ∂ j \partial_j ∂j​不全大于0于是选取负数中最小的，在这一列里面找非负的数对应的x就是入基，让b/对应的数，取最小的就是出基。

用x2代替x6,化这个数字2为1，这列其他的数为0继续单纯形法,替代只需要修改变量和系数，即0 x6变成-2 x2，其他的不需要变。 C B x b b x 1 x 2 x 3 x 4 x 5 x 6 0 x 4 8 3 2 0 0 1 0 − 1 2 0 x 5 10 3 2 0 [ 2 ] 0 1 1 2 − 2 x 2 2 − 1 2 1 − 2 0 0 1 2 ∂ j 0 0 − 3 0 0 1 \begin{array}{rrrr|r} &C_B &x_b &b & x_1 & x_2 & x_3 & x_4& x_5 & x_6 \\ \hline\\ & 0 & x_4 & 8 & \frac{3}{2} & 0 & 0 & 1 & 0 & -\frac{1}{2} \\\\ & 0 & x_5 & 10 & \frac{3}{2} & 0 & [2 ]& 0 & 1 & \frac{1}{2} \\\\ & -2 & x_2 & 2 & -\frac{1}{2} & 1 & -2 & 0 & 0 & \frac{1}{2}\\\\ \hline\\ &&\partial_j & & 0 & 0 & -3 & 0 & 0 & 1 \end{array} ​CB​00−2​xb​x4​x5​x2​∂j​​b8102​x1​23​23​−21​0​x2​0010​x3​0[2]−2−3​x4​1000​x5​0100​x6​−21​21​21​1​​ 确 定 入 基 为 x 3 ， 出 基 为 x 5 ， 继 续 单 纯 形 法 为 ： 确定入基为x_3，出基为x_5，继续单纯形法为： 确定入基为x3​，出基为x5​，继续单纯形法为： C B x b b x 1 x 2 x 3 x 4 x 5 x 6 0 x 4 8 3 2 0 0 1 0 − 1 2 1 x 3 5 3 4 0 1 0 1 2 1 4 − 2 x 2 12 1 1 0 0 1 1 ∂ j 9 4 0 0 0 3 2 7 4 \begin{array}{rrrr|r} &C_B &x_b &b & x_1 & x_2 & x_3 & x_4& x_5 & x_6 \\ \hline\\ & 0 & x_4 & 8 & \frac{3}{2} & 0 & 0 & 1 & 0 & -\frac{1}{2} \\\\ & 1 & x_3 & 5 & \frac{3}{4} & 0 & 1& 0 & \frac{1}{2} & \frac{1}{4} \\\\ & -2 & x_2 & 12 & 1 & 1 & 0 & 0 & 1 & 1\\\\ \hline\\ &&\partial_j & & \frac{9}{4} & 0 & 0 & 0 & \frac{3}{2}& \frac{7}{4} \end{array} ​CB​01−2​xb​x4​x3​x2​∂j​​b8512​x1​23​43​149​​x2​0010​x3​0100​x4​1000​x5​021​123​​x6​−21​41​147​​​ 此时所有的 ∂ j ≥ 0 \partial_j\ge0 ∂j​≥0,达到结束条件，此时的b这一行就是x的取值，其他的都是0 x 2 = 12 , x 3 = 5 , x 4 = 8 , x 1 = x 5 = x 6 = 0 x_2=12,x_3=5,x_4=8,x_1=x_5=x_6=0 x2​=12,x3​=5,x4​=8,x1​=x5​=x6​=0 由于目标函数只包含 x 1 , x 2 , x 3 x_1,x_2,x_3 x1​,x2​,x3​,于是最优解X*=(0,12,5,8)T 2）大M法 这个M是值很大的正数 列：使用大M法求解下列线性规划 max z=-3x1+x3 s . t . = { x 1 + x 2 + x 3 ≤ 4 − 2 x 1 + x 2 − x 3 ≥ 1 3 x 2 + x 3 = 9 x 1 x 2 , x 3 ≥ 0 s.t.=\left \{ \begin{array}{c} x_1+x_2+x_3\le4 \\ \\ -2x_1+x_2-x_3\ge1\\\\ 3x_2+x_3=9\\\\ x_1x_2,x_3\ge0 \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​+x2​+x3​≤4−2x1​+x2​−x3​≥13x2​+x3​=9x1​x2​,x3​≥0​ 转化为标准形式 m i n z ′ = 3 x 1 − x 3 min z'=3x_1-x_3 minz′=3x1​−x3​ s . t . = { x 1 + x 2 + x 3 + x 5 = 4 − 2 x 1 + x 2 − x 3 − x 5 = 1 3 x 2 + x 3 = 9 x 1 x 2 , x 3 , x 4 , x 5 ≥ 0 s.t.=\left \{ \begin{array}{c} x_1+x_2+x_3+x_5=4 \\ \\ -2x_1+x_2-x_3-x_5=1\\\\ 3x_2+x_3=9\\\\ x_1x_2,x_3,x_4,x_5\ge0 \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​+x2​+x3​+x5​=4−2x1​+x2​−x3​−x5​=13x2​+x3​=9x1​x2​,x3​,x4​,x5​≥0​ 列出系数矩阵如下 A = [ 1 1 1 [ 1 ] 0 − 2 1 − 1 [ 0 ] − 1 0 3 1 [ 0 ] 0 ] A=\left[ \begin{array}{ccc} 1&1&1&[1]&0\\ -2&1&-1&[0]&-1\\ 0&3&1&[0]&0 \end{array} \right] A=⎣⎡​1−20​113​1−11​[1][0][0]​0−10​⎦⎤​ 发现没有单位矩阵不能使用单纯形法于是采用大M法，原来矩阵有一行于是补两个人工变量凑成一个单位矩阵 A = [ 1 1 1 [ 1 ] 0 0 0 − 2 1 − 1 [ 0 ] − 1 1 0 0 3 1 [ 0 ] 0 0 1 ] A=\left[ \begin{array}{ccccc|cc} 1&1&1&[1]&0&0&0\\ -2&1&-1&[0]&-1&1&0\\ 0&3&1&[0]&0&0&1 \end{array} \right] A=⎣⎡​1−20​113​1−11​[1][0][0]​0−10​010​001​⎦⎤​ 则原来的线性规划转化为： m i n z ′ = 3 x 1 − x 3 + M x 6 + M x 7 min z'=3x_1-x_3+Mx_6+Mx_7 minz′=3x1​−x3​+Mx6​+Mx7​ s . t . = { x 1 + x 2 + x 3 + x 5 = 4 − 2 x 1 + x 2 − x 3 − x 5 + x 6 = 1 3 x 2 + x 3 + x 7 = 9 x j ≥ 0 ( j = 1 , . . . , 7 ) s.t.=\left \{ \begin{array}{c} x_1+x_2+x_3+x_5=4 \\ \\ -2x_1+x_2-x_3-x_5+x_6=1\\\\ 3x_2+x_3+x_7=9\\\\ x_j\ge0(j=1,...,7) \end{array} \right. s.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​+x2​+x3​+x5​=4−2x1​+x2​−x3​−x5​+x6​=13x2​+x3​+x7​=9xj​≥0(j=1,...,7)​ 解答过程如下：

3)两阶段法 第一步：继承了大M法,先将目标函数，变成人工变量相加，其中M取1 其他条件不变，用单纯刑法使得所有的 ∂ j ≥ 0 \partial_j\ge0 ∂j​≥0，并且CB不含人工变量，求解如下：

如果包含人工变量替换为其他变量 第二步：以第一阶段的最终单纯形表为基础，出去人工变量 x 6 , x 7 x_6,x_7 x6​,x7​及其系数列，只恢复基础变量的系数，其他不变，继续进行迭代，结果如下：

练题是最重要的，多做多想。