应用运筹学-线性规划-1资料

1、徐薇南京大学工程管理(gunl)学院 运筹(ynchu) 学共一百九十三页什么是运筹学？为什么要学习运筹学？要学习哪些(nxi)内容？引言(ynyn)共一百九十三页什么(shn me)是运筹学运筹帷幄之中，决胜千里之外作为一门学科诞生于20世纪30年代末在英国称为Operational Research，在美国称为Operations Research，缩写为O.R.在大英百科全书中的定义：“运筹学是一门应用于管理有组织系统的科学，运筹学为掌握这类系统的人提供(tgng)决策目标和数量分析的工具”共一百九十三页什么(shn me)是运筹学在中国(zhn u)大百科全书中的定义：“用数学方法研究

2、经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”共一百九十三页什么(shn me)是运筹学运筹学的研究对象是各种系统；运筹学的研究目的(md)是实现系统的最优化，求得合理利用各种资源的最优方案；运筹学的研究方法是运用数学语言来描述实际系统，通过建立数学模型和优化技术求得系统运营的最优解；运筹学的研究动机是为决策者提供科学决策的依据。 共一百九十三页朴素的运筹思想 都江堰水利工程 战国时期（大约公元前250年）川西太守李冰父子主持修建。其目标是：利用岷江上游的水资源灌溉川西平原。同时(t

3、ngsh)还有助于防洪与航运。其总体构思是系统思想的杰出运用。运筹学发展(fzhn)背景共一百九十三页 都江堰由三大工程以及120多项配套工程组成：1.“鱼嘴”岷江分水工程：将岷江水有控制地引入内江。2.“飞沙堰”分洪排沙工程：将泥沙排入外江(wi jin)。3.“宝瓶口”引水工程：除沙后的江水引入水网干道。它们巧妙结合，完整而严密，相得益彰。两千多年来，这项工程一直发挥着巨大的效益，是我国最成功的水利工程。共一百九十三页 丁谓主持(zhch)的皇宫修复工程 北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与

4、汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、生产、运输及废墟物的处理用“一沟三用”巧妙地解决了。共一百九十三页 田忌赛马 齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导(zhdo)下，以以下安排： 齐王 上 中 下 田忌 下 上 中 最终净胜一局，赢得1000金。共一百九十三页起源于二次大战的一门新兴学科与作战相关雷达的设置(shzh)运输船队的护航反潜作战中深水炸弹的深度飞行员的编组军事物资的存储等运筹学的起源(qyun)共一百九十三页 鲍德西（Ba

5、wdsey）雷达站的研究 1935年，英国科学家R.Watson-Wart发明了雷达。丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站。当时，德国已拥有一支强大的空军，起飞(qfi)17分钟即到达英国本土。在如此短的时间内，如何预警和拦截成为一大难题。战争(zhnzhng)背后的数学奥秘共一百九十三页 1939年由曼彻斯特大学物理学家、英国战斗机司令部顾问、战后获得诺贝尔奖的P. M. S. Blackett 为首，组织了一个小组，代号“Blackett马戏团”。这个小组包括：三名心理学家、两名数学家、两名应用数学家、一名天文(tinwn)物理学家、一名普通物理学家、一名海军军官、一

6、名陆军军官、一名测量员。战争(zhnzhng)背后的数学奥秘共一百九十三页 研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调(xitio)，作了系统的研究，并获得成功。 “Blackett马戏团”在秘密报告中首次使用了“Operational Research”，即“运筹学”。战争背后的数学(shxu)奥秘共一百九十三页 精计算，深水炸弹弱变强 1941-1942年，德国潜艇严密封锁了英吉利海峡，企图(qt)切断英国的“生命线”。海军几次反封锁，均不成功。应英国要求，美国派麻省理工学院的物理学家P.W.Mors

7、e担任计划与监督。率领一个小组去协助。Morse经过多方实地考察和分析计算，最后提出了两条重要建议：战争背后(bihu)的数学奥秘共一百九十三页 将反潜(fnqin)攻击由反潜(fnqin)潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率4-7倍) 运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（25%下降到10%） 战争背后(bihu)的数学奥秘共一百九十三页战后在经济、管理部门和学校及科研单位继续开展研究1948年英国首先成立战问题运筹学俱乐部1952年美国成立运筹学会1952年，

8、Morse 和 Kimball出版运筹学方法1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于1999年8月组织(zzh)了第15届大会运筹学的发展(fzhn)共一百九十三页 定量分析(dnglingfnx)的过程定性分析定量分析(dnglingfnx)的前奏应当是一个彻底的定性分析表达问题列出表达问题的基本要素：决策变量、限制条件等建立模型列出表达这些要素之间关系的数学方程式求解模型与分析运用算法求解所构建的模型得到最佳方案或满意方案对输入数据和模型结构作灵敏度分析执行决定或修改模型在实际应用过程中不断完善模型共一百九十三页 建立(jinl)模型的重要性建立模型

