运筹学第1章线性规划与对偶问题.ppt

《运筹学第1章线性规划与对偶问题.ppt》由会员分享，可在线阅读，更多相关《运筹学第1章线性规划与对偶问题.ppt（179页珍藏版）》请在三一办公上搜索。

1、2023/6/27,1,运筹学OPERATIONS RESEARCH,单而芳(上海大学 管理学院)公共邮箱 cst_ 201211,2023/6/27,2,一、课程基本情况,课程名称：运筹学 Operations Research 参考书：管理运筹学，于丽英（主编），同济大学出版社,2012运筹学教程（第三版），胡运权（主编），清华大学出版社,2007运筹学（第三版），运筹学教材编写组，清华大学出版社,2005,2023/6/27,3,二、课程主要内容,绪论线性规划运输问题整数规划网络优化（网络规划，网络计划技术）动态规划决策分析,2023/6/27,4,三、课程考核方法,平时成绩占30%，包

2、括：课堂考勤平时作业课堂讨论，练习课堂提问期末闭卷考试占70%。,2023/6/27,5,绪 论,运筹学的含义及其发展运筹学的模型化方法论,2023/6/27,6,运筹学的产生与发展三个来源军事、管理、经济运筹学的发展历程 运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题.大规模轰炸的效果搜索和攻击敌军潜水艇的策略兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。,

3、0.1 运筹学的含义及其发展,2023/6/27,7,第二次世界大战期间，“OR”成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为“OR”后来的发展铺平了道路。战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。世界上不少国家已成立了致力于该领域及相关活动的专门学会，美国于1952年成立了运筹学会，并出版期刊运筹学，世界其它国家也先后创办了运筹学会与期刊，1957年成立了国际运筹学协会。运筹学在中国的发展1957年，我国科学家从史记中的古语“夫运筹帷幄之中、决胜千里之外”摘

4、取“运筹”二字，把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义 我国运筹学的主要奠基人:钱学森、华罗庚、许国志等。,2023/6/27,8,运筹学的含义及其与其他学科的关系运筹学Operations Research,简称OR研究如何以合理的方式，组织具有明确目标的活动的学科。研究在某一系统中，如何统筹安排，合理利用，以使该系统在某些方面的总效益达到最优的一门学科。是由各领域的专家学者协力完成并从各领域角度出发而得出的定量解决问题的方法。,2023/6/27,9,运筹学与决策科学的关系决策科学是研究决策过程规律,提供决策方法的科学。

5、,决策过程可用决策问题表达如下:OPTz(x)xS()其中x为决策方案；S()为环境条件下所有决策方案x的集合；z(x)为关于决策方案x的目标(评价)指标体系；OPT为关于z(x)的“最优”选择。,对于环境下的所有可行方案xS(),依据决策准则OPT，依据指标z(x)选择“最优”者。,2023/6/27,10,运筹学与管理科学的关系从管理的角度看，可以说运筹学是用定量方法为管理决策提供依据的一门学科。以便实现有效管理、正确决策和现代化管理可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”。现在普遍认为，运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有

6、普遍性的运筹问题加以提炼，然后利用数学方法进行解决。运筹学已成为管理科学中最重要的组成部分之一。,2023/6/27,11,0.2 运筹学的模型化方法论,运筹学解决问题的关键建立模型,2023/6/27,12,按照模型特征的分类：线性规划整数规划网络规划动态规划非线性规划多目标规划存贮论决策论排队论博弈论搜索论，等等,2023/6/27,13,运筹学模型求解的软件介绍 EXCELMATLAB WINQSB LINDO LINGO 等等,2023/6/27,14,运筹学在管理中的应用,生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等库存管理：多种物资库存量的管理，库存方式、

7、库存量等运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等 设备维修、更新，项目选择、评价，工程优化设计与管理等城市交通,2023/6/27,15,第一章 线性规划(Linear Programming,LP),线性规划模型图解法及单纯形算法几何意义单纯形算法及扩展对偶线性规划灵敏度分析线性规划应用举例软件应用,2023/6/27,16,1.1 线性规划模型,生产计

