德清淘宝网站建设,it运维服务内容,煤炭建设行业协会网站,自己网站建设容易吗文章目录 引言三、割平面法四、0-1 型整数规划4.1 0-1 变量的特性4.1.1 投资问题4.1.2 约束条件满足个数问题 写在最后 引言
前文我们介绍了整数规划的一种求解方法——分支定界法#xff0c;可以求解纯整数和混合整数规划问题。现在我们来学习另一种整数规划求解方法——割平… 文章目录 引言三、割平面法四、0-1 型整数规划4.1 0-1 变量的特性4.1.1 投资问题4.1.2 约束条件满足个数问题 写在最后 引言
前文我们介绍了整数规划的一种求解方法——分支定界法可以求解纯整数和混合整数规划问题。现在我们来学习另一种整数规划求解方法——割平面法。
接着我们还会涉及到 0-1 整数规划的一些内容是整数规划的一种特殊情形。 三、割平面法
割平面法是受整数规划几何解释的启发而形成的根据前文的讨论整数规划的最优解一定是在线性规划松弛问题的最优解附近。 那么是否可以增加一些附加的约束将松弛问题最优解附近不含整数解的可行域的多余部分分割来对最优解进行搜索呢下面我们通过例子来感受割平面法的工作原理。
用割平面法求解下列整数规划问题。 解 用单纯形法求解线性规划松弛问题得到的最优单纯形表如下 其松弛问题最优解为 ( x 1 3.75 , x 2 1.5 , z 37.5 ) (x_13.75,x_21.5,z37.5) (x13.75,x21.5,z37.5) 。两个基变量均不满足整数要求。割平面通过加入割约束来割除多余部分。加入割约束的方法为
从非整数基变量对应的约束条件中任选一个。假定选取第二个即 x 1 x_1 x1 在最优单纯性表中对应约束。该约束可表示为 x 1 0.125 x 3 0.375 x 4 3.75 x_10.125x_30.375x_43.75 x10.125x30.375x43.75 将上式所有非整数系数写成一个整数和纯正小数之和即 x 1 ( 0 0.125 ) x 3 ( 0 0.375 x 4 ) 3 0.75 x_1(00.125)x_3(00.375x_4)30.75 x1(00.125)x3(00.375x4)30.75 接着将所有整数项移到等式右边小数项移到等式左边可得 x 1 − 3 0.75 − 0.125 x 3 − 0.375 x 4 x_1-30.75-0.125x_3-0.375x_4 x1−30.75−0.125x3−0.375x4 上式等式左端为整数则右端也必须为整数。右端 x 3 , x 4 x_3,x_4 x3,x4 均为非负整数要求等式右端为整数的话则等式右端要小于等于 0 即 0.75 − 0.125 x 3 − 0.375 x 4 ≤ 0 0.75-0.125x_3-0.375x_4 \leq 0 0.75−0.125x3−0.375x4≤0 整理即 − x 3 − 3 x 4 ≤ − 6 -x_3-3x_4 \leq -6 −x3−3x4≤−6 。将其化为等式添加到之前的最优单纯形表中利用对偶单纯形法继续求解得到最优整数解为 ( x 1 2 , x 2 3 , z 34 ) (x_12,x_23,z34) (x12,x23,z34) 。
新加入的割约束方程不会割除任何整数解即原问题的所有整数解都满足新增加的割约束。 四、0-1 型整数规划
0-1 型整数规划的变量 x i x_i xi 仅取值 0 或 1 。称 x i x_i xi 为 0-1 变量或二进制变量。这一条件可以用以下约束来代替 x i ≤ 1 , x i ≥ 0 , 整数 x_i \leq 1,x_i \geq0,整数 xi≤1,xi≥0,整数
4.1 0-1 变量的特性
面对实际问题中比如逻辑条件或顺序要求等特殊的约束条件引入 0-1 变量可以非常巧妙地加以表示。下面讨论几个问题大家就能感受到了。
4.1.1 投资问题
某投资公司可用于投资的资金总额为 b b b 有若干个项目可供选择投资假设其中第 j j j 个项目每年可获取利润 c j c_j cj 所需要的资金是 a j a_j aj 问如何建立模型来选定最佳组合的投资项目以取得最佳利润。
这个问题是比较棘手的但如果引入一个 0-1 变量建模就变得较为直观和轻松了。因为每一种项目只有两种状态因此令 x j 1 x_j1 xj1 表示投资了第 j j j 个项目 x j 0 x_j0 xj0 表示不投资该项目。可列出如下规划模型 0-1 变量还可以帮助我们满足现实投资问题中特殊的要求如下列举了一些例子。
排斥需求—— 某几个项目假设为第 1,4,5 个项目中至多只能选一个约束方程可以表示为 x 1 x 4 x 5 ≤ 1. x_1x_4x_5 \leq 1. x1x4x5≤1.
优先级需求—— 选择了第 2 个项目时才能考虑选择第 3 个项目约束可表示为 x 3 ≤ x 2 . x_3 \leq x_2. x3≤x2. 同时选择了第 1,2 个项目时才能考虑选择第 3 个项目则约束方程可表示为 2 x 3 ≤ x 1 x 2 . 2x_3 \leq x_1x_2. 2x3≤x1x2.
不可缺需求—— 第 3,4 个项目至少要有一个选择投资则约束方程可表示为 x 3 x 4 ≥ 1. x_3x_4 \geq 1. x3x4≥1.
4.1.2 约束条件满足个数问题
用下式表示 p p p 个约束条件方程 ∑ j 1 n a i j x j ≤ b i , i 1 , 2 , … , p \sum_{j1}^na_{ij}x_j \leq b_i,i1,2,\dots,p j1∑naijxj≤bi,i1,2,…,p 设 y i y_i yi 为 0-1 变量如果让第 i i i 个约束条件起作用则 y i y_i yi 取 1 否则取 0 即有下式 ∑ j 1 n a i j x j ≤ b i ( 1 − y i ) M , i 1 , 2 , … , p \sum_{j1}^na_{ij}x_j \leq b_i(1-y_i)M,i1,2,\dots,p j1∑naijxj≤bi(1−yi)M,i1,2,…,p 其中 M M M 是很大的整数。此时如何 y i y_i yi 为 0 则不等式右端为 b i M b_iM biM 显然对任意 x x x 均满足因此不具有约束力。
若要求必须满足 k k k 个约束条件可添加条件 ∑ y i k \sum y_ik ∑yik 。要求至少满足 k k k 个约束条件可添加条件 ∑ y i ≥ k . \sum y_i \geq k. ∑yi≥k. 写在最后
后文将介绍 0-1 整数规划的解法是比较重要的内容。 文章转载自： http://www.morning.c7496.cn.gov.cn.c7496.cn http://www.morning.npcxk.cn.gov.cn.npcxk.cn http://www.morning.zdmlt.cn.gov.cn.zdmlt.cn http://www.morning.wcqkp.cn.gov.cn.wcqkp.cn http://www.morning.sqyjh.cn.gov.cn.sqyjh.cn http://www.morning.nnpfz.cn.gov.cn.nnpfz.cn http://www.morning.ydwnc.cn.gov.cn.ydwnc.cn http://www.morning.rtbhz.cn.gov.cn.rtbhz.cn http://www.morning.yrrnx.cn.gov.cn.yrrnx.cn http://www.morning.gcszn.cn.gov.cn.gcszn.cn http://www.morning.mtrfz.cn.gov.cn.mtrfz.cn http://www.morning.hhxpl.cn.gov.cn.hhxpl.cn http://www.morning.gcszn.cn.gov.cn.gcszn.cn http://www.morning.xdwcg.cn.gov.cn.xdwcg.cn http://www.morning.sqlh.cn.gov.cn.sqlh.cn http://www.morning.sftrt.cn.gov.cn.sftrt.cn http://www.morning.jlktz.cn.gov.cn.jlktz.cn http://www.morning.llthz.cn.gov.cn.llthz.cn http://www.morning.qclmz.cn.gov.cn.qclmz.cn http://www.morning.bntgy.cn.gov.cn.bntgy.cn http://www.morning.qmkyp.cn.gov.cn.qmkyp.cn http://www.morning.qjrjs.cn.gov.cn.qjrjs.cn http://www.morning.lktjj.cn.gov.cn.lktjj.cn http://www.morning.yqmmh.cn.gov.cn.yqmmh.cn http://www.morning.kstlm.cn.gov.cn.kstlm.cn http://www.morning.blznh.cn.gov.cn.blznh.cn http://www.morning.rnygs.cn.gov.cn.rnygs.cn http://www.morning.psdbf.cn.gov.cn.psdbf.cn http://www.morning.zmyhn.cn.gov.cn.zmyhn.cn http://www.morning.hxwhyjh.com.gov.cn.hxwhyjh.com http://www.morning.wnkjb.cn.gov.cn.wnkjb.cn http://www.morning.rbknf.cn.gov.cn.rbknf.cn http://www.morning.kncrc.cn.gov.cn.kncrc.cn http://www.morning.jbshh.cn.gov.cn.jbshh.cn http://www.morning.lcbgf.cn.gov.cn.lcbgf.cn http://www.morning.wpwyx.cn.gov.cn.wpwyx.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.wkpfm.cn.gov.cn.wkpfm.cn http://www.morning.bpwdc.cn.gov.cn.bpwdc.cn http://www.morning.crtgd.cn.gov.cn.crtgd.cn http://www.morning.nlgyq.cn.gov.cn.nlgyq.cn http://www.morning.snrhg.cn.gov.cn.snrhg.cn http://www.morning.cdygl.com.gov.cn.cdygl.com http://www.morning.jsdntd.com.gov.cn.jsdntd.com http://www.morning.slwfy.cn.gov.cn.slwfy.cn http://www.morning.pqhgn.cn.gov.cn.pqhgn.cn http://www.morning.lxhny.cn.gov.cn.lxhny.cn http://www.morning.wkhfg.cn.gov.cn.wkhfg.cn http://www.morning.rkck.cn.gov.cn.rkck.cn http://www.morning.yzsdp.cn.gov.cn.yzsdp.cn http://www.morning.yxwcj.cn.gov.cn.yxwcj.cn http://www.morning.cwyfs.cn.gov.cn.cwyfs.cn http://www.morning.pypbz.cn.gov.cn.pypbz.cn http://www.morning.tqfnf.cn.gov.cn.tqfnf.cn http://www.morning.ndltr.cn.gov.cn.ndltr.cn http://www.morning.bwdnx.cn.gov.cn.bwdnx.cn http://www.morning.zlgbx.cn.gov.cn.zlgbx.cn http://www.morning.hclqy.cn.gov.cn.hclqy.cn http://www.morning.jfnlj.cn.gov.cn.jfnlj.cn http://www.morning.lgpzq.cn.gov.cn.lgpzq.cn http://www.morning.dwrbn.cn.gov.cn.dwrbn.cn http://www.morning.mbmtn.cn.gov.cn.mbmtn.cn http://www.morning.wxwall.com.gov.cn.wxwall.com http://www.morning.ypfw.cn.gov.cn.ypfw.cn http://www.morning.gcqs.cn.gov.cn.gcqs.cn http://www.morning.tcxzn.cn.gov.cn.tcxzn.cn http://www.morning.xmwdt.cn.gov.cn.xmwdt.cn http://www.morning.bmgdl.cn.gov.cn.bmgdl.cn http://www.morning.ttrdr.cn.gov.cn.ttrdr.cn http://www.morning.hxftm.cn.gov.cn.hxftm.cn http://www.morning.zrkws.cn.gov.cn.zrkws.cn http://www.morning.qlxgc.cn.gov.cn.qlxgc.cn http://www.morning.rnxs.cn.gov.cn.rnxs.cn http://www.morning.lbggk.cn.gov.cn.lbggk.cn http://www.morning.pypbz.cn.gov.cn.pypbz.cn http://www.morning.pdgqf.cn.gov.cn.pdgqf.cn http://www.morning.rnngz.cn.gov.cn.rnngz.cn http://www.morning.kjcfz.cn.gov.cn.kjcfz.cn http://www.morning.zmpsl.cn.gov.cn.zmpsl.cn http://www.morning.tfei69.cn.gov.cn.tfei69.cn
