数学建模讲义线性规划模型1基本模型.ppt

《数学建模讲义线性规划模型1基本模型.ppt》由会员分享，可在线阅读，更多相关《数学建模讲义线性规划模型1基本模型.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模讲义第4章 线性规划模型-基本模型1 优化模型l优化：在一定条件下，使目标最大的决策。l优化问题是经常遇到的问题，如：结构设计，资源分配，生产计划，运输方案等。l全国大学生数模竞赛题一半以上与优化有关，并且需用软件求解。无约束优化l给定一个函数f(x)，寻找x使得f(x)最小，其中x=(x1,x2,xn)。l最优值出现在定义区间端点，不可导点，稳定点。有约束优化l如果f(x)和hi(x)可导，则可以用拉格朗日方法化为无约束优化问题：规划问题l 最优解在定义域的边界上达到。l 线性规划：目标和约束均为线性函数。l 非线性规划：目标和约束存在非线性函数。二次规划：目标为二次函数，约束为线性

2、l 整数规划：决策变量为整数。0-1规划：决策变量只为0或者是11桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到 30元/公斤，应否改变生产计划？每天：例：加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加

3、工能力 决策变量 目标函数 每天获利约束条件非负约束 线性规划模型(LP)时间480小时 至多加工100公斤A1 50桶牛奶 每天模型分析与假设 比例性 可加性 连续性 xi对目标函数的“贡献”与xi取值成正比 xi对约束条件的“贡献”与xi取值成正比 xi对目标函数的“贡献”与xj取值无关 xi对约束条件的“贡献”与xj取值无关 xi取值连续 A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数 线性规划模型模型

4、求解 图解法 x1x20ABCDl1l2l3l4l5约束条件目标函数 Z=0Z=2400Z=3600z=c(常数)等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边形的某个顶点取得。模型求解 软件实现 LINGO 8.0 max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1Solve20桶牛奶生产A1,30桶生产A2，利润3360元。结果解释 OBJECTIVE FUNCTION V ALUE:3360.000 V ARIABLE V ALUE REDUCED COST X

5、1 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原料无剩余时间无剩余加工能力剩余40max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释 OBJECTIVE FUNCTION V ALUE 3360.000 V ARIABLE V ALUE

6、 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 48,应该买！聘用临时工人付出的工资最多每小时几元？2元！OBJ COEFFICIENT RANGES V ARIABLE CURRENT ALLOWABLE ALLOW

7、ABLE 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最优解不变时目标函数系数允许变化范围 菜单：Lingo-Options-G

8、eneral Solver-Dual Computations:Prices&Range 菜单：Lingo-Range x1系数范围(64,96)x2系数范围(48,72)A1获利增加到 30元/千克，应否改变生产计划 x1系数由24 3=72增加为303=90，在允许范围内 不变！(约束条件不变)结果解释 OBJ COEFFICIENT RANGES V ARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.0000

9、00 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的一些注意事项1.“”与“=”功能相同。2.变量与系数间相乘必须用”*”号，每行用”;”结束。

10、3.变量以字母开头，不能超过8个字符。4.变量名不区分大小写（包括关键字）。5.目标函数用min=3*x1+2*x2或max=3*x1+2*x2的格式表示。6.“!”后为注释。7.变量界定函数实现对变量取值范围的附加限制，共4种：l bin(x)限制x为0或1l bnd(L,x,U)限制LxUl free(x)取消对变量x的默认下界为0的限制，即x可以取任意实数l gin(x)限制x为整数实验l具体题目见实验指导”Lingo求解线性规划问题.doc”。l按照实验报告的格式，特别是要有结果分析。l交作业时注意邮件主题和文件名的命名格式！论文作业l 考虑如下的在线DVD租赁问题。顾客缴纳一定数量的

11、月费成为会员，订购DVD租赁服务。会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次，每次获得3张DVD。会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。请考虑以下问题：l 表中列出了网站手上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当前不在会员的在线订单中。