线性、整数规划模型

优化建模与计算

参考书《优化建模与LINDO/LINGO软件》谢金星,薛毅编著,

清华大学出版社,2005年7月第1版./~jxie/lindo内容提要1.优化模型的基本概念2.优化问题的建模实例3.LINDO/LINGO软件简介1.优化模型的基本概念

最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:优化模型和算法的重要意义结构设计资源分配生产计划运输方案解决优化问题的手段

经验积累，主观判断

作试验，比优劣

建立数学模型，求解最优策略最优化:在一定条件下，寻求使目标最大(小)的决策

优化问题三要素：决策变量；目标函数；约束条件约束条件决策变量优化问题的一般形式

无约束优化(没有约束)与约束优化(有约束)

可行解（只满足约束）与最优解(取到最优值)目标函数局部最优解与整体最优解

局部最优解(LocalOptimalSolution,如x1)

整体最优解(GlobalOptimalSolution,如x2)x*f(x)x1x2o优化模型的简单分类

线性规划(LP)

目标和约束均为线性函数

非线性规划(NLP)

目标或约束中存在非线性函数

二次规划(QP)

目标为二次函数、约束为线性

整数规划(IP)

决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)

纯整数规划(PIP),混合整数规划(MIP)

一般整数规划，0-1（整数）规划连续优化离散优化数学规划优化模型的简单分类和求解难度优化线性规划非线性规划二次规划连续优化整数规划问题求解的难度增加

2.优化模型实例目标函数约束条件例2.1线性规划模型(LP)模型求解

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。求解LP的基本思想思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。LP的约束和目标函数均为线性函数2维可行域

线段组成的凸多边形目标函数等值线为直线最优解凸多边形的某个顶点n维超平面组成的凸多面体等值线是超平面凸多面体的某个顶点LP的通常解法是单纯形法(G.B.Dantzig,1947)线性规划模型的解的几种情况线性规划问题有可行解(Feasible)无可行解（Infeasible）有最优解（Optimal）无最优解(Unbounded)目标98x1+277x2

－x12

－0.3x1x2

－2x22约束x1+x2

≤100x1

≤2x2x1,x2

≥0二次规划模型(QP)若还要求

变量为整数，则是整数二次规划模型(IQP)二次规划模型(QP)-例1.2决策变量：cij，(xj,yj)~16维非线性规划模型(NLP)非线性规划模型(NLP)－例1.3：整数规划问题一般形式

整数线性规划(ILP)

目标和约束均为线性函数整数非线性规划(NLP)

目标或约束中存在非线性函数整数规划问题的分类

纯(全)整数规划(PIP)

决策变量均为整数混合整数规划(MIP)

决策变量有整数，也有实数0-1规划决策变量只取0或1取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入非最优解基本思想：隐式地枚举一切可行解（“分而治之”）所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）.这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.分枝定界法（B&B:BranchandBound）整数线性规划的分枝定界算法无约束优化更多的优化问题线性规划非线性规划网络优化组合优化整数规划不确定规划多目标规划目标规划动态规划连续优化离散优化从其他角度分类

应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等实际问题规模往往较大，用软件求解比较方便3.LINDO/LINGO软件简介常用优化软件1.LINDO/LINGO软件2.MATLAB优化工具箱/Mathematic的优化功能3.SAS(统计分析)软件的优化功能4.EXCEL软件的优化功能5.其他（如CPLEX等）MATLAB优化工具箱能求解的优化模型优化工具箱3.0(MATLAB7.0R14)连续优化离散优化无约束优化非线性极小fminunc非光滑(不可微)优化fminsearch非线性方程(组)fzerofsolve全局优化暂缺非线性最小二乘lsqnonlinlsqcurvefit线性规划linprog纯0-1规划bintprog一般IP(暂缺)非线性规划fminconfminimaxfgoalattainfseminf上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性最小二乘lsqnonneglsqlin约束优化二次规划quadprogLINDO公司软件产品简要介绍

美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：

LINDO:

LinearINteractiveandDiscreteOptimizer(V6.1)LINDOAPI:LINDOApplicationProgrammingInterface(V4.1)LINGO:LinearINteractiveGeneralOptimizer(V10.0)What’sBest!:(SpreadSheete.g.EXCEL)(V8.0)演示(试用)版、高级版、超级版、工业版、扩展版…（求解问题规模和选件不同）LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解等。LINGO软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。

