第三章目标规划和整数规划

null 第三章目标规划和整数规划 第三章目标规划和整数规划3.1 目标规划 3.2 整数规划 null 第三章目标规划和整数规划3．1 目标规划 3．1．1 单目标规划 3．1．2 多目标规划 级别相同的目标规划 具有优先级目标规划 3．2 整数规划 3．2．1 整数规划分枝限界法 3．1．2 整数规划分割平面法 3．2．1 0-1规划 3．1．2 分派问题null3．1目标规划 3．1．1单目标规划 3．1．1．1单目标规划数学模型 (1)如何安排可获得最大利润 Max Z（X）= 8x1+6x2 4x1 + 2x2 ≤60 2x1 + 4x2 ≤48 x1，x2 ≥0 x1=12,x2 =6, Z(X*)=132AB42426860可使用量48设备（hr)原料（kg)利润（千元）例（线性规划）null (2)利润目标为140（百元） 此目标称之为预定目标，实际完成的量与预定目标 之间可能出现偏差，通常用d+、d-（d+、d-≥0）表示， 称为偏差变量。 其中： d+表示超过预定指标的部分， d-表示未达到预定指标的部分 在客观条件下，最终完成的结果可能出现以下三种情况： ① d+>0,d-=0 表明超额完成预定指标 ② d->0,d+=0 表明未达到预定指标 ③ d+ =d- = 0 表明恰好完成预定指标 上述三种情况可用模型表示null 8x1 + 6x2特征：①增加了目标约束、 ②目标中只出现偏差变量且为求极小化问题、 ③d+×d-=0 d- ,d+ d- +d- -d+=目标约束系统约束Z= 4x1 + 2x2 ≤ 60 2x1 +4x2 ≤ 48 x1，x2， ≥0 140Minnull3．1．1．2 单目标规划解 用单纯形法求满意解,注意求极小化问题最优性条件：[] 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 型: Min Z= d- 8x1 + 6x2+d-- d+ =140 4x1 + 2x2 +x3 = 60 2x1 + 4x2 +x4 = 48 x1，x2 x3 ,x4 ,d-, d+ ≥0 X1 X2 X3 X4 d- d+ 0 0 0 0 1 0 8 6 0 0 1 -14 2 1 0 0 0 2 4 0 1 0 0-8 140 60 48d- X3 X41 0 0 -6 0 0 0 1null[][]≥0x1 =12， x2 = 6,d-=8 d+=0 完成利润132（百元）null 由此可得：x1=12，x2=6，d+=0，d-=8 完成利润132（百元） 3．1．2 级别相同的多目标规划 3．1．2．1数学模型 （1）实现利润目标122（百元） （2）产品A的产量不多于10 设：di+,di-(i=1,2)分别为超过目标值的部分，及未完成目标值的部分。 8x1 + 6x2 min目标约束系统约束x14x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48x1，x2，= 122= 10d1+,d1-，d2+,d2-≥0Z=+ d1-- d1++d2-- d2+d1-+ d2+null 8x1 + 6x2 + d1- - d1+ = 122 x1 +d2- - d2+ = 10 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1，x2，d1+,d1-，d2+,d2-≥0 min Z=d1- + d2+目标约束系统约束3．1．2．2单纯形表[]null3．1．2．2单纯形表][][nullx1=10、x2=7 x3=6 x4=0 d1+=d1-=d2+=d2-=0，完成利润122，两个目标均已实现。[]≥0null 3．1．3具有优先级的多目标规划 3．1．3．1数学模型 例：P1: 充分利用设备有效台时，不加班； P2: 产品B的产量不多于4； P3: 实现利润130（百元） 4x1 + 2x2+ d1- - d1+ = 60 ① x2 + d2- - d2+ = 4 ② 8x1 + 6x2+ d3- - d3+ = 130 ③ 2x1 + 4x2 ≤48 ④ x1，x2，di+,di-(i=1,2,3) ≥0 Z= (d1-+d1+)P1P2P3+ d2++ d3-Minnull3．1．3．2目标规划图解法 仍以例3为例 （1）根据系统约束④，确定可行域，如图 多边形OAB为该目标规划的可行域； （2）不考虑偏差，即：di+=di-=0（i=1,2,3)，然后按 顺序作出目标约束相应的直线，并标出di+>0,di->0的方向 。（3）按优先顺序找出该目标的满意解： 4x1 + 2x2+ d1- - d1+ = 60 ① x2 + d2- - d2+ = 4 ② 8x1 + 6x2+ d3- - d3+ = 130 ③ 2x1 + 4x2 ≤48 ④ x1，x2，di+,di-(i=1,2,3) ≥0 Z= (d1-+d1+)P1P2P3+ d2++ d3-MinnullFECBADOX2X1①④③②d1+ >0d3+ >0d2+ >0d2- >0d3- >0d1- >0G 4x1 + 2x2+ d1- - d1+ = 60 ① x2 + d2- - d2+ = 4 ② 8x1 + 6x2+ d3- - d3+ = 130 ③ 2x1 + 4x2 ≤48 ④ x1，x2，di+,di-(i=1,2,3) ≥0 Z= (d1-+d1+)P1P2P3+ d2++ d3-Min (1) 显然线段CD上的点满足第一目标 (2) FD上的点同时满足第一目标与第二 目标nullFECBADOX2X1①④③②d1+ >0d3+ >0d2+ >0d2- >0d3- >0d1- >0G (1) 显然线段CD上的点满足第一目标 (2) FD上的点同时满足第一目标与第二目标(3)E点满足第一、第三目标,与第二目标矛盾 ，G点满足第二、第三目标 与第一目标矛盾 ，因此允许第三目标有偏差，线段FD上的F点 可使d3-取最小值，故F点为所求满意解。其坐 标为（13，4） x1=13，x2=4， 利润128（百元）。Operational Researchnull3．1．3．3单纯形法 例 Min Z= P1 (d1-+d1+)+P2 d2++P3 d3- 4x1 + 2x2+ d1- - d1+ = 60 ① x2 + d2- - d2+ = 4 ② 8x1 + 6x2+ d3- - d3+ = 130 ③ 2x1 + 4x2 ≤48 ④ x1，x2，di+,di-(i=1,2,3) ≥0[]null[]≥0≥0[]null[]≥0≥0≥0≥0nullx1* =13，x2* =4， Z=128（百元）。 3．1．4 目标规划的目标 （1）决策人希望恰好实现预定的第i个目标 Min Z= di+ + di- （2）决策人不希望超过预定的第i个目标 Min Z= di+ （3）决策人希望超过预定的第i个目标 min Z= di- null3.2整数规划 3．2．1整数规划数学模型 Max Z（X）= c1x1+c2x2+…+cnxn ai1x1 + ai2x2+…+ain xn≤(=,≥)bi x1，x2，…，xn ≥0 纯整数规划:所有决策变量xj(j=1,2,…,n)均取整数. 混合整数规划:部分决策变量取整数. 0-1整数规划:所有决策变量只取0或1.这类变量又称 为逻辑变量.(i=1,2,…,m)全部或部分为整数 null3.2.2分枝限界法 例 Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 （A）： 2x1 + x2 ≤ 9 x1，x2 ≥ 0 且为整数 解；（1）先不考虑变量的整数约束，求解相应的线性规划 Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 （B0）： 2x1 + x2 ≤9 x1，x2 ≥0nullCC/9 由于x1 ，x2均不满足整数条件 ，故可由x1（或x2）进行分枝，使x1满足 ： x1≤3 或 x1≥4 将3< x1<4 的非整数部分割掉于是问题B0分成了两个子问题B1 ,B2 然后分别求出其最优解。 最优解：x1=13/4，x2 =5/2，Z0=143/4（2）分枝：Operational Researchnull Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 （B1）： 2x1 + x2 ≤9 x1 ≤3 x1，x2 ≥0 Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 (B2）： 2x1 + x2 ≤9 x1 ≥4 x1，x2 ≥0最优解:X2*=（4，1）Z2=14 此分枝已查清。 最优解:X1*=（3，8/3） Z1=141/3 Operational ResearchCX2987654321C/null（3）定界：问题（B2）已获得整数最优解， 可将Z2=14作为问题（A）的下界，同时将 Z0=143/4作为问题（A）的上界。可以断定 Z2=14≤ Z < Z0=143/4 （4）返回到（2）继续对B1中的x2进行分枝， 使x2满足： x2≤2或x2≥3 将2< x2< 3之间的非整数部分割掉于是问题B2又分成了两个子问题B3和B4 再分别求出其最优解.Operational Researchnull Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 （B3） 2x1 + x2 ≤9 x1 ≤3 x2 ≤2 x1，x2 ≥0 Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 (B4） 2x1 + x2 ≤9 x1 ≤3 x2 ≥3 x1，x2 ≥0最优解X3*=（3，2） Z3=13最优解X4*=（5/2，3） Z4=131/2Operational Researchnull Z3=13和Z4=131/2均小于界值Z2，不可能成为最优值，将被剪掉（剪枝）。 由此可得出问题（A）的最优解就是问题（B2）的最优解。即： X*=（4，1）；Z（X*）=14null树状图:B1 x1=3，x2 =8/3 Z1=141/3B2 x1=4，x2 =1 Z2=14B3 x1=3，x2 = 2 Z3=13B4 x1=5/2，x2 =3 Z4=131/2B0 x1=13/4，x2 =5/2 Z0=143/4x2≥3x2≤2 x1≥4x1≤3 null3.2.3割平面法 例： Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 （A）： 2x1 + x2 ≤9 x1，x2 ≥0 且为整数解: (1) 不考虑其整数条件,用单纯形法求解相应的线性 规划问题 最终单纯形表如下null（2）构造Gomory约束（割平面） 在最终单纯形表中，任意选择一个非整数变量（如x2），写出该变量所在行的方程式： x2 + 1/2x3 –1/2x4=5/2 将各变量的系数及常数项分解为整数与非负真分数之和；再将系数为整数的变量移到方程式左端，系数为分数的变量移到方程式右端 x2 –x4-2=1/2-（1/2x3+1/2x4） Gomory约束为： 1/2-（1/2x3+1/2x4）≤0 （3）将Gomory约束化为方程，填入到最终单纯形表中，继续求问题的最优解null1/2-（1/2x3+1/2x4）+x5= 0[]该单纯形表中当前解不可行，而其对偶解满足可行性条件 ，故用对偶单纯形法求解，最终表如下：null表中x1仍不满足整数条件，返回到（2） 构造Gomory约束（割平面）继续求解 由：x1+x4-1/2x5=7/2 x1+x4+(-1+ 1/2)x5=3 + 1/2 得：Gomory约束为： 1/2-1/2x5≤0 或 1/2-1/2x5+x6=0 将该约束插入上述的最终单纯形表中得：null[]null 最优解X*=（4，1）；Z（X*）=14 3.2.4 0-1规化 3．2．4．1 0-1规划问题及其数学模型 3．2．4．2 0-1规划的隐枚举解法例 MaxZ（X）=3x1-2x2+5x3 x1 +2x2 - x3 ≤2 ① x1 +4x2 + x3 ≤ 4 ② x1 + x2 ≤3 ③ 4x2 + x3 ≤ 6 ④ x1,x2,x3 =0 或 1解：首先通过试探的方法找出一个可行解 X =（x1,x2,x3 ）=（1，0，0） Z（X）= 3x1-2x2+5x3 = 3 增加约束： 3x1-2x2+5x3 ≥3 ⊙（称为过滤条件）null例 MaxZ（X）=3x1-2x2+5x3 x1 +2x2 - x3 ≤2 ① x1 +4x2 + x3 ≤ 4 ② x1 + x2 ≤3 ③ 4x2 + x3 ≤ 6 ④ x1,x2,x3 =0 或 1626N8021Y11N31110Y315N5-1101Y5-2N0N将不满足过滤条件的X全部过滤掉，见下表38null改进过滤条件： -2x2+3x1+5x3 ≥5 ⊙改进过滤条件： -2x2+3x1+5x3 ≥8 ⊙注意： （1）为进一步减少计算工作量，可及时改进过滤条件。 （2）价值系数按递增排列， 如 MaxZ（X）=-2x2+3x1+5x3 nullX*=(1,0,1) Z=8Operational Researchnull3．2．5分派问题（Assignment problem） 一般描述: 有n项任务,指派n个人(广义)去完成,第i个人完成第j项 任务的效率为Cij(i=1,2,…,n;j=1,2,…,n)；要求每个人只 能承担一项任务,并且每一项任务都有一个人个来承担；问 如何分派可以使总的效率达到最高。（Cij）为效率矩阵。 3．2．5．1建立数学模型 引入0-1变量 效率矩阵:xij=0 不分派第i个人去承担第j项任务1 分派第i个人去承担第j项任务nullx11+ x21+…+ xn1= 1A1A2...B1B2...BnC11C12...C1n............AnC21C22...C2nCn1Cn2...CnnX21X22...X2nX11X12...X1nXn1Xn2...Xnn............x21+ x22+…+ x2n= 1…………………... xn1+ xn2+…+ xnn= 1x12+ x22+…+ xn2= 1……………………. x1n+ x2n+…+ xnn= 1x11+ x12+…+ x1n= 1null(i =1,2,…,n) 每人只能承担一项工作(j =1,2,…,n) 每项工作只允许一人承担null特点： （1）特殊的0-1规划 （2）m=n;ai=bj=1的特殊运输问题 （3）所有可行解的个数为n!(i =1,2,…,n)每人只能承担一项工作(j =1,2,…,n)每项工作只允许一人承担Xij= 0 或 1null3．2．5．2分派问题的匈牙利解法 同解性原理： 如果在效率矩阵（Cij）的第i （i=1,2,…,n）行（列 ）加（减）一个常数ki，那么新效率矩阵与原效率矩阵有相 同的最优解。 在求解的过程中可反复利用这个性质。 步骤： (1) 化简效率矩阵：使其每行、每列至少有一个零元素。 例： 2 10 5 7 15 4 14 8 13 14 12 11 4 15 13 9 0 8 3 5 11 0 10 4 2 3 1 0 0 11 9 5 -2-4-11-4-1null(2) 检验： 用尽可能少的直线去覆盖所有的零元素，当覆盖线的 条数n0=n 时,可转入（4）确定最优 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ,当 n0 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 开办五家新商店。为了尽早建成营业，商业公司决定由3家建筑公司分别承建。已知第Ai(i=1,2,3)个建筑公司对第Bj(j=1,2,3,4,5)家新商店的建造费用的报价如下表，为保证工程进度，每家建筑公司最多只能承建两个商店，且由于某种原因，第B3家商店不能由第A1个建筑公司承办，求使总费用最少的指派方案商店建筑公司报价B1 B2 B3 B4 B5A1 A2 A34 8 7 15 12 7 9 17 14 10 6 9 12 8 7 B1 B2 B3 B4 B5A11 A12 A21 A22 A31 A32每家公司最多可 承建两家商店：人数≠工作数：B1 B2 B3 B4 B5 B6A11 A12 A21 A22 A31 A32B3不能由A1承办：5050null√√√√√√√√√√√B1 B2 B3 B4 B5 B6A11 A12 A21 A22 A31 A32由A1承建B1、B2指派方案：，由A2承建B5由A3承建B3、B4总费用=42nullnull管理运筹学应用软件可解决:1、纯整数规划2、0-1规划3、混合型整数规划要求：变量个数≤100约束方程个数≤50null例2.1 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？纯整数规划null数学模型：例 一登山队员做登山准备，他需要携带的物品及每件物品的重要系数、重量如下表，假定登山队员可携带的最大重量为25千克，问该队员该携带那些物品1 2 3 4 5 6 7序号物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通讯设备 重量ai（千克） 5 5 2 6 12 2 4重要系数ci 20 15 18 14 8 4 1010带第i个物品不带第i个物品Z表示总重要系数0-1规划null混合型null练习： 6个人应聘4份工作，由于个人的技术专长不同，他们承担各项工作所获得的收益如下表，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总收益最大的指派方案。工作人收益1 2 3 41 2 3 4 5 63 5 4 5 6 7 6 8 8 9 8 10 10 10 9 1112 11 10 1213 12 11 13分派方案：第3个人第2项工作第4个人第3项工作第5个人第1项工作第6个人第4项工作第1、2个人没工作