第八章 线性规划和整数规划.doc

第八章 线性规划和整数规划线性规划模型(Linear Programming model)是在一组线性的限制式(a set of linear constraints)之下，寻找极大化(maximize)或极小化(minimize)一个特定的目标函数(objective function) ，线性规划模型由下列三个部分组成: 一组决策变量 (A set of decision variables) 一个特定的目标函数(An objective function) 一组线性的限制式 (A set of constraints)线性规划的特点是：参数具有“确定性”；目标函数与限制符合“固定规模报酬”的假设；决策变量间没有互动性，即某个函数的总价值只能借由线性累加求得；变量值在某一范围之内。81简单线性规划简单线性规划就是直接利用题目给出的约束关系构建约束函数，利用数学方法直接进行求解，有效率高、程序简单等优点。下题就是简单线性规划的一个典型例子：811案例1：炼金术好几个世纪以来，如何从铅得到金一直困扰着炼金学家们。在最近的一次炼金俱乐部会议上，宣布了一个重大的突破。通过将三种化学药品Algolene、Vasicine及Cobolase（简称A、B、C）以正确的比例混合，可以生成一种能将铅转换成金的混合物，由于A、B、C一般不单独出售，而是混合成溶液出售，所以这个问题并不像看起来那么简单。考虑以下的例子。有两种由A、B及C组成的混合物，比例分别为1:2:3和3:7:1。将这两种混合物再以1:2的比例混合，我们得到一种A、B、C的溶液，比例为7:16:5。但没有办法能将这两种混合物混合成比例为3:4:5的新溶液。但如果我们增加一种溶液，其含有A、B、C三种物质的比例为2:1:2，那么将八分的1:2:3、一份的3:7:1和五份的2:1:2混合后就可以得到3:4:5的混合物。决定将给定的一组溶液以何种比例混合并不是件轻松的任务。但是，正如ACM所表明的，这可能是一件利润丰厚的任务。你必须写一个程序以寻找混合比例。输入输入文件包含多个测试数据。每个测试数据的第一行包含一个整数n(0n100)，代表了测试数据中混合物的数目。接下来的n行每行包含三个非负整数ai、bi、ci，指明了A、B、C在第i种混合物中出现的比例为ai:bi:ci。每种混合物的三个整数中至少有一个是正的。最后，有包含三个非负的整数a、b、c的一行，指明了所需溶液的比例为a:b:c。输入文件由最后一个测试数据之后仅含整数0的一行结束。输出对于每一个测试数据，输出单词“Mixture”，其后跟着测试数据的编号。在下一行中，如果能通过混合输入的溶液得到所需溶液，则输出单词“possible”，否则的话，输出单词“impossible”。输入范例21 2 33 7 13 4 531 2 33 7 12 1 23 4 50输出范例Mixture 1impossibleMixture 2Possible算法分析该题实际上是一门线性代数题，要求选手通过计算机编程求解。设xi为第i种溶液取出的比例(xi0，1in)；ai，bi，ci为第i种溶液中A、B、C三种物质的比例(ai，bi，ci0，1in)；x，y，z为混合溶液中A、B、C三种物质的比例。能否从铅中提炼出金子，就是判断下述非齐次线性方程组a1x1+a2x2+.+anxn=xb1x1+b2x2+.+bnxn=yc1x1+c2x2+.+cnxn=z是否有解。该非齐次线性方程组的增广矩阵为常量系数矩阵 xa1anA= yb1bn zc1cn如果n3，则增添(3-n)个全零的列向量，使得系数矩阵的规模扩充至34。 3-n个全0的列向量0.增广矩阵0.0.34n+1个列向量这个非齐次线性方程组有解的充分必要条件是增广矩阵与系数矩阵的秩相等。所谓矩阵的秩就是矩阵中最大一个非零子行列式的规模。显然矩阵A的秩小于等于3。正因为如此，我们每次仅取三种溶液，其他溶液不取，设这三种溶液的序号分别为i，j，k(ijk，1i，j，kn)，即aixi+ajxj+akxk=xbixi+bjxj+bkxk=ycixi+cjxj+ckxk=z混合溶液中A、B、C的比例x ai aj ak b10 b11 b12 b13对应的增广矩阵为B=y bi bj bk =b20 b21 b22 b23z ci cj ck b30 b31 b32 b33i，j，k三种溶液中A，B，C的比例我们采用主元消去对矩阵B进行初等变换，使其系数矩阵变成一个单位矩阵x 1 0 0B=y 0 1 0z 0 0 1注意，变换后非零的行向量可能会减少，初始时设行数pm=3我们从第1行开始搜索每一行向量，若第i行(1ipm)中的三个系数bi1，bi2，bi3全0，则分析同行的常量bi0：1 若bi00，则不可能使bi1*xi+bi2*xj+bi3*xk =bi00，因此方程组无解；2 若bi0=0，则消去第i行（i行向量与pm行向量对换，pmpm-1;ii-1）；如果l行向量中的一个系数blk0，则称blk为主元。通过下述变换关系式进行消元。变换后矩阵各元素为 blj/blki=lbij = bij-(blj/blk)bikil（1ipm，1j，k3）使得第k列向量中除第1元素blk=1外，其余元素为0。上述一直进行至无解退出或者指针ipm为止（目前系数矩阵为单位矩阵或者产生0矩阵）。最后分析目前矩阵方程的常量b1,0,bpm,0：如果都大于等于0，说明变换后矩阵对应的方程组有解且符合题意。根据线性代数中矩阵初等变换的等价原理“若矩阵B经有限次初等变换后变换成矩阵B，则B的行向量组与B的行向量组等价”，因此可以断定aixi+ajxj+akxk=xbixi+bjxj+bkxk=ycixi+cjxj+ckxk=zxp=0(pi、j、k，1pn)有解。例如，有五种溶液：第一种溶液中A、B、C三种物质的比例为a1=1，b1=2，c1=3；第二种溶液中A、B、C三种物质的比例为a2=3，b2=7，c2=2；第三种溶液中A、B、C三种物质的比例为a3=2，b3=1，c3=2；第四种溶液中A、B、C三种物质的比例为a1=1，b1=2，c1=3；第五种溶液中A、B、C三种物质的比例为a1=2，b1=3，c1=4；如果五种溶液配置成A、B、C的比例为x=3，y=4，z=5的特殊混合溶液，便可以提炼金子。求解过程如下。先列出对应得非齐次方程组和增广矩阵x1+3x2+2x3+x4+2x5=33 1 3 2 1 22x1+7x2+x3+2x4+3x5=4A=4 2 7 1 2 35 3 2 2 3 43x1+2x2+2x3+3x4+4x5=5令x4=x5=0，得出3 1 3 231329101127/25100B =4 2 7 1-201-3-201-34/250105 3 2 2-40-7-4-1800-2518/25001按照x1=27/25、x2=4/25、x3=18/25、x4=x5=0的比例提取5种溶液，便可产生满足要求的混合溶液。上述消元法可描述如下：设i为行向量序号；pm为目前非零的向量行数；pm=3;i=0;while(ipm)i+;if(bi1bin全0)if(bi0=0)i行向量与pm行向量对换;pm-;i-;else无解退出else/bi1bin中有bij0(1jn)for(r=0;rn;r+)bir/=bij;for(r=1;rpm;r+)if(r!=i)for(s=0;sn;s+)brs-=brj*bis;if(b1,0bpm,0非全零)方程有解退出;现有n种溶液。如果n3时，究竟应该取哪三种溶液无法预知，因此只能枚举n种溶液中取3种溶液的全部组合。设三种溶液的一个组合序列为m,其中mi为组合中第i种溶液的一个序号（1i3）。规定组合中的3个溶液序号按递增顺序排列，即mimi-1+1n-3+i。只有其中一个组合m对应的方程组am1xm1+am2xm2+am3xm3=xbm1xm1+bm2xm2+bm3xm3=ycm1xm1+cm2xm2+cm3xm3=z有解，即可断定混合方案存在。如果c(n，3)个组合对应的方程组都无解，则断定混合方案不存在。为此，我们设计了一种solve(s)过程，其中s为组合m的元素序号（1s3）：void solve(s)if(s3)对m组合对应的方程组进行消元变换，判断是否有解；elsefor(i=ms-1+1;in-(3-s);i+)ms=i;solve(s+1);if(m组合对应的方程组有解)exit;ms=0;在主程序中调用solve(如果一个m组合对应的方程组有解，则输出“possible”;否则输出“impossible”。程序题解82整数规划821案例2：装箱问题例1 四件物品将装入一容量为20的集装箱。已知每种物品每装入一件所占用的容量和可获得的效益如下表所示。1234每件物品占用的容量2354每件物品的效益110160260210问：如何安排装箱计划，才能使集装箱中的物品有最大的总效益？注：集装箱只有装满或剩余空间不能再容纳下任何一件物品时才有可能取得最大效益。 求解：设四件物品的装箱数量分别为：x1,x2,x3,x4 则该问题的数学模型为： max z = 110x1+160x2+260x3+210x4 其中， x1,x2,x3,x4为非负整数 且 2x1+3x2+5x3+4x420分析：已知集装箱的容量为201)若集装箱放入物品4的x4件，则 0x45 装入x4件物品4后，集装箱中容量消耗为4x4,但同时带来效益 210x4 此时，还能用来装物品1,2,3的剩余容量为 20-4x4 问题转化为：在容量为20-4x4的情况下，如何装物品1,2,3(即求x1,x2,x3)，才能相对于容量20-4x4产生最大的效益？ 重复以上步骤，可以对x1,x2,x3进行分析 若上面的x1,x2,x3都能确定了，则与x4一起所能带来的总效益值为 z = 110x1+160x2+260x3+210x4。 现求，能产生最大z值得x1,x2,x3,x4 仅就x4而言，x4的值等于多少，才能使箱中效益达到最大呢？求解： 现设一般情况：有n件物品，容器(集装箱)容量为M记：fn(M)为在容量为M时，装入所有n件物品所能带来的最大效益， xi表示装入第i件物品的数量（正整数或0)，i=1,2,n。则 x4的取值由递推式确定： 其中f3(20-4x4)是在容量为20-4x4时，装入1,2,3物品所能带来的最大效益。记当前容量为X,则一般情况下递推关系式有：注：xi的取值范围实例分析f0(k) = 0 故，当b=20时 (k20)有， f4(20)=1100 x4 = 0 依次递推得：x2=x3=x4