9、是运筹学方法的精髓建立模型有助于我们把决策问题所遇到(y do)的复杂性和可能的不确定性，转变为适于综合分析的逻辑结构；模型是一种媒介，借以对现实世界作出正确的认识。模型是现实的近似表达，要能抓住决策问题的关键，在真实性和可用性之间取得适当的平衡共一百九十三页问题类型典型问题 预 测 财 务 人力资源 时 序 资源配置 设备更新 库存控制 选 址 项目规划 排队问题对产品的需求有多大，类别如何，利润影响？需要多少资金，从何处得到，成本有多大？需要多少人员，应有何技能，留用多长时间？什么工作最重要，工作顺序如何安排？需要什么资源，是否短缺，如何优先获得？设备运转如何，可靠性如何，何时更新？合理库

10、存量为多少，订货的最佳批量和周期？运作的最佳场所在何处，需要什么设施？项目合理的作业时间为多少，资源如何利用？队列多长，提供多少个服务台，服务水平？企业(qy)中的定量决策问题共一百九十三页 现实(xinsh)中的优化问题物流网络的设计优化；供应链中的多级存储系统的运行优化；港口集装箱调度的优化；制造(zhzo)系统的生产计划与调度优化；复杂工程系统设计的优化；复杂过程控制系统的参数优化；投资组合优化问题；。共一百九十三页 物流网络(wnglu)的设计优化随着我国物流业的快速发展，不同类型的物流系统的设计，物流园区的设计有很大的实际需求。这些系统设计中有很多优化问题，如：多个仓库位置的选定仓库

11、容量的确定(qudng)运输方式和运输工具的选择车辆路径的规划。共一百九十三页 供应链的运行(ynxng)优化供应链的运行(ynxng)中也有很多优化问题，如：分销网络中多级库存系统的库存补充计划安全库存的分级配置优化考虑缺货或事故情况的处理顺应价格波动的存储计划车辆运输计划和路径优化。共一百九十三页 港口(gngku)集装箱调度的优化现代化港口和铁路集装箱中心站的集装箱运输中也有很多优化问题，如：船舶的泊次计划集装箱的装/卸载计划堆场的空间计划车辆的作业计划货场(hu chn)的堆放计划码头起重机的调度计划。共一百九十三页金融(jnrng)投资问题投资组合问题(Portfolio)已知某三支

12、股票的价格近十年每年(minin)的增长情况,以及500种股票指数变化情况, 假设你现在有一笔资金要进行投资, 并期望年利率至少达到15%, 那么你应该如何投资?。 共一百九十三页航空公司的订票热线(rxin)问题该公司要在郊区商业中心内设一个订票服务处，旅客订票时可以用电话与服务处联系。OR公司想知道，为了满足订票业务的需要，应该安装多少条电话线路为宜？该公司希望对若干条不同线路方案的服务水平加以对比，尤其是公司要设法确定所有线路被占用(zhn yn)的时间百分比，以及平均等待时间长度。共一百九十三页运筹学主要分支(fnzh)简介共一百九十三页数学(shxu)规划Mathematical P

13、rogramming一般数学描述(mio sh) 目标函数或约束函数都是线性的，则是线性规划(Linear Programming)；若其中至少有一个是非线性的，为非线性规划(Nonlinear Programming)；若其中至少有一个变量要求为整数，则为整数规划(Integer Programming)。共一百九十三页数学(shxu)规划动态规划(Dynamic Programming)解决多阶段决策过程最优化问题的一种方法可用于解决最优路径问题、生产计划(jhu)与库存、投资决策等实际问题共一百九十三页图与网络(wnglu)流Graph Theory共一百九十三页 决策(juc)论Dec

14、ision Theory著名经济学家西蒙有一句名言：“管理就是决策”“决策”一词本身是一个广义的概念，运筹学课程介绍的决策是“狭义”的，主要是解决两类决策问题：不确定性情况(qngkung)下的决策问题（如风险投资）多目标决策问题（如买房）共一百九十三页 博弈论Game Theory共一百九十三页 博弈论博弈论研究的问题是：当一个主体，如一个人或一个企业的选择，受到其他人、其他企业选择的影响，而且反过来又影响到其他人、其他企业选择时的决策问题博弈论又称为“对策论”博弈论可以解释一些经济和社会现象，比如(br)家电的价格战、民航业的价格战、国家之间的军备竞赛等等现象,解决竞争环境下的决策问题共一

15、百九十三页银行、医院、机场跑道、港口码头、理发店、通信设备、交通路口等都有排队现象19091920年间，丹麦哥本哈根电话工程师爱尔朗Erlang陆续发表了关于电话线路数量等方面的分析计算论文，开创了排队论的研究排队论又叫做随机服务系统理论。它的研究目的是要回答如何改进服务机构、或组织被服务的对象，使得某种指标达到最优的问题。比如一个(y )港口应该有多少个码头，一个(y )工厂应该有多少维修人员等 排队(pi du)论Queuing Theory共一百九十三页存储物品的现象是为了解决供应（生产）与需求（消费）之间的不协调的一种措施由此带来一些需要(xyo)决策的问题：库存量、进货量（如报童问题

