线性规划与目标规划方法ppt课件.ppt

《线性规划与目标规划方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章运筹决策分析方法线性规划与目标规划方法投入产出分析方法随机型决策分析方法AHP决策分析方法线性规划方法目标规划方法应用实例:农场种植计划模型第1节线性规划与目标规划方法线性规划是运筹学中发展较快、应用较广和比较成熟的一个分支。它在实际应用中日益广泛与深入,已经被广泛地应用到工业、农业、商业与交通运输规划，工程技术的优化设计，以及企业管理等各个领域。在地理学领域，线性规划，作为传统的计量地理学方法之一，是解决有关规划、决策和系统优化问题的重要手段。一、线性规划方法（一）线性规划模型线性规划之实例线性规划研究的两类问题：某项任务确定后，如何统筹安排，

2、以最少的人力、物力和财力去完成该项任务；面对一定数量的人力、物力和财力资源，如何安排使用，使得完成的任务最多。它们都属于最优规划的范畴。以下为一些实例。运输问题假设某种物资（譬如煤炭、钢铁、石油等）有m个产地，n个销地。第i产地的产量为ai（i=1，2，…，m），第j销地的需求量为bj(j=1,2，…，n)，它们满足产销平衡条件如果产地i到销地j的单位物资的运费为Cij，要使总运费达到最小，可这样安排物资的调运计划：设xij表示由产地i供给销地j的物资数量，则上述问题可以表述为：求一组实值变量xij(i=1，2，…，m；j=1，2，…，n)，使其满足

3、而且使资源利用问题假设某地区拥有m种资源，其中，第i种资源在规划期内的限额为bi(i=1，2，…，m)。这m种资源可用来生产n种产品，其中，生产单位数量的第j种产品需要消耗的第i种资源的数量为aij(i=1，2，…，m；j=1,2,…,n)，第j种产品的单价为cj(j=1，2，…，n)。试问如何安排这几种产品的生产计划，才能使规划期内资源利用的总产值达到最大?设第j种产品的生产数量为xj(j=1，2，…，n)，则上述资源问题就是：求一组实数变量xj(j=1，2，…，n)，使其满足线性规划的数学模型以上例子表明，线性规划问题具有以下特征：①每一个问题都用

4、一组未知变量（x1，x2，…，xn）表示某一规划方案，其一组定值代表一个具体的方案，而且通常要求这些未知变量的取值是非负的。②每一个问题的组成部分：一是目标函数，按照研究问题的不同，常常要求目标函数取最大或最小值；二是约束条件，它定义了一种求解范围，使问题的解必须在这一范围之内。③每一个问题的目标函数和约束条件都是线性的。由此可以抽象出线性规划问题的数学模型，一般形式为：在线性约束条件以及非负约束条件xj≥0（j=1，2，…，n）下，求一组未知变量xj(j=1，2，…，n)的值，使采用矩阵形式可描述为：在约束条件AX≤(≥，＝)b及X≥0下，求未知向量

5、的值，使得Z=CX→max(min)其中（二）线性规划的标准形式线性规划的标准形式在讨论与计算时，需要将线性规划问题的数学模型转化为标准形式，即在约束条件xj≥0（j=1，2，…，n）下，求一组未知变量xj（j=1，2，…，n）的值，使其缩写形式为：在约束条件x≥0（j=1，2，…，n）下，求一组未知变量（j=1，2，…，n）的值，使得常记为如下更为紧凑的形式或（二）化为标准形式的方法具体的线性规划问题，需要对目标函数或约束条件进行转换，化为标准形式。目标函数化为标准形式的方法如果其线性规划问题的目标函数为minZ=CX显然有minZ=max(-Z)=

6、maxZ′则目标函数的标准形式为maxZˊ=-CX约束方程化为标准形式的方法若第k个约束方程为不等式，即引入松弛变量,K个方程改写为则目标函数标准形式为（三）线性规划的解及其性质线性规划的解可行解与最优解满足约束条件（即满足线性约束和非负约束）的一组变量为可行解。所有可行解组成的集合称为可行域。使目标函数最大或最小化的可行解称为最优解。基本解与基本可行解在线性规划问题中，将约束方程组的m×n阶矩阵A写成由n个列向量组成的分块矩阵如果B是A中的一个阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设则称为基向量，与基向量相对应的向量为基变量

7、，而其余的变量为非基变量。如果是方程组的解,则就是方程组AX=b的一个解，它称之为对应于基B的基本解，简称基解。满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。线性规划问题的以上几个解的关系，可用下图来描述：线性规划解的性质凸集和顶点①凸集：若连接n维点集S中的任意两点X(1)和X(2)之间的线段仍在S中，则S为凸集。②顶点：若凸集S中的点X(0)不能成为S中任何线段的内点，则称X(0)为S的顶点或极点。线性规划解的性质①线性规划问题的可行解集（可行域）为凸集。②可行解集S中的点X是顶点的充要条件是基本可行解。③若可行解集有

8、界，则线性规划问题的最优值一定可以在其顶点上达到。因此线性规划的最优解只需从其可行解集的有限个