《(精品)运筹学第一章.ppt》由会员分享，可在线阅读，更多相关《(精品)运筹学第一章.ppt（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章 线性规划与单纯形法重点与难点：1、线性规划的概念和模型，线性规划问题的标准型，线性规划问题的标准化；2、线性规划问题解的概念，图解法(解的几何表示)，基本可行解的几何意义，线性规划求解思路(单纯形法思想)；3、单纯形法的一般描述，表格单纯形法，一般线性规划问题的处理，单纯形迭代过程中的注意事项；4、线性规划建模，决策变量，约束不等式、等式，目标函数，变量的非负限制。OR11第一章 线性规划与单纯形法w1.1 LP(linear programming)的基本概念 LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。LP有一组有待决策的变量，（决策变量）一个线
2、性的目标函数，一组线性的约束条件。OR121.1.1 LP的数学模型 例题1：生产计划问题w某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120OR13例题1建模w步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20综上所述，该问
3、题的数学模型表示为：OR14例题2:营养配餐问题w有A、B两种食品，含有每天必须得营养成分C、D，每天至少需要营养成分C和D分别为2和3个单位。食品A、B的成分和单价如下表，试做花钱最少的食谱，并求其费用。ABC12D31单价（单位/元）0.90.8OR15例题2建模w1、确定决策变量：设A、B两种食品每天的购买量分别为x1,x2单位。w2、确定目标函数：minW=0.9x1+0.8x2w3、确定约束条件：x1+2x2 2 3x1+x2 3 x1 0,x2 0综上所述，该问题的数学模型表示为：OR16例题3：人员安排问题w医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计
4、：序号时段最少人数安排人数1061060X12101470X23141860X34182250X45220220X56020630 x6请问该请问该医院至医院至少需要少需要多少名多少名护士？护士？OR17例题3建模w目标函数：min Z=x1+x2+x3+x4+x5+x6w约束条件：x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30非负性约束：xj 0,j=1,2,6OR18例题4：运输问题运输问题 三个加工棉花的加工厂，并且有三个仓库供应棉花，各供应点到各工厂的单位运费以及各点的供应量与需求量分别如下表所示：问如何运输才能使总的运费最小？问如何运输才能使
5、总的运费最小？仓库 工厂 B1B2B3库存A121350A222430A334210需求401535OR19例题4建模w设Xij为第i个仓库运到底j座工厂的运输量。w目标函数：总运费最省：minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33w约束条件：供给要求：x11+x12+x13 50需求要求：x11+x21+x31=40 x21+x22+x23 30 x12+x22+x32=15 x31+x32+x33 10 x13+x23+x33=35 非负要求：Xij 0OR110例题5：项目投资问题w某某部部门门有有一一批批资资金金用用于于甲甲、乙乙、丙
6、丙、丁丁、戊戊五五个个工工程程项项目目的的投投资资，已已知知用用于于各各个个工工程程项项目目时时所所得得之之净净收收益益(投投入资金的百分比入资金的百分比)，如下表所示。，如下表所示。由于某种原因，决定用于项目甲的投资不大于其他各项投资之和；而用于项目乙和戊的投资之和不小于项目丙的投资。试确定使该部门收益最大的投资分配方案。工程项目甲乙丙丁戊收益108659OR111例题5建模w设Xj表示用于第j个项目的投资百分比。w目标函数：maxZ=0.1x1+0.08x2+0.06x3+0.05x4+0.09x5w约束条件：w全投资要求：x1+x2+x3+x4+x5=1w对甲的要求：x x1 1-x-x
7、2 2-x-x3 3-x-x4 4-x-x5 500 w对乙、戊的要求：x x2 2-x-x3 3+x+x5 500 w非负要求：x xj j0(j=1,2,3,4,5)0(j=1,2,3,4,5)OR112例题6：连续投资问题（书P42页）w某投资者有资金10万元，考虑在今后5年内给下列4个项目进行投资，已知：w项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115。w项目B：第三年初需投资，到第五年末能回收本利125。但规定投资额不超过4万元。w项目C：第二年初需要投资，到第五年末能回收本利140，但规定最大投资额不超过3万元。w项目D：5年内每年初可购买公债，于当年末归还，并
8、加利息6。w问该投资者应如何安排他的资金，确定给这些项目每年的投资额，使到第五年末能拥有的资金本利总额为最大？OR113建模w解：记xiA,xiB,xiC,xiD(i=1,2,3,4,5)分别表示第i年年初给项目A,B,C,D的投资额，它们都是决策变量，为了便于书写数学模型，我们列表如下：OR114例题7：合理下料问题w将长8m的圆钢，截取成长2.5m的毛坯100根、长1.3m的毛坯200根，问应该怎样选择下料方式，才能既满足需要，又使总的用料最少?各种搭配方案如下：长度根数方案甲 乙 丙 丁需要根数 2.5米3 2 1 0 100 1.3米0 2 4 6 200 料头0.5 0.4 0.3
9、0.2OR115例题7建模w设Xj表示采用第j种方案下料的根数。w目标函数：minZ=x1+x2+x3+x4约束条件：3x1+2x2+x3 100 2x2+4x3+6x4 200 xj 00且为整数且为整数 (j=1,2,3,4)(j=1,2,3,4)OR116课堂练习：营养配餐问题w养海狸鼠 饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表:OR117建 模w设抓取饲料I x1kg;饲料II x2kg;饲料III x3kgw目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5w约束条件：3x2+2x2+x3+
10、6x4+18x5 700营养要求：x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1 50,x2 60,x3 50,x4 70,x5 40非负性要求：x1 0,x2 0,x3 0,x4 0,x5 0OR118 总 结w从以上7个例子可以看出，它们都属于优化问题，它们的共同特征：w1、每个问题都用一组决策变量表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的。w2、存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。w3、都有一个要求达到的目标，它可用决策变量的线性函数（称为目标
11、函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。w满足以上三个条件的数学模型称为线性规划的数学模型。OR119线性规划模型的一般模式w目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxnw约束条件：a11x1+a12x2+a13x3+a1nxn(=)b1 a21x1+a22x2+a23x3+a2nxn(=)b2 am1x1+am2x2+am3x3+amnxn(=)bm非负性约束：x1 0,x2 0,xn 0.OR120线性规划的标准型w代数式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 a
12、m1x1+am2x2+amnxn=bm xj 0 j=1,2,nOR121线性规划的标准型w和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,nj=1nnj=1OR122线性规划的标准型w向量式：maxZ=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn)X=(X1,X2,X3,Xn)Tnj=1OR123线性规划的标准型w矩阵式：maxZ=CX AX=b X 0 其中：b=(b1,b2,bm)T a11 a12.a1n A=a21 a22 a2n am1 am2 amnOR124标准型的特征w目标函数极大化（也有的版本
13、选择极小化）w约束条件为等式w决策变量非负OR125非标准型转化为标准型w目标函数极小化转为极大化：minZ=max(Z)，一个数的极小化等价于其相反数的极大化。w不等式约束的转化：aijxjbi 加入松弛变量 aijxjbi 减去剩余变量w非正变量：即xk 0 则令xk=xk 自由变量：即xk无约束，令xk=xkx”kOR126非标准型转化举例之一之一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2+X4=200 3X1+10X2 300 3X1+10X2+X5=300 X10 X20
14、Xj0 j=1,2,5OR127非标准型转化举例之二之二minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3)x1+x2+x3 9 x1+x2+x3 x”3+x4=9-x1-2x2+x3 2 x12x2+x3 x”3-x5=2 3x1+x2-3x3=5 3x1+x23(x3 x”3)=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 x40 x50 OR128课堂练习：将下列非标准型化为标准型w1、minZ=x1-2x2+3x3 2，maxZ=x1+x2ws.t.x1+x2+x3 7 s.t.x1-x2 0w x1-x2+x3 2 3x1-x2 -3
15、w -3x1+x2+2x3=-5 x1,x2 0w x1,x2 0,x3无约束。OR1291.1.2线性规划问题的图解法一、图解法的步骤1、在平面上建立直角坐标系；2、图示约束条件，找出可行域；3、图示目标函数，即为一直线；4、将目标函数直线沿其法线方向其最优化方向平移，直至与可行域第一次相切为止，这个切点就是最优点。二、几种可能结局：1、有唯一最优解，2、有无穷多个最优解，3、无界解，4、无解。OR130线性规划图解法例题（唯一最优解）maxZ=70X1+120X2s.t.9X1+4X2360 4X1+5X2 200 3X1+10X2 300 X10 X20OR131线性规划图解法例题（无穷
16、多最优解）OR132线性规划图解法例题（无界解）OR133线性规划图解法例题（无解）OR134利用图解法的常识w1、若存在唯一最优解，则此最优解在可行域的顶点上取得。w2、若存在无穷多最优解，则最优解在可行域的边界上取得。w3、若可行域为空集，则没有可行解，也就没有最优解。w4、若可行域无界，目标函数取值可以增大到无穷大，称这种情况为无界解或无最优解。w5、若有可行解，则可能有最优解，也可能无最优解（最优解无界）。OR1351.1.3解的概念w概念：1、可行解：满足所有约束条件的解。2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域
17、。3、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形。OR136凸 集线性规划的可行域是凸集。若线性规划问题存在最优解，它一定在可行域的某个顶点得到，若在两个顶点同时得到最优解，则它们连线上的任意点都是最优解，即有无穷多最优解。（P11）OR137基的概念w基基：如前所述LP标准型和式：maxZ=cjxj aijxj=bi xj 0 j=1,2,n 矩阵式：maxZ=CX AX=b X 0 约束方程的系数矩阵A的秩为m，且m0=bL/aLk 确定XL为出基变量。w4、以aLk 为枢轴元素进行迭代，回到第二步。OR155解的判别定理(P24)w1、最优解的判别定理：若X(0)
18、为对应于基B的一个基可行解，且对于一切非基变量，有 ，则 X*为最优解。称 为检验数。w2、无穷多最优解的判别定理：若X(0)为对应于基B的一个基可行解，且对于一切非基变量，有 ，又存在某个非基变量的检验数为0，则称该LP问题有无穷多最优解。OR156解的判别定理w3、无界解的判别：若X(0)为对应于基B的一个基可行解，有某个正检验数的非基变量对应的列向量其分量均为非正，则该问题便无界（无最优解）。OR1571.3单纯形法的进一步探讨w2.3.1极小化LP的解法。w2.3.2人工变量法之一：大M法。w2.3.3人工变量法之二：两阶段法。OR1581.3.1极小化LP问题的解法方法一：将最小化问
19、题化为最大化问题，再对该最大化问题进行求解。方法二：最小化问题直接求解：检验数的判别由所有j(cj-zj)0 即为最优，变为所有j 0则为最优。(选择最小的负的j 所对应的变量为进基变量。其余同最大化求解方法。)OR159极小化问题的直接解法w例：求解线性规划问题：OR160解：该规划的基变量为x1,x3,x6。直接按最小问题单纯形法的求解过程如下：cj1-110-30cBxBbx1x2x3x4x5x6100212010-2-11023001568x1x3x6110z11131-3200-403-5038/3 x1x3x511-31002-1/32/3010-2-5/31/30010-2/31
20、/352/38/35/200-2/3014/305/3x2x3x51/6-1/3100010-1-210010-2/31/35/23/2100405/34-11-3OR1611.3.2人工变量法之一：大M法w首先看下面例题：OR162大M法w对于这种无初始可行基的问题可以大M法求解。方法：化为标准型的同时，将以及的约束条件中，加入人工变量（虚拟变量），将目标函数中，虚拟变量的系数定为M。w注：当目标函数为最大化时，虚拟变量的系数为M,当目标函数为最小化时，虚拟变量的系数为+M。(目的是迫使人工变量为0）该问题的解法同LP问题的一般解法。例同上。解法见书P33。OR163解法w解:在上述问题的约
21、束条件中加入松弛变量，剩余变量，人工变量，得到：OR164用单纯形表计算：cj-31100MMx1x2x3x4x5x6x7cBXBb1-4-2-2101211000-10010001x4x6x70MM1131-3+6M1-M 1-3M0M00113/21x4x6x30M130-2-2100011000-10010-1-211011-11-M00M03M-11x1x2x3-3111000100011/302/3-2/3-1-4/32/314/3-5/3-2-7/341920001/31/3M-1/3M-2/3OR165人工变量法:两阶段法w大M法如果在计算机上运作，M就只能用很大的数来代替，这样
22、可能会出现错误。故介绍两阶段法。w方法：第一阶段：不考虑原问题是否存在基可行解；原线性规划问题加入人工变量，并构造仅含人工变量的要求最小化的目标函数。（注：不管原问题是求最大化还是求最小化，第一阶段的目标函数都为人工变量之和的最小化。）OR166例题1OR167例题2OR168第二阶段w用单纯形法求解上述模型，若得到 ，说明所有的人工变量都为0。至此，可以去掉人工变量，进入第二阶段；若得到 w 说明仍有人工变量没有降至0，表示原问题无可行解，应停止计算。w第二阶段：将第一阶段计算得到的最终表，除出人工变量。将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始解。OR169解法举例
23、：例2w解：用两阶段法求解如下：w第一阶段，用单纯形法求解下列线性规划问题：OR170计算过程如下：cj000-1-1x1x2x3x4x5312-2-311001x4x564-1-1zj-40-102-1-140-20024x1x5102/3-8/3-121/3-1/301220-1-20-8/32-4/301x1x30010-2/3-3/4011/6-1/61/2310000-1-1cBXBbOR171w由上表可知，辅助问题的最优解为：X*=(3,0,1,0,0)T,=0故可得原问题的一个初始基本可行解：X*=(3,0,1)T阶段2：求解原问题：将目标函数换回，并且删去人工变量，得到第二阶段的问题。由表上作业法求解。OR172cj3-1-2cBXBbx1x2x3x1x33110-2/3-4/3013270-5/30OR173