01规划问题深入剖析.ppt

0-1规划的解法0-1规划在线性整数规划中具有重要地位。定理：任何整数规划都可以化成0-1规划。一般地说，可把整数x变成(k+1)个0-1变量公式为：x=y0+2y1+22y2+.2kyk若x上界为U，则对0xU,要求k满足2k+1U+1.由于这个原因，数学界曾纷纷寻找“背包问题”解的方法，但进展缓慢。,隐枚举法(ImplicitEnumeration)基本上此法可以从所有变量等于零出发（初始点），然后依次指定一些变量取值为1，直到获得一个可行解，于是把第一个可行解记作迄今为止最好的可行解，再重复，依次检查变量为0，1的各种组合，对迄今为止最好的可行解加以改进，直到获得最优解。,例5-9求下列问题：MaxZ=3x1-2x2+5x3s.t.x1+2x2-x32(1)x1+4x2+x34(2)x1+x23(3)4x2+x36(4)xj0或1(5),解：容易看出(1,0,0)满足约束条件，对应Z=3，对MaxZ来说，希望Z3,所以增加约束条件：Z=3x1-2x2+5x33(0)称为过滤性条件。初看起来，增加约束条件需增加计算量，实际减少了计算量。,最优解（1，0，1）Z=8,增加约束条件（0）（Z3)后实际做了24次运算，而原问题需要计算23*4=32次运算（3个变量，4个约束条件）。,注意：改进过滤性条件，在计算过程中随时调整右边常数。价值系数按递增排列。以上两种方法可减少计算量。,改进过滤性条件Z5(0),改进过滤性条件Z8(0),最优解(X2,X1,X3)=（0，1，1）Z=8实际只计算了16次,例5-10求下列问题：MaxZ=3x1+4x2+5x3+6x4s.t.2x1+3x2+4x3+5x415xj0且为整数解：先变换xj为0-1变量x=y0+2y1+22y2+.2kyk,解：先变换xj为0-1变量x=y0+2y1+22y2+.2kykx17x1=y01+2y11+22y21x25x2=y02+2y12+22y22x33x3=y03+2y13x43x4=y04+2y14代入原问题，得到：,MaxZ=3y01+6y11+12y21+4y02+8y12+16y22+5y03+10y13+6y04+12y14s.t.2y01+4y11+8y21+3y02+6y12+12y22+4y03+8y13+5y04+10y1415yij=0或=1,用隐枚举法可得到：y11=y21=y02=1其他全为零最优解（6，1，0，0）Z=22,0-1规划应用华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：,该公司只有600万元资金可用于投资，由于技术原因，投资受到以下约束：在项目1、2和3中必须有一项被选中；项目3和4只能选中一项；项目5被选中的前提是项目1必须被选中。如何在上述条件下，选择一个最好的投资方案，使收益最大。,解：令1选中该项目0未选中该项目,xi=,MaxZ=150 x1+210 x2+60 x3+80 x4+180 x5s.t.210 x1+300 x2+100 x3+130 x4+260 x5600 x1+x2+x3=1x3+x41x5x1xi=1或0,5指派问题（分配问题）(AssignmentProblem)例5-11有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？,类似有：有n项加工任务，怎样分配到n台机床上分别完成；有n条航线，怎样指定n艘船分别去航行.等。表中数据称为效率矩阵或系数矩阵，其元素大于零，表示分配第i人去完成第j项任务时的效率（或时间、成本等）。,引入0-1变量xij=1分配第i人去完成第j项任务，xij=0不分配第i人去完成第j项任务。分配问题的数学模型：MinZ=cijxijxij=1(j=1,2n)xij=1(i=1,2n)xij0或1(i=1,2.m;j=1,2n),xij=1(j=1,2n)表示第j项任务只能由一人去完成。xij=1(i=1,2n)第i人只能完成一项任务。满足约束条件的解称为可行解可写成矩阵形式：,X=,010000100000001,称为解矩阵其各行各列元素之和为1。,匈牙利算法基本思想：对同一工作i来说，所有机床的效率都提高或降低同一常数，不会影响最优分配；同样，对同一机床j来说,做所有工作的效率都提高或降低同一常数，也不会影响最优分配。,分配问题性质：分配问题的最优解有这样的性质，若从系数矩阵C的一行（列）各元素中分别减去该行（列）的最小元素得到的新矩阵B，那么B为系数矩阵求得的最优解和用原来的系数矩阵C求得的最优解相同。,匈牙利算法：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。,例5-11有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？,匈牙利算法的步骤：第一步：使分配问题的系数矩阵经变换，在各行各列中都出现0元素：从系数矩阵的每行元素减去该行的最小元素。再从所得系数矩阵的每列元素减去该列的最小元素。若某行已经有0元素，就不必再减了。,(cij)=,21513441415914161378119,2497,01311260101105740142,42,01370606905320100,第二步：进行试分配，以寻找最优解。从只有一个0元素的行（或列）开始，给这个0元素加圈，记，然后划去所在的列（或行）的其他0元素，记作。给只有一个0元素的列（或行）的0元素加圈，记，然后划去所在的行（或列）的其他0元素，记作。反复进行上述两步，直到所有的0元素都被圈出和划掉为止。,若还有没有划圈的0元素，且同行（或列）的0元素至少有二个，从剩有0元素最少的行（或列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的0元素加圈，然后划掉同行同列的其他0元素，可反复进行，直到所有的0元素都被圈出和划掉为止。若元素的数目m等于矩阵阶数n，那么这分配问题的最优解已得到。若mn，则转下一步。,0137066905320100,从只有一个0元素的行（或列）开始，给这个0元素加圈，记。,013706695320100,从只有一个0元素的行（或列）开始，给这个0元素加圈，记，,1370669532100,然后划去所在的列的其他0元素，记作。,137066953210,给只有一个0元素的列的0元素加圈，记。然后划去所在的行的其他0元素，记作,1376695321,给最后一个0元素加圈，记。,0001010010000010,可见m=n=4,得到最优解。,即甲译俄文、乙译日文、丙译英文、丁译德文所需时间最少。Z=28小时,例5-12分配问题效率矩阵,76764,从只有一个0元素的行开始，给这个0元素加圈，记,然后划去所在的列的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,的个数m=4,而n=5,mn，转下一步。,第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素数。对没有的行，打；对已打行中所有含0元素的列打；再对打列中含0元素的行打；重复上述两步，直到得不出新的打行列为止。对没有打行画横线，有打列画纵线，就得到覆盖所有0元素的最少直线数。,对没有的行，打,对已打行中所有含0元素的列打,再对打列中含0元素的行打,对没有打行画横线,有打列画纵线,第四步：在没有被直线覆盖的部分中找出最小元素，然后在打行各元素都减去这最小元素，而在打列中各元素都加上这最小元素，以保证原来0元素不变，这样得到新的系数矩阵（它的最优解和原问题相同）。若得到n个独立的0元素，则已经得到最优解。否则回到第三步重复进行。,没有被直线覆盖的最小元素为2,在打行各元素都减去这最小元素2。,在打列中各元素都加上这最小元素2。,重复第二步，寻找独立0元素。,从只有一个0元素的行开始，给这个0元素加圈，记,然后划去所在的列的其他0元素，记作。,从只有一个0元素的行开始，给这个0元素加圈，记,然后划去所在的列的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,下面有二种分配方案：,下面有二种分配方案：第一种,最优解如下：Z=32,分配问题结果如下：Z=32,下面有二种分配方案：第二种,最优解如下：Z=32,分配问题结果如下：Z=32,整数规划应用模型电力规划问题某地区在制定十年电力规划时，遇到这样一个问题，根据电力需求预测，该地区十年以后发电装机容量需要增加180万千瓦，到时年发电量需增加100亿度，根据调查和讨论，电力规划的备选技术方案有三个：,扩建原有火电站，但最多只能安装5台10万千瓦机组；新建水电站，但最多只能安装4台25万千瓦机组；新建火电站，但最多只能安装4台30万千瓦机组。通过调研和计算，获得有关参数如下：,注：负荷因子=全年满功率运行天数/全年总天数。方案1：241天；方案2：146天；方案3：255天；资本回收因子：火电站15年，年利率0.06；水电站30年，年利率0.04。,建立模型：设置决策变量设备选方案1，2，3的装机台数分别为x1、x2、x3，它们的年发电量分别为x6、x7、x8亿度，备选方案1无前期土建工程要求，备选方案2和3都需要前期土建工程，这两个前期土建工程是否施工用变量x4、x5代表。,则x1取值0-5之间的整数，x2、x3取值0-4之间的整数，x4、x5只能取0或1，x6、x7、x8大于零。约束方程满足装机容量需求约束：10 x1+25x2+30 x3180满足规划年发电量需求约束：x6+x7+x8100,各电站容量与发电量平衡方程：每台机组发电量等于单机容量乘全年小时数，再乘与负荷因子，换算亿度量纲，即：方案1：x6=(0.66*8760*10/10000)*x1方案2：x7=(0.4*8760*25/10000)*x2,方案3：x8=(0.7*8760*30/10000)*x3得三个约束方程：5.782x1-x6=08.76x2-x7=018.39x3-x8=0,每个方案最多的装机台数约束：方案1：不需前期土建工程；x15方案2：前期土建工程是装机的先决条件，且小于最大允许数；x24x4方案3：前期土建工程是装机的先决条件，且小于最大允许数；x34x5,变量取值限制x1、x2、x30且整数x6、x7、x80 x4或x5=1前期土建工程要求x4或x5=0无前期土建工程要求,设计目标函数目标函数：年成本费用最低。成本包括两大部分：可变成本与发电量有关的成本，如：原材料，燃料，动力和活劳动消耗等。即参数表中年运行成本。不变成本指与装机容量及前期土建投资有关的成本。,方案1：单机投资*回收因子=21*0.103=2.163(百万元）方案2：单机投资*回收因子=70*0.0578=4.046(百万元）方案3：单机投资*回收因子=65*0.103=6.695(百万元）方案2和3的前期土建投资的年资本回收成本分别为504*0.0578=29.131(百万元）240*0.103=24.72(百万元）,对方案1，2，3每发一亿度电的运行成本分别为4.11,2.28,3.65百万元。则数学模型如下：MinZ=2.163x1+4.046x2+6.695x3+29.131x4+24.72x5+4.11x6+2.28x7+3.65x8s.t.10 x1+25x2+30 x3180 x6+x7+x8100,5.782x1-x6=08.76x2-x7=018.39x3-x8=0 x15x24x4x34x5x1、x2、x30且整数x6、x7、x80 x4、x5=1或0,利用混合整数规划求解程序MIP，得到：x1=2x2=4x3=3x4=1x5=1x6=11.56x7=35.04x8=55.17Z=423.24百万元。,扩建原有火电站，安装2台10万千瓦发电机组；新建水电站，安装4台25万千瓦发电机组；新建火电站，安装3台30万千瓦发电机组。总装机容量达：2*10+4*25+3*30=210万千瓦,地区电网最优化规划方案研讨背景据电力市场调查与预测，辽宁省盘锦地区2020年最大电力将达1500MW，供电量为6579GWh。地区电网规划拟以220kV变电所作主供电源。技术方案有三。,决策变量xj设置方案1、2和3的变电所座数分别为x1、x2和x3，供电能力为x7、x8和x9(GWh)。原有变电所的扩建、主变增容与新建变电所都将进行前期建筑安装等工程，每个方案的前期工程是否施工分别以x4、x5和x6代表。,约束条件()最大电力需求：k1(B1x1B2x2B3x3)cosPmax式中：k1为供电同时率；cos为平均功率因数；B1、B2和B3为对应方案1、2和3的变电所主变容量；Pmax为地区综合最大电力。,约束条件(2)满足目标年需用电量需求：x7x8x9Q,式中:Q为盘锦地区目标年供电量。,约束条件(3)各变电所主变容量与供电负荷平衡：x7k21B1Tx1cos1104x8k22B2Tx2cos2104x9k23B3Tx3cos3104式中:k2为主变经济负荷系数；为最大负荷利用时间。,约束条件(4)各方案最多变电所座数约束如果前期工程不施工，则该方案变电所座数一定为零；前期工程施工，则变电所座数必须小于其最大允许数。故有约束方程式：x16x40 x28x50 x38x60,约束条件(5)xj取值限制：x1、x2和x3均为大于或等于零的整数；x7、x8和x9均为大于或等于零的实数。,目标函数设计目标函数设计为年总费用最小，并采用年总费用最小法。即把收益(供电效益)相同的各方案的开支流贴现后进行比较，年总费用最小者即为最优方案。年总费用为:ZrKu式中:Z为年总费用；K为逐年投资额；ri(1i)n/(1i)n1为回收系数；u为等年值的年运行费用。,成本包括不变成本和可变成本。不变成本指与变电所设备投资及前期建筑安装工程投资有关的材料费、折旧费及维修费等成本，分年计算后计入Z。可变成本是指购入电力费的成本，在电价一定的条件下，它随着Q的增加而增大，即表1中给出的年供电成本。,方案1、2和3平均每座变电所设备的年投资费用c1、c2、c3分别为551.88万元、491.38万元和372.7万元。其前期建筑安装工程分年计算的年投资费用c4、c5、c6分别为953.56万元、1237.44万元和1364.39万元三个方案每供电1kWh的供电成本c7、c8、c9分别为0.557元、0.556元和0.561元。,因此，该问题的目标函数zcjxj(j1,2,，9)为Minz551.88x1491.38x2372.7x3953.56x41237.44x51364.39x60.557x70.560 x80.561x9,技术参数aij变电所主变主容量规格及规模的设置，以及k1、k2、T、cos等参数是影响aij的主要因素，均依盘锦地区具体情况而定。规划设计中，按照满足安全准则的要求，变电所一般应配置2台或以上同容量主变及相应的电源进线。,技术参数aij主变在一定条件下可过负荷30%。考虑到满足安全准则后，2台主变的k2取65%，3台取87%。随着地区电力负荷的发展和用电构成的变化，T将不断缩短，负荷率将有所回落，k1随着供电充足程度的提高而下降。据测算，盘锦地区2020年220kV的k1为77%，T为4335h。,资源变量brbr构成了约束条件的右端常数，也称外生变量。本问题中，20年后该地区Pmax与Q就是地方政府和供电部门由该地区工业、农业、交通运输等产业发展以及人口增长对电力发展的要求研究制定的。,价值系数cjcj为目标函数的系数。工程建设投资应在电力设施使用年限n内全部回收。若工程开始时投资现值为P0，且全部投资从银行贷款，年利率为i，则每年等额收回资金P与P0有如下关系：,价值系数cj这个与i及n有关的比例系数i(1i)n/(1i)n1也可称为回收系数r，或称资本回收系数。本问题中n取25年。电力工业投资利润率，亦即西方计算贴现时用的利率i10%，则求得r0.110。,在变电所综合投资构成中，设备(包括工器具)投资约占68.6%，建筑安装(含其他费用)投资约占31.4.%。c1、c2、c3、c4、c5、c6即可得知。,由盘锦供电企业19901997年固定资产、供电成本分类构成统计资料分析，变电设备约占固定资产的23.7%，购电成本约占总成本的89.48%。经测算，2020年购电价为0.5167元/kWh。工资与职工福利费、材料费、折旧费、