《运筹学线性规划》

运筹学

.举例例（线材合理下料问题）某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？例（机器负荷分配问题）某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。.消防站选址问题

某城市的消防总部将全市划分为11个防火区，设有4个消防救火站。下图①~④表示消防站，1~11表示防火区域，图中连线表示各地区由哪个消防站负责。问题：可否减少消防站的数目，仍能同样负责各地区的防火任务？如果可以，应关闭哪个消防站？12345678910111234.绪论产生于二战时期，运筹学（OperationalResearch)直译为“运作研究”。

20世纪60年代，在工业、农业、社会等各领域得到广泛应用在我国，20世纪50年代中期由钱学森等引入

运用数学方法，为决策者进行最优决策提供科学依据的一门应用科学。运筹学的特点

面向管理和工程实际问题应用数学方法建立数学模型一定意义下的优化一、运筹学的产生与发展二、学科性质.三、运筹学的分支线性规划非线性规划图论与网络分析存储论决策论排队论对策论（博弈论）….四、管理运筹学的工作程序明确问题问题分类建立数学模型求解数学模型结果分析实施.五运筹学与决策管理就是决策

从这个意义上说，运筹学是典型的辅助决策的学科

决策的基本问题是发现问题和解决问题发现问题需要决策者丰富的经验、广博的知识和敏锐的观察判断能力以及深入细致的调查研究。运筹学可提供某些辅助分析，但主要不针对此问题。解决问题首先要提出方案，方案的创造同样是决策者才干的体现。

在解决问题中有两类问题是值得注意的：有些问题的解决方案在既定的准则下隐含在一系列限制条件中，需要一些方法“找出”这个方案；有些问题可能提出几个（有限个）方案，需要一些方法评价和优选这些方案；运筹学在以上两类问题中是很有用的。.课程教材：吴育华,杜纲，管理科学基础（修订版），天津大学出版社。主要参考书：[1]钱颂迪等，运筹学，北京：清华大学出版社，1990；[2]胡运权，运筹学教程，北京：清华大学出版社，1998；[3]（加）PeterCBell,韩伯棠等译，管理科学（运筹学）—战略角度的审视，机械工业出版社，2000；[4]丁以中主编，管理科学---运用Spreadsheet建模和求解，北京：清华大学出版社，2003；[5][美]弗雷德里克·S·希利尔（FrederickSHillier）,任建标译,数据、模型与决策（原书名IntroductiontoManagementScience），北京：中国财政经济出版社，2004；.主要授课内容：线性规划*线性目标规划图论与网络分析*网络计划*风险型决策*库存决策动态规划*矩阵对策

排队论课程基本要求：掌握好基本概念、主要模型形式及其特点、必要的算法原理及简单的计算。所需基础知识：微积分、矩阵、线性方程组、概率基础等.班级公共邮箱guanliyunchou@密码：6个6.第一章线性规划（LinearProgramming，简称LP）§1线性规划的模型与图解法一、LP问题及其数学模型例1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。127单价300103油(C)20054电(B)36049煤(A)资源限制乙甲产品资源....结构约束条件非负约束条件目标函数资源向量（右端项）.Max（Min）Z=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn

≤（=,≥）b1……am1x1+am2x2+…+amnxn

≤（=,≥）bmx1，x2，…，xn≥0s.t.

