规划理论及模型.ppt

《规划理论及模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、引言二、线性规划模型三、整数线性规划模型第一讲规划理论及模型四、0-1整数规划模型五、非线性规划模型六、多目标规划模型七、动态规划模型一、引言我们从2005年“高教社杯”全国大学生数模竞谈起.其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.它在运筹学中处于中心的地位.这类问题一般可以归结为数学规划模型.赛的B题“DVD在线租赁”问题的第二问和第三问最优化问题概述最优化问题的定义最优化问题的分类及处理方法最优化模型的基本要素最优化问题的定义最优化问题就是在给定条件下寻

2、找最佳方案的问题，即在资源给定时寻找最好的目标，或在目标确定时使用最少的资源。最优化问题的分类及处理方法无条件最优化问题：求导法等约束条件为等式的有约束条件的最优化问题：拉格朗日乘数法等约束条件为不等式的有约束条件的最优化问题：数学规划数学规划模型：目标规划（一个、多个）、动（静）态规划（与时间是否有关）、线性规划（整数规划、0-1规划）、非线性规划最优化（规划）模型的基本要素决策变量、目标函数和约束条件：决策变量是问题中有待确定的未知因素。目标函数是指对问题所追求的目标的数学描述。约束条件是指实现问

3、题目标的限制因素。引例某工厂在计划期内要安排生产I、II两种产品，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问应如何安排计划使该工厂获利最多？已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示12kg40原材料B16kg04原材料A8台时21设备III运用规划模型解决最优化问题的一般方法步骤如下：①前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。②定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。③针对建立的模型，选择合适的求解方

4、法或数学软件。④编写程序，利用计算机求解。⑤对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量.特别是在数模竞赛过程中，规划模型是最常见的一类数学模型.从92-06年全国大学生数模竞越多的人所重视.随着计算机的逐渐普及，它越赛试题的解题方法统计结果来看，规划模型共出现了15次，占到了50%，也就是说每两道竞

5、赛题中就有一道涉及到利用规划理论来分析、求解.二、线性规划模型线性规划模型是所有规划模型中最基本、最例1.（食谱问题）设有n种食物，各含m种营养素，第j种食物中第i中营养素的含量为aij,n种食物价格分别为c1,c2,…,cn，请确定食谱中n种食物的数量x1,x2,…,xn，要求在食谱中m种营养素简单的一种.2.1线性规划模型的标准形式的含量分别不低于b1,b2,…,bm的情况下，使得总总的费用最低.首先根据食物数量及价格可写出食谱费用为其次食谱中第i种营养素的含量为因此上述问题可表述为：解上述食谱问

6、题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的数学模型.它是指在一组线性的等式或不等式的约束条件下，例：某豆腐店用黄豆制作两种不同口感的豆腐出售。制作口感较鲜嫩的豆腐每千克需要0.3千克一级黄豆及0.5千克二级黄豆，售价10元；制作口感较厚实的豆腐每千克需要0.4千克一级黄豆及0.2千克二级黄豆，售价5元。现小店购入9千克一级黄豆和8千克二级黄豆。问：应如何安排制作计划才能获得最大收益。一、问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制作计划，使得售

7、出各种豆腐能获得最大收益。二、模型假设1．假设制作的豆腐能全部售出。2．假设豆腐售价无波动。变量假设：设计划制作口感鲜嫩和厚实的豆腐各x1千克和x2千克，可获得收益R元。目标函数：获得的总收益最大。总收益可表示为：。。。受一级黄豆数量限制：。。。受二级黄豆数量限制：。。。综上分析，得到该问题的线性规划模型：运输问题（常见典型的线性规划问题）例2.设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C假定运费与运量成正比.在这种情况下，采用不地200吨、D地1

8、00吨.已知每吨运费如表1.1所示.同的调拨计划，运费就可能不一样.现在问：怎样才能找出一个运费最省的调拨计划？1572521甲15375151乙DCBA表1.1销地运费产地假设：①假设题目中所给运费已考虑各地间公里数；②只考虑运量和运费，不考虑车辆调拨等其它相关因素③不考虑车辆返空的费用（或：所给运费已包含车辆返空的费用）变量说明：xij:从第i城运往第j地的蔬菜数量（i=1,2,3;j=1,2,3,4）乙甲DCBA解一般的运输问题可以表述如下