8、划模型运输模型投资模型人员安排模型等等,2023/6/27,17,例1 生产计划问题,2023/6/27,18,x1 12 x2 8 x1+2x2 20 x1，x2 0,max Z=100 x1+250 x2 s.t.,解:设产品甲,乙产量分别为变量 x1，x2,注意模型特点,这是约束条件（资源量的限制和产品数量非负的限制）,这是目标函数,2023/6/27,19,例2 运输问题,如何安排运输，可使总运费最小？,销售点,工厂,2023/6/27,20,设xij为i 厂运到 j销售点的运输量(i 1,2,3，j 1,2,3),minZ=7x11+9x12+3x13+x21+5x22+4x23+2

9、x31+4x32+2x33 s.t.,注意模型特点,2023/6/27,21,例3 投资计划问题。某公司现有资金10万元，欲制定其后三年对四个项目的投资计划，四个项目投资要求和收益如下：项目1，第一年至第三年每年年初投资，每年末回收本年本利111%(即投资额的111%，以下同);项目2，第二年年初投资，第三年末回收本利125%，但规定投资不超过3万元;项目3，第三年初投资，年末收本利120%，但规定投资额不超过4万元;项目4，第一年，第二年每年初投资，次年末收本利115%。,公司应怎样对各年各项目投资，才能使第三年末拥有的资金量(本利和)最大?,2023/6/27,22,分析,max,Xik(

10、i=1,2,3;k=1,2,3,4)第i年初投k项目的资金数,2023/6/27,23,xik(i=1,2,3;k=1,2,3,4)第i年初投k项目的资金数MaxZ=1.11x31+1.25 x22+1.2x33+1.15x24 s.t.,2023/6/27,24,例4 租借计划 某公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资。已知各月所需仓库面积如表。仓库租借费用随合同期而定，期限越长，折扣越大，具体如表。该公司可根据需要在任何一个月初办理租借合同，每次办理时可签订各类合同。试建立总租借费用最小的租借计划。,2023/6/27,25,分析,12 20 15 10,xij(i=1,2

11、,3,4;j=1,2,3,4)第i月月初签订租借期为j个月的合同租借面积,租借期,2023/6/27,26,xij(i=1,2,3,4;j=1,2,3,4)第i月月初签订租借期为j个月的合同租借面积资金数,minZ=2000（x11+x21+x31+x41）+3200（x12+x22+x32）+4200（x13+x23）4800 x14 s.t.,x11+x12+x13+x14=12x21+x22+x23+x12+x23+x14=20 x31+x22+x32+x13+x23+x14=15x41+x32+x23+x14=10 xij 0(i=1,2,3,4;j=1,2,3,4),2023/6/2

12、7,27,例5 人员安排计划 某昼夜服务的公交线路每天各时间区段所需司机和乘务人员数如表1-6所示。设司机和乘务人员分别在各时间区段一开始时上班，并连续工作8h，问该公交线路至少需配备多少名司机和乘务人员。,2023/6/27,28,设xi，yi(i1，2，6)分别表示第i班次开始上班的司机和乘务员人数，,2023/6/27,29,线性规划模型特点,决策变量：向量X=(x1 xn)T 决策人要考虑和控制的因素，非负约束条件：关于X的线性等式或不等式目标函数：Z=(x1 xn)为关于X 的线性函数，求Z极大或极小,2023/6/27,30,一般式,Max(min)Z=c1x1+c2x2+cnxn

13、 s.t.,2023/6/27,31,2023/6/27,32,隐含的假设,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值,2023/6/27,33,LP模型应用,市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计

