数学规划模型课件

第四章数学规划模型

y4.2自来水输送与货机装运（运输问题）4.3汽车生产与原油采购(整数规划)第四章数学规划模型y4.2自来水输送与货机装运（运4.2自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。4.2自来水输送与货机装运生产、生活物资从若干供应点运送其他费用:450元/千吨

应如何分配水库供水量，公司才能获利最多？

若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨

支出A：50B：60C：50甲：30；+50乙：70；+70丙：10；+20丁：10；+40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）其他费用:450元/千吨应如何分配水库供水量，公司才能获总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；+50乙：70；+70丙：10；+20丁：10；+40<总需求量：120+180=300总收入900160=144,000(元)与送水方案无关！

收入：900元/千吨

其他费用:450元/千吨

支出引水管理费+其他费用450160=72,000(元)与送水方案无关！

使引水管理费最小总供水量：160确定送水方案使利润最大问题分析A：50B：6供应限制约束条件需求限制

线性规划模型(LP)目标函数

水库i向j区的日供水量为xij（x34=0）决策变量

模型建立确定3个水库向4个小区的供水量供应限制约束条件需求限制线性规划模型(LP)目标函数水库模型求解

Globaloptimalsolutionfound.Objectivevalue:24400.00Totalsolveriterations:8VariableValueReducedCostX110.00000030.00000X1250.000000.000000X130.00000050.00000X140.00000020.00000X210.00000010.00000X2250.000000.000000X230.00000020.00000

X2410.000000.000000

X3140.000000.000000X320.00000010.00000

X3310.000000.000000利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费24400(元)模型求解Globaloptimalsolutionf目标函数

总供水量(320)>总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其它费用(450)

–引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论

确定送水方案使利润最大需求约束可以不变目标函数总供水量(320)>总需求量(300)每个水库求解这类问题一般称为“运输问题”(TransportationProblem)总利润88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030

Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000

X2130.000000.000000X2240.000000.000000

X230.00000010.00000X2450.000000.000000

X3150.000000.000000X320.00000020.00000

X3330.000000.000000求解这类问题一般称为“运输问题”总利润88700（元）A如何装运，使本次飞行获利最大？

三个货舱最大载重(吨),最大容积(米3)

例2货机装运

