应用运筹学线性规划

1、徐薇南京大学工程管理学院 运筹 学F什么是运筹学？F为什么要学习运筹学？F要学习哪些内容？引言什么是运筹学F运筹帷幄之中，决胜千里之外F作为一门学科诞生于20世纪30年代末F在英国称为Operational Research，在美国称为Operations Research，缩写为O.R.F在大英百科全书中的定义： “运筹学是一门应用于管理有组织系统的科学，运筹学为掌握这类系统的人提供决策目标和数量分析的工具”什么是运筹学F在中国大百科全书中的定义： “用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势

2、，制定行动规划或优选可行方案”什么是运筹学F运筹学的研究对象是各种系统；F运筹学的研究目的是实现系统的最优化，求得合理利用各种资源的最优方案；F运筹学的研究方法是运用数学语言来描述实际系统，通过建立数学模型和优化技术求得系统运营的最优解；F运筹学的研究动机是为决策者提供科学决策的依据。 运筹学发展背景v 丁谓主持的皇宫修复工程 北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、生产、运输及废墟物

3、的处理用“一沟三用”巧妙地解决了。v 田忌赛马 齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排： 齐王 上 中 下 田忌 下 上 中 最终净胜一局，赢得1000金。F起源于二次大战的一门新兴学科F与作战相关 雷达的设置 运输船队的护航 反潜作战中深水炸弹的深度 飞行员的编组 军事物资的存储等运筹学的起源v 鲍德西（Bawdsey）雷达站的研究1935年，英国科学家R.Watson-Wart发明了雷达。丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站。当时，德国已拥有一支强大的空军，起飞17分钟即到达

4、英国本土。在如此短的时间内，如何预警和拦截成为一大难题。战争背后的数学奥秘 1939年由曼彻斯特大学物理学家、英国战斗机司令部顾问、战后获得诺贝尔奖的P. M. S. Blackett 为首，组织了一个小组，代号“Blackett马戏团”。这个小组包括：三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官、一名测量员。战争背后的数学奥秘 研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。 “Blackett马戏团”在秘密报告中首次使

5、用了“Operational Research”，即“运筹学”。战争背后的数学奥秘v 精计算，深水炸弹弱变强 1941-1942年，德国潜艇严密封锁了英吉利海峡，企图切断英国的“生命线”。海军几次反封锁，均不成功。应英国要求，美国派麻省理工学院的物理学家P.W.Morse担任计划与监督。率领一个小组去协助。Morse经过多方实地考察和分析计算，最后提出了两条重要建议：战争背后的数学奥秘 将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率4-7倍) 运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次

6、，这样，损失率将减少。（25%下降到10%） 战争背后的数学奥秘F战后在经济、管理部门和学校及科研单位继续开展研究F1948年英国首先成立战问题运筹学俱乐部F1952年美国成立运筹学会F1952年，Morse 和 Kimball出版运筹学方法F1959年成立国际运筹学联合会(IFORS)F我国于1982年加入IFORS，并于1999年8月组织了第15届大会运筹学的发展 定量分析的过程F定性分析定量分析的前奏应当是一个彻底的定性分析F表达问题列出表达问题的基本要素：决策变量、限制条件等F建立模型列出表达这些要素之间关系的数学方程式F求解模型与分析运用算法求解所构建的模型得到最佳方案或满意方案对输

7、入数据和模型结构作灵敏度分析F执行决定或修改模型在实际应用过程中不断完善模型 建立模型的重要性F建立模型是运筹学方法的精髓建立模型有助于我们把决策问题所遇到的复杂性和可能的不确定性，转变为适于综合分析的逻辑结构；模型是一种媒介，借以对现实世界作出正确的认识。F模型是现实的近似表达，要能抓住决策问题的关键，在真实性和可用性之间取得适当的平衡问题类型典型问题 预 测 财 务 人力资源 时 序 资源配置 设备更新 库存控制 选 址 项目规划 排队问题对产品的需求有多大，类别如何，利润影响？需要多少资金，从何处得到，成本有多大？需要多少人员，应有何技能，留用多长时间？什么工作最重要，工作顺序如何安排？

