数学建模:第五章 运筹与优化模型
- 格式:ppt
- 大小:2.76 MB
- 文档页数:162
数学建模论文题目:送货问题学院(直属系):数学与计算机学院年级、专业:2010级信息与计算科学姓名:杨尚安刘洋谭笑指导教师:蒲俊完成时间:2012年3月20日摘要本文讨论的是货运公司的运输问题,根据各公司需求和运输路线图,建立了线性规划模型和0-1规划模型,对货运公司的出车安排进行了分析和优化,得出运费最小的调度方案。
对于问题一,由于车辆在途中不能掉头,出车成本固定,要使得总成本最小,即要使在一定的车辆数下,既满足各公司的需求,又要尽量减小出车次数。
故以最小出车数为目标函数,建立线性规划模型,并通过lingo求解,得出最小出车数27次。
接着考虑车的方向问题,出车分为顺时针和逆时针,建立0-1模型,并求解,得出满足问题一的调度方案(见附录表1)。
对于问题二,车辆允许掉头,加上车辆装载货物和空装时运输费不同,,要使总成本最小,故可以通过修改原目标函数,建立线性规划模型和0-1规划模型,求解,得出最佳派出车辆3辆并列出满足问题二的调度方案。
对于问题三第一小问,增加了运输车辆的类型。
即装载材料的方法很多,在上述分析的基础上,通过增加约束条件,建立新的线性规划模型,并求解,得出满足问题三的调度方案。
在第二小问中,由于给出部分公司有道路相通,可采用运筹学中的最短路问题的解决方法加以解决。
关键字:线性规划模型0-1规划模型调度一、问题重述某地区有8个公司(如图一编号①至⑧),某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。
路线是唯一的双向道路(如图1)。
货运公司现有一种载重6吨的运输车,派车有固定成本20元/辆,从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。
每辆车平均需要用15分钟的时间装车,到每个公司卸车时间平均为10分钟,运输车平均速度为60公里/小时(不考虑塞车现象),每日工作不超过8小时。
运输车载重运费1.8元/吨公里,运输车空载费用0.4元/公里。
第五章 目标规划§5.1重点、难点提要一、目标规划的基本概念与模型特征 (1)目标规划的基本概念。
当人们在实践中遇到一些矛盾的目标,由于资源稀缺和其它原因,这些目标可能无法同时达到,可以把任何起作用的约束都称为“目标”。
无论它们是否达到,总的目的是要给出一个最优的结果,使之尽可能接近制定的目标。
目标规划是处理多目标的一种重要方法,人们把目标按重要性分成不同的优先等级,并对同一个优先等级中的不同目标赋权,使其在许多领域都有广泛应用。
在目标规划中至少有两个不同的目标;有两类变量:决策变量和偏差变量;两类约束:资源约束(也称硬约束)和目标约束(也称软约束)。
(2)模型特征。
目标规划的一般模型:⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=≥==-+=≤⎪⎭⎫ ⎝⎛+=+-=+-===++--∑∑∑∑.,,2,1;0,;,,2,10,,2,1,,2,1..)(min 1111K k d d n j x K k g d d x c m i b x a t s d d P Z k k j n j k k k j kj i nj j ij Lr K k k rk k rk r ωω 其中r P 为目标优先因子,+-rk rk ωω,为目标权系数,+-k k d d ,为偏差变量。
1)正、负偏差变量,i i d d +-。
正偏差变量i d +表示决策值超过目标值的部分;负偏差变量i d -表示决策值未达到目标值的部分。
因为决策值不可能既超过目标值同时又未达到目标值,所以有0i i d d +-⨯=。
2)硬约束和软约束。
硬约束是指必须严格满足的等式约束和不等式约束;软约束是目标规划特有的。
我们可以把约束右端项看成是要努力追求的目标值,但允许发生正、负偏差,通过在约束中加入正、负偏差变量来表示努力的结果与目标的差距,于是称它们为目标约束。
3)优先因子与权系数。
一个规划问题通常有若干个目标,但决策者在要求达到这些目标时,是有主次或缓急之分的。
运筹学第五章课后习题答案运筹学第五章课后习题答案运筹学是一门研究如何进行有效决策和优化问题的学科。
在运筹学的学习过程中,课后习题是非常重要的一部分,通过解答习题可以帮助我们巩固所学的知识,并且加深对运筹学理论的理解。
本文将给出运筹学第五章的课后习题答案,希望对大家的学习有所帮助。
1. 线性规划问题是运筹学中最基本的问题之一。
以下是一道线性规划问题的习题:Maximize 2x + 3ySubject to:x + y ≤ 102x + y ≤ 15x, y ≥ 0解答:首先,我们需要将目标函数和约束条件转化为标准形式。
将目标函数改写为最小化形式,即 Minimize -2x - 3y。
然后,我们引入松弛变量,将不等式约束转化为等式约束,得到以下形式的线性规划问题:Minimize -2x - 3ySubject to:x + y + s1 = 102x + y + s2 = 15x, y, s1, s2 ≥ 0接下来,我们可以使用单纯形法或者图解法来求解这个线性规划问题。
通过计算或者画图,我们可以得到最优解为 x = 5, y = 5,目标函数的最大值为 25。
2. 整数规划是线性规划的一种扩展形式,其中变量的取值限制为整数。
以下是一道整数规划问题的习题:Maximize 3x + 2ySubject to:x + y ≤ 5x, y ≥ 0x, y 是整数解答:这是一个整数规划问题,我们需要找到满足约束条件的整数解,并求解出目标函数的最大值。
通过穷举法,我们可以得到以下整数解:当 x = 2, y = 3 时,目标函数的值为 13;当 x = 3, y = 2 时,目标函数的值为 12;当 x = 4, y = 1 时,目标函数的值为 11;当 x = 5, y = 0 时,目标函数的值为 10。
综上所述,目标函数的最大值为 13,对应的整数解为 x = 2, y = 3。
3. 0-1整数规划是整数规划的一种特殊形式,其中变量的取值限制为0或1。