第4章 线性规划模型1_基本模型及教案.ppt

数学建模讲义第4章线性规划模型,黄可坤嘉应学院,-基本模型,1优化模型,优化：在一定条件下，使目标最大的决策。优化问题是经常遇到的问题，如：结构设计，资源分配，生产计划，运输方案等。全国大学生数模竞赛题一半以上与优化有关，并且需用软件求解。,无约束优化,给定一个函数f(x)，寻找x使得f(x)最小，其中x=(x1,x2,xn)。,最优值出现在定义区间端点，不可导点，稳定点。,有约束优化,如果f(x)和hi(x)可导，则可以用拉格朗日方法化为无约束优化问题：,规划问题,最优解在定义域的边界上达到。线性规划：目标和约束均为线性函数。非线性规划：目标和约束存在非线性函数。二次规划：目标为二次函数，约束为线性整数规划：决策变量为整数。0-1规划：决策变量只为0或者是1,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到30元/公斤，应否改变生产计划？,每天：,例：加工奶制品的生产计划,x1桶牛奶生产A1,x2桶牛奶生产A2,获利243x1,获利164x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,模型求解,软件实现,LINGO8.0,max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1Solve,20桶牛奶生产A1,30桶生产A2，利润3360元。,结果解释,OBJECTIVEFUNCTIONVALUE:3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES13360.0001.00000020.00000048.0000030.0000002.000000440.000000.000000,原料无剩余,时间无剩余,加工能力剩余40,max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1GeneralSolver-DualComputations:Prices”结束。变量以字母开头，不能超过8个字符。变量名不区分大小写（包括关键字）。目标函数用min=3*x1+2*x2或max=3*x1+2*x2的格式表示。“!”后为注释。变量界定函数实现对变量取值范围的附加限制，共4种：bin(x)限制x为0或1bnd(L,x,U)限制LxUfree(x)取消对变量x的默认下界为0的限制，即x可以取任意实数gin(x)限制x为整数,实验,具体题目见实验指导”Lingo求解线性规划问题”。按照实验报告的格式，特别是要有结果分析。用A4纸打印。三人一组交