8、需要什么资源，是否短缺，如何优先获得？设备运转如何，可靠性如何，何时更新？合理库存量为多少，订货的最佳批量和周期？运作的最佳场所在何处，需要什么设施？项目合理的作业时间为多少，资源如何利用？队列多长，提供多少个服务台，服务水平？企业中的定量决策问题 现实中的优化问题F物流网络的设计优化；F供应链中的多级存储系统的运行优化；F港口集装箱调度的优化；F制造系统的生产计划与调度优化；F复杂工程系统设计的优化；F复杂过程控制系统的参数优化；F投资组合优化问题；F。 物流网络的设计优化F随着我国物流业的快速发展，不同类型的物流系统的设计，物流园区的设计有很大的实际需求。这些系统设计中有很多优化问题，如：

9、多个仓库位置的选定仓库容量的确定运输方式和运输工具的选择车辆路径的规划。 供应链的运行优化F供应链的运行中也有很多优化问题，如：分销网络中多级库存系统的库存补充计划安全库存的分级配置优化考虑缺货或事故情况的处理顺应价格波动的存储计划车辆运输计划和路径优化。 港口集装箱调度的优化F现代化港口和铁路集装箱中心站的集装箱运输中也有很多优化问题，如：船舶的泊次计划集装箱的装/卸载计划堆场的空间计划车辆的作业计划货场的堆放计划码头起重机的调度计划。金融投资问题F投资组合问题(Portfolio) 已知某三支股票的价格近十年每年的增长情况,以及500种股票指数变化情况, 假设你现在有一笔资金要进行投资,

10、并期望年利率至少达到15%, 那么你应该如何投资? 。 航空公司的订票热线问题F该公司要在郊区商业中心内设一个订票服务处，旅客订票时可以用电话与服务处联系。OR公司想知道，为了满足订票业务的需要，应该安装多少条电话线路为宜？F该公司希望对若干条不同线路方案的服务水平加以对比，尤其是公司要设法确定所有线路被占用的时间百分比，以及平均等待时间长度。运筹学主要分支简介数学规划Mathematical ProgrammingF一般数学描述 F目标函数或约束函数都是线性的，则是线性规划(Linear Programming)；F若其中至少有一个是非线性的，为非线性规划(Nonlinear Program

11、ming)；F若其中至少有一个变量要求为整数，则为整数规划(Integer Programming)。121212 () ( ,.,). . ( ,.,)0 1,2,., ( ,.,)0 1,2,.,ninjnmin maxf x xxsth x xximgx xxjl数学规划F动态规划(Dynamic Programming)解决多阶段决策过程最优化问题的一种方法可用于解决最优路径问题、生产计划与库存、投资决策等实际问题图与网络流Graph Theory 决策论Decision TheoryF著名经济学家西蒙有一句名言：“管理就是决策”F“决策”一词本身是一个广义的概念，运筹学课程介绍的决策

12、是“狭义”的，主要是解决两类决策问题： 不确定性情况下的决策问题（如风险投资） 多目标决策问题（如买房） 博弈论Game Theory 博弈论F博弈论研究的问题是：当一个主体，如一个人或一个企业的选择，受到其他人、其他企业选择的影响，而且反过来又影响到其他人、其他企业选择时的决策问题F博弈论又称为“对策论”F博弈论可以解释一些经济和社会现象，比如家电的价格战、民航业的价格战、国家之间的军备竞赛等等现象,解决竞争环境下的决策问题F银行、医院、机场跑道、港口码头、理发店、通信设备、交通路口等都有排队现象F19091920年间，丹麦哥本哈根电话工程师爱尔朗Erlang陆续发表了关于电话线路数量等方面

13、的分析计算论文，开创了排队论的研究F排队论又叫做随机服务系统理论。它的研究目的是要回答如何改进服务机构、或组织被服务的对象，使得某种指标达到最优的问题。比如一个港口应该有多少个码头，一个工厂应该有多少维修人员等 排队论Queuing TheoryF存储物品的现象是为了解决供应（生产）与需求（消费）之间的不协调的一种措施F由此带来一些需要决策的问题：库存量、进货量（如报童问题）、补货的时间等等决策量F库存论是供应链管理研究中的热点问题库存论Inventory Theory运筹学的应用F有人曾对世界上500家著名的企业集团或跨国公司进行过调查，发现其中 95%使用过线性规划 75%使用过运输模型

