第三讲数学规划模型

第三讲数学规划模型第一页，共三十三页，编辑于2023年，星期四优化模型的简单分类

线性规划(LP)目标和约束均为线性函数

非线性规划(NLP)目标或约束中存在非线性函数

二次规划(QP)目标为二次函数、约束为线性

整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)一般整数规划，0-1（整数）规划连续优化离散优化数学规划第二页，共三十三页，编辑于2023年，星期四例1加工奶制品的生产计划获利24元/公斤1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利16元/公斤50桶牛奶时间480小时甲设备至多加工100公斤A1

制订生产计划，使每天获利最大每天：线性规划模型第三页，共三十三页，编辑于2023年，星期四1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天第四页，共三十三页，编辑于2023年，星期四模型求解

软件实现

LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2

VariableValueReducedCost

X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

20桶牛奶生产A1,30桶生产A2，利润3360元.第五页，共三十三页，编辑于2023年，星期四如何装运，使本次飞行获利最大？

三个货舱最大载重(t),最大容积(m3)

例2货机装运

重量（t）体积(m3/t）利润（元/t）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例.

前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡第六页，共三十三页，编辑于2023年，星期四WET=(10,16,8),VOL=(6800,8700,5300);w=(18,15,23,12),v=(480,650,580,390),p=(3100,3800,3500,2850).已知参数i=1,2,3,4（货物）j=1,2,3(分别代表前、中、后仓)货舱j的重量限制WETj体积限制VOLj第i种货物的重量wi，单位重量的体积vi，利润pi货机装运第七页，共三十三页，编辑于2023年，星期四决策变量

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

j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；所给出的数据都是精确的，没有误差.

模型建立第八页，共三十三页，编辑于2023年，星期四货舱容积

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

10；680016；87008；5300xij--第i种货物装入第j个货舱的重量第九页，共三十三页，编辑于2023年，星期四约束条件平衡要求

货物供应

货机装运模型建立10；680016；87008；5300xij--第i种货物装入第j个货舱的重量j,k=1,2,3;j≠k

第十页，共三十三页，编辑于2023年，星期四!定义集合及变量;sets:cang/1..3/:WET,VOL;wu/1..4/:w,v,p;link(wu,cang):x;endsets!对已知变量赋值;data:WET=10,16,8;VOL=6800,8700,5300;w=18,15,23,12;v=480,650,580,390;p=3100,3800,3500,2850;enddatamax=@sum(wu(i):p(i)*@sum(cang(j):x(i,j)));@for(wu(i):@sum(cang(j):x(i,j))<w(i));@for(cang(j):@sum(wu(i):x(i,j))<WET(j));@for(cang(j):@sum(wu(i):v(i)*x(i,j))<VOL(j));@for(cang(j):

@for(cang(k)|k#GT#j: !#GT#是大于等于的含义; @sum(wu(i):x(i,j)/WET(j))=@sum(wu(i):x(i,k)/WET(k))););END货机装运LINGO程序第十一页，共三十三页，编辑于2023年，星期四

Globaloptimalsolutionfound.Objectivevalue:121515.8Totalsolveriterations:12VariableValueReducedCostX(1,1)0.000000400.0000X(1,2)0.00000057.89474X(1,3)0.000000400.0000X(2,1)7.0000000.000000X(2,2)0.000000239.4737X(2,3)8.0000000.000000X(3,1)3.0000000.000000X(3,2)12.947370.000000X(3,3)0.0000000.000000X(4,1)0.000000650.0000X(4,2)3.0526320.000000X(4,3)0.000000650.0000货物2：前仓7,后仓8；

货物3:前仓3,中仓13；货物4:中仓3.货机装运模型求解最大利润约121516元第十二页，共三十三页，编辑于2023年，星期四如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例1汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.小型中型大型现有量钢材（t）1.535600劳动时间（h）28025040060000利润（万元）234制订月生产计划，使工厂的利润最大.4.3

汽车生产与原油采购第十三页，共三十三页，编辑于2023年，星期四IP可用LINGO直接求解整数规划(IntegerProgramming,简记IP)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.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000IP结果输出设每月生产小、中、大型汽车的数量分别为x1,x2,x3第十四页，共三十三页，编辑于2023年，星期四其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划若生产某类汽车，则至少生产80辆，求生产计划.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610第十五页，共三十三页，编辑于2023年，星期四LINGO中对0-1变量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1变量，化为整数规划

M为大的正数,本例可取1000ObjectiveValue:610.0000VariableValueReducedCost

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000若生产某类汽车，则至少生产80辆，求生产计划.x1=0或

80x2=0或

80x3=0或

80最优解同前

第十六页，共三十三页，编辑于2023年，星期四max=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);方法3：化为非线性规划

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

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

80x2=0或

80x3=0或

80最优解同前.一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.

第十七页，共三十三页，编辑于2023年，星期四汽车厂生产计划决策变量为整数,建立整数规划模型.求解整数规划和非线性规划比线性规划困难得多(即便用数学软件).当整数变量取值很大时,可作为连续变量处理,问题简化为线性规划.

对于类似于“x=0或

80”这样的条件，通常引入0-1变量处理，尽量不用非线性规划（特别是引入的整数变量个数较少时）.第十八页，共三十三页，编辑于2023年，星期四应如何安排原油的采购和加工

？

例2原油采购与加工市场上可买到不超过1500t的原油A：购买量不超过500t时的单价为10000元/t；购买量超过500t但不超过1000t时，超过500t的部分8000元/t；购买量超过1000t时，超过1000t的部分6000元/t.售价4800元/t售价5600元/t库存500t库存1000t汽油甲(A50%)原油A原油B汽油乙(A60%)第十九页，共三十三页，编辑于2023年，星期四决策变量

目标函数问题分析利润：销售汽油的收入购买原油A的支出.难点：原油A的购价与购买量的关系较复杂.甲(A50%)AB乙(A60%)购买xx11x12x21x224.8千元/t5.6千元/t原油A的购买量,原油A,B生产汽油甲,乙的数量c(x)~购买原油A的支出利润(千元)c(x)如何表述？第二十页，共三十三页，编辑于2023年，星期四原油供应

约束条件x

500t单价为10千元/t；500tx1000t，超过500t的8千元/t；1000tx1500t，超过1000t的6千元/t.目标函数购买xABx11x12x21x22库存500t库存1000t第二十一页，共三十三页，编辑于2023年，星期四目标函数中c(x)不是线性函数，是非线性规划；对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；想办法将模型化简，用现成的软件求解.

汽油含原油A的比例限制约束条件甲(A50%)AB乙(A60%)x11x12x21x22第二十二页，共三十三页，编辑于2023年，星期四x1,x2,x3~以价格10,8,6(千元/t)采购A的吨数目标函数

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

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

500t

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

类似地有第二十三页，共三十三页，编辑于2023年，星期四方法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;end

Localoptimalsolutionfound.Objectivevalue:4800.000Totalsolveriterations:14VariableValueReducedCostX11500.00000.000000X21500.00000.000000X120.0000000.2666667X220.0000000.000000X10.0000000.4000000X20.0000000.000000X30.0000000.000000X0.0000000.000000LINGO得到的是局部最优解,还能得到更好的解吗？

用库存的500t原油A、500t原油B生产汽油甲，不购买新的原油A，利润为4800千元.

第二十四页，共三十三页，编辑于2023年，星期四方法1：LINGO求解计算全局最优解：选LINGO|Options菜单；在弹出的选项卡中选择“GeneralSolver”；然后找到选项“UseGlobalSolver”将其选中；应用或保存；重新求解。

Globaloptimalsolutionfound.Objectivevalue:5000.000Extendedsolversteps:1Totalsolveriterations:43VariableValueReducedCost

X110.0000000.000000X210.0000000.900000X121500.0000.000000X221000.0000.000000X1500.00000.000000X2500.00000.000000X30.0000000.000000X1000.0000.000000

还有其他建模和求解方法吗？

购买1000t原油A，与库存的500t原油A和1000t原油B一起，共生产2500t汽油乙，利润为5000千元

.

第二十五页，共三十三页，编辑于2023年，星期四y1,y2,y3=1~以价格10,8,6(千元/t)采购A增加约束方法2

0-1线性规划模型,可用LINGO求解.y1,y2,y3=0或1购买1000t原油A，与库存的500t原油A和1000t原油B一起，生产汽油乙，利润为5000千元.x1,x2,x3~以价格10,8,6(千元/t)采购A的吨数y=0x=0x>0y=1与方法1（全局最优解）的结果相同引入0-1变量模型求解第二十六页，共三十三页，编辑于2023年，星期四b1b2

b3

b4方法3

b1

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

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)第二十七页，共三十三页，编辑于2023年，星期四IP模型，LINGO求解，得到的结果与方法2相同.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)x1200090005000O50010001500b1b2

b3

b4对于k=1,2,3第二十八页，共三十三页，编辑于2023年，星期四

方法3:直接处理分段线性函数，方法更具一般性.

分段函数无法直接用非线性