16、）、补货的时间等等决策量库存论是供应链管理研究中的热点问题库存(kcn)论Inventory Theory共一百九十三页运筹学的应用(yngyng)有人曾对世界上500家著名的企业(qy)集团或跨国公司进行过调查，发现其中95%使用过线性规划75%使用过运输模型90%使用过网络计划技术90%使用过库存模型43%使用过动态规划 共一百九十三页本课程(kchng)的主要内容线性规划整数规划(guhu)(线性)图论决策论博弈论共一百九十三页参考书：管理决策方法:问题、模型与决策王延章，郭崇慧，叶鑫编著(binzh)，清华大学出版社，2010。管理运筹学教程宁宣熙主编，清华大学出版社，2007。实用管

17、理运筹学:基于Excel陈士成主编，清华大学出版社，2011。决策分析与管理:全面决策质量提升的架构与方法，简祯富著，清华大学出版社，2007。面向经济管理的优化决策方法及应用王勇，赵骅，张宗益著，科学出版社，2005。策略思维:商界、政界及日常生活中的策略竞争，中国人民大学出版社，2013。共一百九十三页第一章 线性规划(xin xn u hu)Linear Programming共一百九十三页运筹学中应用最广泛的方法之一运筹学的最基本方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效(yuxio)方法，使付出的费用最小或获得的收益最大共一百九

18、十三页发展(fzhn)历程原始的数学规划模型早在1759年和1874年就分别由经济学家Quesnay和Walras提出。康托洛维奇于1939年出版了“生产组织与计划中的数学方法”一书，对一个(y )工厂的生产计划任务建立了线性规划模型，并提出“解乘数法”。冯诺伊曼（Von Neuman）和摩根斯坦（Morgenstern）1944年发表的 对策论与经济行为涉及与线性规划等价的对策问题及线性规划对偶理论。丹齐格（G.B. Dantzig）1947年在研究美国空军资源优化配置时提出了线性规划的通用解法单纯形法，并于50年代初成功地利用电子计算机求解线性规划问题。共一百九十三页从1964年诺贝尔奖设

19、经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究(ynji)工作，其中著名的还有Simon，Samullson，Leontief，Arrow，Miller等发展(fzhn)历程共一百九十三页1.1 线性规划(xin xn u hu)的数学模型共一百九十三页 A B 备用资源 煤 1 2 30 劳动力 3 2 60 仓库 0 2 24 利润 40 50例1、生产(shngchn)计划问题问产品A, B各生产(shngchn)多少, 可获最大利润?共一百九十三页 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0 max Z

20、= 40 x1 +50 x2解: 设产品(chnpn)A, B产量分别为变量x1 ， x2共一百九十三页例2求：最低成本(chngbn)的原料混合方案 原料 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 素最低含量共一百九十三页解: 设混合(hnh)添加剂中原料 i 的用量为 xi (i =1,2,3,4)min Z = 2x1+5x2+6x3+8x4 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)共一百九十三页

21、要解决的问题的目标可以用数值指标(zhbio)反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件线性规划(xin xn u hu)问题的特征共一百九十三页线性规划模型(mxng)的要素决策变量：向量(x1 xn)T 决策人要考虑和控制的因素（决策变量类型）约束条件：线性等式(dngsh)或不等式(dngsh)目标函数：Z=(x1 xn) 线性式，求Z的极大或极小共一百九十三页49一般(ybn)式max(min)Z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn (=, )b1a21x1+ a22x2+ a2nxn (=, )b2 am1x1+ am2x2+ am

22、nxn (=, )bmxj ( ) 0, j = 1, 2, , n共一百九十三页共一百九十三页线性规划问题(wnt)的标准形式标准形式的矩阵(j zhn)表示：max z = cTxs.t. Ax = b x 0 a11 a12 a1n其中 A = a21 a22 a2n am1 am2 amn x1 x = x2 xn b1 b = b2 bm c1 c = c2 cn共一百九十三页线性规划(xin xn u hu)问题的标准形式非标准型 标准型(1) 目标(mbio)函数(2) 约束条件(3) 决策变量共一百九十三页(1) 目标(mbio)函数xoz-z线性规划(xin xn u hu)

23、问题的标准形式非标准型 标准型令 z = z共一百九十三页(2) 约束条件线性规划(xin xn u hu)问题的标准形式非标准型 标准型例1. max z = 40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0共一百九十三页(2) 约束条件线性规划(xin xn u hu)问题的标准形式非标准型 标准型 x1 +2x2 +x3 = 30 3x1 +2x2 +x4 = 60 2x2 + +x5 = 24 x1 , , x5 0 x3, x4, x5 称为松弛变量 (slack variables)例1. max z = 40 x1+ 50 x2+

