线性规划与编程

线性规划与编程第一页，共七十六页，编辑于2023年，星期一内容说明

以下内容在《数学建模与数学实验（第二版）》（汪晓银，周保平主编）第3章第二页，共七十六页，编辑于2023年，星期一2.1什么是数学规划2.2连续性线性规划2.3敏感性分析2.4整数线性规划2.50-1规划内容说明第三页，共七十六页，编辑于2023年，星期一

数学规划俗称最优化,首先是一种理念,其次才是一种方法,它所追求的是一种“至善”之道,一种追求卓越的精神.2.1什么是数学规划

小明同学，烧一壶水要8分钟，灌开水要1分钟，取牛奶和报纸要5分钟，整理书包要6分钟，为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？

第四页，共七十六页，编辑于2023年，星期一

十个人各提一只水桶，同时到水龙头前打水。设水龙头注满第一个人的桶需要1分钟，注满第二个人的桶需要2分钟，依此类推，注满第几个人的桶就需要几分钟，如果只有一只水龙头，适当安排这10个人的顺序，就可以使每个人所费的时间总和尽可能小，问这个总费时至少是几分钟？

2.1什么是数学规划第五页，共七十六页，编辑于2023年，星期一

数学规划(最优化)作为一门学科孕育于20世纪的30年代,诞生于第二次世界大战弥漫的硝烟中。

数学规划指在一系列客观或主观限制条件下，寻求合理分配有限资源使所关注的某个或多个指标达到最大（或最小）的数学理论和方法，是运筹学里一个十分重要的分支。2.1什么是数学规划第六页，共七十六页，编辑于2023年，星期一最优化问题的数学模型的一般形式为：（1）（2）三个要素：决策变量decisionbariable，目标函数objectivefunction，约束条件constraints。2.1什么是数学规划第七页，共七十六页，编辑于2023年，星期一

约束条件（2）所确定的x的范围称为可行域feasibleregion，满足（2）的解x称为可行解feasiblesolution，同时满足（1）（2）的解x称为最优解Optimalsolution，整个可行域上的最优解称为全局最优解globaloptimalsolution，可行域中某个领域上的最优解称为局部最优解localoptimalsolution。最优解所对应的目标函数值称为最优值optimum。2.1什么是数学规划第八页，共七十六页，编辑于2023年，星期一（一）按有无约束条件（2）可分为：1.无约束优化unconstrainedoptimization。2.约束优化constrainedoptimization。大部分实际问题都是约束优化问题。优化模型的分类2.1什么是数学规划第九页，共七十六页，编辑于2023年，星期一（二）按决策变量取值是否连续可分为：1.数学规划或连续优化。可继续划分为线性规划(LP)Linearprogramming和非线性规划(NLP)Nonlinearprogramming。在非线性规划中有一种规划叫做二次规划(QP)Quadraticprogramming，目标为二次函数，约束为线性函数。2.离散优化或组合优化。包含：整数规划(IP)Integerprogramming，整数规划中又包含很重要的一类规划：0-1（整数）规划Zero-oneprogramming，这类规划问题的决策变量只取0或者1。2.1什么是数学规划第十页，共七十六页，编辑于2023年，星期一（三）按目标的多少可分为：1.单目标规划。2.多目标规划。（四）按模型中参数和变量是否具有不确定性可分为：1.确定性规划。2.不确定性规划。（五）按问题求解的特性可分为：1.目标规划。2.动态规划。3.多层规划。4.网络优化。5.……等等。2.1什么是数学规划第十一页，共七十六页，编辑于2023年，星期一LINGO软件和MATLAB软件。对于LINGO软件，线性优化求解程序通常使用单纯形法simplexmethod，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点算法interiorpointmethod备选（LINGO中一般称为障碍法，即barrier），非线性优化求解程序采用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（LINGO中称multistart）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序—分解原问题成一系列的凸规划。求解优化问题常用的软件2.1什么是数学规划第十二页，共七十六页，编辑于2023年，星期一线性规划的一般形式：2.2连续性线性规划第十三页，共七十六页，编辑于2023年，星期一

