第十八讲 运筹学模型（2）——线性规划模型的整数解问题

yunjiang

< align=left>　　这一讲我们继续探讨线性规划基础模型，并给出非整数解化为整数解的一个常用方法。
　　<b>例2</b> 有一定数学功底的老张
　　老张下岗后，凭自己的数学功底成立了一个小加工部，专职搞原料套裁加工设计，如服装面料套裁、铝合金原料套裁设计等等。下面是他做过的一个问题。
　　某种新车，每台需要A、B、C三种轴件，其规格与数量如表4—1所示。各种轴件都用5.5米长的同一种圆钢下料。若计划生产100台车，最少要用多少根圆钢？
　　　　　　　　　　　　　　表4—1
　　　　 <IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image082.gif">
</P>

yunjiang

<b>　问题分析与模型构建</b>
　　本问题与前几例不同,不能直接由题意建模,而要先进行一下分析。注意,实际问题抽象为数学模型往往如此。
　　首先要考虑一根长为5.5米的圆钢截成A、B、C三种轴有哪些具体套裁方式，为此，只需找出全部省料截法。其次，所谓省料截法，这里是指余料σ<SUB>j</SUB>＜1.2米的各种截法。老张找出了如表4－2所示的所有下料方案。问题便归结为：采用上述五种截法方案各截多少根圆钢，才能在配成100套轴件条件下，使总下料根数最少？
　　假设按第<I>j</I>种截法下料<I>x<SUB>j</SUB></I>根，<I>j</I>=1,2,3,4,5。则有
　　　　 <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image004.gif"> </SUB>
　　　　 <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image006.gif"> 　　　　　　　　　　
　　　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image083.gif"> </SUB>
　　　　　　　　　　　 　　　　　表4－2

yunjiang

<b>　模型求解与分析</b>  
　　本题需使用单纯形解法才能解决，其解为
　　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image010.gif"> </SUB>
　　这表明最优下料方案为：按截法2、3各截100根，按截法5截25根，截法1和4不采纳。这样最多用225根圆钢便可制造出100套（700件）轴件。对此结果分析如下：
　　（1）最优方案中包括了余料较大的截法5（σ<SUB>5</SUB>=0.7），这自然是为了满足轴件配套之需要。事实上，若仅考虑按余料较小的截法1，2，3下料，其结果自然非最优（并不省料）。这也说明，找出全部省料截法的必要性。
　　（2）我们注意到，上述问题的目标是追求总下料根数达到最小，在有些资料中与本例提法有所不同。比如说，在相同的配套约束下，目标函数改成为min<I>Z</I>=0.3<I>x</I><SUB>1</SUB>+0.1<I>x</I><SUB>3</SUB>+<I>x</I><SUB>4</SUB>+0.7<I>x</I><SUB>5</SUB>（总料头数最小），也有相同的结果。
　　（3）本题的变量<I>x<SUB>j</SUB></I>的取值自然是正整数，仍属于整数规划问题，但用线性规划解法恰好得到整数解，便免去圆整工作。考虑到现行中学数学应用类题目中出现过类似问题，以下简介处理非整数解的分支定界法，看下例。

yunjiang

<b>　分支定界法　　
</b>　　塑钢窗厂要做20个矩形塑钢框，每个框由2.2米和1.5米的材料各两根组成。已知原料长4.6米，该如何下料，使用料最省?
　　容易得到其数学模型为：
　　 <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image012.gif"> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image014.gif"> </SUB>
　　其解为<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image016.gif"> </SUB>若使用四舍五入法，可得“最佳”方案为<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image018.gif"> </SUB>即按方案1截14根料，方案3截20根料，方案2不于考虑，总计需34根原料，料头总长为5.4米。那麽这个方案真是最优方案吗？
　　事实上，将<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image020.gif"> </SUB>，<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image022.gif"> </SUB>代入第二个约束条件即知未被满足 (42=40)，这是不允许的。实际上本模型属于运筹学模型中整数规划问题，应该按整数规划问题的相应解法求其整数解。这里就本例介绍处理这类问题的一个常用作法——分支定界法。

yunjiang

