第2章-线性规划模型

第1页运筹帷幄之中决胜千里之外线性规划LinearProgramming第一篇运筹学模型第2页第2章线性规划模型2.1拟订生产计划问题2.2运输问题2.3食谱问题2.4作物布局问题2.5配料问题2.6LP模型的一般形式与标准形式2.7LP模型的几何解释和图解法2.8一些实例第3页实例1某化工厂生产四种化工产品,每种产品生产1吨消耗的工时、能源和获得的利润如表2-1所示表2-1生产1t产品的消耗和收益1234,,,AAAA1852利润/万元0.10.50.30.2能耗/t标准煤75380250100工时/h产品1A2A3A4A第4页问题已知该厂明年的工时限额为18480h，能耗限额为100t标准煤，欲使该厂明年的总利润最高，请确定定各种产品的生产数量，试建立数学模型。第5页模型假设四种产品的每吨获利是与它们各自的生产数量无关的常数；每种产品生产一吨消耗的工时，能耗是与各种产品的产量无关的常数。四种产品每吨的获利是与它们相互间产量无关的常数。每种产品所消耗的工时，能耗是与它们相互间产量无关的常数。生产产品的数量可以是任意实数。第6页问题分析决策变量：四种产品明年的生产数量目标：该厂明年的总利润最大利润函数：约束条件：工时限制能耗限制蕴含约束：四种产品产量非负1234,,,xxxx1234258xxxx12341002503807518480xxxx12340.20.30.50.1100xxxx1234,,,0xxxx第7页模型建立123412341234max258..10025038075184800.20.30.50.11000,1,2,3,4izxxxxstxxxxxxxxxi由于目标函数是变量的线性函数，约束条件是的线性不等式，所以该问题为线性规划问题，简写为LP.z1234,,,xxxx1234,,,xxxx第8页线性规划问题的特征比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续第9页实例2一般的拟定生产计划问题例2设有m种资源：12,,mAAA，拟生产n种产品：12,,nBBB.用ija表示生产1个单位第j种产品所需要的第i种资源的数量，用表示第i种资源ib的使用限额，用表示销售一个单位的第j种产品jc获得的利润，用表示第j种产品的生产数量，则jx12(,,)Tnxxxx就代表一个生产计划，我们的问题是：要设法安排一个生产计划，使该厂获得的总利润最高。第10页问题分析决策变量:n种产品的生产数量目标：该厂获得的总利润最大利润函数：约束条件：资源的使用限额蕴含约束：n种产品产量非负12,,nxxx1nijijjcxiA第11页模型建立11max..,1,2,0,1,2,njjjnijjijjzcxstaxbimxjn当拟订的生产计划规模较大时,我们通常采用向量、矩阵记号，则该模型变成什么样了呢？max..,0.TzcxstAxbx第12页设有3个化肥厂：甲、乙、丙，供应3个地区:A,B,C化肥，各厂的化肥年产量、各地区需求量及各厂到3个地区的单位运价见表所示；假设各地区需求量没有满足会造成经济损失:B,C区的单位损失分别为3万元/万吨和2万元/万吨，A区的需求量必须保证，求使得总运费和经济损失费最少的调运方案。实例1化肥的供应与销售第13页ABC年产量（万吨）甲51710乙64680丙32515销量（万吨）752050销地运价产地万元/万吨第14页问题分析总产量为10+80+15=105，总销量为75+20+50=145因为总产量总销量，故该问题为产销不平衡的运输问题。目标函数：总运费与经济损失费之和决策变量：从产地运往销地的化肥量约束条件：必须保证A区的需求量，即A区无损失费；B,C有损失费；三个厂生产的化肥全部运出无剩余。第15页设从甲、乙、丙三个工厂向A,B,C三个地区运送的化肥量为总运费与经济损失费之和为.①三个工厂到三地的运费之和记为②销地A必须满足需要量，无损失费③销地B损失费为销地C损失费为,,1,2,3()ijxij万吨Z1111213212223313233(57)(646)(325)Zxxxxxxxxx1222323(20)xxx1323332(50)xxx1Z第16页模型建立111213212223313233min1605256433Zxxxxxxxxx311321331311321331108015..7520500,,1,2,3jjjjjjiiiiiiijxxxstxxxxij第17页实例2一般的运输问题假设某种物资有m个产地，n个销地.第i个产地的产量为；第个产地的需要量为.其中.由产地i到销地j的距离已知为，问应如何分配该种物资，使既能满足各地的需要，又使所花费的运输总吨公里数最少？,1,2,iaimj,1,2,jbjn11mnijijabijd什么是吨公里数呢？吨公里数=运载量*运载公里数第18页模型建立用表示产地i供给产地j的物资数量，设s为运输的总吨公里数，则上述问题的数学模型为ijx1111min..,1,2,,1,2,0,1,2,;1,2,.mnijijijnijjinijijijsdxstxbjnxaimximnn对运输问题感兴趣的同学可以查阅相关书籍，例如由前苏联数学家编写的《生产组织与计划中的数学方法》一书提出了这一类问题的数学模型和求解方法。第19页一般食谱问题假定有n种食品，每种食品中含有m种营养成分.其中：ijijjjabicjxj一个单位的第j种食品中含有第i种营养的数量每人每天对第种营养的最低需求第种食品的单价所用第种食品的数量问：应该怎样选配食品，才能保证在满足m种营养成分需要的条件下，使食品总成本y最低？第20页模型建立11min..,1,2,,0,1,2,,.njjjnijjijjycxstaxbimxjn第21页例红星农场要在n块土地上，种植m种作物，各块土地的面积、各种作物计划种植面积和在各块地上的每平方米产量如下表，问应如何合理安排种植计划，才能使总产量最高.这里假设计划播种的种面积等于土地的总面积，即§2.4作物布局问题12,nBBB12,,mAAA11mnijijab第22页计划播种面积/平方米土地面积/平方米111212122212nnmmmnccccccccc12nBBB12nbbb12mAAA12maaa土地每平产量/kg作物第23页问题分析决策量：各块土地种植某种作物的面积，且非负.目标：总产量最高约束：①各块土地上种植作物面积总和=作物计划种植面积；②第j块土地种植各种作物面积总和=土地面积③种植面积非负iAiAiajBjbiijjijjiaAbBcBA计划播种作物的面积土地的面积土地上种植作物的单位产量第24页模型建立1111max..,1,2,,1,2,0,1,2,;1,2,,mnijijijnijijmijjiijycxstxaimxbjnximjn这是等式约束第25页一般形式qjxqjxmpibxaxaxapibxaxaxatsxcxcxczjjininiiininiinn,...,2,1;,...,2,1;0,...,1;,...,2,1;..min221122112211无限制目标函数约束条件第26页注释njxj,...,2,1;为待定的决策变量，),,,(21ncccc为价值向量，njcj,...,2,1;为价值系数，),...,,(21mbbbb为右端向量，矩阵为系数矩阵。mnmmnnaaaaaaaaaA212222111211第27页规范形式0..minxbAxtsxc第28页标准形式0..minxbAxtsxc第29页概念可行解（或可行点）：满足所有约束条件的向量),,(21nxxxx可行集（或可行域）：所有的可行解的全体}0,{xbAxxD最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合DyycxcDxO,{}最优值：最优解的目标函数值Oxxcv,第30页模型转换约束转换实例令自由变量jjjxxx，其中jjxx,为非负变量求最大可以等价成求负的最小xcxcminmax目标转换变量转换第31页约束转换不等式变等式不等式变不等式ininiibxaxaxa2211ininiibxaxaxa2211ininiibxaxaxa2211等式变不等式第32页不等式变等式ininiibxaxaxa22110,2211iiininiisbsxaxaxa或ininiibxaxaxa22110,2211iiininiisbsxaxaxa松弛变量剩余变量第33页不等式变不等式ininiibxaxaxa2211ininiibxaxaxa2211或ininiibxaxaxa2211ininiibxaxaxa2211第34页例2.1.3把问题转化为标准形式052222..21max1212121xxxxxxxtsxxz7,6,5,4,3,1;05)(2)(22)(2..)(min743164315431431ixxxxxxxxxxxxxtsxxxzi第35页图解法对于只有两个变量的线性规划问题可以用图解法求解：变量用直角坐标系中的点表示约束条件用坐标系中的半空间或直线的交表示可行区域是一个凸多面体目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。第36页例解线性规划2221xx2221xx521xx最优解（1，4）052222..max121212121xxxxxxxtsxxz第37页当目标函数该边后，等值线的方向会发生改变，如果等值线与某个约束对应的函数直线平行，则该函数值线上的所有可行解都是最优解2221xx2221xx最优解（1，4）521xx第38页注释可能出现的情况：可行域是空集可行域无界无最优解最优解存在且唯一，则一定在顶点上达到最优解存在且不唯一，一定存在顶点是最优解第39页其他费用:450元/千吨•应如何分配水库供水量，公司才能获利最多？•若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）第40页总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40总需求量：120+180=300总收入900160=144,000(元)收入：900元/千吨其他费用:450元/千吨支出引水管理费其他支出450160=72,000(元)使引水管理费最小第41页供应限制约束条件需求限制线性规划模型(LP)5014131211xxxx50603332