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

2023-2-71运筹学运筹学OPERATIONS RESEARCH单而芳单而芳(上海大学上海大学 管理学院管理学院)公共邮箱公共邮箱 cst_ 2012112023-2-72一、课程基本情况一、课程基本情况n课程名称：运筹学课程名称：运筹学 qOperations Research n参考书：参考书：q管理运筹学，于丽英（主编），同济大学出版社管理运筹学，于丽英（主编），同济大学出版社,2012q运筹学教程（第三版），胡运权（主编），清华大学出版运筹学教程（第三版），胡运权（主编），清华大学出版社社,2007q运筹学（第三版），运筹学教材编写组，清华大学出版运筹学（第三版），运筹学教材编写组，清华大学出版社社,20052023-2-73二、课程主要内容二、课程主要内容n绪论绪论n线性规划线性规划n运输问题运输问题n整数规划整数规划n网络优化（网络规划，网络计划技术）网络优化（网络规划，网络计划技术）n动态规划动态规划n决策分析决策分析2023-2-74三、课程考核方法三、课程考核方法n平时成绩占平时成绩占30%，包括：，包括：q课堂考勤课堂考勤q平时作业平时作业q课堂讨论，练习课堂讨论，练习q课堂提问课堂提问n期末闭卷考试占期末闭卷考试占70%。2023-2-75绪绪 论论n运筹学的含义及其发展运筹学的含义及其发展n运筹学的模型化方法论运筹学的模型化方法论2023-2-76n运筹学的产生与发展运筹学的产生与发展q三个来源军事、管理、经济三个来源军事、管理、经济q运筹学的发展历程运筹学的发展历程n 运筹学是在第二次世界大战中诞生和发展起来的。由于战争的运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题的领导下研究战争中的问题.大规模轰炸的效果大规模轰炸的效果 搜索和攻击敌军潜水艇的策略搜索和攻击敌军潜水艇的策略 兵力和军需物质的调运等等。兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战作战研究研究”，英文是，英文是Operational Research，在美国称为，在美国称为Operations Research。0.1 运筹学的含义及其发展运筹学的含义及其发展2023-2-77 第二次世界大战期间，第二次世界大战期间，“OR”成功地解决了许多重要作战问题，显示了成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为科学的巨大物质威力，为“OR”后来的发展铺平了道路。后来的发展铺平了道路。n战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，理领域，也产生了很好的效果。这样，Operations Research就转义成为就转义成为“作作业研究业研究”。n 世界上不少国家已成立了致力于该领域及相关活动的专门学会，美国于世界上不少国家已成立了致力于该领域及相关活动的专门学会，美国于1952年成立了运筹学会，并出版期刊年成立了运筹学会，并出版期刊运筹学运筹学，世界其它国家也先后创办了运筹，世界其它国家也先后创办了运筹学会与期刊，学会与期刊，1957年成立了国际运筹学协会。年成立了国际运筹学协会。q运筹学在中国的发展运筹学在中国的发展n1957年，我国科学家从年，我国科学家从史记史记中的古语中的古语“夫运筹帷幄之中、决夫运筹帷幄之中、决胜千里之外胜千里之外”摘取摘取“运筹运筹”二字，把二字，把Operations Research译成译成“运筹学运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义面的涵义n 我国运筹学的主要奠基人我国运筹学的主要奠基人:钱学森、华罗庚、许国志等。钱学森、华罗庚、许国志等。2023-2-78n运筹学的含义及其与其他学科的关系运筹学的含义及其与其他学科的关系q运筹学运筹学Operations Research,简称简称ORn研究如何以合理的方式，组织具有明确目标的活动的学科。研究如何以合理的方式，组织具有明确目标的活动的学科。n研究在某一系统中，如何研究在某一系统中，如何统筹安排统筹安排，合理利用，以使该系统在，合理利用，以使该系统在某些方面的某些方面的总效益达到最优总效益达到最优的一门学科。的一门学科。n是由各领域的专家学者协力完成并从各领域角度出发而得出的是由各领域的专家学者协力完成并从各领域角度出发而得出的定定量解决问题的方法量解决问题的方法。2023-2-79q运筹学与决策科学的关系运筹学与决策科学的关系n决策科学是决策科学是研究决策过程规律研究决策过程规律,提供决策方法的科学。提供决策方法的科学。决策过程可用决策问题表达如下决策过程可用决策问题表达如下:OPTz(x)xS()其中其中x为决策方案；为决策方案；S()为环境条件为环境条件 下所有决策方案下所有决策方案x的集合；的集合；z(x)为关于决策方案为关于决策方案x的目标的目标(评价评价)指标体系；指标体系；OPT为关于为关于z(x)的的“最优最优”选择。选择。对于环境对于环境 下的所有可行方案下的所有可行方案xS(),依据决策准则依据决策准则OPT，依据指标依据指标z(x)选选择择“最优最优”者。者。2023-2-710q运筹学与管理科学的关系运筹学与管理科学的关系n从管理的角度看，可以说运筹学是用从管理的角度看，可以说运筹学是用定量方法定量方法为管为管理决策提供依据的一门学科。以便理决策提供依据的一门学科。以便实现有效管理、正确决策和现代化管理可简单地归结为一句话：可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方依照给定条件和目标，从众多方案中选择最佳方案案”。n现在普遍认为，运筹学是近代现在普遍认为，运筹学是近代应用数学的一个分支应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解性的运筹问题加以提炼，然后利用数学方法进行解决。决。n运筹学已成为管理科学中最重要的组成部分之一。运筹学已成为管理科学中最重要的组成部分之一。2023-2-7110.2 运筹学的模型化方法论运筹学的模型化方法论运筹学解决问题的关键运筹学解决问题的关键建立模型建立模型 确定现实问题模型模型解实施方案建摸分析求解解释2023-2-712n按照模型特征的分类：按照模型特征的分类：q线性规划线性规划q整数规划整数规划q网络规划网络规划q动态规划动态规划q非线性规划非线性规划q多目标规划多目标规划q存贮论存贮论q决策论决策论q排队论排队论q博弈论博弈论q搜索论，搜索论，等等等等2023-2-713n运筹学模型求解的软件介绍运筹学模型求解的软件介绍 qEXCELqMATLAB qWINQSB qLINDO qLINGO q等等2023-2-714运筹学在管理中的应用运筹学在管理中的应用n生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等n库存管理：多种物资库存量的管理，库存方式、库存量等n运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等n人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等n市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等n财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等n 设备维修、更新，项目选择、评价，工程优化设计与管理等n城市交通2023-2-715第一章第一章 线性规划线性规划(Linear Programming,LP)n线性规划模型n图解法及单纯形算法几何意义n单纯形算法及扩展n对偶线性规划n灵敏度分析n线性规划应用举例n软件应用2023-2-7161.1 线性规划模型线性规划模型n生产计划模型生产计划模型n运输模型运输模型n投资模型投资模型n人员安排模型人员安排模型n等等等等2023-2-717 甲甲 乙乙 生产能力生产能力 A生产线生产线 1 0 12 B生产线生产线 0 1 8 检测车间检测车间 1 2 20 利润利润 100 250例例1 生产计划问题生产计划问题产品产品甲甲产品产品乙乙2023-2-718 x1 12 x2 8 x1+2x2 20 x1，x2 0 max Z=100 x1+250 x2 s.t.解解:设产品甲设产品甲,乙产量分别为变量乙产量分别为变量 x1，x2注意模型特点注意模型特点这是约束条件（资这是约束条件（资源量的限制和产品源量的限制和产品数量非负的限制）数量非负的限制）这是目标函数这是目标函数2023-2-719例例2 运输问题运输问题 单位运费单位运费 甲甲 乙乙 丙丙 供应量供应量 A 7 9 3 18 B 1 5 4 12 C 2 4 2 12 需求量需求量 6 16 8如何安排运输，可使总运费最小？如何安排运输，可使总运费最小？销售点销售点工工厂厂2023-2-720设设xij为为i 厂运到厂运到 j销售点的运输量销售点的运输量(i 1,2,3，j 1,2,3)minZ=7x11+9x12+3x13+x21+5x22+4x23+2x31 +4x32+2x33 s.t.x11+x12+x13 18x21+x22+x23 12x31+x32+x33 12x11+x21+x31 =6x12+x22+x32 =16x13+x23+x33 =8 xij 0注意模型特点注意模型特点2023-2-721例例3 投资计划问题。投资计划问题。某公司现有资金某公司现有资金10万元，欲制定其后三年对四个项万元，欲制定其后三年对四个项目的投资计划，四个项目投资要求和收益如下：目的投资计划，四个项目投资要求和收益如下：q项目项目1，第一年至第三年每年年初投资，每年末回收第一年至第三年每年年初投资，每年末回收本年本利本年本利111%(即投资额的即投资额的111%，以下同，以下同);q项目项目2，第二年年初投资，第三年末回收本利第二年年初投资，第三年末回收本利125%，但规定投资不超过但规定投资不超过3万元万元;q项目项目3，第三年初投资，年末收本利第三年初投资，年末收本利120%，但规定但规定投资额不超过投资额不超过4万元万元;q项目项目4，第一年，第二年每年初投资，次年末收本利第一年，第二年每年初投资，次年末收本利115%。公司应怎样对各年各项目投资，才能使第三年末拥有的资金量公司应怎样对各年各项目投资，才能使第三年末拥有的资金量(本利本利和和)最大最大?2023-2-722n分析分析 1 2 31 x11 x21 x31 1.112 x22 1.25 33 x33 1.2 4 4 x14 x24 1.15maxXik(i=1,2,3;k=1,2,3,4)第第i年初投年初投k项目的资金数项目的资金数2023-2-723nxik(i=1,2,3;k=1,2,3,4)第第i年初投年初投k项目的资金数项目的资金数nMaxZ=1.11x31+1.25 x22+1.2x33+1.15x24 s.t.x11+x14=10 x21+x22+x24=1.11 x11x22 3x31+x33=1.11 x21+1.15x14x33 4 xik 0(i=1,2,3;k=1,2,3,4)2023-2-724例例4 租借计划租借计划 某公司拟在下一年度的某公司拟在下一年度的1-4月的月的4个月内需租用仓库堆放物资。个月内需租用仓库堆放物资。已知各月所需仓库面积如表。仓库租借费用随合同期而定，期已知各月所需仓库面积如表。仓库租借费用随合同期而定，期限越长，折扣越大，具体如表。该公司可根据需要在任何一个限越长，折扣越大，具体如表。该公司可根据需要在任何一个月初办理租借合同，每次办理时可签订各类合同。试建立总租月初办理租借合同，每次办理时可签订各类合同。试建立总租借费用最小的租借计划。借费用最小的租借计划。月1234面积（100m2）12201510租借期限1个月2个月3个月4个月合同期内租费（元/100m2）20003200420048002023-2-725n分析分析 1 2 3 41 x11 x21 x31 x41 20002 x12 x22 x32 3200 3 x13 x23 42004 x14 4800 12 20 15 10 xij(i=1,2,3,4;j=1,2,3,4)第第i月月初签订租借月月初签订租借期为期为j个月的合同租借面积个月的合同租借面积租借期租借期2023-2-726xij(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-2-727例例5 人员安排计划人员安排计划 某昼夜服务的公交线路每天各时间区段所需司机和乘务人员数如某昼夜服务的公交线路每天各时间区段所需司机和乘务人员数如表表1-6所示。设司机和乘务人员分别在各时间区段一开始时上班，所示。设司机和乘务人员分别在各时间区段一开始时上班，并连续工作并连续工作8h，问该公交线路，问该公交线路至少至少需配备多少名司机和乘务人员。需配备多少名司机和乘务人员。班次班次工作时间工作时间所需司机人数所需司机人数（人）（人）所需乘务人员所需乘务人员人数（人）人数（人）16:00-10:002010210:00-14:00126314:00-18:002010418:00-22:00168522:00-2:0010562:00-6:00842023-2-728 设设xi，yi(i1，2，6)分别表示第分别表示第i班次开始上班的司班次开始上班的司机和乘务员人数机和乘务员人数，1020485108161020612.min1616656554544343323221216161yyxxyyxxyyxxyyxxyyxxyyxxtsyxziiii2023-2-729线性规划模型特点线性规划模型特点n决策变量决策变量：向量：向量X=(x1 xn)T 决策人要考虑和控制的决策人要考虑和控制的因素，因素，非负非负n约束条件约束条件：关于：关于X的的线性线性等式或不等式等式或不等式n目标函数目标函数：Z=(x1 xn)为关于为关于X 的的线性线性函数，求函数，求Z极大或极小极大或极小2023-2-730一般式一般式Max(min)Z=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn (=,)b1a21x1+a22x2+a2nxn (=,)b2 am1x1+am2x2+amnxn (=,)bmxj 0(j=1,n)2023-2-731.max(min)1tsxcZnjjj),2,1(0),2,1(1njxmibxajinjjij2023-2-732隐含的假设隐含的假设n比例性比例性：决策变量变化引起目标的改变量与决策：决策变量变化引起目标的改变量与决策变量改变量成正比变量改变量成正比n可加性可加性：每个决策变量对目标和约束的影响：每个决策变量对目标和约束的影响独立独立于其它变量于其它变量n连续性连续性：每个决策变量取连续值：每个决策变量取连续值n确定性确定性：线性规划中的参数：线性规划中的参数aij,bi,ci为确定值为确定值 2023-2-733LP模型应用模型应用n市场营销市场营销(广告预算和媒介选择，竞争性定价，新产品广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划开发，制定销售计划)n生产计划制定生产计划制定(合理下料，配料，合理下料，配料，“生产计划、库存、生产计划、库存、劳力综合劳力综合”)n库存管理库存管理(合理物资库存量，停车场大小，设备容量合理物资库存量，停车场大小，设备容量)n运输问题运输问题n财政、会计财政、会计(预算，贷款，成本分析，投资，证券管理预算，贷款，成本分析，投资，证券管理)n人事人事(人员分配，人才评价，工资和奖金的确定人员分配，人才评价，工资和奖金的确定)n设备管理设备管理(维修计划，设备更新维修计划，设备更新)n城市管理城市管理(供水，污水管理，服务系统设计、运用供水，污水管理，服务系统设计、运用)2023-2-7341.2 图解法及单纯形算法几何图解法及单纯形算法几何 图解法举例图解法举例例例1：max Z=100 x1+250 x2 s.t.x1 12 x2 8 x1+2x2 20 x1，x2 02023-2-735x2P5P4P3P2P1x1x2=8x1+2x2=20 x1=12100 x1+250 x2=hz=z0(4,8)Z*=100*4+250*8=2400等值线等值线2023-2-736max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解64-860 x1x22023-2-737(1)1)无解无解例例6 max6 maxZ Z=100=100 x1+200 x2 s.t.x1 12x2 8x1+2x2 20 x1+x2 20 x1,x2 0 0 几点说明：几点说明：这两个约束是不这两个约束是不相容的相容的2023-2-738(2)2)目标无界目标无界例例7 7 maxZ=2x1+3x2 s.t.x1-x2 2-3x1+x2 3/2x1,x2 0约束构成无界区约束构成无界区域，目标函数的域，目标函数的等值线无限延伸等值线无限延伸2023-2-739(3)3)无穷多最优解无穷多最优解例例8 max8 maxZ Z=100=100 x1+200 x2 s.t.x1 12x2 8x1+2x2 20 x1,x2 0 0 这两条直线是这两条直线是平行的平行的2023-2-740n结论结论q解的几种情况：最优解（唯一和无穷），无最解的几种情况：最优解（唯一和无穷），无最优解（无解和目标无界）。优解（无解和目标无界）。qLP的可行解存在，则的可行解存在，则可行解域可行解域是一个是一个凸集凸集。凸集凸集不是凸集极点极点2023-2-741qLP有最优解，则有最优解，则最优解或最优解之一最优解或最优解之一必在必在可可行解域的凸集的顶点行解域的凸集的顶点上达到。上达到。q可行解域的一个顶点是最优解的充分条件是：可行解域的一个顶点是最优解的充分条件是：在这个顶点处每条棱均不改善。在这个顶点处每条棱均不改善。q从可行解域的一个顶点出发，沿着从可行解域的一个顶点出发，沿着改善棱改善棱前进，前进，有限次后会找到最优顶点。有限次后会找到最优顶点。2023-2-742Sk最优最优kk+1存在一个极点存在一个极点So否否极点极点Sk有改善棱否有改善棱否改善棱上有另一个极点否改善棱上有另一个极点否极点极点Sk+1(比比Sk改善改善)LP无解无解LP目标无界目标无界否否否否否否单纯形算法的几何叙述单纯形算法的几何叙述2023-2-7431.3 单纯形算法及扩展单纯形算法及扩展 1、LP标准型标准型2、解的概念、解的概念3、单纯形法、单纯形法4、单纯形法的进一步讨论、单纯形法的进一步讨论5、注意的问题、注意的问题2023-2-7441、线性规划的标准型、线性规划的标准型线性规划标准型任何形式的线性规划转化单纯形算法求解2023-2-745n线性规划的线性规划的标准型标准型定义定义max(min)Z=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn=b b1 1 a21x1+a22x2+a2nxn=b b2 2 am1x1+am2x2+amnxn=b bm m xj j 0(0(j=1,n)其中其中:bi02023-2-746.max(min)1tsxcZnjjj),2,1(0),2,1(1njxmibxajinjjij其中其中:bi00.maxXbAXtsCXZ其中其中:b0矩阵形式矩阵形式2023-2-747n如何化标准型？如何化标准型？q要求目标函数要求目标函数max q要求要求b非负非负q要求要求x非负非负q要求约束为等式约束要求约束为等式约束n举例举例(对例对例1）2023-2-748max Z=100 x1+250 x2s.t.x1 +x3 =12 x2 +x4 =8 x1+2x2 +x5=20 x1 x5 0 0 max Z=100 x1+250 x2 s.t.x1 12 x2 8 x1+2x2 20 x1，x2 0 对例对例1松弛变量松弛变量2023-2-749无约束321321321321321,0,52327.32minxxxxxxxxxxxxtsxxxZ例例9这需要减一个这需要减一个剩余变量剩余变量2023-2-7502、解的概念、解的概念n可行解可行解：满足约束条件的解。：满足约束条件的解。n最优解最优解：使目标达到最优的可行解。：使目标达到最优的可行解。n基矩阵基矩阵AB（许多参考书用记号：许多参考书用记号：B）n基变量基变量XBn非基变量非基变量XNn基解：基解：n基本可行解基本可行解：基解，且非负：基解，且非负 AB-1 b 0X=令非基令非基变量变量=02023-2-751 max Z=100 x1+250 x2 s.t.x1 12 x2 8 x1+2 x2 20 x1，x2 0 x1x2x28x1+2x2 20 x1 12(12,0)(12,4)(4,8)(0,8)(0,0)对例对例1可行解域可行解域最优解最优解2023-2-752 maxZ=CX s.t.LP的的标准标准型型 AX=b X 0 0XB=AB-1 b-AB-1 AN XNZ=CB AB-1 b+(CN-CB AB-1 AN)XN当当XN=0时，时，AB-1 b 0X=Z=CB AB-1 b(,)BBNNXA AbX2023-2-753 max Z=100 x1+250 x2 s.t.x1 +x3 =12 x2+x4 =8 x1+2 x2+x5=20 x1，x2 0 x1x2x28x1+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-2-754Sk最优最优kk+1存在一个极点存在一个极点So否否极点极点Sk有改善棱否有改善棱否改善棱上有另一个极点否改善棱上有另一个极点否极点极点Sk+1(比比Sk改善改善)LP无解无解LP目标无界目标无界否否否否否否单纯形算法单纯形算法STEP 1STEP 2STEP 3,4STEP 5单纯形法原理示意图单纯形法原理示意图顶点顶点4，最优解，最优解初始顶点初始顶点1顶点顶点2顶点顶点3其实，不必搜索可行域的每一个顶点，只要从一个顶点出发，沿着使目标函数改善的方向，到达下一个相邻的顶。如果相邻的所有顶点都不能改善目标函数，这个顶点就是最优顶点。用这样的搜索策略，可以大大减少搜索顶点的个数。按照这样的搜索策略建立的算法，叫做单纯形法(simplex algorithm)。它是由美国数学家G.B.丹齐克于1947年首先提出来的，是线性，是线性规划问题的数值求解的流行技术规划问题的数值求解的流行技术。目标函数改善目标函数改善目标函数改善目标函数改善目标函数改善目标函数改善单纯形法的基本思想单纯形法的基本思想n它的理论根据是：线性规划问题的可行域是它的理论根据是：线性规划问题的可行域是 n维向量空间维向量空间Rn中的中的多面凸集多面凸集，其最优值如果存在必在该，其最优值如果存在必在该凸集的某顶点凸集的某顶点处达到。处达到。顶点所对应的可行解称为基本可行解顶点所对应的可行解称为基本可行解。n单纯形法的基本思想是：先找出一个基本可行解，对它进单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照行鉴别，看是否是最优解；若不是，则按照一定法则一定法则转换转换到另一到另一改进的基本可行解改进的基本可行解,再鉴别；若仍不是，则再转换再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法换必能得出问题的最优解。如果问题无最优解也可用此法判别。判别。2023-2-7573、单纯形算法、单纯形算法-基本步骤基本步骤(对对max问题问题)n(1)给出初始单纯形表给出初始单纯形表,确定确定初始基本可行解初始基本可行解。（注意初始单。（注意初始单纯形表的特征）纯形表的特征）n(2)检验。检验非基变量检验数检验。检验非基变量检验数 是否全是否全 0。若是，停止，若是，停止，得到最优解；得到最优解；若否，转若否，转(3)n(3)选择选择进基变量进基变量。若非基变量检验数有。若非基变量检验数有 0，对应的系数对应的系数Pk全全 0，停止，原问题目标无界。停止，原问题目标无界。否则选择否则选择为进基变量，转为进基变量，转(4)jc000maxjjjjxccc2023-2-758定定xr为出基变量，为出基变量，为为主元，转主元，转(5)。由最小比值法求：由最小比值法求：(4)选择选择出基变量出基变量0000minrjrijijiabaabt0rja对应变量对应变量xr转转(2)(2)。(5)修正表格。以修正表格。以 为中心，换基迭代为中心，换基迭代0rja001000001初等行变换jmjrjjcaaa2023-2-759max Z=100 x1+250 x2 s.t.x1 +x3 =12 x2 +x4 =8 x1+2x2 +x5=20 x1 x5 0 0对例对例1这个标准型中有一个明显的这个标准型中有一个明显的基和基可行解基和基可行解2023-2-760基变量基变量初始基初始基可行解可行解初始单纯形表初始单纯形表250-(00+01+02)=250检验数：检验数：,NNNBBccc Accc A也可记作：2023-2-7612023-2-7622023-2-763 举例cj1100CBXBbx1x2x3x40 x34-21100 x421-101cj-zj1100加入松弛变量加入松弛变量12121212max24s.t 20Zxxxxxxxx、1212312412max2 4s.t +20Zxxxxxxxxxx、cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj1100所以把x3换出为非基变量，x2为换入变量即新的基变量。cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj11001x24-2110cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj11001x24-21100 x46-1011cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj11001x24-21100 x46-1011cj-zj30-10cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj11001x24-21100 x46-1011cj-zj30-10可以看出，x1的检验数为3，大于0，但是x1的系数列向量中的所有元素（-2,-1)T，都小于0，所以该题为无界解.加入松弛变量加入松弛变量举例cj3900CBXBbx1x2x3x40 x32113100 x44-1101cj-zj390012121212max39 321s.t.4,0zxxxxxxx x121231241234max39 3 21s.t.4,0zxxxxxxxxx x x xcj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-93x19/4101/4-3/49x225/4011/41/4cj-zj00-30此时所有的检验数都小于等于0，所以该解为最优解。最优解为X（9/4，25/4，0，0）T，Z*63非基变量非基变量x4的检验数的检验数0，那么该，那么该LP问题有问题有无穷多个最优解无穷多个最优解2023-2-772max Z=-2x1+x2 x3+5x4-22x5 s.t.x1+2x4+x5=6 x2+x4+4x5=3 x3+3x4+2x5 =10=10 x1,，x5 0例例102023-2-773练习练习 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 02023-2-774最优解最优解 x1=50 x2=250 x4 =50（松弛标量，表示原松弛标量，表示原料料A有有50个单位的剩余个单位的剩余）2023-2-775n注意：单纯形法中，注意：单纯形法中，1、每一步运算只能用矩阵初等行变换；、每一步运算只能用矩阵初等行变换；2、表中第、表中第b列的数总应保持非负（列的数总应保持非负（0）；）；3、当所有检验数均非正（、当所有检验数均非正（0）时，得到最优）时，得到最优单纯形表。单纯形表。2023-2-776几何概念几何概念代数概念代数概念约束直线约束直线满足一个等式约束的解满足一个等式约束的解约束半平面约束半平面满足一个不等式约束的解满足一个不等式约束的解约束半平面的交集：约束半平面的交集：凸多边形凸多边形满足一组不等式约束的解满足一组不等式约束的解约束直线的交点约束直线的交点基解基解可行域的极点可行域的极点基本可行解基本可行解目标函数等值线：目标函数等值线：一组平行线一组平行线 目标函数值等于一个常目标函数值等于一个常数的解数的解2023-2-7774、单纯形单纯形算算法法的进一步讨论的进一步讨论两阶段法和大两阶段法和大M法法前面讨论了在标准型中系数矩阵有单位前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实矩阵，很容易确定一组基可行解。在实际问题中有际问题中有些模型并不含有单位矩阵些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，为了得到一组基向量和初始基可行解，在约束条件的等式左端在约束条件的等式左端加一组虚拟变量加一组虚拟变量，得到一组基变量。这种人为加的变量称得到一组基变量。这种人为加的变量称为为人工变量人工变量，构成的可行基称为，构成的可行基称为人工基人工基，用用大大M法法或或两阶段法两阶段法求解，这种用人工求解，这种用人工变量作桥梁的求解方法称为变量作桥梁的求解方法称为人工变量法人工变量法。不存在单位不存在单位矩阵，如何构造矩阵，如何构造初始可行基？初始可行基？2023-2-778（1）两阶段法两阶段法原问题原问题 max z=cj xj j=1n xj 0j=1n aij xj=bi(i=1,2,m)4、单纯形单纯形算算法法的进一步讨论的进一步讨论两阶段法和大两阶段法和大M法法s.t.作辅助问题作辅助问题min w=yi i=1m xj，yi 0j=1n aij xj+yi=bi(i=1,2,m)s.t.yi人工变量人工变量（伪变量）（伪变量）2023-2-779 例例11 min z=4x1+x2+x32x1+x2+2x3=43x1+3x2+x3=3x1，x2，x3 0s.t.辅助问题辅助问题：min W=y1+y22x1+x2+2x3+y1=43x1+3x2+x3+y2=3x1，x3,y1,y2 0s.t.人工变量人工变量2023-2-780解题过程解题过程：u第一阶段：第一阶段：用单纯形法求解辅助问题。用单纯形法求解辅助问题。若求得辅助问题的目标函数若求得辅助问题的目标函数=0,也即人工也即人工变量都等于变量都等于0，则进入第二阶段。，则进入第二阶段。否则否则,原问题无可行解。原问题无可行解。u第二阶段：第二阶段：去掉人工变量，还原目标函数系数去掉人工变量，还原目标函数系数，此时，就能得到原问题的初始单纯形表。，此时，就能得到原问题的初始单纯形表。u 继续用单纯形法求解即可。继续用单纯形法求解即可。2023-2-781练习练习：max z=-3x1+x3x1+x2+x3 4-2x1+x2-x3 1 3x2+x3=9x1，x2，x3 0s.t.标准化标准化x1+x2+x3+x4 =4-2x1+x2-x3-x5=1 3x3+x3 =9x1,x5 0max z=-3x1+x32023-2-782辅助问题：辅助问题：min w=y1+y2x1+x2+x3+x4=4-2x1+x2-x3-x5+y1=1 3x3+x3 +y2=9x1,y2 0s.t.2023-2-783max z=-x1+2x2 x1+x2 2-x1+x2 1 x2 3 3x1,x2 0练习：练习：s.t.2023-2-784第第(1)阶段：阶段：min w=x6+x7 x1+x2-x3 +x6 =2-x1+x2 -x4 +x7=1 x2 +x5 =3x1 x7 0s.t.0,1 232 411 232131321321xxxxxxxxxxx123max 3zxxx例：671234123561371234567min 2 114 2 32 1,0 xxxxxxxxxxxxxxx x x x x x x构造第一阶段问题并求解构造第一阶段问题并求解解：解：用单纯形法求解用单纯形法求解两阶段法两阶段法（第一阶段、求第一阶段、求min min ）1 -2 1-4 1 2 -2 0 1 -6 1 3 0 0 0 x x1 x x2 x x3 0 x x4 11-1 x x6 3 -1 x x7 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 -1 x x4 x x5 x x6 0 11 0 3/2 1 1 0 -1 x x7 i i表表1jjzc -1 -2 1 1 -3 -1 x x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x x1 x x2 x x3 0 x x4 10-1 x x6 1 0 x x3 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 x x4 x x5 x x6i两阶段法两阶段法（第一阶段、求第一阶段、求min min ）表表21jjzc -5 4 -2 -1 -1 -1 x x7 3 0 0 0 1 0 -2 0 1 0 0 0 0 0 0 x x1 x x2 x x3 0 x x4 12 0 x x2 1 0 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 -1 0 0 -1 x x4 x x5 x x6i两阶段法两阶段法（第一阶段、求第一阶段、求min min ）表表3：最终单纯形表：最终单纯形表jjzc 不含人工不含人工变量且变量且=0=0两阶段法两阶段法 3 0 0 0 1 0 -2 0 1 3 -1 -1 x x1 x x2 x x3 0 x x4 12-1 x x2 1-1 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 x x4 x x5 ijjzc 1 0 0 0 -1两阶段法两阶段法 1 0 0 0 1 0 0 0 1 3 -1 -1 x x1 x x2 x x3 3 x x1 4-1 x x2 1-1 x x3 9 C i CB XB b 1/3 -2/3 0 -1 2/3 -4/3 0 0 x x4 x x5 i 0 0 0 -1/3 -1/3jjzc 914321xxx2023-2-792(2)例例11 min z=4x1+x2+x32x1+x2+2x3=43x1+3x2+x3=3x1，x2，x3 0s.t.建立一个新问题建立一个新问题2023-2-793min z=4x1+x2+x3+My1+My22x1+x2+2x3+y1=43x1+3x2+x3+y2=3x1，y2 0s.t.目标函数中添加“罚因子”M（M是任意大的正数）为人工变量系数，只要人工变量0，则目标函数不可能实现最优。判定无解条件判定无解条件：当进行到最优当进行到最优表时，仍有人表时，仍有人工变量在基中，工变量在基中，且且00，则说则说明原问题无可明原问题无可行解。行解。2023-2-794练习练习 ：max z=-3x1+x3x1+x2+x3 4-2x1+x2-x3 1 3x2+x3=9x1，x2，x3 0s.t.2023-2-795标准化标准化max z=-3x1+x3x1+x2+x3+x4 =4-2x1+x2-x3 -x5 =1 3x2+x3 =9x1 x7 0s.t.2023-2-796加入加入人工变量人工变量max z=-3x1+x3-My1 My2x1+x2+x3+x4=4-2x1+x2-x3-x5+y1 =1 3x3+x3 +y2=9x1 y2 0s.t.目标函数中目标函数中添加添加“罚因子罚因子”-M M为人工变量为人工变量系数，只要人系数，只要人工变量工变量00，则目标函数则目标函数不可能实现不可能实现最优最优。约束条件：约束条件：“”“”：则减去一个剩余变量后，再加一个人工变量：则减去一个剩余变量后，再加一个人工变量.“”：则加一个人工变量：则加一个人工变量.目标函数求最大：目标函数求最大：人工变量的系数为人工变量的系数为“M”M”，即罚因子，即罚因子.若线性规划问题有最优解则人工变量必为若线性规划问题有最优解则人工变量必为0.0.0,12334112.3max32131321321321xxxxxxxxxxxtsxxxz标准化标准化0,12334112.3max543213153214321321xxxxxxxxxxxxxxxtsxxxz7,1012334112.3max731653214321321jxxxxxxxxxxxxxtsxxxzj7,1012334112.3max73165321432176321jxxxxxxxxxxxxxtsMxMxxxxzj加入人工变量加入人工变量cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-211000-MX63-4120-110-MX71-2010001cj-zj3-6M-1+M-1+3M0-M0012367123412356137max3211433s.t.2101,7jzxxxMxMxxxxxxxxxxxxxxjcj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M00cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M00-1X31-2010001cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-1X31-2010001cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-2-1X31-2010001cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-2-1X31-2010001cj-zj1-1+M00-M01-3Mcj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3Mcj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M-1X210100-11-2cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M0X4123001-22-5-1X210100-11-2cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M0X4123001-22-5-1X210100-11-2-1X31-2010001cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M0X4123001-22-5-1X210100-11-2-1X31-2010001cj-zj1000-1-M+1-M-1cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M0X4123001-22-54-1X210100-11-2-1X31-2010001-cj-zj1000-1-M+1-M-1cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4123001-22-54-1X210100-11-2-1X31-2010001-cj-zj1000-1-M+1-M-13X141001/3-2/32/3-5/3cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4123001-22-54-1X210100-11-2-1X31-2010001-cj-zj1000-1-M+1-M-13X141001/3-2/32/3-5/3-1X210100-11-2cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4123001-22-54-1X210100-11-2-1X31-2010001-cj-zj1000-1-M+1-M-13X141001/3-2/32/3-5/3-1X210100-11-2-1X390012/3-4/34/3-7/3cj-zj000-1/3-1/3-M-1/4-M+2/32023-2-71145 5、单纯形法计算中的几个注意问题、单纯形法计算中的几个注意问题1)1)判定最优解定理：判定最优解定理：max z问题，非基变量检验数问题，非基变量检验数 0min z问题，非基变量检验数问题，非基变量检验数 0 2)2)退化解问题退化解问题3 3）计算中注意）计算中注意（1 1）标准型中有初始基本可行解，用单纯形法求解。）标准型中有初始基本可行解，用单纯形法求解。（2)2)标准型中没有初始基本可行解，用大标准型中没有初始基本可行解，用大M M法（或者用二阶法（或者用二阶段法）段法）加人工变量，使之构成单位基。加人工变量，使之构成单位基。2023-2-71154)4)解的几种情况：解的几种情况：唯一解唯一解:最优表中非基变量检验数最优表中非基变量检验数0(0(max)max)。无穷多最优解无穷多最优解:最优表中最优表中非基变量检验数非基变量检验数有为有为0 0者。者。无可行解无可行解:最优表中人工变量在基中，且不等于最优表中人工变量在基中，且不等于0 0。（用大。（用大M M法或两阶段法判别）法或两阶段法判别）目标无界：存在进基变量，其对应的系数均目标无界：存在进基变量，其对应的系数均 0。2023-2-71161.4 对偶线性规划Dual linear programming,DLP1 1、对偶问题的建立、对偶问题的建立2 2、对偶规划性质、对偶规划性质3 3、利用、利用LPLP的最优表的最优表求求DLPDLP的最优解的最优解4 4、经济解释、经济解释5 5、对偶单纯形算法、对偶单纯形算法1954年美国数学家年美国数学家C.莱姆基莱姆基提出对偶单纯形法提出对偶单纯形法(Dual Simplex Method)。实例：实例：某家电厂利用现有资源生产两种产品，某家电厂利用现有资源生产两种产品，有关数据如下表：有关数据如下表：设备设备A 设备设备B调试工序调试工序C利润（元）利润（元）0612521115时时24时时 5时时产品产品产品产品D如何安排生产，如何安排生产，使获利最多使获利最多？厂厂家家设设 产量产量 产量产量1x2x1221212121max 2 0+5156224 5,0 zxxxxxxs.t.xxx x若厂长决定不生产甲和乙型产品，决定若厂长决定不生产甲和乙型产品，决定出租机器出租机器用于接受外加工，只收加工费，用于接受外加工，只收加工费，那么那么3 3种设备的机时如何定价才是最佳决种设备的机时如何定价才是最佳决策策？设：设备设：设备A A 元时元时 设备设备B B 元时元时 调试工序调试工序 元时元时1y2y3y收收购购出让代价应不低于用出让代价应不低于用同等数量的资源自己同等数量的资源自己生产的利润。生产的利润。付出的代价最付出的代价最小，且对方能小，且对方能接受。接受。厂厂家家 设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时D厂家能接受的条件：厂家能接受的条件：收购方的意愿：收购方的意愿：32152415minyyyw单位产品单位产品:出租出租收入不低于收入不低于2 2元元单位产品单位产品:出租收出租收入不低于入不低于1 1元元出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。1252632132yyyyy厂厂家家0,5 2426 155 2max212121221xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32152415minyyyw对对偶偶问问题题原原问问题题收收购购厂厂家家一对对偶问题一对对偶问题2023-2-7122