14、90%使用过网络计划技术 90%使用过库存模型 43%使用过动态规划 本课程的主要内容F线性规划F整数规划(线性)F图论F决策论F博弈论参考书：参考书：q管理决策方法管理决策方法:问题、模型与决策问题、模型与决策王延章，郭崇慧，叶王延章，郭崇慧，叶鑫编著，清华大学出版社，鑫编著，清华大学出版社，2010。q管理运筹学教程管理运筹学教程宁宣熙主编，清华大学出版社，宁宣熙主编，清华大学出版社，2007。q实用管理运筹学实用管理运筹学:基于基于Excel陈士成主编，清华大学出版陈士成主编，清华大学出版社，社，2011。q决策分析与管理决策分析与管理:全面决策质量提升的架构与方法全面决策质量提升的架构

15、与方法，简，简祯富著，清华大学出版社，祯富著，清华大学出版社，2007。q面向经济管理的优化决策方法及应用面向经济管理的优化决策方法及应用王勇，赵骅，张宗王勇，赵骅，张宗益著，科学出版社，益著，科学出版社，2005。q策略思维策略思维:商界、政界及日常生活中的策略竞争商界、政界及日常生活中的策略竞争，中国，中国人民大学出版社，人民大学出版社，2013。第一章 线性规划Linear ProgrammingF运筹学中应用最广泛的方法之一F运筹学的最基本方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的F解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大发展历程F

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

17、获奖者中有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各生产多少各生产多少, 可获最大利润可获最大利润? x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0 max Z = 40 x1 +50 x2解解: 设产品设产品A, B产量分别为变量产量分别为变量x1 ， x2例

18、例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 的用量为的用量为 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)F要解决的问题的目标可以用数值指标反映要解决的问题的目标可以用数

19、值指标反映F对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择F有影响决策的若干约束条件有影响决策的若干约束条件线性规划问题的特征线性规划模型的要素F决策变量：向量决策变量：向量(x1 xn)T 决策人要考虑决策人要考虑和控制的因素（决策变量类型）和控制的因素（决策变量类型）F约束条件：线性等式或不等式约束条件：线性等式或不等式F目标函数：目标函数：Z=(x1 xn) 线性式，求线性式，求Z的的极大或极小极大或极小49一般式一般式max(min)Z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn (=, (=, ) )b1a21x1+ a22x2+ a2nx

20、n (=, (=, ) )b2 am1x1+ am2x2+ amnxn (=, (=, ) )bmxj ( ) 0, j = 1, 2, , n1max(min)njjjZc x)0(), 2 , 1(1jinjjijxmibxa线性规划问题的标准形式F标准形式的矩阵表示：标准形式的矩阵表示：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线性规划问题的标准形式F非标准型非标准型 标准型标准型(1) 目标函数(2) 约束条件(

21、3) 决策变量(1) 目标函数目标函数xoz-z线性规划问题的标准形式F非标准型非标准型 标准型标准型1min njjjzc x令令 z = z1max njjjzc x (2) 约束条件约束条件线性规划问题的标准形式F非标准型非标准型 标准型标准型例例1. max z = 40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0(2) 约束条件约束条件线性规划问题的标准形式F非标准型非标准型 标准型标准型 x1 +2x2 +x3 = 30 3x1 +2x2 +x4 = 60 2x2 + +x5 = 24 x1 , , x5 0 x3, x4, x5

22、称为称为松弛变量松弛变量 (slack variables)例例1. max z = 40 x1+ 50 x2+0 x3 +0 x4+0 x54x1+6x2+ x3 +2x4 12 x1+ x2+7x3+5x4 14 2x2+ x3+3x4 8 x1 , , x4 0 例例2. min z = 2x1+ 5x2+6x3 +8x4(2) 约束条件约束条件线性规划问题的标准形式F非标准型非标准型 标准型标准型(2) 约束条件约束条件线性规划问题的标准形式F非标准型非标准型 标准型标准型4x1+6x2+ x3 +2x4 - x5 = 12 x1+ x2+7x3+5x4 - x6 = 14 2x2+

23、x3+3x4 - x7 = 8 x1 , , x7 0 x5, x6, x7 剩余变量剩余变量 (surplus variables)例例2. min z = 2x1+ 5x2+6x3 +8x4(3) 决策变量决策变量线性规划问题的标准形式F非标准型非标准型 标准型标准型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) 决策变量决策变量线性规划问题的标准形式F非标准型非标准型 标准型标准型 x1 +x2 11 x1 16 x1 , x2 0 x1+x2 5-6 x1