24、0 x3 +0 x4+0 x5共一百九十三页4x1+6x2+ x3 +2x4 12 x1+ x2+7x3+5x4 14 2x2+ x3+3x4 8 x1 , , x4 0 例2. min z = 2x1+ 5x2+6x3 +8x4(2) 约束条件线性规划问题(wnt)的标准形式非标准型 标准型共一百九十三页(2) 约束条件线性规划问题的标准(biozhn)形式非标准型 标准型4x1+6x2+ x3 +2x4 - x5 = 12 x1+ x2+7x3+5x4 - x6 = 14 2x2+ x3+3x4 - x7 = 8 x1 , , x7 0 x5, x6, x7 剩余变量 (surplus v

25、ariables)例2. min z = 2x1+ 5x2+6x3 +8x4共一百九十三页(3) 决策(juc)变量线性规划(xin xn u hu)问题的标准形式非标准型 标准型3 x1 -3 x1 +2x2 8 x1 - x1 4x2 14 x1 , x1 , x2 03x1+2x2 8 x1 4x2 14 x2 0令 x1= x1- x1 共一百九十三页(3) 决策(juc)变量线性规划问题的标准(biozhn)形式非标准型 标准型 x1 +x2 11 x1 16 x1 , x2 0 x1+x2 5-6 x1 10 x2 0-6+6 x1+6 10+6 令 x1 = x1 +6 0 x1

26、 16共一百九十三页练习(linx)：线性规划(xin xn u hu)问题的标准形式将 min z = x1+2x2 3x3化为标准型。 x1+x2 +x3 7x1 x2 +x3 2 x1，x2 0，x3 无限制共一百九十三页解： 令 x3 = x4 x5 加松弛(sn ch)变量 x6 加剩余(shngy)变量 x7 令 z = zmax z = x1 2x2 +3x4 3x5 x1 +x2 +x4 x5 +x6 = 7x1 x2 +x4 x5 x7 = 2 x1 , x2 , x4 , , x7 0线性规划问题的标准形式共一百九十三页线性规划问题(wnt)解的定义max Z=cTx Ax

27、=b (1)x 0 (2)定义1：满足所有约束条件(1)、(2) 的解x=(x1, , xn)T称为(chn wi)LP问题的可行解，全部可行解的集合称为可行域。定义2：使目标函数达到最优值的可行解称为LP问题的最优解.(LP)共一百九十三页1.3 线性规划(xin xn u hu)的图解法共一百九十三页max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行(kxng)域目标(mbio)函数等值线最优解64-860 x1x2共一百九十三页例1、max Z=40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0共一百九十

28、三页解：(1)、确定(qudng)可行域 x1 0 x1 =0 (纵) x2 0 x2=0 (横) x1+2x2 30 x1+2x2 =30 (0,15) (30,0)0102030 x2DABC3x1+2x2 60 (0,30) (20,0) 2x2 24203010 x1共一百九十三页(2)、求最优解解：x* = (15,7.5) Zmax =975Z=40 x1+50 x20=40 x1+50 x2 (0,0)， (10,-8)C点： x1+2x2 =30 3x1+2x2 =600203010102030 x1x2DABC共一百九十三页例2、 max Z=40 x1+ 80 x2 x1+

29、2x2 303x1+2x2 60 2x2 24 x1 , x2 0共一百九十三页0Z= 40 x1 + 80 x2 =0 x1 + 2x2 =30DABCx2x1最优解：BC线段(xindun)B点 C点x(1)=(6,12) x(2)=(15,7.5)x= x(1)+(1-) x(2) (0 1)求解(qi ji)共一百九十三页x1 =6+ +(1- )15x2=12+ +(1- )7.5x1 =15-9x2 =7.5+4.5 (0 1)X= = +(1- )Max Z=1200 x1 6 15 x2 12 7.5共一百九十三页无界无有限(yuxin)最优解例3、 max Z=2x1+ 4x

30、2 2x1+x2 8-2x1+x2 2x1 , x2 0Z=02x1+ x2=8-2x1+ x2=28246x240 x1共一百九十三页例4、 max Z=3x1+2x2 - x1 - x2 1x1 , x2 0无解无可行(kxng)解-1X2-1X10共一百九十三页 线性规划的可行域及最优解的可能结果图示：(a)可行(kxng)域封闭，唯一最优解(b)可行(kxng)域封闭，多个最优解(d)可行域开放，多个最优解(e)可行域开放，目标函数无界 (f) 可行域为空集(c)可行域开放，唯一最优解共一百九十三页总结(zngji) 唯一解 无穷多解 无有限最优解（无界解） 无可行解有解无解共一百九十

31、三页(1)、可行(kxng)域为凸多边形。(2)、若有最优解，一定(ydng)可在可行域的顶点达到。X(1)X(2)凸多边形凹多边形X(1)X(2)1.4 线性规划解的几何特性共一百九十三页 凸集及其性质(xngzh)定义1：凸集D是n维欧氏空间的一个集合 X(1), X(2)D,若任一个满足 X= X(1)+(1-) X(2) (0 1) 有XD凸集中任意(rny)两点的连线仍然属于该集合。共一百九十三页凸集图例(tl) (a)凸集 (b)凸集 (c)凸集 (a)非凸集 (b)非凸集 (c)非凸集 共一百九十三页 X(1) , X(2) , ,X(k) 是n维欧氏空间(kngjin)中的k个