一般线性规划问题都可以通过引入非负的松弛变量slackvariable与非负的剩余变量surplusv-ariable的方法化为标准形式（约束全是等约束）。

线性规划问题的可行域feasibleregion是一个凸集convexset（任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解Optimalsolution/point在凸多面体的某个顶点上达到求解方法：单纯形算法simplexmethod。2.2连续性线性规划第十四页，共七十六页，编辑于2023年，星期一1.比例性：每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。2.可加性：每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。3.连续性：每个决策变量的取值都是连续的。连续线性规划问题的性质要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件2.2连续性线性规划第十五页，共七十六页，编辑于2023年，星期一例1运输问题2.2连续性线性规划第十六页，共七十六页，编辑于2023年，星期一解设A1,A2调运到三个粮站的大米分别为x1，x2，

x3，

x4，

x5，

x6吨。题设量可总到下表：2.2连续性线性规划第十七页，共七十六页，编辑于2023年，星期一结合存量限制和需量限制得数学模型：2.2连续性线性规划第十八页，共七十六页，编辑于2023年，星期一程序编写1model:min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6;x1+x2+x3<4;x4+x5+x6<8;x1+x4>2;x2+x5>4;x3+x6>5;end提示：课件中的程序请先粘贴在记事本中再转帖于lingo软件中2.2连续性线性规划第十九页，共七十六页，编辑于2023年，星期一运行结果

Globaloptimalsolutionfound.Objectivevalue:160.0000Totalsolveriterations:0VariableValueReducedCostX12.0000000.000000X20.00000028.00000X32.0000000.000000X40.0000002.000000X54.0000000.000000X63.0000000.000000RowSlackorSurplusDualPrice1160.0000-1.00000020.00000016.0000031.0000000.00000040.000000-28.0000050.000000-12.0000060.000000-24.000002.2连续性线性规划第二十页，共七十六页，编辑于2023年，星期一84库存量x23x22x21A2542需要量x13x12x11A1B3B2B1粮库粮站距离及运量12122430824变量更换为：2.2连续性线性规划第二十一页，共七十六页，编辑于2023年，星期一模型:2.2连续性线性规划第二十二页，共七十六页，编辑于2023年，星期一程序编写MODEL:TITLE

调运大米的运输问题程序3;!定义集合段;SETS:LIANGKU/1..2/:A;!定义粮库的集合;LIANGZHAN/1..3/:B;!定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离;ENDSETSDATA:!粮库到粮站的距离;C=12248301224;2.2连续性线性规划第二十三页，共七十六页，编辑于2023年，星期一!粮库的限量;A=48;!粮站的限量;B=245;ENDDATA[OBJ]MIN=@SUM(YULIANG:C*X);!粮库上限的约束;@FOR(LIANGKU(I):[LK]

@SUM(LIANGZHAN(J):X(I,J))<A(I));!粮站下限的约束;@FOR(LIANGZHAN(J):[LZ]

@SUM(LIANGKU(I):X(I,J))>B(J));END

2.2连续性线性规划第二十四页，共七十六页，编辑于2023年，星期一程序的调试1.直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；2.可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；3.可以边写程序边运行，保证每行书写都是正确的程序；2.2连续性线性规划第二十五页，共七十六页，编辑于2023年，星期一例2

阶段生产问题

某公司生产某产品,最大生产能力为10000单位,每单位存储费2元,预定的销售量与单位成本如下:月份单位成本(元)销售量12347060007270008012000766000求一生产计划,使1)满足需求;2)不超过生产能力;3)成本(生产成本与存储费之和)最低.2.2连续性线性规划第二十六页，共七十六页，编辑于2023年，星期一

解假定1月初无库存,4月底买完,当月生产的不库存,库存量无限制.2.2连续性线性规划第二十七页，共七十六页，编辑于2023年，星期一model:title