24、10 x2 0-6+6 x1+6 10+6 令令 x1 = x1 +6 0 x1 16练习：练习：线性规划问题的标准形式将将 min z = x1+2x2 3x3化为标准型。化为标准型。 x1+x2 +x3 7x1 x2 +x3 2 x1，x2 0，x3 无限制无限制解：解： 令令 x3 = x4 x5 加松弛变量加松弛变量 x6 加剩余变量加剩余变量 x7 令令 z = zmax z = x1 2x2 +3x4 3x5 x1 +x2 +x4 x5 +x6 = 7x1 x2 +x4 x5 x7 = 2 x1 , x2 , x4 , , x7 0线性规划问题的标准形式线性规划问题解的定义max

25、Z=cTx Ax=b (1)x 0 (2)定义定义1 1：满足所有约束条件：满足所有约束条件(1)、(2) 的解的解x=(x1, , xn)T称为称为LP问题的问题的可行解可行解，全部可行，全部可行解的集合称为解的集合称为可行域。可行域。定义定义2 2：使目标函数达到最优值的可行解称为：使目标函数达到最优值的可行解称为LP问题的问题的最优解最优解.(LP)1.3 线性规划的图解法max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域可行域目标函数等值线目标函数等值线最优解最优解64-860 x1x2例例1、max Z=40 x1+ 50 x2 x1+2x2 3

26、03x1+2x2 60 2x2 24 x1 , x2 0 0解：解：(1)、确定可行域、确定可行域 x1 0 0 x1 =0=0 ( (纵纵) ) x2 0 0 x2=0=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 =60020301

27、0102030 x1x2DABC例例2、 max Z=40 x1+ 80 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 00Z= 40 x1 + 80 x2 =0 x1 + 2x2 =30DABCx2x1最优解：最优解：BC线段线段B点点 C点点x(1)=(6,12) x(2)=(15,7.5)x= x(1)+(1- ) x(2) (0 1)求解求解x1 =6 + +(1- )15x2=12 + +(1- )7.5x1 =15-9 x2 =7.5+4.5 (0 1)X= = +(1- )Max Z=1200 x1 6 15 x2 12 7.5无界无界无有限最优

28、解无有限最优解例例3、 max Z=2x1+ 4x2 2x1+x2 8 8-2x1+x2 2x1 , x2 0 0Z=02x1+ x2=8-2x1+ x2=28246x240 x1例例4、 max Z=3x1+2x2 - x1 - x2 1 1x1 , x2 0 0无解无解无可行解无可行解-1X2-1X10 (a)可行域封闭，唯一最优解可行域封闭，唯一最优解 (b)可行域封闭，多个最优解可行域封闭，多个最优解(d)可行域开放，多个最优解可行域开放，多个最优解(e)可行域开放，目标函数无界可行域开放，目标函数无界 (f) 可行域为空集可行域为空集(c)可行域开放，唯一最优解可行域开放，唯一最优解

29、总结总结 唯一解唯一解 无穷多解无穷多解 无有限最优解（无界解）无有限最优解（无界解） 无可行解无可行解有解有解无解无解(1)、可行域为凸多边形。、可行域为凸多边形。(2)、若有最优解，一定可在可行域的顶点达到。、若有最优解，一定可在可行域的顶点达到。X(1)X(2)凸多边形凸多边形凹多边形凹多边形X(1)X(2)1.4 线性规划解的几何特性 凸集及其性质F定义定义1：凸集：凸集D是是n维欧氏空间的一个集维欧氏空间的一个集合合 X(1), X(2)D,D,若任一个满足若任一个满足 X= X(1)+(1- ) X(2) (0 1) 有有XDDF凸集中任意两点的连线仍然属于该集合。凸集中任意两点的

30、连线仍然属于该集合。凸集图例凸集图例(a)凸集凸集 (b)凸集凸集 (c)凸集凸集(a)非凸集非凸集 (b)非凸集非凸集 (c)非凸集非凸集 X(1) , X(2) , ,X(k) 是是n维欧氏空间中的维欧氏空间中的k个点，若有一组数个点，若有一组数 1 , 2 , , k 满足满足 0 i 1 1 (i=1,(i=1, ,k) )定义定义2 i =1ki=1有点有点 X= 1 X(1) + + k X(k)则称点则称点X为为 X(1) , X(2) , ,X(k) 的凸组合。的凸组合。凸组合凸组合 凸集凸集D, 点点 X D，若找不到两个若找不到两个不同的点不同的点X(1) , X(2) D

