0 1规划.pptVIP

第4节 0-1型整数线性规划 一、0-1规划问题的概念 在整数规划问题中，若变量xi取值为0或者1，则为0-1规划问题;并称xi为0-1变量，或称布尔（Boole）变量。 注意：①xi仅取值0或1这个条件可由下述约束条件所代替。 xi≤1, xi≥0，整数 ②如果变量xi不是仅取值0或1，而是可取其他范围的非负整数，这时可利用二进制的记数法将它用若干个0-1变量来代替。例如，在给定的问题中，变量x可任取0与10之间的任意整数时，令x=20x0+21x1+22x2+23x3. 这时，x就可用4个0-1变量x0，x1，x2，x3来代替。。 二、引入0-1变量的实际问题 1. 投资场所的选定——相互排斥的计划 例 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai (i=1，2，…，7)可供选择。规定： 在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大? 2. 相互排斥的约束条件 在本章开始的例1中，关于运货的体积限制为 5x1+4x2≤24 (5-9) 今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为 7x1+3x2≤45 (5-10) 这两条件是互相排斥的。为了统一在一个问中，引入0-1变量y，令 于是(5-9)式和(5-10)式可由下述的条件(5-11)式和(5-12)式来代替： 5x1+4x2≤24+yM (5-11) 7x1+3x2≤45+(1-y)M (5-12) 其中M是充分大的数。读者可以验证，当y=0时，(5-11)式就是(5-9)式，而(5-12)式自然成立，因而是多余的。当y=1时(5-12)式就是(5-10)式，而(5-11)式是多余的。引入的变量y不必出现在目标函数内，即认为在目标函数式内y的系数为0。 为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,…，m)和一个充分大的常数M，而下面这一组m+1个约束条件 αi1x１+αi2x2+…+αinxn≤bi+yiM， i=1,2,…，m (5-13) y1+y2+…+ym=m-1 (5-14) 就合于上述的要求。这是因为，由于(5-14)式，m个yi中只有一个能取0值，设yi*=0，代入(5-13)式，就只有i=i*的约束条件起作用，而别的式子都是多余的。 习题求解 人数和工作数不等的指派问题 2.一个人可做几项工作的指派问题 3.某项工作一定不能由某人做的指派问题 最大化指派问题 A1可同时做三项工作 A1不能做B4; A3不能做B3 * * 解题时先引入0-1变量xi (=1,2，…，7) 于是问题可列成： 如果有m个互相排斥的约束条件(≤型)： αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m 现实生活之中，我们经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂 。 The Assignment Problem 指派问题 典型问题 例：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。 甲 乙 丙 丁 工作 人 译英文 译日文 译德文 译俄文 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 问：如何分配，能使所需的总时间最少？ 建立模型： Min z = ? ? aijxij (aij---效率) i=1j=1 4 4 设 xij= 1 0 若第i项工作交与第j个人完成 若第i项工作不交与第j个人完成 译英文： x11+ x12 + x13 + x14 =1 译日文： x21+ x22 + x23 + x24 =1 译德文