运筹与决策之4整数规划和特殊情况下的投资决策

11绪论—Introduction2线性规划—LinearProgramming3运输与指派问题—TransportationModels4整数规划—IntegerProgramming5网络模型—NetworkModels6项目计划—PERT&CPM7排队论—QueueingModels8

模拟—Simulation9决策分析—DecisionTheory10多目标决策—Multi-objectiveDecision《管理数量方法》目录2授课内容Case:分销系统设计（P192）整数规划图解法及分枝定界法MS6.0软件求解整数规划应用举例银行选址P209（讲义：消防站选址）案例讨论：课本出版P2223Questions整数规划IP与线性规划LP有何不同？整数规划的分类？整数规划的求解方法？分枝定界法的基本思路？分枝问题解可能出现的情况？4Q1：整数规划与线性规划LP区别：

（要求所有xj的解为整数，或者要求部分xj的解为整数）1）一般整数规划。要求所有xj的解为整数，称为纯整数规划；或者要求部分xj的解为整数，称为混合整数规划。2）0-1整数规划。它规定整数变量只能有两个值，0或1。5Q2：整数规划的解法图解法穷举法分枝定界法(BranchandMethod)割平面法6Q3：分枝定界法的基本思路maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X为整数

(B)(B)为(A)的线性规划松弛问题。7(C)(D)(B)Xj

i+1(B)Xj

iX*最优解Xj*i+1i(C)(D)X*最优解为非整数解，则对(B)每次分两枝,每枝多一个约束条件8Q4：分枝问题解可能出现的情况如何回答？9表分枝问题解可能出现的情况情况2,4,5

找到最优解情况3

在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝的整数解进行比较，结论如情况4。结果101绪论—Introduction2线性规划—LinearProgramming3运输问题

—TransportationModels4整数规划—IntegerProgramming5网络模型—NetworkModels6项目计划—PERT&CPM7排队论—QueueingModels8

模拟—Simulation9决策分析—DecisionTheory10多目标决策—Multi-objectiveDecision《管理数量方法》目录11授课内容整数规划图解法及分枝定界法MS6.0软件求解整数规划应用举例银行选址P230（讲义：消防站选址）案例讨论：课本出版P24212整数规划举例产品桌

椅备用资源木工1230油漆工3260搬运工0224利润4050例1、家具厂生产计划问题桌，椅各生产多少,可获最大利润?13图解法求最优解解：X*=(15,7.5)Zmax=975该解是否符合实际要求？0203010102030X1X2DABCDABCC点：X1+2X2=30

3X1+2X2=60如何求解整数解？144整数规划整数规划的难度远大于一般线性规划15整数规划简介要求所有xj的解为整数，称为纯整数规划要求部分xj的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解16整数规划的解法图解法穷举法分枝定界法割平面法17§4.1整数规划的穷举法穷举法：可以通过计算和比较所有整数格点的值来求解。18例：maxZ=40x1+60x2+70x3+160x416x1+35x2+45x3+85x4

100x1,x2,x3,x4为0,1X1=1X1=0111010101X2=0X3=00解法1：枚举法：x1=1,x2=1,x3=1,x4=0

。枚举法？192100个整数解，用最现代化的计算机也要算上几亿亿年。穷举法是无法用来求解实际问题。最优解经过四舍五入的方法是否可以？若该整数规划问题有100个0－1整数变量，那么整数解有多少个？如何回答？20§4.2分枝定界法的基本思路maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X为整数

(B)(B)为(A)的线性规划松弛问题。21(C)(D)(B)Xj

i+1(B)Xj

iX*最优解Xj*i+1i(C)(D)X*最优解为非整数解，则对(B)每次分两枝,每枝多一个约束条件22分枝定界法的步骤思路:暂不考虑整数条件,用单纯形法求解,得整数解,停;不是整数解,分枝。分枝:每次分两枝,每枝多一个约束条件，（每个节点代表一个子问题）。停止分枝条件:1）子问题无可行解.2）子问题得整数解.3）子问题的目标值比下界差。maxZ定界:1）初始整数规划的松弛问题的最优值是上界.2）子问题得整数解的最优值是一个下界。23分枝问题解可能出现的情况如何回答？24表分枝问题解可能出现的情况情况2,4,5

找到最优解情况3

在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝的整数解进行比较，结论如情况4。结果25举例例：maxZ=x1+x26x1+

2x2175x1+

9x2