LINGO可以求解:线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等。LINDO/LINGO软件能求解的模型优化线性规划非线性规划二次规划连续优化整数规划LINDOLINGO建模时需要注意的几个基本问题

1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y<5改为x<5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)需要掌握的几个重要方面LINGO：

正确阅读求解报告；掌握集合(SETS)的应用； 正确理解求解状态窗口； 学会设置基本的求解选项(OPTIONS)； 掌握与外部文件的基本接口方法§1.2

了解LINGO的菜单新建打开保存打印剪切复制粘贴取消重做查找定位匹配括号求解显示答案模型图示选项设置窗口后置关闭所有窗口平铺窗口在线帮助上下文相关帮助文件菜单编辑菜单LINGO菜单窗口菜单帮助菜单[变量][约束][非零系数][内存使用量][已运行时间][求解器状态][扩展求解器状态]例1加工奶制品的生产计划1桶牛奶

3kgA1

12h

8h

4kgA2

或获利24元/kg获利16元/kg50桶牛奶时间480h至多加工100kgA1

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

可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/kg，应否改变生产计划？每天：问题1桶牛奶3kgA1

12h8h4kgA2

或获利24元/kg获利16元/kgx1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

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

线性规划模型(LP)时间480h至多加工100kgA1

50桶牛奶每天基本模型模型求解

软件实现

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元.LINGO的语法规定：（1）求目标函数的最大值或最小值分别用MAX=…或MIN=…来表示；（2）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；（3）变量名称必须以字母(A~Z)开头，由字母、数字(0~9)和下划线所组成，长度不超过32个字符，不区分大小写；（4）可以给语句加上标号，例如[OBJ]MAX=200*X1+300*X2；LINGO的语法规定：（5）以惊叹号“！”开头，以分号“；”结束的语句是注释语句;（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；（7）乘号“*”必须输入，不能省略。（8）LINGO模型以语句“MODEL：”开头，以“END”结束，对于比较简单的模型，这两个语句可以省略。模型求解

软件实现

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元.模型求解

reducedcost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量结果解释

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000

MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

model:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end三种资源“资源”剩余为零的约束为紧约束（有效约束）原料无剩余时间无剩余加工能力剩余40结果解释

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最优解下“资源”增加1单位时“效益”的增量影子价格35元可买到1桶牛奶，要买吗?35<48,应该买！

聘用临时工人付出的工资最多每小时几元?2元！原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润该命令产生当前模型的灵敏度分析报告（需要通过Lingo菜单设置激活）(1)最优解保持不变的情况下,目标函数的系数变化范围;(2)在影子价格和缩减成本系数都不变的前提下,约束条件右边的常数变化范围;敏感性分析(“LINGO|Ranges”)注意：灵敏性分析耗费相当多的求解时间，因此当速度很关键时,就没有必要激活它Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000

最优解不变时目标函数系数允许变化范围敏感性分析

(“LINGO|Ranges”)

x1系数范围(64,96)

x2系数范围(48,72)

A1获利增加到30元/kg，应否改变生产计划?x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶,每天最多买多少?最多买10桶!(目标函数不变)充分条件!奶制品的生产与销售

由于产品利润、加工时间等均为常数，可建立线性规划模型.

线性规划模型的三要素：决策变量、目标函数、约束条件.

用LINGO求解，输出丰富，利用影子价格和灵敏性分析可对结果做进一步研究.

建模时尽可能利用原始的数据信息，把尽量多的计算留给计算机去做.主要内容整数规划方法432023年5月18日整数规划的一般模型；整数规划解的求解方法；整数规划的软件求解方法；

0-1规划的模型与求解方法；整数规划的应用案例分析。

如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.

小型中型大型现有量钢材（t）1.535600劳动时间（h）28025040060000利润（万元）234

制订月生产计划，使工厂的利润最大.引例汽车生产计划设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)模型求解

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

均为整数，重新求解.

ObjectiveValue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大.2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解.

但必须检验它们是否满足约束条件.为什么？IP可用LINGO直接求解整数规划(IntegerProgramming,简记IP)IP的最优解x1=64，x2=168，x3=0，最优值z=632