14、划，设备更新)城市管理(供水，污水管理，服务系统设计、运用),2023/6/27,34,1.2 图解法及单纯形算法几何,图解法举例例1：max Z=100 x1+250 x2 s.t.x1 12 x2 8 x1+2x2 20 x1，x2 0,2023/6/27,35,x2,P5,P4,P3,P2,P1,x1,x2=8,x1+2x2=20,x1=12,100 x1+250 x2=h,z=z0,(4,8),Z*=100*4+250*8=2400,等值线,2023/6/27,36,max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20,可行域,目标函数等值线,最优解,6,4,-

15、8,6,0,x1,x2,2023/6/27,37,(1)无解例6 maxZ=100 x1+200 x2 s.t.,几点说明：,这两个约束是不相容的,2023/6/27,38,(2)目标无界例7,maxZ=2x1+3x2 s.t.,x1-x2 2-3x1+x2 3/2x1,x2 0,约束构成无界区域，目标函数的等值线无限延伸,2023/6/27,39,(3)无穷多最优解例8 maxZ=100 x1+200 x2 s.t.,这两条直线是平行的,2023/6/27,40,结论解的几种情况：最优解（唯一和无穷），无最优解（无解和目标无界）。LP的可行解存在，则可行解域是一个凸集。,凸集,凸集,不是凸集

16、,极点,2023/6/27,41,LP有最优解，则最优解或最优解之一必在可行解域的凸集的顶点上达到。可行解域的一个顶点是最优解的充分条件是：在这个顶点处每条棱均不改善。从可行解域的一个顶点出发，沿着改善棱前进，有限次后会找到最优顶点。,2023/6/27,42,Sk最优,kk+1,存在一个极点So否,极点Sk有改善棱否,改善棱上有另一个极点否,极点Sk+1(比Sk改善),LP无解,LP目标无界,否,否,否,单纯形算法的几何叙述,2023/6/27,43,1.3 单纯形算法及扩展,1、LP标准型2、解的概念3、单纯形法4、单纯形法的进一步讨论5、注意的问题,2023/6/27,44,1、线性规划

17、的标准型,2023/6/27,45,线性规划的标准型定义,max(min)Z=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0(j=1,n),其中:bi0,2023/6/27,46,其中:bi0,其中:b0,矩阵形式,2023/6/27,47,如何化标准型？要求目标函数max 要求b非负要求x非负要求约束为等式约束举例(对例1）,2023/6/27,48,max Z=100 x1+250 x2s.t.x1+x3=12 x2+x4=8 x1+2x2+x5=20 x1 x5

18、0,max Z=100 x1+250 x2 s.t.x1 12 x2 8 x1+2x2 20 x1，x2 0,对例1,松弛变量,2023/6/27,49,例9,这需要减一个剩余变量,2023/6/27,50,2、解的概念,可行解：满足约束条件的解。最优解：使目标达到最优的可行解。基矩阵AB（许多参考书用记号：B）基变量XB非基变量XN基解：基本可行解：基解，且非负,AB-1 b 0,X=,令非基变量=0,2023/6/27,51,max Z=100 x1+250 x2 s.t.x1 12 x2 8 x1+2 x2 20 x1，x2 0,x1,x2,x28,x1+2x2 20,x1 12,(12

19、,0),(12,4),(4,8),(0,8),(0,0),对例1,可行解域,最优解,2023/6/27,52,2023/6/27,53,max Z=100 x1+250 x2 s.t.x1+x3=12 x2+x4=8 x1+2 x2+x5=20 x1，x2 0,x1,x2,x28,x1+2x2 20,x1 12,(12,0,0,8,8),(12,4,0,4,0),(4,8,8,0,0),(0,8,12,0,4),(0,0,12,8,20),对例1,基本可行解,2023/6/27,54,Sk最优,kk+1,存在一个极点So否,极点Sk有改善棱否,改善棱上有另一个极点否,极点Sk+1(比Sk改善)

20、,LP无解,LP目标无界,否,否,否,单纯形算法,STEP 1,STEP 2,STEP 3,4,STEP 5,单纯形法原理示意图,顶点4，最优解,初始顶点1,顶点2,顶点3,其实，不必搜索可行域的每一个顶点，只要从一个顶点出发，沿着使目标函数改善的方向，到达下一个相邻的顶。如果相邻的所有顶点都不能改善目标函数，这个顶点就是最优顶点。用这样的搜索策略，可以大大减少搜索顶点的个数。按照这样的搜索策略建立的算法，叫做单纯形法(simplex algorithm)。它是由美国数学家G.B.丹齐克于1947年首先提出来的，是线性规划问题的数值求解的流行技术。,目标函数改善,目标函数改善,目标函数改善,单

21、纯形法的基本思想,它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。,2023/6/27,57,3、单纯形算法-基本步骤(对max问题),(1)给出初始单纯形表,确定初始基本可行解。（注意初始单纯形表的特征）(2)检验。检验非基变量检验数 是否全

22、 0。若是，停止，得到最优解；若否，转(3)(3)选择进基变量。若非基变量检验数有 0，对应的系数Pk全 0，停止，原问题目标无界。否则选择为进基变量，转(4),2023/6/27,58,定xr为出基变量，为主元，转(5)。,由最小比值法求：,(4)选择出基变量,对应变量xr,转(2)。,(5)修正表格。以 为中心，换基迭代,2023/6/27,59,max Z=100 x1+250 x2 s.t.x1+x3=12 x2+x4=8 x1+2x2+x5=20 x1 x5 0,对例1,这个标准型中有一个明显的基和基可行解,2023/6/27,60,基变量,初始基可行解,初始单纯形表,250-(00

23、+01+02)=250,检验数：,2023/6/27,61,2023/6/27,62,2023/6/27,63,举例,加入松弛变量,所以把x3换出为非基变量，x2为换入变量即新的基变量。,可以看出，x1的检验数为3，大于0，但是x1的系数列向量中的所有元素（-2,-1)T，都小于0，所以该题为无界解.,加入松弛变量,举例,此时所有的检验数都小于等于0，所以该解为最优解。,最优解为X（9/4，25/4，0，0）T，Z*63,非基变量x4的检验数0，那么该LP问题有无穷多个最优解,2023/6/27,72,max Z=-2x1+x2 x3+5x4-22x5 s.t.,x1+2x4+x5=6 x2+

