《第五章整数规划优秀课件.ppt》由会员分享，可在线阅读，更多相关《第五章整数规划优秀课件.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章整数规划第1页，本讲稿共60页2022/10/262 在很多场合，我们建立最优化模型时，实际问题要求在很多场合，我们建立最优化模型时，实际问题要求决策变量只能取整数值而非连续取值。此时，这类最决策变量只能取整数值而非连续取值。此时，这类最优化模型就称为整数规划（离散最优化）模型。优化模型就称为整数规划（离散最优化）模型。整数规划的求解往往比线性规划求解困难得多，而且，整数规划的求解往往比线性规划求解困难得多，而且，一般来说不能简单地将相应的线性规划的解取整来获得。一般来说不能简单地将相应的线性规划的解取整来获得。第2页，本讲稿共60页2022/10/263整数线性规划数学模型的一般形式整
2、数线性规划数学模型的一般形式整数规划（整数规划（IPIP）松弛问题松弛问题整数线性规划（整数线性规划（ILPILP）的数学模型：）的数学模型：一、整数规划的数学模型及解的特点一、整数规划的数学模型及解的特点5.1c5.1d5.1a5.1b第3页，本讲稿共60页2022/10/264决策变量只能取值决策变量只能取值0 或或 1。整数规划问题的整数规划问题的类型类型纯纯整数线性规划整数线性规划(pure integer linear programming)全部全部决策变量决策变量都必须都必须取整数值取整数值。混合混合整数线性规划整数线性规划(mixed integer linear progra
3、mming)决策变量中决策变量中一部分必须取整数值，一部分必须取整数值，另一部分另一部分可以不取整数值。可以不取整数值。0-1型型整数线性规划整数线性规划(zero-one integer linear programming)第4页，本讲稿共60页2022/10/265例例1 1、某公司准备投资某公司准备投资 50 50 万元为其产品做广告，万元为其产品做广告，广告代理商给公司的有关广告方式的费用和其效广告代理商给公司的有关广告方式的费用和其效果情况如下表，公司面临的管理决策问题是广告果情况如下表，公司面临的管理决策问题是广告总费用不超过总费用不超过 50 50 万元的基础上选择哪些广告方万
4、元的基础上选择哪些广告方式，使得潜在顾客数尽可能地多。式，使得潜在顾客数尽可能地多。广告方式广告方式电视台台报纸杂志志电台台广告广告费（万元）（万元）40152010潜在潜在顾客数（万人）客数（万人）40202510整数规划问题实例整数规划问题实例第5页，本讲稿共60页2022/10/266 xi=1 选择第选择第 i i 种广告方式种广告方式0 0 不选择第不选择第 i i 种广告方式种广告方式Max Z=40 x1+20 x2+25x3+10 x4 40 x1+15x2+20 x3+10 x4 50 x1，x2，x3，x4 =0 或或 1例例1 1、模型模型设：设：x xi i（i=1,2
5、,3,4i=1,2,3,4）表示表示 4 4 种广告方式。种广告方式。第6页，本讲稿共60页2022/10/267 例例2 2、某公司在城市的东、西、南三区建立门市部。、某公司在城市的东、西、南三区建立门市部。拟议中有拟议中有7 7个位置（地点）个位置（地点）A Ai i（i=1i=1，2 2，7 7）可供选择。公司规定：可供选择。公司规定：在东区，由在东区，由 A A1 1，A A2 2，A A3 3 三个点中至多选两个；三个点中至多选两个；在南区，由在南区，由 A A4 4，A A5 5 两个点中至少选一个；两个点中至少选一个；在西区，由在西区，由 A A6 6，A A7 7 两个点中至少
6、选一个。两个点中至少选一个。如果选用如果选用 A Ai i 点，设备投资估计为点，设备投资估计为 b bi i 元，每年元，每年可获利润估计为可获利润估计为 c ci i 元，但投资总额不能超过元，但投资总额不能超过 B B 元。元。问公司选择哪几个点可使年总利润最大？问公司选择哪几个点可使年总利润最大？第7页，本讲稿共60页2022/10/268 例例2 2、模型、模型 设：设：Ai=1 选择选择 A Ai i 建立门市建立门市0 0 不选择不选择 A Ai i 建立门市建立门市 Max Z=ci Ai bi Ai B A1+A2+A3 2 A4+A5 1 A6+A7 1 Ai=0 或或 1
7、，（，（i=1，2，3，4，5，6，7）第8页，本讲稿共60页2022/10/269例 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为S1S10，相应的钻探费用为c1c10，并且井位选择上要满足下列限制条件：或选择S1和S7，或选择S8；选择了S3或S4就不能选S5，反之，选了S5，则不能选S3或S4；在S5S8中最多选两个。建立这个问题的0-1型整数规划模型第9页，本讲稿共60页2022/10/2610解：令 （i1，10）第10页，本讲稿共60页2022/10/2611 设：工序设：工序 B B 有两种方式完成有两种方式完成方式（方式（1
8、 1）的工时约束）的工时约束:0.3X0.3X1 1+0.5X+0.5X2 2 150 150方式（方式（2 2）的工时约束）的工时约束:0.2X0.2X1 1+0.4X+0.4X2 2 120 120 问题是完成工序问题是完成工序 B B 只能从两种方式中任选一种，只能从两种方式中任选一种，如何将这两个互斥的约束条件统一在一个线性规划如何将这两个互斥的约束条件统一在一个线性规划模型中呢？模型中呢？例例3 3、应用应用 0-1 0-1 变量解决含互斥约束条件问题变量解决含互斥约束条件问题第11页，本讲稿共60页2022/10/2612 例例3 3、模型、模型 引入引入 0-1 0-1 变量变量
9、y1=0 若工序若工序 B B 采用方式（采用方式（1 1）完成）完成1 1 若工序若工序 B B 不采用方式（不采用方式（1 1）完成）完成y2=0 0 若工序若工序 B B 采用方式（采用方式（2 2）完成）完成1 1 若工序若工序 B B 不采用方式（不采用方式（2 2）完成）完成于是前面两个互斥的约束条件可以统一为如下三个约束条件：于是前面两个互斥的约束条件可以统一为如下三个约束条件：0.3X0.3X1 1+0.5X+0.5X2 2 150+M 150+M1 1y y1 1 0.2X 0.2X1 1+0.4X+0.4X2 2 120+M 120+M2 2y y2 2 y y1 1+y+
10、y2 2=1 =1 其中其中 M M1 1 ，M M2 2 都是足够大的正数。都是足够大的正数。第12页，本讲稿共60页2022/10/2613 有三种资源被用于生产三种产品，资源量、产有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划，品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。使总收益最大。资源量源量A248500B234300C123100单件可件可变费用用456固定固定费用用100150200单件售价件售价81012 例例4 4固定费用问题固定费用问
11、题第13页，本讲稿共60页2022/10/2614 解：设解：设x xj j为第为第j j种产品的生产数量，种产品的生产数量，j=1,2,3j=1,2,3；yj=1 1 当生产第当生产第 j j种产品种产品,即即 xj 0 时时0 0 当不生产第当不生产第 j j种产品即种产品即 xj=0 时时 引入约束引入约束 xi M yi ，i=1，2，3，M充分大，以保充分大，以保证当证当 yi =0 时，时，xi=0。可建立如下的数学模型：可建立如下的数学模型：Max z=4Max z=4x x1 1+5+5x x2 2+6+6x x3 3-100y-100y1 1-150y-150y2 2-200
12、y-200y3 3s.t.2s.t.2x x1 1+4+4x x2 2+8+8x x3 3 500 500 2 2x x1 1+3+3x x2 2+4+4x x3 3 300 300 x x1 1+2+2x x2 2+3+3x x3 3 100 100 xi M yi ，i=1，2，3，M充分大充分大 x xj j 0 0 y yj j 为为0-10-1变量变量，i i=1,2,3=1,2,3第14页，本讲稿共60页2022/10/2615例例5、人人员时间员时间安排安排 某航空公司希望更有效地安排售票员的工作某航空公司希望更有效地安排售票员的工作时间，以减少工资支出。每个售票员上班后将连时间
13、，以减少工资支出。每个售票员上班后将连续工作续工作8 8个小时，但并非每时每刻都有一样多的个小时，但并非每时每刻都有一样多的顾客，因此，适当地将一天分成顾客，因此，适当地将一天分成8 8个时段，每个个时段，每个时段时段2 2小时（假定每天的小时（假定每天的8 8：00 00 至至2424：00 00 为售票为售票工作时间）。应该如何计划每个时段初的上班售工作时间）。应该如何计划每个时段初的上班售票员人数，才能使一天雇佣的售票员总人数最少？（数据票员人数，才能使一天雇佣的售票员总人数最少？（数据资料见下表）资料见下表）第15页，本讲稿共60页2022/10/2616 例例5、人、人员时间员时间安
14、排安排时段段起始起始时间结束束时间需售票需售票员人数人数18：0010：0010210：0012：008312：0014：009414：0016：0011516：0018：0013618：0020：008720：0022：005822：000：003第16页，本讲稿共60页2022/10/2617 例例5 5、模型、模型Min Z=x1+x2+x3+x4+x5 x1 10 x1+x2 8 x1+x2+x3 9 x1+x2+x3+x4 11 x2+x3+x4+x5 13 x3+x4+x5 8 x4+x5 5 x5 3 xi 0，且为整数且为整数 设：决策变量设：决策变量x xi i为第为第i i
15、时间段初上班的售票员人数时间段初上班的售票员人数第17页，本讲稿共60页2022/10/2618 例例6 6、合理下料合理下料 造某种机床，需要造某种机床，需要 A A，B B，C C 三种轴件，其规格与三种轴件，其规格与数量如下表，各类轴件都用数量如下表，各类轴件都用5.55.5米长的同一种圆钢下料。若米长的同一种圆钢下料。若计划生产计划生产100100台机床，最少要用多少根圆钢？台机床，最少要用多少根圆钢？轴类规格：格：长度（米）度（米）每台机床所需每台机床所需轴件数件数A3.11B2.12C1.24第18页，本讲稿共60页2022/10/2619 例例6 6、模型、模型 分析该问题后，发
16、现较合理的下料方案有：分析该问题后，发现较合理的下料方案有：轴类方案方案1方案方案2方案方案3方案方案4方案方案5A（3.1）11000B（2.1）10012C（1.2）02421用料用料长5.25.54.84.55.4余料余料0.300.710.1第19页，本讲稿共60页2022/10/2620 例例6 6、模型、模型 设：设：x xi i 采用方案采用方案i i下料所用的原料根数。下料所用的原料根数。Min Z=x1+x2+x3+x4+x5 x1+x2 =100 x1+x4+2x5 =200 2x2+4x3+2x4+x5 =400 x1，x2，x3，x4，x5 0，且为整数且为整数第20页
17、，本讲稿共60页2022/10/2621 例例7 7、指派问题指派问题 某企业正在考虑某企业正在考虑4 4名人员名人员 4 4项工作的分派问题，由项工作的分派问题，由于每项工作只需要一个人去完成，而每名人员也只能去完于每项工作只需要一个人去完成，而每名人员也只能去完成某一项工作，各人员完成各工作的成本如下表，管理人成某一项工作，各人员完成各工作的成本如下表，管理人员应该如何分派工作才能使总成本最小？员应该如何分派工作才能使总成本最小？工作工作人人员ABCD甲甲乙乙丙丙丁丁2109715414813141611415139第21页，本讲稿共60页2022/10/2622例例7 7、模型、模型 设
18、：设：Xij=0 不指派第不指派第i i人完成第人完成第j 项工作工作1 指派第指派第i i人完成第人完成第j 项工作工作其中其中 C Cijij 为第为第 i i 人完成第人完成第 j j 项工作的费用项工作的费用第22页，本讲稿共60页2022/10/2623例、例、某公司计划在某公司计划在m个地点建厂，可供选择的地点有个地点建厂，可供选择的地点有A1,A2Am，他们的生产能力分别是他们的生产能力分别是a1,a2,am（假设生产（假设生产同一产品）。第同一产品）。第i i个工厂的建设费用为个工厂的建设费用为fi(i=1.2m),又有又有n个个地点地点B1,B2,Bn 需要销售这种产品，其销
19、量分别为需要销售这种产品，其销量分别为b1.b2bn。从工厂运往销地的单位运费为。从工厂运往销地的单位运费为Cij。试决定应在哪。试决定应在哪些地方建厂，既满足各地需要，又使总建设费用和总运输些地方建厂，既满足各地需要，又使总建设费用和总运输费用最省？费用最省？第23页，本讲稿共60页2022/10/2624单销地厂址价生产能力建设费用销量第24页，本讲稿共60页2022/10/2625 设：设：xij 表示从工厂运往销地的运量表示从工厂运往销地的运量(i=1.2m、j=1.2n),1),1 在在Ai建厂建厂 又设又设 Yi （i=1.2m）0 0 不在不在Ai建厂建厂 模型：模型：第25页，
20、本讲稿共60页2022/10/2626（三）整数规划与线性规划的关系（三）整数规划与线性规划的关系 从数学模型上看整数规划似乎是线性从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。能保证所得倒的解是整数可行解。举例说明。举例说明。第26页，本讲稿
21、共60页2022/10/2627例：设整数规划问题如下例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称为松弛首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。问题）。第27页，本讲稿共60页2022/10/2628用图解法求出最优解用图解法求出最优解x13/2,x2=10/3且有且有Z=29/6x1x233(3/2,10/3)现求整数解（最优解）：现求整数解（最优解）：如用如用“舍入取整法舍入取整法”可得到可得到4个点即个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可。显然，它们都不可能是整数规划的最优解。能是整数规划的最优解。按整数规划约束条件，其
22、可行解肯定在线性规划问题的按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。有限集，如图所示。第28页，本讲稿共60页2022/10/2629 因此，可将集合内的整数点一一找出，其最因此，可将集合内的整数点一一找出，其最大目大目标函数的函数的值为最最优解，此法解，此法为完全枚完全枚举法。法。如上例：其中如上例：其中（2，2）（）（3，1）点点为最最大大值，Z=4。目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：分支定界法和割平面法；分支定界法和割平面法；对于特
23、别的对于特别的0 01 1规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。第29页，本讲稿共60页2022/10/2630（一）基本思路（一）基本思路 考虑纯整数问题：考虑纯整数问题：整数问题的松弛问题：整数问题的松弛问题：二、分枝定界法二、分枝定界法第30页，本讲稿共60页2022/10/2631 maxZ=CXAX=bX 0(A)IPmaxZ=CXAX=bX 0X为整数为整数(B)LP(B)B)为为(A)A)的松弛问题。的松弛问题。第31页，本讲稿共60页2022/10/2632 分枝定界法一般步骤：分枝定界法一般步骤：(1)(1)先解先解(A)A)的松弛问题的松弛问题(B
24、(B)(2)2)(B(B)无可行解无可行解(A)A)无可行解。无可行解。(B (B)最优解符合最优解符合(A)A)要求，停。要求，停。(B (B)最优解不符合最优解不符合(A)A)要求，转要求，转(3)(3)。(3)(3)估整数解估整数解S S0 0 ，定界（上界、下界），定界（上界、下界）(4)(4)选选(B(B)解中不符合整数条件的分量解中不符合整数条件的分量Xj(Xj=b bj j)分枝，作分枝，作(B(B)的后续问题的后续问题(C(C)、(D(D)。(C (C)：(B(B)加约束加约束Xj b bj j+1+1 (D (D)：(B(B)加约束加约束Xj b bj j 第32页，本讲稿共
25、60页2022/10/2633 剪枝条件剪枝条件:(C)，(D)无可行解无可行解 (C)（(D)）对应的目标值对应的目标值Sc(Sd)S0（极大化极大化）(C)（(D)）对应的目标值对应的目标值Sc(Sd)S0（极小化极小化）且解为整数解，令且解为整数解，令Sc(Sd)S0 且解为非整数解，令且解为非整数解，令(C)，(D)取代取代 (B)返回返回(4)(4)(6)(6)全部枝剪完，停全部枝剪完，停(5)解解(C)、(D)第33页，本讲稿共60页2022/10/2634例例1：用分枝定界法求解整数规划问题（用图解法计算）：用分枝定界法求解整数规划问题（用图解法计算）记为（IP）解：首先去掉整数
26、约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题记为（记为（LP）例题例题第34页，本讲稿共60页2022/10/2635用图解法求用图解法求（LP）的最优的最优解，如图所示。解，如图所示。x1x233(18/11,40/11)对于对于x118/111.64，取值取值x1 1，x1 2对于对于x2=40/11 3.64，取值取值x2 3，x2 4先将先将（LP）划分为（）划分为（LP1）和（）和（LP2）,取取x1 1,x1 2 x118/11,x2=40/11 Z(0)=218/11(19.8)即即Z 也是也是（IP）最小值的下限。最小值的下限。第35页，本讲稿共60页2
27、022/10/2636有下式：有下式：现在只要求出（现在只要求出（LP1）和（）和（LP2）的最优解即可。）的最优解即可。第36页，本讲稿共60页2022/10/2637x1x233(18/11,40/11)先求先求（LP1）,如图所示。如图所示。此时在此时在B 点取得最优解。点取得最优解。x11,x2=3,Z(1)16找到整数解，问题已探明，找到整数解，问题已探明，此枝停止计算。此枝停止计算。11同理求同理求（LP2）,如图所示。如图所示。在在C 点取得最优解。点取得最优解。即即x12,x2=10/3,Z(2)56/318.7 Z2 Z116 原问题有比（原问题有比（16）更小的最优解，但）
28、更小的最优解，但 x2 不是整数，故利用不是整数，故利用 3 10/34 加入条件。加入条件。BAC第37页，本讲稿共60页2022/10/2638加入条件：加入条件：x23,x24 有下式：有下式：只要求出（只要求出（LP3）和（）和（LP4）的最优解即可。）的最优解即可。第38页，本讲稿共60页2022/10/2639x1x233(18/11,40/11)11BAC先求先求（LP3）,如图所示。此时如图所示。此时D 在点取得最优解。在点取得最优解。即即 x112/52.4,x2=3,Z(3)-87/5-17.4 Z(5)F 如对如对 Z(6)继续分解，其最小值也不会低于继续分解，其最小值也
29、不会低于15.5 ，问题，问题探明探明,剪枝。剪枝。第41页，本讲稿共60页2022/10/2642 至此，原问题至此，原问题（IP）的最优解）的最优解为：为：x1=2，x2=3,Z*=Z(5)17以上的求解过程可以上的求解过程可以用一个树形图表以用一个树形图表示如右：示如右：LP1x1=1,x2=3Z(1)16LPx1=18/11,x2=40/11Z(0)19.8LP2x1=2,x2=10/3Z(2)18.5LP3x1=12/5,x2=3Z(3)17.4LP4无可无可行解行解LP5x1=2,x2=3Z(5)17LP6x1=3,x2=5/2Z(6)15.5x11x12x23x24x12x13第
30、42页，本讲稿共60页2022/10/2643练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （图解法）（图解法）第43页，本讲稿共60页2022/10/2644LP1x1=1,x2=7/3Z(1)10/3LPx1=3/2,x2=10/3Z(0)29/6LP2x1=2,x2=23/9Z(2)41/9x11x12LP5x1=1,x2=2Z(5)3LP6无可无可行解行解x22x23LP3x1=33/14,x2=2Z(3)61/14LP4无可无可行解行解x22x23LP7x1=2,x2=2Z(7)4LP8x1=3,x2=1Z(8)4x12x13第44页，本讲稿共60页2022/
31、10/2645LP1x1=1,x2=7/3Z(1)10/3LPx1=2/3,x2=10/3Z(0)29/6LP2x1=2,x2=23/9Z(2)41/9LP3x1=33/14,x2=2Z(3)61/14LP4无可无可行解行解LP7x1=2,x2=2Z(7)4LP8x1=3,x2=1Z(8)4x11x12x22x23x12x13第45页，本讲稿共60页2022/10/26463200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/40
32、0-5/4-1/4解解:用单纯形法解对应的用单纯形法解对应的(LP)问题问题,如表所示如表所示,获得最优解。获得最优解。初始表初始表最终表最终表例例2、用分枝定界法求解整数规划问题（单纯形法）、用分枝定界法求解整数规划问题（单纯形法）第46页，本讲稿共60页2022/10/2647 x1=13/4 x2=5/2 Z(0)=59/414.75 选选 x2 进行分枝，即增加两个约束，进行分枝，即增加两个约束，2 x2 3 有下式：有下式：分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6，将新加约束，将新加约束条件加入上表计算。即条件加入上表计算。即 x2+x5=2,x2
33、+x6=3 得下表得下表:第47页，本讲稿共60页2022/10/264832000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2 Z(1)=29/2=14.5继续分枝，加继续分枝，加入约束入约束 3 x1 4LP1第
34、48页，本讲稿共60页2022/10/264932000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3 Z(2)=27/2=13.5 Z(2)Z(1)先不考虑分枝先不考虑分枝第49页，本讲稿共60页2022
35、/10/2650接接(LP1)继续分枝，加入约束继续分枝，加入约束 4 x1 3，有下式：有下式：分别引入松弛变量分别引入松弛变量x7 和和 x8，然后进行计算。，然后进行计算。第50页，本讲稿共60页2022/10/2651CB XB b x1x2x3x4x5x73x17/2101/20-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x2201001
36、00 x420001-3-20 x310010-1-2-Z-130000-2-3 x1=3,x2=2 Z(3)=13找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP3第51页，本讲稿共60页2022/10/2652CB XB b x1x2x3x4x5x83x17/2101/20-1/202x220100100 x4100-11-200 x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-1
37、2x210110020 x4300-310-40 x5100-101-2-Z-1400-200-1 x1=4,x2=1 Z(4)=14找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP4第52页，本讲稿共60页2022/10/2653树形图如下：树形图如下：LP1x1=7/2,x2=2Z(1)29/2=14.5LPx1=13/4,x2=5/2Z(0)59/4=14.75LP2x1=5/2,x2=3Z(2)27/2=13.5LP3x1=3,x2=2Z(3)13LP4x1=4,x2=1Z(4)14x22x23x13x14第53页，本讲稿共60页2022/10/2654练习：用
38、分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （单纯形法）（单纯形法）第54页，本讲稿共60页2022/10/2655cj-1-5000cBxBbx1x2x3x4x50 x32-111000 x4 30560100 x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-5x240/11011/11 5/110-1x1 18/11101/11-6/1100 x526/1100-1/116/111-Z218/11006/1119/110第55页，本讲稿共60页2022/10/2656LP1x1=1,x2=3Z(1)16LPx1=18/11,x2=40/
39、11Z(0)19.8LP2x1=2,x2=10/3Z(2)18.5LP3x1=12/5,x2=3Z(3)17.4LP4无可无可行解行解LP5x1=2,x2=3Z(5)17LP6x1=3,x2=5/2Z(6)15.5x11x12x23x24x12x13第56页，本讲稿共60页2022/10/2657 隐枚举法隐枚举法(max)原则：原则：1 1、用试探法，求出一个可行解，以它的目标值、用试探法，求出一个可行解，以它的目标值 作为当前最好值作为当前最好值Z Z0 02 2、增加过滤条件、增加过滤条件Z Z Z Z0 03 3、将、将x xi i 按按c ci i由小由小大排列大排列三、三、0 01
40、 1 整数规划整数规划 01 整数规划是一种特殊形式的整数规划，这时的决策变整数规划是一种特殊形式的整数规划，这时的决策变量量xi 只取两个值只取两个值0或或1，一般的，一般的解法为隐枚举法解法为隐枚举法。第57页，本讲稿共60页2022/10/2658 例例1：maxZ=3x1-2x2+5x3x1+2x2-x3 2 x1+4x2+x3 4 x1+x2 3 4x2+x3 6 x1,x2,x3为为0或或1解：解：观察得解观察得解(x1,x2,x3)=(1,0,0)Z0=3过滤条件过滤条件：3x1-2x2+5x3 3将将(x1，x2 ，x3)(x2，x1，x3)第58页，本讲稿共60页2022/10/2659 解解(x2 x1 x3)目标值目标值 Z0 当前最好值当前最好值 (0,0,0)0 5 (0,1,0)3 8 (1,0,0)-2 (1,0,1)3 (1,1,0)1 (1,1,1)6 最优解最优解 x=(1,0,1)T Z=8第59页，本讲稿共60页2022/10/2660（0.1.1.0.0）练习：用隐枚举法求解练习：用隐枚举法求解0 01 1规划问题规划问题第60页，本讲稿共60页