生产计划程序1;Sets:yuefen/1..4/:c,x,e,d;endsetsdata:c=70718076;d=60007000120006000;e=2222;a=10000;enddatamin=@sum(yuefen:c*x)+

@sum(yuefen(j)|j#lt#4:

@sum(yuefen(i)|i#le#j:x-d)*e(j+1));@for(yuefen(j)|j#lt#4:

@sum(yuefen(i)|i#le#j:x)>@sum(yuefen(i)|i#le#j:d));@sum(yuefen:x)=@sum(yuefen:d);@for(yuefen:x<a);end

2.2连续性线性规划第二十八页，共七十六页，编辑于2023年，星期一2.2连续性线性规划第二十九页，共七十六页，编辑于2023年，星期一Model:Title

生产计划程序2;Sets:yuefen/1..4/:c,x,e,d,s;endsetsdata:c=70718076;d=60007000120006000;e=2222;a=10000;enddatamin=@sum(yuefen:c*x+e*s);@for(yuefen(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i));s(4)+x(4)-d(4)=0;s(1)=0;@for(yuefen:x<a);End2.2连续性线性规划第三十页，共七十六页，编辑于2023年，星期一月份单位成本(元)销售量123470600072700080120007660002.2连续性线性规划第三十一页，共七十六页，编辑于2023年，星期一76827676---80--7472-747270生产月10000100001000010000产量600041200070006000销量4321321需求月费用cij2.2连续性线性规划第三十二页，共七十六页，编辑于2023年，星期一建立模型如下：2.2连续性线性规划第三十三页，共七十六页，编辑于2023年，星期一model:title

生产计划程序3;sets:yuefen/1..4/:a,d,xx;!定义上三角矩阵;link(yuefen,yuefen)|&2#ge#&1:c,x;endsetsdata:c=70727476717375808276;d=60007000120006000;a=10000100001000010000;enddatamin=@sum(link:c*x);@for(yuefen(i):@sum(yuefen(j)|j#ge#i:x(i,j))<a(i););@for(yuefen(j):@sum(yuefen(i)|j#ge#i:x(i,j))>d(j););!得到每个月的生产量;@for(yuefen(i):xx=@sum(yuefen(j)|j#ge#i:x(i,j)));End2.2连续性线性规划第三十四页，共七十六页，编辑于2023年，星期一ModelTitle::生产计划程序1VariableValueReducedCostA10000.000.000000C(1)70.000000.000000C(2)71.000000.000000C(3)80.000000.000000C(4)76.000000.000000X(1)10000.000.000000X(2)10000.000.000000X(3)5000.0000.000000X(4)6000.0000.000000E(1)2.0000000.000000E(2)2.0000000.000000E(3)2.0000000.000000E(4)2.0000000.000000D(1)6000.0000.000000D(2)7000.0000.000000D(3)12000.000.000000D(4)6000.0000.000000

2.2连续性线性规划第三十五页，共七十六页，编辑于2023年，星期一

设有两个工厂A、B，产量都是10万个，工厂有三个仓库x，y，z，产品都先送到仓库。现有四个顾客分别为甲，乙，丙，丁，需求量分别为3，5，4，5万个。工厂到仓库、仓库到顾客的运费单价（元/个）见下表所示。试求总运费最少的运输方案以及总运费。AB甲乙丙丁x43571020y2196715z5220674课后训练第三十六页，共七十六页，编辑于2023年，星期一model:title

转运问题;sets:Plant/A,B/:produce;Warhouse/x,y,z/;Customer/1..4/:require;LinkI(Plant,Warhouse):cI,xI;LinkII(Warhouse,Customer):cII,xII;endsetsdata:produce=10,10;require=3,5,4,5;cI=4,2,5,3,1,2;cII=5,7,10,20,9,6,7,15,20,6,7,4;enddata课后练习第三十七页，共七十六页，编辑于2023年，星期一[OBJ]min=@sum(LinkI:cI*xI)+@sum(LinkII:cII*xII);!Thesupplyconstraints;@for(Plant(i):[SUP]

@sum(Warhouse(j):xI(i,j))<=produce(i));!运进仓库的量等于运出的量;@for(Warhouse(j):[MID]

@sum(Plant(i):xI(i,j))=@sum(Customer(k):xII(j,k)));!Thedemandconstraints;@for(Customer(k):[DEM]

@sum(Warhouse(j):xII(j,k))=require(k));课后练习第三十八页，共七十六页，编辑于2023年，星期一连续投资10万元A：从第1年到第4年每年初要投资，次年末回收本利1.15B：第3年初投资，到第5年末回收1.25，最大投资4万元C：第2年初投资，到第5年末回收1.40，最大投资3万元D：每年初投资，每年末回收1.11。求：5年末总资本最大。练习2连续投资课后练习第三十九页，共七十六页，编辑于2023年，星期一第1年第2年第3年第4年第5年Ax1Ax1Ax1Ax1ABx3BCx2CDx1Dx1Dx1Dx1Dx1D练习2解答变量设置课后练习第四十页，共七十六页，编辑于2023年，星期一模型建立

课后练习第四十一页，共七十六页，编辑于2023年，星期一程序编写model:title

投资问题;max=1.15*x4a+1.40*x2c+1.25*x3b+1.06*x5d;x1a+x1d=100000;x2a+x2c+x2d=1.06*x1d;x3a+x3b+x3d=1.15*x1a+1.06*x2d;x4a+x4d=1.15*x2a+1.06*x3d;x5d=1.15*x3a+1.06*x4d;x3b<=40000;x2c<=30000;课后练习第四十二页，共七十六页，编辑于2023年，星期一运行结果Globaloptimalsolutionfound.Objectivevalue:143750.0Totalsolveriterations:2ModelTitle:投资问题

VariableValueReducedCostX4A45000.000.000000X2C30000.000.000000X3B40000.000.000000X5D0.0000000.000000X1A71698.110.000000X1D28301.890.000000X2A0.0000000.000000X2D0.0000000.3036000E-01X3A0.0000000.000000X3D42452.830.000000X4D0.0000000.2640000E-01课后练习第四十三页，共七十六页，编辑于2023年，星期一

例3生产计划问题某工厂计划安排生产Ⅰ，Ⅱ两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：１）怎么安排生产使得工厂获利最大？２）产品Ⅰ的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？３）产品Ⅱ的单位利润增大到5万元，要不要改变生产计划？４）如果产品Ⅰ，Ⅱ的单位利润同时降低了1万元，要不要改变生产计划？产品Ⅰ产品Ⅱ最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润232.3敏感性分析第四十四页，共七十六页，编辑于2023年，星期一2.3敏感性分析第四十五页，共七十六页，编辑于2023年，星期一程序编写model:title

生产计划问题;[maxf]max=2*x1+3*x2;[TIME]x1+2*x2<8;[A]4*x1<16;[B]4*x2<12;END2.3敏感性分析第四十六页，共七十六页，编辑于2023年，星期一运行结果

ModelTitle:生产计划问题

VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPriceMAXF14.000001.000000A0.0000001.500000B0.0000000.1250000TIME4.0000000.000000

对问题1，安排是生产产品Ⅰ4单位，产品Ⅱ2单位，最大盈利为14万元。2.3敏感性分析第四十七页，共七十六页，编辑于2023年，星期一目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数f斜率的变化，但是只要f的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变.

2.3敏感性分析第四十八页，共七十六页，编辑于2023年，星期一要使用敏感性分析必须要在这里选择Prices&Ranges然后保存退出路径：LINGO︱Options︱GeneralSolver(通用求解程序)选项卡2.3敏感性分析第四十九页，共七十六页，编辑于2023年，星期一要调出敏感性分析的结果，必须先求解后再在程序窗口下点击LINGO｜Range，2.3敏感性分析第五十页，共七十六页，编辑于2023年，星期一Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRanges

CurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12.000000INFINITY0.5000000X23.0000001.0000003.000000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8.0000002.0000004.000000B16.0000016.000008.000000TIME12.00000INFINITY4.000000

当前变量系数允许增加量允许减少量对问题2，产品Ⅰ的单位利润降低到1.8万元，在（1.5，∞）之间，所以不改变生产计划。如果降低到1万元，不在（1.5，∞）内，要改变生产计划。在程序中将目标函数的系数“2”改为“1”，可得新的计划为安排是生产产品Ⅰ2单位，产品Ⅱ3单位，最大盈利为11万元.对问题3，要改变生产计划，更改程序得新计划为生产产品Ⅰ2单位，产品Ⅱ3单位，最大盈利为19万元.对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到8万元.

2.3敏感性分析第五十一页，共七十六页，编辑于2023年，星期一2.3敏感性分析第五十二页，共七十六页，编辑于2023年，星期一把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润.在最优情况下，y的值就是资源的影子价格，影子价格有意义是有范围的。影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量．2.3敏感性分析第五十三页，共七十六页，编辑于2023年，星期一Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12.000000INFINITY0.5000000X23.0000001.0000003.000000

RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8.0000002.0000004.000000B16.0000016.000008.000000TIME12.00000INFINITY4.000000

运行结果

ModelTitle:生产计划问题

VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPriceMAXF14.000001.000000A0.0000001.500000B0.0000000.1250000TIME4.0000000.000000

2.3敏感性分析第五十四页，共七十六页，编辑于2023年，星期一1桶牛奶3公斤A1

12小时8小时4公斤A2

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

制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?

可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：例4加工奶制品的生产计划2.3敏感性分析第五十五页，共七十六页，编辑于2023年，星期一x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

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

线性规划模型(LP)2.3敏感性分析第五十六页，共七十六页，编辑于2023年，星期一Max=72*x1+64*x2;x1+x2<50;12*x1+8*x2<480;3*x1<100;

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生产A1,30桶生产A2，利润3360元。2.3敏感性分析第五十七页，共七十六页，编辑于2023年，星期一OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.00000035元可买到1桶牛奶，要买吗？35<48,应该买！

聘用临时工人付出的工资最多每小时几元？2元！2.3敏感性分析第五十八页，共七十六页，编辑于2023年，星期一RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE

250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000A1获利增加到30元/千克，应否改变生产计划？不变！35元可买到1桶牛奶，每天最多买多少？最多买10桶！2.3敏感性分析第五十九页，共七十六页，编辑于2023年，星期一问题：如何下料最节省?原料钢管:每根19米4米50根6米20根8米15根客户需求例5下料问题2.4整数规划第六十页，共七十六页，编辑于2023年，星期一按照客户需要在一根原料钢管上安排切割的一种组合。

余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根2.4整数规划第六十一页，共七十六页，编辑于2023年，星期一

为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？模式

4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023xi~按第i种模式切割的原料钢管根数(i=1,2,…7)决策变量

2.4整数规划第六十二页，共七十六页，编辑于2023年，星期一2.所用原料钢管总根数最少1.原料钢管剩余总余量最小目标函数：（两种标准）2.4整数规划第六十三页，共七十六页，编辑于2023年，星期一模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015约束整数约束：xi为整数2.4整数规划第六十四页，共七十六页，编辑于2023年，星期一model:Title

钢管下料;

Min=3*x1+x2+3*x3+3*x4+x5+x6+3*x7;4*x1+3*x2+2*x3+x4+x5>50; x2+2*x4+x5+3*x6>20; x3+x5+2*x7>15;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7);end程序编写2.4整数规划第六十五页，共七十六页，编辑于2023年，星期一按模式2切割12根,按模式5切割15根，余料27米

最优解：x2=12,