《线性规划及其应用》由会员分享,可在线阅读,更多相关《线性规划及其应用(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问题解的概念,