5北交大经管学院939管理运筹学教案讲义很详细有较多例题价值第7章整数

1、第四节0-1整数规划问题的提出：0-1整数规划是线性规划及整数规划的一种特殊形式。模型结构和形式是线性规划，只是决策变量取0或1。0-1规划模型的建立方法例1：投资场所的选定某公司拟在城市的东、西、南三区建立，拟议中有七个位置Ai（i=1, 2,7), 如选用Ai点,设备投资估计为bi元, 每年可获利润估计为ci元, 但投资总额利润为最大?过B元, 问应选择那几个点年1当Ai点被选用xi=1, ,7 0令i当Ai点未被选用7maxZcxiii17bxBiis . tix10or1i另外，项目有一些规定在A1,A2,A3三个点中至多选两个;在A4,A5两点中至少选一个;在A6,A7中只能选一个；

2、A1,A7不能同时选；只有在A被选中的情况下，A 才能被选；某市共有6个区，每个区都可以设消防站。市希望设置消防站最少以便节省费用，但必须保证在城区任何地方发生火警时，消防车能在15分钟内赶到现场。据实地测定，各区之间消防车行驶时间如表2所示。建立该问题的规划模型。表2一区二区 三区 四区 五区 六区一区二区三区四区五区六区01000272125140例某厂拟采用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运(车运)所受限制如下表, 如采用船运, 其体积托运限制则为45,问两种货物托运多少箱，可使获得利润为最大？货物体积每箱（ m3）重量每箱（吨） 利润每箱（百元） 甲424乙51

3、3托运限制206解: 设x1, x2分别表示甲乙两种货物的托运箱数, 则其整数规划数学模型为Z4 x 1max3 x22442xx x55xx x22045yM( 1 12y ) M12s . t610 x 1 , xx 1 , x 2 取整数10其中当采用船运方式当采用车运方式y一般情况下, m个相互排斥的约束条件, 则可变成为:ai1x1+ai2x2+ainxnbi+yiM, y1+y2+ym=m-1其中yi是0, 1变量，且只有一个取0。若上述个方程中，至少有个方程必须满足时（约束条件相容）？i=1,2,m例设两种产品的利润分别为1,2，需要的工时是和，成本和工时的关系，确定产品的产量。

4、成本，要求建立整数规划模型，200001500010000工时200030005000Max Z=c1x1+c2x2-10000y1-15000y2-20000y36x1+4x2 2000y1 y1+y2+y3=1yj 为0或1，x j 非负y2y3例4 某工厂有3种不同的生产方式可供选择，产量不同，固定成本和变动成本也不相同，各种方式的总成本为Kj+cjxj0 xj 0 xj =0pj=Min Z=(K1y1+c1x1 )+ （K2y2+c2x2 ）+（K3y3+c2x2 ）xj yjM0-1整数规划问题的解法若有n个决策变量, 则可以产生2n个可能变量的组合, 故完全枚举是不可能的. 求解

5、0-1整数规划问题的解法均是部分枚举法或称为隐枚举法(Implicit enumeration)是: 在2n个可能的变量组合中, 往往只有一部分是可行基本解. 只要发现某个变量组合不满足其中的某一约束条件时, 就不必要检验其它的约束条件是否可行。 若发现一个可行解, 则根据它的目标函数值可以产生一个过滤条件(Filtering constra), 对于目标函数值比它差的的变量组合就不必再去检验它的可行性（类似分支定界法中的定界。实际上，隐枚举法是一种特殊的分支定界法）。 在以后求解过程中, 每当发现比原来更好的可行解, 则依次替代原来的过滤条件 (可减少运算次数, 较快地发现最优解)。以例子说

6、明上述求解方法例1:求解下述0-1整数规划问题3maZx24s . tx 1 3x36x2 4x 230or1解：求解过程见下表所以，最优解为（x1，x2，x3)T=(1,0,1)T, 最优值为8.(x1,x2,x3)Z 值约束条件过滤条件（ 0,0,0）0Z0(0,0,1)5Z5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8Z8(1,1,0)1(1,1,1)6注： 当决策变量(x1, x2 , x3)按(0,0,0), (0,0,1), (0,1,0), (0,1,1),.方式取值时, 为了减少计算次数, 通常将目标函数中的决策变量的顺序按其系数的大小重新排序, 以使最优

