《数学实验线性规划》由会员分享，可在线阅读，更多相关《数学实验线性规划（66页珍藏版）》请在金锄头文库上搜索。
1、重庆大学数理学院,国家级精品课程数学实验课件,数学实验之线性规划,SHUXUESHIYANZHIXIANXINGGUIHUA,课件制作：数学实验课程组,2002.5.,1,1理解优化模型的三个要素:决策变量，目标函数和约束条件； 掌握用MATLAB优化工具箱求解线性规划的方法； 了解线性规划模型中的灵敏度分析方法；掌握如何使用软件来实现分析； 体验由实际问题建立线性规划模型的全过程。,实验目的,2002.5.,2,成功的优化例子,“最优人员安排”为美国航空每年节约两千万美元.,2002.5.,3,成功的优化例子,“改进的出货流程”每年为Yellow Freight 公司节约一千七百多万美元.,
2、2002.5.,4,成功的优化例子,“改进的卡车分派”为 Reynolds 公司每年节约七百万美元 .,2002.5.,5,成功的优化例子,“最优全局供应链”为数字设备行业节约超过三亿美元.,2002.5.,6,成功的优化例子,宝洁公司重建北美业务, 减少 20%的工厂, 每年节约两亿美元.,2002.5.,7,成功的优化例子,大阪Hanshin高速的 “最优交通控制”每年节约一千七百万人小时 ,为他们带来三亿二千万美圆的收益.,2002.5.,8,2002.5.,9,引 例,在一定的条件下，问生产数量为多少时, 利润达到最大？,数据表,生产计划问题,2002.5.,10,引 例,运输问题,目
3、标：运费达到最小,2002.5.,11,特点：从若干可能的计划（方案）中寻求某种意义下的最优方案，数学上将这种问题称为最优化问题（optimization).,1、生产计划问题；,2、运输问题；,最优化问题简介,2002.5.,12,优化问题的表述,最优化是企业运作、科技研发和工程设计中常见的问题。,要表述一个最优化问题（即建立数学模型），应明,明确三样东西：决策变量、约束条件 和目标函数,决策变量：它们是决策者（你）所控制的那些数量，它们取什么数值需要决策者来决策，最优化问题的求解就是找出决策变量的最优取值。,约束条件：它们是决策变量在现实世界中所受到的限制，或者说决策变量在这些限制范围之内
4、取值才有实际意义。,目标函数：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。,2002.5.,13,规划模型,利润,材料,工时,人力,生产计划问题,max,目标函数,约束条件,决策变量,x1, x2, x3,2002.5.,14,生产计划问题,2002.5.,15,最优化问题,运输问题,目标：运费达到最小,2002.5.,16,cij 单位运费； ai 在第i 厂提供的量； bj 第j 地需要量； 求从si运多少钢管到Aj, 可使总运费最少. 决策变量: xij 从si运到Aj的钢管数量,C11,C12,Ci,j,ai,a1,a2,a7,b15,b1,b2,bj,2002.
5、5.,17,2002.5.,18,三个基本要素,1、决策变量（decision variables); 2、约束条件（constraints); 3、目标函数（objective function),最优化问题分类 线性、非线性 静态、动态 整数、非整数 随机、非随机等,最优化问题,2002.5.,19,最优化数学模型的分类,线性规划(LP) 非线性规划(NLP)二次规划(QP) 整数规划(IP) 多目标规划动态规划,最优化问题,2002.5.,20,生产计划问题,该模型的目标函数和约束条件均为线性函数, 满足线性规划的要求,故该问题为一线性规划问题,其模型为线性规划模型.,线性规划,2002
6、.5.,21,生产计划问题,max cTx s.t. Axbx0,矩阵形式：,线性规划模型,2002.5.,22,min (max) cTx s.t. Axb, (或Ax = b)x0 (或a x b),标准形式,其中：xRn，A Rmn， bRm， cRn,线性规划,2002.5.,23,2 X1 + X2 = 40,X1 + 2 X2 = 50,a,b,c,d,可行点 可行域 凸多面体,v,内点,边界点,顶点,v,B,线性规划解的若干概念,线性规划模型,max z = 5x1+3x2 s.t. 2x1+x240x1+2x250 x1，x20,2002.5.,24,线性规划解的图示,线性规划
7、模型,max z = 5x1+3x2 s.t. 2x1+x240x1+2x250 x1，x20,a,20,x1=10,x2=20,25,问:什么样的问题可以使用图解法?你从图中得到什么启示?,P=0,P=50,P=110,2002.5.,25,求解LP的特殊情形,Max z = 3x1+x2 s.t. -x1+x22 -L1x1-2x22 -L23x1+2x214 -L3x1，x20,x1, 无最优解, 无可行解, 最优解不唯一,2002.5.,26,线性规划的基本性质,可行域 线段组成的凸多边形 目标函数 等值线为直线 最优解 凸多边形的某个顶点,LP的基本性质：可行域存在时，必是凸多面体；
8、可行解对应于可行域中的点；最优解存在时，必在可行域的顶点取得。 LP的通常解法是单纯形法。,超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点,2 维,n 维,2002.5.,27,Matlab中求解线性规划的命令为: linprog, 解决的线性规划的标准格式为：min cTx xRns.t. Ax = b Aeqx = beqVLBxVUB其中，A, b, c, x, Aeq, beq, VLB, VUB等均表示矩阵,特别b, c, x, beq, VLB, VUB为列矩阵。,MATLAB软件求解,2002.5.,28,命令linprog的基本调用格式如果没有等式约束,就在相应位置输
9、入空数组 , 不等式约束和上下界也类似.最后的输入项若没有,则可省略.,x = linprog(c, A, b, Aeq,beq ,VLB, VUB),MATLAB软件求解,2002.5.,29,还可以增加输出,x, fval, exitflag, output = linprog(c, A, b, ）,MATLAB软件求解,2002.5.,30,看一个小例子 程序:c=-5,3; A=2,1;1,2; b=40,50; L=0, 0;x,fmin=linprog(c,A,b,L);Pmax=-fminx1=x(1), x2=x(2)输出结果:Pmax=110, x1=10, x2=20.,模
10、型: max P=5 X1 + 3 X2s.t. 2 X1 + X2 40 X1 + 2 X2 50X10, X20,MATLAB软件求解,2002.5.,31,加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,每天：,范 例,2002.5.,32,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,加工奶制品的生产计划,2002.5.,33,LINDO 6.1程序,max 72x1+64x2 st 2）x1+x250 3）12x1+8
11、x2480 4）3x1100 end,DO RANGE (SENSITIVITY) ANALYSIS?,No,加工奶制品的生产计划,范 例,2002.5.,34,OBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.0000003) 0.000000 2.0000004) 40.000000 0.000000NO. ITERATIONS= 2,20桶
12、牛奶生产A1, 30桶生产A2，利润3360元。,范 例,2002.5.,35,OBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.0000003) 0.000000 2.0000004) 40.000000 0.000000NO. ITERATIONS= 2,原料无剩余,时间无剩余,加工能力剩余40,三种资源,“资源” 剩余为零的约束为紧约束（有
13、效约束）,2002.5.,36,OBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.0000003) 0.000000 2.0000004) 40.000000 0.000000NO. ITERATIONS= 2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位, 利润增长48,时间增加1单位, 利润增长2,加工能力增长不影响利润,影子价
14、格,结果解释,2002.5.,37,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,加工奶制品的生产计划,范 例,2002.5.,38,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEX1 72.000000 24.000000 8.000000X2 64.000000 8.000000 16.000000RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASE2 50.000000 10.000000 6.6666673 480.000000 53.333332 80.0000004 100.000000 INFINITY 40.000000,
