1、第五章 线性规划线性规划模型线性规划的图解单纯形法原理单纯形法单纯形表单纯形的理论分析人工变量法15.1线性规划的数学模型一、问题的提出例1：生产计划问题：问：甲乙各生产多少，使企业利润最大？ 品ABC利(元/公斤)甲35970乙95330限制工5404507202解:设产品甲、乙各生产x1，x2公斤设总利润为Z，则： 品ABC利(元/公斤)甲35970乙95330限制工540450720资源约束变量非负约束3二、线性规划模型的一般特点 Max(Min)z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn(=或)b1a21x1+a22x2+a2nxn(=或)b2am1x1+am2
2、x2+amnxn(=或)bmxj(j=1,n)()0，或者没有限制s.t.cj为价值系数反映了客观限制条件。明确的目标要求，极大或极小行动方案线性规划模型的一般形式：1、决策变量：向量(x1 xn)T2、目标函数：Z=(x1 xn)线性式，3、约束条件：线性等式或不等式变量约束约束方程4源品煤（吨）金属材料（公斤）力（千瓦）品利（元/吨）A680506000B850105000源供量54040002000表2：例2：资源合理利用问题：某厂生产A、B两种产品，都需用煤、金属材料、电力等资源，各产品对三种资源的消耗及可供利用的资源如表2示：问：应如何安排生产，使企业获利最大？三、常用的线性规划模型
3、 5解：设产品A、B产量分别为变量x1，x2（吨），则：源品煤（吨）金属材料（公斤）力（千瓦）品利（元/吨）A680506000B850105000源供量540400020006例3、合理下料问题： 有一批长度为180厘米的钢管，需截成70、52和35厘米3种管料。它们的需求量分别不少于100、150和100根。问如何下料才能使钢管的消耗量为最少？先找出各种可能的下料方式：（再在各种可能的下料方案中去选择）设在180厘米长的钢管上能下出u个70厘米管料，v个52厘米管料，w个35厘米，则满足约束条件：70u+52v+35w180，其中，u，v，w只能是正整数。从最大尺寸管料下起：7IIIIII
4、IVVVIVIIVIII702111000052021032103510130235合175174157175156174157175余料56235246235各种可能的下料方案：82x1+x2+x3+x41002x2+x3+3x5+2x6+x7150 x1+x3+3x4+x6+3x7+5x8100 xi0(i=1,8)，且为整数minZ=5x1+6x223x3+5x4+24x5+6x6+23x7+5x8解：设按第j种方案下料的原材料为xj根 9例4：运输问题问：如何安排运输，使运输费用最小？ 冶厂山B1B2B3B4量A11.520.33100A270.81.4280A31.20.322.55
5、0需求量5070803023010解：设xij为第i个矿山运到第j个冶炼厂的矿石量 MinZ=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31+0.3x32+2x33+2.5x34(万元)x11+x12+x13+x14=100 x21+x22+x23+x24=80 x31+x32+x33+x34=50 x11+x21+x31=50 x12+x22+x32=70 x13+x23+x33=80 x14+x24+x34=30 xij0(i=1,2,3。j=1,2,3,4)第i个矿山的产量第j个冶炼厂的需求量11方案序号技改方案内容决策量投（
6、万元）年收益(万元)第一年第二年1更新旧装置，提高油能力500桶/天x12001001002建造新装置，提高油能力1000桶/天x23001502003往新厂建油管，提高油能力100桶/天x315050504往老厂建油管，提高油能力50桶/天x410070305增加槽运能力，能提高出油20桶/天x5504020例5：投资方案选择问题（01规划）12又要求：方案1和2只能选择其中一种，不能兼而实现，并且，选择方案2，则方案3必须与2同时选择，或者都不选择。现该公司可供支配的资金总额为：第一年有650万元，第二年仅有460万元。要求技改后，至少增加出油能力500桶/天，但又不得超过1100桶/天，
7、确定该公司总经济效益最大的投资方案。解：1）确定决策变量：方案的选择只有两种状态，选或不选，设xj（j=1,5）为第j方案的取舍，有：2）目标函数：maxZ=100 x1+200 x2+50 x3+30 x4+20 x513200 x1+300 x2+150 x3+100 x4+50 x5650（万元）200 x1+150 x2+50 x3+70 x4+40 x5460500 x1+1000 x2+100 x3+50 x4+20 x5500500 x1+1000 x2+100 x3+50 x4+20 x51100 x1+x21-x2+x3=0 xj=1或0(j=1,5)3)约束条件：（投资总额
8、约束（第一、二年），生产能力增加约束，方案制约约束，变量的取舍限制。14例6：人员分派问题数模（01规划）每项工作只能由一个人承担，每人做每项工作的工作效率如上表所示，现在怎样安排工作使总的效率最大。 工作人ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0.70.70.50.415解：设xij为第i个人做第j项工作，（xij=1或0）MaxZ0.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x24+0.8x31+x32+0.7x33+0.3x34+0.7x41+0.7x42+0.5x43+0.4x4
9、4x11+x12+x13+x14=1x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1xij=1或0(i=1,.,4。j=1,4）每一项工作都有人做每个人只做一项工作16v线性规划建立模型步骤：确定一组决策变量确定目标函数确定对决策变量的约束条件线性规划建模小结 v线性规划的共同点：要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件17作业：现有一家公司准备制定一个广
10、告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：目广播一般黄金每个广告元的用(元)每个广告元所接触的客数(万人)每个广告元所接触的女客数(万人)40004030700090403000502015002010 该企业计划用于此项广告宣传的经费预算是80万元，此外要求：1.至少有200万人次妇女接触广告宣传；2.电视广告费用不得超过50万元,3.电视广告至少占用三个单元一般时间和两个单元黄金时间,4.广播和报纸广告单元均不少于5个单元而不超过10个单元。 试为该企业制定广告计划，使得广告所接触的未来顾客总
11、数尽可能多，建立线性规划数学模型。185.2线性规划的图解法一、图解法求最优解的步骤思路：在直角坐标系中，描绘出约束条件和变量限制的公共区域，然后通过观察确定符合目标要求的变量的取值。求解例1中的生产计划问题： 对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。19Ox1x280603070901、绘出约束方程的图形2、确定可行解域3、绘出目标函数图形4、确定最优解及目标函数值可行解域目标函数变形得：目标函数等值线最优解Q2(75,15)Q1Q3Q4Q5Q6Q7Q820几个概念：v可行解：满足线性规划所有约束条件（含约束方程与变量约束）的点。v可行解域：
12、所在可行解的集合。v最优解：使目标函数得到极值的可行解。最优解包括：唯一最优解和无穷多最优解。v等值线：具有相同目标函数值的直线。v法向量(梯度):由目标函数系数组成的与等值线垂直的向量。21二、二维线性规划问题解的形式1、唯一最优解2、无穷多个最优解66843x2可行解域目标函数的等值线C(1,2)Q2(4,2)Q3(2,3)x1MaxZ=x1+2x2x1+x26x1+2x28x23xi0(i=1,2)223、有可行解但无最优解maxZ=x1+x2-2x1+x24x1-x22x1,x20 x2x1-24-22可行解域(1,1)234、无可行解MinZx1+2x2s.t.x1+x212x1+x
13、24x1,x20 x2x11142(1,2)可行域为空集，无可行解!24线性规划的可行解域为凸多边形（凸集）。可行解域凸多边形有若干个顶点，顶点的个数是有限的。三、线性规划的几何意义线性规划问题若存在最优解，则最优解必可在其可行域的某一顶点上得到。Ox1x2Q2(75,15)60最优解Q1Q3Q4Q5Q6Q7Q825四、单纯形法原理Ox1x2Q2(75,15)60最优解Q1Q3Q4Q5Q6Q7Q8找可行解域顶点的计算方法，但不是计算所有的顶点，而是从凸集的一个顶点出发，沿着凸集的边缘逐个验算所遇到的顶点，直到找到目标函数为最优的顶点为止。如从OQ1Q2或从OQ4Q3Q2。261.3单纯形法原理
14、5.3线性规划标准型和规范型一、线性规划的标准型 约束方程均为等式方程。右边常数bi为正数。所有变量均为非负变量。目标函数求max1、一般形式：27或写成累加和形式：标准型的一般形式28或写成矩阵形式：其中：292、化线性规划问题为标准型约束方程为“号，在方程式的左端“”一个变量（变量0，称为松驰变量），原不等式化为等式约束。约束方程为“”号在方程式的左端“”一个变量（变量0，称为剩余变量），原不等式化为等式约束。 (1) 约束条件为等式30（2）变量非负约束若xk为无约束变量（即可0，也可0），引进两个变量xk,xk”（均0），令xk=xkxk”。在规划模型中去掉xk这个变量。（3）约束方程
15、右边常数非负约束在方程两边同时乘以（-1）使得约束方程右边常数变为非负 31标准型为：例1：把下面的线性规划模型化为标准型：32得到 的准型：(1)用x4x5替换x3，其中x4，x50(2)在第一个约束不等式号左端加上松驰变量x6(3)在第二个约束不等式左边减去松驰变量x7(4)令DZ,把求minZ化成maxD例2：把下面的线性规划模型化为标准型：33二、线性规划的规范型要用单纯形法求解线性规划数学模型，还需要把数学模型化成规范型。1基、基变量与非基变量基：设A是约束方程组的mn维系数矩阵，B是矩阵A中m阶方阵（行列式的值不为0），则称B是线性规划问题的一个基。基变量与非基变量：与基B对应的变
16、量为基变量。其余变量为非基变量。设线性规划模型的标准型：34请列举出其中的三个基及对应的基变量与非基变量。例1：解：从约束系数矩阵可看出，该模型的基不超过个。对应的基变量为x3,x4,x5,非基变量为x1,x2。35对应的基变量为x1,x3,x4，非基变量为x2,x5。对应的基变量为x1,x2,x3，非基变量为x4,x5。362基本解和基本可行解基本解：对某一确定的基，令非基变量等于0，可求出m个约束方程的基变量的值，则这组解称为基本解。基本可行解：若基本解还满足决策变量非负要求，则这组基本解称为基本可行解（也称基可行解）。37基B1来，令非基量，可以得到一个基本解 因，故是基可行解。 基B2
17、来，令非基量，可以得到一个基本解因，故也是基可行解。38基B3来，令非基量，可以得到一个基本解因，故不是基可行解。基B4来，令非基量,可得基本解因，故也不是基可行解。393基可行解与可行解域顶点的关系Ox1x2Q2(75,15)60最优解Q1Q3Q4Q5Q6Q7Q8X(1)对应原点O,X(2)对应顶点Q1,X(3)对应Q7.X(4)对应?40Ox1x2806090最优解Q2(75,15)Q1Q3Q4Q5Q6Q7Q8非基量基量基本解X(x1,x2x3,x4,x5)T 点x1,x2x3,x4,x5(0,0,540,450,720)TOx2,x5x1,x3,x4(80,0,300,50,0)TQ1x
18、2,x4x1,x3,x5(90,0,270,0,-90)TQ5x4,x5x1,x2,x3(75,15,180,0,0)TQ241定理1：线性规划的基本可行解对应于可行解域的顶 点。从定理1和单纯形的几何意义知，用单纯形法寻求最优解，就可从基本可行解（顶点）出发，在基本可行解（顶点）之间变换，如果L.P.有最优解，则最优解一定可在某一基本可行解（顶点）上得到。这个方法可用来求有任意多个变量的线性规划模型！Ox1x2Q2(75,15)60最优解Q1Q3Q4Q5Q6Q7Q842已是标准型；得初始基本可行解：X(1）=(0,0,540,450,720) T,Z=0。4、线性规划的规范型例1：特点（1）
19、基变量的值刚好是约束方程右边的常数；（2）目标函数Z的值就是目标函数表达式中的常数。含单位基；目标函数用非基变量表示。规范型条件：43若取基变量x3,x4,x1,则基解及目标函数值？可把模型化成以基变量系数矩阵为单位阵的规范型：得到基本可行解：， 44引例1：求解下列线性规划模型的最优解解：1、确定初始基可行解取B1（P3P4P5）I，令非基变量x1,x2=0，得X(1)（0,0,540,450,720）T，Z(1)0；（解的含义？）从规范型出发5.4单纯形法步骤452、判定解是否最优目标函数MaxZ0+70 x1+30 x2检验数：用非基变量表达的目标函数中变量前的系数Rj（判别数或检验数）
20、。当x1从0或x2从0，Z从0，X(1)不是最优解3、由一个基可行解另一个基可行解。(1)确定入基变量可选Rj0的任一变量入基。（意义？）一般地，选择maxRj的变量入基，选x1从0，保持x2=0(2)确定出基变量46问题：确定入基变量x1增加的上界：从约束方程组怎样求解？在中，继续令x2为非基变量，即x2 0，求出当前每个基变量出基能使x1增大的上界值。即：x3=5403x10 x1180=540/3x4=4505x10 x190=450/5x5=7209x10 x180=720/947min180,90,80=min540/3,450/5,720/9=80,x5出基(变为0)，即x1的取值
21、受第三种资源的约束。规则：入基变量满足约束条件下取最大值。（大中取小）x3=5403x10 x1180 x4=4505x10 x190 x5=7209x10 x180新的基变量为x3,x4,x1，怎样求出新的基可行解？把模型变成以基变量的系数矩阵为单位阵的规范型。 (3)求出新的基可行解48 以基变量x3,x4,x5的系数矩阵为单位阵的规范型: （1）从出基变量x5所在的方程开始：方程两边同时除以入基变量x1的系数9，得：（2）方程中消去x1（入基变量）：方程两边同时乘以某个数，加到方程上。（3）目标函数中消去x1：从方程中解出x1的值代入目标函数中：新的基变量为x3,x4,x1本质：就是线性
22、代数中的高斯消去法方程组同解变形.49通过以上方程的变换，原线性规划模型等价于以下模型（得到当前基表示的规范型）：X(2)（80,0,300,50,0）T，Z(2)5600；对应图形上的Q1点。1、确定出新的基可行解502、判定解是否最优3、由一个基可行解另一个基可行解。(1)确定入基变量选择x2入基，即x2从0，x5仍为0从约束方程组求解x2的最大取值，从而确定出基变量。同理：在中令x5=0，求出当前解下x2取值的上界。当x2从0，Z从5600，X(2)不是最优解.目标函数：，R2=20/3,R5=-70/951=min37.5，15，24015，x4出基(2)确定新基可行解：x3=3008
23、x2 x237.5 x4=5010 x2/3 x215x1=80 x2/3 x2240把模型变成以基变量x3,x2,x1的系数矩阵为单位阵的规范型。 新的基变量x3,x2,x152怎样把模型变成以基变量x3,x2,x1的系数矩阵为单位阵的规范型？ (1)从出基变量x4所在的方程开始：使入基变量x2的系数变成1。(2)用消元法消去方程中的x2。53X(3)（75,15,180,0,0）T，Z(3)5700；由方程组变形得：542、判定解是否最优目标函数X(3)（75，15，180，0，0）T，Z(3)5700；非基变量的检验系数均为负数，故不能入基，否则使目标值劣化。当前解为最优解。最优解判断标
24、准：（1） 若全部检验数Rj 0，当前基本可行解为最优解。（2） 若存在Rj 0，则当前解非最优，解可改进，寻求 更好的解。551、确定初始基可行解。本题确定初始基为单位阵I，令单位阵对应的变量为基变量，可得到一个基本可行解。小结：单纯形法求解线性规划的过程规范型：AXbX0，b0A中含有一单位阵。2、最优化检验：用当前可行基的非基变量的检验数确定。3、从一个基本可行解到另一个基本可行解入基变量：由检验数确定。出基变量：由规则确定。56用单纯形法从另一条路径寻优？57cj c1 c2 cnCBXB x1 x2 xnxi1xi2ximZ R1 R2 RnZ05.5单纯形表目标函数行：常数Z0在右
25、边。581、由规范型列出初始单纯形表：X(1)（0,0,540,450,720）TZ(1)0主元cj7030000CBXBx1x2x3x4x50 x3391005401800 x455010450900 x59300172080-Z70300000592、变换到下一单纯表（变成以新基为单位阵的规范型）思考：单纯形表有什么特点？（1）基变量对应的约束方程中系数矩阵为单位矩阵。（2）目标函数基变量的检验数为0。（3）基可行解(？)不同，反映在原表中就是对应的基不同。 新的基变量：x3,x4,x1cj7030000CBXBx1x2x3x4x50 x30810-1/330037.50 x4010/30
26、1-5/9501570 x111/3001/980240-Z020/300-70/9-5600主元60表一表二00003070-Z8072010039x509045001055x4018054000193x30 x5x4x3x2x1XBCB0003070Cj9-5600-70/90020/30-Z240801/9001/31x11550-5/91010/30 x4037.5300-1/30180 x3070?613、重复以上过程直到得最优解：思考：在单纯形表中，怎样判断LP问题已取得最优解？最优解判断标准：（1） 若全部检验数Rj 0，当前基本可行解为最优解。（2） 若存在Rj 0，则当前解非
27、最优，解可改进，寻求更好的解。62cj7030000CBXBx1x2x3x4x5b0X3391005401800X455010450900 x59300172080-Z703000000 x30810-1/330037.50 x4010/301-5/9501570 x111/3001/980240-Z020/300-70/9-56000 x3001-12/5118030 x20103/10-1/61570 x1100-1/101/675-Z000-2-20/3-5700X*=(75,15,180,0,0)T,Z=570063例1：求解下列线性规划模型：解：化线性规划模型为规范型，并列出初始单纯
28、形表：按单纯法迭代，计算如下表，得最优解为:X=(1500,0,0,3500,0)T,Z=600064-6000-20-3-10-Z15001/2021/21x13500-3/21-2-1/20 x4-3750-5/400-1/43/2-Z15007501/4011/4x350005000-11001x4000514-Z750300010412x52000800001413x4bx5x4x3x2x1XBCB00514Cj41/265例2：用单纯形法求解下列线性规划数学模型选x1、x3、x6为基变量 目标函数用非基变量表示：由 约束方程(1)(2)(3)解出x3 = 6 - x2 + x4 -
29、2x5 x1 = 5 - 2x2 + 2x4代入目标函数得：Min Z = 11 - 4x2 + 3x4 - 5x5 把LP化成求极大的规范型：66XBx1x2x3x4x5x6bx1120-2005x3011-12063x602013188/3-D040-3501167X(3)=(0，5/2，3/2，0，1，0)TD(3)=4，Z4-4-5/30-400-1/3-D11/31100-1/3x53/2-2/30-2101/6x35/200-1011/2x2-7/3-5/30-14/302/30-D48/31/311/302/30 x52/3-2/30-5/31-1/30 x35/2500-202
30、1x11105-3040-D8/38131020 x63602-1110 x3500-2021x1bx6x5x4x3x2x1XB68假设目标函数求极大MAX1、从规范型出发，得出一个初始基可行解。按要求填入表中。2、最优化检验：若还存在Rj0，则当前解不是最优解。3、解的改进：由检验数确定入基变量xp。(一般正系数大的变量先入基)确定出基变量:确定L为出基行，则xL为换出变量。得到一个新的可行基。单纯形算法步骤4、用初等行变换方法把主元（aLp）变为1，把入基列（含其检验数）中除主元的其它元素消为零。转2.69讨论：单纯形表进行求解的特殊情况 （1）若最大检验数有两个或两个以上并且相等，应如何
31、确定入基变量，理论上可任选一个非基变量入基，但在实际应用中，可采用以下法则：XBx1x2x3x4x5b12x33910054018060 x4550104509090 x59300172080240-Z70700000依次选择X1和X2入基，分别计算出两组比值1和2，每组比值中分别选择最小值得80和60，两个最小值中选择最大值80，因此确定X1入基，此时目标函数值改变得最快(?)。70（2）原问题有解但无最优解(无界)的判断：某个Rj0,但aij0(i=1,2,m)。例4：求解线性规划问题：XBx1x2x3x4bx33-2101x42-1014Z1100标准化71一、最优决策变量的解最优解是单
32、纯形法的基本目标信息，在建模参数可靠的基础上，它提供最优决策方案 。如例2中：最优解：X(3)（75，15，180，0，0）T，Z(3)5700；X4=0，X5=0，表明资源B、C没有剩余，为企业的关键资源；X3=180，资源A还剩180个单位。应设法提高关键资源的获得量。二、松弛变量的解单纯形表的每一个基本可行解，还包含有松弛变量的解，在最优决策条件下，松弛变量的解提供资源的剩余量。 5.6单纯形的经济意义72三、检验数Rj(产品的相关价值系数)经济意义基本解X(2)（80，0，300，50，0）TZ(2)5600；基本解：X(1)（0，0，540，450，720）T，Z(1)0；MaxZ7
33、0 x1+30 x2当前方案下，非基变量Xj增加1个单位，使目标函数增大的量。R2=20/3，而当前表中，入基变量x2可增加值为15，故当前表中x2入基，利润可增加100。73从例1的第二个单纯形表来看，生产80个单位的x1，C资源全部用完，A、B资源分别剩余300和50。生产1个单位的x2，分别需要A、B、C各9,5，3单位，由于资源总量的约束，只能少生产1/3单位的x1，所以少生产1/3单位的x1要损失的利润为：Z20803/10+701/3=70/3，故R23070/320/3。 -5600-70/90020/30-Z240801/9001/31x1701550-5/91010/30 x
34、4037.5300-1/30180 x30 x5x4x3x2x1XBCB0003070Cj74C230，孤立地讲，生产1个单位的乙产品对市场的利润还是30，但在企业的资源约束下，在当前的生产方案下，要使x2=1，必然以少生产其它产品为代价，故在当前方案下增加1个单位的乙产品只能净得利润20/3。为了生产一单位的某产品将所需资源从原来的用途中抽出来而牺牲的利润为此种产品在此生产方案下的机会成本。（Zj为生产一单位xj产品所付出的成本。 cjzj表示生产1单位j产品对方案收益的增量。检验数Rj综合考虑了市场信息和规划方案改变对利润的影响。一旦作出了生产安排，单位产品的利润增值（Rj）就可能变化，
35、Rj能起到判别计划能否进一步改进的作用。75四、资源的影子（潜在）价格1、定义：最优规划条件下，单位资源能够带来的目标函数增量。是反映资源最优利用的一种虚拟价格，也叫资源边际利润。 2、影子价格的计算最优表中表示资源的松弛变量检验数的相反数。-57000-20/3-200-Z751/6-1/10001x115-1/63/10010 x21801-12/5100 x3x5x4x3x2x1XBCB00043Cj76根据影子价格的定义：资源A的影子价格为0，资源B的影子价格为2，资源C的影子价格为20/3。含义：在最优方案下，资源B增加1个单位，能使利润增加2个单位。资源C增加1个单位，能使利润增加
36、20/3个单位。资源A增加1个单位，不会使利润增加(A本身有剩余)。资源影子价格的高低表明资源的重要性的大小，影子价格为0的资源是非关键资源，影子价格大于0的资源是关键资源。X(3)（75，15，180，0，0）T77 在企业内部：指出挖潜方向，影子价格高的资源潜力大，影子价格低的资源潜力小。问题：资源的影子价格是否是一定的？注意：随着资源可用量的不断增加，其影子价格会不断下降，当影子价格降为0时，再增加该资源的可用量,利润不会增加，此时该资源已成为非关键资源。 衡量资源的使用是否合理。同一种资源在不同的地方和不同的时期，其影子价格不相同，影子价格高的说明使用合理，所以应建立动态影子价格体系，
37、做到物尽其用。 对企业外部来讲，影子价格是决定资源在市场上出售的标准：当资源的市场价不低于其影子价格时，企业管理人员可以考虑出售，得到的利润与自己组织生产所得利润是一样的。3、影子价格的应用78一、线性规划标准型的表达形式约束方程均为等式方程。所有变量均为非负变量。右边常数bi为正数。MaxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmxj0(j=1,2,n)1、一般形式：5.7 单纯形法理论分析792、求和表达式803、矩阵表达式X1X=X2XnC=(c1c2cn) A=(P1 P2 P
38、n)a11a12a1n其中 A= a21a22a2nam1am2amnmaxZ=CXAX=bX0 81一、单纯形表（规范型）的一般表示1、单纯形表的数学推导不失一般性，设某一基变量为XB=(x1,x2,xm)T，则对应此基下的约束方程组可表达为：LP的数学模型为：82基变量的求和表达式：把目标函数也表达成基变量和非基变量两部分的求和表达式：把（1）式代入（2）式经整理得： 83Zj基变量的价值系数当前单纯形表中该变量前的系数检验数RjCjZj2、当前解的改进和最优解的确定设检验数为：Rj0解能改进的条件。Rj0最优解的确定条件。当存在若干个Rj0，一般选最大的数实际上：可选使目标函数值Z变化最
39、大的非基变量入基：ZZ0Rj843、出基变量、主元素xp入基为正数，其它非基变量保持为零，入基量的上界 ：aip0，因xp非的有限数，要求aip0由规则为：则xl行为换出行，主元为：854、旋转运算要得到下一单纯形表，即使入基列向量xp成为单位向量，其旋转运算方法：第l行（出基行）元素除以主元，使主元变为1。入基列xp中除主元外的其它元素（包括检验数行）消为零。86例1：用公式验算引例第二个单纯形表（见表1）中目标函数的值与检验数。CBXBx1x2x3x4x5b0 x30810-1/330037.50 x4010/301-5/9501570 x111/3001/980240-Z020/300-
40、70/9-5600解：计算检验数：其中ci为基变量的价值系数。R230(08+010/3+701/3)=20/3R50(0(-1/3)+0(-5/9)+701/9)70/9计算目标函数值： ZCixi=7080560087maxZ=CXAX=b（1）X0对于线性规划模型的标准型：设某个基可行解对应的基为B，LP模型又可表示为：ZCBXBCNXNBXBNXNb (2)对约束方程，两边同乘B1得：怎样得出该基对应下的单纯形表呢？二、单纯形表（规范型）的矩阵表示IXB+B-1NXN=B-1b，解出：XB=B-1bB-1NXN代入目标函数，消去基变量，得：Z0XB（CNCBB1N）XNCBB1b单纯形
41、表的矩阵表达式：88问题：与原模型相比，1、基变量的系数向量如何变化？非基变量的呢？2、与原模型中的价值系数比较，基变量的检验数如何变化？非基变量的呢？3、与原模型相比，约束方程右边的常数如何变化？4、在当前基可行解下，目标函数值与B、CB及b的关系？89例1：用单纯形表的矩阵表达式计算引例中以x3,x4,x1为基变量的单纯形表。(1)基变量的值：(2)非基变量的系数：90(3)非基变量的检验数：XBx1x2x3x4x5bx30810-1/330037.5x4010/301-5/95015x111/3001/980240-Z020/300-70/9-5600用单纯形表的计算公式算出来的结果与用
42、表格迭代的结果一致！ 91例2：引例中，若知道最优基（以x3,x4,x1为基变量），最优基对应的单纯形表是否可一步求出？如何求？XBx1x2x3x4x5bx3001-12/51180 x20103/10-1/615x1100-1/101/675-Z000-2-20/3-570092(1)、定初始基，初始基本可行解(2)、对应于非基变量检验数Rj全0。若是，停，得到最优解；若否，转(3)。(3)、若有Rp0，全Pp0，停，（Pp为入基列的系数向量）没有有限最优解；否则转(4)(4)、maxRj=RpXp入基变量XL为出基变量，aLp为主元。(5)、以为中心，换基迭代，得出新的基可行解。单纯形法基
43、本步骤 (max型)出基变量确定：思考：求MIN型？93XBx1x2x3x4x5x6bx1120-2005x3011-12063x602013188/3-D040-35011-Z0-403-50-1194练习：下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为：maxZ=5x1+3x2,约束形式为，x3,x4为松弛变量，表中解代入目标函数后得Z10。（1）求ag的值；（2）表中给出的解是否为最优解。CBXBx1x2x3x4b0 x3c011/525x1de01aZb-1fgZ0答案：a=2,b=0,c=0,d=1,e=4/5,f=0,g=-5955.8两阶段法与大M法下面的线性规划
44、模型，怎样得到一个初始基本可行解？ 一般说来，对于不是规范型的标准型，我们看不出哪组变量为基变量，可得基可行解。对于不是规范型的标准型，用单纯形法求解的办法就是添加人工变量，使标准型人为地变成规范型的形式。标准化96人工变量法思想：v目的：使A中含单位基，得到模型（2）的一个基可行解，但此基可行解不是（1）的可行解。v人工变量是人为添加到原约束方程的虚拟变量，若人工变量不等于0，则不是原模型（1）的解。v 单纯形法是确定入基变量和出基变量的过程，(约束方程的等价变换过程)，只要人工变量全部出基，基变量中不含有人工变量，这时模型（2）的基可行解也是（1）的可行解。如模型(2)的解：97一、两阶段
45、法第一阶段：不考虑原问题是否存在基可行解；给原LP模型加入人工变量，并构造仅含有人工变量的目标函数，实现极小化。如xn+1,xn+2,xn+m为加入的人工变量，则新的目标函数为：然后用单纯形法求解上述模型，若得到W=0，这说明原问题存在基可行解，可以进入第二阶段计算。否则，原问题无可行解，应停止计算。第二阶段也分2种情形1)无人工变量作为基变量，直接进入第二阶段；2)有人工变量为0作为基变量，该行约束冗余，可以丢掉，在进入第二阶段.minW=xn+1xn+2xn+m98100000-Z21-1/2-11/211/20 x30631/20-1/201/21x100010-1-2-Z440-101
46、11x303610-1012x61bx6x5x4x3x2x1XB100000cj21/2第一阶段，构造新的目标函数：minw=x69936-6-2-100-Z2-21210 x2-821-1-101x1-10-7-3/201/20-Z21-11/211/20 x3-7630-1/201/21x1-10bx5x4x3x2x1XB00-7-8-10cj1/2第二阶段：换回原来的目标函数maxz=10 x18x27x3cB教材例100把标准型化为规范型，如右边示：x6,x7为人工变量。解：第一阶段：希望人工变量等于零，故构造仅含人工变量的目标函数，并要求实现最小化。用单纯形法求解模型(2)，若人工变
47、量x6，x7能全部出基，变成非基变量，则W0，同时原问题也存在一个可行基，进入第二阶段的运算，否则原问题无可行解。10101100000-W3/2-1/2-1/211/21/200 x503/21/21/20-1/2-1/210 x201/2-1/21/201/2-1/201x10-1200-110-2-W22-1011001x50-1100-101-1x201/21-1101-102x61-300011-20-W330010010 x5011100-101-1x71220100-111x61bx7x6x5x4x3x2x1XBCB1100000cj102第二阶段：将第一阶段计算得到的最终表，去
48、掉人工变量，将目标函数换回原问题的目标函数，并用非基变量表示目标函数。（此时原问题已变换成规范型）1035/20-3/2-1/200-Z33/211/21/200 x50-3/20-1/2-1/210 x2-211/201/2-1/201x11bx5x4x3x2x1XBCB0 00-21cj 400-203-Z111010-1x50-200-111x2-2-101-102x40620001-Z11010-1x30310010 x2-2211001x40104例3.用两阶段单纯形法求解线性规划解：标准形式为105在第一、三约束方程中加入人工变量x6、x7后，构造第一阶段问题用单纯形法求解，得到第
49、一阶段问题的计算表格106Cj0000011bCBXBx1x2x3x4x5x6x7101x6x5x74123121211000101000014101Rj2121000100 x6x5x3632532001100010100381Rj650100000 x2x5x36/53/52/51000011/53/52/50103/531/511/5Rj00000107最解最优值w=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解,即第二阶段问题为108用单纯形法计算得到下表Cj32100bCBXBx1x2x3x4x5201x2x5x36/53/52/51
50、000011/53/52/50103/531/511/5Rj50000231x2x1x301010000111025/32/31331/319/3Rj000525/3检验数j0,j=1,2,5，最优解与最优值109注：在第二阶段计算时，初始表中的检验数不能引用第一阶段最优表的检验数，必须换成原问题的检验数，用代入法或消元法计算。另外，即使第一阶段最优值w=0，只能说明原问题有可行解，第二阶段问题不一定有最优解，即原问题可能无界。例4：用两阶段法求解下列线性规划。110加入松驰变量x3、x4化为标准型第一段111用单纯形法计算如表Cj00001bCBXBx1x2x3x4x501x3x531121
