第一章线性规划与单纯形法运筹学教程培训课件.ppt

1、第一章线性规划与单纯形法运筹学教程优选第一章线性规划与单纯形法运筹学教程第一节 运筹学释义和发展简史运筹学是一门应用科学应用科学，它广泛应用现有的科学技术知识和数学方法科学技术知识和数学方法，解决生产和管理过程中提出的专门问题，为决策者选择最优方案提供为决策者选择最优方案提供定量依据定量依据。运筹学管理科学用科学（系统化的知识）代替凭经验的方法1914，战斗方程1935，Bawdsey雷达站的研究1942，大西洋反潜作战协助英国打破德国对英吉利海峡的封锁将反潜攻击由潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米改为25米。运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模，减少

2、批次，这样损失率将减少141第二节 运筹学研究的基本特征和基本方法基本特征系统的整体观念多学科的综合模型方法的应用研究的基本步骤分析和表述问题建立模型求解模型和优化方案测试模型及对模型进行必要的修正建立对解的有效控制方案的实施第三节 运筹学的主要分支线性规划非线性规划动态规划图论与网络分析存储论排队论对策论决策论运筹学的主要内容第一章 线性规划与单纯形法第二章 对偶理论与灵敏度分析第三章 运输问题第四章 目标规划第五章 整数规划第十章 图与网络分析第十二章 排队论x1,x2,xn0,xn+1,xn+2,xn+m05 单纯形法的进一步讨论线性规划问题的几何意义|可行解min z=3x1+x2+x

3、31942，大西洋反潜作战246810121416184、通常变量有符号约束或整数约束或01变量约束max z=50(AC+AP+AH)+35(BC+BP+BH)+25(DC+DP+DH)65(AC+BC+DC)25(AP+BP+DP)35(AH+BH+DH)4x1 +x4 =16 1.1942，大西洋反潜作战x1 +x3+3x4+x5+2x6+3 x7+4x8 1009m的元钢不少于100根：x1、x2 0(i=1,2,m)(1.运筹学学习方法1、课前预习2、认真听课，适当笔记3、认真作业运筹学有一定难度，该课程有一定的研究性特征；以线性代数和概率论为基础运筹学 解决问题的主要程序建立数学模

4、型（线性规划数学模型）求解数学模型（图解法与单纯形法）分析求解结果（对偶问题与灵敏度分析）生产问题管理问题第一章 线性规划与单纯形法2 线性规划问题的几何意义线性规划问题的几何意义3 4 5 6 应用举例应用举例线性规划(运筹学)主要解决两类问题企业利润=收入成本收入由提供产品或服务获得成本由消耗的资源承担1、资源有限（获成本），要求生产的产品获得的收入（或利润）最多。12、任务（或产品收入）一定，要求消耗的资源（或成本）最少。2线性规划中的两类数学模型11、max 总收入或总利润 总成本b 返回线性规划中的两类数学模型22、min 总成本 总收入b 返回2）表格单纯形法1、设(未知数)决策变

5、量1 线性规划问题 及其数学模型(最优值)minz=90 x1+2x2 8min z=x1+x2+x3+x4+x5+x6+x7为了使目标函数值增加最快，从直观上一般选j0种的大者（可以任意选或按最小下标选）即max(j0)=k例 2 环境保护问题线性规划的数学模型的一般形式AC+BC+DC100指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。x1=4,x2=1,x3=9,x4=x5=x6=x7=0,最优值z=22 x1+2 x2 18x1+2x2 8123456789令 ，（j=m+1,n）线性规划问题的解的概念从第一化工厂排出的工业污水流到第二化工厂以前,有20

6、%可以净化.4x1+6x2 48目标函数 Max Z=2x1+3x21 1 1.1 问题的提出线性规划是运筹学的一个重要分支。线性线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、到工业、农业、商业、交通运输业、军事

7、、经济计划和管理决策等领域都可以发挥作经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。用。它已是现代科学管理的重要手段之一。将生产经营和管理过程中的决策问题 转化成数学模型例1:生产计划问题(步骤)x1III资资源源限限量量设设备备原原材材料料A原原材材料料B1402048 台台时时16kg12kg利利润润23x2产品产品I产品产品2x1x2x1x2z4x2 124x1 16min z=x1+x2+x3+x4+x5+x6+x7是凸集.为了确定初始基可行解，首先找出初始可行基，其方法如下对所有约束条件是“”形式的不等式及等式约束情况，若不存在单位矩阵时，就采取人造基的方

8、法。4 x1+6 x2 48例6 求解下面的线性规划max z=15AC+25AP+15AH30BC+10BP40DC10DH整理得到本问题的数学模型为线性规划问题的解的概念基、基变量、非基变量、基向量、非基向量、基解、基可行解、可行基以线性代数和概率论为基础最优解（Optimal solution)246810121416184 x1+6 x2 48例 2 环境保护问题x1=10，x2=50，x4=30X(0)=(0,0,8,16,12)再 （j=m+1,n）问每个厂各应处理多少工业污手,使这两个工厂总的处理工业污水费用最小.III资资源源限限量量设设备备原原材材料料A原原材材料料B1402

