第1章线性规划及单纯形法 11 max(min)2=c11+c22+...+Cnn s.t. a11x1+a12x2+…+a1nxn≤(=，≥)b1 a21x1+a22x2+·+a2nxn≤(=，≥)b2 (1-1-3) 。。。。 amlx1+am2x2+·+AmnEn≤(=，≥)bm x1≥0(i=1,2,…,n） 在模型(1-1-3)中，称z=c1x1+c2x2+…+cmxn为目标函数，对于该函数可能是求极 大(max),也可能是求极小(min)。模型中写成max(min)是为了将两种情况写在一起以便 于说明，并非同时求极大和极小。称a1工1+a2x2+…+anxn≤(=，≥)b(位=1,2，·，m) 为约束条件。同样，式(1-1-3)右边的≤(=，≥)是将可能的3种约束情况写在一起以 便于说明。最后≥0（位=1,2，·，）称为决策变量的非负约束。由于线性规划问题 在经济学上的含义，称c(位=1,2，…，n)为价值系数：b行=1,2，·，m)为资源系 数：a(位=1,2，…，m;j=1,2,…,n)为技术系数。值得注意的是，今后所遇到的问题并 不全是经济学问题，但仍然这样称呼这些参数。 求解线性规划问题(1-1-3)只能通过算法（没有解析解的方法）进行。也就是说，不 能通过将上述参数代入某个公式然后求得该问题。因此，必须指定一种表达形式为标准 形式，这种标准形式必须是能很容易地将其他非标准形式化为该标准形式。本书规定的 线性规划问题的标准形式为： maxz=C1x1+C2r2+···+CnEn S.t. a111 a1272+...+ainIn b1 a2171 a222+...+a2ntn b2 (1-1-4) amlx1+am2x2+··+amnIn=bm x1≥0(i=1,2,·,n) 它有3个特点： (1)目标函数求极大。由于对于任何函数均有minz=-max(-z),可见，如果原问 题是对目标函数z求极小，则可以先求其相反函数（即一z)的极大，得到极大值之后，再 将函数值反号即可。 (②)所有约束条件都是等式约束。实际上，若第i个约束条件是“≤”，即 ai1x1+ai2x2+…+anxn≤b:
第 1 章 线性规划及单纯形法 11 max(min) z = c1x1 + c2x2 + · · · + cnxn s.t. a11x1 + a12x2 + · · · + a1nxn 6 (=, >)b1 a21x1 + a22x2 + · · · + a2nxn 6 (=, >)b2 · · · · · · am1x1 + am2x2 + · · · + amnxn 6 (=, >)bm xi > 0(i = 1, 2, · · · , n) (1-1-3) 在模型 (1-1-3) 中，称 z = c1x1+c2x2+· · ·+cnxn 为目标函数，对于该函数可能是求极 大 (max)，也可能是求极小 (min)。模型中写成 max(min) 是为了将两种情况写在一起以便 于说明，并非同时求极大和极小。称 ai1x1 +ai2x2 +· · ·+ainxn 6 (=, >)bi(i = 1, 2, · · · , m) 为约束条件。同样，式 (1-1-3) 右边的 6 (=, >) 是将可能的 3 种约束情况写在一起以 便于说明。最后 xi > 0(i = 1, 2, · · · , n) 称为决策变量的非负约束。由于线性规划问题 在经济学上的含义，称 ci(i = 1, 2, · · · , n) 为价值系数；bj (j = 1, 2, · · · , m) 为资源系 数；aij (i = 1, 2, · · · , m; j = 1, 2, · · · , n) 为技术系数。值得注意的是，今后所遇到的问题并 不全是经济学问题，但仍然这样称呼这些参数。 求解线性规划问题 (1-1-3) 只能通过算法 (没有解析解的方法) 进行。也就是说，不 能通过将上述参数代入某个公式然后求得该问题。因此，必须指定一种表达形式为标准 形式，这种标准形式必须是能很容易地将其他非标准形式化为该标准形式。本书规定的 线性规划问题的标准形式为： max z = c1x1 + c2x2 + · · · + cnxn s.t. a11x1 + a12x2 + · · · + a1nxn = b1 a21x1 + a22x2 + · · · + a2nxn = b2 · · · · · · am1x1 + am2x2 + · · · + amnxn = bm xi > 0(i = 1, 2, · · · , n) (1-1-4) 它有 3 个特点： (1) 目标函数求极大。由于对于任何函数均有 min z = − max(−z)，可见，如果原问 题是对目标函数 z 求极小，则可以先求其相反函数 (即 −z) 的极大，得到极大值之后，再 将函数值反号即可。 (2) 所有约束条件都是等式约束。实际上，若第 i 个约束条件是“6”，即 ai1x1 + ai2x2 + · · · + ainxn 6 bi
12 运筹学基础及其MATLAB应用 则表明表达式左边比右边少了某一个非负数，称该非负数为松弛变量，在经济学上表明 该种资源（即b)没有用完的部分。设该非负数为工（具体的下标视原问题的变量个数以 及有多少个松弛变量而定，一般与原问题的变量下标连续)，则一定有： ait1 aj2z2++ainIn +Is =bi x。作为新的变量加入到原问题中，在整个模型求解后其值也就出来了。第i个约束条件 也可能是“≥”，即 a1x1+a2x2+…+anxn≥bi 这时，表达式左边比右边多了某一个非负数，称该非负数为剩余变量，也可继续称为松弛 变量。在经济学上的意义是该种资源（即）用超过的部分，比如某种产品中某种成分的 含量至少达到b,则就会出现这样的约束。类似地，设该非负数为x,(具体的下标视原问 题的变量个数以及有多少个松弛变量而定，一般与原问题的变量下标连续)，则一定有 ailt1 ai2x2+...+aintn Is bi x。也作为新的变量加入原问题中，在整个模型求解后其值同样出来了。 (3)所有决策变量非负。实际上，对于决策变量的符号，总共有3种可能。若某变量 本来就是非负的，则不用改变：若某变量非正，则用其相反的变量取代。即若原模型中要 求，≤0，则令x=-x,或者说x:=-x,并将其代入原模型中，则x;被x取代，且 x≥0：若原模型中对x:没有符号要求，即正负均可，则可令 x=x{-x,x,x{≥0 带入原模型中，则出现的变量均是非负变量。 通过这3点，任何一个线性规划问题都可以容易地化为标准形式。今后讨论线性 规划问题的有关理论以及有关算法时都是针对模型(1-1-4)进行的。此外，还常常用到 模型(1-1-4)的向量表达形式(1-1-5)和矩阵表达形式(1-1-6)，相应的称式(1-1-4)为线性 规划问题的分量表达形式。 max 2=cTX s.t. EP j=b (1-1-5) x≥0(0=1,2，…，n) 其中，c=(G1,c2,…,c)T∈R";X=(1,z2,…,n)T∈R;P)=(a,a2…,am)T∈
12 运筹学基础及其 MATLAB 应用 则表明表达式左边比右边少了某一个非负数，称该非负数为松弛变量，在经济学上表明 该种资源 (即 bi) 没有用完的部分。设该非负数为 xs(具体的下标视原问题的变量个数以 及有多少个松弛变量而定，一般与原问题的变量下标连续)，则一定有： ai1x1 + ai2x2 + · · · + ainxn + xs = bi xs 作为新的变量加入到原问题中，在整个模型求解后其值也就出来了。第 i 个约束条件 也可能是“>”，即 ai1x1 + ai2x2 + · · · + ainxn > bi 这时，表达式左边比右边多了某一个非负数，称该非负数为剩余变量，也可继续称为松弛 变量。在经济学上的意义是该种资源 (即 bi) 用超过的部分，比如某种产品中某种成分的 含量至少达到 bi，则就会出现这样的约束。类似地，设该非负数为 xs(具体的下标视原问 题的变量个数以及有多少个松弛变量而定，一般与原问题的变量下标连续)，则一定有 ai1x1 + ai2x2 + · · · + ainxn − xs = bi xs 也作为新的变量加入原问题中，在整个模型求解后其值同样出来了。 (3) 所有决策变量非负。实际上，对于决策变量的符号，总共有 3 种可能。若某变量 本来就是非负的，则不用改变；若某变量非正，则用其相反的变量取代。即若原模型中要 求 xi 6 0，则令 x 0 i = −xi，或者说 xi = −x 0 i，并将其代入原模型中，则 xi 被 x 0 i 取代，且 x 0 i > 0；若原模型中对 xi 没有符号要求，即正负均可，则可令 xi = x 0 i − x 00 i , x0 i , x00 i > 0 带入原模型中，则出现的变量均是非负变量。 通过这 3 点，任何一个线性规划问题都可以容易地化为标准形式。今后讨论线性 规划问题的有关理论以及有关算法时都是针对模型 (1-1-4) 进行的。此外，还常常用到 模型 (1-1-4) 的向量表达形式 (1-1-5) 和矩阵表达形式 (1-1-6)，相应的称式 (1-1-4) 为线性 规划问题的分量表达形式。 max z = c TX s.t. Xn j=1 P jxj = b xj > 0(j = 1, 2, · · · , n) (1-1-5) 其中，c = (c1, c2, · · · , cn) T ∈ R n ; X = (x1, x2, · · · , xn) T ∈ R n ; P j = (a1j , a2j , · · · , amj ) T ∈
第1章线性规划及单纯形法13 Rm(j=1,2,…,n):b=(b1,b2,…,bm)T∈Rm。 max z=cTX s.t. (1-1-6) AX=b X≥0 其中，A=(a)mn∈Rmn;c∈R”;X=(x1,x2,…,xn)T∈R”;b∈Rm。 根据向量和矩阵的相关运算，容易看出上面3种表达形式是一样的，只是在讨论有 关问题时，不一样的表达方式有时更方便，特别是线性规划的矩阵表达形式。最后需要强 调的是，在线性规划的标准形式中要求资源向量b≥0。这点容易办到而且意义明显。 例1.1将线性规划问题(1-1-1)化为标准形式。 解线性规划问题(1-1-1)原为： max z=6x1+7x2 s.t. 2x1+3x2≤16 4红1+x2≤12 x1,x2≥0 对照上面的3个特点逐一检查：目标函数己是求极大，决策变量己是非负，但两个 约束条件都是“≤”，故需要引入两个松弛变量，分别记为x3,x4。无论是松弛变量还是剩 余变量都是非负变量，故式(1-1-1)等价于如下标准形式： max z=6x1+72 s.t. 2x1+3x2+x3 =16 4x1+x2 +x4=12 x1≥0，i=1,2,3,4 写成矩阵形式为： max z=cTX s.t. 「AX=b X≥0 ,c-a7a0r4-(） b=(16,12)T;X=(c1,x2,x3,x4)T
第 1 章 线性规划及单纯形法 13 R m(j = 1, 2, · · · , n); b = (b1, b2, · · · , bm) T ∈ R m。 max z = c TX s.t. ( AX = b X > 0 (1-1-6) 其中，A = (aij )m·n ∈ R m·n ; c ∈ R n ; X = (x1, x2, · · · , xn) T ∈ R n ; b ∈ R m。 根据向量和矩阵的相关运算，容易看出上面 3 种表达形式是一样的，只是在讨论有 关问题时，不一样的表达方式有时更方便，特别是线性规划的矩阵表达形式。最后需要强 调的是，在线性规划的标准形式中要求资源向量 b > 0。这点容易办到而且意义明显。 例 1.1 将线性规划问题 (1-1-1) 化为标准形式。 解 线性规划问题 (1-1-1) 原为： max z = 6x1 + 7x2 s.t. 2x1 + 3x2 6 16 4x1 + x2 6 12 x1, x2 > 0 对照上面的 3 个特点逐一检查：目标函数已是求极大，决策变量已是非负，但两个 约束条件都是“6”，故需要引入两个松弛变量，分别记为 x3, x4。无论是松弛变量还是剩 余变量都是非负变量，故式 (1-1-1) 等价于如下标准形式： max z = 6x1 + 7x2 s.t. 2x1 + 3x2 + x3 = 16 4x1 + x2 + x4 = 12 xi > 0, i = 1, 2, 3, 4 写成矩阵形式为： max z = c TX s.t. ( AX = b X > 0 其中，c = (6, 7, 0, 0)T; A = Ã 2 3 1 0 4 1 0 1 ! ; b = (16, 12)T; X = (x1, x2, x3, x4) T
14 运筹学基础及其MATLAB应用 例1.2将下述线性规划化为标准形式。 min z=-21+2x2-33 s.t. D1+2+x3≤7 T1-2+x3≥2 -3x1+x2+2x3=5 (x1,x2≥0，x3无符号限制 解由于x3无符号限制，故令x3=x4-x5,x4,x6≥0，并在第一个约束条件引入 一个松弛变量x6≥0，在第二个约束条件引入剩余变量（松弛变量）z7≥0，则得到原问 题的标准形式： max z=1-22+34-35 S.t. x1十E2十T4-工5+T6 ÷7 x1-T2+E4-工5 -x7=2 -3x1+x2+2x4-2x5 =5 x1≥0，T2≥0，x4≥0，x5≥0，x6≥0，x7≥0 其矩阵形式为： max z=cTX s.t. AX=b 1X≥0 其中， c=(1,-2,3,-3.0,0)T 12-200 b=(7,2,5)T,X=(c1,x2,x4,x5,x6,7)T 1.1.2图解法及基本概念 由于线性规划问题的目标函数和约束条件都是线性函数，在只有两个决策变量时，可 以在笛卡儿直角坐标系上画出相应的约束函数并可以直观地看出其最优解。这就是线性 规划的图解法。图解法只适用于两个决策变量的情形，超过两个决策变量的线性规划问
14 运筹学基础及其 MATLAB 应用 例 1.2 将下述线性规划化为标准形式。 min z = −x1 + 2x2 − 3x3 s.t. x1 + x2 + x3 6 7 x1 − x2 + x3 > 2 −3x1 + x2 + 2x3 = 5 x1, x2 > 0, x3无符号限制 解 由于 x3 无符号限制，故令 x3 = x4 − x5, x4, x5 > 0，并在第一个约束条件引入 一个松弛变量 x6 > 0，在第二个约束条件引入剩余变量 (松弛变量)x7 > 0，则得到原问 题的标准形式： max z = x1 − 2x2 + 3x4 − 3x5 s.t. x1 + x2 + x4 − x5 + x6 = 7 x1 − x2 + x4 − x5 − x7 = 2 −3x1 + x2 + 2x4 − 2x5 = 5 x1 > 0, x2 > 0, x4 > 0, x5 > 0, x6 > 0, x7 > 0 其矩阵形式为： max z = c TX s.t. AX = b X > 0 其中， A = 1 1 1 −1 1 0 1 −1 1 −1 0 −1 −3 1 2 −2 0 0 , c = (1, −2, 3, −3, 0, 0)T b = (7, 2, 5)T, X = (x1, x2, x4, x5, x6, x7) T 1.1.2 图解法及基本概念 由于线性规划问题的目标函数和约束条件都是线性函数，在只有两个决策变量时，可 以在笛卡儿直角坐标系上画出相应的约束函数并可以直观地看出其最优解。这就是线性 规划的图解法。图解法只适用于两个决策变量的情形，超过两个决策变量的线性规划问
第1章线性规划及单纯形法 15 题无法利用图解法求解。因此，图解法除了帮助初学者直观地了解线性规划的有关概念 和基本原理以外，没有其他作用。图解法的基本步骤为： (1)在笛卡儿直角坐标系上画出所有的约束函数（直线），并确定决策变量的取值范 围，这个范围内的每个点称为可行点或可行解，其全体称为可行域。 (2)画出至少两条目标函数直线，它们是平行的（实际上目标函数是平行直线族），这 样可以看到目标函数向什么方向移动时函数值是增加还是减少，当目标函数增加（原问 题是求极大)到某一点，如果再增加就跑到了约束域的外面时，这点就是所求的最优点 (最优解)。 例1.3 用图解法求解线性规划问题(1-1-1)。 B x*1=2,2*2=4 0 、、A 4+2=122m+3物=16 图1-1图解法求解线性规划问题(1-1-1) 解首先在笛卡儿直角坐标系上画出两条约束函数直线，然后判断约束域。由于有 变量非负的要求，所以只需要第一象限。原来第一个约束条件是2x1+3x2≤16，故满足 该条件的点位于△OCD区域，类似地，满足第二个约束条件的点位于△OAB区域。从 而满足所有约束条件的点位于四边形OAED区域。令目标函数6x1+7x2分别取值6和 12(当然也可以是其他值)并画出这两条直线，即图1-1中左下方的两条虚线。可以看出， 该直线向右上方移动时函数值是增加的。因此，该直线移动到E点时不能再移动了。因 为，E点还属于可行域的一点（可行点），继续向上移动时，目标函数值虽然增加，但直线 上所有点都不在约束域里面了。这就是说，E点是约束域里使得线性规划问题(1-1-1)目 标函数值最大的点，故该点即为所求的最优点。显然，这是两条约束直线的交点，解线性 方程组即可得到x1=2,x陵=4，而最优目标函数值为2*=40。 上述例题中的最优解是唯一的，但对于一般的线性规划问题，其解的结果还有可能 是：无穷多组解、无界解以及无可行解这3种情况。下面通过图解法加以说明
第 1 章 线性规划及单纯形法 15 题无法利用图解法求解。因此，图解法除了帮助初学者直观地了解线性规划的有关概念 和基本原理以外，没有其他作用。图解法的基本步骤为： (1) 在笛卡儿直角坐标系上画出所有的约束函数 (直线)，并确定决策变量的取值范 围，这个范围内的每个点称为可行点或可行解，其全体称为可行域。 (2) 画出至少两条目标函数直线，它们是平行的 (实际上目标函数是平行直线族)，这 样可以看到目标函数向什么方向移动时函数值是增加还是减少，当目标函数增加 (原问 题是求极大) 到某一点，如果再增加就跑到了约束域的外面时，这点就是所求的最优点 (最优解)。 例 1.3 用图解法求解线性规划问题 (1-1-1)。 图 1-1 图解法求解线性规划问题 (1-1-1) 解 首先在笛卡儿直角坐标系上画出两条约束函数直线，然后判断约束域。由于有 变量非负的要求，所以只需要第一象限。原来第一个约束条件是 2x1 + 3x2 6 16，故满足 该条件的点位于 4OCD 区域，类似地，满足第二个约束条件的点位于 4OAB 区域。从 而满足所有约束条件的点位于四边形 OAED 区域。令目标函数 6x1 + 7x2 分别取值 6 和 12(当然也可以是其他值) 并画出这两条直线，即图 1-1 中左下方的两条虚线。可以看出， 该直线向右上方移动时函数值是增加的。因此，该直线移动到 E 点时不能再移动了。因 为，E 点还属于可行域的一点 (可行点)，继续向上移动时，目标函数值虽然增加，但直线 上所有点都不在约束域里面了。这就是说，E 点是约束域里使得线性规划问题 (1-1-1) 目 标函数值最大的点，故该点即为所求的最优点。显然，这是两条约束直线的交点，解线性 方程组即可得到 x ∗ 1 = 2, x∗ 2 = 4，而最优目标函数值为 z ∗ = 40。 上述例题中的最优解是唯一的，但对于一般的线性规划问题，其解的结果还有可能 是：无穷多组解、无界解以及无可行解这 3 种情况。下面通过图解法加以说明