31、 使得使得 X= X(1) +(1- ) X(2) (0 1) 则称则称X为为 D的顶点。的顶点。定义定义3顶点顶点求解线性规划的单纯形法1.5 LP问题的基本解问题的基本解Max Z=cTx Ax =b x 0 0A Amn 满秩满秩 x= (x1 xn)T a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amnP1 Pm Pm+1 PnBN(m n) r(A)=m , 至少有一个至少有一个m阶子式不为阶子式不为0定义定义4：基：基(基阵基阵) 由由A中一个子矩阵中一个子矩阵B是可是可逆矩阵，则方阵逆矩阵，则方阵B称为称为LP问题的一个基。问

32、题的一个基。A= (P1 Pm Pm+1 Pn )=(B N) 基向量基向量 非基向量非基向量X= (x1 xm xm+1 xn )T=(XB XN)T 基变量基变量 非基变量非基变量 XB XN基、基变量、非基变量=目标函数目标函数约束条件约束条件行列式行列式0基基右边常数右边常数AX=b的求解的求解A=(B N)X=(XB XN )T XB XN(B N) = bBXB +NXN=bBXB =b-NXNXB = B-1 b - B-1N XN定义定义4：基本解基本解对应于基对应于基B，X=为为AX=b的一个解。的一个解。B-1 b 0定义定义5：基本可行解基本可行解基基B，基本解，基本解X

33、=若若B-1 b 0 0，称基，称基B B为为可行基可行基。若其基本解是最。若其基本解是最优解，成为优解，成为最优基本解最优基本解，相应的基为，相应的基为最优基最优基 B-1 b 0 基本解中最多有基本解中最多有m个非零分量。个非零分量。 基本解的数目不超过基本解的数目不超过Cnm = 个。个。n!m!(n-m)!max z= 2x1 +3x2 +x3 s.t. x1 +3x2 +x3 15 2x1 +3x2 -x3 18 x1 -x2 +x3 3 x1, x2, x3 0 st x1 +3x2 +x3 +x4 =15 2x1 +3x2 -x3 +x5 =18 x1 -x2 +x3 +x6 =

34、3 x1, x2, x3, x4, x5, x6 0 例：x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量基变量x1、x2、x3，非基变量，非基变量x4、x5、x6基本解为（基本解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基本可行解，表示可行域的一个极点。是基本可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=20 x1+3x2+x4=152x1+3x2=18x1-x2=3基变量基变量x1、x2、x4，非基变量，非基变量x3、x5、x6基本

35、解为基本解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基本可行解，表示可行域的一个极点。是基本可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+3x2=152x1+3x2+x5=18x1-x2=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量基变量x1、x2、x5，非基变量，非基变量x3、x4、x6基本解为（基本解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基本解，但不

36、是可行解，不是一个极点。是基本解，但不是可行解，不是一个极点。x1+3x2=152x1+3x2=18x1-x2+x6=3基变量基变量x1、x2、x6，非基变量，非基变量x3、x4、x5基本解为（基本解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基本可行解，表示可行域的一个极点。是基本可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3+x4=153x2-x3=18-x2+x3=3基变量基变量x2、x3、x4，非基变量，非基变量x1、x5、x6基本解为基本解

37、为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基本解，但不是可行解。是基本解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3+x5=18-x2+x3=3基变量基变量x1、x2、x3，非基变量，非基变量x4、x5、x6基本解为（基本解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基本可行解，表示可行域的一个极点。是基本可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x

38、1-x2+x3+x6=33x2+x3=153x2-x3=18-x2+x3+x6=3基变量基变量x1、x2、x3，非基变量，非基变量x4、x5、x6基本解为基本解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基本解但不是可行解。是基本解但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3 (LP)问题的基本可行解问题的基本可行解 可行域的顶点。可行域的顶点。 若若(LP)问题有最优解，必定可以在基本可问题有最优解，必定可以在基本可行解行解(顶点顶点)达到。达到。LP问题解的性质问题解的性质若若(LP)问题有可