24、x4+4x5=3 x3+3x4+2x5=10 x1,，x5 0,例10,2023/6/27,73,练习 max z=50 x1+100 x2 s.t.x1+x2 300 2 x1+x2 400 x2 250 x1,x2 0先标准化：max z=50 x1+100 x2 s.t.x1+x2+x3=300 2 x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x5 0,2023/6/27,74,最优解 x1=50 x2=250 x4=50（松弛标量，表示原料A有50个单位的剩余）,2023/6/27,75,注意：单纯形法中，1、每一步运算只能用矩阵初等行变换；2、表中第b列的数

25、总应保持非负（0）；3、当所有检验数均非正（0）时，得到最优单纯形表。,2023/6/27,76,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：凸多边形,满足一组不等式约束的解,约束直线的交点,基解,可行域的极点,基本可行解,目标函数等值线：一组平行线,目标函数值等于一个常数的解,2023/6/27,77,4、单纯形算法的进一步讨论两阶段法和大M法,前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。

26、这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。,不存在单位矩阵，如何构造初始可行基？,2023/6/27,78,4、单纯形算法的进一步讨论两阶段法和大M法,s.t.,s.t.,yi人工变量（伪变量）,2023/6/27,79,例11 min z=4x1+x2+x3,2x1+x2+2x3=43x1+3x2+x3=3x1，x2，x30,s.t.,辅助问题：min W=y1+y2,2x1+x2+2x3+y1=43x1+3x2+x3+y2=3x1，x3,y1,y20,s.t.,人工变量,2023/6/27,80,解题过程：第

