运筹学线性规划1.pptx

第一章 线性规划与单纯形法年G.B.Dantzig 提出单纯形法第一节 线性规划问题及其数学模型问题的提出:在生产管理和经营活动中经常提出一类问题，即如何合理的利用有限的人力、物力、财力等资源，以便得到最好的经济效果。上海交通大学安泰管理学院 2007 例1 某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所式。 该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问应如何安排计划使该工厂获利最多？上海交通大学安泰管理学院 2007上海交通大学安泰管理学院 20072工作人员安排问题联邦航空公司上海交通大学安泰管理学院 2007 以上例子可以看出，他们都是一类优化问题。它们的共同特征： (1)每一个问题都用一组决策变量 表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。上海交通大学安泰管理学院 2007 (2) 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 (3) 都有一个要求达到的目标，它可用决策的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。上海交通大学安泰管理学院 2007 满足以上三个条件的数学模型成为线性规划的数学模型。其一般形式为： 上海交通大学安泰管理学院 2007上海交通大学安泰管理学院 2007 在线性规划的数学模型中，方程（1.1）称为目标函数；（1.2）（1.3）成为约束条件；（1.3）也称为变量的非负约束条件。上海交通大学安泰管理学院 2007 线性规划的图解法上海交通大学安泰管理学院 2007上海交通大学安泰管理学院 2007上海交通大学安泰管理学院 2007线性规划的解上海交通大学安泰管理学院 2007唯一解无穷多解无可行解无界解Max Z =x1+x2-2x1+x2=4X1-x2=2X1=0,x2=0 线性规划问题的几个特点：线性规划问题的可性解的集合是凸集线性规划问题的基础可行解一般都对应于凸集的极点凸集的极点的个数是有限的最优解只可能在凸集的极点上，而不可能发生在凸集的内部上海交通大学安泰管理学院 20071.2.1 线性规划问题的标准形式maxZ= 上海交通大学安泰管理学院 2007标准型向量形式矩阵形式上海交通大学安泰管理学院 2007 变换的方法：目标函数为min型，价值系数一律反号。令 f?(x) = -f(x) = -CX, 有 min f(x) = - max [- f(x)] = - max f ?(x)第i 个约束的bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向第i 个约束为 ? 型，在不等式左边增加一个非负的变量xn+i ，称为松弛变量；同时令 cn+i = 0第i 个约束为 ? 型，在不等式左边减去一个非负的变量xn+i ，称为剩余变量；同时令 cn+i = 0若xj ?0，令 xj= -xj? ，代入非标准型，则有xj? ? 0若xj ?不限，令 xj= xj? - xj?， xj? ? 0，xj? ? 0，代入非标准型上海交通大学安泰管理学院 2007 变换举例：上海交通大学安泰管理学院 2007线性规划标准型解的若干基本概念：标准型有 n+m 个变量， m 个约束行“基”的概念在标准型中，技术系数矩阵有 n+m 列，即 A = ( P1, P2 , … , Pn+m )A中线性独立的 m 列，构成该标准型的一个基，即 B = ( P1?, P2 ? , … , Pm ? )， | B | ? 0 P1 ?, P2 ?, … , Pm ? 称为基向量与基向量对应的变量称为基变量，记为 XB = ( x1 ?, x2 ? , … , xm ? )T，其余的变量称为非基变量，记为 XN = ( xm+1 ?, xm+2 ?, … , xm+n ? ) T ，有 X = XB + XN最多有 个基上海交通大学安泰管理学院 2007 关于标准型解的若干基本概念：可行解满足约束条件和非负条件的解 X 称为可行解，基础解令非基变量 XN = 0，求得基变量 XB的值称为基础解 即 XB = B-1 bXB 是基础解的必要条件为XB 的非零分量个数 ? m基础可行解基础解 XB 的非零分量都 ? 0 时，称为基础可行解，否则为基础非可行解基础可行解的非零分量个数 m 时，称为退化解上海交通大学安泰管理学院 2007 线性规划标准型问题解的关系约束方程的解空间非可行解基础可行解基础解可行解退化解上海交通大学安泰管理学院 2007线性规划几何意义凸集凸组合顶点上海交