数学规划模型概述课件.ppt

数学规划模型概述,假期你想去旅游。假如你只去一个地方而且只有一条线路可走，反倒省心一些如果你要去许多地方，又有许多路线，许多交通工具，而你还想尽量节省路费，那么你就要考虑“最优决策”或“最优（方案）设计”的问题了最优化(optimization)是企业运作、科技研发和工程设计中常见的问题要表述一个最优化问题(即建立数学模型)，应明确三个基本要素：决策变量（decision variables）约束条件(constraints)目标函数(objective function),决策变量(decision variables):它们是决策者所控制的那些数量，它们取什么数值需要决策者来决策，最优化问题的求解就是找出决策变量的最优取值约束条件(constraints)：它们是决策变量在现实世界中所受到的限制，或者说决策变量在这些限制范围之内取值才有实际意义目标函数(objective function):它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数,如果一个最优化问题的决策变量不是时间的函数，则属于静态优化(static optimization)或有限维优化(finite dimensional optimization)的范畴按照静态优化问题的结构是否线性分为线性规划和非线性规划线性规划的特征是目标函数和约束条件中的函数都是决策变量的线性函数，并且约束是必不可少的（否则不存在有实际意义的解）,三要素：决策变量；目标函数；约束条件,数学规划模型的一般形式,规划问题：求目标函数在约束条件下的最值可行解（只满足约束）与最优解(取到最优值),数学规划模型的简单分类,线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标或约束中存在非线性函数 二次规划(QP)目标为二次函数、约束为线性 整数规划(IP)决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0(MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性极小fminunc,非光滑(不可微)优化fminsearch,非线性方程(组)fzerofsolve,全局优化暂缺,非线性最小二乘lsqnonlinlsqcurvefit,线性规划linprog,纯0-1规划 bintprog一般IP(暂缺),非线性规划fminconfminimaxfgoalattainfseminf,上下界约束fminbndfminconlsqnonlinlsqcurvefit,约束线性最小二乘lsqnonneglsqlin,约束优化,二次规划quadprog,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,LINDO,LINGO,LINDO/LINGO软件能求解的模型,LP QP NLP IP 全局优化(选)ILP IQP INLP,LINGO软件的求解过程,LINGO预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1.确定常数2.识别类型,1.单纯形算法2.内点算法(选),1、顺序线性规划法(SLP)2、广义既约梯度法(GRG)(选)3、多点搜索(Multistart)(选),LINGO软件的功能与特点,LINGO模型的优点,集成了线性(非线性)/连续(整数)优化功能 具有多点搜索/全局优化功能 提供了灵活的编程语言(矩阵生成器)，可方便地输入模型 提供与其他数据文件的接口 提供与其他编程语言的接口 LINDO API 可用于自主开发 运行速度较快,LINDO 公司软件产品简要介绍,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发,后来成立 LINDO系统公司（LINDO Systems Inc.），网址：http:/,LINDO:Linear INteractive and Discrete Optimizer(V6.1)LINDO API:LINDO Application Programming Interface(V4.1)LINGO:Linear INteractive General Optimizer(V10.0)Whats Best!:(SpreadSheet e.g.EXCEL)(V8.0),演示(试用)版、高级版、超级版、工业版、扩展版（求解问题规模和选件不同）,历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。,线性规划模型,1939年前苏联康托洛维奇（KOHTOPOBUZ）生产组织与计划中的 数学方法提出“解乘数法”。,线性规划理论的发展,美国科学院院士DANTZIG（丹齐克），1948年在研究美国空军资源的优化配置时提出线性规划及其通用解法“单纯形法”。被称为线性规划之父。,线性规划之父的Dantzig(丹齐克)。据说，一次上课，Dantzig迟到 了，仰头看去，黑板上留了几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是惭愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很不解,后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。,1960年，“最佳资源利用的经济计算”康托洛维奇和库伯曼斯(Koopmans)。两人因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖,1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。20世纪70年代，斯姆李与杰斯开莱尼应用计算机处理目标规划问题,从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。,保罗-萨缪尔逊（PAUL A SAMUELSON）,他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里列昂惕夫（WASSILY LEONTIEF），美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗（KENNETH J.ARROW）,美国人，因与约翰-希克斯（JOHN R.HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒（MERTON M.MILLER）,1923-2000,美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。,一个农场有50亩土地,20个劳动力,计划种蔬菜,棉花和水稻.种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4,预计每亩产值分别为 110元,75元,60元.如何规划经营使经济效益最大.,种植蔬菜 x1 亩,棉花 x2 亩,水稻 x3 亩(决策变量)以取得最高的产值的方式达到收益最大的目标.求f=110 x1+75x2+60 x3的最大值(目标函数、优劣标准)约束条件 x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 x1，x2，x3 0,例1 农作物种植,max:Z=110 x1+75x2+60 x3 s.t.x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 x1，x2，x3 0,如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。实际问题中线性的含义：一是严格的比例性二是可叠加性,关于线性的界定,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij,bi,ci为确定值。,正则模型 决策变量:x1,x2,xn.目标函数:Z=c1x1+c2x2+cnxn.求目标函数的最小或最大 约束条件:a11x1+a1nxnb1,am1x1+amnxnbm,线性规划的数学模型及其标准化,标准化模型 决策变量 x1,x2,xn,max Z=c1x1+cnxn,s.t.a11x1+a1nxn=b1,am1x1+amnxn=bm,x1 0,xn 0,模型的标准化 10.引入松弛变量将不等式约束变为等式约束 若有 ai1x1+ainxnbi,则引入xn+i 0,使得 ai1x1+ainxn+xn+i=bi 若有 aj1x1+ajnxnbj,则引入xn+j 0,使得 aj1x1+ajnxn-xn+j=bj.且此时目标函数Z=c1x1+c2x2+cnxn+0 xn+1+0 xn+m.20.将目标函数的优化变为目标函数的极大化.若求 min Z,令 Z=Z,则问题变为 max Z.30.引入人工变量,使得所有变量均为非负.若xi没有非负的条件,则引入 xi 0和xi0,令xi=xi xi,则可使得问题的全部变量均非负.,线性规划的对偶性和影子价格,农作物种植（续）：一个农场有50亩土地,20个劳动力,计划种蔬菜,棉花和水稻.种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4,预计每亩产值分别为110元,75元,60元.如果出租土地和劳动力如何规划经营使经济效益最大.,决策变量:单位土地和单位劳力出租价格分别为 y1 y2,目标函数:g=50y1+20y2,优劣准则:应求g的最小值.(因为要达到的要求已经通过约束条件满足，决策者关心的是在基本要求达到时出租价格的心理底线是多少？标底),约束条件:y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60(成本不小于产值)（我出租出去要比自己种植合适。出租底线）,对偶线性规划,原问题 max f=cTx s.t.Ax b xi 0,i=1,2,n.,对偶问题 min f=bTy s.t.ATy c yi 0,i=1,2,m.,max:Z=110 x1+75x2+60 x3 s.t.x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 x1，x2，x3 0,A 是m n 矩阵，c 是 n 1向量，b 是 m 1向量 x 是 n 1向量,y 是 m 1向量,min：g=50y1+20y2s.t.y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60 y1，y2 0,对偶定理:互为对偶的两个线性规划问题 若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等.若两者之一有无界的最优解,则另一个没有可行解。,模型II 给出了生产中资源的最低估价.这种价格涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中做出的贡献确定的估价,被称为“影子价格”。,模型I 给出了生产中的资源最优分配方案。,灵敏度分析主要包括下面几个内容：1：当约束条件的右边常数项变化的影响；2：约束条件的系数变化的影响；3：目标函数的系数变化的影响。可能的影响结果：1：最优解保持不变；2：基变量保持不变，但值变了；3：基本解变化。,线性规划的灵敏度分析,例：简单的线性规划（LP）问题,在空白的模型窗口中输入这个LP模型：,max 2x+3yst 4x+3y=10 3x+5y12end,附录1：用Lindo解线性规划,如图：,程序以“MAX”（或“MIN”）开始，表示目标最大化（或最小化）问题，后面直接写出目标函数表达式和约束表达式；目标函数和约束之间用“ST”分开；（或用“s.t.”，“sunject to”）程序以“END”结束（“END”也可以省略）。系数与变量之间的乘号必须省略。系统对目标函数所在行自动生成行名“1）”,对约束默认的行名分别是“2)”“3)”，用户也可以自己输入行名；行名放在对应的约束之前。书写相当灵活，不必对齐，不区分字符的大小写。默认所有的变量都是非负的,所以不必输入非负约束。约束条件中的“=”可分别用“”代替。一行中感叹号“！”后面的文字为是注释语句，可增强程序的可读性，不参与模型的建立。,LINDO程序有以下特点,模型求解,用鼠标点击工具栏中的图标，或从菜单中选择Solve|Solve（Ctrl+S）命令,LINDO首先开始编译这个模型，编译没有错误则开始求解；求解时会首先显示如右图所示的LINDO“求解器运行状态窗口”。,求解器运行状态窗口显示的相应信息及含义,紧接着弹出一对话框，询问你是否需要做灵敏性分析（DO RANGE(SENSITIVITY)ANALYSIS?）先选择“否（N）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。,报告窗口,用鼠标选择“Window|Reports Window”（报告窗口），就可以查看该窗口的内容,保存文件,选择File|Save（F5）命令把“结果报告”保存在一个文件中（缺省的后缀名为LTX,即LINDO文本文件）类似地，回到模型窗口，可以把输入的模型保存在一个文件中。保存的文件将来可以用File|Open（F3）和File|View（F4）重新打开，用前者打开的程序可以进行修改，而后者只能浏览。,如果模型有错误,运行时会弹出出错信息报告窗口(LINDO Error Message)，则需要修改模型。,例1：某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示。,若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？,解：,用DESKS、TABLES和CHAIRS分别表示三种产品的生产量（决策变量），容易建立LP模型。,在LINDO模型窗口中输入模型：,MAX 60 DESKS+30 TABLES+20 CHAIRSSUBJECT TO 2)8 DESKS+6 TABLES+CHAIRS=48 3)4 DESKS+2 TABLES+1.5 CHAIRS=20 4)DESKS+1.5 TABLES+0.5 CHAIRS=8 5)TABLES=5END,解这个模型，并对弹出的对话框“DO RANGE(SENSITIVITY)ANALYSIS?”选择“是（Y）”按钮，这表示你需要做灵敏性分析。然后，查看输出结果。,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)280.0000 VARIABLE VALUE REDUCED COST DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)24.000000 0.000000 3)0.000000 10.000000 4)0.000000 10.000000 5)5.000000 0.000000 NO.ITERATIONS=1,输出结果的前半部分：,前半部分的输出结果的解释:,“LP OPTIMUM FOUND AT STEP2”表示两次迭代（旋转变换）后得到最优解。,“OBJECTIVE FUNCTION VALUE 1）280.000000”表示最优目标值为280。,“VALUE”给出最优解中各变量的值：造2个书桌（desks）,0个餐桌（tables）,8个椅子（chairs）。所以desks、chairs是基变量（取值非0），tables是非基变量（取值为0）。,“SLACK OR SURPLUS”给出松驰变量的值。（在最优的情况下资源的剩余量）第2行松驰变量=24（第1行表示目标函数，第2行对应第1个约束）第3行松驰变量=0 第4行松驰变量=0 第5行松驰变量=5,“REDUCED COST”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时,目标函数的变化率.其中 基变量的reduced cost值应为0;非基变量 Xj，相应的 reduced cost值1）表示当非基变量Xj 增加一个单位时，目标函数相应减少的量(max型问题)。2）理解为：为了使该非基变量变成基变量，目标函数中该变量前对应系数应增加的量。,本例中：变量TABLES对应的reduced cost值为5。1）表示当非基变量TABLES 的值从0变为1时（此时假定其它非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），此时的最优的目标函数值为280-5=275。2）理解为目前table的单价30元偏低，不值得生产，如果生产的话至少35元。,“DUAL PRICE”（对偶价格）表示当对应约束有微小变动时,目标函数的变化率.输出结果中对应于每一个约束有一个对偶价格.若其数值为p,表示对应约束中不等式右端项若增加1个单位,目标函数将增加p个单位（max型问题)。也就是相应的一个单位的该资源在生产过程中产生的效益，即其价值。1）如果在最优解处约束正好取等号（也就是“紧约束”现有相应资源全部使用），该资源的对偶价格才可能不是0。例如本例中：第3行是紧约束，对应的是资源是漆工，其对偶价格值为10，表示当紧约束 4 DESKS+2 TABLES+1.5 CHAIRS=20变为 4 DESKS+2 TABLES+1.5 CHAIRS=21时，目标函数值是280+10=290。即若再增加一名漆工的话，可增加10的利润。2）对于非紧约束（如本例中第2行木料是非紧约束），DUAL PRICE 的值为0,表示对应约束中不等式右端项的微小扰动不影响目标函数。因为最优的时候还有剩余。,输出结果的后半部分：,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE DESKS 60.000000 20.000000 4.000000 TABLES 30.000000 5.000000 INFINITY CHAIRS 20.000000 2.500000 5.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 48.000000 INFINITY 24.000000 3 20.000000 4.000000 4.000000 4 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000,（报告中INFINITY表示正无穷）,1.目标函数中系数变化的范围（OBJ COEFFICIE NT RANGES）如本例中：目标函数中DESKS变量当前的系数(CURRENT COEF)=60，允许增加(Allowable Increase)=4、允许减少(Allowable Decrease)=2，说明当这个系数在60-4，60+20=56，80范围变化时，最优基保持不变。对TABLES、CHAIRS变量，可以类似解释。由于此时约束没有变化（只是目标函数中某个系数发生变化），所以最优基保持不变的意思也就是最优解不变（当然，由于目标函数中系数发生了变化，所以最优值会变化）。,这个部分包括两方面的敏感性分析内容：,2.约束右端项变化的范围（Right Hand Side RANGES）如本例中：第2行约束中当前右端项(CURRENT RHS）=48，允许增加（Allowable Increase）=INFINITY（无穷）、允许减少（Allowable Decrease）=24，说明当它在 48-24，48+)=24，）范围变化时，最优基保持不变。第3、4、5行可以类似解释。不过由于此时约束发生变化，最优基即使不变，最优解、最优值也会发生变化。,1.变量名由字母和数字组成，但必须以字母开头，且长度不能超过8个字符，不区分大小写字母，包括关键字（如MAX、MIN等）也不区分大小写字母。,2.对目标函数和约束用行号（行名）进行标识，这些标识会在将来的求解结果报告中用到。行名可以和变量名一样命名，也可以只用数字命名，还可以含有中文字符，但长度同样不能超过8个字符。为了方便将来阅读求解结果报告，建议用户总是自觉地对每个约束进行命名。行名结束标志符号、即右括号“）”必须是英文字符，否则会出现错误。,LINDO模型的一些注意事项,3.可以用“TITLE”语句对输入的模型命名，用法是在TITLE后面写出其名字（最多72个字符，可以有汉字），在程序中单独占一行，可以在模型的任何地方。模型命名的第一个作用类似于对模型的注释和说明。模型命名的另一个目的，是为了方便将来阅读求解结果报告。因为用户有可能同时处理多个模型，很容易混淆模型与求解结果的对应关系。这时如果对不同模型分别进行了命名，就可以随时（例如在求解当前模型前）使用菜单命令“FILE|TITLE”将当前模型的名字显示在求解结果报告窗口中，这样就容易判别每个求解结果与每个模型的对应关系。,4.模型中以感叹号“!”开头的是注释行（注释语句，或称为说明语句），可以帮助他人或以后自己理解这个模型。实际上，每行中“!”符号后面的都是注释或说明。注释语句中可以使用汉字字符。,5.变量不能出现在一个约束条件的右端（即约束条件的右端只能是常数）；变量与其系数间可以有空格（甚至回车），但不能有任何运算符号（包括乘号“*”等）。,6.模型中不接受括号“()”和逗号“,”等符号（除非在注释语句中）。例如:4(X1+X2)需写为4X1+4X2；“10,000”需写为10000。,7.表达式应当已经经过化简。如不能出现2X1+3X2-4X1，而应写成-2X1+3X2等。,8.LINDO 中已假定所有变量非负。若要取消变量的非负假定，可在模型的“END”语句后面用命令“FREE”。例如，在“END”语句后输入FREE vname，可将变量vname的非负假定取消。,9.可以在模型的“END”语句后面用命令“SUB”（即设置上界（SET UPPER BOUND）的英文缩写）设定变量的上界，用命令“SLB”（即设置下界（SET LOWER BOUND）的英文缩写）设定变量的上下界。其用法是：“SUB vname value”将变量vname的上限设定为value；“SLB”的用法类似。用“SUB”和“SLB”表示的上下界约束不计入模型的约束，因此LINDO也不能给出其松紧判断和敏感性分析。,10.数值均衡化考虑：如果约束系数矩阵中各非零元的绝对值的数量级差别很大（相差1000倍以上），则称其为数值不均衡的。为了避免数值不均衡引起的计算问题,使用者应尽可能自己对矩阵的行列进行均衡化。此时还有一个原则,即系数中非零元的绝对值不能大于100000 或者小于.0001。LINDO 不能对LP 中的系数自动进行数值均衡化，但如果LINDO 觉得矩阵元素之间很不均衡,将会给出警告。,11.简单错误的检查和避免：输入模型时可能会有某些输入错误.当问题规模较大时,要查找错误是比较困难的。在LINDO 中有一些可帮助寻找错误的功能，其中之一就是菜单命令“Report|Picture（Alt+5）”,它的功能是可以将目标函数和约束表达式中的非零系数通过列表（或图形）显示出来。,附录2：用MATLAB优化工具箱解线性规划,min z=cX,1.模型：,命令：x=linprog（c,A,b）,2.模型：min z=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若没有不等式，则令A=，b=.,3.模型：min z=cX,VLBXVUB,命令：x=linprog（c，A，b，Aeq,beq,VLB，VUB）,注意：若没有等式约束:,则令 Aeq=,beq=.,4.命令：x,fval=linprog()返回最优解及处的目标函数值fval.,问题2 任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用不同车床加工单位数量的不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型：,编写M文件xxgh3.m如下:f=13 9 10 11 12 8;A=0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b=800;900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb=zeros(6,1);vub=;x,fval=linprog(f,A,b,Aeq,beq,vlb,vub),结果:x=0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval=1.3800e+004 即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.,注：本问题应还有一个约束条件：决策变量取整数.故它是一个整数线性规划问题。这里把它当成一个线性规划来解，求得其最优解刚好是整数，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解。,整数规划、0-1规划如果要求决策变量取整数,或部分取整数的数学规划问题,称为整数规划.如果要求决策变量只取0 或 1的线性规划问题,称为0-1规划.0-1 约束不一定是由变量的性质决定的,更多地是由于逻辑关系引进问题的.,整数规划、01规划模型,整数规划问题一般形式,整数线性规划(ILP)目标和约束均为线性函数 整数非线性规划(NLP)目标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP)决策变量均为整数 混合整数规划(MIP)决策变量有整数，也有实数,0-1规划 决策变量只取0或1,取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题,整数规划问题对应的松弛问题,下界（对Min问题）上界（对Max问题）,用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解（见例2）,对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解）,去掉整数限制后，可行域为点（0,0),(6,0),(0,5),P(2.25,3.75)围成的4边形,从LP最优解经过简单的“移动”不一定能得到IP最优解,例,LINDO可用于求解线性纯整数规划或混合整数规划(IP)，模型的输入与LP问题类似,但需在END标志后定义整型变量。,0/1型的变量可由INTEGER（可简写为INT）命令来标识，有以下两种可能的用法：INT vname INT n前者只将决策变量vname标识为0/1型,后者将当前模型中前n 个变量标识为0/1型（模型中变量顺序由模型中输入时出现的先后顺序决定,该顺序可由输出结果中的变量顺序查证是否一致）。,一般的整数变量可用命令GIN（是GENERAL INTEGER的意思）,其使用方式及格式与INT 命令相似。,LINDO求解整数线性规划概述,纯整数规划-聘用方案,决策变量：周一至周日每天(新)聘用人数 x1,x2,x7,目标函数：7天(新)聘用人数之和,约束条件：周一至周日每天需要人数,连续工作5天,设系统已进入稳态（不是开始的几周）,聘用方案,整数规划模型(IP),首先在LINDO模型窗口输入模型:,MIN X1+X2+X3+X4+X5+X6+X7SUBJECT TOMON)X1+X4+X5+X6+X7=50TUE)X1+X2+X5+X6+X7=50WED)X1+X2+X3+X6+X7=50THU)X1+X2+X3+X4+X7=50FRI)X1+X2+X3+X4-X5=80SAT)X2+X3+X4-X5+X6=90SUN)X3+X4-X5+X6+X7=90ENDGIN 7,其中“GIN 7”表示7个变量都是一般整数变量。（仍然默认为取值是非负的）,求解后状态窗口中与整数相关的三个域有了相关结果:,“Best IP：94”表示当前得到的最好的整数解的目标函数值为94（人）。“IP Bound：93.5”表示该整数规划目标值的下界为93.5（人）。“Branches：1”表示分枝数为1（即在第1个分枝中就找到了最优解）。我们前面说过，LINDO求解IP用的是分枝定界法。,显然，上面第二条“整数规划目标值的下界为93.5（人）”表明至少要聘用93.5名员工，由于员工人数只能是整数，所以至少要聘用94（人）。而第一条说明目前得到的解就是聘用94（人），所以已经是最优的了。,LP OPTIMUM FOUND AT STEP 8 OBJECTIVE VALUE=93.3333359 SET X2 TO=4 AT 1,BND=-94.00 TWIN=-93.50 18 NEW INTEGER SOLUTION OF 94.0000000 AT BRANCH 1 PIVOT 18 BOUND ON OPTIMUM:93.50000 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE.BRANCHES=1 PIVOTS=18 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION.,求解结果的报告窗口如下：,（接下页）,OBJECTIVE FUNCTION VALUE 1)94.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 4.000000 1.000000 X3 40.000000 1.000000 X4 2.000000 1.000000 X5 34.000000 1.000000 X6 10.000000 1.000000 X7 4.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES MON)0.000000 0.000000 TUE)2.000000 0.000000 WED)8.000000 0.000000 THU)0.000000 0.000000 FRI)0.000000 0.000000 SAT)0.000000 0.000000 SUN)0.000000 0.000000 NO.ITERATIONS=18 BRANCHES=1 DETERM.=1.000E 0,报告窗口中前两行告诉我们：在8次迭代后找到对应的线性规划（LP）问题的最优解，最优值=93.3333359。LINDO求解IP用的是分枝定界法，紧接着几行显示的是分枝定界的信息，在第1个分枝中设定x2=4,并在该分枝中找到了整数解，而且就是全局整数最优解，所以算法停止。旋转迭代（PIVOT）共18次。,后面显示的是最后的最优解：x=(0,4,40,2,34,10,4).松弛和剩余变量（SLACK OR SURPLUS）仍然可以表示约束的松紧程度，但目前IP尚无相应完善的敏感性分析理论，因此REDUCED COST和DUAL PRICES的结果在整数规划中意义不大。,聘用方案（续）邮局一周中每天需要不同数目的雇员，设周一至少需要a1人，周二至少需要a2人，周三至少需要a3人，等等。又规定应聘者需连续工作5天，问邮局每天聘多少雇员才能既满足需求，又使聘用总人数最少。进一步考虑，上述指全时雇员（每天工作8小时）。如果邮局也可聘用半天雇员（每天工作4小时，连续工作5天），设全时和半时雇员的工资每小时为3元和2元，并且限制半时雇员的工作量不应超过总工作量的四分之一，问邮局如何安排聘用方案，使所付工资总额最少？,分析此时决策变量由两部分构成：全时雇员x1,x2,x3,x4,x5,x6,x7;半时雇员y1,y2,y3,y4,y5,y6,y7.目标值应该是雇员的总工资，标准是最少：min:Z=385xi245yi约束条件：每天的工作量应该折合为小时工作量(以周一的工作量为例)8(x4x5x6x7x1)4(y4y5y6y7y1)=8a1 半时雇员的限制 45yi=0.258(ai),一个旅行者的背包最多只能装 6 kg 物品.现有4 件物品 重量为 2 kg,3 kg,3 kg,4 kg,价值为 1 元,1.2元,0.9元,1.1元.应携带那些物品使得携带物品的价值最大?,0-1规划 背包问题,决策变量：xj 旅行者是否携带第 j 件物品,xj=0,1.约束条件 2x1+3x 2+3x 3+4x 4 6目标函数 f=x1+1.2x2+0.9x3+1.1x4 优劣标准：最大.,用Lingo 软件求解0-1规划Linear Interactive and General OptimizerModel:Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4=6;bin(x1);bin(x2);bin(x3);bin(x4);end,工厂可用k种不同的工艺生产n种产品，每种产品的利润已知。在各种工艺条件下每种产品所消耗的资源是确定的，并且，工厂的总资源有一定限制。问应选择哪种工艺，每种产品各生产多少，使总利润最大,混合0-1规划 生产工艺问题,分析有关参量：用A1,A2,Ak表示k种工艺；用B1,B2,Bn表示n种产品；单件Bi的利润pi；在工艺Aj下,资源限制Qj，单件Bi的资源消耗cij。,决策变量：一是Bi的产量xi；一是工艺的选择。,目标函数:max:Zp1*x1+p2*x2+pn*xn,资源限制约束：cij*xi=Qj j=1,2,k,工艺选择:引入01变量 yj=0 选择第j个工艺；yj=1 否则,约束条件：yj=k-1,yj=0,1,xi=0 为保证yj1的工艺不被选择，资源限制条件改为 cij*xi=Qj+yjM j=1,2,k 其中M充分大的一个正数。（当yj1时，此约束条件对任何决策变量xi都成立，所以在k个资源限制约束中只有yj0的有效。）,某厂生产两个牌号的同一种产品，如何确定产量使利润最大,二次规划模型产销计划问题,=（100-x1-0.1 x2-2）x1+（280-0.2x1-2x2-3）x2=98 x1+277 x2 x12 0.3 x1 x2 2x22,约束,x1+x2 100 x1 2 x2x1,x2 0,二次规划模型(QP),若还要求产量为整数，则是整数二次规划模型(IQP),非线性规划模型选址问题,某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）,假设：料场和工地之间有直线道路,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型(LP),决策变量：ci j(料场j到工地i的运量）12维,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。,决策变量：ci j，(xj,yj)16维,非线性规划模型(NLP),上机作业：装货问题要把7种规格的包装箱装到两辆铁路平板车上去，箱子的宽、高相同，而厚度和重量不同。每辆平板车有10.2米长的地方用于装箱（象面包片一样），载重40吨。由于货运限制，对5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过302.7厘米。试把包装箱装到平板车上，使浪费的空间最小。,1 2 3 4 5 6 7 厚度t(cm)48.7 52.0 61.3 7