9、048台台时时16kg12kg利利润润231xx2建立线性规划数学模型的步骤1、选择适当的决策变量l设决策变量的原则2、用决策变量表达目标函数l收入或利润极大化l成本或支出极小化3、用决策变量表达所有的约束条件4、注意变量的符号约束返回 工厂1（工业污水2万m3）治污成本 1000元/万m3 500万m320%自然净化 200万m3 工厂2 （工业污水1.4万m3）治污成本800元/万m3 要求污水含量不大于0.2%(步骤)长江长江嘉陵江嘉陵江朝天门朝天门说明从第一化工厂排出的工业污水流到第二化工厂以前,有20%可以净化.江水中要求污水含量不大于0.2%.工厂1和工厂2的污水净化成本分别为10

10、00元/万m和800元/万m问每个厂各应处理多少工业污手,使这两个工厂总的处理工业污水费用最小.设设：化工厂1每天处理的污水量为x1万立方米；化工厂2每天处理的污水量为x2万立方米建模型之前的分析和计算100027004128021000250022211)x.()x(.)x(工厂后的水质要求：经第工厂前的水质要求：经第整理得到本问题的数学模型为0,4.126.18.018001000min212121121xxxxxxxxxz约束条件目标函数例3 合理下料问题书上P38例10原材料，长原材料，长7.4米米一套钢架一套钢架任务：任务：100套钢架套钢架目标：成本最少目标：成本最少2.9m2.1

11、m1.5m分析下料的方式方 式x1x2x3x4x5x6x7x8元钢2.9m211100002.1m021032101.5m10130234余料0.10.30.901.10.40.81.4原材料7.4m2x1+x2+x3+x41002x2+x3+3x5+2 x6+x7+x8 100 x1+x3+3x4+x5+2x6+3 x7+4x8 100数学模型为min z=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x4100 2x2+x3 +3x5+2 x6+x7+x8 100 x1 +x3+3x4+x5+2x6+3 x7+4x8 100 xj 0，xj 为整数，j=1,2,8x1=

12、10，x2=50，x4=30(最优值)minz=90模型建立1、设(未知数)决策变量设按方案下料的原材料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5，2、用决策变量表达目标函数min z=0 x1+0.1 x2+0.2x3+0.3x4+0.8x5 3、用决策变量表达全部的约束条件4、注意符号约束方 式x1x2x3x4x5元钢2.9m120102.1m002211.5m31203余料00.10.20.30.80,1003231002210028.03.02.01.00min54321532154342154321xxxxxxxxxxxxxxxxxxxxz教材上的模型说明上题计算求得

13、如下方案:x1=30,x2=10,x4=50,其余为0.即按方案1下料30根,按方案2下料10根,按方案4下料50根,总共需要90根原材料可以制造100套钢架.例4 人事管理问题一个企业每周七天都要生产或营业每个工作人员每周连续5天据分析每天的上班人数分别60、40、50、30、65、70和75人问该企业至少需要多少个职工？模型建立1、设(未知数)决策变量设从星期一开始上班的人数为x1,星期二开始上班的人数为x2，星期三开始上班的人数为x3，星期四开始上班的人数为x4,星期五开始上班的人数为x5，星期六开始上班的人数为x6，星期日开始上班的人数为x7。2、用决策变量表达目标函数min z=x1

14、+x2+x3+x4+x5+x6+x73、用决策变量表达全部的约束条件4、注意符号约束min z=x1+x2+x3+x4+x5+x6+x7x4+x5+x6+x7+x1 60 x5+x6+x7+x1+x2 40 x6+x7+x1+x2+x3 50 x7+x1+x2+x3+x4 30 x1+x2+x3+x4+x5 65x2+x3+x4+x5+x6 70 x3+x4+x5+x6+x7 75xj 0，xj 为整数，j=1,2,7数学模型为x1=9，x2=0，x3=23，x4=19，x5=14，x6=19，x7=0(最优值)minz=84max z=50(AC+AP+AH)+35(BC+BP+BH)+25

15、(DC+DP+DH)65(AC+BC+DC)25(AP+BP+DP)35(AH+BH+DH)246810121416182 线性规划问题的几何意义4x1+6x2 48指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。定理3：若可行域有界，线性规划|x1、x2 0 xm+am,m+1xm+1+amnxn=bm2、用决策变量表达目标函数问每个厂各应处理多少工业污手,使这两个工厂总的处理工业污水费用最小.1、找一个基可行解X0作为初始解;123456789Max Z=2x1+3x22x1+2x2 18x1、x2 0约束条件 x1+2x2 8重复（2）（5），直到终止。例9

16、 用两阶段法求解下面的线性规划问题对应于基B2的基解X2设决策变量的原则1、将决策者想知道但还不知道的设为未知数；（返回）2、所取决策变量要便于表达目标函数和约束条件。3、当将决策者想知道但还不知道的是由多个部分组成时，则应将最基本的部分取为决策变量。(作业)建立线性规划数学模型的步骤1、选择适当的决策变量l设决策变量的原则2、用决策变量表达目标函数l收入或利润极大化l成本或支出极小化3、用决策变量表达所有的约束条件4、注意变量的符号约束返回线性规划数学模型 的特点1、一组决策变量(x1,x2,xn)l决策者可选择2、一个目标函数l极大化或极小化l是决策变量的线性函数lMax(或min)z=c

17、1x1+c2x2+cnxn3、一组约束条件l决策变量的线性等式或不等式组4、通常变量有符号约束lxjP38例11 配料问题产品原材料产价品格CPHA50%25%50B 25%50%35D25原材料供应量10010060原材料价格652535模型建立1、设(未知数)决策变量设A产品中含原材料C、P、H的数量分别为AC、AP、AH B产品中含原材料C、P、H的数量分别为BC、BP、BH D产品中含原材料C、P、H的数量分别为DC、DP、DH。2、用决策变量表达目标函数(利润=销售收入成本)max z=50(AC+AP+AH)+35(BC+BP+BH)+25(DC+DP+DH)65(AC+BC+DC

18、)25(AP+BP+DP)35(AH+BH+DH)=15AC+25AP+15AH30BC+10BP40DC10DH3、用决策变量表达全部的约束条件4、注意符号约束约束条件),BB(B21),BB(B41),AA(A41),AA(A21HPCHPCHPCHPCPCPCBBAA0214121041414304143410212121HPCHPCHPCHPCBBBBBBAAAAAA整理得AC+BC+DC100AP+BP+DP100AH+BH+DH60含量约束原材料数量约束数学模型为max z=15AC+25AP+15AH30BC+10BP40DC10DH60DBA100DBA100DBA021412

19、1041414304143410212121HHHPPPCCCHPCHPCHPCHPCBBBBBBAAAAAAAC、AP、AH，BC、BP、BH，DC、DP、DH0能够求得最优解和最优值最优解l需要用原料C为100kg，P为50kg，H为50kg，构成产品A。其它产品不生产。l即每天只生产产品A为200kg，分别需要用原料C为100kg，P为50kg，H为50kg。最优值即总利润是z=500元/天。生产与库存的优化安排某工厂生产五种产品（i=1，.，5），上半年各月对每种产品的最大市场需求为dij。已知每件产品的单件售价为Si元，生产每件产品所需要的工时为ai，单件成本为Ci元；该工厂上半年各

20、月正常生产工时为ri（j=1，.，6），各月允许的加班工时为ri,Ci为加班单件成本。又每月生产的各种产品如当月销售不完，可以库存。库存费用为Hi（元/件.月)。假设1月初所有产品的库存为0，要求6月末个产品库存量为ki件。现要求为该厂制定一个生产计划，在尽可能利用生产能力的条件下，获取最大利润。设xij，xij分别为该厂第i种产品第j个月在正常时间和加班时间内的生产量；yii为i种产品在第j个月的销售量，wij为第i种产品第j月末的库存量。516151i61jii6i0 15151maxkw0,w)1,.,6j 1,.,5;(i dijyii1,.,6)(j 1,.,6)(j ijijiij

21、iijiiiiijijiji,jijijijiijijiwHxCxCySzyxxwwrxarxa例4 运输问题P80,产销平衡表 单位吨 销地加工厂B1B2B3B4产量A1A2A3 317119432101085749 销量3656作业P46 习题1.9，提示设从第i个班次开始上班的人数为xi,i=1,2,6习题1.10二、线性规划数学模型 的特点1、一组决策变量(x1,x2,xn)决策者可选择2、一个目标函数极大化或极小化是决策变量的线性函数Max(或min)z=c1x1+c2x2+cnxn3、一组约束条件决策变量的线性等式或不等式组4、通常变量有符号约束或整数约束或01变量约束xj；xj为

22、整数；xj=0或1xm+am,m+1xm+1+amnxn=bm2、用决策变量表达目标函数若有两个以上的j0，那么选哪个非基变量作为换入变量呢？x1、x2 02x1+2x2 18它已是现代科学管理的重要手段之一。1、max 总收入或总利润例7 试用上述方法计算例6的两个基变换。Max Z=34 x1+40 x2现用x2去替换x5,于是将x3，x4，x2的系数矩阵变换为单位矩阵矩阵形式表示线性规划问题123456789二、线性规划数学模型 的特点am,m+1当存在正的检验数时,该基可行解就不是最优解,就要换到一个新的(与X0相邻的)基可行解（X1）例6 求解下面的线性规划2、一个单纯形表中，基变量

23、的系数矩阵是单位矩阵;2x1+x2 4一个企业每周七天都要生产或营业（5）以alk为主元素进行迭代（即用高斯消去法或称为旋转运算），把xk所对应的列向量目标函数 Max Z=2x1+3x2 0,.,),(.),(.),(.)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax0,.,0,.,.2121221122222121112121112211mnmnmnmmnnnnnnbbbxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMax1、目标函数最大、目标函数最大2、约束条件等式

