《线性规划及其应用》由会员分享，可在线阅读，更多相关《线性规划及其应用（119页珍藏版）》请在金锄头文库上搜索。
1、1,第二章 线性规划及其应用,线性规划研究的主要内容,线性规划主要解决两个方面的问题： （1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？ （2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？,线性规划内容框架,2,3,第一章 LP问题的数学模型与求解,4,解：,设x1,x2分别表示在计划期内生产产品、的产量。由于资源的限制，所以有：,机器设备的限制条件:x1+2x28 原材料A的限制条件： 4x116 （称为资源约束条件） 原材料B的限制条件： 4x212 同时，产品、的产量不能是负数，所以有 x10，x20 （称为变量的非负约束） 显然，在满足上述约束条件下
2、的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数Z=2x1+3x2 的值达到最大。,5,综上所述，该生产计划安排问题可用以下数学模型表示：maxz=2x1+3x2,例2. （营养配餐问题） 假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能使在满足营养的前提下使购买食品的总费用最小？,6,解:设xj(j =1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为minz
3、=10x1+6x2+3x3+2x4,7,例3 运输问题（课本P6）,某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保证产销平衡的条件下，如何调运可使总运费最少？,8,解:（1）确定决策变量：设xij(i=1,2,3;j=1,2,3,4)为从产地i运到销地j的运量,（2）确定目标函数：总运费最小 minz=,（3）确定约束条件：,x11+x12+x13+x14=60 产量约束： x21+x22+x23+x24=40x31+x32+x33+x34=60,x11+x21+x31=30销量约束： x12+x22+x32=50x13+x23+x33=40x14+x24+x3
4、4=40,9,非负约束 xij0,由此模型总结为：,10,（二）LP问题的模型,上述几例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。,（1）每个问题都可用一组决策变量(x1,x2,xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。,（2）存在一组线性等式或不等式的约束条件。,（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。,11,满足以上三个条件的数学模型称为LP问题的数学模型，其一般形式为：max(或m
5、in)z=c1x1+c2x2+cnxn,（1.1),（1.2),（1.3),或紧缩形式,12,或矩阵形式,或向量形式：max(或min)z=cx,其中c=(c1,c2,cn)，称为价值系数向量；,称为技术系数矩阵(也称消耗系数矩阵),13,称为资源限制向量,X=(x1,x2,xn)T称为决策变量向量,下面我们再来看几个实际例子。 引例3 课本P60 例25（投资计划问题）某公司经调研分析知，在今后三年内有四种投资机会。第种方案是在三年内每年年初投资，年底可获利15%，并可将本金收回；第种是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；第种是在第二年的年初
6、投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第种是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大？,14,解：问题分析。该问题的实际投资背景如下表所示： （1）确定决策变量：设xij表示第i年对第j个方案的投资额,i=1,2,3; j=1,2,3,4,年份 一 二 三 四x11 1.15x11x12 1.45x12x21 1.15x21x23 1.65x23x31 1.15x31x34 1.35x34,15,（2）确定目标函数：第三年年未的本利和为maxz=1.65
7、x23+1.15x31+1.35x34,（3）确定约束条件： 每一年的投资额应等于当年公司拥有的资金数： x11+x12=3 x21+x23=1.15x11x31+x34=1.45x12+1.15x21,每个方案投资额的限制： x122 x231.5 非负约束：xij0,i=1,2,3;j=1,2,3,4 x341,16,引例4 （合理下料问题）要用一批长度为7.4米的园钢做100套钢架，每套钢架由2.9米、2.1米、1.5米的园钢各一根组成，问：应如何下料才能使所用的原料最省？解：问题分析：一根长度为7.4米的园钢，要裁出2.9米、2.1米、1.5米的料有多种裁法，如可裁出一根2.9米、二根
8、2.1米，也可裁出三根2.1米的。这样我们把所有裁法列举出来，如下表所示：,下料 方案根数 一 二 三 四 五 六 七 八 长度米2.9 1 1 1 2 0 0 0 02.1 2 0 1 0 1 2 3 01.5 0 3 1 1 3 2 0 4合计 7.1 7.4 6.5 7.3 6.6 7.2 6.3 6料头（米） 0.3 0 0.9 0.1 0.8 0.2 1.1 1.4,17,（1） 确定决策变量：设xj表示按第j种方案所用的园钢的数量 （2） 确定目标函数：问题要求所用原料最省，所用原料为： minz=x1+x2+x3+x4+x5+x6+x7+x8 （3） 确定约束条件：2.9米园钢的
9、数量限制 x1+x2+x3+2x41002.1米园钢的数量限制 2x1+x3+x5+2x6+3x71001.5米园钢的数量限制 3x2+x3+x4+3x5+2x6+4x3100非负限制 xj0，且为整数， j=1,2,8,建立线性规划模型的一般步骤： （1）确定决策变量； （2）确定目标函数； （3）确定约束条件。,18,引例5一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存量为2000万米3，储存费用为（70+100u）千元/万米3，u为存储时间（季度数）。已知每季度的买进卖
10、出价及预计的销售量如下表所示。,由于木材不宜久贮，所有库存木材应于每年秋末售完。为使售后利润最大，试建立这个问题的线性规划模型。,19,设yi分别表示冬、春、夏、秋四个季度采购的木材数，xij代表第i季度采购的用于第j季度销售的木材数。,20,引例6、有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表1所示。现有三种货物待运，已知有关数据列于表2。为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不超过15%，前、后舱之间不超过10%。问该货轮应装载A，B，C各多少件，运费收入为最大？试建立这个问题的线
11、性规划模型。,表1,21,设表示xij装于第j(j=1,2,3)舱位的第i(i=1,2,3)种商品的数量,舱位载重限制,舱位体积限制,商品数量限制,平衡条件,22,引例7 . (仓库租用问题)捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资.已知各月份所需仓库面积数列于表1.仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表2.租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要,在任何一个月初办理租借合同.每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小.,表1,表2,2
12、3,解:1)设决策变量xij表示捷运公司在第i(I=1,2,3,4)个月初签订的租借期为j(j=1,2,3,4)个月的仓库面积的合同(单位为100m2).因5月份起该公司不需要租借仓库,故x24,x33,x34,x42,x43,x44均为零,2)目标函数:使总的租借费用最小,3)约束条件:每个月份所需仓库面积的限制,24,引例8 (混合配料问题)某糖果厂用原料A,B,C加工成三种不同牌号的糖果甲,乙,丙.已知各种牌号糖果中A,B,C含量,原料成本,各种原料的每月限制用理,三种牌号糖果的单位加工费及售价如下表所示.问该厂每月生产这三种牌号糖果各多少时,使该厂获利最大.试建立这个问题的线性规划模型
13、.,25,解:1)设决策变量xij表示生产第j种糖果(j=1,2,3,表示甲,乙丙三种糖果)耗用的第 i种原料(i =1,2,3表示A,B,C三种原料)的kg数,2)目标函数:该厂的获利为三种牌号糖果的售价减去相应的加工费和原料成本.,3)约束条件:,原料月供应量限制,含量成份的限制,26,（三）LP问题的标准型,1.为了讨论LP问题解的概念和解的性质以及对LP问题求解方便，必须把LP问题的一般形式化为统一的标准型：,或,maxz=cx,标准型的特点： 目标函数是最大化类型 约束条件均由等式组成 决策变量均为非负 bi(i=1,2,n)=0,27,2.化一般形式为标准型 目标函数：minzmax(-z)=-cx 若约束为“”型左边+松驰变量；若约束为“”型左边“松驰变量” 若变量xj0-xj0变量，若变量xj无限制令xj=xjxj 若右边常数bi0等式两边同乘以(-1)。,例4 课本P9 化下述问题为标准型 minz=-x1+2x2-3x3x1+2x2+3x37s.t. -x1+x2-x3-2-3x1+x2+2x3=5x1,x30,x2无约束,28,解：首先考察变量：令 ，并加入松驰变量x4,x5化为如下标准型：,练习：课本P64 2.2（3）,29,解：令,则,加入松驰变量s,w，得到标准型如下：,30,（四）LP问题解的概念,