7、较早出现。对最大化问题, 按从小到大的顺序排列；对极小化问题, 则相反。例2：求解下述0-1整数规划问题minZx1 x4x44403845s . t5x 4,3or1解：重新排序为miZnxx1x3658s . t3, 3x 4 0or1(x 2 ,x1 ,x4 ,x3 )Z 值约束条件 过滤条件 （ 0,0 ,0 ,0 ）0(0 ,0,0 ,1 )-1(0 ,0,1 ,0 )1(0 ,0,1 ,1 )0(0 ,1,0 ,0 )3(0 ,1,0 ,1 )2(0 ,1,1 ,0 )4(0 ,1,1 ,1 )3Z 3(1 ,0,0 ,0 )7(1 ,0,0 ,1 )6(1 ,0,1 ,0 )8(

8、1 ,0,1 ,1 )7(1 ,1,0 ,0 )10(1 ,1,0 ,1 )9(1 ,1,1 ,0 )11(1 ,1,1 ,1 )10练习：求解下述整数规划问题min Z 5 1 x4 x4 x5 x525362x2-xo1rs.t.-12 x5 ,2 ,1j0,5j第五节指派问题（Assignment Problem）1. 标准指派问题的提法及模型指派问题的标准形式是：有n个人和n件事，已知第i个人做第j件事的费用为cij（i，j=1，2，n），要求确定人和事之间的一一对应的指派方 案，使完成这n件事的总费用最小。1若指派第i个人做第j件事 xij设n2个0-1变量(i,j=1,2, n)0

9、若不指派第i个人做第j件事nn i 1j 1Zminc ij x ijn x ij1数学模型为: i 1n s .tx ij1 j 1j x0or1,i ,1, 2 , , nij其中矩阵C称为是效率矩阵或系数矩阵。其解的形式可用0-1矩阵的形式来描述，即 (xij)nn。标准的指派问题是一类特殊的整数规划问题，又是特殊的0-1问题。1955年W. W. Kuhn利用匈牙利数学规划问题和特殊的家D. Konig关于矩阵中独立零元素的定理, 提出了解指派问题的一种算法,上称之为匈牙利解法。2. 匈牙利解法匈牙利解法的关键是指派问题最优解的以下性质：若从指派问题的系数矩阵C=（cij）的某行（或某

10、列）各元素分别减去一个常数k，得到一个新的矩阵C=（c )，则以C和C为系数矩阵的两ij个指派问题有相同的最优解。（这种变化不影响约束方程组，而只是使目标函数值减少了常数k，所以，最优解并不改变。）作变换，其不变性是最优解对于指派问题，由于系数矩阵均非负，故若能在在系数矩阵中找到n和不同列的零元素（独立的0元素），则对应的指派方个位于不案总费用为零，从而一定是最优的。匈牙利法的步骤如下：步1：变换系数矩阵。对系数矩阵中的每行元素分别减去该行的最小元素；再对系数矩阵中的每列元素分别减去该列中的最小元素。若某行或某列已有0元素，就不必要在减了（不能出现负元素）。步2：在变换后的系数矩阵中确定独立0

11、元素（试指派）。若独立0元素已有n个，则已得出最优解；若独立0元素的个数少于n个，转步3。确定独立0元素的方法：当n较小时，可用观察法、或试探法；当n较大时，可按下列顺序进行从只有一个0元素的行（列）开始，给这个0元素加圈，记作，然后划去所在的列（行）的其它0元素，记作。给只有一个0元素的列（行）的0加圈，记作，然后划去所在行的0元素，记作。反复进行，直到系数矩阵中的所有0元素都被圈去或划去为止。如遇到行或列中0元素都不只一个（存在0元素的闭回路），可任选其中一个0元素加圈，同时划去素即是独立的0元素。和同列中的其它0元素。被划圈的0元步3：作最少数目的直线，覆盖所有0元素（目的是确定系数矩阵