27、一阶段：用单纯形法求解辅助问题。若求得辅助问题的目标函数=0,也即人工变量都等于0，则进入第二阶段。否则,原问题无可行解。第二阶段：去掉人工变量，还原目标函数系数，此时，就能得到原问题的初始单纯形表。继续用单纯形法求解即可。,2023/6/27,81,练习：max z=-3x1+x3,x1+x2+x3 4-2x1+x2-x3 1 3x2+x3=9x1，x2，x30,s.t.,标准化,x1+x2+x3+x4=4-2x1+x2-x3-x5=1 3x3+x3=9x1,x5 0,max z=-3x1+x3,2023/6/27,82,辅助问题：min w=y1+y2,s.t.,2023/6/27,83,

28、max z=-x1+2x2,x1+x2 2-x1+x2 1 x2 3x1,x2 0,练习：,s.t.,2023/6/27,84,第(1)阶段：,min w=x6+x7,x1+x2-x3+x6=2-x1+x2-x4+x7=1 x2+x5=3x1 x7 0,s.t.,例：,构造第一阶段问题并求解,解：,用单纯形法求解,两阶段法（第一阶段、求min）,表1,1 0 0 0-1 1 0 0 0,0-1 0,0 0-1,x4 x5 x6,两阶段法（第一阶段、求min）,表2,1,1-2 2 0-1 1 0 0 0,0 0-1,0 0-1,x4 x5 x6,两阶段法（第一阶段、求min）,表3：最终单纯形

29、表,第二阶段,不含人工变量且=0,两阶段法,第二阶段,将去掉人工变量，还原目标函数系数，做出初始单纯形表。,1 0 0 0-1,两阶段法,1/3-2/3 0-1 2/3-4/3,0 0,x4 x5,第二阶段,0 0 0-1/3-1/3,最优解为目标函数值 z=2,2023/6/27,92,(2)人工变量法（大M法）,例11 min z=4x1+x2+x3,2x1+x2+2x3=43x1+3x2+x3=3x1，x2，x30,s.t.,建立一个新问题,2023/6/27,93,min z=4x1+x2+x3+My1+My2,2x1+x2+2x3+y1=43x1+3x2+x3+y2=3x1，y20,

30、s.t.,目标函数中添加“罚因子”M（M是任意大的正数）为人工变量系数，只要人工变量0，则目标函数不可能实现最优。,判定无解条件：当进行到最优表时，仍有人工变量在基中，且0，则说明原问题无可行解。,2023/6/27,94,练习：max z=-3x1+x3,x1+x2+x3 4-2x1+x2-x3 1 3x2+x3=9x1，x2，x30,s.t.,2023/6/27,95,标准化,max z=-3x1+x3,x1+x2+x3+x4=4-2x1+x2-x3-x5=1 3x2+x3=9x1 x7 0,s.t.,2023/6/27,96,加入人工变量,s.t.,目标函数中添加“罚因子”-M为人工变量

31、系数，只要人工变量0，则目标函数不可能实现最优。,约束条件：“”：则减去一个剩余变量后，再加一个人工变量.“”：则加一个人工变量.目标函数求最大：人工变量的系数为“M”，即罚因子.若线性规划问题有最优解则人工变量必为0.,例题,标准化,加入人工变量,2023/6/27,114,5、单纯形法计算中的几个注意问题,1)判定最优解定理：max z问题，非基变量检验数 0min z问题，非基变量检验数0 2)退化解问题3）计算中注意（1）标准型中有初始基本可行解，用单纯形法求解。（2)标准型中没有初始基本可行解，用大M法（或者用二阶段法）加人工变量，使之构成单位基。,2023/6/27,115,4)解

32、的几种情况：唯一解:最优表中非基变量检验数0(max)。无穷多最优解:最优表中非基变量检验数有为0者。无可行解:最优表中人工变量在基中，且不等于0。（用大M法或两阶段法判别）目标无界：存在进基变量，其对应的系数均 0。,2023/6/27,116,1.4 对偶线性规划Dual linear programming,DLP,1、对偶问题的建立2、对偶规划性质3、利用LP的最优表求DLP的最优解4、经济解释5、对偶单纯形算法,1954年美国数学家C.莱姆基提出对偶单纯形法(Dual Simplex Method)。,实例：某家电厂利用现有资源生产两种产品，有关数据如下表：,一、对偶问题的提出,如何

