§40一1型整数规划 0一1型整数规划是整数规划的特殊情形，它的决策变量 仅取0或1这两个值，这时的决策变量也称为0一1变量。在实 际问题中，有些问题只需回答“是”或“否”，问题就解决 了，描述这类问题的变量只需取两个值就可以了。例如是否 采纳某个方案；某项任务是否可以交某人承担；集装箱内是 否装入某种货物等等。对于这类问题我们可以用逻辑变量来 描述： 1,是 X= 0,否
§4 0—1 型整数规划 0—1 型整数规划是整数规划的特殊情形，它的决策变量 仅取0或1这两个值，这时的决策变量也称为0—1 变量。在实 际问题中，有些问题只需回答“是”或“否”，问题就解决 了，描述这类问题的变量只需取两个值就可以了。例如是否 采纳某个方案；某项任务是否可以交某人承担；集装箱内是 否装入某种货物等等。对于这类问题我们可以用逻辑变量来 描述： = 否 是 , , 0 1 x
4.1引入0一1变量的实例 1.确定投资方案 相互排斥的计划 例4某市工商银行拟抽调a万元资金对小五金、小百货和洗 涤剂三个行业给予低息贷款。由于资金有限，只能在四个小五金 企业A、A、A、A中至多选两个；在五个小百货企业A、A6 A、A中至多选三个；在四个洗涤剂企业A,、A1o、A1、A12中 至多选两个给予低息贷款。已知企业A得到贷款a万元后，可获 利b万元。问工商银行应如何发放贷款，可使总利润最大？ 解：因为本问题只要求解决是否给企业贷款，因此可用0一1 变量描述所求方案。设 1,给A贷款 0,不给4否贷款1=12,12 于是，根据题意， 本问题可描述为： max ≤2 盒xs2 X=0或1，=1,2，…，12
4.1 引入0—1 变量的实例 1.确定投资方案——相互排斥的计划 例4 某市工商银行拟抽调a万元资金对小五金、小百货和洗 涤剂三个行业给予低息贷款。由于资金有限，只能在四个小五金 企业A1、A2、A3、A4 中至多选两个；在五个小百货企业A5、A6、 A7、A8 中至多选三个；在四个洗涤剂企业A9、A10、A11、A12 中 至多选两个给予低息贷款。已知企业Ai得到贷款ai万元后，可获 利bi万元。问工商银行应如何发放贷款，可使总利润最大？ 解：因为本问题只要求解决是否给企业贷款，因此可用0—1 变量描述所求方案。设 = , =1,2,,12 i 不给A否贷款 给A 贷款 , , 0 1 i i i x 于是，根据题意，本问题可描述为： maxZ= = 12 i 1 i i bx a x a i i i = 12 1 2 4 1 i= i x 3 9 5 i= i x 2 12 10 i= i x Xi=0或1,i=1,2, …,12
这是一个0一1整数规划问题。与其相类似的问题很多，比 如：投资项目的选择；投资场所的选定；工厂的选址；新产品 开发方案的确定等等。总之，凡是一些相互排斥的计划、方案 的确定问题都可以归结为与例4类似的0一1整数规划问题。 2.相互排斥的约束条件 回顾本章例1，用集装箱托运甲、乙两种货物，根据每件货 物的体积、重量、可获利润，以及集装箱的托运限制得整数规划 模型如下： (x1,2分别表示甲、乙货物托运的件数) maxZ=20x+10x2 (1) 5x1+4x2≤24 (2) 2x1+5x≤13 (3) X1,X2≥0，整数 (4) 今设集装箱有车运和船运两种方式，(3)式是车运时的重 量限制条件。如用船运时关于重量的限制条件为2x,+5x,≤20 试确定集装箱托运甲、乙货物的数量及运输方式，使总利润最大 为了建立问题的模型，除了设甲、乙货物托运的件数分别为 xx外，还要把运输方式表示出来。由于只有两种运输方式，所
这是一个0—1整数规划问题。与其相类似的问题很多，比 如：投资项目的选择；投资场所的选定；工厂的选址；新产品 开发方案的确定等等。总之，凡是一些相互排斥的计划、方案 的确定问题都可以归结为与例4 类似的0—1整数规划问题。 2.相互排斥的约束条件 回顾本章例1，用集装箱托运甲、乙两种货物，根据每件货 物的体积、重量、可获利润，以及集装箱的托运限制得整数规划 模型如下： （x1 ,x2分别表示甲、乙货物托运的件数） maxZ=20x1+10x2 ⑴ 5x1+4x2 ≤24 ⑵ 2x1+5x2 ≤13 ⑶ x1 ,x2 ≥0，整数 ⑷ 今设集装箱有车运和船运两种方式，（3）式是车运时的重 量限制条件。如用船运时关于重量的限制条件为 2x1+5x2 ≤20 试确定集装箱托运甲、乙货物的数量及运输方式，使总利润最大。 为了建立问题的模型，除了设甲、乙货物托运的件数分别为 x1 ,x2外，还要把运输方式表示出来。由于只有两种运输方式，所
以可设 1,车运 0,船运 在约束条件中，两种不同运输方式对应的重量约束条件是相互 排斥的，所以不能简单地将它们都写到约束中。利用y这个0一1 变量可以将上述两个重量约束改写成： 2x1+5x2≤13+(1-y)M (5) 2X,+5x,≤20+yM (6) 其中M是相当大正数，显然当y=1时，（⑤）式就是车运的重量限制 条件，而(6)式自然成立，因而是多余的；当y=O时，(6)式就是船 运的重量限制条件，而（⑤）式成为多余的。经过这样处理后，问 题的数学模型可以写成如下形式： maxZ=20x+10x2 5x1+4x,≤24 2x+5x,≤13+(1-y)M 2x+5x20+yM X1,X2≥0，整数 y=0或1
以可设 = 船运 车运 , , 0 1 y 在约束条件中，两种不同运输方式对应的重量约束条件是相互 排斥的，所以不能简单地将它们都写到约束中。利用y这个0—1 变量可以将上述两个重量约束改写成： 2x1+5x2 ≤13+（1-y）M ⑸ 2x1+5x2 ≤20+yM ⑹ 其中M是相当大正数，显然当y=1时，⑸式就是车运的重量限制 条件，而⑹式自然成立，因而是多余的；当y=0时，⑹式就是船 运的重量限制条件，而⑸式成为多余的。经过这样处理后，问 题的数学模型可以写成如下形式： maxZ=20x1+10x2 5x1+4x2 ≤24 2x1+5x2 ≤13+（1-y）M 2x1+5x2 ≤20+yM x1 ,x2 ≥0，整数 y=0或1
类似地，如果有m个相互排斥的约束条件： ai1x1tai2x2+·…+ainXn≤b1 (i=1,2,m) 为了保证这m个条件只有一个起作用，可以引入m个0一1变 量y1(i=1,2,m)和充分大正常数M,将这个约束条件改写成： aiix1+ai2x2+…+ainXni≤b:+yiM (i=1,2,.m) y1+y2+.+ym-=m-1 显然，这些y:中只能有一个取0值，因而这个约束只能有一个 起作用，而其余都是多余的
类似地，如果有m个相互排斥的约束条件： ai1x1 +ai2x2 +‥‥+ainxn≤bi （i=1,2,…m) 为了保证这m个条件只有一个起作用，可以引入m个0—1变 量 yi（i=1,2,…m)和充分大正常数M，将这个约束条件改写成： ai1x1 +ai2x2 +‥‥+ainxn≤bi+yiM （i=1,2,…m) y1 +y2 +…+ym =m-1 显然，这些yi中只能有一个取0值，因而这m个约束只能有一个 起作用，而其余都是多余的