重量（吨）空间(米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例

前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡如何装运，使本次飞行获利最大？三个货舱最大载重(吨),最决策变量

xij--第i种货物装入第j个货舱的重量(吨）i=1,2,3,4,

j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；模型建立决策变量xij--第i种货物装入第j个货舱的重量(吨）货舱容积

目标函数(利润)约束条件货机装运模型建立货舱重量

10；680016；87008；5300xij--第i种货物装入第j个货舱的重量货舱容积目标函数(利润)约束条件货机装运模型建立货舱重量约束条件平衡要求

货物供应

货机装运模型建立10；680016；87008；5300xij--第i种货物装入第j个货舱的重量约束条件平衡要求货物供应货机装运模型建立10；6800

Globaloptimalsolutionfound.Objectivevalue:121515.8VariableValueReducedCostX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000

X32

12.9473690.000000X33

3.0000000.000000X410.000000650.000000

X423.0526320.000000X430.000000650.000000货物2：前仓10,后仓5；

货物3:中仓13,后仓3；货物4:中仓3。货机装运模型求解最大利润约121516元货物~供应点货舱~需求点平衡要求运输问题运输问题的扩展Globaloptimalsolutionfou数学规划模型课件其他费用:450元/千吨

应如何分配水库供水量，公司才能获利最多？

若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨

支出A：50B：60C：50甲：30；+50乙：70；+70丙：10；+20丁：10；+40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）其他费用:450元/千吨应如何分配水库供水量，公司才能获总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；+50乙：70；+70丙：10；+20丁：10；+40<总需求量：120+180=300总收入900160=144,000(元)与送水方案无关！

收入：900元/千吨

其他费用:450元/千吨

支出引水管理费+其他费用450160=72,000(元)与送水方案无关！

使引水管理费最小总供水量：160确定送水方案使利润最大问题分析A：50B：6供应限制约束条件需求限制

线性规划模型(LP)目标函数

水库i向j区的日供水量为xij（x34=0）决策变量

模型建立确定3个水库向4个小区的供水量供应限制约束条件需求限制线性规划模型(LP)目标函数水库模型求解

Globaloptimalsolutionfound.Objectivevalue:24400.00Totalsolveriterations:8VariableValueReducedCostX110.00000030.00000X1250.000000.000000X130.00000050.00000X140.00000020.00000X210.00000010.00000X2250.000000.000000X230.00000020.00000

X2410.000000.000000

X3140.000000.000000X320.00000010.00000

X3310.000000.000000利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费24400(元)模型求解Globaloptimalsolutionf目标函数

总供水量(320)>总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其它费用(450)

–引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论

确定送水方案使利润最大需求约束可以不变目标函数总供水量(320)>总需求量(300)每个水库求解这类问题一般称为“运输问题”(TransportationProblem)总利润88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030

Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000

X2130.000000.000000X2240.000000.000000

X230.00000010.00000X2450.000000.000000

X3150.000000.000000X320.00000020.00000

X3330.000000.000000求解这类问题一般称为“运输问题”总利润88700（元）A如何装运，使本次飞行获利最大？

三个货舱最大载重(吨),最大容积(米3)

例2货机装运

重量（吨）空间(米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例

前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡如何装运，使本次飞行获利最大？三个货舱最大载重(吨),最决策变量

xij--第i种货物装入第j个货舱的重量(吨）i=1,2,3,4,

j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；模型建立决策变量xij--第i种货物装入第j个货舱的重量(吨）货舱容积

目标函数(利润)约束条件货机装运模型建立货舱重量

10；680016；87008；5300xij--第i种货物装入第j个货舱的重量货舱容积目标函数(利润)约束条件货机装运模型建立货舱重量约束条件平衡要求

货物供应

货机装运模型建立10；680016；87008；5300xij--第i种货物装入第j个货舱的重量约束条件平衡要求货物供应货机装运模型建立10；6800

Globaloptimalsolutionfound.Objectivevalue:121515.8VariableValueReducedCostX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000

X32

12.9473690.000000X33

3.0000000.000000X410.000000650.000000

X423.0526320.000000X430.000000650.000000货物2：前仓10,后仓5；

货物3:中仓13,后仓3；货物4:中仓3。货机装运模型求解最大利润约121516元货物~供应点货舱~需求点平衡要求运输问题运输问题的扩展Globaloptimalsolutionfou4.3汽车生产与原油采购整数规划4.3汽车生产与原油采购整数规划设每月生产小、中、大型汽车的数量分别为x1,x2,x3例1汽车厂生产计划模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)设每月生产小、中、大型汽车的数量分别为x1,x2,x3例模型求解

3）

模型中增加条件：x1,x2,x3

均为整数，重新求解。

Globaloptimalsolutionfound.Objectivevalue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237

RowSlackorSurplusDualPrice[ST1]0.0000000.731183[ST2]0.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。可能找不到最优！但必须检验它们是否满足约束条件。可能不是可行解！模型求解3）模型中增加条件：x1,x2,x3均为IP可用LINDO直接求解整数规划(IntegerProgramming,简记IP)“@gin(x1);”表示“x1为整数”.

IP的最优解x1=64，x2=168，x3=0，最优值z=632max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);Globaloptimalsolutionfound.Objectivevalue:632.0000VariableValueReducedCostX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP结果输出IP可用LINDO直接求解整数规划(IntegerProg其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划若生产某类汽车，则至少生产80辆，求生产计划。x1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整方法2：引入0-1变量，化为整数规划

M为大的正数，可取1000若生产某类汽车，则至少生产80辆，求生产计划。x1=0或

80x2=0或

80x3=0或

80方法2：引入0-1变量，化为整数规划M为大的正数，可取10max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<=600;280*x1+250*x2+400*x3<=60000;x1<=1000*y1;x1>=80*y1;x2<=1000*y2;x2>=80*y2;x3<=1000*y3;x3>=80*y3;@gin(x1);@gin(x2);@gin(x3);@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1变量，化为整数规划

Globaloptimalsolutionfound.Objectivevalue:610.0000Extendedsolversteps:0Totalsolveriterations:10VariableValueReducedCostX180.00000-2.000000X2150.0000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000若生产某类汽车，则至少生产80辆，求生产计划。最优解同前

max=2*x1+3*x2+4*x3;方法2：引入0-1变量NLP虽然可用现成的数学软件求解(如LINGO,MATLAB)，但是其结果常依赖于初值的选择。方法3：化为非线性规划

非线性规划（Non-LinearProgramming，简记NLP）

实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。

若生产某类汽车，则至少生产80辆，求生产计划。x1=0或

80x2=0或

80x3=0或

80NLP虽然可用现成的数学软件求解(如LINGO,MATLAmax=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<=600;280*x1+250*x2+400*x3<=60000;x1*(x1-80)>=0;x2*(x2-80)>=0;x3*(x3-80)>=0;@gin(x1);@gin(x2);@gin(x3);Globaloptimalsolutionfound.Objectivevalue:610.0000Extendedsolversteps:2Totalsolveriterations:171VariableValueX180.00000X2150.0000X30.000000max=2*x1+3*x2+4*x3;Globalopt应如何安排原油的采购和加工

？

例2原油采购与加工市场上可买到不超过1500吨的原油A：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨但不超过1000吨时，超过500吨的部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨。售价4800元/吨售价5600元/吨库存500吨库存1000吨汽油甲(A50%)原油A原油B汽油乙(A60%)应如何安排原油的采购和加工？例2原油采购与加工决策变量

目标函数问题分析利润：销售汽油的收入-购买原油A的支出难点：原油A的购价与购买量的关系较复杂甲(A50%)AB乙(A60%)购买xx11x12x21x224.8千元/吨5.6千元/吨原油A的购买量,原油A,B生产汽油甲,乙的数量c(x)~购买原油A的支出利润(千元)c(x)如何表述？决策变量目标函数问题分析利润：销售汽油的收入-购买原油供应

约束条件x

500吨单价为10千元/吨；500吨x1000吨，超过500吨的8千元/吨；1000吨x1500吨，超过1000吨的6千元/吨。目标函数购买xABx11x12x21x22库存500吨库存1000吨原油供应约束条件x500吨单价为10千元/吨；目标函目标函数中c(x)不是线性函数，是非线性规划；对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；想办法将模型化简，用现成的软件求解。

汽油含原油A的比例限制约束条件甲(A50%)AB乙(A60%)x11x12x21x22目标函数中c(x)不是线性函数，是非线性规划；汽油含原油Ax1,x2,x3~以价格10,8,6(千元/吨)采购A的吨数目标函数

只有当以10千元/吨的价格购买x1=500(吨)时，才能以8千元/吨的价格购买x2方法1

非线性规划模型，可以用LINGO求解模型求解x=x1+x2+x3,c(x)=10x1+8x2+6x3

500吨

x1000吨，超过500吨的8千元/吨增加约束x=x1+x2+x3,c(x)=10x1+8x2+6x3

x1,x2,x3~以价格10,8,6(千元/吨方法1：LINGO求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12<x+500;x21+x22<1000;x11-x21>0;2*x12-3*x22>0;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1<500;x2<500;x3<500;x>0;x11>0;x12>0;x21>0;x22>0;x1>0;x2>0;x3>0;endObjectivevalue:4800.000VariableValueReducedCostX11500.00000.0000000E+00X21500.00000.0000000E+00X120.0000000E+000.0000000E+00X220.0000000E+000.0000000E+00X10.1021405E-1310.00000X20.0000000E+008.000000X30.0000000E+006.000000X0.0000000E+000.0000000E+00LINGO得到的是局部最优解，还能得到更好的解吗？

用库存的500吨原油A、500吨原油B生产汽油甲，不购买新的原油A，利润为4,800千元。

方法1：LINGO求解Model:Objectivevaly1,y2,y3=1~以价格10,8,6(千元/吨)采购A增加约束方法2

0-1线性规划模型，可用LINGO求解y1,y2,y3=0或1Objectivevalue:5000.000VariableValueReducedCostY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X1000.0000000.000000购买1000吨原油A，与库存的500吨原油A和1000吨原油B一起，生产汽油乙，利润为5,000千元。x1,x2,x3~以价格10,8,6(千元/吨)采购A的吨数y=0x=0x>0y=1优于方法1的结果y1,y2,y3=1~以价格10,8,6(千元/b1b2

b3

b4方法3

b1

xb2，x=z1b1+z2b2，z1+z2=1，z1,z20,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2

xb3，x=z2b2+z3b3，z2+z3=1，z2,z3

0,c(x)=z2c(b2)+z3c(b3).b3

xb4，x=z3b3+z4b4，z3+z4=1，z3,z4

0,c(x)=z3c(b3)+z4c(b4).直接处理处理分段线性函数c(x)b1b2b3IP模型，LINGO求解，得到的结果与方法2相同.处理分段线性函数，方法3更具一般性bkxbk+1yk=1,否则,yk=0方法3

bkxbk+1,x=zkbk+zk+1bk+1zk+zk+1=1，zk,zk+10,c(x)=zkc(bk)+zk+1c(bk+1).c(x)x1200090005000050010001500b1b2

b3

b4对于k=1,2,3IP模型，LINGO求解，得到的结果与方法2相同.处理分段线示性函数的使用已知mxM,z=0or1,那么若x>0,则z=1若z=0,则x=0xMz若x=0,则z=0若z=1,则x>0xmz条件约束if,then若x1+x2>3,则x3+x46x3+x46z,x1+x2-3Mz若x1+x2=3,则x3+x46x3+x46(1-z),x1+x2-3mz逻辑运算or,andx13或x23x13z1,x23z2,z1+z21分段线性目标函数如例2原油采购与加工

示性函数的使用已知mxM,z=0or1,那么数学规划模型课件第四章数学规划模型

y4.2自来水输送与货机装运（运输问题）4.3汽车生产与原油采购(整数规划)第四章数学规划模型y4.2自来水输送与货机装运（运4.2自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。4.2自来水输送与货机装运生产、生活物资从若干供应点运送其他费用:450元/千吨

应如何分配水库供水量，公司才能获利最多？

若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨

支出A：50B：60C：50甲：30；+50乙：70；+70丙：10；+20丁：10；+40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）其他费用:450元/千吨应如何分配水库供水量，公司才能获总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；+50乙：70；+70丙：10；+20丁：10；+40<总需求量：120+180=300总收入900160=144,000(元)与送水方案无关！

收入：900元/千吨

其他费用:450元/千吨

支出引水管理费+其他费用450160=72,000(元)与送水方案无关！

使引水管理费最小总供水量：160确定送水方案使利润最大问题分析A：50B：6供应限制约束条件需求限制

线性规划模型(LP)目标函数

水库i向j区的日供水量为xij（x34=0）决策变量

模型建立确定3个水库向4个小区的供水量供应限制约束条件需求限制线性规划模型(LP)目标函数水库模型求解

Globaloptimalsolutionfound.Objectivevalue:24400.00Totalsolveriterations:8VariableValueReducedCostX110.00000030.00000X1250.000000.000000X130.00000050.00000X140.00000020.00000X210.00000010.00000X2250.000000.000000X230.00000020.00000

X2410.000000.000000

X3140.000000.000000X320.00000010.00000

X3310.000000.000000利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费24400(元)模型求解Globaloptimalsolutionf目标函数

总供水量(320)>总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其它费用(450)

–引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论

确定送水方案使利润最大需求约束可以不变目标函数总供水量(320)>总需求量(300)每个水库求解这类问题一般称为“运输问题”(TransportationProblem)总利润88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030

Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000

X2130.000000.000000X2240.000000.000000

X230.00000010.00000X2450.000000.000000

X3150.000000.000000X320.00000020.00000

X3330.000000.000000求解这类问题一般称为“运输问题”总利润88700（元）A如何装运，使本次飞行获利最大？

三个货舱最大载重(吨),最大容积(米3)

例2货机装运

重量（吨）空间(米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例

前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡如何装运，使本次飞行获利最大？三个货舱最大载重(吨),最决策变量

xij--第i种货物装入第j个货舱的重量(吨）i=1,2,3,4,

j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；模型建立决策变量xij--第i种货物装入第j个货舱的重量(吨）货舱容积

目标函数(利润)约束条件货机装运模型建立货舱重量

10；680016；87008；5300xij--第i种货物装入第j个货舱的重量货舱容积目标函数(利润)约束条件货机装运模型建立货舱重量约束条件平衡要求

货物供应

货机装运模型建立10；680016；87008；5300xij--第i种货物装入第j个货舱的重量约束条件平衡要求货物供应货机装运模型建立10；6800

Globaloptimalsolutionfound.Objectivevalue:121515.8VariableValueReducedCostX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000

X32

12.9473690.000000X33

3.0000000.000000X410.000000650.000000

X423.0526320.000000X430.000000650.000000货物2：前仓10,后仓5；

货物3:中仓13,后仓3；货物4:中仓3。货机装运模型求解最大利润约121516元货物~供应点货舱~需求点平衡要求运输问题运输问题的扩展Globaloptimalsolutionfou数学规划模型课件其他费用:450元/千吨

应如何分配水库供水量，公司才能获利最多？

若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨

支出A：50B：60C：50甲：30；+50乙：70；+70丙：10；+20丁：10；+40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）其他费用:450元/千吨应如何分配水库供水量，公司才能获总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；+50乙：70；+70丙：10；+20丁：10；+40<总需求量：120+180=300总收入900160=144,000(元)与送水方案无关！

收入：900元/千吨

其他费用:450元/千吨

支出引水管理费+其他费用450160=72,000(元)与送水方案无关！

使引水管理费最小总供水量：160确定送水方案使利润最大问题分析A：50B：6供应限制约束条件需求限制

线性规划模型(LP)目标函数

水库i向j区的日供水量为xij（x34=0）决策变量

模型建立确定3个水库向4个小区的供水量供应限制约束条件需求限制线性规划模型(LP)目标函数水库模型求解

Globaloptimalsolutionfound.Objectivevalue:24400.00Totalsolveriterations:8VariableValueReducedCostX110.00000030.00000X1250.000000.000000X130.00000050.00000X140.00000020.00000X210.00000010.00000X2250.000000.000000X230.00000020.00000

X2410.000000.000000

X3140.000000.000000X320.00000010.00000

X3310.000000.000000利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费24400(元)模型求解Globaloptimalsolutionf目标函数

总供水量(320)>总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其它费用(450)

–引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论

确定送水方案使利润最大需求约束可以不变目标函数总供水量(320)>总需求量(300)每个水库求解这类问题一般称为“运输问题”(TransportationProblem)总利润88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030

Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000

X2130.000000.000000X2240.000000.000000

X230.00000010.00000X2450.000000.000000

X3150.000000.000000X320.00000020.00000

X3330.000000.000000求解这类问题一般称为“运输问题”总利润88700（元）A如何装运，使本次飞行获利最大？

三个货舱最大载重(吨),最大容积(米3)

例2货机装运

重量（吨）空间(米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例

前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡如何装运，使本次飞行获利最大？三个货舱最大载重(吨),最决策变量

xij--第i种货物装入第j个货舱的重量(吨）i=1,2,3,4,

j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；模型建立决策变量xij--第i种货物装入第j个货舱的重量(吨）货舱容积

目标函数(利润)约束条件货机装运模型建立货舱重量

10；680016；87008；5300xij--第i种货物装入第j个货舱的重量货舱容积目标函数(利润)约束条件货机装运模型建立货舱重量约束条件平衡要求

货物供应

货机装运模型建立10；680016；87008；5300xij--第i种货物装入第j个货舱的重量约束条件平衡要求货物供应货机装运模型建立10；6800

Globaloptimalsolutionfound.Objectivevalue:121515.8VariableValueReducedCostX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000

X32

12.9473690.000000X33

3.0000000.000000X410.000000650.000000

X423.0526320.000000X430.000000650.000000货物2：前仓10,后仓5；

货物3:中仓13,后仓3；货物4:中仓3。货机装运模型求解最大利润约121516元货物~供应点货舱~需求点平衡要求运输问题运输问题的扩展Globaloptimalsolutionfou4.3汽车生产与原油采购整数规划4.3汽车生产与原油采购整数规划设每月生产小、中、大型汽车的数量分别为x1,x2,x3例1汽车厂生产计划模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)设每月生产小、中、大型汽车的数量分别为x1,x2,x3例模型求解

3）

模型中增加条件：x1,x2,x3

均为整数，重新求解。

Globaloptimalsolutionfound.Objectivevalue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237

RowSlackorSurplusDualPrice[ST1]0.0000000.731183[ST2]0.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z