39、行解，则可行解集问题有可行解，则可行解集(可行域可行域)是凸集是凸集(可能有界，也可能无界可能有界，也可能无界)，有有限个，有有限个顶点。顶点。基本解、基本可行解与顶点max z=x1+3x2Ds.t. x1+ x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1,x2,x3,x40 x1=0 E O x2=0 AOABCDE基变量x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3非基变量x1 x2x2 x3x3 x4x1 x4x1 x3x2 x4xj 40 选选x2从从0，x1 =0 x3 =30-2x2 0 0 x2 30/2 x4 =60-2x2 0 0

40、x2 60/2 x5 =24-2x2 0 0 x2 24/2 x2=min(30/2 , 60/2 , 24/2 ) =12x2进基变量，进基变量， x5出基变量。出基变量。B B2 2 = (P3 P4 P2)Z=0+40 x1+50 x2 x3 +2x2 =30-x1 x4+2x2 =60-3x1 2x2=24-x5 1/2 ，代入式，代入式， ，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)(2) 判断判断 400 X

41、(2)不是不是。(3)(3) 选选x1从从0， x5 =0 x3= 6- x1 0 0 x4= 36-3x1 0 0 x2=12 0 0 x1=min( 6/1 , 36/3 ) =6x1进基，进基， x3出基。出基。B3 = (P1 P4 P2 )Z=840-40 x3+15x5x1=6 - x3 + x5 x4= 18+3x3 - 2x5x2=12 - 1/2x5令令x3 =x5 =0 X(3) =(6, 12, 0, 18, 0)TZ(3) =840(2)(2) 150 X(3)不是不是(3)(3) 选选x5从从0， x3 =0 x1=6 +x5 0 0 x4= 18 -2x5 0 0

42、x2=12 - 1/2 x5 0 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令令x3 =x4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =9750(0,0)x x2 2x x1 1A A D DC CB B(0,12)(6,12)(15,7.5)三、单纯形表三、单纯形表 c1 c2 cm cm+1 cm

43、+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 annmiiibcZ10miijijjacc1 Z0 0 0 0 m+1 m+k n例例1Max Z=40 x1 +50 x2 x1 +2x2 +x3 =30 3x1 +2x2 +x4 =60 2x2 +x5 =24 x1 x5 0 0 40 50 0 0 0 40 50 0 0 0 CB

44、XB b x1 x2 x3 x4 x5 0 0 x3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 x4 6060 3 3 2 0 1 0 302 0 1 0 300 0 x5 24 0 (2) 0 0 1 12 24 0 (2) 0 0 1 12 0 40 50 0 0 0 0 40 50 0 0 00 0 x3 6 (1) 0 1 0 -1 66 (1) 0 1 0 -1 60 0 x4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 x2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 600 40 0 0 0 -25 60

45、0 40 0 0 0 -2540 40 x1 6 1 0 1 0 -16 1 0 1 0 -10 0 x4 18 0 0 -3 1 (2) 9 18 0 0 -3 1 (2) 950 50 x2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24840 0 0 -40 0 15840 0 0 -40 0 1540 40 x1 15 1 0 -1/2 1/2 0 15 1 0 -1/2 1/2 0 0 0 x5 9 0 0 -3/2 1/2 1 9 0 0 -3/2 1/2 1 50 50 x2 15/2 0 1 3/4 -1/4 0 15/2 0 1 3/4 -1/4 0本

46、问题的最优解本问题的最优解 X=(15, 15/2, 0, 0, 9)T Z=975 40 50 0 0 0 40 50 0 0 0 CB XB b x1 x2 x3 x4 x5 975 0 0 -35/2 -15/2 0975 0 0 -35/2 -15/2 0例例2 2 max Z = x1 +2x2x1 4x2 3x1+2x2 8 x1 , x2 0 0 x1+x3 = = 4x2+x4 = = 3x1+2x2+x5= = 8 x1 x5 0 0 1 2 0 0 0 1 2 0 0 0 CB XB b x1 x2 x3 x4 x50 0 x3 4 1 0 1 0 0 4 1 0 1 0