24、、约束条件等式3、决策变量非负、决策变量非负4、右端系数非负、右端系数非负目标函数：约束条件：将下述线性规划化为标准形式取值无约束321321321321321,0,063244239232 xxxxxxxxxxxxxxxZMin向量形式表示线性规划问题n,j;bbbb;aaaP;xxxX;c,c,cCn,j,xbxPCXzmax:Mmmjjjjnnjnjjj 212102121212111约束条件：目标函数：Tnnmnmn x,x,xX;P,P,PaaaaAXbAXCXzmax:M21m12111111bbb0000决策变量向量：；资源向量：零向量：系数矩阵：约束条件：目标函数：矩阵形式表示

25、线性规划问题作目标函数等值线，确定使目标函数最优的移动方作目标函数等值线，确定使目标函数最优的移动方向；向；平移目标函数的等值线，找出最优点，算出最优值。平移目标函数的等值线，找出最优点，算出最优值。1.2 线性规划问题的图解法 适用于两个自变量9 8 7 6 5 4 3 2 1 0|123456789x1x2x1+2x2 8(0,4)(8,0)4x1 164 x2 129 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 12可行域可行域9 8 7 6 5 4 3 2 1 0|123456789x1x2x1+2x2 84x1 164 x2

26、12可行域可行域BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 12BCDEA可行基对应基可行解的基称为可行基假设1月初所有产品的库存为0，要求6月末个产品库存量为ki件。X(0)=(0,0,8,16,12)线性规划问题的几何意义4x1+6x2 481942，大西洋反潜作战24）式代入目标函数（1.特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。z x1 x2 xm xm+1 xn b这就得到初始即可行解X(0)=(0,0,8,16,12)TB产品中含原材料C、P、H的数量