LP模型的一般形式.......课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0300N0.2200每头日需10587养分饲料.课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0300N0.2200每头日需10587养分饲料答案：设购买M饲料x1，N饲料x20.5x1+0.1x2≥100.2x1+0.3x2≥50.3x1+0.4x2≥80.2x2≥7x1,x2≥0s.t.MinZ=300x1+200x2.二、线性规划的图解法1.步骤（1）作约束的图形——可行域可行解的集合①先作非负约束②再作资源约束9x1+4x2=3604x1+5x2=2003x1+10x2=300公共部分，即为可行域例：煤电油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.x1x240206080100204060801000.（2）作目标函数的等值线①给z不同的值，作相应直线，判断出z增大时，直线的移动方向②将直线向增大方向移动，直至可行域边界，交点X*即为最优解。7x1+12x2=847x1+12x2=168如：令7x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=2003x1+10x2=300x1x240206080100204060801000X*=（20，24），Z*=428.最优解：x1=0，x2=1最优目标值z=6练习（自学）图解法求解线性规划012341234x1x2O-1-2(1)(2)(3).2.LP解的几种情况（1）唯一解（2）多重最优解（3）无可行解注：出现（3）、（4）情况时，建模有问题（4）无有限最优解.图解法的结论：线性规划的可行域是凸集线性规划的最优解若存在，必在可行域的在极点获得若在两个极点同时获得，则有无穷多最优解凸集不是凸集极点.三线性规划应用举例例1（线材合理下料问题）某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？.2x1+x2+x3+x4=1002x2+x3+3x5+2x6+x7=100x1++x3+3x4++2x6+3x7+4x8=100x1,x2,x3,x4,x5,x6,x7,x8≥0设x1,x2,x3,x4,x5,x6,x7,x8分别为上述8种方案下料的原材料根数，建立如下的LP模型：最优解为：

x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0minZ=x1+x2+x3+x4+x5+x6+x7+x8s.t.解：共有下列8种下料方案.一、线性规划的标准型MaxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn

=b1…………am1x1+am2x2+…+amnxn

=bmx1，x2，…，xn≥0s.t.1、标准形式矩阵表示MaxZ=CXAX=bX≥0s.t.注：标准型中要求bi≥0§2单纯形法.2、非标准型标准型（1）MinZ=CXMaxZ'=-CX（2）约束条件例如：9x1+4x2≤3609x1+4x2+x3=360松弛变量“≤”型约束，加松弛变量；“≥”型约束，减松弛变量；（3）自由变量xj进行变量替换：xj=xj'

-xj''，其中xj'

、xj''≥0.例、将如下问题化为标准型解：令、第一个约束加松弛变量第二个约束减松弛变量、、得标准型：.二、单纯形法的基本方法基本方法：确定初始基可行解检验是否最优？转到另一更好的基可行解停YN方法前提：模型化为标准型..并保证其他的基变量非负...基变量和非基变量....三、单纯形法的步骤1.初始可行基B0的确定若A中含有I：B0=I若A中不含I：人工变量法.2.最优性检验（1）计算每个xj的检验数（2）若所有σj≤0，则当前解为最优；否则，至少有σk>0，转3。注:（1）基变量的检验数必为0；（2）非基变量σ的经济含义：非基变量取值由0变正，每增加一个单位，使目标值的增加量。.3.换基迭代（基变换）（1）进基：取对应的Pk进基。（2）出基：取对应的Pl出基。得新基，计算新的基可行解，转2。保证新解的可行性.σ的计算:XBCBB-1bx1x2x3x4x5θσ四、单纯形法的实现——单纯形表例：煤电油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0s.t.化为标准型x3x4x5000360200300943451010001000112000单纯形表:7.σθx5x4x3x2x1B-1bCBXB四、单纯形法的实现——单纯形表例：煤电油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0s.t.化为标准型x3x4x5000360200300943451010001000112000单纯形表:790θ的计算:4030.σθx5x4x3x2x1B-1bCBXB四、单纯形法的实现——单纯形表例：煤电油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0s.t.化为标准型x3x4x5000360200300943451010001000112000单纯形表:7904030[]枢纽元素.σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表:7904030[]x3x4x20012300.31000.1σ以10为主元进行初等行变换502.5001-0.52407.8010-0.43.4000-1.2.σθx5x4x3x2x1B-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.120.16σ201000.4-0.284001-3.121.16000-1.36-0.52σσθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表:7904030[]x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100[]以为主元进行初等行变换2.5.x3x1x2071224010-0.120.16σ201000.4-0.284001-3.121.16000-1.36-0.52σσθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表:7904030[]x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100[]∴X*=(20,24,84,0,0)TZ*=428.9x1+4x2=3604x1+5x2=2003x1+10x2=300x1x240206080100204060801000(0,0)(40,0)(36.5,10.8)(20,24)(0,30).课堂练习用单纯形法求解MinS=-x1+2x2x1-x2≥

