管理运筹学(第二章 线性规划的图解法).ppt

管理运筹学 孙 树 垒 第二章 线性规划的图解法 线性规划 Linear Programming 简称LP 是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。 非线性规划Nonlinear Programming 简称NLP 线性规划通常用来解决有限资源的最佳分配问题 求解方法： 图解法 单纯形法 第二章 线性规划的图解法 线性规划在管理中一些典型的应用 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小 第二章 线性规划的图解法 线性规划问题的一些共同特点 都有要求达到某些数量上的最大化或最小化的目标 所有线性规划问题都是在一定的约束条件下来追求其目标的 第二章 线性规划的图解法 §2.1　问题的提出 §2.1　问题的提出 第二章 线性规划的图解法 决策变量（X） 决策问题待定的量值称为决策变量。 决策变量的取值要求非负。 目标函数（ Max F 或 Min F ） 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。 目标函数是决策变量的线性函数。 有的目标要实现极大，有的则要求极小。 约束条件 （s.t. (subject to) 满足于） 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。 约束条件是决策方案可行的保障。 LP的约束条件，都是决策变量的线性函数。 §2.1　问题的提出 建模过程 1.明确问题：理解要解决的问题，了解解题的目标和条件； 2.定义决策变量：定义决策变量（ x1 ，x2 ，… ，xn ），每一组值表示一个方案； 3.确定目标函数：用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； 4.确定约束条件：用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 一般形式 目标函数： Max （Min） z = c1 x1 + c2 x2 + … + cn xn 约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 §2.1　问题的提出 线性规划有关解的几个概念 1. 可行解：满足约束条件的一组决策变量的取值； 2. 可行域：可行解所构成的集合； 3. 最优解：使目标函数达到极值的可行解； 4. 最优值：与最优解相对应的目标函数的取值。 §2.2　图解法 图解法的局限性 只能求解具有两个决策变量的线性规划问题 学习图解法的目的 图解法只能求解具有两个决策变量的线性规划问题，其应用具有很大的局限性，但是学习图解法的目的并非只是要掌握一种线性规划问题的求解方法，而是要通过图解法揭示线性规划问题的内在规律，为学习线性规划问题的一般算法（单纯形法）奠定基础。 §2.2　图解法 图解法的基本步骤 1.画出平面直角坐标系； 2.将约束条件逐一反映进平面直角坐标系，用标号和箭线表明约束条件的顺序和不等号的方向； 3.找出可行域并反映出目标函数直线的斜率； 4.平移目标函数直线找出最优解。 §2.2　图解法 例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0