运筹学 一般线性规划问题的数学模型.ppt

问题转化为： max Z′= x′1 -2 x2 -3 x′3+3x′′3 +0 x4 +0 x5 s. t. 2 x′1 + x2 + x′3- x′′3 +x4 =9 3 x′1 + x2+2 x′3-2 x′′3 -x5=4 3 x′1 +2x2 +3 x′3-3 x′′3 = 6 x′1 ,x2 , x′3, x′′3 , x4 , x5 ≥ 0? 练习1.6（a） 解：首先令z′=-z， x2 = x′2- x′′2，其中x′2 ≥ 0,x′′2 ≥0， x′3 =－x3，其中x′3 ≥ 0， 考虑约束，引进松弛变量x4 ≥0 、剩余变量x5 ≥0 问题转化为： 六、线性规划问题的解 对于线性规划问题 max CTX （1.1a） (LP) s.t. AX ≤ b（1.1b） X≥0 （1.1c） 其中,C , X ?Rn,b ?Rm,A m?n 矩阵 有以下几个概念（单纯形法中详细介绍）： 1.可行解(feasible solution ) 满足(1.1b)(1.1c)X =( x1,x2,…..,xn)T称为线性规划问题(LP)的可行解。全部可行解的集合称为可行域。 2.最优解(optimal solution) 使目标函数(1.1a)达到最大值的可行解成为最优解。 3.基 设nm,A的秩为m。B是矩阵A中的一个m?m阶的满秩矩阵，称B是线性规划问题的一个基。不失一般性，设 =(P1,··· ,Pm),B中的 每一个列向量Pj(j=1, ··· m)称为基向量，与 基向量Pj对应的变量xj称为基变量。线性规划 除基变量以外的其他变量称为非基变量。 4.基解在约束方程组(1.1b)中，令所有非基变量xm+1= xm+2= ··· xn = 0，又因为有|B|#0，根据克莱姆法则，由m个约束方程可解出m个基变量的唯一XB=( x1,x2,…..,xm)T。 将这个解加上非基变量取0的值有 X =( x1,x2,… xm,0 …,0)T，称X 为线性规划的基解。基解的总数不超过 。 5.基可行解 满足非负约束(1.1c)的基解称为基可行解。 6.可行基 对应于基可行解的基称为可行基。 例1.7 B=（ P3，P4， P5 ，P6）满秩为一个基 基向量： P3，P4， P5 ，P6 非基向量： P1，P2 基变量： x3，x4， x5 ，x6 非基变量： x1，x2 令x1=x2=0，得基解（0，0，12，8，16，12）T 基可行解：满足非负约束的基解 可行基：对应于基可行解的基 例中基解（0，0，12，8，16，12）T ，所有变量取值为非负， 所以它又是基可行解 相应的，B=（ P3，P4， P5 ，P6）为可行基 七、线性规划解之间的关系 ◆可行解与最优解—— 最优解一定是可行解，但可行解不一定是最优解 ◆可行解与基解—— 基解不一定是可行解，可行解也不一定是基解 ◆可行解与基可行解—— 基可行解一定是可行解，可行解不一定是基解 ◆最优解与基解—— 最优解不一定是基解，基解也不一定是最优解 可行解 基解 基最优解 基可行解 2010年8月 管理工程学院 《运筹学》 * 运 筹 帷 幄 之 中 决 胜 千 里 之 外 线 性 规 划 Linear Programming 第一章 线性规划及单纯形法 一般线性规划问题的数学模型 图解法 单纯形法原理 单纯形法的计算步骤 单纯形法的进一步讨论 应用举例 第一节 一般线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的标准型及其标准化 线性规划问题解的含义 一、线性规划的发展 1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题 1947年，Dantzig提出求解线性规划的单纯形法 1950-1956年，主要研究线性规划的对偶理论 1958年，发表整数规划的割平面法 1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。 1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多项式算法。 另外，很多现代