(2.1.1)--线性规划模型（NO2）.pdf

运运 筹筹 学学 第二讲第二讲 线性规划的模型建立线性规划的模型建立 线性规划线性规划(Linear Programming；LP)在第二次世界大战在第二次世界大战期间从军事应用中发展起来，是期间从军事应用中发展起来，是20世纪中叶最重要的科学世纪中叶最重要的科学进步之一。线性规划作为运筹学的重要分支，自从进步之一。线性规划作为运筹学的重要分支，自从1947年年美国学者美国学者G.B.Dantzig提出单纯形法以来，大量的研究成果提出单纯形法以来，大量的研究成果相继问世，其理论和方法更加趋于成熟，特别是计算机运相继问世，其理论和方法更加趋于成熟，特别是计算机运算处理能力的提高，新的应用领域不断地拓展。线性规划算处理能力的提高，新的应用领域不断地拓展。线性规划的理论与方法广泛应用于工业、农业、商业、交通运输业、的理论与方法广泛应用于工业、农业、商业、交通运输业、国防和经济管理等领域，成为现代科学管理与决策中不可国防和经济管理等领域，成为现代科学管理与决策中不可或缺的重要手段和有效方法。线性规划也是运筹学中最基或缺的重要手段和有效方法。线性规划也是运筹学中最基本的方法之一。网络分析、整数规划、目标规划和多目标本的方法之一。网络分析、整数规划、目标规划和多目标规划等都以线性规划为基础。规划等都以线性规划为基础。线性规划模型的建立线性规划模型的建立 线性规划的研究对象是稀缺资源最优分配问题，即将有线性规划的研究对象是稀缺资源最优分配问题，即将有限的资源限的资源(limited resource)以最佳的以最佳的(optimal)方法，分配于方法，分配于相互竞争的活动相互竞争的活动(competing activities)之中。一般体现为在之中。一般体现为在一定的资源条件下，如何合理使用，达到效益最高；或在一定的资源条件下，如何合理使用，达到效益最高；或在给定任务后，如何统筹安排，使资源耗费最低。由于许多给定任务后，如何统筹安排，使资源耗费最低。由于许多实际问题本质上是线性的，所以线性规划可以解决诸如生实际问题本质上是线性的，所以线性规划可以解决诸如生产计划、配料问题、运输问题、投资问题、劳动力安排和产计划、配料问题、运输问题、投资问题、劳动力安排和工业污染等许多方面的应用问题。工业污染等许多方面的应用问题。线性规划模型的建立线性规划模型的建立 4 一、典型的线性规划问题建模举例一、典型的线性规划问题建模举例 1 1、生产计划问题、生产计划问题 例例.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备备A A、B B加工，最后都需在设备加工，最后都需在设备C C上装配。经测算得到相关数据如表所上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。示。应如何制定生产计划，使总利润为最大。据市场分析，单位甲乙产品的销售价格分别为据市场分析，单位甲乙产品的销售价格分别为7373和和7575元，试确定获元，试确定获利最大的产品生产计划。利最大的产品生产计划。产品 设备 工时消耗 甲 乙 工时成本 元/h 生产能力 h A B C 2 0 0 2 3 4 20 15 10 16 10 32 线性规划模型的建立线性规划模型的建立 设生产甲x1单位，生产乙x2单位 A设备工时约束 B设备工时约束 1216x 2210 x C设备工时约束 123432xx利润=销售收入 -成本 =（）-（）-（）=217573xx 114030 xx 223040 xx 2153xx 5(1)决策变量决策变量：设设x1为甲产品的产量为甲产品的产量，x2为乙产品的产量为乙产品的产量。(2)约束条件约束条件：生产受设备能力制约生产受设备能力制约，能力需求不能突破有效供给量能力需求不能突破有效供给量。设备A的约束条件表达为 2 x1 16 同理，设备B的加工能力约束条件表达为 2x2 10 设备C的装配能力也有限，其约束条件为 3x1+4x2 32(3)目标函数：目标函数：目标是企业利润最大化目标是企业利润最大化 max Z=3x1+5x2 (4)非负约束：非负约束：甲乙产品的产量为非负甲乙产品的产量为非负 x1 0，x2 0 12121212max35216210s.t.3432,0Zxxxxxxx x综上的综上的LPLP模型：模型：线性规划模型的建立线性规划模型的建立 6 2 2、物资运输问题、物资运输问题 例：例：某产品商有三个供货源某产品商有三个供货源A1、A2、A3，其经销商有，其经销商有4个（需求个（需求市场）市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及。已知各厂的产量、各经销商的销售量及从从Ai 到到Bj 的单位运费为的单位运费为Cij。为发挥集团优势，公司要统一筹划运。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。销问题，求运费最小的调运方案。销地 产地 B1 B2 B3 B4 产量 A1 6 3 2 5 50 A2 7 5 8 4 20 A3 3 2 9 7 30 销量 20 30 10 40 线性规划模型的建立线性规划模型的建立 设从设从Ai到到Bj的运输量的运输量为为xij，产量约束 x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34=30 销量约束 x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40 目标费用最小 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 7(1 1)决策变量：决策变量：设从设从Ai到到Bj的运输量为的运输量为xij，(2 2)目标函数：目标函数：运费最小的目标函数为运费最小的目标函数为 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)(3)约束条件约束条件：产量之和等于销量之和产量之和等于销量之和,故要满足：故要满足：供应平衡条件供应平衡条件 x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34=30 销售平衡条件销售平衡条件 x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40 非负性约束非负性约束 xij0 (i=1,2,3；j=1,2,3,4)线性规划模型的建立线性规划模型的建立 8 3 3、配料问题、配料问题 某养鸡专业户某养鸡专业户,养鸡养鸡1000只只,用大豆和谷物饲料混合喂养用大豆和谷物饲料混合喂养,每每天每只鸡平均吃混合饲料天每只鸡平均吃混合饲料0.5公斤公斤;其中应至少含有其中应至少含有0.1公斤的蛋公斤的蛋白质和白质和0.002公斤钙公斤钙.已知每公斤大豆含有已知每公斤大豆含有50%的蛋白质和的蛋白质和0.5%的钙的钙,价格是每公斤价格是每公斤1.00元元;每公斤谷物含有每公斤谷物含有10%的蛋白质和的蛋白质和0.4%的钙的钙,价格是每公斤价格是每公斤0.30元元.粮食部门每周只保证供应谷物粮食部门每周只保证供应谷物饲料饲料2500公斤公斤,大豆供应量不限大豆供应量不限,问如何搭配这两种饲料问如何搭配这两种饲料,才能使才能使喂养成本最低喂养成本最低?线性规划模型的建立线性规划模型的建立 决策变量：决策变量：设每周供设每周供应大豆和谷物应大豆和谷物x1,x2公公斤斤 目标函数：目标函数：喂养成本最喂养成本最低低:minZ=x1+0.3x2 混合饲料总量应恰好为鸡混合饲料总量应恰好为鸡群一周的饲料群一周的饲料,从而有从而有 x1+x2=710000.5=3500,即即 x1+x2=3500 由蛋白质要求由蛋白质要求:50%x1+10%x2 710000.1=700 即即5x1+x2 3500 由钙要求由钙要求:0.5%x1+0.4%x2 710000.002=14 即即5x1+4x2 14000 谷物饲料限制谷物饲料限制:x22500 （1 1）决策变量：决策变量：设每周供应大豆和谷物设每周供应大豆和谷物x1,x2公斤公斤，0,25001400045700053500.3.0min21221212121xxxxxxxxxtsxxZ由钙要求由钙要求:0.5%x1+0.4%x2 710000.002=14 即即5x1+4x2 14000 混合饲料总量应恰好为鸡群一周的饲料混合饲料总量应恰好为鸡群一周的饲料,从而有从而有 x1+x2=710000.5=3500,即即 x1+x2=3500（2 2）目标函数：）目标函数：喂养成本最低喂养成本最低:minZ=x1+0.3x2（3 3）约束条件：）约束条件：由蛋白质要求由蛋白质要求:50%x1+10%x2 710000.1=700 即即5x1+x2 3500 谷物饲料限制谷物饲料限制:x22500 因此因此,综合而得其数学模型为综合而得其数学模型为:线性规划模型的建立线性规划模型的建立 10 二、构成线性规划模型的三个要素二、构成线性规划模型的三个要素 决策变量决策变量 决策问题待定的量值决策问题待定的量值 取值要求非负取值要求非负 约束条件约束条件 任何管理决策问题都是限定在一定的条件下求解任何管理决策问题都是限定在一定的条件下求解 把各种限制条件表示为一组等式或不等式称约束条件把各种限制条件表示为一组等式或不等式称约束条件 约束条件是决策方案可行的保障约束条件是决策方案可行的保障 约束条件是决策变量的线性函数约束条件是决策变量的线性函数 目标函数目标函数 衡量决策优劣的准则衡量决策优劣的准则，如时间最省如时间最省、利润最大利润最大、成本最低成本最低 目标函数是决策变量的线性函数目标函数是决策变量的线性函数 有的目标要实现极大有的目标要实现极大，有的则要求极小有的则要求极小 线性规划模型的建立线性规划模型的建立 11 三、线性规划的一般数学模型三、线性规划的一般数学模型 用一组非负决策变量表示的一个决策方案；用一组非负决策变量表示的一个决策方案；存在一组等式或不等式的线性约束条件；存在一组等式或不等式的线性约束条件；有一个希望达到的目标，可表示成决策变量的线性函数。有一个希望达到的目标，可表示成决策变量的线性函数。1 12211 11221121 1222221 12212max(min)Z(,)(,)s.t.(,),0nnnnnnmmmnnmnc xc xc xa xa xa xba xa xa xba xaxaxbx xx 线性规划模型的建立线性规划模型的建立 s.t.=subject to 通过上述实际问题的建模过程，可归纳得到建立线性规划模型的一般步骤：（1）根据决策要求，确定决策变量；（2）根据目标要求，确定目标函数；（3）根据各种数量限制关系，确定约束条件。建立线性规划模型的三个基本步骤建立线性规划模型的三个基本步骤 线性规划模型的建立线性规划模型的建立 (1)生产活动需要消耗一定的资源，以获得最大收益（如生产活动）通常资源Ai消耗量不超过Ai的资源总量bi,这类问题典型的模型是：11max(1,2,.,).0(1,2,.,)njjjnjjijjzc xa xbimstxjn几种典型的线性规划模型：几种典型的线性规划模型：（2）以成本最小完成某些任务（如采购活动、投资活动）第i种效益的值不低于最低可接受水平，这种问题的典型模型是：11min(1,2,.,).0(1,2,.,)njjjnjjijjzc xa xbimstxjn几种典型的线性规划模型：几种典型的线性规划模型：1111min,(1,2,).,(1,2,)0,()mnijijijmijjinijijijzjnstimijc xxbxax对对所所有有的的，（3）平衡问题，如运输问题 这类问题的典型模型是：几种典型的线性规划模型：几种典型的线性规划模型：销量约束销量约束 产量约束产量约束 例题例题4 （投资计划问题）某公司经调研分析知，在今后三（投资计划问题）某公司经调研分析知，在今后三年内有四种投资机会。第年内有四种投资机会。第种方案是在三年内每年年初投资种方案是在三年内每年年初投资，年底可获利，年底可获利15%，并可将本金收回；第，并可将本金收回；第种是在第一年的种是在第一年的年初投资，第二年的年底可获利年初投资，第二年的年底可获利45%，并将本金收回，但该，并将本金收回，但该项投资不得超过项投资不得超过2万元；第万元；第种是在第二年的年初投资，第种是在第二年的年初投资，第三年的年底可获利三年的年底可获利65%，并将本金收回，但该项投资不得超，并将本金收回，但该项投资不得超过过1.5万元；第万元；第种是在第三年的年初投资，年底收回本金种是在第三年的年初投资，年底收回本金，且可获利，且可获利35%，但该项投资不得超过，但该项投资不得超过1万元。现在本公司万元。现在本公司准备拿出准备拿出3万元来投资，问如何计划可使到第三年年未本利万元来投资，问如何计划可使到第三年年未本利和最大？和最大？一些复杂的线性规划问题建模一些复杂的线性规划问题建模 决策变量：设xij表示第i年对第j个方案的投资额 第一年x11 1.15x11 x12 1.45x12 第二年x21 1.15x21 x23 1.65x23 第三年x31 1.15x31 x34 1.35x34 解：问题分析解：问题分析。该问题的实际投资背景如下表所示：（1）确定决策变量：设xij表示第i年对第j个方案的投资额,i=1,2,3;j=1,2,3,4 年份 一 二 三 四 x11 1.15x11 x12 1.45x12 x21 1.15x21 x23 1.65x23 x31 1.15x31 x34 1.35x34 目标函数：第三年年未的本利和为 maxz=1.65x23+1.15x31+1.35x34（2）确定目标函数：第三年年未的本利和为 maxz=1.65x23+1.15x31+1.35x34 （3）确定约束条件：每一年的投资额应等于当年公司拥有的资金数：x11+x12=3 x21+x23=1.15x11 x31+x34=1.45x12+1.15x21 每个方案投资额的限制：x122 x231.5 非负约束：xij0,i=1,2,3;j=1,2,3,4 x341 例题例题5（木材库存问题）（木材库存问题）一个木材储运公司有很大的仓库用一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存量为后出售。已知该公司仓库的最大储存量为2000万米万米3，储存，储存费用为（费用为（70+100u）千元）千元/万米万米3，u为存储时间（季度数）。为存储时间（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示。已知每季度的买进卖出价及预计的销售量如下表所示。季度季度 买进价（万元买进价（万元/万米万米3）卖出价（万元卖出价（万元/万米万米3）预计销售量（万米预计销售量（万米3）冬冬 410 425 1000 春春 430 440 1400 夏夏 460 465 2000 秋秋 450 455 1600 由于木材不宜久贮，所有库存木材应于每年秋末售完。为由于木材不宜久贮，所有库存木材应于每年秋末售完。为使售后利润最大，试建立这个问题的线性规划模型。使售后利润最大，试建立这个问题的线性规划模型。设设yi分别表示冬、春、夏、秋四个季度采分别表示冬、春、夏、秋四个季度采购的木材数，购的木材数，xij代表第代表第i季度采购的用于第季度采购的用于第j季度销售的木材数。季度销售的木材数。冬季：冬季：x11,x12,x13,x14 春季：春季：x22,x23,x24 夏季：夏季：x33,x34 秋季秋季:x44 目标函数 111213141222324133343444max(425423438418410)(440448428430)(465438460)(455450)Zxxxxyxxxyxxyxy第一个季度约束 111112131411200001000yyxxxxx 第二个季度约束 121314222223241222200001400 xxxyyxxxxx解：解：设设yi分别表示冬、春、夏、秋四个季度采购的木材数，分别表示冬、春、夏、秋四个季度采购的木材数，xij代表第代表第i季度采购的用于第季度采购的用于第j季度销售的木材数。季度销售的木材数。1411121322232412333444341111213141111213142222324212221314232max(425423438418410)(440448428430)(465438460)(455450)200001000200001400 xyyxxxxxxyyxxxyyxxxxxyxxxyxxxxxxxx 4333343132333142434444414243444200002000200001600yxyxxxxxyxxxyxxxxx 季季度度 买进价（万买进价（万元元/万米万米3）卖出价（万卖出价（万元元/万米万米3）预计销售量预计销售量（万米（万米3）冬冬 410 425 1000 春春 430 440 1400 夏夏 460 465 2000 秋秋 450 455 1600 例题例题6（装载问题）（装载问题）有一艘货轮，分前、中、后三个舱位有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表，它们的容积与最大允许载重量如表1所示。现有三种货物所示。现有三种货物待运，已知有关数据列于表待运，已知有关数据列于表2。为了航运安全，要求前、中。为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不超过偏差不超过15%，前、后舱之间不超过，前、后舱之间不超过10%。问该货轮应。问该货轮应装载装载A，B，C各多少件，运费收入为最大？试建立这个问各多少件，运费收入为最大？试建立这个问题的线性规划模型。题的线性规划模型。前舱前舱 中舱中舱 后舱后舱 最大允许载重量（吨）最大允许载重量（吨）2000 3000 1500 容积（立方米）容积（立方米）4000 5400 1500 商品商品 数量（件）数量（件）每件体积（立方米每件体积（立方米/件）件）每件重量（吨每件重量（吨/件）件）运价（元运价（元/件）件）A 600 10 8 1000 B 1000 5 6 700 C 800 7 5 600 决策变量 设表示设表示xij装于第装于第j(j=1,2,3)舱位的第舱位的第i(i=1,2,3)种商品的数种商品的数量量 目标函数：运费收入最大 111213212223313233max1000()700()600()Zxxxxxxxxx舱位载重限制 112131122232132333865200086530008651500 xxxxxxxxx 舱位容积限制 112131122232132333105740001057540010571500 xxxxxxxxx 商品数量限制 1112132122233132336001000800 xxxxxxxxx 平衡限制：前舱与中舱之间比例关系 11213112223228652(10.15)(10.15)38653xxxxxx设表示设表示xij装于第装于第j(j=1,2,3)舱位的第舱位的第i(i=1,2,3)种商品的数量种商品的数量)10.01(34x5x6x8x5x6x8)10.01(34)15.01(21x5x6x8x5x6x8)15.01(21)15.01(32x5x6x8x5x6x8)15.01(32800 xxx1000 xxx600 xxx1500 x7x5x105400 x7x5x104000 x7x5x101500 x5x6x83000 x5x6x82000 x5x6x8)xxx(600)xxx(700)xxx(1000zmax332313312111322212332313322212312111333231232221131211332313322212312111332313322212312111333231232221131211舱位载重限制 舱位体积限制 商品数量限制 平衡条件 前舱前舱 中舱中舱 后舱后舱 重量重量 2000 3000 1500 容积容积 4000 5400 1500 商商品品 数量数量 体积体积 重重量量 运运价价 A 600 10 8 1000 B 1000 5 6 700 C 800 7 5 600 敬请指教！谢谢！