32、点，若有一组数 1 , 2 , , k 满足 0 i 1 (i=1, ,k)定义(dngy)2 i =1ki=1有点 X= 1 X(1) + + k X(k)则称点X为 X(1) , X(2) , ,X(k) 的凸组合。凸组合共一百九十三页 凸集D, 点 XD，若找不到(b do)两个不同的点X(1) , X(2) D 使得 X= X(1) +(1- ) X(2) (0 1) 则称X为 D的顶点。定义(dngy)3顶点共一百九十三页求解(qi ji)线性规划的单纯形法共一百九十三页1.5 LP问题(wnt)的基本解Max Z=cTx Ax =b x0Amn 满秩 x= (x1 xn)T 共一百

33、九十三页a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amnP1 Pm Pm+1 PnBN(m 40 选x2从0，x1 =0 x3 =30-2x2 0 x2 30/2 x4 =60-2x2 0 x2 60/2 x5 =24-2x2 0 x2 24/2 x2=min(30/2 , 60/2 , 24/2 ) =12x2进基变量(binling)， x5出基变量。共一百九十三页B2 = (P3 P4 P2)Z=0+40 x1+50 x2 x3 +2x2 =30-x1 x4+2x2 =60-3x1 2x2=24-x5 共一百九十三页 1/2 ，代入

34、式， ，Z=600 +40 x1 -25x5x3 =6 -x1 +x5 x4 = 36-3x1 +x5 x2=12 -1/2x5令x1 =x5 =0 X(2) =(0, 12, 6, 36, 0)T Z(2) =600共一百九十三页(2) 判断(pndun) 400 X(2)不是(b shi)。(3) 选x1从0， x5 =0 x3= 6- x1 0 x4= 36-3x1 0 x2=12 0 x1=min( 6/1 , 36/3 ) =6x1进基， x3出基。共一百九十三页B3 = (P1 P4 P2 )Z=840-40 x3+15x5x1=6 - x3 + x5 x4= 18+3x3 - 2

35、x5x2=12 - 1/2x5令x3 =x5 =0 X(3) =(6, 12, 0, 18, 0)TZ(3) =840共一百九十三页(2) 150 X(3)不是(b shi)(3) 选x5从0， x3 =0 x1=6 +x5 0 x4= 18 -2x5 0 x2=12 - 1/2 x5 0 x5=min( 18/2 , 12/1/2 ) =9x5进基， x4出基。共一百九十三页B4 = (P1 P5 P2 )Z=975- 35/2 x3 - 15/2 x4x1= 15 + 1/2 x3 - 1/2 x4x5= 9 + 3/2 x3 - 1/2 x4x2= 15/2 -3/4 x3 + x4令x

36、3 =x4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975共一百九十三页0(0,0)x2x1A DCB(0,12)(6,12)(15,7.5)共一百九十三页三、单纯形表 c1 c2 cm cm+1 cm+k cnCB XB B-1b x1 x2 xm xm+1 xm+k xnc1 x1 b1 1 0 0 a1m+1 a1m+k a1nc2 x2 b2 0 1 0 a2m+1 a2m+k a2ncr xr br 0 0 0 arm+1 arm+k arncm xm bm 0 0 1 amm+1 amm+k ann Z0 0 0 0 m+1 m+k n共一百九十

37、三页例1Max Z=40 x1 +50 x2 x1 +2x2 +x3 =30 3x1 +2x2 +x4 =60 2x2 +x5 =24 x1 x5 0共一百九十三页 40 50 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 30 1 2 1 0 0 150 x4 60 3 2 0 1 0 300 x5 24 0 (2) 0 0 1 12 0 40 50 0 0 00 x3 6 (1) 0 1 0 -1 60 x4 36 3 0 0 1 -1 1250 x2 12 0 1 0 0 1/2 600 40 0 0 0 -2540 x1 6 1 0 1 0 -10 x4 18 0

38、 0 -3 1 (2) 950 x2 12 0 1 0 0 1/2 24840 0 0 -40 0 15共一百九十三页40 x1 15 1 0 -1/2 1/2 0 0 x5 9 0 0 -3/2 1/2 1 50 x2 15/2 0 1 3/4 -1/4 0本问题(wnt)的最优解 X=(15, 15/2, 0, 0, 9)T Z=975 40 50 0 0 0 CB XB b x1 x2 x3 x4 x5 975 0 0 -35/2 -15/2 0共一百九十三页例2 max Z = x1 +2x2x1 4x2 3x1+2x2 8 x1 , x2 0 x1+x3 = 4x2+x4 = 3x1

39、+2x2+x5= 8 x1 x5 0共一百九十三页 1 2 0 0 0 CB XB b x1 x2 x3 x4 x50 x3 4 1 0 1 0 00 x4 3 0 (1) 0 1 00 x5 8 1 2 0 0 1 0 1 2 0 0 00 x3 4 1 0 1 0 0 2 x2 3 0 1 0 1 0 0 x5 2 (1) 0 0 -2 1 (接下表) 6 1 0 0 -2 0共一百九十三页 1 2 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 2 0 0 1 (2) -12 x2 3 0 1 0 1 01 x1 2 1 0 0 -2 1 8 0 0 0 0 -10

40、x4 1 0 0 1/2 1 -1/2 2 x2 2 0 1 -1/2 0 1/2 1 x1 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无穷(wqing)多解全部解：X= + (1-) (0 1)2 4 3 2共一百九十三页例3 求 max Z = x1 x2+x3 3x5x2+x3 x4+2x5 = 6x1+2x2 2x4 = 52x2 +x4+3x5 +x6 = 8x1 x6 0共一百九十三页 1 -1 1 0 -3 0 CB XB b x1 x2 x3 x4 x5 x61 x3 6 0 1 1

41、-1 2 01 x1 5 1 2 0 -2 0 00 x6 8 0 2 0 1 3 1 11 0 -4 0 3 -5 01 x3 14 0 3 1 0 5 1 1 x1 21 1 6 0 0 6 20 x4 8 0 2 0 1 3 1 35 0 -10 0 0 -14 -3共一百九十三页例4 max Z = 10 x1 + 12x23x1+4x2 64x1+ x2 23x1 +2x2 3x1 , x2 0共一百九十三页 10 12 0 0 0 XB b x1 x2 x3 x4 x5 i 0 x3 6 3 (4) 1 0 0 3/20 x4 2 4 1 0 1 0 2/10 x5 3 3 2 0

42、 0 1 3/2 0 10 12 0 0 0 12 x2 3/2 3/4 1 1/4 0 0 20 x4 1/2 13/4 0 -1/4 1 0 2/130 x5 0 (3/2) 0 -1/2 0 1 0 18 1 0 -3 0 0 12 x2 3/2 0 1 1/2 0 -1/20 x4 1/2 0 0 5/6 1 -13/6 10 x1 0 1 0 -1/3 0 2/3 18 0 0 -8/3 0 -2/3 共一百九十三页退化解(hu ji)X *= (0, 3/2, 0, 1/2, 0)TZmax = 18共一百九十三页例5：max Z = 4x1 +x2 -x1+ x2 2 x1 4x

43、2 4 x1 2x2 8x1 , x2 0共一百九十三页 4 1 0 0 0 CB XB b x1 x2 x3 x4 x50 x3 2 -1 1 1 0 00 x4 4 (1) -4 0 1 00 x5 8 1 -2 0 0 1 0 4 1 0 0 0共一百九十三页0 x3 6 0 -3 1 1 04 x1 4 1 -4 0 1 00 x5 4 0 (2) 0 -1 1 16 0 17 0 -4 00 x3 12 0 0 1 -1/2 3/24 x1 12 1 0 0 -1 21 x2 2 0 1 0 -1/2 1/2 50 0 0 0 9/2 -17/2共一百九十三页本问题(wnt)无界。x

44、1x2OZ=0共一百九十三页四、 初始(ch sh)基本可行解的求法(一)、大M法：判定无解条件：当进行到最优表时，仍有人工变量(binling)在基中，且0，则说明原问题无可行解。共一百九十三页例1：max Z = 6x1 +4x2 2x1 +3x2 1004x1 +2x2 120 x1 =14 x2 22x1 x2 0共一百九十三页max Z = 6x1+4x22x1 +3x2 +x3 =1004x1 +2x2 +x4 =120 x1 =14 x2 - x5 = 22x1 x5 0共一百九十三页max Z = 6x1+4x2-Mx6 -Mx72x1 +3x2 +x3 =1004x1 +2x

45、2 +x4 =120 x1 +x6 =14 x2 - x5 +x7 = 22x1 x7 0共一百九十三页 6 4 0 0 0 - M - M CB XB b X1 X2 X3 X4 X5 X6 X70 X3 100 2 3 1 0 0 0 0 0 X4 120 4 2 0 1 0 0 0 -M X6 14 (1) 0 0 0 0 1 0 -M X7 22 0 1 0 0 -1 0 1 -36 M M +6 M +4 0 0 - M 0 00 X3 72 0 3 1 0 0 -2 0 0 X4 64 0 2 0 1 0 -4 0 6 X1 14 1 0 0 0 0 1 0 -M X7 22 0

46、(1) 0 0 -1 0 1 84-22M 0 M+4 0 0 -M 6-M 0共一百九十三页0 x3 6 0 0 1 0 (3) -2 -3 0 x4 20 0 0 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0 4 x2 22 0 1 0 0 -1 0 1 172 0 0 0 0 4 6-M 4-M0 x5 2 0 0 1/3 0 1 -2/3 -1 0 x4 16 0 0 -2/3 1 0 -8/3 0 6 x1 14 1 0 0 0 0 1 0 4 x2 24 0 1 1/3 0 0 -2/3 -2 180 0 0 -4/3 0 0 -M-10/3 -MCB XB

47、b x1 x2 x3 x4 x5 x6 x76 4 0 0 0 - M - M共一百九十三页1.7 线性规划(xin xn u hu)的对偶问题Duality共一百九十三页一、对偶(du u)问题 例：某厂生产甲、乙两种产品(chnpn)，消耗A、B两种原材料。生产一件甲产品可获利2元，生产乙产品获利3元。问在以下条件下应如何安排生产获利最大？ 甲乙总量设备台时原材料A原材料B140204 81612建立线性规划模型：目标函数： MAX Z = 2X1+3X2约束条件： X1+2X2 8 4X1+ 16 4X212 X1, X20共一百九十三页 从另一角度考虑： 如果该厂决定不生产甲、乙两种产

48、品，而将其资源出租或出售，这时工厂的决策者就要考虑给每种资源如何定价的问题。设用Y1,Y2,Y3分别表示出租单位设备台时的租金和出让原材料 A、B 的附加值。作如下比较，用一个单位设备台时和四个单位的原材料可以生产甲产品一件，获利2元，那么(n me)出租和出让的收益不应低于自己生产时的收益。因此有 Y1+4Y22 同样地乙产品也有：2Y1+4Y33 一、对偶(du u)问题共一百九十三页 全部出让或出租的总收入为 W = 8Y1+16Y2+12Y3 从决策者来看，当然希望(xwng)W值越大越好。但从接受者来讲，支付越少越好。为提高竞争力，因此工厂只能在满足所有产品的利润条件，使其总收入具有

49、竞争力的，因此，W需要求解最小值。 因此有线性规划模型： 目标函数： min W = 8Y1+16Y2+12Y3 s.t. Y1+4Y22 2Y1+4Y33 Y1,Y2,Y30一、对偶(du u)问题共一百九十三页 二、对偶(du u)关系原问题(wnt) (primal problem)（P）：max z = CTXAX bX 0对偶问题 (dual problem)（D）：min w = bTYATY CY 0共一百九十三页二、对偶(du u)关系 （P）（D）目标函数maxmin目标系数Cb约束右端bC系数矩阵AAT函数约束与变量约束第k个约束 第k个变量约束个数=变量个数（非）规范约束

50、 非负（正）变量等式约束 自由变量共一百九十三页二、对偶(du u)关系例子(l zi):min z = 3x1 + 2x2 x3s.t. 2x1 + x2 + 3x3 23x1 - 5x2 5 x1 + x2 + x3 = 1x1 0, x2自由, x3 0共一百九十三页二、对偶(du u)关系其对偶(du u)问题:max w = 2y1 + 5y2 + y3s.t. 2y1 + 3y2 + y3 3 y1 5y2 + y3 = 23y1 + y3 -1y1 0, y2 0, y3自由min z = 3x1 + 2x2 x3s.t. 2x1 + x2 + 3x3 23x1 - 5x2 5

51、x1 + x2 + x3 = 1x1 0, x2自由, x3 0共一百九十三页例、写对偶(du u)规划Min Z= 4x1 +2x2 3x3 -x1+2x2 62x1 +3x3 9 x1 +5x2 2x3 = 4x2 , x3 0Max W= 6y1 +9y2 +4y3 -y1+2y2 + y3 = 42y1 +5y3 2 3y2 -2y3 -3y1 0 , y2 0 , y3自由(zyu)共一百九十三页Min Z= 4x1 +2x2 3x3 x1 2x2 - 62x1 +3x3 9 x1 +5x2 2x3 = 4x2 , x3 0Max W= -6y1 +9y2 +4y3 y1+2y2 +

52、 y3 = 4-2y1 +5y3 2 3y2 -2y3 -3y1 , y2 0 , y3自由(zyu)例、写对偶(du u)规划共一百九十三页三、对偶(du u)性质对称性: (P)和(D)相互对偶弱对偶性: CTX bTY最优性: 当CTX = bTY时,(P)(D)皆最优对偶原理: 如果一个问题有最优解,其对偶问题也有最优且等最优值; 如一个问题无界,其对偶问题无可行(kxng)解兼容性: 达到最优时，原问题的检验数给出对偶问题的最优解互补松弛性共一百九十三页例1、3x1 +x2 +x3=483x1 +4x2 +x4=120 x1 x40max Z= 5x1 +6x2 3x1 +x2 48

53、3x1 +4x2 120 x1 , x2 0共一百九十三页X=(8,24)T Z =184 5 6 0 0 XB b x1 x2 x3 x40 x3 48 3 1 1 00 x4 120 3 (4) 0 1 0 5 6 0 00 x3 18 (9/4) 0 1 -1/46 x2 30 3/4 1 0 1/4 180 1/2 0 0 -3/25 x1 8 1 0 4/9 -1/96 x2 24 0 1 -1/3 1/3 184 0 0 -2/9 -13/9共一百九十三页3y1+3y2 5 y1 +4y2 6min W=48y1+120y23y1+3y2 -y3+y5 =5 y1 +4y2 -y4

54、+y6= 6min W=48y1+120y2 +My5 +My6共一百九十三页 48 120 0 0 M M yB y1 y2 y3 y4 y5 y6M y5 5 3 3 -1 0 1 0 M y6 6 1 4 0 -1 0 1 11M 48-4M 120-7M M M 0 0M y5 1/2 9/4 0 -1 3/4 1 -3/4120 y2 3/2 1/4 1 0 -1/4 0 1/4 180+1/2M 18-9/4M 0 M 30-3/4M 0 -30+7/4M48 y1 2/9 1 0 -4/9 1/3 4/9 -1/3120 y2 13/9 0 1 1/9 -1/3 -1/9 1/3

55、y=(2/9,13/9), Z=184 184 0 0 8 24 M-8 M-24共一百九十三页观察(gunch)结论: 一对互为对偶的线性规划问题(wnt)都有最优解，且目标函数值相等。 最优表中有两个问题的最优解。共一百九十三页互补松弛(sn ch)性（松紧定理）在线性规划(xin xn u hu)问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量为零。原问题：max z=CX AX + Xs =b X , Xs 0 X =x1xnXs=xs1xsm共一百九十三页2.6 互补(h b)松弛性的应用例. 已知

56、线性规划问题min Z = 2x1+ 3x2 + 5x3 + 2x4 + 3x5 x1+ x2 + 2x3 + x4 +3x5 4 2x1- x2 + 3x3 + x4 + x5 3 x1, x2 , x3 , x4 , x5 0其对偶问题的最优解为 y1=4/5，y2=3/5，试应用(yngyng)对偶理论求原问题的解。共一百九十三页将 y1=4/5, y2 =3/5的值代入，得知 为严格不等式，于是(ysh)由互补松驰性，必有 x2= x3 = x4=0 解：写出对偶(du u)问题：max S = 4y1+ 3y2 y1+ 2y2 2 y1- y2 3 2y1+ 3y2 5 y1+ y2

57、 2 3y1+ y2 3 y1, y2 0又因 y1, y2 0，故原问题的两个约束条件必为紧约束，即有 x1+ 3x5 =4 2x1+ x5 =3 解得 x1=x5 =1 即 X*=(1,0,0,0,1)T, Z*=5共一百九十三页四、对偶解的经济(jngj)意义(1)、Z= CBB-1b + (CN - CBB-1 N)XN (*) Z= Z(b) b为资源对(*)求偏导： Z b=CBB-1=Y对偶解Y：b 的单位改变量所引起的目标函数改变量。共一百九十三页经济(jngj)解释：W=Yb=(y1 ym )b1bm= b1 y1 + b2 y2 + + bm ymbi ： 第 i 种资源(

58、zyun)的数量yi ：对偶解bi增加 bi ,其它资源数量不变时,目标函数的增量 Z=bi yiyi ：反映bi 的边际效益(边际成本)例1中y1 =2/9, 当机器台时数增加1个单位时，工厂可增加利润2/9个单位。共一百九十三页影子(yng zi)价格由前面的经济解释可知，yi 的大小与系统内资源(zyun)对目标的贡献有关，是资源(zyun)的一种估价，称为影子价格(Shadow Price)。注：这种估价不是资源的市场价格。市场价格是已知数，相对较稳定；而影子价格则依赖于资源的利用情况，是未知数。当企业的生产任务、产品结构等等发生变化时，资源的影子价格也会随之改变，它是一种动态价格。共

59、一百九十三页影子价格(jig)的应用即某资源对偶解0，该资源有利可图(yu l k t)，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。 影子价格的大小客观地反映了资源在系统内的稀缺程度 根据互补松弛定理的条件，如果某一资源在系统内供大于求，其影子价格就为零。 即增加该资源的供应不会引起系统目标的任何变化。 如果某一资源是稀缺资源（即相应约束条件的剩余变量为零），则影子价格必然大于零。 影子价格越高，资源在系统中越稀缺。共一百九十三页即直接用影子价格(jig)与市场价格(jig)相比较，进行决策，是否买入该资源。影子价格(jig)的应用 影子价格实际上是一种机会成本 在完全市场经济条

60、件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大再生产； 而当某种资源的市场价格高于影子价格时，企业应卖掉已有资源。 随着资源的买进卖出，其影子价格也将发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡。共一百九十三页 生产计划问题 项目投资问题 配料配套(pi to)问题 合理下料问题 人力资源问题 运输调运问题 任务指派问题 1.8 线性规划(xin xn u hu)模型的应用共一百九十三页例1: 生产(shngchn)计划问题 某企业拟生产A、B两种产品，需利用一种原材料并经过车、刨两台机床加工，加工的工时定额、每天可用工时和原材料以及两种产品可能获得的利润如