Globaloptimalsolutionfound.

Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000模型求解

IP结果输出IP模型LINGO求解Model：max=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);end其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划

若生产某类汽车，则至少生产80辆，求生产计划.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610LINGO中对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最优解同前

IP模型LINGO求解Model：max=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;%取M=1000x2<1000*y2;x2>80*y2;x2<1000*y2;x2>80*y2;@gin(x1);@gin(x2);@gin(x3);%整数约束@bin(y1);@bin(y2);@bin(y3);%0-1变量endmax=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最优解同前.一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.532023年5月18日2.整数规划模型的一般形式

一、整数规划的一般模型问题是如何求解整数规划问题呢？能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？实际上，可借鉴这种思想来解决整数规划问题．整数规划模型示例542023年5月18日固定资源分配问题问题分析与准备

固定资源分配问题资源B1…Bj…Bm车间A1利润：r11……………Ai……rij………An…………rnm价格a1…aj…am总量X1…Xj…Xm

目标总利润各车间、各资源利润资源分配量决策变量562023年5月18日

固定资源分配问题

3、整数规划的LINGO解法二、整数规划的求解方法572023年5月18日582023年5月18日

1、0-1整数规划的模型三、0-1整数规划592023年5月18日

2、指派（或分配）问题三、0-1整数规划

在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。例如：某部门有n项任务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。2.指派（或分配）问题602023年5月18日

现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如右表：问如何分配何人去完成何项目使完成4项任务所需总时间最少？612023年5月18日2.指派（或分配）问题622023年5月18日2.指派（或分配）问题632023年5月18日2.指派（或分配）问题642023年5月18日2.指派（或分配）问题指派问题的一般模型：652023年5月18日2.指派（或分配）问题指派问题的一般模型：662023年5月18日

匈牙利算法的基本思想

因为每个指派问题都有一个相应的效益矩阵，通过初等变换修改效益矩阵的行或列，使得在每一行或列中至少有一个零元素，直到在不同行不同列中都至少有一个零元素为止。从而得到与这些零元素相对应的一个完全分配方案，这个方案对原问题而言是一个最优的分配方案。3.指派问题的匈牙利算法672023年5月18日

用LINGO求解0-1规划模型4、0-1规划的LINGO解法如何选拔队员组成4100m混合泳接力队?例1混合泳接力队的选拔5名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种.甲乙丙丁戊蝶泳仰泳蛙泳自由泳讨论:丁的蛙泳成绩退步到；戊的自由泳成绩进步到,组成接力队的方案是否应该调整？目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=0

0-1规划模型

cij(s)~队员i第j种泳姿的百米成绩约束条件每人最多入选泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有1人模型求解MODEL:sets:person/1..5/;position/1..4/;link(person,position):c,x;endsetsdata:c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6,57.2,67.4,71,83.8,62.4;enddata输入LINGO求解

min=@sum(link:c*x);@for(person(i):@sum(position(j):x(i,j))<=1;);@for(position(i):@sum(person(j):x(j,i))=1;);@for(link:@bin(x));END模型求解最优解：x14=x21=x32=x43=1,其他变量为0;输入LINGO求解

甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.成绩为253.2(s)=甲乙丙丁戊蝶泳仰泳蛙泳自由泳丁蛙泳c43

=69.675.2(s)，戊自由泳c54=62.4

57.5(s),方案是否调整？

敏感性分析？新方案:乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP一般没有与LP相类似的理论，LINGO输出的敏感性分析结果通常是没有意义的.c43,c54

的新数据重新输入模型，用LINGO求解

原分配方案:甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.讨论最优解：x21=x32=x43=x51=1,成绩为混合泳接力队的选拔指派(Assignment)问题：有若干项任务,

每项任务必有且只能有一人承担，每人只能承担一项，不同人员承担不同任务的效益(或成本)不同，怎样分派各项任务使总效益最大(或总成本最小)?

人员数量与任务数量相等

人员数量大于任务数量(本例)

人员数量小于任务数量

?建立0-1规划模型是常用方法为了选修课程门数最少，应学习哪些课程？

例

选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号课名学分所属类别先修课要求1微积分5数学