-2x1+2x2≤6x1,x2≥0s.t.化为标准型MaxS´=x1-2x2-x1+x2+x3=

2x1+2x2+x4=

6x1,…,x4≥0s.t.XBCBB-1bx1x2x3x4θx302-1110不考虑x406[1]2016σ1-2x3080311x1161201σ0-40-1∴X*=(6,0,8,0)TZ*=-6..

联系用矩阵表示的单纯形法原理，单纯形表各部分内容可如下表示..§3线性规划的对偶问题（DualProgramming）一、对偶问题的提出和模型1、问题的提出煤电油例今有另厂要购买三种资源，在原厂可接受的条件下，单价多少可使另厂付费最低？MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.设煤电油“价格”分别为y1,y2,y3MinW=360y1+200y2+300y3s.t.9y1+4y2+3y3≥74y1+5y2+10y3≥12y1,y2,y3≥0DUAL以后将特别讨论这一“价格”的含义.2、原问题与对偶问题的对应关系MaxZ=CXAX≤bX≥0s.t.原问题（P）：对偶问题（D）：MinW=bTYATY≥CTY≥0s.t.MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MinW=360y1+200y2+300y3s.t.9y1+4y2+3y3≥74y1+5y2+10y3≥12y1,y2,y3≥0（Y为行向量）

对称的对偶问题原问题与对偶问题形式上的对应关系原问题（P）对偶问题（D）目标max型目标min型有n个变量（非负）有n个约束（大于等于）有m个约束（小于等于）有m个变量（非负）价格系数资源向量资源向量价格系数技术系数矩阵技术系数矩阵的转置.1、对称性二、对偶性质与定理2、弱对偶性设X、Y分别为（P）、（D）的任一可行解，则一个线性规划的对偶问题的对偶问题恰是原问题；即（P）与（D）互为对偶3、无界性若原问题（P）无上界，则对偶问题（D）无可行解；同样，若对偶问题（D）无下界，则原问题（P）无可行解；

（注意：该命题的逆命题不成立。）.4、解的最优性设

、

分别为（P）与（D）的可行解，且则、分别是原问题（P）和对偶问题（D）的最优解。

5、对偶定理（强对偶性）若（P）有最优解，则（D）也有最优解，且二者最优值相等.

由该性质的证明中可以得到一个有用的结论：

若原问题（P）有最优解，设最优基为B，则CBB-1是对偶问题（D）的最优解。

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+10x2=300x1x2402060801002040608010009x1+4x2=320.X*=（20，24），Z*=4287x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=200x1x2402060801002040608010004x1+5x2=170右端项变化示意2，某个右端项在一定范围变化，影响最优解,但可能不影响最优基。...2．价格系数C变化的分析3x1+10x2=300X*=（20，24），Z*=4287x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=200x1x240206080100204060801000目标函数系数变化示意，目标函数系数在一定范围变化，可能不影响最优解.....§5（线性）整数规划IntegerProgramming(简称IP)一、整数规划的一般模型LP:maxz=CXAX=bX≥0IP:maxz=CXAX=bX≥0X为整数.整数规划的解法：分枝定界法或割平面法基本思想是把一个整数规划问题化为一系列的线性规划问题来求解整数规划的分类：纯整数规划：所有变量都限制为整数混合整数规划：仅部分变量限制为整数

0-1整数规划：变量的取值仅限于0或1.[例]人力资源分配的问题某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：

设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?班次时间所需人数16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：0030.解：设xi表示第i班次时开始上班的司机和乘务人员数,于是LP模型为:x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0且为整数minz=x1+x2+x3+x4+x5+x6