44x1,x2为整数如何回答？26

松弛问题Z0=5.545X1=1.477X2=4.068子问题1Z1=5.333X1=1X2=4.333子问题2Z2=4.5X1=2X2=2.5子问题3Z3=5X1=1X2=4子问题4无可行解x1≥2x1≤1x2≤4x2≥5分枝定界法求解过程∴最优整数解X1=1X2=4最优目标函数值Z=5270-1Programming(BinaryIP)

0-1整数规划决策变量取值0或1，称0-1或二进制变量。0-1变量可数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件0-1规划应用：如工厂选址、生产计划安排、旅行购物、背包问题、人员安排、代码选取、线路设计、可靠性等28§4.3整数规划建模应用举例：

0-1变量的作用1.Xj=3.从N个方案中最多选中3个:2.从N个方案中必须选中一个:29特殊约束的处理1.只有方案J选中时，方案I才可能被选中:如何表示？xi≤xj2.方案I与方案J是否选中是同时的:

xi=xj3.矛盾约束:f(x)-5≥0与f(x)≤0→-f(x)+5≤M(1-y)与f(x)≤MyM表示很大的数，y为0－1变量。如何回答？30特殊约束的处理4.多个选一:fi(x)≤0,I=1,2,…,n.如何表示？

5.逻辑关系约束：若f(x)无限制,则g(x)≤0;若f(x)<0不成立,则g(x)无限制.如何表示？

fi(x)≤M(1-yi)I=1,2,…,n.y1+y2+…+yn=1→f(x)≥-M(1-y),g(x)≤My，M表示很大的数，y为0－1变量。310-1整数规划模型及其应用8.3.1资金预算（投资决策）问题8.3.2固定成本问题8.3.3配送系统设计8.3.4银行选址（覆盖问题）8.3.5产品设计与市场份额优化32整数规划应用举例例华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下约束：1.在项目1、2和3中必须（只）有一项被选中；2.项目3和4只能选中一项；（必须选一项）3.项目5被选中的前提是项目1必须被选中。如何在上述条件下选择一个最好的投资方案，使投资收益最大。33

项目投资收益表

项目投资额（万元）投资收益（万元）

121015023002103100604130805260180Xj=1表项目j选中,Xj=0表项目j未选中.j=1,2,3,4,5.约束条件如何表示？34计算过程解:Xj=1表项目j选中,Xj=0表项目j未选中.j=1,2,3,4,5.Z表示总收益.则模型如下:

MaxZ=150X1+210X2+60X3+80X4+180X5s.t:210X1+300X2+100X3+130X4+260X5

≤600X1+X2+X3=1X3+X4=1X5

≤X1Xj=0或1;j=1,2,3,4,5.35

例解决某市消防站的布点问题。该城市共有6个区，每个都可以建消防站。市政府希望建设的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见下表：请帮助该市制定一个最节省的计划。

消防车在各区行驶距离表

地区1地区2地区3地区4地区5地区6地区1地区2地区3地区4地区5地区6

010

16282720

100243217

1016240122721283212015

252717271501420

10

2125140Howtosolve？36计算过程解:Xj=1表地区设消防站,Xj=0表地区不设消防站.Z=消防站总数,则模型如下:

MinZ=X1+X2+X3+X4+X5+X6s.t.X1+X2≥1X1+X2+X6≥1X3+X4≥1X3+X4+X5≥1X4+X5+X6≥1X2+X5+X6≥1Xj=0或1；j=1,2,3,4,5,6.37银行选址P209俄亥俄信托公司（OhioTrustCompany）希望在俄亥俄西北部20个县进行选址，该地区还没有首席业务处（PrincipalPlaceofbusinessPPB）。根据俄亥俄州的银行法，如果金融企业在任何一个县设立PPB，就可以在该县及其比邻的县设立分支机构。俄亥俄信托公司想知道在那些县设立PPB会使其数量最少？38表俄亥俄信托公司考虑的各县邻居考虑的县邻县的数字代号考虑的县邻县的数字代号12，12，16118，10，13，14，15，18，19，2021，3，12121，2，3，10，13，1632，4，9，10，12，13133，10，11，12，15，1643，5，7，91411，15，2054，6，71511，13，14，1665，7，17161，12，13，1574，5，6，8，9，17，18176，7，1887，9，10，11，18187，8，11，17，1993，4，7，8，101911，18，20103，8，9，11，12，132011，14，1939整数规划选址模型使用OR软件对该问题进行求解，我们得出需要3个PPB，他们应分别选址在7、11、12。40例红光服装厂可生产三种服装：西服、衬衫和羽绒服。生产不同种类的服装要使用不同的设备，红光服装厂可从专业租赁公司租用这些设备。设备租金和其他经济参数见下表：假定市场需求不成问题，服装厂每月可用工人工时为2023小时，该厂如何安排生产可使每月的利润最大？41表产品经济参数