27、分别为BC、BP、BH1234567892、用决策变量表达目标函数线性规划问题求解的 几种可能结果最优解（Optimal solution)X3=8-2x2=0|运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模，减少批次，这样损失率将减少9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 12BCDEAx1+2x2=8 4x1=16x26 5 4 3 2 1 0|123456789x16 5 4 3 2 1 0 x2|123456789x1 x2x118 16 14 12 10 8 6 4 2 0|24681012141618x1

28、x24x1+6x2 482x1+2x2 182x1+x2 1618 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16可行域可行域ABCDE18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)x218 16

29、14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)4x1+6x2=48 2x1+2x2=18图解法图解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 16可行域可行域BCDEA可行域为凸集可行域为凸集目标函数不同时目标函数不同时等值线的斜率不同等值线的斜率不同最优解在顶点产生最优解在顶点产生 目标函数等目标函数等值线的斜率值线的斜率最优解最优解图解法图解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x

30、1+2x2 84x1 164 x2 16可行域可行域BCDEA可行域为凸集可行域为凸集目标函数不同时目标函数不同时等值线的斜率不同等值线的斜率不同最优解在顶点产生最优解在顶点产生 目标函数等目标函数等值线的斜率值线的斜率最优解最优解图解法图解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 16可行域可行域BCDEA可行域为凸集可行域为凸集目标函数不同时目标函数不同时等值线的斜率不同等值线的斜率不同最优解在顶点产生最优解在顶点产生 目标函数等目标函数等值线的斜率值线的斜率最优解最优解第三节第三节 单纯形法原理单纯形法原理一、线性规划问题