12、的下一个变换），可按下述方法进行对没有的行打“”号；在已打“”号的行中，对 所在列打“”在已打“”号的列中，对所在的行打“”号；重复2）3），直到再也找不到可以打“”号的行或列为止；对没有打“”的行划一横线，对打“”的列划一纵线，这样就得到覆盖所有0元素的最少直线数。步4：继续变换系数矩阵，目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素中都减去这一元素，而在打“”列的各元素都加上这 一最小元素，以保持原来0元素不变（为了消除负元素）。得到新的系数矩阵，返回步2。以例说明匈牙利法的应用。例1：求解效率矩阵为如下的指派问题的最优指派方案。4979 1

13、2107109有0元素）解：第一步：系数矩阵的变换（目的是得到某行或52099 003108620007 209795212030645104710第二步：确定独立0元素520900310820007 2052元素的个数m=4，而n=5，进行第三步。0306456第三步：作最少的直线覆盖所有的0元素，目的是确定系数矩阵的下一个变换。50202230000210850709406365第四步：对上述矩阵进行变换，目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素中都减去这一元素，而在打“”列的各元素都加上这一最小元素，以保持原来0元素不变（消除负元素）

14、。得到新的系数矩阵。（它的最优解和原问题相同，为什么？）74003200002 00 000110000000100100000100354指派方案和最优值为32。由解矩阵例2 某大型工程有五个工程项目，决定向社会公开招标，有五家建筑能力相当的建筑公司分别获得中标承建。已知建筑公司Ai（I=1，2，3，4，5）的报价cij（百万元）见表，问该部门应该怎样分配建造任务，才能使总的建造费用最小？工程公司B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106Z 4 x8 x 10 x6 xmin 1j 1,2, ,5xij i 5 j xij

15、1i 1,2, ,5s.txij 0i, j 1,2, ,5or1有0元素）117解：第一步：系数矩阵的变换（目的是得到某行或000006307812 712023140935320467129610第二步：确定独立0元素, 即加圈000003073531172048120231 元素的个数m=4，而n=5，进4 行第三步。0第三步：作最少的直线覆盖所有的0元素，目的是确定系数矩阵的下一个变换。0301180120735720301 4 00 0234第四步：对上述矩阵进行变换，目的是增加独立0元素个数。方法是在未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素中都减去这一元素，而在打

16、“”列的各元素都加上这一最小元素，以保持原来0元素不变（消除负元素）。得到新的系数矩阵。（它的最优解和原问题相同，为什么？因为仅在目标函数系数中进行操作）0301161048130102062531161048 1202 016253 10 00 014 02400110 3010206253116104802 00 14 10 此矩阵中已有5个独立的0元素，故指派问题的最优指派方案为：0010001000100000001000001也就是说，最优指派方案为：让A1承建B3， A2承建B2，A3承建 B1，A4承建B4，A5承建B5。这样安排建造费用为最小，即7+9+6+6+6=34（百万元

17、）3. 一般的指派问题在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理方法是先将它们转化为标准形式，然后用匈牙利解法求解。最大化指派问题设最大化指派问题系数矩阵C中最大元素为m。令矩阵B=(bij)=(m-cij),则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。人数和事数不等的指派问题若人少事多，则添上一些虚拟的“人”。这些虚拟的人作各事的费用系数可取0，理解为这些费用实际上不会发生。若人多事少，则添上一些虚拟的“事”。这些虚拟的事被各人做的费用系数同样也取0。一个人可做几件事的指派问题若某个人可做几件事，则可将该人看做相同的几个人来接受指派。这几

18、个人作同一件事的费用系数当然都一样。某事一定不能由作的指派问题若某事一定不能由某个人做，则可将相应的费用系数取做足够大的数M。例3：对于例2的指派问题，为了保证工程质量，经研究决定，舍 弃建筑公司A4和A5，而让技术力量较强的建设公司A1，A2，A3参加招标承建，根据实际情况，可允许每家建设公司承建一项或二项工程。求使总费用最少的指派方案。工程公司B1B2B3B4B5A14871512A279171410A3691287解：由于每家建筑公司最多可以承建两项，因此可把每家建筑公司看成两家建筑公司，其系数矩阵为B41B2B3B 415B5 1A287A 3上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟的事B6，使之成为标准指派问题的系数矩阵：BBBBBBA 1A 1 0A02487812 4715141079A 2A 30 97 66121288 97 A 30 费用最省为4+7+9+8+7=35（百万元）然后，用匈牙利解法求解。练习：某最大化指派问题的效率矩阵如下，求最优