47、00 0 x4 3 0 (1) 0 1 03 0 (1) 0 1 00 0 x5 8 1 2 0 0 1 8 1 2 0 0 1 0 1 2 0 0 0 0 1 2 0 0 00 0 x3 4 1 0 1 0 0 4 1 0 1 0 0 2 2 x2 3 0 1 0 1 0 3 0 1 0 1 0 0 0 x5 2 2 (1) 0 0 -2 1 (1) 0 0 -2 1 ( (接下表接下表) ) 6 1 0 0 -2 06 1 0 0 -2 0 1 2 0 0 0 1 2 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x3 2 0 0 1 (2) -1 2 0 0 1 (2

48、) -12 2 x2 3 0 1 0 1 03 0 1 0 1 01 1 x1 2 1 0 0 -2 1 2 1 0 0 -2 1 8 0 0 0 0 -1 8 0 0 0 0 -10 0 x4 1 0 0 1/2 1 -1/2 1 0 0 1/2 1 -1/2 2 2 x2 2 0 1 -1/2 0 1/2 2 0 1 -1/2 0 1/2 1 1 x1 4 4 1 0 1 0 0 1 0 1 0 0 8 0 0 0 0 -18 0 0 0 0 -1X X(1)(1)= = (2,3) Z Z(1)(1)=8 =8 X X(2)(2)= = (4,2) Z Z(2)(2)=8=8无穷多解无穷

49、多解全部解：全部解：X X= + (1-) (0 1)2 4 3 2例例3 3 求求 max Z = x1 x2+x3 3x5x2+x3 x4+2x5 = = 6x1+2x2 2x4 = = 52x2 +x4+3x5 +x6 = = 8x1 x6 0 0 1 -1 1 0 -3 0 1 -1 1 0 -3 0 CB XB b x1 x2 x3 x4 x5 x61 1 x3 6 0 1 1 -1 2 0 6 0 1 1 -1 2 01 1 x1 5 1 2 0 -2 0 05 1 2 0 -2 0 00 0 x6 8 0 2 0 1 3 1 8 0 2 0 1 3 1 11 0 -4 0 3 -

50、5 0 11 0 -4 0 3 -5 01 1 x3 14 0 3 1 0 5 1 14 0 3 1 0 5 1 1 1 x1 21 1 6 0 0 6 221 1 6 0 0 6 20 0 x4 8 8 0 2 0 1 3 10 2 0 1 3 1 35 0 -10 0 0 -14 -3 35 0 -10 0 0 -14 -3例例4 4 max Z = 10 x1 + 12x23x1+4x2 64x1+ x2 23x1 +2x2 3x1 , x2 0 0 10 12 0 0 010 12 0 0 0 XB b x1 x2 x3 x4 x5 i i 0 x3 6 3 (4) 1 0 0 3/2

51、 6 3 (4) 1 0 0 3/20 0 x4 2 4 1 0 1 0 2/12 4 1 0 1 0 2/10 0 x5 3 3 2 0 0 1 3/2 3 3 2 0 0 1 3/2 0 10 12 0 0 0 0 10 12 0 0 0 12 12 x2 3/2 3/4 1 1/4 0 0 23/2 3/4 1 1/4 0 0 20 0 x4 1/2 13/4 0 -1/4 1 0 2/131/2 13/4 0 -1/4 1 0 2/130 0 x5 0 0 (3/2) 0 -1/2 0 1 0(3/2) 0 -1/2 0 1 0 18 1 0 -3 0 0 18 1 0 -3 0 0

52、12 12 x2 3/2 0 1 1/2 0 -1/23/2 0 1 1/2 0 -1/20 0 x4 1/2 0 0 5/6 1 -13/6 1/2 0 0 5/6 1 -13/6 10 10 x1 0 1 0 -1/3 0 2/30 1 0 -1/3 0 2/3 18 0 0 -8/3 0 -2/3 18 0 0 -8/3 0 -2/3 退化解退化解X *= (0, 3/2, 0, 1/2, 0)TZmax = 18例例5 5：max Z = 4x1 +x2 -x1+ x2 2 x1 4x2 4 x1 2x2 8x1 , x2 0 4 1 0 0 0 CB XB b x1 x2 x3 x4

53、 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 00 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本问题无界。本问题无界。x1x2OZ=0四、四、 初始基本可行解的求法初始基本可行解的求法(一一)、大、大M法：法：判定无解条件：当进行到最优表时，仍有人工变量判定无解