　　分支定界法的基本思路是：
　　1. 先求问题的解，若恰为整数解则停，否则转下一步；
　　2. 以上述解为出发点，将原问题分解为两个支问题，且每一支问题各增加一个新条件。由于增加新条件便保证所求解不至于跑出原问题解的允许范围，就不至于出现象本例圆整解跑出允许范围的情况了。
　　3. 求解支问题，并对新的非整数解问题再分支，直到求得整数解。
　　就本例讲，<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image024.gif"> </SUB>是非整数解，令 <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image026.gif"> </SUB>（这是因为在<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image028.gif"> </SUB>内无整数解，因而不予考虑）。于是原问题变成两个子问题：
　　　　　　 <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image030.gif"> </SUB>   （4.8） <><SUB>　　　　　　　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image032.gif"> </SUB>（4.9）
　　分别求解问题（4.8）、（4.9）。注意到问题（4.9）无解(因为<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image034.gif"> </SUB>，则第二个条件必不成立)，故只需求解（4.8）。仍采用以前解法有<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image036.gif"> </SUB>，而<I>x</I><I><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image038.gif"> </SUB></I><I><SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image040.gif"> </SUB></I>13，得<I>x</I><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image042.gif"> </SUB><SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image044.gif"> </SUB>1
　　代入目标函数有  <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image046.gif"></SUB> </P>

yunjiang

<>　　令<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image048.gif"> </SUB>，<I>y</I>取最小值。故将<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image049.gif"> </SUB>代入<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image051.gif"> </SUB>表达式得解为
　　 <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image053.gif">
　　 </SUB>即为所求。
　　仍非整数解，再对(4.8)式分支如下
　　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image055.gif"> </SUB>         (4.8)’
　　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image057.gif"> </SUB>          (4.9)’
　　易知(4.9)’仍无解，只解(4.8)’，可得解
　　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image059.gif"> </SUB>
　　再分支一次（过程略）即可得到
<SUB>　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image060.gif"> </SUB>，而<I>x</I><I><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image061.gif"> </SUB></I><I><SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image062.gif"> </SUB></I>12，故得<I>x</I><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image063.gif"> </SUB><SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image064.gif"> </SUB>4
　　代入料头函数　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image065.gif">
　　</SUB>知当<I>x</I><SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image066.gif"> </SUB>=4时,<I>y</I>取最小值<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image068.gif"> </SUB>，将<I>x</I><SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image069.gif"> </SUB>=4代入<I>x</I><SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image071.gif"> </SUB>,<I>x</I><SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image073.gif"> </SUB>表达式便得到整数解　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image075.gif"> </SUB>即为所求。</P>

yunjiang

　　如果这一步解仍非整数，则只须对非整数解变量继续分支定界求解即可。进一步的问题可参考整数规划相关资料。
　　问题是，经过这样处理感到不太令人满意的是料头函数的最小值变大了。一般地，对同一个问题加限制性条件的结果必导至可行域缩小，因而使目标值受损，这是很正常的。
　　好在本题的两种方案尽管目标值不同，但所用的原料数是相同的，均为34根，且剩料中，按原圆整方案剩下14个0.1米长料头，20个0.2米长料头。而按后一方案，除去12个0.1米长料头和18个0.2米长料头，还有4个0.9米长料头，一旦可利用料头，第二个方案或许还能派上4个0.9米长料头的用处呢。
　　实际中的线性规划模型通常要比上述例子复杂，看下例。

yunjiang

　　<b>例3</b>  某厂生产代号为<I>I</I>、<I>II</I>、<I>III</I>的三种产品，都分别经<I>A</I>、<I>B</I>两道工序加工。其中<I>A</I>工序可分别在设备<I>A</I><SUB>1</SUB>或<I>A</I><SUB>2</SUB>上完成，有<I>B</I><SUB>1</SUB>、<I>B</I><SUB>2</SUB>、<I>B</I><SUB>3</SUB>三种设备可用于完成<I>B</I>工序。已知产品<I>I</I>可在<I>A</I>、<I>B</I>任何一种设备上加工；产品<I>II</I>可在任何规格的<I>A</I>设备上加工，但完成<I>B</I>工序时，只能在<I>B</I><SUB>1</SUB>设备上加工；产品<I>III</I>只能在<I>A</I><SUB>2</SUB>与<I>B</I><SUB>2</SUB>设备上加工。加工单位产品所需工序时间及其它各项数据见表4-3。试安排最优生产计划，使该厂获利最大。
<B>　　</B><B>问题分析与假设</B>
　　1．这是一个产品生产与加工安排问题，涉及三种产品、两道工序和五种设备，而建模目的是给出一个生产计划使获利最大，故为线性规划问题。
　　　　　　　　　　　　　　表4-3
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image084.gif">

yunjiang

　2．如果简单地假设产品<I>I</I>、<I>II</I>、<I>III</I>的产量为<I>x</I><SUB>1</SUB>、<I>x</I><SUB>2</SUB>、<I>x</I><SUB>3</SUB>，建模会遇到困难。事实上，每种产品不仅要求有产量，还要有对应加工设备和工序问题。考虑到其间对应关系，可按产品<I>I</I>、<I>II</I>、<I>III</I>分类考虑，并同时注意对应加工设备。
　　3．依上述分析我们假设：
<I>　　</I><I>x<SUB>ij</SUB></I>——表示产品<I>I</I>在两种设备<I>A<SUB>i</SUB></I>、<I>B<SUB>j</SUB></I>上加工的数量，其中<I>i</I>=1,2;<I>j</I>=1,2,3.
<I>　　y</I><SUB>1</SUB>,<I>y</I><SUB>2</SUB>——表示产品<I>II</I>在<I>A</I><SUB>1</SUB>、<I>B</I><SUB>1</SUB>上加工的数量和在<I>A</I><SUB>2</SUB>、<I>B</I><SUB>1</SUB>上加工的数量。
<I>　　</I><I>x</I>——表示产品<I>III</I>在<I>A</I><SUB>2</SUB>、<I>B</I><SUB>2</SUB>上加工的数量。
　　模型建立
　　由假设及设备有效台时，资源约束应为：
<I>　　</I><I>A</I><SUB>1</SUB>：（<I>x</I><SUB>11</SUB>+<I>x</I><SUB>12</SUB>+<I>x</I><SUB>13</SUB>）×5+10<I>y</I><SUB>1</SUB>≤6000，
<I>　　</I><I>A</I><SUB>2</SUB>：（<I>x</I><SUB>21</SUB>+<I>x</I><SUB>22</SUB>+<I>x</I><SUB>23</SUB>）×7+9<I>y</I><SUB>1</SUB>+12<I>x</I>≤10000，
<I>　　</I><I>B</I><SUB>1</SUB>：（<I>x</I><SUB>11</SUB>+<I>x</I><SUB>21</SUB>）×6+8（<I>y</I><SUB>1</SUB>+<I>y</I><SUB>2</SUB>）≤4000，
<I>　　</I><I>B</I><SUB>2</SUB>：（<I>x</I><SUB>12</SUB>+<I>x</I><SUB>22</SUB>）×4+11<I>x</I>≤7000，
<I>　　</I><I>B</I><SUB>3</SUB>：（<I>x</I><SUB>13</SUB>+<I>x</I><SUB>23</SUB>）×7≤4000，
　　显然有<I>x<SUB>ij</SUB></I>≥0，<I>i</I>=1,2;<I>j</I>=1,2,3;<I>y</I><SUB>1</SUB>,<I>y</I><SUB>2</SUB>≥0,<I>x</I>≥0。

yunjiang

　用<I>Z</I>表示利润函数，则因每件产品的利润都涉及其售价（毛收入）和两项成本费用，即原料费和设备加工费，分类讨论如下：
　　产品<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image077.gif"> </SUB>利润为
　　（1.25-0.25）(<I>x</I><SUB>11</SUB>+<I>x</I><SUB>12</SUB>+ <I>x</I><SUB>13</SUB>+ <I>x</I><SUB>21</SUB>+ <I>x</I><SUB>22</SUB>+ <I>x</I><SUB>23</SUB>) -0.05×(<I>x</I><SUB>11</SUB>+ <I>x</I><SUB>12</SUB>+<I>x</I><SUB>13</SUB>)×5-0.03×(<I>x</I><SUB>21</SUB>+ <I>x</I><SUB>22</SUB>+ <I>x</I><SUB>23</SUB>)×7-0.06×(<I>x</I><SUB>11</SUB>+ <I>x</I><SUB>21</SUB>)×6-0.11×(<I>x</I><SUB>12</SUB>+ <I>x</I><SUB>22</SUB>)×4-0.05×(<I>x</I><SUB>13</SUB>+ <I>x</I><SUB>23</SUB>)×7
　　=0.39 <I>x</I><SUB>11</SUB>+0.31 <I>x</I><SUB>12</SUB>+0.4 <I>x</I><SUB>13</SUB>+0.43 <I>x</I><SUB>21</SUB>+0.35 <I>x</I><SUB>22</SUB>+0.44 <I>x</I><SUB>23</SUB>
　　产品<I>II</I>的利润为
　　（2-0.35）(<I>y</I><SUB>1</SUB>+<I>y</I><SUB>2</SUB>)-[0.05×10<I>y</I><SUB>1</SUB>+0.03×9<I>y</I><SUB>2</SUB>+0.06×(<I>y</I><SUB>1</SUB>+<I>y</I><SUB>2</SUB>)×8]=0.67<I>y</I><SUB>1</SUB>+0.9<I>y</I><SUB>2</SUB>
　　产品<I>III</I>的利润为
　　（2.8-0.5）<I>x</I>-0.03×12<I>x</I>-0.11×11<I>x</I>=0.73<I>x</I>
　　综之便得本问题数学模型。
　　 <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image079.gif">
　　 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_18/htm/sxjm18.files/image081.gif"> </SUB>
　　由于本模型只能用单纯形法求解，故略去。