《数学建模讲义线性规划模型基本模型》由会员分享，可在线阅读，更多相关《数学建模讲义线性规划模型基本模型（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的数量和 时间是与相互产量无关的常
4、数加工A1,A2的牛奶桶数是实数 线性规划模型模型求解 图解法 x1x20ABCDl1l2l3l4l5约 束 条 件目标 函数 Z=0Z=2400Z=3600z=c (常数) 等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边 形的某个顶点取得。 模型求解 软件实现 LINGO 8.0 max=72*x1+64*x2; x1+x2Solve20桶牛奶生产A1, 30桶生产A2，利润3360元。 结果解释 OBJECTIVE FUNCTION VALUE: 3360.000VARIABLE VALUE RE
5、DUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES1 3360.000 1.0000002 0.000000 48.000003 0.000000 2.0000004 40.00000 0.000000原料无剩余时间无剩余加工能力剩余40max=72*x1+64*x2; x1+x2Options-General Solver- Dual Computations: Prices ”结束。 l 变量以字母开头，不能超过8个字符。 l 变量名不区分大小写（包括关键字）。 l 目标函
6、数用min=3*x1+2*x2或max=3*x1+2*x2的格 式表示。 l “!”后为注释。 l 变量界定函数实现对变量取值范围的附加限制，共 4种： lbin(x) 限制x为0或1 lbnd(L,x,U) 限制LxU lfree(x) 取消对变量x的默认下界为0的限制，即x可 以取任意实数 lgin(x) 限制x为整数实验l具体题目见实验指导” Lingo求解线性 规划问题.doc”。 l按照实验报告的格式，特别是要有结果 分析。l交作业时注意邮件主题和文件名的命名 格式！论文作业l考虑如下的在线DVD租赁问题。顾客缴纳一定数 量的月费成为会员，订购DVD租赁服务。会员对 哪些DVD有兴趣
7、，只要在线提交订单，网站就会 通过快递的方式尽可能满足要求。会员提交的订 单包括多张DVD，这些DVD是基于其偏爱程度排 序的。网站会根据手头现有的DVD数量和会员的 订单进行分发。每个会员每个月租赁次数不得超 过2次，每次获得3张DVD。会员看完3张DVD之后 ，只需要将DVD放进网站提供的信封里寄回（邮 费由网站承担），就可以继续下次租赁。请考虑 以下问题： l表中列出了网站手上100种DVD的现有张数和当前 需要处理的1000位会员的在线订单，如何对这些 DVD进行分配，才能使会员获得最大的满意度？ 请具体列出前30位会员（即C0001C0030）分别获 得哪些DVD。 现有DVD张数和当前需要处理的会员的在线订 单 (见B2005.xls) DVD编号D001D002D003D004DVD现有数量15351520会员在 线订 单C00011000C00020000C00030003C00040000注：D001D100表示100种DVD, C0001C1000表示1000个 会员, 会员的在线订单用数字1,2,表示，数字越小表示会 员的偏爱程度越高，数字0表示对应的DVD当前不在会员 的在线订单中。