31、解的概念一、线性规划问题解的概念标准型可行解:满足AX=b,X=0的解X称为线性规划问题的可行解。最优解使Z=CX达到最大值的可行解称为最优解。0 max XbAXCXZ 基若B是矩阵A中mm阶非奇异子矩阵（|B|0），则B是线性规划问题的一个基。不妨设),.,(,.,.,.,11111mmmmmPPaaaaBjPjXjX ,j=1，2，,m 基向量。，j=1，2，,m 基变量。,j=m+1,n 非基变量。例0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz基、基变量、非基变量、基向量、非基向量、基解、基可行解、可行基100010

32、040004121,54321PPPPPA54321,PPPPP54321,xxxxx例0400041211B321,PPP行列式0160000160040004121|1B基变量非基变量基向量非基向量321,xxx54,xx321,PPP54,PP对应于基B1的基解X112 4 16 48 25241321xxxxxxx)0,0,2,3,4(1X非基可行解例1000100012B543,PPP行列式01000001100010001|2B基变量非基变量基变量非基变量543,xxx21,xx543,PPP21,PP对应于基B2的基解X212 4 16 48 25241321xxxxxxx)12

33、,16,8,0,0(2X基可行解 求解 nmnnmmmmmmmmmmxaaxaabbxaaxaa.111111111110 max XbAXCXZ基解称上面求出的X解为基解。基可行解非负的基解X称为基可行解可行基对应基可行解的基称为可行基TmBxxxX).,(210.21nmmxxx)0,.,0,0,.,(21mbbbX T基变量令 可求出：线性规划解的关系图可行解可行解 基可行解基可行解 最优解？最优解？例求基解、基可行解、最优解。max,.,zxxxxxxxxxxxii235210401251231312425x1x2x5x4x3z1 0 0 5 10 4 5 Y 2 0 4 5 2 0

34、17 Y 3 5 0 0 5 4 10 Y 4 0 5 5 0 -1 20 N5 10 0 -5 0 4 15 N6 5 2.5 0 0 1.5 17.5 Y 7 5 4 0 -3 0 22 N8 2 4 3 0 0 19 Y 是否基是否基可行解可行解最优解最优解解：解：求基解、基可行解、最优解。0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz3.的秩是A 1 0 0 4 00 1 0 0 40 0 1 2 1A练习：单纯形法原理举例 例6 求解下面的线性规划max z=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2

35、+x3 =8 4x1 +x4 =16 1.12 4x2 +x5=12 x1,x2,x3,x4,x501、找一个基可行解X0作为初始解;l最容易得到的可行基是标准型线性规划的系数矩阵的单位矩阵.2、求检验数，检验X0是否为最优解（）求检验数l将约束方程组的基变量的系数矩阵化为单位矩阵（或将基变量用非基变量表出）；l通过代入或加减乘除消元法将目标函数中的基变量消去，则非基变量的系数即为检验数（）最优解的判别l当检验数全部小于或等于0时，该基可行解为最优解,求解可结束.l当存在正的检验数时,该基可行解就不是最优解,就要换到一个新的(与X0相邻的)基可行解（X1）Z=2x1+3x2+0X3=8-x1-

36、2x2X4=16-4x2X5=12-4x2目标函数的表达式中还存在正系数的非基变量,这表示目标函数还有增加的可能,就需要基变量和非基变量对换.一般取正系数最大的那个基变量x2为换入变量,那么取哪个基变量为换出变量呢?当将x2确定为换入变量,x1=0时,必须确保x3,x4,x5均非负.X3=8-2x2=0X4=16=0X5=12-4x2=0 x2必须满足:x2 0,并 且 对i=1,2,m有ai,m+k0,那么该线性规划问题具有无界解（或称无最优解）,21mbbb例x3=8 2x20 x4=160（1.15）x5=124x20此时最小比=min(8/2,12/4)=3是进基变量的最大取值，但是若

37、（1.15）式中x2的系数全部非负，则最小比为+，即x 2 可 以 取 到+，目 标 函 数 值 z=0+2x1+3x2 就可取到+，因此目标函数无界。3.4 3.4 基变换基变换 1、换入变量的确定由（1.27）式看到，当某些j0时，xj增加则目标函数还可以增大，这时要将某个非基变量xj换到基变量中去（称为换入变量）。若有两个以上的j0，那么选哪个非基变量作为换入变量呢？为了使目标函数值增加最快，从直观上一般选j0种的大者（可以任意 选 或 按 最 小 下 标 选）即max(j0)=k则对应的xk为换入变量。实际上换一次基将使目标函数值改进k。2、换出变量的确定按最小比值确定换出变量。3.5

38、 迭代（旋转运算）将约束条件的增广矩阵中新基变量的系数通过矩阵的行变换或Gauss变换变为单位矩阵。例7 试用上述方法计算例6的两个基变换。解 约束条件的增广矩阵为 x1 x2 x3 x4 x5 b 12100401601004800121当以x3，x4，x5为基变量，x1，x2为非基变量，令x1=x2=0，可得到一个基可行解X(0)=(0,0,8,16,12)现用x2去替换x5,于是将x3，x4，x2的系数矩阵变换为单位矩阵 经变换后为 x1 x2 x3 x4 x5 b令非基变量x1,x5=0,得到新的基可行解X(1)=(0，3，2，16，0)T34/10010160100422/10101

39、1.4 1.4 单纯形法的计算步骤单纯形法的计算步骤 与表格单纯形法线性规划问题X1 +a1,m+1xm+1+a1nxn=b1 x2 +a2,m+1xm+1+a2nxn=b2 xm+am,m+1xm+1+amnxn=bmz+c1x1+c2x2+cmxm+c m+1xm+1+cnxn=0为了便于迭代运算，可将上述方程组写成增广矩阵z x1 x2 xm xm+1 xn b 011000010000101211,222,2111,1nmmmmnmmnmnmcccccbaabaabaa若将z看成不参与基变换的基变量，它与x1，x2，xm的系数构成一个基，这时可采用行初等变换将c1,c2,cm变换为零，

40、使其对应的系数矩阵为单位矩阵，得到z x1 x2 xm xm+1 xn bmiiimiininmimiimmmnmmnmnmbcaccaccbaabaabaa1111,11,222,2111,10001100001000010可根据上述增广矩阵设计计算表如下cjc1 cm cm+1 cnCBxB bx1 xm xm+1 xnc1C2cm x1x2xm b1b2 bm 10 0 00 1 a1,m+1a2,m+1 am,m+1 a1na2n amn 12m-z0 0miiibc1mimiimacc11,1miininacc14.2 计算步骤（1）找出初始可行基，确定初始基可行解，建立初始单纯形表

41、。（2）检验各非基变量xj的检验数是则已得到最优解。可停止计算。否则，转入下一步。（3）在 中，若有某个对应项xk的系数列向量Pk0，则此问题是无界，停止计算。否则，转入下一步。nmjaccjmiijijj,1,01若nmjj,1,0（4）根据max(j0)=k,确定xk为换入变量，按规则计算可确定xl换入变量。转入下一步。（5）以alk为主元素进行迭代（即用高斯消去法或称为旋转运算），把xk所对应的列向量)0|min(iklikikiabaab010021mklkkkkaaaaP将xB列中的xl换为xk,得到新的单纯形表。重复（2）（5），直到终止。现用例1的标准型来说明上述计算步骤。（1）

42、根据例1的标准型，以x3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始即可行解X(0)=(0,0,8,16,12)T将有关数值填入表中，得到（对应于初始基可行解的）初始单纯形表。表13 cj23000cB xBBx1x2x3x4x50 x30 x40 x5816121402041000100014-3-z023000(初始)单纯形表的特点1、一个单纯形表对应于一个基可行解;2、一个单纯形表中，基变量的系数矩阵是单位矩阵;3、一个单纯形表中，目标函数中基变量的系数为零，非基变量的系数为检验数；4、检验数的计算既可用公式法，也可用消去法；5、一个单纯形表中，基可行解的基变量为右端常数；各

43、非基变量的检验数为1=c1z1=2(01+04+00)=22=c2z2=3(02+00+04)=3(2)因检验数中有正数，且P1,P2有正分量存在，转入下一步（3）max(1,2)=max(2,3)=3;对应的变量x2 为换入变量。计算=它所在行对应的x5为换出变量，x2所在的列与x5所在的行交叉处4为主元素。3)4/12,2/8min()0|(min22iiiiaab以4为主元素进行旋转运算，即初等变换，使P2变为（0，0，1）T,在xB列中将x2替换x5,于是得到新表14 表1.4cj23000cB xBBx1x2x3x4x50 x30 x40 x22163140001100010-1/2

44、01/424-z92000-3/4由于检验数有正数，还没有得到最优解，max(1,5)=max(2,3/4)=2=1,则x1为换入变量，=则x3为换出变量。以1为主元数进行旋转运算，得 2),4/16,1/2min()0|(min11iiiiaab表15 cjcB xBb2x13x20 x30 x40 x52 x10 x43 x22831000011-40010-1/221/4-412-z-13 00-201/4由于检验数有正数，还没有得到最优解，max(3,5)=max(2,1/4)=1/4=5,则x5为换入变量，=则x4为换出变量。以2 为主元数进行旋转运算，得 4)4/1/(3,2/8,

45、min()0|(min55iiiiaab表 16cjcB xBb2x13x20 x30 x40 x52 x10 x53 x24421000010-21/21/41/2-1/8010-z-1400-1.5-1/80从表16看出检验数都小于或等于零，于是对应的基可行解X=(4,2,0,0,4)为最优解,最优值z=14.非基变量的检验数都是正，因此有唯一最优解。5 单纯形法的进一步讨论 5.1 人工变量法 5.1 人工变量法设线性规划问题的约束条件是分别给每一个约束方程加入人工变量xn+1,xn+2,xn+m,得到njjjbxP1a11x1+a12x2+a1nxn+xn+1 =b1 a21x1+a2

46、2x2+a2nxn +xn+2 =b2 am1x1+am2x2+amnxn +xn+m=bmx1,x2,xn0,xn+1,xn+2,xn+m0以xn+1,xn+2,xn+m为基变量，则可得到mm一个单位矩阵，l令非基变量x1,x2,xn为零，得到一个初始基可行解X(0)=(0,0,0,b1,b2,bm)T若经过基变换后，得到的最终单纯形表中当所有的cjzj0，基变量中不包含人工变量，就得到原问题的一个基可行解，否则，原问题无可行解。1、大M法 在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数的取值无影响，为此可取人工变量在目标函数中的系数为M(M为非常大的正数)，这样目标函

47、数要实现最大化，人工变量只能取零，因此必须把人工变量从基变量中换出，否则目标函数就不可能实现最大化。例7 用大M法求解线性规划问题 min z=3x1+x2+x3x12x2+x3114x1+x2+2x332x1 +x3=1x1,x2,x30解在上述问题的约束条件中加入松弛变量，剩余变量和人工变量，得到min z=3x1+x2+x3+0 x4+0 x5+Mx6+Mx7x12x2+x3+x4=114x1+x2+2x3x5+x6=32x1 +x3+x7=1x1,x2,x3,x4,x5,x6,x70用单纯形表进行计算，得到最优解是x1=4,x2=1,x3=9,x4=x5=x6=x7=0,最优值z=2

48、cjcB xBb-3X11x21x30 x40 x5Mx6Mx70 x4M x6Mx711311-4-2-2101211000-10010001113/21cj-zj-3+6M1-M1-3M 0M000 x4M x61x3101130-2-2100011000-10010-1-211cj-zj-11-M00M03M-10 x41 x21x3121130-2010001100-2-10210-5-214cj-zj-10001M-1M+1-3 x11 x21x34191000100011/302/3-2/3-1-4/32/314/3-5/3-2-7/32000 1/31/3M-1/3M-2/32、

49、两阶段法由于大M法在使用电子计算机求解时，只能用很大的数代替M，这就可能造成计算上的出错。故下面介绍两阶段法。第一阶段不考虑原问题是否存在基可行解，给原线性规划问题加上人工变量，构造仅含人工变量的目标函数和要求实现最小化。即求解如下问题min=0 x1+0 xn+xn+1+xn+ma11x1+a12x2+a1nxn+xn+1 =b1a21x1+a22x2+a2nxn +xn+2 =b2am1x1+am2x2+amnxn +xn+m=bmx1,x2,xn0,xn+1,xn+2,xn+m0若得到=0，这说明原问题存在基可行解，可以进行第二阶段的计算否则，原问题无可行解。第二阶段将第一阶段得到的最优单纯形表，除去人工变量，将原目标函数的系数换掉该表的目标函数的系数行，作为第二阶段计算的初始表。例9 用两阶段法求解下面的线性规划问题 min z=3x1+x2+x3x12x2+x3114x1+x2+2x332x1 +x3=1 x1,x2,x30 解将上面的问题的约束方程加上人工变量得到第一阶段的问题min z=x6+x7x12x2+x3+x4=114x1+x2+2x3x5+x6=32x1 +x3+x7=1x1,x2,x3,x4,x5,x6,x70第一阶段