单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数学建模讲义,第4章 线性规划模型,-基本模型,1 优化模型,优化：在一定条件下，使目标最大的决策。,优化问题是经常遇到的问题，如：结构设计，资源分配，生产计划，运输方案等。,全国大学生数模竞赛题一半以上与优化有关，并且需用软件求解。,无约束优化,给定一个函数f(x)，寻找x使得f(x)最小，其中x=(x1,x2,xn)。,最优值出现在定义区间端点，不可导点，稳定点。,有约束优化,如果f(x)和h,i,(x)可导，则可以用拉格朗日方法化为无约束优化问题：,规划问题,最优解在定义域的边界上达到。,线性规划：目标和约束均为线性函数。,非线性规划：目标和约束存在非线性函数。,二次规划：目标为二次函数，约束为线性,整数规划：决策变量为整数。,0-1规划：决策变量只为0或者是1,1桶牛奶,3公斤A,1,12小时,8小时,4公斤A,2,或,获利24元/公斤,获利16元/公斤,50桶牛奶,时间480小时,至多加工100公斤A,1,制订生产计划，使每天获利最大,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,公斤，应否改变生产计划？,每天：,例：加工奶制品的生产计划,1桶牛奶,3公斤A,1,12小时,8小时,4公斤A,2,或,获利24元/公斤,获利16元/公斤,x,1,桶牛奶生产A,1,x,2,桶牛奶生产A,2,获利 243,x,1,获利 164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A,1,50桶牛奶,每天,模型分析与假设,比例性,可加性,连续性,x,i,对目标函数的“贡献”与,x,i,取值成正比,x,i,对约束条件的“贡献”与,x,i,取值成正比,x,i,对目标函数的“贡献”与,x,j,取值无关,x,i,对约束条件的“贡献”与,x,j,取值无关,x,i,取值连续,A,1,A,2,每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A,1,A,2,的数量和时间是与各自产量无关的常数,A,1,A,2,每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A,1,A,2,的数量和时间是与相互产量无关的常数,加工A,1,A,2,的牛奶桶数是实数,线性规划模型,模型求解,图解法,x,1,x,2,0,A,B,C,D,l,1,l,2,l,3,l,4,l,5,约束条件,目标函数,Z,=0,Z,=2400,Z,=3600,z,=,c,(常数)等值线,c,在,B,(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,模型求解,软件实现,LINGO 8.0,max=72*x1+64*x2;,x1+x250;,12*x1+8*x2480;,3*x1Solve,20桶牛奶生产A,1,30桶生产A,2,，利润3360元。,结果解释,OBJECTIVE FUNCTION VALUE:3360.000,VARIABLE VALUE,REDUCED COST,X1 20.000000,0.000000,X2 30.000000,0.000000,ROW SLACK OR SURPLUS DUAL PRICES,1 3360.000 1.000000,2 0.000000 48.00000,3 0.000000 2.000000,4 40.00000 0.000000,原料无剩余,时间无剩余,加工能力剩余40,max=72*x1+64*x2;,x1+x250;,12*x1+8*x2480;,3*x1100;,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVE FUNCTION VALUE,3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW SLACK OR SURPLUS,DUAL PRICES,2,0.000000,48.000000,3,0.000000,2.000000,4,40.000000,0.000000,原料增加1单位,利润增长48,时间增加1单位,利润增长2,加工能力增长不影响利润,影子价格,35,元可买到,1,桶牛奶，要买吗？,35 Options-General Solver-Dual Computations:Prices&Range 菜单：,Lingo-Range,x,1,系数范围,(64,96),x,2,系数范围(48,72),A,1,获利增加到,30,元,/,千克，应否改变生产计划,x,1,系数由24,3=72增加,为30,3=90，在,允许范围内,不变！,(约束条件不变),结果解释,OBJ COEFFICIENT RANGES,VARIABLE CURRENT ALLOWABLE ALLOWABLE,COEF INCREASE DECREASE,X1 72.000000 24.000000 8.000000,X2 64.000000 8.000000 16.000000,RIGHTHAND SIDE RANGES,ROW CURRENT ALLOWABLE ALLOWABLE,RHS INCREASE DECREASE,2 50.000000 10.000000 6.666667,3 480.000000 53.333332 80.000000,4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶!,(目标函数不变),使用Lingo的一些注意事项,“,”,与“,=”,功能相同。,变量与系数间相乘必须用”*”号，每行用”,;”,结束。,变量以字母开头，不能超过,8,个字符。,变量名不区分大小写（包括关键字）。,目标函数用,min=3*x1+2*x2,或,max=3*x1+2*x2,的格式表示。,“,!”,后为注释。,变量界定函数实现对变量取值范围的附加限制，共,4,种：,bin(x,),限制,x,为,0,或,1,bnd(L,x,U,),限制,LxU,free(x,),取消对变量,x,的默认下界为,0,的限制，即,x,可以取任意实数,gin(x,),限制,x,为整数,实验,具体题目见实验指导”Lingo求解线性规划问题.doc”。,按照实验报告的格式，特别是要有结果分析。,交作业时注意邮件主题和文件名的命名格式！,论文作业,考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会员，订购DVD租赁服务。会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次，每次获得3张DVD。会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。请考虑以下问题：,表中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单，如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即C0001C0030）分别获得哪些DVD。,现有DVD张数和当前需要处理的会员的在线订单,(见B2005.xls),DVD,编号,D001,D002,D003,D004,DVD,现有数量,15,35,15,20,会员在线订单,C0001,1,0,0,0,C0002,0,0,0,0,C0003,0,0,0,3,C0004,0,0,0,0,注：D001D100表示100种DVD,C0001C1000表示1000个会员,会员的在线订单用数字1,2,表示，数字越小表示会员的偏爱程度越高，数字0表示对应的DVD当前不在会员的在线订单中。,