运筹学-第1章素材.ppt

《运筹学-第1章素材.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学主讲人：朱建明2014年9月应用数学系第1章线性规划线性规划的数学模型及其标准型1线性规划问题的解和单纯形法2单纯形的基本理论（自学）3对偶问题和对偶单纯形法4灵敏度分析5第一节线性规划的数学模型及其标准型一、线性规划应用举例(LinerProgramming)例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？产品资源甲乙资源限制ABC120111300400250单位利润50100第一节线性

2、规划的数学模型及其标准型例1的线性规划模型：决策变量：x1、x2——分别代表甲、乙两种产品的生产数量目标函数：maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400不等式约束x2≤250x1，x2≥0非负约束一、线性规划应用举例第一节线性规划的数学模型及其标准型一、线性规划应用举例(LinerProgramming)例2（营养搭配问题）如果有甲、乙、丙、丁四种食品，单价各不相同，都含有不同成份的维生素，其含量和单价如下表所示：若要保证每人每天维生素的最低需要量，则应如何搭配各种食品，

3、使花的钱最少？维生素甲乙丙丁每人每天需要量一二三10000.617.515000.277.517500.68032500.3304000130单价0.80.50.91.5第一节线性规划的数学模型及其标准型一、线性规划应用举例例3靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。

4、两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小。第一节线性规划的数学模型及其标准型一、线性规划应用举例解：决策变量：x1、x2——分别代表工厂1和工厂2处理污水的数量(万m3)目标函数：minz=1000x1+800x2约束条件：第一段河流（工厂1——工厂2之间）：(2－x1)/500≤0.002第二段河流：[0.8(2－x1)+(1.4-x2)]/700≤0.002此外有：x1≤2x2≤1.4第一节

5、线性规划的数学模型及其标准型一、线性规划应用举例例2的线性规划模型：minz=1000x1+800x2s.t.x1≥10.8x1+x2≥1.6x1≤2x2≤1.4x1，x2≥0第一节线性规划的数学模型及其标准型线性规划的数学模型的一般形式：max(min)z=c1x1+c2x2+…+cnxn——目标函数a11x1+a12x2+…+a1nxn=(≥,≤)b1a21x1+a22x2+…+a2nxn=(≥,≤)b2——约束条件…………………………………am1x1+am2x2+…+amnxn=(≥,≤)bmx1，x2，…，

6、xn≥0模型特点：目标函数(Objectivefunction)与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。第一节线性规划的数学模型及其标准型二、线性规划的标准型LP标准型：maxz=c1x1+c2x2+…+cnxn——目标函数a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2——约束条件………………………am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥0特点：1.Z——max2.约束条件为等号3.变量非负4.右端常数项大于等于零

7、第一节线性规划的数学模型及其标准型二、线性规划的标准型LP标准型的矩阵形式：第一节线性规划的数学模型及其标准型三、化非标准型为标准型1、若minz=CTX此时可令：z=－f，则minzmax-f这样处理所得最优解不变举例：minz=－x1－x2s.t.2x1+x2=2－x1+x2=1x1，x2≥0、第一节线性规划的数学模型及其标准型三、化非标准型为标准型2、若约束条件为“≤”时，∑aijxj≤bi→∑aijxj+xn+i=bixn+i——松弛变量(slackvariable)3、若约束条件为“≥”时，∑aijxj≥

8、bi→∑aijxj－xn+i=bixn+i——剩余变量(surplusvariable）举例：maxz=x1+10x2s.t.x1+2x2≤100x1+x2≥50x1，x2≥0第一节线性规划的数学模型及其标准型三、化非标准型为标准型4、若xk为无限制，则令xk=x+k－x-k，其中x+k－x-k≥05、若bi<0，则－bi>0举例:化下列线性规划为标准型mi