整数规划问题

第四章整数规划与分配问题数学模型割平面法分枝定界法0-1整数规划分配问题整数规划IntegerLinearProgramming简述LP虽然用途广泛，但经常地，客观上要求L.P.最优解中不能含有非整数值（如股票的购买之解答），整数规划就是专门用来求解这类问题的有效工具•重点掌握：0-1规划灵活应用、分枝定界法。提出问题•某厂生产A1，A2两种品牌电视，用B1，B2两种原料，具体数据如下，求如何安排生产使利润最大A1A2供应量B130（g/台）2080gB27040150g利润200（元/g）100整数规划数学模型njxxmibxatsxczjjnjijijnjjj,,2,10,,2,1,),(..max(min)11部分或全部为整数•若所有xj的解为整数，称为纯整数规划pureintegerlinearprogramming•若部分xj的解为整数，称为混合整数规划mixedintegerlinearprogramming•若xj只取0或1，成为0-1整数规划zero-oneintegerlinearprogramming松弛问题整数规划整数规划的最优解不会优于其松弛问题的最优解注释•最优解不一定在顶点上达到•最优解不一定是松弛问题最优解的邻近整数解•整数可行解远多于顶点，枚举法不可取整数规划问题的求解方法分枝定界法branchandboundmethod分枝定界法是一种隐枚举方法（implicitenumeration）或部分枚举方法，是枚举方法基础上的改进，几乎所有的计算机计算都用此算法。其关键是分支和定界。例——MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0X1，X2取整数s.t.6分支定界法思路与解题步骤•只解松弛问题1、在全部可行域上解松弛问题–若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程–若松弛问题最优解中某个xk=bk不是整数，令bk为bk的整数部分–构造两个新的约束条件xkbk和xkbk+1，分别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题—定界过程–设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况整数规划分支问题解可能出现的情况序号问题1问题2说明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即最优解3无可行解非整数解对问题2继续分枝4整数解整数解较优的一个为最优解5整数解，目标函数优于问题2非整数解问题1的解即最优解6整数解非整数解，目标函数优于问题1问题1停止分枝(剪枝)，其整数解为界，对问题2继续分枝•情况2,4,5找到最优解•情况3在缩减的域上继续分枝定界法•情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或5整数规划分支定界法图解整数规划松弛问题MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0该整数规划松弛问题的解为：（X1，X2）=（3/2,10/3）Z1=29/614X1+9X2≤51-6X1+3X2≤151/141/39整数规划IntegerProgramming（IP）分支定界法图解整数规划松弛问题MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0（3/2，10/3）Z1=29/6B1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X1，X2≥0B2MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≤1X1，X2≥0B2：解（1,7/3）Z21=17/3B1：解（2,23/9）Z11=41/912B1B210整数规划IntegerProgramming（IP）整数规划问题的求解方法分支定界法图解整数规划（3/2,10/3）Z1=29/6B1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X1，X2≥0B2：解（1,7/3）Z21=17/3B1：解（2,23/9）Z11=41/9B11MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≥3X1，X2≥0B12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≤2X1，X2≥0B12：解（33/14,2）Z12=61/1412X=2X=311整数规划IntegerProgramming（IP）整数规划问题的求解方法分支定界法图解整数规划（3/2，10/3）Z1=29/6B2：解（1,7/3）Z21=17/3B12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≤2X1，X2≥0B12：解（33/14,2）Z12=61/14B121MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥3X2≤2X1，X2≥0B122MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≤2X2≤2X1，X2≥0B121：解（3，1）Z121=4B122：解（2，2）Z122=4B1：解（2，23/9）Z11=41/912312割平面法cuttingplaneapproach割平面法求解整数规划问题时，若其松驰问题的最优解X*不满足整数要求时，则从X*的非整分量中选取一个，用以构造一个线性约束条件（Gomory割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而不会切割掉问题的任何整数解。13整数规划IntegerProgramming（IP）整数规划问题的求解方法割平面法cuttingplaneapproach构造切割方程的步骤：1、令xi是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得：xi+∑aikxk=bi……………………（1式）其中i∈Q（Q指基变量下标集）k∈K（K指非基变量下标集）14整数规划IntegerProgramming（IP）整数规划问题的求解方法割平面法cuttingplaneapproach构造切割方程的步骤：2、将bi和aik都分解成整数部分N（不超过b的最大整数）与非负真分数部分f之和，即：bi=Ni+fi，其中0＜fi＜1………（2式）aik=Nik+fik，其中0≤fik＜1例如：若b=2.35，则N=2，f=0.35；若b=-1.45，则N=-2，f=0.5515整数规划IntegerProgramming（IP）割平面法cuttingplaneapproach构造切割方程的步骤：2、将（2式）代入（1式）得：xi+∑Nikxk-Ni=fi-∑fikxk……………………（3式）3、提出变量为整（当然含非负）的条件：由于（3式）中等式左边需整，而0＜fi＜1，故有fi-∑fikxk≤0……………………（4式）此即为所需切割方程。16整数规划IntegerProgramming（IP）割平面法cuttingplaneapproach构造切割方程的步骤：（1）切割方程fi-∑fikxk≤0真正进行了切割，至少把非整数最优解这一点切割掉了。证明：（反证法）假设松驰问题的最优解X*未被切割掉，则由fi-∑fikx*k≤0，又因为x*k=0，（因x*k为非基变量）有fi≤0，这与fi＞0矛盾。（2）不会切割掉任何整数解，因为切割方程是由变量为整的条件提出的。17整数规划IntegerProgramming（IP）割平面法cuttingplaneapproach例——求解IPMaxZ=X1+X2-X1+X2≤13X1+X2≤4X1，X2≥0X1，X2整数LPMaxZ=X1+X2-X1+X2≤13X1+X2≤4X1，X2≥0181、求解LP得到非整数最优解：X=（3/4，7/4，0，0），MaxZ=5/2Cj1100I表CBXBB–1bX1X2X3X40X31-11100X443101j01100B表1X13/410-1/41/41X27/4013/41/4j-5/200-1/2-1/2求解步骤：19整数规划IntegerProgramming（IP）求解步骤：2、构造切割方程：由B表中的第2个方程——X2+3/4X3+1/4X4=7/4有b2=7/4=1+3/4a23=3/4=0+3/4，a24=1/4=0+1/4因此，切割方程为——3/4–3/4X3–1/4X4≤0增加松弛变量X5，并将如下方程的约束条件添加到B表中。-3X3-1X4+X5=-3X5≥020整数规划IntegerProgramming（IP）求解步骤：3、求解新的松弛问题Cj11000B表CBXBB–1bX1X2X3X4X51X13/410-1/41/401X27/4013/41/400X5-300-3-11j-5/200-1/2-1/20新B表1X111001/3-1/121X2101001/40X310011/3-1/3j-2000-1/3-1/6210-1整数规划问题0-1变量及其应用0-1变量作为逻辑变量（Logicalvariable），常常被引用来表示系统是否处于某个特定的状态，或者决策变量是否取某个特定的方案。xj=1当决策取方案Pj时0当决策不取方案Pj时220-1整数规划一、项目选定(选址）问题整数规划•在经济全球化的时代，许多公司为在全球范围内最优地配置资源（如获取廉价劳动力或原料等），要在不同地方建厂或仓库及其他服务设施，这些都要进行项目或地址的选择。在选址之前，许多侯选地点要进行分析和比较，而每个决策都涉及到一个选还是不选的问题。案例一•某销售公司打算通过在武汉或长春设立分公司（也许两个城市都设）增加市场份额，管理层同时也计划在新设分公司的城市最多建一个配送中心，当然也可以不建配送中心。经过计算，每种选择对公司收益的净现值、所需费用列在下表中，总预算投资费用不得超过20万。如何决策使总净现值最大决策编号问题净现值（万元）所需资金（万）1长春建厂否？18122武汉建厂否？1063长春建配送中心否？12104武汉建配送中心否？84设xj=10---决策j问题的答案是“是”---决策j问题的答案是“否”maxz=18x1+10x2+12x3+8x412x1+6x2+10x3+4x4≤20x3+x4≤1（建1个配送中心）x3≤x1x4≤x2xj=0或1(j=1,2,3,4)最优解x1=1，x2=1案例练习例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收净益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设xj=10---选择开采第j个构造---不选择开采第j个构造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年总收益----投资额限制1、表示选择性决策若在开采时还需满足下述条件：（a）若开采8号，则必须同时开采6号；（b）若开采5号，则不许开采3号；（c）2号和4号至少开采一个；（d）8号与7号必须同时开采；（e）1号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。设xj=10---选择开采第j个构造---不选择开采第j个构造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年总收益----投资额限制（a）当x8=1x6=1，x6≠0当x8=0x6=1，x6=0∴x8x6（b）当x5=1x3=0，x3≠1当x5=0x3=0，x3=1∴x5+x31（c）x2+x41（d）x8=x7（e）x1+x4+x6+x92•在生产或经营过程中，某一个业务活动开展通常伴随着固定成本的发生，比如添置或起用设备，新采购材料时产生的差旅费，对工人必要培训的费用等，这些构成产品的固定成本。这时，业务活动的总成本就包括与活动数量大小相关的变动成本和起动活动的固定成本。二固定费用（成本）问题案例•某工厂近期接到一批订单，