33、安排生产，使获利最多？,厂家,设 产量 产量,若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么3种设备的机时如何定价才是最佳决策？,设：设备A 元时 设备B 元时 调试工序 元时,收购,出让代价应不低于用同等数量的资源自己生产的利润。,付出的代价最小，且对方能接受。,厂家,厂家能接受的条件：收购方的意愿：,出让代价应不低于用同等数量的资源自己生产的利润。,厂家,对偶问题,原问题,收购,厂家,一对对偶问题,2023/6/27,122,甲,乙各生产多少,才能使工厂获利最大?,y1,y2,y3,1、对偶问题的建立,2023/6/27,123,max Z=100 x1+250

34、 x2,min W=8y1+5y2+12y3,s.t.,s.t.,2023/6/27,124,定义：,是互为对偶的线性规划。,Dual linear programming,s.t.,s.t.,2023/6/27,125,对一般线性规划模型-对偶规划建立的法则,2023/6/27,126,例13,2023/6/27,127,例14,2023/6/27,128,练习：,s.t.,2023/6/27,129,对称性弱对偶性:若X*和Y*分别是原问题（1）及对偶问题（2）的可行解，则有CX*bTY*LP有可行解，且目标无界，则DLP无可行解。DLP有可行解，且目标无界，则LP无可行解。LP有可行解，

35、DLP无可行解，则LP目标无界。DLP有可行解，LP无可行解，则DLP目标无界。最优性LP有一个可行解X，DLP有一个可行解Y，且目标值相等，则分别为LP和DLP的最优解。,2、对偶规划性质,2023/6/27,130,强对偶性：若LP和DLP均有可行解，则两者均有最优解，且他们的最优解的目标值相等。互补松驰性：每个约束的松弛变量（或者剩余变量）和该约束相对应的对偶变量的乘积为0。利用该性质可以求出DLP的最优解。,(b-AX)TY=0,X T(ATY-CT)=0,2023/6/27,131,对例1,max Z=100 x1+250 x2 x1 12 x2 8 x1+2x2 20 x1，x2

36、0,X*=(4,8),求对偶问题的最优解。,s.t.,2023/6/27,132,min Z=2x1-x2+2x3,-x1+x2+x3=4-x1+x2-kx3 6x1 0，x2 0,x3无约束,其最优解为X=（-5，0，-1）。（1）求 k值；（2）求对偶问题的最优解。,练习,s.t.,2023/6/27,133,练习,线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。线性规划的对偶问题无可行解，则原问题也一定无可行解。在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值。任何线性规划问题具有唯一的对偶问题。,20

37、23/6/27,134,练习,已知线性规划利用对偶理论证明:z1.,2023/6/27,135,DLP的最优解的变量值与LP的最优表的松弛变量的检验数的相反数对应相等。见例1的单纯形最终表,3、利用LP的最优表求得DLP的最优解,2023/6/27,136,求偏导：,对偶解y：b 的单位改变量所引起的目标函数值的改变量。yi的大小表示:在其他条件不变的情况下，单位第i资源变化对目标的贡献，是对资源i的一种估价，称为影子价格。,4、经济解释,2023/6/27,137,影子价格是一种边际价格：单位资源的变化所引起的目标值的变化量。A生产线的资源影子价格y1=0说明生产能力的增加对获利没有影响；B

