文档介绍：二、线性规划法线性规划是运筹学的一个重要分支,它主要研究两方面的问题: 一是研究在人力、物力、财力一定的条件下, 如何合理利用这些资源取得最大利润; 二是在任务一定的条件下, 如何统筹安排, 以最小的资源消耗来完成任务。计划管理的重要任务, 就是要合理利用组织的有限资源, 取得最佳的经济效益。因此, 线性规划法可以在计划管理中广泛应用。它具体可以解决以下一些最优化问题: 资源的合理利用、生产任务的合理分配、工作的合理安排、机床负荷的合理安排、零件加工顺序的合理安排、物资运输的最优调配、原材料的合理下料、厂址的选择和工厂的合理布置等问题。(一)线性规划的运用条件运用线性规划必须具备以下基本条件: 1、有明确的目的。如追求最大利润、最低成本、最短时间等。 2、资源有限。如果可供利用的资源是无限的,则无需进行合理规划。 3、有多种可行方案。如果只有一个达到目的的方案,则无优选的必要。 4、线性相关。即各因素(变量)之间必须线性相关,可以用线性方程式表示。(二)线性规划的数学模型线性规划所要解决的问题, 就是要求一组变量在同时满足一定约束条件下使目标函数最优化。因此, 线性规划问题的数学模型一般包括目标函数和一组约束条件方程。目标函数: ?? nnxcxcxcxf????? 2211 (取最大值或最小值) 约束条件: ???????????????????????????????????????决策变量的非负要求 nix bxaxaxa bxaxaxa bxaxaxa m n mn mm nn nn,,2,10 , , , 1 2211 222 22 1 21 112 12 1 11???????(三)线性规划的应用步骤第一步: 建立线性规划模型。即根据所提出的问题和希望达到的目的, 建立目标函数; 根据所给出的限制条件, 建立约束条件方程组。例: 设某企业生产 A、 B 两种产品, A 产品每件可获利润 70元, B 产品每年可获利润 120 元。两种产品都要用甲、乙、丙三种原材料, 各产品的材料消耗定额及原材料下月的可供量如表 3— 2 所列。试决定下月的生产计划,使其利润最大。 A、 B 产品原材料消耗定额表表 3— 2 产品材料材料消耗定额(公斤/ 件) 下月材料可供量(公斤) AB 甲 94 3,600 乙 45 2,000 丙 3 10 3,000 解:设 X 1, X 2 分别为 A、 B 产品下月的计划产量(决策变量), S 为利润额。依题意,其线性规划数学模型如下: 目标函数: 21 120 70xxS??约束条件: ??????????????0, 3000 10 3 2000 54 3600 49 21 21 21 21xx xx xx xx 第二步: 求解。即找出在同时满足约束条件下使目标函数( 利润) 最大的计划方案。此处可用图解法求解。首先,以 X 1 为横轴, X 2 为纵轴,根据约束条件方程在平面直角坐标系中作出图形(见图 3— 5) ,找出可行解区域。 X 2 1,000 0 800 400 200 200X 1 1000 400 600 800D C B 9X 1 +4X 2 =3,600 4X 1 +5X 2 =2,000 3X 1 +10X 2 =3,000 A图 3— 5 从图中可以看出, 各直线所围成的凸多边形 OABCD 就是该问题的可行解区域。其次, 从可行解区域中找出最优解。办法可采用枚举法, 将凸集各顶点的坐标值分别代入目标函数求值, 进行比较, 取最大值。目标函数最大值所对应的变量值即为所求。在本例中,利用约束条件方程组,很容易求出各顶点的坐标值: O( 0, 0), A( 0, 300 ), B( 200 , 240 ), C( 345 , 124 ), D( 400 , 0) 分别代入目标函数方程求值得: S 0 =0 S A =70 × 0+120 × 300=3600 S B =70 × 200+120 × 240=42800 S C =70 × 345+120 × 124=39030 S D =70 × 400 × +120 × 0=28000 比较得知:在 B 点的目标函数值最大, 即当 X 1 =200 , X 2 =240 时, 利润最大。所以,下月应安排生产 A 产品 200 件, B 产品 240 件。用图解法求解比较简单,但只适用于含两个决策变量的问题。要解决含多个变量的问题,应采用“单纯形法”,限于篇幅,此处不作介绍。计划工作的一个重要步骤是综合平衡, 其中包括处理好计划与各种资源限制间的协调。线性规划法正是进行综合平衡, 并由此选择优化方案,而在实践中常用的一种计划工具。三、网络计划法(一)网络计划法的含义和适用范围网络计划法是指以网络图的形式反映和表达计