运筹学基础及应用第五版-胡运权第一章

1、2021/3/111 1 1一般线性规划问题的数学模型一般线性规划问题的数学模型 2图解法图解法 3单纯形法原理单纯形法原理 4单纯形法的计算步骤单纯形法的计算步骤 5单纯形法的进一步讨论单纯形法的进一步讨论 6改进单纯形法改进单纯形法 7应用举例及应用举例及Matlab求解方法求解方法 第一章第一章 线性规划及单纯形法线性规划及单纯形法 2021/3/112 1 1一般线性规划问题的数学模型一般线性规划问题的数学模型 例如图所示，如何截取x使铁皮所围 成的容积最大？ x x a a xxav 2 2 0 dx dv 0)2()2()2(2 2 xaxxa 6 a x 2021/3/113 一

2、、问题的提出 某企业计划生产某企业计划生产、两种产品。这两种产两种产品。这两种产 品都要分别在品都要分别在A、B、C、D四种不同设备上加工。四种不同设备上加工。 生产每件产品生产每件产品需占用各设备分别为需占用各设备分别为2、1、4、 0h，生产每件产品，生产每件产品，需占用各设备分别为，需占用各设备分别为2、2、 0、4h。已知各设备计划期内用于生产这两种产。已知各设备计划期内用于生产这两种产 品的能力分别为品的能力分别为12、8、16、12h，又知每生产一，又知每生产一 件产品件产品企业能获得企业能获得2元利润，每生产一件产品元利润，每生产一件产品 企业能获得企业能获得3元利润，问企业应安

3、排生产两种元利润，问企业应安排生产两种 产品各多少件，使总的利润收入为最大。产品各多少件，使总的利润收入为最大。 1 1一般线性规划问题的数学模型一般线性规划问题的数学模型 2021/3/114 产品产品 产品产品 计划期内计划期内 生产能力生产能力 A2212 B128 C4016 D0412 利润利润23MAX 2021/3/115 需满足条件：需满足条件： 实现目的：实现目的： 0, 12 4 16 4 82 1222 21 2 1 21 21 xx x x xx xx max 32 21 xxz 2021/3/116 二、线性规划问题的数学模型 三个组成要素：三个组成要素： 1.决策变

4、量决策变量:是决策者为实现规划目标采取是决策者为实现规划目标采取 的方案、措施，是问题中要确定的未知量。的方案、措施，是问题中要确定的未知量。 2.目标函数目标函数:指问题要达到的目的要求，表指问题要达到的目的要求，表 示为决策变量的函数。示为决策变量的函数。 3.约束条件约束条件:指决策变量取值时受到的各种指决策变量取值时受到的各种 可用资源的限制，表示为含决策变量的等式可用资源的限制，表示为含决策变量的等式 或不等式。或不等式。 2021/3/117 一般线性规划问题的数学模型：一般线性规划问题的数学模型： 0, , , , 21 2211 22222121 11212111 n mnmn

5、mm nn nn xxx bxaxaxa bxaxaxa bxaxaxa ）（或 ）（或 ）（或 目标函数：目标函数： 约束条件：约束条件： nnx cxcxcz 2211 minmax）（或 2021/3/118 简写形式：简写形式： ），（ ），（），（或 ）（或 njx mibxa xcz j i n j jij n j jj 1 0 1 minmax 1 1 2021/3/119 矩阵形式表示为：矩阵形式表示为： maxmin 0 zCX AXb X （或） （或，） 其中：其中： nnnn n n aaa aaa aaa A 21 22221 11211 n cccC, 21 T n

6、 xxxX, 21 T n bbbb, 21 2021/3/1110 三、线性规划问题的标准形式 标准形式：标准形式： ），（ ），（ njx mibxa xcz j i n j jij n j jj 1 0 1 max 1 1 标准形式特点：标准形式特点： 4. 决策变量取值非负。决策变量取值非负。 1. 目标函数为求极大值；目标函数为求极大值； 2. 约束条件全为等式；约束条件全为等式； 约束条件右端常数项全为非负值；约束条件右端常数项全为非负值； 2021/3/1111 一般线性规划问题如何化为标准型：一般线性规划问题如何化为标准型： 1. 目标函数求极小值：目标函数求极小值： n j

7、jj xcz 1 min 令：令： ，即化为：，即化为：zz n j jj n j jj xcxc zzz 11 min)max(max 2021/3/1112 2. 约束条件为不等式：约束条件为不等式： （1）当约束条件为）当约束条件为“”时时 如：如：1222 21 xx 可令：可令： ， 显然显然1222 321 xxx 0 3 x （2）当约束条件为）当约束条件为“”时时 如：如：181210 21 xx 可令：可令： ， 显然显然0 4 x181210 421 xxx 称为称为松弛变量。松弛变量。 3 x 称为称为剩余变量剩余变量。 4 x 2021/3/1113 松弛变量和剩余变量

8、统称为松弛变量松弛变量和剩余变量统称为松弛变量 （3）目标函数中松弛变量的系数）目标函数中松弛变量的系数 由于松弛变量和剩余变量分别表示未被充分利由于松弛变量和剩余变量分别表示未被充分利 用的资源以及超用的资源，都没有转化为价值和利用的资源以及超用的资源，都没有转化为价值和利 润，因此润，因此在目标函数中系数为零在目标函数中系数为零。 2021/3/1114 3. 取值无约束的变量取值无约束的变量 如果变量如果变量 x 代表某产品当年计划数与上代表某产品当年计划数与上 一年计划数之差，显然一年计划数之差，显然 x 的取值可能是正也的取值可能是正也 可能是负，这时可令：可能是负，这时可令： xx

9、x 其中：其中：00 xx， 令令 4. 变量变量 xj0 jj xx，显然，显然0 j x 2021/3/1115 例例. 将下述线性规划模型化为标准型将下述线性规划模型化为标准型 取值无约束 321 321 321 321 321 , 0, 0 6323 42 3 9 2 32min xxx xxx xxx xxx xxxz 2021/3/1116 解：解：令令， 11 xxzz 00 33333 xxxxx， 得标准形式为：得标准形式为： 0 6 3323 4 22 3 9 2 00332max 543321 3321 53321 43321 543321 xxxxxx xxxx xxx

10、xx xxxxx xxxxxxz ， 2021/3/1117 求解线性规划问题：求解线性规划问题： 就是从满足约束方程组和约束不等式的决策变量取就是从满足约束方程组和约束不等式的决策变量取 值中，找出使得目标函数达到最大的值。值中，找出使得目标函数达到最大的值。 ），（ ），（ njx mibxa xcz j i n j jij n j jj 1 0 1 max 1 1 2021/3/1118 四、线性规划问题的解 可行解：可行解：满足约束条件的解称为满足约束条件的解称为可行解可行解，可行解的集，可行解的集 合称为合称为可行域可行域。 最优解：最优解：使目标函数达到最大值的可行解。使目标函数达

11、到最大值的可行解。 基基：约束方程组的一个满秩子矩阵称为规划问题的一：约束方程组的一个满秩子矩阵称为规划问题的一 个个基基，基中的每一个列向量称为，基中的每一个列向量称为基向量基向量，与基向量对应，与基向量对应 的变量称为的变量称为基变量基变量，其他变量称为，其他变量称为非基变量非基变量。 基解：基解：在约束方程组中，令所有非基变量为在约束方程组中，令所有非基变量为0，可以，可以 解出基变量的唯一解，这组解与非基变量的解出基变量的唯一解，这组解与非基变量的0共同构成共同构成 基解基解。 基可行解：基可行解：满足变量非负的基解称为满足变量非负的基解称为基可行解基可行解 可行基：可行基：对应于基可

12、行解的基称为对应于基可行解的基称为可行基可行基 2021/3/1119 例例4 说明什么是基、基说明什么是基、基 变量、基解、基可变量、基解、基可 行解和可行基行解和可行基 实现目的：实现目的： 12312 12124 115 226 12123456 22122212 2828 4 164 16 4 12 4 12 ,0,0 xxxxx xxxxx xxx xxx x xx x x x x x 123456 max230000zxxxxxx 2021/3/1120 为了便于建立为了便于建立 n 维空间中线性规划问题的维空间中线性规划问题的 概念及便于理解求解一般线性规划问题的单纯概念及便于理

13、解求解一般线性规划问题的单纯 形法的思路，先介绍图解法。形法的思路，先介绍图解法。 求解下述线性规划问题：求解下述线性规划问题： 0, 12 4 16 4 82 1222 21 2 1 21 21 xx x x xx xx 21 32maxxxz 2. 2. 线性规划问题的图解法线性规划问题的图解法 2021/3/1121 画出线性规划问题的可行域：画出线性规划问题的可行域： 2021/3/1122 目标函数的几何意义：目标函数的几何意义： 2021/3/1123 最优解的确定：最优解的确定： 2021/3/1124 图解法的步骤：图解法的步骤： 建立坐标系，将约束条件在图上表示；建立坐标系，

14、将约束条件在图上表示； 确立满足约束条件的解的范围；确立满足约束条件的解的范围； 绘制出目标函数的图形；绘制出目标函数的图形； 确定最优解。确定最优解。 2021/3/1125 无穷多最优解的情况：无穷多最优解的情况： 目标函数与某个约束条件恰好平行目标函数与某个约束条件恰好平行 2021/3/1126 无界解（或无最优解）的情况：无界解（或无最优解）的情况： 可行域上方无界可行域上方无界 2021/3/1127 无可行解的情况：无可行解的情况： 约束条件不存在公共范围约束条件不存在公共范围 2021/3/1128 图解法的启示：图解法的启示： 求解线性规划问题时，解的情况有：唯一最求解线性规

15、划问题时，解的情况有：唯一最 优解，无穷多最优解，无界解，无可行解；优解，无穷多最优解，无界解，无可行解； 若线性规划问题可行域存在，在可行域是一若线性规划问题可行域存在，在可行域是一 个凸集；个凸集； 若线性规划问题最优解存在，在最优解或最若线性规划问题最优解存在，在最优解或最 优解之一一定能够在可行域的某个顶点取得；优解之一一定能够在可行域的某个顶点取得； 解题思路是，先找凸集的任一顶点，计算其解题思路是，先找凸集的任一顶点，计算其 目标函数值。比较其相邻顶点函数值，若更目标函数值。比较其相邻顶点函数值，若更 优，则逐点转移，直到找到最优解。优，则逐点转移，直到找到最优解。 2021/3/

16、1129 3 3单纯形法原理单纯形法原理 凸集：凸集：如果集合如果集合 C 中任意两个点中任意两个点 ，其连线上，其连线上 的所有点也都是集合的所有点也都是集合C 中的点。中的点。 21, X X 上图中（上图中（1）（）（2）是凸集，（）是凸集，（3）（）（4）不是凸集）不是凸集 顶点：顶点：如果对于凸集如果对于凸集 C 中的点中的点 X ，不存在，不存在C 中的任中的任 意其它两个不同的点意其它两个不同的点 ，使得，使得 X 在它们的连线上，在它们的连线上， 这时称这时称 X 为凸集的顶点。为凸集的顶点。 21 XX 、 2021/3/1130 一、线性规划问题基本定理 定理一定理一 若线

17、性规划问题存在可行解，则问题的可行若线性规划问题存在可行解，则问题的可行 域是凸集。域是凸集。 定理二定理二 线性规划问题的基本可行解线性规划问题的基本可行解 X 对应线性规划对应线性规划 问题可行域（凸集）的顶点。问题可行域（凸集）的顶点。 定理三定理三 若线性规划问题有最优解，一定存在一个基若线性规划问题有最优解，一定存在一个基 可行解是最优解。可行解是最优解。 从上述三个定理可以看出，要求线性规划问从上述三个定理可以看出，要求线性规划问 题的最优解，只要比较可行域（凸集）各个题的最优解，只要比较可行域（凸集）各个 顶点对应的目标函数值即可，最大的就是我顶点对应的目标函数值即可，最大的就是

18、我 们所要求的最优解。们所要求的最优解。 2021/3/1131 定理定理1 1：若LP模型存在可行解，则可行域为凸集。 证明：证明：设 max z=CX st.AX=b X0 并设其可行域为C，若X1、X2为其可行解，且X1X2 ， 则 X1C，X2 C， 即AX1=b，AX2=b，X10，X20， 又 X为X1、X2连线上一点，即 X=X1+(1-)X2， (01)， AX=AX1+ (1-)AX2 = b+ (1-)b =b , (01)，且 X 0， X C， C为凸集。 三个基本定理：三个基本定理： 2021/3/1132 引理：引理：线性规划问题的可行解X=(x1, x2,xn)T

19、 为基本可行 解的充要条件是X的正分量所对应的系数列向量线性独立。 证：证： （1）必要性：）必要性：X基本可行解基本可行解X的正分量所对应的系数列向量线性独立的正分量所对应的系数列向量线性独立 可设X=(x1,x2,xk,0,0,0)T，若X为基本可行解，显然，由 基本可行解定义可知x1, x2,xk所对应的系数列向量P1,P2,Pk应 该线性独立。 （2）充分性：）充分性： X的正分量所对应的系数列向量线性独立的正分量所对应的系数列向量线性独立 X为基本可行解为基本可行解 若A的秩为m，则X的正分量的个数km； 当k=m时，则x1,x2,xk的系数列向量P1,P2,Pk恰好构成基， X为基

20、本可行解。 当km时，则必定可再找出m-k个列向量与P1,P2,Pk一起构成基， X为基本可行解。 2021/3/1133 证：等价于 X非基本可行解非基本可行解X非凸集顶点非凸集顶点 （1）必要性）必要性：X非基本可行解非基本可行解 X非凸集顶点非凸集顶点 不失一般性，设X=(x1,x2,xm,0,0,0)T，为非基本可行解， X为可行解， pjxj=b， j=1 n 即 pjxj=b (1) j=1 m 又 X是非基本可行解， P1,P2,Pm线性相关，即有 1P1+2P2+mPm=0， 其中1，2，m不全为0，两端同乘0，得 1P1+2P2+mPm=0，（2） 定理定理2 2：线性规划模

21、型的基本可行解对应其可行域的顶点。 2021/3/1134 由 (1)+(2)得 (x1+ 1)P1+ (x2+ 2)P2+ (xm+ m)Pm=b 由 (1)-(2)得 (x1 -1)P1+ (x2 - 2)P2+ (xm -m)Pm=b 令X1=(x1+ 1，x2+ 2，xm+ m，0， ，0)T X2=(x1- 1，x2- 2，xm- m ，0，0)T 取充分小,使得 xj j0， 则 X1、X2均为可行解， 但 X=0.5X1+(1-0.5)X2， X是X1、X2连线上的点， X非凸集顶点。 2021/3/1135 （2）充分性：）充分性： X非凸集顶点非凸集顶点 X非基本可行解非基本

22、可行解 设X=(x1,x2,xr,0,0,0)T为非凸集顶点，则必存在Y、Z两点，使 得 X=Y+(1-)Z，(01)，且Y、Z为可行解 或者 xj=yj+(1-)zj (00, 1-0 ，当xj=0， 必有yj=zj=0 pjyj = j=1 n pjyj=b (1) j=1 r pjzj = j=1 n pjzj=b (2) j=1 r (yj-zj)pj=0 j=1 r ,(1)-(2),得 即(y1 - z1)P1+ (y2 - z2)P2+ (yr -zr)Pr=0 2021/3/1136 Y、Z为不同两点， yj-zj不全为0， P1,P2,Pr线性相关， X非基本可行解。 202

23、1/3/1137 z1=CX1=CX0-C=zmax-C ，z2=CX2=CX0+C =zmax+C z0 = zmax z1 ， z0 = zmax z2 ， z1 = z2 = z0 ，即 X1 、 X2也为最优解， 若X1、X2仍不是顶点，可如此递推，直至找出一个顶点为最优 解。 从而，必然会找到一个基本可行解为最优解。 定理定理3 3：若线性规划模型有最优解，则一定存在一个基本可 行解为最优解。 证：证：设 X0=(x10, x20,xn0)T 是线性规划模型的一个最优解， z0=zmax=CX0 若X0非基本可行解，即非顶点，只要取充分小， 则必能找出X1= X0-0 ，X2 = X

24、0 +0 ，即X1 、 X2为可行解， 2021/3/1138 单纯形法的计算步骤： 初始基本可行解 新的基本可行解 最优否？STOP Y N 2021/3/1139 二、确定初始基可行解 线性规划问题的最优解一定会在基可行解中取得，我线性规划问题的最优解一定会在基可行解中取得，我 们先找到一个初始基可行解。然后设法转换到另一个们先找到一个初始基可行解。然后设法转换到另一个 基可行解，直到找到最优解为止。基可行解，直到找到最优解为止。 设给定线性规划问题：设给定线性规划问题： ），（ ），（ njx mibxa xcz j i n j jij n j jj 1 0 1 max 1 1 2021

25、/3/1140 因此约束方程组的系数矩阵为：因此约束方程组的系数矩阵为： 100 010 001 21 22221 11211 mnmm n n aaa aaa aaa 由于该矩阵含有一个单位子矩阵，因此，用这个单位由于该矩阵含有一个单位子矩阵，因此，用这个单位 阵做基，就可以求出一个基可行解：阵做基，就可以求出一个基可行解： T m bbX, 0 , 0 1 其标准形为：其标准形为： ），（ ），（ njx mibxxa xxcz j isi n j jij m i si n j jj 1 0 1 0max 1 11 2021/3/1141 三、从初始基可行解转换为 另一个基可行解 对初始可

26、行解的系数矩阵进行初等行对初始可行解的系数矩阵进行初等行 变换，构造出一个新的单位矩阵，其各列变换，构造出一个新的单位矩阵，其各列 所对应的变量即为一组新的基变量，求出所对应的变量即为一组新的基变量，求出 其数值，就是一个新的基可行解。其数值，就是一个新的基可行解。 2021/3/1142 从一个基本可行解向另一个基本可行解转换从一个基本可行解向另一个基本可行解转换 不失一般性，设基本可行解X0=(x10, x20,xm0,0,0)T ， 前m个分量为正值，秩为m，其系数矩阵为 P1 P2 Pm Pm+1 Pj Pn b 1 0 0a 1,m+1 a1j a 1n b1 0 1 0 a 2,m

27、+1 a2j a 2nb2 0 0 1a m,m+1 amj a mn bm pjxj0 = j=1 n pixi0=b (1) i=1 m 2021/3/1143 又P1 P2 Pm为一个基，任意一个非基向量Pj可以以该组向 量线性组合表示，即 Pj = a1j P1 + a2j P2 + amj Pm ，即 Pj = aij pi ， 移项，两端同乘0 ，有 (Pj- aij pi )=0 (2) i=1 m i=1 m (1)+(2)： (xi 0- aij)Pi + Pj =b， 取充分小，使所有xi 0 - aij 0，从而 i=1 m X1 = (x1 0- a1j ,x2 0-

28、a2j ,xm 0- amj ,0,0)T 也是可行解。 当取 = min aij 0 = ，则X1前m个分量至少有一个xL1为0。 xi 0 aijaLj xL 0 i P1 , P2,PL-1, PL+1, Pm, Pj 线性无关。 X1 也为基本可行解。 2021/3/1144 四、最优性检验和解的判别 令令 m i ijijj acc 1 ，其中，其中 随基的改变而改变随基的改变而改变 ij a lj l ij ij i i a x a a x 00 0min X1 = (x1 0- a1j ,x2 0- a2j ,xm 0- amj ,0,0)T 基本可行解X0=(x10, x20,

29、xm0,0,0)T z0 = cjxj0 =ci xi0 i=1 m j=1 n z1 = cjxj1 =ci(xi 0- aij) + cj i=1 m j=1 n =cixi 0+ (cj - ciaij)= z0 + j i=1 mm i=1 2021/3/1145 四、最优性检验和解的判别 当所有当所有 时，现有顶点对应的基可行解即为最时，现有顶点对应的基可行解即为最 优解。优解。 当所有当所有 时，又对某个非基变量时，又对某个非基变量 有有 且可以找到且可以找到 ，则该线性规划问题有无穷多最，则该线性规划问题有无穷多最 优解。优解。 3. 如果存在某个如果存在某个 ，又，又 向量所有

30、分量向量所有分量 ， 对任意对任意 ，恒有，恒有 ，则存在无界解。，则存在无界解。 0 j 0 j i x0 i 0 0 j j P0 ij a 00 0 iji ax 因因 0，所以有如下结论：，所以有如下结论：z1=z0 + j 2021/3/1146 4 4单纯形法的计算步骤单纯形法的计算步骤 第一步：求初始可行解，列初始单纯形表 表中最上端一行是各变量在目标函数中的系数，表中最上端一行是各变量在目标函数中的系数， 最左端一列是各基变量在目标函数中的系数值。最左端一列是各基变量在目标函数中的系数值。 2. 表中最后一行就是检验数表中最后一行就是检验数 。 j 2021/3/1147 第二

31、步：进行最优性检验 如果表中，所有检验数如果表中，所有检验数 ，则表中，则表中 的基可行解就是问题的最优解，计算到此为的基可行解就是问题的最优解，计算到此为 止，否则转入下一步。止，否则转入下一步。 0 j 2021/3/1148 第三步：转换到新的基可行解， 构造新单纯形表 1. 确定换入变量确定换入变量 取使得取使得0max jj j k 所对应的所对应的 作为换入基的变量。作为换入基的变量。 k x 2. 确定换出变量确定换出变量 取使得取使得 min0 il ik iklk bb a aa 所对应的所对应的 作为换出基的变量。作为换出基的变量。 l x 2021/3/1149 3. 用

32、换入变量替换换出变量，做新单纯形表用换入变量替换换出变量，做新单纯形表 （1） klll abb lia a b bb ik kl l ii （2） kljljl aaalia a a aa ik kl jl ijij （3）检验数）检验数 的求法与初始单纯形表中求法相同的求法与初始单纯形表中求法相同 j 2021/3/1150 第四步：重复第二、三步直到计算结束 例例5 用单纯形法求解线性规划问题用单纯形法求解线性规划问题 0, 124 16 4 82 1222 32max 21 2 1 21 21 21 xx x x xx xx xxz 2021/3/1151 解：解：将原线性规划问题化为

33、标准型将原线性规划问题化为标准型 0, 12 4 16 4 8 2 12 22 000032max 21 62 51 421 321 654321 xx xx xx xxx xxx xxxxxxz 第一步：第一步： 取系数矩阵中单位阵部分为基，得初始基可行解取系数矩阵中单位阵部分为基，得初始基可行解 T X12,16, 8 ,12, 0 , 0 2021/3/1152 列出初始单纯形表列出初始单纯形表 第二步：第二步： 由于：由于： 都大于零，因此，目前没有得都大于零，因此，目前没有得 到最优解。到最优解。 3 2 2 1 2021/3/1153 在大于零的检验数中，由于在大于零的检验数中，由

34、于 ，且，且 3 2 2 1 12 所以所以 为换入变量。为换入变量。 2 x 第三步：第三步： 由于由于 12 81212 min, ,3 2244 所以确定所以确定 为换出变量为换出变量 6 x 1. 确定换入变量确定换入变量 2. 确定换出变量确定换出变量 2021/3/1154 3. 作新单纯形表作新单纯形表 第四步：第四步：由于还存在检验数由于还存在检验数 ，因此重复上述步骤。，因此重复上述步骤。0 1 2021/3/1155 2021/3/1156 由于上表中所有检验数都小于等于零，因此已经由于上表中所有检验数都小于等于零，因此已经 得到最优解，最优解为：得到最优解，最优解为： 4

35、00024 654321 xxxxxx， 代入目标函数得最优值：代入目标函数得最优值：14z 当计算检验数有相同值的时候，可从中任选一个变量当计算检验数有相同值的时候，可从中任选一个变量 作为换入变量。作为换入变量。 当计算当计算 值出现相同时，也可以从中任选一个作为换值出现相同时，也可以从中任选一个作为换 出变量出变量 注意：注意： 2021/3/1157 5 5单纯形法的进一步讨论单纯形法的进一步讨论 一、人工变量法 考察上一节例考察上一节例5中的线性规划问题：中的线性规划问题： 0, 124 16 4 82 1222 32max 21 2 1 21 21 21 xx x x xx xx

36、xxz 2021/3/1158 化标准形为：化标准形为： 0, 12 4 16 4 8 2 12 22 000032max 21 62 51 421 321 654321 xx xx xx xxx xxx xxxxxxz 它的系数矩阵是：它的系数矩阵是： 100040 010004 001021 000122 2021/3/1159 由于由于系数矩阵中存在单位阵系数矩阵中存在单位阵，很容易找到初始可行，很容易找到初始可行 基。但存在着不同的情况，考察下面的线性规划问题：基。但存在着不同的情况，考察下面的线性规划问题： 化为标准型：化为标准型： 0, 9 3 1 2 4 003max 54321

37、 32 5321 4321 5431 xxxxx xx xxxx xxxx xxxxz 0, 93 1 2 4 3max 321 32 321 321 31 xxx xx xxx xxx xxz 例例6 2021/3/1160 该问题的系数矩阵为：该问题的系数矩阵为： 00130 10112 01111 54321 PPPPP 这个矩阵中不含有单位矩阵，因此很难找到初始基。这个矩阵中不含有单位矩阵，因此很难找到初始基。 对于这种线性规划问题的系数矩阵不含有单位对于这种线性规划问题的系数矩阵不含有单位 矩阵的情况，我们往往采用添加矩阵的情况，我们往往采用添加人工变量人工变量 的方法，的方法， 来

38、人为构造一个单位矩阵。这样的方法就是来人为构造一个单位矩阵。这样的方法就是人工人工 变量法变量法。 2021/3/1161 为了构造出单位矩阵，在系数矩阵中添加两列单位为了构造出单位矩阵，在系数矩阵中添加两列单位 列向量，系数矩阵变为：列向量，系数矩阵变为： 1000130 0110112 0001111 7654321 PPPPPPP 线性规划问题的约束条件就变为：线性规划问题的约束条件就变为： 0, 9 3 1 - 2 4 7654321 732 65321 4321 xxxxxxx xxx xxxxx xxxx 2021/3/1162 因为因为 、 是人为添加的，因此其对应的变量是人为添

39、加的，因此其对应的变量 、 称为称为人工变量人工变量。 6 P 7 P6 x 7 x 目标函数中人工变量的系数：目标函数中人工变量的系数： 添加人工变量前，在线性规划问题的标准形中，添加人工变量前，在线性规划问题的标准形中， 各约束条件已经是等式约束了，因此为了保证等式约各约束条件已经是等式约束了，因此为了保证等式约 束满足不变，在最优解中，人工变量的取值必须为束满足不变，在最优解中，人工变量的取值必须为0。 为此，令目标函数中人工变量的系数为为此，令目标函数中人工变量的系数为任意大的任意大的 一个负值一个负值，用，用“ ”来表示，这样，只要人工变量来表示，这样，只要人工变量 取值不为零，则目

40、标函数就不能达到极大化。取值不为零，则目标函数就不能达到极大化。 M 目标函数变为：目标函数变为： 765431 003maxMxMxxxxxz 添加添加 M 来处理人工变量的方法，称为大来处理人工变量的方法，称为大M 法法 2021/3/1163 求解过程：求解过程： 2021/3/1164 因此最优解为：因此最优解为： T X 0 , 0 , 0 , 0 , 2 3 , 2 5 , 0 2 3 maxz 2021/3/1165 二、两阶段法 用大用大 M 处理人工变量时，用计算机求解会出现处理人工变量时，用计算机求解会出现 错误，由此产生了两阶段法。错误，由此产生了两阶段法。 第一阶段：先

41、求解一个目标函数中只含有人工第一阶段：先求解一个目标函数中只含有人工 变量的线性规划问题。变量的线性规划问题。 即令目标函数中其它变量的系数取零，人工变即令目标函数中其它变量的系数取零，人工变 量的系数取某个正的常数（一般取量的系数取某个正的常数（一般取1），在保持原问），在保持原问 题约束条件不变的情况下求这个目标函数极小化时题约束条件不变的情况下求这个目标函数极小化时 的解。的解。 第二阶段：从第一阶段的最终单纯形表出发，第二阶段：从第一阶段的最终单纯形表出发， 去掉人工变量，按原问题的目标函数，继续寻找原去掉人工变量，按原问题的目标函数，继续寻找原 问题的最优解。问题的最优解。 2021

42、/3/1166 三、关于解的判别 当所有当所有 时，又对某个非基变量时，又对某个非基变量 有有 且可以找到且可以找到 ，则该线性规划问题有无穷，则该线性规划问题有无穷 多最优解。多最优解。 0 j i x0 i 0 例例7. 求解线性规划问题求解线性规划问题 0, 12 4 16 4 82 1222 21 2 1 21 21 xx x x xx xx 21 42maxxxz 2021/3/1167 解：解： 在图解法中，我们知道这个问题有无穷多解。在图解法中，我们知道这个问题有无穷多解。 它的标准形为：它的标准形为： 6 , 2 , 10 12 4 16 4 8 2 12 22 62 51 4

43、21 321 jx xx xx xxx xxx j 654321 000042maxxxxxxxz 2021/3/1168 用单纯形法计算，得到最终单纯形表为：用单纯形法计算，得到最终单纯形表为： 从表中可以得到最优解：从表中可以得到最优解： T X0 , 8 , 0 , 2 , 3 , 2 1 它对应的目标函数值为：它对应的目标函数值为：14z 2021/3/1169 在上表中，非基变量在上表中，非基变量 的检验数为的检验数为0，如果将，如果将 换入基变量，得：换入基变量，得： 6 x 6 x 从表中可以得到新的最优解：从表中可以得到新的最优解： T X4 , 0 , 0 , 0 , 2 ,

44、 4 2 它对应的目标函数值为：它对应的目标函数值为：14z 因此因此 和和 连线上所有的点都是最优解，该连线上所有的点都是最优解，该 问题有无穷多最优解。问题有无穷多最优解。 1 X 2 X 2021/3/1170 例例8. 求解线性规划问题求解线性规划问题 0, 16 4 21 1 xx x 21 32maxxxz 解：用图解法求解时知道该问题有无界解，解：用图解法求解时知道该问题有无界解， 它的标准形为：它的标准形为： 0, 16 4 321 31 xxx xx 321 032maxxxxz 2021/3/1171 用单纯形表求解过程如下：用单纯形表求解过程如下： 表中表中 ，但，但 列

45、数字为零，因此列数字为零，因此 的取的取 值可无限增大，所以目标函数值也可随之无限增值可无限增大，所以目标函数值也可随之无限增 大，说明问题的解无界。大，说明问题的解无界。 0 2 2 x 2 x 2021/3/1172 例例9. 求解线性规划问题求解线性规划问题 12 12 12 2212 214 ,0 xx xx x x 21 32maxxxz 解：利用图解法，我们已经知道该问题无可行解，解：利用图解法，我们已经知道该问题无可行解， 将其化为标准形：将其化为标准形： 5 , 4 , 3 , 2 , 10 14 2 12 22 5421 321 jx xxxx xxx j 54321 003

46、2maxMxxxxxz 2021/3/1173 该问题单纯形法求解如下：该问题单纯形法求解如下： 当所有当所有 时，人工变量时，人工变量 仍然留在基变量中，仍然留在基变量中， 而且不为零，故问题无可行解。而且不为零，故问题无可行解。 0 j 5 x 2021/3/1174 四、单纯形法小结 对给定的线性规划问题应首先化为标准形式；对给定的线性规划问题应首先化为标准形式； 选取或构造一个单位矩阵作为基；选取或构造一个单位矩阵作为基； 求出初始可行解并列出初始单纯形表；求出初始可行解并列出初始单纯形表； 计算检验数，判断是否最优解；计算检验数，判断是否最优解； 寻找换入及换出变量，构造新的单纯形表

47、；寻找换入及换出变量，构造新的单纯形表； 求出最优解。求出最优解。 2021/3/1175 6 6改进单纯形法改进单纯形法 用矩阵形式描述线性规划的标准形式为：用矩阵形式描述线性规划的标准形式为： 0 max X bAX CXz 由于在转化成标准形时，总可以构造一个单位矩由于在转化成标准形时，总可以构造一个单位矩 阵作为初始单纯形表中的基。阵作为初始单纯形表中的基。 因此将矩阵因此将矩阵 A 分成作为分成作为初始基的单位矩阵初始基的单位矩阵 I 和和 非基变量系数矩阵非基变量系数矩阵 N 两块。两块。 把把新单纯形表中的基（新表中的新单纯形表中的基（新表中的 I ），对应的），对应的 初始单纯

48、形表中的那些向量初始单纯形表中的那些向量抽出来，单独列成一块，抽出来，单独列成一块， 用用B 表示。表示。 2021/3/1176 初始单纯形表可以改写为：初始单纯形表可以改写为： 单纯形法的迭代计算实际上就是对约束方程系数矩阵单纯形法的迭代计算实际上就是对约束方程系数矩阵 实施的初等变换。对矩阵（实施的初等变换。对矩阵（b | B | N | I）实施初等变）实施初等变 换时，当换时，当 B 变为变为 I ，I 将变换为将变换为 B-1。因此，上述矩阵。因此，上述矩阵 变为（变为（ B-1 b | I | B-1 N | B-1 ）,新单纯形表可写为：新单纯形表可写为： 2021/3/117

49、7 显然：显然： bBb 1 NBN 1 jj PBP 1 11 1 0, BCBCyyY BBm NBCCNCC BNBNN 1 jBjjBjj PBCcPCc 1 0 1 BBCC BBI 利用这些公式，我们来研究改进单纯形法利用这些公式，我们来研究改进单纯形法 2021/3/1178 改进单纯形法的步骤：改进单纯形法的步骤： 在下一步迭代的基变量确定后，新基可行解为：在下一步迭代的基变量确定后，新基可行解为： 计算非基变量的检验数计算非基变量的检验数 和和 产生产生 列的数字，有列的数字，有 ，如，如 ，线，线 性规划问题有无界解，计算结束。否则寻找换出性规划问题有无界解，计算结束。否则

50、寻找换出 变量：变量： 用非基变量用非基变量 替换基变量替换基变量 ，得出下一步中的，得出下一步中的 基变量。基变量。 重复上述步骤，直到计算结束。重复上述步骤，直到计算结束。 bBX B 1 NBCC BNN 1 1 BCY B kk PBP 1 0 k P lk l ik ik i i PB bB PB PB bB 1 1 1 1 1 0min k x l x k P 2021/3/1179 B-1的求法：的求法： 10 010 01 1 lkmk lk lkk aa a aa D令令 将将 D 左乘迭代前的基的逆矩阵左乘迭代前的基的逆矩阵 ，就得到迭，就得到迭 代后基的逆矩阵代后基的逆矩

51、阵 。 1 old B 1 new B 2021/3/1180 例例10. 用改进单纯形法求解用改进单纯形法求解 0, 15 3 9 62 24max 21 21 21 21 21 xx xx xx xx xxz 解：其标准形为解：其标准形为 0, 15 3 9 6 2 00024max 51 521 421 321 54321 xx xxx xxx xxx xxxxxz 2021/3/1181 因此因此 13 11 21 N 15 9 6 b （1）确定初始解）确定初始解 0 , 0 , 0, 543 cccCB 2 , 4, 21 ccCN 找出约束条件中的单位矩阵找出约束条件中的单位矩阵

52、 I 作为基，初始解：作为基，初始解： 15 9 6 5 4 3 b x x x X B ， 2021/3/1182 非基变量检验数：非基变量检验数：2 , 4, 21 NCC BNN 因此因此 是换入变量，是换入变量， 且且 3 1 1 31 21 11 1 a a a P 1 x1k 5 3 15 3 15 , 1 9 ,min 由于由于 因此因此 是换出变量，是换出变量， 。 5 x3l 且且3 31 aalk在基变量中，在基变量中， 表示的是第三行。表示的是第三行。 5 x 2021/3/1183 （2）第一次迭代）第一次迭代 新的基变量：新的基变量： T B xxxX 143 , 逆

53、矩阵逆矩阵 3100 3110 3101 100 010 001 3100 3110 3101 100 010 001 100 10 01 31 3121 3111 1 a aa aa B 2021/3/1184 5 4 11 15 9 6 3100 3110 3101 1 1 4 3 2 BB XB x x x X 4 , 0 , 0, 143 2 cccCB N 中只对应变元中只对应变元 ，因此，因此 2 x 3 10 1 1 2 3100 3110 3101 4 , 0 , 02 2 1 2 PBCc BN 2021/3/1185 3 4 31 31 31 4 , 0 , 0 5 1 P

54、BCY B 最大正检验数为最大正检验数为10/3，即，即 为换入变量，又为换入变量，又 2 x 31 34 35 1 1 2 3100 3110 3101 2 P 3, 3 , 5 33 min 所以所以 为换出变量。为换出变量。 4 x 2021/3/1186 （3）第二次迭代）第二次迭代 新的基变量为：新的基变量为： T B xxxX 123 3 , 41410 41430 43451 3100 3110 3101 1410 0430 0451 1 B 6 3 6 15 9 6 41410 41430 43451 1 2 3 3 x x x X B 4 , 2 , 0 B C0 2 1 ,

55、 4 10 N 因为所有检验数为零，所以最优解为：因为所有检验数为零，所以最优解为： 0 , 0 , 6 , 3 , 6X 2021/3/1187 7. 7. 应用举例及应用举例及MatlabMatlab求解法求解法 例例11. 工业原料的合理利用工业原料的合理利用 要制作要制作100套钢筋架子，每套有长套钢筋架子，每套有长2.9m、2.1m和和 1.5m的钢筋各一根。已知原料长的钢筋各一根。已知原料长7.4m，应如何切割，应如何切割， 使用原料最节省（扔掉的料头最小）。使用原料最节省（扔掉的料头最小）。 考察如下方案的综合使用：考察如下方案的综合使用： 2021/3/1188 解解：该问题的

56、线性规划数学模型如下：该问题的线性规划数学模型如下 5 , 10 1003 2 3 100 22 100 2 8 . 03 . 02 . 01 . 0min 5321 543 421 5432 jx xxxx xxx xxx xxxxz j 该问题要用单纯形法求解，需要添加人工变量：该问题要用单纯形法求解，需要添加人工变量： 8 , 10 100 3 2 3 100 22 100 2 8 . 03 . 02 . 01 . 0max 85321 7543 6421 8765432 jx xxxxx xxxx xxxx MxMxMxxxxxz j 2021/3/1189 利用大利用大 M 法求解，

57、得到：法求解，得到： T X0 , 0 , 0 , 0 ,50, 0 ,10,30 16minz 2021/3/1190 例例12. 混合配料问题混合配料问题 某糖果厂用原料某糖果厂用原料A、B、C 加工成三种不同牌号的加工成三种不同牌号的 糖果甲、乙、丙。已知各种牌号糖果中糖果甲、乙、丙。已知各种牌号糖果中A、B、C 含量，含量， 原料成本，各种原料的每月限制用量，三种牌号糖果的原料成本，各种原料的每月限制用量，三种牌号糖果的 单位加工费及售价如下表，问该厂每月生产这三种牌号单位加工费及售价如下表，问该厂每月生产这三种牌号 糖果各多少千克，使该厂获利最大，试建立该问题的线糖果各多少千克，使该

58、厂获利最大，试建立该问题的线 性规划数学模型。性规划数学模型。 2021/3/1191 解：解：用用 i = 1 , 2 , 3 分别代表原料分别代表原料A、B、C，用，用 j = 1, 2, 3 分别代表甲、乙、丙三种糖果。设分别代表甲、乙、丙三种糖果。设 xij 为生产第为生产第 j 种种 糖果使用的第糖果使用的第 i 种原料的质量，则问题的数学模型可种原料的质量，则问题的数学模型可 归结为：归结为： 目标函数目标函数 332313 322212312111 333231232221 131211332313 322212312111 95. 045. 005. 0 45. 195. 04

59、5. 09 . 14 . 19 . 0 0 . 11.50 0 . 230. 025. 2 40. 085. 250. 040. 3max xxx xxxxxx xxxxxx xxxxxx xxxxxxz 2021/3/1192 约束条件为约束条件为 含量要求条件 原料供应限制 3 , 2 , 1; 3 , 2 , 10 6 . 0 5 . 0 3 . 0 2 . 0 6 . 0 1200 2500 2000 33231333 32221232 32221212 31211131 31211111 333231 232221 131211 jix xxxx xxxx xxxx xxxx xxx

60、x xxx xxx xxx ij 2021/3/1193 例例13. 投资项目的组合问题投资项目的组合问题 兴安公司有一笔兴安公司有一笔 30 万元的资金，考虑今后三年内万元的资金，考虑今后三年内 用于下列项目的投资：用于下列项目的投资： 1. 三年内的每年年初均可投入，每年获利为投资三年内的每年年初均可投入，每年获利为投资 额的额的 20%，其本利可一起用于下一年的投资；，其本利可一起用于下一年的投资； 2. 只允许第一年初投入，于第二年年末收回，本只允许第一年初投入，于第二年年末收回，本 利合计为投资额的利合计为投资额的150%，但此类投资限额，但此类投资限额15万以内；万以内； 3. 允