运筹学线性规划.ppt

运筹学线性规划运筹学线性规划举例例例（线材合理下料问题）（线材合理下料问题）某工厂要做某工厂要做100套钢套钢架，每套用长为架，每套用长为2.9m,2.1m,1.5m的圆钢各一的圆钢各一根。已知原料每根长根。已知原料每根长7.4m，问：应如何下料，问：应如何下料，可使所用原料最省？可使所用原料最省？例例（机器负荷分配问题）（机器负荷分配问题）某种机器可以在高、某种机器可以在高、低两种负荷下进行生产。高负荷年产量低两种负荷下进行生产。高负荷年产量8，年，年完好率完好率0.7；低负荷年产量；低负荷年产量5，年完好率，年完好率0.9。现有完好机器现有完好机器1000台，需制定一个台，需制定一个5年计划，年计划，以决定每年安排多少台机器投入高、低负荷以决定每年安排多少台机器投入高、低负荷生产，使生产，使5年的总产量最大年的总产量最大。消防站选址问题消防站选址问题某城市的消防总部将全市划分为某城市的消防总部将全市划分为11个防火区，设有个防火区，设有4个个消防救火站。下图消防救火站。下图表示消防站，表示消防站，111表示防火区域，表示防火区域，图中连线表示各地区由哪个消防站负责。问题：可否减少消图中连线表示各地区由哪个消防站负责。问题：可否减少消防站的数目，仍能同样负责各地区的防火任务？如果可以，防站的数目，仍能同样负责各地区的防火任务？如果可以，应关闭哪个消防站？应关闭哪个消防站？12345678910111234绪绪论论产生于二战时期，运筹学（产生于二战时期，运筹学（OperationalResearch)直译为直译为“运作研运作研究究”。20世纪世纪60年代，在工业、农业、社会等各领域得到广泛应用年代，在工业、农业、社会等各领域得到广泛应用在我国，在我国，20世纪世纪50年代中期由钱学森等引入年代中期由钱学森等引入运用数学方法，为决策者进行最优决策提供科学依据的一门运用数学方法，为决策者进行最优决策提供科学依据的一门应用应用科学科学。运筹学的特点运筹学的特点面向管理和工程实际问题面向管理和工程实际问题应用数学方法建立数学模型应用数学方法建立数学模型一定意义下的优化一定意义下的优化一、运筹学的产生与发展一、运筹学的产生与发展二、学科性质二、学科性质三、运筹学的分支三、运筹学的分支线性规划线性规划非线性规划非线性规划图论与网络分析图论与网络分析存储论存储论决策论决策论排队论排队论对策论（博弈论）对策论（博弈论）四、四、管理管理运筹学运筹学的工作程序的工作程序明确问题明确问题问题分类问题分类建立数学模型建立数学模型求解数学模型求解数学模型结果分析结果分析实施实施五 运筹学与决策管理就是决策管理就是决策 从这个意义上说，运筹学是典型的辅助决策的学科从这个意义上说，运筹学是典型的辅助决策的学科 决策的基本问题是发现问题和解决问题决策的基本问题是发现问题和解决问题发现问题需要决策者丰富的经验、广博的知识和敏锐的观察判断能力发现问题需要决策者丰富的经验、广博的知识和敏锐的观察判断能力以及深入细致的调查研究。运筹学可提供某些辅助分析，但主要不针对以及深入细致的调查研究。运筹学可提供某些辅助分析，但主要不针对此问题。此问题。解决问题首先要提出方案，方案的创造同样是决策者才干的体现。解决问题首先要提出方案，方案的创造同样是决策者才干的体现。在解决问题中有两类问题是值得注意的：在解决问题中有两类问题是值得注意的：有些问题的解决方案在既定的准则下隐含在一系列限制条件中，需要有些问题的解决方案在既定的准则下隐含在一系列限制条件中，需要一些方法一些方法“找出找出”这个方案；这个方案；有些问题可能提出几个（有限个）方案，需要一些方法评价和优选这有些问题可能提出几个（有限个）方案，需要一些方法评价和优选这些方案；些方案；运筹学在以上两类问题中是很有用的。运筹学在以上两类问题中是很有用的。课程教材：课程教材：吴育华吴育华,杜纲，管理科学基础（修订版），天津大学出杜纲，管理科学基础（修订版），天津大学出版社。版社。主要参考书：主要参考书：1钱颂迪等，运筹学，北京：清华大学出版社，钱颂迪等，运筹学，北京：清华大学出版社，1990；2胡运权，运筹学教程，北京：清华大学出版社，胡运权，运筹学教程，北京：清华大学出版社，1998；3（加）（加）PeterCBell,韩伯棠等译，韩伯棠等译，管理科学（运筹学）管理科学（运筹学）战略角度的审视，战略角度的审视，机械工业出版社，机械工业出版社，2000；4丁以中主编，管理科学丁以中主编，管理科学-运用运用Spreadsheet建模和求解，北建模和求解，北京：清华大学出版社，京：清华大学出版社，2003；5美美弗雷德里克弗雷德里克S希利尔（希利尔（FrederickSHillier）,任建标译任建标译,数据、模型与决策（原书名数据、模型与决策（原书名IntroductiontoManagementScience），北京：中国财政经济出版社，），北京：中国财政经济出版社，2004；主要授课内容：主要授课内容：线性规划线性规划*线性目标规划线性目标规划图论与网络分析图论与网络分析*网络计划网络计划*风险型决策风险型决策*库存决策库存决策动态规划动态规划*矩阵对策矩阵对策排队论排队论课程基本要求：课程基本要求：掌握好基本概念、主要模型形式及其特点、必要的算法掌握好基本概念、主要模型形式及其特点、必要的算法原理及简单的计算。原理及简单的计算。所需基础知识：微积分、矩阵、线性方程组、概率基础等所需基础知识：微积分、矩阵、线性方程组、概率基础等班级公共邮箱密码：6个6第一章第一章线性规划线性规划（LinearProgramming，简称，简称LP）1线性规划的模型与图解法线性规划的模型与图解法一、一、LP问题及其数学模型问题及其数学模型例例1某工厂可生产甲、乙两种产品，需消耗煤、电、某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。最大的生产计划。127单价单价300103油油(C)20054电电(B)36049煤煤(A)资源限制资源限制乙乙甲甲产品产品资源资源结构约束条件结构约束条件非负约束条件非负约束条件目标函数目标函数资源资源向量向量（右（右端项）端项）Max（Min）Z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn（=,）b1am1x1+am2x2+amnxn（=,）bmx1，x2，xn0s.t.LP模型的一般形式模型的一般形式课堂练习课堂练习某蓄场每日要为每头牲畜购买饲料，以使其某蓄场每日要为每头牲畜购买饲料，以使其获取所需的获取所需的A、B、C、D四种养分。有关数据如四种养分。有关数据如下表，现饲料可从市场上出售的下表，现饲料可从市场上出售的M、N两种饲料两种饲料中选择，试决定总花费最小的购买方案。（列中选择，试决定总花费最小的购买方案。（列出模型）出模型）ABCD价格价格M0.50.20.30300N0.10.30.40.2200每头每头日需日需10587养分养分饲料饲料课堂练习课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所需的某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四四种养分。有关数据如下表，现饲料可从市场上出售的种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选两种饲料中选择，试决定总花费最小的购买方案。（列出模型）择，试决定总花费最小的购买方案。（列出模型）ABCD价格价格M0.50.20.30300N0.10.30.40.2200每头日需每头日需10587养分养分饲料饲料答案：答案：设购买设购买M饲料饲料x1，N饲料饲料x20.5x1+0.1x2100.2x1+0.3x250.3x1+0.4x280.2x27x1,x20s.t.MinZ=300 x1+200 x2二、线性规划的图解法二、线性规划的图解法1.步骤步骤（1）作约束的图形）作约束的图形可行域可行域可行解的集合可行解的集合先作非负约束先作非负约束再作资源约束再作资源约束9x1+4x2=3604x1+5x2=2003x1+10 x2=300公共部分，即为可行域公共部分，即为可行域例：煤电油例例：煤电油例MaxZ=7x1+12x29x1+4x23604x1+5x22003x1+10 x2300 x1,x20s.t.x1x240206080100204060801000（2）作目标函数的等值线）作目标函数的等值线给给z不同的值，作相应直线，判断出不同的值，作相应直线，判断出z增大时，直线的移动方向增大时，直线的移动方向将直线向增大方向移动，直至可行域将直线向增大方向移动，直至可行域边界，交点边界，交点X*即为最优解。即为最优解。7x1+12x2=847x1+12x2=168如：令如：令7x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=2003x1+10 x2=300 x1x240206080100204060801000X*=（20，24），），Z*=428最优解：最优解：x1=0，x2=1最优目标值最优目标值z=6练习（练习（自学自学）图解法求解线性规划图解法求解线性规划0 01 12 23 34 41 12 23 34 4x1x2O O-1-1-2-2(1)(2)(3)2.LP 解的几种情况解的几种情况（1）唯一解）唯一解（2）多重最优解）多重最优解（3）无可行解）无可行解注：出现（注：出现（3）、（）、（4）情况时，建模有问题）情况时，建模有问题（4）无有限最优解）无有限最优解图解法的结论：图解法的结论：线性规划的可行域是凸集线性规划的可行域是凸集 线性规划的最优解若存在，必在可行域的在极点获线性规划的最优解若存在，必在可行域的在极点获得得 若在两个极点同时获得，则有无穷多最优解若在两个极点同时获得，则有无穷多最优解凸集凸集不是凸集不是凸集极极点点三三线性规划应用举例线性规划应用举例 例例1 1（线材合理下料问题）（线材合理下料问题）某工厂要某工厂要做做100100套钢架，每套用长为套钢架，每套用长为2.9 m,2.1 2.9 m,2.1 m,1.5 mm,1.5 m的圆钢各一根。已知原料每根长的圆钢各一根。已知原料每根长7.4 m7.4 m，问：应如何下料，可使所用原料，问：应如何下料，可使所用原料最省？最省？2x 2x1 1+x+x2 2+x+x3 3+x+x4 4 =100 =100 2x 2x2 2+x+x3 3 +3x+3x5 5+2x+2x6 6+x+x7 7 =100 =100 x x1 1+x+x3 3+3x+3x4 4+2x+2x6 6+3x+3x7 7+4x+4x8 8=100=100 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6,x,x7 7,x,x8 8 0 0设设 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6,x,x7 7,x,x8 8 分别为上述分别为上述8 8种方案下料的原材料根数，种方案下料的原材料根数，建立如下的建立如下的LPLP模型：模型：最优解为：最优解为：x x1 1=10,x=10,x2 2=50,x=50,x3 3=0,x=0,x4 4=30,x=30,x5 5=0,x=0,x6 6=0,x=0,x7 7=0,x=0,x8 8=0=0min Z=xmin Z=x1 1+x+x2 2+x+x3 3+x+x4 4+x+x5 5+x+x6 6+x+x7 7+x+x8 8s.t.解：解：共有下列共有下列 8 8 种下料方案种下料方案一、线性规划的标准型一、线性规划的标准型MaxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1am1x1+am2x2+amnxn=bmx1，x2，xn0s.t.1、标准形式、标准形式矩阵表示矩阵表示MaxZ=CXAX=bX0s.t.注：标准型中注：标准型中要求要求bi02单纯形法单纯形法2、非标准型、非标准型标准型标准型（1）MinZ=CXMaxZ=-CX（2）约束条件）约束条件例如：例如：9x1+4x23609x1+4x2+x3=360松弛变量松弛变量“”型约束，加松弛变量；型约束，加松弛变量；“”型约束，减松弛变量；型约束，减松弛变量；（3）自由变量）自由变量xj进行变量替换：进行变量替换：xj=xj-xj，其中，其中xj、xj0例、将如下问题化为标准型例、将如下问题化为标准型解解：令：令、第一个约束加松弛变量、第一个约束加松弛变量第二个约束减松弛变量第二个约束减松弛变量、得标准型：得标准型：二、单纯形法的基本方法二、单纯形法的基本方法基本方法：基本方法：确定初始基可行解确定初始基可行解检验是否最优？检验是否最优？转到另一更好的转到另一更好的基可行解基可行解停停YN方法前提：方法前提：模型化为标准型模型化为标准型并保证其他的基变量非负并保证其他的基变量非负基变量和非基变量基变量和非基变量三、单纯形法的步骤三、单纯形法的步骤1.初始可行基初始可行基B0的确定的确定若若A中含有中含有I：B0=I若若A中不含中不含I：人工变量法：人工变量法2.最优性检验最优性检验（1）计算每个）计算每个xj的检验数的检验数（2）若所有）若所有j0，则当前解为最优；，则当前解为最优；否则，至少有否则，至少有k0，转，转3。注注:（1）基变量的检验数必为基变量的检验数必为0；（2）非基变量）非基变量的经济含义的经济含义：非基变量取值由：非基变量取值由0变正，每增加一个单位，使目标值的增加量。变正，每增加一个单位，使目标值的增加量。3.换基迭代（基变换）换基迭代（基变换）（1）进基：取）进基：取对应的对应的Pk进基。进基。（2）出基：取）出基：取对应的对应的Pl出基。出基。得新基，计算新的基可行得新基，计算新的基可行解，转解，转2。保证新解保证新解的可行性的可行性的计算的计算:XBCBB-1bx1x2x3x4x5四、单纯形法的实现四、单纯形法的实现单纯形表单纯形表例例：煤电油例：煤电油例MaxZ=7x1+12x29x1+4x23604x1+5x22003x1+10 x2300 x1,x20s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10 x2+x5=300 x1,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:7x5x4x3x2x1B-1bCBXB四、单纯形法的实现四、单纯形法的实现单纯形表单纯形表例例：煤电油例：煤电油例MaxZ=7x1+12x29x1+4x23604x1+5x22003x1+10 x2300 x1,x20s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10 x2+x5=300 x1,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:790的计算的计算:4030 x5x4x3x2x1B-1bCBXB四、单纯形法的实现四、单纯形法的实现单纯形表单纯形表例例：煤电油例：煤电油例MaxZ=7x1+12x29x1+4x23604x1+5x22003x1+10 x2300 x1,x20s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10 x2+x5=300 x1,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030枢纽枢纽元素元素x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等等行行变变换换502.5001-0.52407.8010-0.43.4000-1.2x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等等行行变变换换502.5001-0.52407.8010-0.43.4000-1.230.820100 x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等等行行变变换换502.5001-0.52407.8010-0.43.4000-1.230.820100 x3x1x2071224010-0.12 0.16201000.4-0.284001-3.12 1.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100以以为为主主元元进进行行初初等等行行变变换换2.5x3x1x2071224010-0.12 0.16201000.4-0.284001-3.12 1.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100X*=(20,24,84,0,0)TZ*=4289x1+4x2=3604x1+5x2=2003x1+10 x2=300 x1x240206080100204060801000(0,0)(40,0)(36.5,10.8)(20,24)(0,30)课堂练习课堂练习用单纯形法求解用单纯形法求解MinS=-x1+2x2x1-x2-2x1+2x26x1,x20s.t.化为标准型化为标准型MaxS=x1-2x2-x1+x2+x3=2x1+2x2+x4=6x1,x40s.t.XBCBB-1bx1x2x3x4x302-1110不考虑不考虑x406120161-2x3080311x11612010-40-1X*=(6,0,8,0)TZ*=-6联系用矩阵表示的单纯形法原理，单纯形表各部分联系用矩阵表示的单纯形法原理，单纯形表各部分内容可如下表示内容可如下表示3线性规划的对偶问题线性规划的对偶问题（DualProgramming）一、对偶问题的提出和模型一、对偶问题的提出和模型1 1、问题的提出、问题的提出煤电油例 今有另厂要购买三种今有另厂要购买三种资源，在原厂可接受的资源，在原厂可接受的条件下，单价多少可使条件下，单价多少可使另厂付费最低？另厂付费最低？MaxZ=7x1+12x29x1+4x23604x1+5x22003x1+10 x2300 x1,x20s.t.设煤电油设煤电油“价格价格”分别为分别为y1,y2,y3MinW=360y1+200y2+300y3s.t.9y1+4y2+3y374y1+5y2+10y312y1,y2,y30DUAL以后将特别讨论这一以后将特别讨论这一“价格价格”的含义的含义2 2、原问题与对偶问题的对应关系、原问题与对偶问题的对应关系MaxZ=CXAXbX0s.t.原问题原问题（P）：对偶问题对偶问题（D）：MinW=bTYATYCTY0s.t.MaxZ=7x1+12x29x1+4x23604x1+5x22003x1+10 x2300 x1,x20s.t.MinW=360y1+200y2+300y3s.t.9y1+4y2+3y374y1+5y2+10y312y1,y2,y30（Y为行向量）为行向量）对称的对偶问题原问题与对偶问题形式上的对应关系对称的对偶问题原问题与对偶问题形式上的对应关系原问题（原问题（P）对偶问题对偶问题（D）目标目标max型型目标目标min型型有有n个变量（非负）个变量（非负）有有n个约束（大于等于）个约束（大于等于）有有m个约束个约束（小于等于）（小于等于）有有m个变量（非负）个变量（非负）价格系数价格系数资源向量资源向量资源向量资源向量价格系数价格系数技术系数矩阵技术系数矩阵技术系数矩阵的转置技术系数矩阵的转置1 1、对称性、对称性二、对偶性质与定理二、对偶性质与定理2 2、弱对偶性、弱对偶性设设X、Y 分别为（分别为（P）、（）、（D）的任一可行解，）的任一可行解，则则一个线性规划的对偶问题的对偶问题恰是原问题；即一个线性规划的对偶问题的对偶问题恰是原问题；即（P）与（）与（D）互为对偶）互为对偶3 3、无界性、无界性若原问题（若原问题（P）无上界，则对偶问题（）无上界，则对偶问题（D）无可行解；同样，）无可行解；同样，若对偶问题（若对偶问题（D）无下界，则原问题（）无下界，则原问题（P）无可行解；）无可行解；（注意：该命题的逆命题不成立。）（注意：该命题的逆命题不成立。）4 4、解的最优性、解的最优性设设 、分别为（分别为（P）与（）与（D）的可行解，且）的可行解，且则则 、分别是原问题（分别是原问题（P）和对偶问题（）和对偶问题（D）的最优）的最优解。解。5 5、对偶定理（强对偶性）、对偶定理（强对偶性）若若（P）有最优解，则有最优解，则（D）也有最优解，且二者最优值相等也有最优解，且二者最优值相等.由该性质的证明中可以得到一个有用的结论：由该性质的证明中可以得到一个有用的结论：若原问题（若原问题（P）有最优解，设最优基为）有最优解，设最优基为B，则则CBB-1是对偶问是对偶问题（题（D）的最优解。）的最优解。6 6、互补松弛定理、互补松弛定理若若 是原问题（是原问题（P）的可行解，）的可行解，是对偶问题（是对偶问题（D）的可行解，）的可行解，那么那么 和和 分别是原问题分别是原问题（P）和对偶问题和对偶问题（D）的最优解的的最优解的充要条件是：充要条件是：可以看出，在原问题（可以看出，在原问题（P）最优解单纯型表中，松弛变）最优解单纯型表中，松弛变量检验数为量检验数为它的负值它的负值CBB-1刚好是对偶问题（刚好是对偶问题（D）的最优解。）的最优解。对于性质对于性质5，进一步联系单纯型表的矩阵表示，进一步联系单纯型表的矩阵表示，三、对偶问题最优解的经济解释三、对偶问题最优解的经济解释影子价格影子价格设设DP其最优值为其最优值为Z*(注：与注：与LP最优值同），则根据最优值同），则根据Z*=bTy*=b1y1*+b2y2*+bmym*Z/bi=yi*简单推导：Y*=(y1*,y2*,，ym*）为对偶问题的最优解，则）为对偶问题的最优解，则yi*表示在原问题表示在原问题LP模型最有解基础上，资源（右端项）模型最有解基础上，资源（右端项）bi对目标函数的边际贡献。即对目标函数的边际贡献。即bi变化变化1个单位对目标函数产个单位对目标函数产生的影响，称生的影响，称yi*为为bi的的影子价格影子价格（shadowprice)。例如：例如：煤电油例的对偶问题的最优解为煤电油例的对偶问题的最优解为Y*=(01.360.52),即煤电油三种资源的影子价格分别为即煤电油三种资源的影子价格分别为0、1.36、0.52，它表明：在所，它表明：在所求出的最优生产方案（甲生产求出的最优生产方案（甲生产20，乙生产，乙生产24，资源煤剩余，资源煤剩余84，资源电，资源电和油无剩余，总收入和油无剩余，总收入428）基础上，资源煤增加）基础上，资源煤增加1单位，目标函数值不单位，目标函数值不变；资源电增加变；资源电增加1单位，目标函数值相应增加单位，目标函数值相应增加1.36；资源油增加；资源油增加1单位，单位，目标函数值相应增加目标函数值相应增加0.52。由原问题所做推导：由原问题所做推导：注意：注意：对偶解（影子价格）的所有应用都是基于这一基本概念。对偶解（影子价格）的所有应用都是基于这一基本概念。影子价格在管理决策中的作用：影子价格在管理决策中的作用：（1）影子价格）影子价格市场价格市场价格在以本章引例为代表的目标函数最大化毛收入这类模型中在以本章引例为代表的目标函数最大化毛收入这类模型中若若影子价格市场价格，则应影子价格市场价格，则应买进该资源买进该资源影子价格市场价格，则应影子价格市场价格，则应卖出该资源卖出该资源（2）影子价格反映了当前优化模型中资源的稀缺）影子价格反映了当前优化模型中资源的稀缺性，性，影子价格越高，则越稀缺。影子价格越高，则越稀缺。例如：煤的影子价格为例如：煤的影子价格为0，则表明有剩余；电的影子价，则表明有剩余；电的影子价格为格为1.36，是三种资源中最大的，则表明电是相对重要，是三种资源中最大的，则表明电是相对重要的。的。（3）在资源不变条件下，增加新产品是否）在资源不变条件下，增加新产品是否合算的评价合算的评价（见灵敏性分析）（见灵敏性分析）4线性规划的灵敏性分析线性规划的灵敏性分析（sensitivityanalysis）1右端项右端项b变化的分析变化的分析（先看后两页图示）（先看后两页图示）对于线性规划对于线性规划在其最优解基础上，在其最优解基础上，设设B为最优基，则为最优基，则由单纯形法由单纯形法b的变化直接影响右的变化直接影响右端项（可行性）而端项（可行性）而不直接影响检验数不直接影响检验数（最优性）（最优性）右端项变化示意右端项变化示意1，某，某个右端项在一定范围变个右端项在一定范围变化，可能不影响最优解化，可能不影响最优解7x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=2003x1+10 x2=300 x1x2402060801002040608010009x1+4x2=320X*=（20，24），），Z*=4287x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=200 x1x2402060801002040608010004x1+5x2=170右端项变化示意右端项变化示意2，某，某个右端项在一定范围变个右端项在一定范围变化，影响最优解化，影响最优解,但可但可能不影响最优基。能不影响最优基。2价格系数价格系数C变化的分析变化的分析3x1+10 x2=300X*=（20，24），），Z*=4287x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=200 x1x240206080100204060801000目标函数系数变化示意，目标函数系数变化示意，目标函数系数在一定范围目标函数系数在一定范围变化，可能不影响最优解变化，可能不影响最优解5 5（线性）整数规划（线性）整数规划Integer Programming(Integer Programming(简称简称IP)IP)一、整数规划的一般模型一、整数规划的一般模型LP:max z=CX AX=b X0IP:max z=CX AX=b X0 X为整数整数规划的解法：分枝定界法或割平面法整数规划的解法：分枝定界法或割平面法基本思想是把一个整数规划问题化为一基本思想是把一个整数规划问题化为一系列的线性规划问题来求解系列的线性规划问题来求解整数规划的分类：整数规划的分类：纯整数规划：所有变量都限制为整数纯整数规划：所有变量都限制为整数 混合整数规划：仅部分变量限制为整数混合整数规划：仅部分变量限制为整数 0-10-1整数规划：变量的取值仅限于整数规划：变量的取值仅限于0 0或或1 1 例例 人力资源分配的问题人力资源分配的问题 某昼夜服务的公交线路每天各时间段内所需司机和乘某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员足工作需要，又配备最少司机和乘务人员?班次班次时间时间所需人数所需人数16 6：00 1000 10：00006021010：00 1400 14：00007031414：00 1800 18：00006041818：00 2200 22：00005052222：00 200 2：00002062 2：00 600 6：000030 解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘务人班次时开始上班的司机和乘务人员数员数,于是于是LPLP模型为模型为:x x1 1+x+x6 6 60 60 x x1 1+x+x2 2 70 70 x x2 2+x+x3 3 60 60 x x3 3+x+x4 4 50 50 x x4 4+x+x5 5 20 20 x x5 5+x+x6 6 30 30 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6 0 0且为整数且为整数min z=xmin z=x1 1+x+x2 2+x+x3 3+x+x4 4+x+x5 5+x+x6 6 最优解：最优解：X*=(60，10，50，0，30，0）T，Z*=150二、二、0-10-1整数规划整数规划选址问题选址问题指派问题指派问题固定费用问题固定费用问题背包问题背包问题1.投资场所的选址问题投资场所的选址问题某城市拟在东、西、南三区设立商业网点，备选位置有某城市拟在东、西、南三区设立商业网点，备选位置有A1A7共共7个，如果选个，如果选Ai，估计投资为，估计投资为bi元，利润为元，利润为ci元，要元，要求总投资不超过求总投资不超过B元，规定元，规定东区：东区：A!、A2、A3中至多选中至多选2个个西区：西区：A4、A5中至少选一个中至少选一个南区：南区：A6、A7中至少选一个中至少选一个问如何设点使总利润最大？问如何设点使总利润最大？1，Ai被选中被选中0，Ai没被选中没被选中解：令解：令xi=maxz=xi=0或或1，i=1,7bixiBi=17x1+x2+x32x4+x51x6+x71s.t.课堂练习课堂练习1:某钻井队要从某钻井队要从S1S10共共10个井位中确定五个钻个井位中确定五个钻井探油，如果选井探油，如果选Si，估计钻探费用为，估计钻探费用为ci元，并且元，并且井位选择上要满足下列条件：井位选择上要满足下列条件：（1）或选择或选择S1和和S7，或选择，或选择S8;（2）选择了选择了S3或或S4就不能选择就不能选择S5，反，反过来也一样过来也一样;（3）在在S5，S6，S7，S8中最多只能选中最多只能选两个。两个。问如何选择井位使总费用最小？问如何选择井位使总费用最小？课堂练习课堂练习1:某钻井队要从某钻井队要从S1S10共共10个井位中确定五个钻井探油，个井位中确定五个钻井探油，如果选如果选Si，估计钻探费用为，估计钻探费用为ci元，并且井位选择上要满足下列条件：元，并且井位选择上要满足下列条件：（1）或选择）或选择S1和和S7，或选择，或选择S8（2）选择了）选择了S3或或S4就不能选择就不能选择S5，反过来也一样，反过来也一样（3）在）在S5，S6，S7，S8中最多只能选两个中最多只能选两个问如何选择井位使总费用最小？问如何选择井位使总费用最小？1，Si被选中被选中0，Si没被选中没被选中解：令解：令xi=min z=s.t.或 1，i=1,10某篮球队有某篮球队有8名队员，其身高和专长如下表，现要选名队员，其身高和专长如下表，现要选拔拔5名球员上场参赛，要求：名球员上场参赛，要求：（1）中锋只有）中锋只有1人上场人上场（2）后卫至少有一人上场）后卫至少有一人上场（3）只有）只有2号上场，号上场，6号才上场号才上场要求平均身高最高，应如何选拔队员？要求平均身高最高，应如何选拔队员？课堂练习课堂练习2:1，队员队员i被选中被选中0，队员，队员i没被选中没被选中解：令解：令xi=max z=或 1，i=1,8s.t.某篮球队有某篮球队有8名队员，其身高和专长如下表，现要选名队员，其身高和专长如下表，现要选拔拔5名球员上场参赛，要求：名球员上场参赛，要求：（1）中锋只有）中锋只有1人上场人上场（2）后卫至少有一人上场）后卫至少有一人上场（3）只有）只有2号上场，号上场，6号才上场号才上场要求平均身高最高，应如何选拔队员？要求平均身高最高，应如何选拔队员？2.指派问题指派问题例：例：有一份中文说明书，需译成英、日、德、俄四种文字，有一份中文说明书，需译成英、日、德、俄四种文字，分别记作任务分别记作任务E、J、G、R，现有甲、乙、丙、丁四人，他们，现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种说明书所需的时间如下表所示，将中文说明书翻译成不同语种说明书所需的时间如下表所示，问应指派何人去完成何项任务，使所需总时间最少？问应指派何人去完成何项任务，使所需总时间最少？问题描述：问题描述：n项任务可由项任务可由n个人完成，由于专长不同，各人完个人完成，由于专长不同，各人完成各任务的时间也不同，求最优安排。成各任务的时间也不同，求最优安排。要求：要求：每人只能完成一项任务，每项任务只能由一人完成。每人只能完成一项任务，每项任务只能由一人完成。x x1111+x x1212+x x1313+x x1414=1 (=1 (甲只能干一项工作甲只能干一项工作)x x2121+x x2222+x x2323+x x2424=1 (=1 (乙只能干一项工作乙只能干一项工作)x x3131+x x3232+x x3333+x x3434=1 (=1 (丙只能干一项工作丙只能干一项工作)x x4141+x x4242+x x4343+x x4444=1 (=1 (丁只能干一项工作丁只能干一项工作)x x1111+x x2121+x x3131+x x4141=1 (E=1 (E任务只能一人干任务只能一人干)x x1212+x x2222+x x3232+x x4242=1 (J=1 (J任务只能一人干任务只能一人干)x x1313+x x2323+x x3333+x x4343=1 (G=1 (G任务只能一人干任务只能一人干)x x1414+x x2424+x x3434+x x4444=1 (R=1 (R任务只能一人干任务只能一人干)x xijij=0 =0 或或 1 1，i,j i,j=1,2,3,4=1,2,3,4min z=2min z=2x x1111+15+15x x1212+13+13x x1313+4+4x x1414+10+10 x x2121+4+4x x2222+14+14x x2323+15+15x x2424 +9 +9x x3131+14+14x x3232+16+16x x3333+13+13x x3434+7+7x x41 41+8+8x x4242+11+11x x4343+9+9x x44441，指派第指派第i人去完成第人去完成第j项任务项任务0，不指派第不指派第i人去完成第人去完成第j项任务项任务解：令解：令xij=课堂练习课堂练习:P57例例2.23指派问题可以一般化表述为有指派问题可以一般化表述为有n个人个人n项工作，已知第项工作，已知第i个人做第个人做第j项工作项工作的费用为的费用为cij，现如何分派任务，使一个人只做一项工作，一项工作只，现如何分派任务，使一个人只做一项工作，一项工作只由一个人完成，而且总费用最小。由一个人完成，而且总费用最小。以以4个人个人4项工作的指派问题为例，该问题需用项工作的指派问题为例，该问题需用4416个个01变量，即变量，即设设把这些变量和已知费用系数分别排成一把这些变量和已知费用系数分别排成一44矩阵，分别称为解矩阵和费用矩阵