优化问题与LINGO软件1

优化问题与

LINGO软件1/13/20231（一）

线性规划问题概述1/13/20232【例1】

生产计划问题1/13/20233

2x1

+x2

8s.t.x1

3x2

4

x1，x2

0

maxf=5x1+2x2

求最大利润三种材料量的限制生产量非负1/13/20234【例2】

运输问题1/13/20235解：设A1,A2调运到三个粮站的大米分别为x1，x2，

x3，

x4，

x5，

x6吨。题设量可总到下表：1/13/20236结合存量限制和需量限制得数学模型：1/13/20237

m个产地A1,…,Am联合供应n个销地B1,…,Bn,各产地至各销地单位运价(单位:元/吨)为cij，问如何调运使总运费最少?一般运输问题总运价产量限制需量限制运量非负1/13/20238假设产销平衡:在很多实际问题中,解题思想和运输问题同出一辙,也就是说我们可以用运输模型解决其他问题.1/13/20239设有n件工作B1,B2,…Bn,分派给n人A1,A2,…An去做,每人只做一件工作且每件工作只派一个人去做,设Ai完成Bj的工时为cij,问应如何分派才能完成全部工作的总工时最少.每件工作只派1人每个人只派做1件【例3】

分派问题变量xi只取0和1,故建立的模型也称0-1规划.1/13/202310【例4】

选址问题1/13/202311现要做100套钢架,用长为2.9m、2.1m和1.5m的元钢各一根,已知原料长7.4m,问如何下料,使用的原材料最省?分析:下料方式：最省：1.所用刚架根数最少；2.余料最少【例5】下料问题1/13/202312原料截成所需长度的根数下料方法ⅠⅡⅢⅣⅤⅥⅦⅧ所需根长2.9m211100002.1m021032101.5m10130234剩余料头0.10.30.901.10.20.81.41/13/202313不同方法截得每种根长的总数至少100例3,4中的此例的变量xi只取正整数,故建立的模型也称整数规划.0-1规划是整数规划的特殊情形.1/13/202314某公司生产某产品,最大生产能力为100单位,每单位存储费2元,预定的销售量与单位成本如下:月份单位成本(元)销售量1234

70607270801207660求一生产计划,使1)满足需求;2)不超过生产能力;3)成本(生产成本与存储费之和)最低.【例6】阶段生产问题1/13/202315解:假定1月初无库存,4月底买完,当月生产的不库存,库存量无限制.第j+1个月的库存量第j+1个月的库存费共3个月的库存费到本月总生产量大于等于销售量4个月总生产量等于总销售量4个月总生产成本1/13/2023161/13/202317月份单位成本(元)销售量1234

706072708012076601/13/20231876827676---80--7472-747270生产月100100100100产量6041207060销量4321321需求月费用cij1/13/202319本题3个模型为整数规划模型.1/13/202320线性规划模型特点决策变量：向量(x1…xn)T

,决策人要考虑和控制的因素非负；约束条件：线性等式或不等式；目标函数：Z=ƒ(x1

…xn)

线性式，求Z极大或极小；线性规划问题的数学模型将实际问题转化为在一组线性不等式或等式约束下求线性目标函数的最大最小问题。1/13/202321一般形式目标函数约束条件用CAI补充矩阵知识22矩阵形式1/13/202323满足约束条件的变量的值称为可行解，可行解的集合称为可行域。使目标函数达到最大（小）值的可行解称为最优解，相应的目标函数的值称为最优值。1/13/202324线性规划问题的性质:比例性

每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比.可加性每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关.连续性每个决策变量的取值都是连续的.1/13/202325应用市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)1/13/202326（二）

一般优化问题概述1/13/202327优化问题三要素：决策变量decisionbariable；目标函数objectivefunction；约束条件constraints约束条件决策变量优化问题的一般形式目标函数等约束equalityconstraint不等约束inequalityconstraint1/13/202328要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件特点1/13/202329可行解feasiblesolution（满足约束）与可行域feasibleregion（可行解的集合）最优解optimalsolution（取到最小minimum／大值maximum的可行解,对应最优值optimalvalue）局部最优解或相对最优解local/relativeoptimizer全局或整体最优解globaloptimizaer优化模型的基本类型无约束优化unconstrainedoptimization约束优化constrainedoptimization特殊：等式（不等式）方程组systemofequations(inequations)1/13/202330约束优化constrainedoptimization的简单分类1.数学规划mathematicalprogramming或连续优化continuousoptmization线性规划(LP)

目标和约束均为线性函数