54、条件：当进行到最优表时，仍有人工变量在基中，且在基中，且0，则说明原问题无可行解。则说明原问题无可行解。例例1 1：max Z = 6x1 +4x2 2x1 +3x2 1004x1 +2x2 120 x1 = =14 x2 22x1 x2 0max Z = 6x1+4x22x1 +3x2 +x3 = =1004x1 +2x2 +x4 = =120 x1 = =14 x2 - x5 = 22x1 x5 0max Z = 6x1+4x2-Mx6 -Mx72x1 +3x2 +x3 = =1004x1 +2x2 +x4 = =120 x1 +x6 = =14 x2 - x5 +x7 = 22x1 x7

55、 0 6 4 0 0 0 - 6 4 0 0 0 - M - - M CB XB b X1 X2 X3 X4 X5 X6 X70 0 X3 100 2 3 1 0 0 0 0 100 2 3 1 0 0 0 0 0 0 X4 120120 4 4 2 0 1 0 0 0 2 0 1 0 0 0 -M X6 14 (1) 0 0 0 0 1 0 14 (1) 0 0 0 0 1 0 -M X7 22 0 1 0 0 -1 0 1 -36 -36 M M +6 +6 M +4 0 0 - +4 0 0 - M 0 0 0 00 0 X3 72 0 3 1 0 0 -2 0 72 0 3 1 0 0

56、 -2 0 0 0 X4 64 0 64 0 2 0 1 0 -4 0 2 0 1 0 -4 0 6 X1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 -M X7 22 0 (1) 0 0 -1 0 1 8484-22M 0 0 M+4 0 0 - 0 0 -M 6-M 00 0 x3 6 0 0 1 0 (3) -2 -3 6 0 0 1 0 (3) -2 -3 0 0 x4 2020 0 0 0 0 0 1 2 -4 -2 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 4 x2 22 0 1 0 0 -1 0

57、1 172 172 0 0 0 0 4 0 0 4 6- 6-M 4- 4-M0 0 x5 2 0 0 1/3 0 1 -2/3 -1 2 0 0 1/3 0 1 -2/3 -1 0 0 x4 1 16 0 6 0 0 -2/3 1 0 -8/3 0 0 -2/3 1 0 -8/3 0 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 4 x2 24 0 1 1/3 0 0 -2/3 -2 180180 0 0 0 -4/3 0 -4/3 0 0 -M-10/3 -MCB XB b b x1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x

58、x7 76 4 0 0 0 - 6 4 0 0 0 - M - - M1.7 1.7 线性规划的对偶问题线性规划的对偶问题Duality一、对偶问题一、对偶问题某厂生产甲、乙两种产品，消耗A、B两种原材料。生产一件甲产品可获利2元，生产乙产品获利3元。问在以下条件下应如何安排生产获利最大？甲乙 总量设备台时设备台时原材料原材料A原材料原材料B140204 81612目标函数：目标函数： MAX Z = 2X1+3X2约束条件：约束条件： X1+2X2 8 4X1+ 16 4X212 X1, X202 同样地乙产品也有：同样地乙产品也有：2Y +4Y 3 一、对偶问题一、对偶问题 全部出让或出租

59、的总收入为全部出让或出租的总收入为 W = 8YW = 8Y +16Y+16Y +12Y+12Y所有产品的利润条件，使其总收入具有竞争力的，因此所有产品的利润条件，使其总收入具有竞争力的，因此，W W需要求解最小值。需要求解最小值。 因此有线性规划模型：因此有线性规划模型： 目标函数：目标函数： min W = 8Ymin W = 8Y +16Y+16Y +12Y+12Y222Y2Y +4Y+4Y 3300一、对偶问题一、对偶问题 二、对偶关系二、对偶关系原问题原问题 (primal problem)（P）：）：max z = CTXAX bX 0对偶问题对偶问题 (dual problem)

60、（D）：）：min w = bTYATY CY 0二、对偶关系二、对偶关系 （P P）（D D）目标函数maxmin目标系数Cb约束右端bC系数矩阵AAT函数约束与变量约束第k个约束 第k个变量约束个数=变量个数（非）规范约束 非负（正）变量等式约束 自由变量二、对偶关系二、对偶关系例子例子: :min z = 3x1 + 2x2 x3s.t. 2x1 + x2 + 3x3 23x1 - 5x2 5 x1 + x2 + x3 = 1x1 0, x2自由自由, x3 0二、对偶关系二、对偶关系其对偶问题其对偶问题: :max w = 2y1 + 5y2 + y3s.t. 2y1 + 3y2 +