38、生产线资源影子价格y2=50，说明B生产线增加生产能力一台(由12台/天变为13台/天)，最大日利润增加50元；检测车间的劳动力资源影子价格y3=100，说明检测车间每增加一位劳动力可以增加利润100元。影子价格可以确定资源是否充分利用。影子价格是一种机会成本，当资源的市场价格低于影子价格时，企业应买进该种资源，以扩大再生产；反之，则应将已有资源卖掉。注意：随着生产任务、产品结构等情况的不同，资源的影子价格也可能变化。,2023/6/27,138,(1)基解,(2)基可行解,(3)对偶可行解,保持对偶可行，寻找原始可行的顶点。三个概念,单纯形法思路在满足条件(1)和(2)的前提下逐步满足条件(

39、3),对偶单纯形法思路在满足条件(1)和(3)的前提下逐步满足条件(2),5、对偶单纯形法（略）,2023/6/27,139,步骤：建立初始表（对偶可行）检验（是否原始可行）选择出基变量选择进基变量修正表格,2023/6/27,140,STEP1.建立初始单纯形表，满足对偶可行。STEP2.检验:若所有常数项bl非负,则x*为最优解;否则,转下一步。STEP3.选择出基变量。根据 bl=min bi 0|i=1,2,m 确定第l个变量xl为出基变量;若在小于零的常数项中,若有某一系数行向量 0,则此问题无界(没有最优解)。停止计算。否则,转入下一步。,2023/6/27,141,STEP4.选

40、择进基变量。根据最小比值法则:=minj/alj|alj0,j=1,2,n=k/alk 确定原基变量中的第k个基变量为进基变量。,STEP5.修正表格。以第l行第k列元素alk为主元素进行迭代(即用高斯消去法),把xk所对应的列向量(包括检验数共m+1个元素)Ak变换成只有第l个元素为1,其余元素均为0的列向量。转STEP2。,2023/6/27,142,对例1的对偶规划,max Z=100 x1+250 x2 s.t.x1 12 x2 8 x1+2x2 20 x1，x2 0,2023/6/27,143,列出单纯形表，并用对偶单纯形法求解步骤进行计算,8,2023/6/27,144,例15 m

41、inZ=3x1+4x2+5x3,x1+2x2+3x3 52x1+2x2+x3 6x1，x2，x30,s.t.,2023/6/27,145,化为 maxZ=-3x1 4x2-5x3,-x1-2x2-3x3+x4=-5-2x1-2x2-x3+x5=-6x1，x2，x30,s.t.,2023/6/27,146,1.5 灵敏度分析-线性规划最优解的分析,最优解的条件与最优基矩阵的逆矩阵灵敏度分析分析cj的变化对最优解的影响分析bj的变化对最优解的影响分析A的变化对最优解的影响分析系数aij的变化对最优解的影响增加一个约束条件的分析增加一个新的变量xj的分析,2023/6/27,147,单纯形表所表示的

42、解是最优解的条件(MAX)：基解是可行解2)检验数满足0，即,2023/6/27,148,初始表,最优表,A,b,X,检验数 0,max,max,2023/6/27,149,b变为b+b,若满足，原基仍为最优基，但最优解与最优目标值改变。否则，用对偶单纯形法进行迭代。,最优表,检验数,max,（1）资源系数b的灵敏度分析,与b有关,与b无关,2023/6/27,150,根据原最终表确定XB,AB-1,x1 x3 x2,XB=,对例1:b1在怎样的范围内变化，原最优性不变？,2023/6/27,151,15 10 24,例,12820,变为,问原最优性是否改变？,若b,2023/6/27,152

43、,满足,原最优基不变。此时最优解为：,最优目标函数值为：Z*=2900。,2023/6/27,153,C变为C+C,若满足，则原最优性不变，此时最优解不变，但最优目标值改变。否则，原基仍为可行基，用单纯形法进行迭代。,最优表,检验数,max,与C无关,新的检验数0?,（2）价值系数C的灵敏度分析,2023/6/27,154,最终表,对例1,2023/6/27,155,保持原最优基不变的资源常数C的变化范围,若保持原最优性不变，则2c1-2500和-c10，于是有0c1125。,同理c2,2023/6/27,156,目标函数系数向量,变为,原最优性是否改变呢？,2023/6/27,157,迭代得