序号服装种类设备租金元生产成本元/件销售价格元/件人工工时

小时/件设备工时

小时/件设备可用工时123西服衬衫羽绒服500020003000280302004004030051430．5230030030042解:

1.目标函数是什么?每月的利润最大，Ｚ=收入-租金-生产成本。2.决策变量是什么?租用与不租用设备?与租用后产品生产量是多少?3.约束条件是什么?１).人工工时只有2023小时.２).设备工时约束.43Yj=租用第j种设备;Xj=第Ｉ种产品生产量。MaxZ=400X1+40X2+300X3-280X1-30X2-200X3-5000Y1-2023Y2-3000Y3s.t.5X1+X2+4X3≤20233X1≤300Y10.5X2≤300y22X3≤300Y3Xj≥0,且为整数,j=1,2,3.Yj=0或1,j=1,2,344案例1课本出版P222整数规划模型45课本出版计算结果现状优化结果x2=x5=x6=1，预期销售量73,000copies.1）Susan：优化结果x2=x8=1，预期销售量80,000copies.

2）Monica：优化结果x2=x5=x8=1，预期销售量105,000copies.3）由于上述结果均为出版修订本教材，长期看对公司发展不利，故可增加约束至少出版1本新书。46下次课内容P17整数规划作业4.44.6建模，并用MS6.0计算第九章

网络模型哥尼斯堡七桥问题最小树问题最短路问题最大流问题几种特殊情况下的投资决策设备更新决策设备更新决策是比较设备更新与否对企业的利弊。通常采用净现值作为投资决策指标。设备更新决策可采用两种决策方法，一种是比较新、旧两种设备各自为企业带来的净现值的大小；另一种是计算使用新、旧两种设备所带来的现金流量差量，考察这一现金流量差量的净现值的正负，进而做出恰当的投资决策。例（教材97－98页）

方法1，新旧设备净现值比较继续使用旧设备:每年经营现金流量为20万元，净现值为：NPV＝20万元×PVIFA（10％，10）＝20万元×6.145＝122.9万元使用新设备：初始投资额＝120－10－16＝94(万元)经营现金流量现值＝40×PVIFA(10%,10)＝40×6.145＝245.8(万元)终结现金流量现值＝20×0.386＝7.72(万元)净现值＝－94＋245.8＋7.72＝159.52(万元)由于使用新设备的净现值大于继续使用旧设备的净现值，故采用新设备。方法2：差量比较法初始投资额＝120－10－16＝94(万元)经营现金流量差量＝40－20＝20(万元)经营现金流量差量现值＝20×6.145＝122.9(万元)终结现金流量现值＝20×0.386＝7.72(万元)现金流量差量净现值＝－94＋122.9＋7.72＝36.62(万元)设备比较决策这一决策比较购置不同设备的效益高低。一般来讲，进行这一决策时应比较不同设备带来的成本与收益，进而比较其各自净现值的高低。但有时我们也假设不同设备带来的收益是相同的，因而只比较其成本高低即可。很多情况下，不同设备的使用期限是不同的，因此我们不能直接比较不同设备在使用期间的净现值大小，而需要进行必要的调整。这种调整有两种：一种是将不同设备的净现值转化为年金。一种是将不同设备转化为相同的使用年限。例：（教材98－99页）

设备A、B的使用期间成本现值分别为643573元和471622元，虽然B设备的成本现值小于设备A，但使用期限也小于设备A，所以二着不能直接比较。方法1，等年金比较年金现值公式：PV＝A×年金现值系数所以：A＝PV/年金现值系数A设备的成本现值＝40＋6.1×PVIFA(8%,5)=40＋6.1元×3.993＝64.36万元其年金为：AA＝64.36万元/3.993＝16.12万元B设备的成本现值＝25＋8.6×PVIFA(8%,5)＝25＋8.6×3.993＝47.16(万元)其年金为：AB＝47.16元/3.993＝18.30万元

由于设备B的成本年金高于设备A，所以