南京-应用运筹学-线性规划-1.ppt

Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,*,南京大学,周 晶,教授,jzhou,运筹 学,问 题？,什么是运筹学？,为什么要学习运筹学？,要学习哪些内容？,什么是运筹学？,运筹帷幄，决策千里,作为一门学科诞生于,20,世纪,30,年代末期。运筹学一词在英国称为,operational research,，在美国称为,operations research,，缩写为,O.R.,。,在,大英百科全书,中，“运筹学是一门,应用于管理有组织系统的科学,”,，,“,运筹学为掌握这类系统的人提供决策目标和数量分析的工具,”,。,朴素的运筹思想,都江堰水利工程,战国时期（大约公元前,250,年）川西太守李冰父子主持修建。其目标是：利用岷江上游的水资源灌溉川西平原。追求的效益还有防洪与航运。其总体构思是系统思想的杰出运用,。,丁谓的皇宫修复工程,北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、生产、运输及废墟物的处理用,“,一沟三用,”,巧妙地解决了。,田忌赛马,齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负,1000,金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：,齐王 上 中 下,田忌 下 上 中,最终净胜一局，赢得,1000,金。,运筹学的三大来源,军事,运筹帷幄、决策千里,第二次世界大战,经济,莱昂惕夫的投入产出模型,管理,著名经济学家西蒙有一句名言：“管理就是决策”,鲍德西（,Bawdsey,）,雷达站的研究（,1935,年）,1935,年，英国科学家,R.Watson-Wart,发明了雷达。丘吉尔命令在英国东海岸的,Bawdsey,建立了一个秘密雷达站。当时，德国已拥有一支强大的空军，起飞,17,分钟即到达英国本土。在如此短的时间内，如何预警和拦截成为一大难题。,1939,年由曼彻斯特大学物理学家、英国战斗机司令部顾问、战后获得诺贝尔奖金的,P.M.S.Blackett,为首，组织了一个小组，代号“,Blackett,马戏团”。这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官、一名测量员。,研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“,Blackett,马戏团”在秘密报告中使用了“,Operational Research”,，,即“运筹学”。,大西洋反潜战（,1942,年）,1942,年，美国大西洋舰队反潜战官员,W.D.Baker,舰长请求成立反潜战运筹组，麻省理工学院的物理学家,P.W.Morse,被请来担任计划与监督。,Morse,出色的工作之一，是协助英国打破了德国对英吉利海峡的封锁。,1941-1942,年，德国潜艇严密封锁了英吉利海峡，企图切断英国的“生命线”。海军几次反封锁，均不成功。应英国要求，美国派,Morse,率领一个小组去协助。,Morse,经过多方实地考察，最后提出了两条重要建议：,将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由,100,米左右改为,25,米左右。即当潜艇刚下潜时攻击效果最佳。,(,提高效率,4-7,倍,),运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（,25%,下降到,10%,）,管理与运筹学,泰勒的科学管理方法,对工人提出科学的操作方法,（时间动作研究）,对工人进行科学的选择、培训和提高（能力与工作相适应）,制定科学的工艺流程，并以文件的形式加以固定和推广（工作定额与标准化）,使管理和劳动相分离（计划与执行分离）,在工资制度上实行差别计件制（差别计件付酬制）,各种管理科学学派,科学管理原理,社会技术系统学派,行为科学学派,人际关系行为学派,管理过程学派,社会合作系统学派,决策理论学派,沟通信息学派,管理科学学派,经验案例学派,数理学派,系统管理学派,经理角色学派,群体行为学派,战略管理 创新管理 知识管理,决策制定,主体（管理者）,管理者的多重角色,-,认可并奖励业绩,-,不断完善个人管理技能,-,给予指导建议,-,不断提出反馈,-,员工发展,-,构建有效团队,-,倾听,-,调解冲突,-,设定富于挑战但可以,达到的业绩标准,-,提供及时精确的信息,-,控制质量,-,倡导变化,-,影响高层领导的决策,-,争取资源实现团队目标,-,实现经营目标,-,满足客户的需要,-,明确阐述目标,-,全盘考虑,-,计划资源的,合理利用,灵活性,控制,公司外部的重点,公司内部的重点,$,教练员,创新者,促导者,经纪人,监理者,生产者,协调员,指挥者,激励,适应,政策,目标,决策制定,决策环境,不确定性程度：确定、风险、不确定,可重复性程度：程序、非程序,人员参与程度：个体、群体,主体价值判断：最优、满意、合理,决策制定,决策过程,识别问题,方案执行,观察,方案选择,方案评价,备择方案,理解问题,设定目标,解决问题周期,反馈,典型的定量决策问题,问题类型,典型问题,预 测,财 务,人力资源,时 序,资源配置,设备更新,库存控制,选 址,项目规划,排队问题,对产品的需求有多大，类别如何，利润影响？,需要多少资金，从何处得到，成本有多大？,需要多少人员，应有何技能，留用多长时间？,什么工作最重要，工作顺序如何安排？,需要什么资源，是否短缺，如何优先获得？,设备运转如何，可靠性如何，何时更新？,合理库存量为多少，订货的最佳批量和周期？,运作的最佳场所在何处，需要什么设施？,项目合理的作业时间为多少，资源如何利用？,队列多长，提供多少个服务台，服务水平？,装箱问题,已知：两种货物装葙,每种货物装葙利润,体积限制,重量限制,问题,:,两种货物各多少箱,?,可使获得利润最大？,(,箱数不能为分数,),OR,航空公司的问题,该公司要在郊区商业中心内设一个订票服务处。旅客订票时可以用电话与服务处联系。,OR,公司想知道，为了满足订票业务的需要，应该安装多少条电话线路为宜。显然，电话机和雇员的费用随电话线路的增设而变化。该公司希望对若干条不同线路方案的服务水平加以对比。尤其是公司要设法确定所有线路被占用的时间百分比，以及占先的平均时间长度。,经济的定货量问题,萨拇,.,塔龙是某闹市区的一家工装裤零售店的主人，他对于尺码短缺的裤子应该进多少货常常感到为难。他决定采用科学的方法来补充库存，以避免因存货短缺而脱销。先假定他出售某种特殊尺码裤子的销售量每周为,M,件，为简便起见，还假定这个销售是固定的。那么如果库存量为,kM,件，则库存恰好在,k,周内售完。又假设,M,在整个时期内是不变的，因而是补充定货可以定期进行。要决策的问题是确定最经济的定货量。,A,2,B,7,C,20,D,12,1,2,3,4,结点编号,作业,作业长度,最早开工时刻,最迟,开工时刻,最早完工时刻,最迟,完工时刻,时差,关键作业,i,j,tij,TES,TLS,TEF,TLF,S,1,2,A,2,0,0,2,2,0,A,2,3,B,7,2,3,9,10,1,2,4,C,20,2,2,22,22,0,C,3,4,D,12,9,10,21,22,1,0,2,2,9,2,22,9,21,0,2,3,10,10,22,2,22,网络计划,白色表示作业长度,tij,，,红色表示最早,TES,和,TEF,，,绿色表示最迟,TLS,和,TLF,秘书问题,瓦特,.,威洛比是一家从事经济分析和预测的咨询公司,.,这家公司的总经理凯,.,塞拉女士想雇佣一位新的事务秘书,正大算请职业介绍所推荐适当的人选同他会面。根据过去的经验，她自信能凭面谈即可断定求职者在受雇后的表现是极好的、好的、还是一般的。她给三种人以相应的分数：极好的为,3,分，好的为,2,分，一般为,1,分。一往的经验还使她相信，会见极好的候选人的概率为,0.2,，会见好的候选人的概率为,0.5,，而会见一般的候选人的概率为,0.3,。,T0.2,F0.3,G0.5,继续,继续,停止,T0.2,F0.3,G0.5,继续,T0.2,F0.3,停止,G0.5,停止,继续,停止,停止,1,2,3,3,3,2,2,停止,停止,T,极好,F,一般,G,好的,定量分析的过程,定性分析,定量分析的前奏应当是一个彻底的定性分析,表达问题,列出表达问题的基本要素：决策变量、不可控量、限制条件等；,建立模型,列出表达这些要素之间关系的数学方程式,求解模型与分析,运用算法求解所构建的模型得到最佳方案或满意方案,对输入数据和模型结构作灵敏度分析,执行决定或修改模型,在实际应用过程中不断完善模型,定量分析的工具,模型,模型：把需要解决的决策问题，通过分析其外部影响因素和内部的条件变量，用一个逻辑的或数学的表达式，从整体上说明它们之间的结构关系。,代表一种现实情况,经过简化只保留相关的部分,用模型的特性代表现实情况中的 特性,P=N,(S-C),利润销售量,（价格单位成本）,建立模型的重要性,建立模型是运筹学方法的精髓,建立模型有助于我们把决策问题所遇到的复杂性和可能的不确定性，转变为适于综合分析的逻辑结构；,模型是一种媒介，借以对现实世界作出正确的认识。,模型是现实的近似表达，要能抓住决策问题的关键，在真实性和可用性之间取得适当的平衡。,典型的定量分析模型,解决方法,线性规划,目标规划,网络分析,决策分析,库存模型,排队论,在线性目标和约束条件下取得最优结果,在相对立的目标间寻得妥协和满意解,用各种活动和事件的网络排列来说明项目进度,确定、分析和比较备择方案并决定其实施,把库存的成本降至最低,分析正在等待的队列特点,定量分析的特点,定量分析：,管理问题的理性描述和最优解,分析方法：,数学的、概率的和统计的方法,定量优势：,可靠数据为依据保证结果客观,定量局限：,实际问题无法完全地理性描述,方法改进：,数据分析与经验判断有机结合,组织内存在的问题,定量分析,评价,定性分析,决策,运筹学的定义,定义1：为决策机构在对其控制下业务活动进行决策时，提供以定量化为基础的科学方法。,定义2：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。,定义,3:,运筹学是应用系统的、科学的、数学分析的方法，通过 建模、检验和求解数学模型而获得最优决策的科学。,运筹学的研究对象,机器、设备、网络、乃至系统的运用问题，即如何提高运作效率；,拥挤现象：交通路口的车辆排队、服务热线、飞机着陆、船舶进港、网络；,竞争现象：人与自然的对抗、人与人的对抗；,运筹学的重要分支,运用分析理论,数学规划（又包含线性规划、非线性规划、整数规划、目标规划、动态规划等）,图与网络流,随机服务系统理论,排队论,库存论,竞争决策理论,决策论：人与自然的较量,对策论（博弈论）：人与人的较量,运筹学的主要研究分支,线性规划,：,模型简单，是运筹学中应用最为广泛的一个分支。,非线性规划,：在各类工程的优化设计中应用广泛。,动态规划,：研究多阶段决策过程最优化的运筹学分支。,图与网络流,：利用图来表示研究对象及其联系，并用图论方法来研究网络结构和流量的优化分析。,决策论,：研究决策过程中关于方案目标选取和度量、效用值计算、选取最优方案和策略等的有关科学理论。,对策论（博弈论）,：用于研究具有对抗局势的模型。,存贮论：,研究最优存贮策略的理论和方法。,排队论,：对排队系统的研究理论和方法。,运筹学主要分支简介,数学规划,Mathematical Programming,一般数学描述,目标函数或约束函数都是线性的,则是线性规划,(,Linear Programming);,若其中至少有一个是非线性的,为非线性规划(,Nonlinear Programming),;,若其中至少有一个变量要求为整数,则为整数规划,(,Integer Programming),.,数学规划,动态规划,(,Dynamic Programming),解决多阶段决策过程最优化问题的一种方法,可用于解决最优路径问题、生产计划与库存、投资决策等实际问题。,图与网络流,Graph theory,决策论（,decision),著名经济学家西蒙有一句名言：“管理就是决策”。,“决策”一词本身是一个广义的概念，后续课程将介绍在不确定或随机环境下的决策分析方法。,应用背景：产品开发决策问题、风险投资决策问题、开设连锁店问题等等,博弈论（,Game Theory),排队论（,Queuing Theory,银行、医院、机场跑道、港口码头、理发店、通信设备、交通路口等等的排队现象；,排队论又叫做随机服务系统理论。它的研究目的是要回答如何改进服务机构、或组织被服务的对象，使得某种指标达到最优的问题。比如一个港口应该有多少个码头，一个工厂应该有多少维修人员等。,库存论,(Inventory Theory),存储物品的现象是为了解决供应（生产）与需求（消费）之间的不协调的一种措施；,由此带来一些需要决策的问题：库存量、进货量（如报童问题）、补货的时间等等决策量。,现在也是供应链管理研究中的热点问题。,真实系统,系统分析,问题描述,模型建立与修改,模型求解与检验,结果分析与实施,数据准备,运筹学分析的步骤,本课程的主要内容,线性规划,整数规划,(,线性,),图论,决策论,博弈论,第一章 线性规划,Linear Programming,运筹学中应用最广泛的方法之一,运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的,解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大,发展历程,原始的数学规划模型早在1759年和1874年就分别由经济学家,Quesnay,和,Walras,提出。,康托洛维奇于1939年出版了“生产组织与计划中的数学方法”一书，对一个工厂的生产计划任务建立了线性规划模型，并提出“解乘数法”。,冯诺伊曼,(,Von,Neuman,),和摩根斯坦,(Morgenstern)1944,年发表的,对策论与经济行为,涉及与线性规划等价的对策问题及线性规划对偶理论,G B Dantzig1947,年研究美国空军资源的优化配置时提出了线性规划的通用解法单纯型法。50年代初成功地用电子计算机求解线性规划问题。,从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人,(40%),从事过与线性规划有关的研究工作，其中著名的还有,Simon,，,Samullson,，,Leontief,，,Arrow,，,Miller,等,发展历程,1.1,线性规划的数学模型,A B,备用资源,煤,1 2 30,劳动力,3 2 60,仓库,0 2 24,利润,40 50,例,1,、生产计划问题,问产品,A,B,各生产多少,可获最大利润,?,x,1,+,2x,2,30,3x,1,+,2x,2,60,2x,2,24,x,1,，,x,2,0,max Z=,40 x,1,+,50 x,2,解,:,设产品,A,B,产量分别为变量,x,1,，,x,2,例,2,求：最低成本的原料混合方案,原料,A B,每单位成本,1 4 1 0 2,2 6 1 2 5,3 1 7 1 6,4 2 5 3 8,每单位添,加剂中维生,12 14 8,素最低含量,解：设每单位添加剂中原料,i,的用量为,x,i,(,i,=1,2,3,4),minZ,=,2x,1,+,5x,2,+,6x,3,+8x,4,4x,1,+,6x,2,+,x,3,+2x,4,12,x,1,+,x,2,+,7x,3,+5x,4,14,2,x,2,+,x,3,+3x,4,8,x,i,0(,i,=,1,4,),要解决的问题的目标可以用数值指标反映,对于要实现的目标有多种方案可选择,有影响决策的若干约束条件,线性规划问题的特征,线性规划模型的要素,决策变量：向量,(,x,1,x,n,),T,决策人要考虑和控制的因素非负,约束条件：线性等式或不等式,目标函数：,Z=(,x,1,x,n,),线性式，求,Z,极大或极小,一般式,Max(min)Z=c,1,x,1,+c,2,x,2,+,c,n,x,n,a,11,x,1,+a,12,x,2,+a,1n,x,n,(=,)b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,(=,)b,2,a,m1,x,1,+a,m2,x,2,+,a,mn,x,n,(=,),b,m,x,j,()0,j=1,2,n,56,线性规划问题解的定义,Max Z=CX,AX=b (1),X,0,(2),定义1,：满足所有约束条件(1)、(2)的解,X=(,X,1,X,n,),T,称为,LP,问题的,可行解,，全部可行解的集合称为,可行域。,定义2,：使目标函数达到最优值的可行解称为,LP,问题的,最优解,.,(,LP),1.3,线性规划的图解法,max z=x,1,+3x,2,s.t.x,1,+x,2,6,-x,1,+2x,2,8,x,1,0,x,2,0,可行域,目标函数等值线,最优解,6,4,-8,6,0,x,1,x,2,例,1,、,max Z=40 x,1,+50 x,2,x,1,+2x,2,30,3x,1,+2x,2,60,2x,2,24,x,1,x,2,0,解：,(1),、确定可行域,x,1,0,x,1,=0,(,纵,),x,2,0,x,2,=0,(,横,),x,1,+2x,2,30,x,1,+2x,2,=30,(0,15)(30,0),0,10,20,30,x,2,D,A,B,C,3x,1,+2x,2,=60,(0,30)(20,0),2x,2,=24,20,30,10,x,1,(2),、求最优解,解：,x,*,=(15,7.5),Z,max,=975,Z=40 x,1,+50 x,2,0=40 x,1,+50 x,2,(0,0),，,(10,-8),C,点：,x,1,+2x,2,=30,3,x,1,+2x,2,=60,0,20,30,10,10,20,30,x,1,x,2,D,A,B,C,例,2,、,max Z=40 x,1,+80 x,2,x,1,+2x,2,30,3x,1,+2x,2,60,2x,2,24,x,1,x,2,0,0,Z=40 x,1,+80 x,2,=0,x,1,+2x,2,=30,D,A,B,C,x,2,x,1,最优解：,BC,线段,B,点,C,点,x,(1),=(6,12),x,(2),=(15,7.5),x=,x,(1),+(1-,)x,(2),(,0,1,),求解,x,1,=6,+,+(1-,)15,x,2,=12,+,+(1-,)7.5,x,1,=15-9,x,2,=7.5+4.5,(,0,1,),X=,+(1-,),Max Z=1200,x,1,6 15,x,2,12 7.5,无界,无有限最优解,例,3,、,max Z=2x,1,+4x,2,2x,1,+x,2,8,-2x,1,+x,2,2,x,1,x,2,0,Z=0,2x,1,+x,2,=8,-2x,1,+x,2,=2,8,2,4,6,x,2,4,0,x,1,例,4,、,max Z=3x,1,+2x,2,-x,1,-x,2,1,x,1,x,2,0,无解,无可行解,-1,X,2,-1,X,1,0,线性规划的可行域及最优解的可能结果图示：,(a),可行域封闭，唯一最优解,(a),可行域封闭，多个最优解,(d),可行域开放，多个最优解,(e),可行域开放，目标函数无界,(f),可行域为空集,(c),可行域开放，唯一最优解,总结,唯一解,无穷多解,无有限最优解,无可行解,有解,无解,(1),、可行域为凸多边形。,(2),、若有最优解，一定可在可行域的顶点达到。,X,(1),X,(2),凸多边形,凹多边形,X,(1),X,(2),1.4,线性规划解的几何特性,凸集及其性质,定义,1,：凸集,D,是,n,维欧氏空间的一个集合,X,(1),X,(2),D,若任一个满足,X=,X,(1),+(1-,)X,(2),(,0,1,),有,X,D,凸集中任意两点的连线仍然属于该集合。,凸集图例,(a),凸集,(b),凸集,(c),凸集,(a),非凸集,(b),非凸集,(c),非凸集,X,(1),X,(2),X,(k),是,n,维欧氏空间中的,k,个点，若有一组数,1,2,k,满足,0,i,1,(i=1,k,),定义,2,i,=1,k,i=1,有点,X=,1,X,(1),+,k,X,(k),则称点,X,为,X,(1),X,(2),X,(k),的凸组合。,凸组合,凸集,D,点,X,D,，,若找不到两个不同的点,X,(1),X,(2),D,使得,X=,X,(1),+(1-),X,(2),(0,1,),则称,X,为,D,的顶点。,定义,3,顶点,1.5 LP,问题的基本解,Max Z=CX,AX,=b,X,0,A,m,n,满秩,X,=(x,1,x,n,),T,a,11,a,1m,a,1m+1,a,1n,a,21,a,2m,a,2m+1,a,2n,a,m1,a,mm,a,mm+1,a,mn,P,1,P,m,P,m+1,P,n,B,N,(m,n)r(A)=m,至少有一个,m,阶子式不为,0,定义,4,：基,(,基阵,),由,A,中一个子矩阵,B,是可逆矩阵，则方阵,B,称为,LP,问题的一个基。,A=,(,P,1,P,m,P,m+1,P,n,)=(,BN,),基向量 非基向量,X=,(,x,1,x,m,x,m+1,x,n,),T,=(,X,B,X,N,),T,基变量 非基变量,X,B,X,N,基,、,基变量,、,非基变量,=,=,目标函数,约束条件,行列式,0,基,右边常数,AX=b,的求解,A=(BN),X=(X,B,X,N,),T,X,B,X,N,(BN)=b,BX,B,+NX,N,=b,BX,B,=b-NX,N,X,B,=B,-1,b-B,-1,N X,N,定义,4,：,基本解,对应于基,B,，,X=,为,AX=b,的一个解。,B,-1,b,0,定义,5,：,基本可行解,基,B,，基本解,X=,若,B,-1,b,0,，称基,B,为,可行基,。若其基本解是最优解，成为,最优基本解,，相应的基为,最优基,B,-1,b,0,基本解中最多有,m,个非零分量。,基本解的数目不超过,C,n,m,=,个。,n!,m!(n-m)!,例：,基变量,x,1,、,x,2,、,x,3,，非基变量,x,4,、,x,5,、,x,6,基本解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,5,，,3,，,1,，,0,，,0,，,0,）,是基本可行解，表示可行域的一个极点。,目标函数值为：,z=20,基变量,x,1,、,x,2,、,x,4,，非基变量,x,3,、,x,5,、,x,6,基本解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,27/5,，,12/5,，,0,，,2/5,，,0,，,0,）,是基本可行解，表示可行域的一个极点。,目标函数值为：,z=18,基变量,x,1,、,x,2,、,x,5,，非基变量,x,3,、,x,4,、,x,6,基本解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,6,，,3,，,0,，,0,，,-3,，,0,）,是基本解，但不是可行解，不是一个极点。,基变量,x,1,、,x,2,、,x,6,，非基变量,x,3,、,x,4,、,x,5,基本解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,3,，,4,，,0,，,0,，,0,，,4,）,是基本可行解，表示可行域的一个极点。,目标函数值为：,z=18,基变量,x,2,、,x,3,、,x,4,，非基变量,x,1,、,x,5,、,x,6,基本解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,0,，,21/2,，,27/2,，,-30,，,0,，,0,）,是基本解，但不是可行解。,基变量,x,1,、,x,2,、,x,3,，非基变量,x,4,、,x,5,、,x,6,基本解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,0,，,3,，,6,，,0,，,15,，,0,）,是基本可行解，表示可行域的一个极点。,目标函数值为：,z=15,基变量,x,1,、,x,2,、,x,3,，非基变量,x,4,、,x,5,、,x,6,基本解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,0,，,11/2,，,-3/2,，,0,，,0,，,10,）,是基本解但不是可行解。,(,LP),问题的基本可行解 可行域的顶点。,若,(LP),问题有最优解，必定可以在基本可行解,(,顶点,),达到。,LP,问题解的性质,若,(LP),问题有可行解，则可行解集,(,可行域,),是凸集,(,可能有界，也可能无界,),，有有限个顶点。,基本解、基本可行解与顶点,max z=x,1,+3x,2,D,s.t.x,1,+x,2,+x,3,=6 B,-x,1,+2x,2,+x,4,=8 x,4,=0 C x,3,=0,x,1,x,2,x,3,x,4,0 x,1,=0,E O x,2,=0 A,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：凸多边形,满足一组不等式约束的解,约束直线的交点,基本解,可行域的极点,基本可行解,目标函数等值线：,一组平行线,目标函数值等于一个常数的解,定理,2,：,LP,有最优解，必定可以在可行域,(,凸多面集,),的顶点得到。,定理,3,：可行域中点,X,是顶点,X,是基本可行解。,可行解,基本解,定理,1,：,LP,问题的可行域一定是凸集,(,凸多面集,),C,n,m,=,n!,m!(n-m)!,(m,40,选,x,2,从,0,，,x,1,=0,x,3,=30-2x,2,0,x,2,30,/,2,x,4,=60-2x,2,0,x,2,60,/,2,x,5,=24-2x,2,0,x,2,24,/,2,x,2,=min(,30,/,2,60,/,2,24,/,2,)=12,x,2,进基变量，,x,5,出基变量。,B,2,=(P,3,P,4,P,2,),Z=0+40 x,1,+50 x,2,x,3,+2x,2,=30-x,1,x,4,+2x,2,=60-3x,1,2x,2,=24-x,5,1,/,2,，,代入式，,Z=600 +40 x,1,-25x,5,x,3,=6 -x,1,+x,5,x,4,=,36-3x,1,+x,5,x,2,=12 -,1,/,2,x,5,令,x,1,=x,5,=0 X,(2),=(0,12,6,36,0),T,Z,(2),=600,(2),判断,40,0,X,(2),不是,。,(3),选,x,1,从,0,，,x,5,=0,x,3,=6-x,1,0,x,4,=,36-3x,1,0,x,2,=12,0,x,1,=min(,6,/,1,36,/,3,1,)=6,x,1,进基，,x,3,出基。,B,3,=(P,1,P,4,P,2,),Z=840-40 x,3,+15x,5,x,1,=6 -x,3,+x,5,x,4,=,18+3x,3,-2x,5,x,2,=12 -,1,/,2,x,5,令,x,3,=x,5,=0,X,(3),=(6,12,0,18,0),T,Z,(3),=840,(2),15,0,X,(3),不是,(3),选,x,5,从,0,，,x,3,=0,x,1,=6 +x,5,0,x,4,=,18 -2x,5,0,x,2,=12-,1,/,2,x,5,0,x,5,=min(,18,/,2,12,/,1/2,)=9,x,5,进基，,x,4,出基。,B,4,=(P,1,P,5,P,2,),Z=975-,35,/,2,x,3,-,15,/,2,x,4,x,1,=15+,1,/,2,x,3,-,1,/,2,x,4,x,5,=,9 +,3,/,2,x,3,-,1,/,2,x,4,x,2,=,15,/,2,-,3,/,4,x,3,+,x,4,令,x,3,=x,4,=0,X,(4),=(15,15,/,2,0,0,9),T,Z,(4),=975,0,(0,0),x,2,x,1,A,D,C,B,(0,12),(6,12),(15,7.5),三、单纯形表,c,1,c,2,c,m,c,m+1,c,m+k,c,n,C,B,X,B,B,-1,b,x,1,x,2,x,m,x,m+1,x,m+k,x,n,c,1,x,1,b,1,1 0,0 a,1m+1,a,1m+k,a,1n,c,2,x,2,b,2,0 1,0 a,2m+1,a,2m+k,a,2n,c,r,x,r,b,r,0 0,0 a,rm+1,a,rm+k,a,rn,c,m,x,m,b,m,0 0,1 a,mm+1,a,mm+k,a,nn,Z,0,0 0,0 ,m+1,m+k,n,例,1,Max Z=40 x,1,+50 x,2,x,1,+2x,2,+x,3,=30,3x,1,+2x,2,+x,4,=60,2x,2,+x,5,=24,x,1,x,5,0,40 50 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,30 1 2 1 0 0 15,0,x,4,60,3,2 0 1 0 30,0,x,5,24 0 (2)0 0 1 12,0 40 50 0 0 0,0,x,3,6 (1)0 1 0 -1 6,0,x,4,36 3 0 0 1 -1 12,50,x,2,12 0 1 0 0 1/2,600 40 0 0 0 -25,40,x,1,6 1 0 1 0 -1,0,x,4,18 0 0 -3 1 (2)9,50,x,2,12 0 1 0 0 1/2 24,840 0 0 -40 0 15,40,x,1,15 1 0 -1/2 1/2 0,0,x,5,9 0 0 -3/2 1/2 1,50,x,2,15/2 0 1 3/4 -1/4 0,本问题的最优解,X=(15,15/2,0,0,9),T,Z=975,40 50 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,975 0 0 -35/2 -15/2 0,例,2,max Z=,x,1,+2x,2,x,1,4,x,2,3,x,1,+2x,2,8,x,1,x,2,0,x,1,+x,3,=,4,x,2,+x,4,=,3,x,1,+2x,2,+x,5,=,8,x,1,x,5,0,1 2 0 0 0,C,B,X,B,b x,1,x,2,x,3,x,4,x,5,0,x,3,4 1 0 1 0 0,0,x,4,3 0 (1)0 1 0,0,x,5,8 1 2 0 0 1,0 1 2 0 0 0,0,x,3,4 1 0 1 0 0,2,x,2,3 0 1 0 1 0,0,x,5,2,(1)0 0 -2 1,(,接下表,),6 1 0 0 -2 0,1 2 0 0 0,C,B,X,B,b x,1,x,2,x,3,x,4,x,5,0,x,3,2 0 0 1 (2)-1,2,x,2,3 0 1 0 1 0,1,x,1,2 1 0 0 -2 1,8 0 0 0 0 -1,0,x,4,1 0 0 1/2 1 -1/2,2,x,2,2 0 1 -1/2 0 1/2,1,x,1,4,1 0 1 0 0,8 0 0 0 0 -1,X,(1),=,(2,3),Z,(1),=8,X,(2),=,(4,2),Z,(2),=8,无穷多解,全部解：,X,=+(1-),(0,1,),2 4,3 2,例,3,求,max Z=,x,1,-x,2,+x,3,3x,5,x,2,+x,3,-x,4,+2x,5,=,6,x,1,+2x,2,2x,4,=,5,2x,2,+x,4,+3x,5,+x,6,=,8,x,1,x,6,0,1 -1 1 0 -3 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,1,x,3,6 0 1 1 -1 2 0,1,x,1,5 1 2 0 -2 0 0,0,x,6,8 0 2 0 1 3 1,11 0 -4 0 3 -5 0,1,x,3,14 0 3 1 0 5 1,1,x,1,21 1 6 0 0 6 2,0,x,4,8,0 2 0 1 3 1,35 0 -10 0 0 -14 -3,例,4,max Z=10,x,1,+,12x,2,3x,1,+4x,2,6,4x,1,+x,2,2,3x,1,+2x,2,3,x,1,x,2,0,10 12 0 0 0,X,B,b,x,1,x,2,x,3,x,4,x,5,i,0,x,3,6 3 (4)1 0 0 3/2,0,x,4,2 4 1 0 1 0 2/1,0,x,5,3 3 2 0 0 1 3/2,0 10 12 0 0 0,12,x,2,3/2 3/4 1 1/4 0 0 2,0,x,4,1/2 13/4 0 -1/4 1 0 2/13,0,x,5,0,(3/2)0 -1/2 0 1 0,18 1 0 -3 0 0,12,x,2,3/2 0 1 1/2 0 -1/2,0,x,4,1/2 0 0 5/6 1 -13/6,10,x,1,0 1 0 -1/3 0 2/3,18 0 0 -8/3 0 -2/3,退化解,X,*,=(0,3/2,0,1/2,0),T,Z,max,=18,例,5,：,Max Z,=,4x,1,+x,2,-x,1,+x,2,2,x,1,4x,2,4,x,1,2x,2,8,x,1,x,2,0,4 1 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,2 -1 1 1 0 0,0,x,4,4 (1)-4 0 1 0,0 x,5,8 1 -2 0 0 1,0 4 1 0 0 0,0 x,3,6 0 -3 1 1 0,4 x,1,4 1 -4 0 1 0,0 x,5,4 0 (2)0 -1 1,16 0 17 0 -4 0,0,x,3,12 0 0 1 -1/2 3/2,4,x,1,12 1 0 0 -1 2,1,x,2,2 0 1 0 -1/2 1/2,50 0 0 0 9/2 -17/2,本问题无界。,x,1,x,2,O,Z=0,四、初始基本可行解的求法,(,一,),、大,M,法：,判定无解条件：当进行到最优表时，仍有人工变量在基中，且,0,，,则说明原问题无可行解。,例,1,：,Max Z,=,6x,1,+4x,2,2x,1,+3x,2,100,4x,1,+2x,2,120,x,1,=,14,x,2,22,x,1,x,2,0,Max Z,=,6x,1,+4x,2,2x,1,+3x,2,+x,3,=,100,4x,1,+2x,2,+x,4,=,120,x,1,=,14,x,2,-x,5,=,22,x,1,x,5,0,Max Z,=,6x,1,+4x,2,-Mx,6,-Mx,7,2x,1,+3x,2,+x,3,=,100,4x,1,+2x,2,+x,4,=,120,x,1,+x,6,=,14,x,2,-x,5,+x,7,=,22,x,1,x,7,0,6 4 0 0 0 -,M,-,M,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,X,6,X,7,0,X,3,100 2 3 1 0 0 0 0,0,X,4,120,4,2 0 1 0 0 0,-M X,6,14 (1)0 0 0 0 1 0,-M X,7,22 0 1 0 0 -1 0 1,-36,M,M,