Linearprogramming非线性规划(NLP)

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

Nonlinearprogramming

二次规划(QP)

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

Quadraticprogramming1/13/202331整数规划(IP)

决策变量(全部或部分)为整数Integerprogramming

整数线性规划(ILP)，整数非线性规划(INLP)

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

一般整数规划，0-1（整数）规划Zero-oneprogramming2.离散优化discreteoptimization或组合优化combinatorialoptimization1/13/202332线性规划比例性可加性连续性最优解在凸多面体的某个顶点上取得此时，有积极约束或紧约束active/tightconstraints非积极约束inactiveconstraints敏感性分析sensitivityanalysis不可行infeasible,最优解optimizer,无界unbounded单纯形法simplexmethod基变量basicbarible,非基变量nonbasic

barible基解basicsolution迭代或旋转pivot内点算法interiorpointmethod:内部逼近，适用大规模1/13/202333二次规划积极集方法activesetmethod非线性规划算法非线性规划迭代，判停，一般只能找到局部最优解整数规划枚举法，隐枚举法分支定界法branchandboundmethod1/13/202334常用优化软件1.LINDO/LINGO软件2.MATLAB优化工具箱3.EXCEL软件的优化功能4.SAS(统计分析)软件的优化功能5.其他1/13/202335（三）

线性规划问题的基本理论1/13/202336【例1】用图解法求解线性规划问题是一簇斜率为-5/2的平行直线族斜率为-2C/2为直线与y轴的交点x10x284431/13/202337x240x1834如图所示:显然直线向右上移动时，与y轴交点越高，从而c/2越大，使得目标函数值c越大。1/13/202338结论从上述几何直观可看出：⑴线性规划问题的任意两个可行解联线上的点都是可行解；⑵线性规划问题的任意两个最优解联线上的点都是最优解；⑶线性规划问题的最优值若存在，则一定在某个顶点达到。1/13/202339标准形式:任何一个线性规划问题都可以化为标准形式1/13/202340如果给定的LP问题是极大化问题,即可化为极小化问题约束条件不变,其最优解是一致的,但目标函数值的符号相反.则:结论:如果问题是求目标函数的最大值,则化为求–f

的最小值;1.关于目标函数1/13/2023412.关于约束条件(1)如果给定的LP有约束不等式1/13/202342注意:新引入的变量在目标函数和约束条件中的系数均为0.(2)如果给定的LP有约束不等式1/13/2023433.关于变量在标准形式中,所有的变量都有非负限制,如果某些变量没有非负限制,则称这些变量为自由的.两种处理办法:1/13/202344【例2】1/13/202345【例３】1/13/202346相应的典式如下:最优值为5.非基可行解．是最优解，1/13/202347每吨产品需用原料产品现有原料（吨）ⅠⅡⅢ原料AB

211132711每吨产品利润（万元）

231某工厂可以用A、B两种原料生产Ⅰ、Ⅱ、Ⅲ三种产品（每种产品都同时需要用两种原料），有关数据如下表：【例４】1/13/202348问:1、若目前市场上原料A的实际价格为0.5万元/吨,工厂应如何决策?2、若目前市场上原料A的实际价格为0.8万元/吨,工厂应如何决策?解:设x1,x2,x3分别表示Ⅰ,Ⅱ,Ⅲ的生产量,建立模型:1/13/202349互为对偶问题1/13/202350对应目标函数值为f=13万元.最优解:原料A

的数量b1在[11/3,22]之间变化时，最优基不变.对偶问题的最优解为：y1=3/5,y2=4/51/13/202351(1)若目前市场上原料A的实际价格为0.5万元/吨时,它低于原料A的影子价格0.6,因此,可以考虑购进原料,以扩大生产能力,为保证原最优基不变,购进原料A的最大数量为22-7=15吨.此时,问题的目标值为f=13+15×0.6=22万元,扣除购进原料成本0.5×15=7.5万元,实际赢利为14.5万元,比现有原料进行生产多赢利1.5万元.1/13/202352(2)若目前市场上原料A的实际价格为0.8万元/吨时,它高于原料A的影子价格0.6,因此,可以考虑出售部分原料,为保证原最优基不变,出售原料A的最大数量为10/3吨.此时,实际赢利为13-10/3×0.6+10/3×0.8=13+2/3万元,比用现有原料生产多赢利2/3万元.1/13/202353

123456789654321（2.25，3.75）

123456789654321分枝定界法1/13/202354隐枚举法过滤条件检验可行目标值可行检验过滤检