最优解：X*=(60，10，50，0，30，0）T，Z*=150.二、0-1整数规划选址问题指派问题固定费用问题背包问题.1.投资场所的选址问题

某城市拟在东、西、南三区设立商业网点，备选位置有A1~A7共7个，如果选Ai，估计投资为bi元，利润为ci元，要求总投资不超过B元，规定东区：A!、A2、A3中至多选2个西区：A4、A5中至少选一个南区：A6、A7中至少选一个问如何设点使总利润最大？1，Ai被选中

0，Ai没被选中解：令xi=maxz=xi=0或1，i=1,…,7∑bixi≤Bi=17x1+x2+x3≤2x4+x5≥1x6+x7≥1s.t..课堂练习1:

某钻井队要从S1~S10共10个井位中确定五个钻井探油，如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件：（1）或选择S1和S7，或选择S8;

（2）选择了S3或S4就不能选择S5，反过来也一样;（3）在S5，S6，S7，S8中最多只能选两个。问如何选择井位使总费用最小？.课堂练习1:某钻井队要从S1~S10共10个井位中确定五个钻井探油，如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件：（1）或选择S1和S7，或选择S8（2）选择了S3或S4就不能选择S5，反过来也一样（3）在S5，S6，S7，S8中最多只能选两个问如何选择井位使总费用最小？1，Si被选中

0，Si没被选中解：令xi=minz=s.t.或1，i=1,…,10.某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上场参赛，要求：（1）中锋只有1人上场（2）后卫至少有一人上场（3）只有2号上场，6号才上场要求平均身高最高，应如何选拔队员？课堂练习2:.1，队员i被选中

0，队员i没被选中解：令xi=maxz=或1，i=1,…,8s.t.某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上场参赛，要求：（1）中锋只有1人上场（2）后卫至少有一人上场（3）只有2号上场，6号才上场要求平均身高最高，应如何选拔队员？.2.指派问题

例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记作任务E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种说明书所需的时间如下表所示，问应指派何人去完成何项任务，使所需总时间最少？问题描述：n项任务可由n个人完成，由于专长不同，各人完成各任务的时间也不同，求最优安排。要求：每人只能完成一项任务，每项任务只能由一人完成。.x11+x12+x13+x14=1(甲只能干一项工作)

x21+x22+x23+x24=1(乙只能干一项工作)x31+x32+x33+x34=1(丙只能干一项工作)x41+x42+x43+x44=1(丁只能干一项工作)x11+x21+x31+x41=1(E任务只能一人干)

x12+x22+x32+x42=1(J任务只能一人干)x13+x23+x33+x43=1(G任务只能一人干)x14+x24+x34+x44=1(R任务只能一人干)xij=0或1，i,j=1,2,3,4minz=2x11+15x12+13x13+4x14+10x21+4x22+14x23+15x24+9x31+14x32+16x33+13x34+7x41+8x42+11x43+9x441，指派第i人去完成第j项任务

0，不指派第i人去完成第j项任务解：令

xij=课堂练习:P57例2.23.指派问题可以一般化表述为有n个人n项工作，已知第i个人做第j项工作的费用为cij，现如何分派任务，使一个人只做一项工作，一项工作只由一个人完成，而且总费用最小。以4个人4项工作的指派问题为例，该问题需用4×4＝16个0－1变量，即设

把这些变量和已知费用系数分别排成一4×4矩阵，分别称为解矩阵和费用矩阵，

....3.固定费用问题最基本的带有固定费用的费用函数一般表示为：

若引入0－1变量

则带有固定费用的费用函数可表示为：

.固体废物处理规划例（教材P52例2.20）示意图：...固定费用问题另例例、生产三种型号的防寒服，其消耗资源及单件成本如表。此外，每种防寒服不管生产多少，都要支付一定的固定费用。型号资源小中大资源限制尼龙绸1500尼龙棉1000劳动力44.553500设备2800单件成本131210固定费用120150180今要生产500件防寒服，确定总费用最低的生产方式。.一般描述：已知：生产某产品有m种方式，设第j种生产方式的固定成本为kj，可变成本为cj。问题：应选择哪几种生产方式、分别生产多少产量可使总成本最低？分析：这是一个混合0-1规划问题：1，选择第j种方式，即xj>0时0，不选择第j种方式，即xj=0时令yj=设第j种生产方式的产量为xj于是该问题可表示为：

xj≤M

yj.例、生