44、到,2023/6/27,158,最优表,检验数,max,（3）技术系数A的灵敏度分析,与A有关,与A有关,(3.1)A增加一列（相当于增加一种产品）,与“非基变量的系数变化”相同处理,2023/6/27,159,对例1 假设工厂推出一种新产品丙，它同时要利用两条生产线，生产单位产品丙需要各消耗A，B生产线1台时，在检测车间上的消耗为1人/台，利润为180元/台。那最优生产方案是什么呢？,2023/6/27,160,根据原最终表确定的XB,AB-1，得到,我们设产品丙的生产量为x6，此时产品丙在最终表中的系数矩阵为：,a6,2023/6/27,161,最优生产方案：x1=8，x2=4，x6=4，

45、利润为2520元。,2023/6/27,162,(3.2)A增加一行（相当于增加一种资源或者一道工序）用对偶单纯形法迭代,对例1，引入调试工序，相应资源约束为：,2023/6/27,163,修改例1的最终表，得到,进行行变换，得到,2023/6/27,164,用对偶单纯形法继续计算，得到,最优生产方案：，利润为2200元。,2023/6/27,165,(3.3)某非基变量的系数Ar变为Ar+Ar基矩阵：不变基本可行解：不变检验数：CBAB-1(Ar+Ar)0?,若满足，原解仍为最优解，最优值也不变；否则，原基为可行，用单纯形法迭代，求得新的最优解。,重新计算,2023/6/27,166,(3.

46、4)基变量系数变化基矩阵：变化需要重新用单纯形法计算,2023/6/27,167,1.6 线性规划应用举例,例 一家五星级酒店的客房部经理负责安排员工的工作。要求员工每周连续工作5天，然后休假2天，每天酒店对员工的要求如下表。问：至少需要雇佣多少人员，可以满足酒店客房部运转的需要。,2023/6/27,168,设决策变量：xi为自星期i开始上班的员工数。,2023/6/27,169,例(生产计划）,2023/6/27,170,2023/6/27,171,2023/6/27,172,例 一贸易公司专门经营某种杂粮的批发业务。公司现有库容为5000担的仓库。一月一日，公司拥有库存1000担杂粮，并

47、有资金20000元。估计第一季度杂粮价格如表所示。如买进的杂粮当月到货，但需要到下月才能卖出，且规定“货到付款”。公司希望本季末库存为2000担，问应采取什么样的买进与卖出的策略使三个月总的获利最大？如何写出本问题的线性规划模型呢？,2023/6/27,173,解：设sk：第k月初仓库中的库存量(含上月定货量)，xk：第k月卖出的货物量，yk：第k月订购的货物量。数学模型如下：,第2个月初拥有的资金数量,2023/6/27,174,例（生产计划)永久机械厂生产、三种产品，均要经过A、B 两道工序加工。假设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工

48、序。可在A的任何规格的设备上加工，但不能在B1上加工；可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能在A2与B2设备上加工。现已知数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？,2023/6/27,175,2023/6/27,176,例 某厂用原料A，B，C生产三种不同的产品甲、乙、丙。已知各种产品中A，B，C的含量、原料成本、各种原料的每月限制用量、三种产品的加工费用以及售价如表。（假设三种产品的生产过程中无任何损耗。）问如何安排生产，可使该厂利润最大？,2023/6/27,177,设决策变量：xij-生产i 产品消耗原料 j 的量，i,j=1,2,3。,2

49、023/6/27,178,1.7 线性规划软件应用,求解线性规划的软件主要有EXCEL、MATLAB、LINDO/LINGO和WINQSB等,2023/6/27,179,在输入中要注意以下几点：输入的系统可以是整数、小数，但不能是分数，要把分数先化为小数再输入。输入前先要合并同类项。由于计算机键盘没有“”、“”的符号，我们约定用“”代替“”，用“”代替“”。当约束条件都输入完了之后，请在下一个约束条件后输入“END”。点击“计算”，得到输出结果,LINDO/LINGO软件应用,输入：max 100 x1+250 x2s.t.x1=12 x2=8 x1+2x2=20End,其他例题的计算类似！,