运筹学教学课件 线性规划学习课件ppt.ppt

《运筹学教学课件 线性规划学习课件ppt.ppt》由会员分享，可在线阅读，更多相关《运筹学教学课件 线性规划学习课件ppt.ppt（61页珍藏版）》请在三一办公上搜索。

1、线 性 规 划Linear Programing,运筹学,基本内容,线性规划的基本性质及其图解法单纯形法对偶问题灵敏度分析,第一章 线性规划的基本性质,线性规划问题及模型二维线性规划的求解：图解法线性规划的标准形式线性规划问题解及其性质,线性规划研究问题,主要研究解决有限资源的最佳分配问题，即如何对有限资源作出最佳方式的调配和最有力地使用，以便最充分地发挥资源的效能，以获取最佳的经济效益。生产计划问题运输问题配料问题下料问题食谱问题产品配套问题,(1)生产计划问题,应如何安排生产这两种产品才能获利最多？,问题分析,数学模型为,(2)运输问题,设两个粮库供应三个粮店，供应量、需求量和运费如下表所

2、示，问如何安排运输计划，可使总运费最少？建立数学模型,问 题 分 析,数学模型,(3)配料问题,某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有A、B、C三种化学成分，其含量以及产品中各成分含量的最低量如下表所示。甲、乙两种原料成本见下表。厂方希望总成本大到最小，则应如何配制该产品。,问题分析,数学模型,线性规划问题的特点,1、（非负的）决策变量2、求极值的目标函数3、线性的约束条件,一般模型,线性规划的图解,max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20,可行域,目标函数等值线,最优点（最优解）,6,4,-8,6,

3、0,x1,x2,图解法的步骤,可行域图形地确定所有约束条件共同构成的图形成为可行域可行域所有点（包括边界）均是可行解目标函数的等值线与最优点的确定令Z取不同值，得到一组平行的等值线沿目标函数值增大的方向移动等值线，当韩淑芝最大时与可行域的交点即为最优点。最优点的求解在图上观测最优点的坐标通过解方程组得出最优点坐标值,可行域的几种情况,无界域 x1+2x2 4 s.t.x1-2x2 5 x1,x2 0,1,4,2,3,5,1,2,3,x1,x2,x1+2x2 4,x1-2x2 5,可行域的几种情况,有界域,2,8,4,6,10,2,4,10,x1,3x1+4x2 36,x1 8,12,6,8,2

4、x2 12,可行域的几种情况,空集s.t.x1+2x2 4 x1-2x2 5 x1,x2 0,1,4,2,3,5,1,2,3,x1,x2,x1+2x2 4,x1-2x2 5,最优点的几种情况,唯一解多重解无界解无可行解,线性规划的多重解,max z=x1+x2s.t.x1+x26-x1+2x28x1 0,x20,可行域,目标函数等值线,最优点（最优解）,6,4,-8,6,0,x1,x2,max z=2x1+x2s.t.x1+x2 2 x1-2x2 0 x1,x2 0,线性规划无界解,1,4,2,3,5,1,2,3,x1,x2,x1+x2 2,z=2x1+x2,x1-2x2 0,无可行解,Max

5、 z=x1+x2s.t.x1+2x2 4 x1-2x2 5 x1,x2 0,1,4,2,3,5,1,2,3,x1,x2,x1+2x2 4,x1-2x2 5,Z=x1+x2,线性规划的标准形式,线性规划标准型的简写形式,求和符号形式,线性规划标准型的简写形式,向量形式,线性规划标准型的简写形式,矩阵形式,线性规划标准型的简写形式,集合形式,线性规划的模型,线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,unr,0线性规划的标准形式目标函数：max约束条件：=变量符号：0,非标准形LP问题的标准化例题,非标准形LP问题的标准化,目标函数最小化 最大化：z=-z不等式约束 等

6、式约束变量为负约束、无符号约束 非负约束右端常数小于零 非负等式两边均乘-1,松弛变量,剩余变量,线性规划问题的解及其性质,1.线性规划的解2.线性规划的基与基本可行解3.线性规划的基本定理,线性规划解的定义,(1)满足线性规划问题所有约束条件的解是该问题的可行解。X=(X1,X2,XN)T(2)线性规划问题全部可行解的集合构成线性规划问题的可行域（或称可行解集）。R=x Ax=b,x 0(3)使目标函数达到极值的可行解称为线性规划问题的最优解。(4)若对任意大的 M 0，都存在可行解使得该线性规划的目标函数值 z=cx M,则该线性规划问题无界。,线性规划的基与基本可行解,基的定义：给定线性

7、规划问题 P：max c x|Ax=b,x 0 A是 mn 满秩矩阵,n m，如果 B 是其中任 一个 m m 满秩子矩阵，则称 B 是 P 的一个基。,基变量与非基变量假定 B 由 A 中前 m 个列向量构成，约束矩阵可划分为：A=(B,N)与基 B 对应的变量称为基变量，用 xB 表示；与非基 N 对应的变量称为非基变量，用 xN 表示。,基本解,基 本 可 行 解,满足非负条件的基本解为基本可行解，该解对应的基 B 为可行基。如果基本可行解X0则称该基本可行解为非退化解。,非基变量为零，满足函数约束条件的解为基本解。,考虑线性规划模型范例标准形 Max z=3 x1+5 x2 s.t.x

8、1+x3=8 x2+x4=12 3x1+4x2+x5=36 x1,x2,x3,x4,x5 0 注意，线性规划的基本解、基本可行解（极点）和可行基只与线性规划问题标准形式的约束条件有关。,A=P1,P2,P3,P4,P5=A矩阵包含以下10个33的子矩阵：B1=p1，p2，p3 B2=p1，p2，p4 B3=p1，p2，p5 B4=p1，p3，p4 B5=p1，p3，p5 B6=p1，p4，p5 B7=p2，p3，p4 B8=p2，p3，p5 B9=p2，p4，p5 B10=p3，p4，p5,由于B5、B9的行列式的值为0，不是基变量。非基变量为0，得到对应基B的解。如下 x(1)=(4,6,4

9、,0,0)T（对应B1）x(2)=(8,3,0,6,0)T（对应B2）x(3)=(8,6,0,0,-12)T（对应B3）x(4)=(12,0,-4,12,0)T(对应B4）x(6)=(8,0,0,12,3)T（对应B6）x(7)=(0,9,8,-6,0)T（对应B7）x(8)=(0,6,8,0,12)T（对应B8）x(10)=(0,0,8,12,36)T（对应B10）是基本解。,2,8,4,6,10,2,4,10,x1,x1 8,12,6,8,X1,X7,X8,X3,X10,X6,X2,X4,可行解,基本可行解,基本解,3.线性规划解的基本性质,定义1：设 x1,.,xk 是n维欧氏空间中的

10、k 个点，若存在 1,.,k，且满足 0 i 1,i=1,.,k，i=1，使得：x=1 x1+.+k xk则称 x 是 x1,.,xk 的凸组合。,定义2：集合C En 称为凸集，如果对任意 x1,x2 C,01,有x1+(1-)x2 C。,凸集没有凹陷部分，该集合内任取两点连线上的任何点都应该在集合内。,在凸集中，不能表示为不同点的凸组合的点称为凸集的极点，用严格的定义描述如下。定义3 设S为一凸集，且X S，X1 S，X2 S。对于0 1，若 X=X1+(1-)X2 则必定有X=X1=X2，则称X为S的一个极点。,可以证明，线性规划的可行域以及最优解有以下性质：（1）、若线性规划的可行域非

11、空，则可行域必定为一凸集；（2）、若线性规划的可行域非空，则至多有有限个极点；（3）、若线性规划有最优解，则至少有一个极点是最优解。这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。,性质1：线性规划问题所有可行解组成的集合S=x|Ax=b,x0 是凸集。线性规划的可行域是由有限个(m个)超半空间的交集形成的。如果线性规划问题的可行域不空，是一个在n 维空间的凸多面体，这类凸集又称为多面凸集。,性质2：x 是线性规划问题基本可行解的充要条件是 x 为可行域 S=x|Ax=b,x0 的极点。这个结论被称为线性规划的基本定理，它的重要性在于

12、把可行域的极点这一几何概念与基本可行解这一代数概念联系起来。,性质3：给定线性规划 P：max cx|Ax=b,x0 A是秩为m 的 m n 矩阵。(i)若P存在可行解，则必存在基本可行解。(ii)若P存在最优解，则必存在最优基本可行解。,性质4、若线性规划问题的可行域R，则R至少有一个极点。R 可行域非空集，表明线性规划问题有可行解，则由性质3与性质2即可推出这条性质。性质5：线性规划问题可行域R的极点数目必为有限多个。基本可行解与极点一一对应阐述了可行域的极点只有有限个，并且说明可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。,几何概念,代数概念,

13、约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：凸多边形,满足一组不等式约束的解,约束直线的交点,基础解,可行域的极点,基础可行解,目标函数等值线：一组平行线,目标函数值等于一个常数的解,讨论,复习线性代数内容:列向量 x=(x1，x2，xn）T为n维列向量。xRn行向量 x=(x1，x2，xn）为n维列向量。xRn矩阵(向量)运算规则 加减乘、求逆运算 结合律 分配律 交换律 乘法无交换律线性相关 一组向量v1,vn,如果有一组不全为零的 系数1,n,使得:1 v1+nvn=0 则称v1,vn 是线性相关的.线性无关 一组向量v1,vn,如果对于任何数1,n,若要满足:1 v1+nvn=0,则必有系数 1=n=0,(全为零)则称v1,vn线性无关.矩阵A的秩 设A为一个mn阶矩阵(mn)若矩阵中最大线性 无关列向量个数为k,则称矩阵A的秩为k,记 为rank(A)=k.,本章小结,重点：线性规划的要素、图解法、解的性质、标准形及其转化难点：线性规划模型的建立作业：建立模型、图解法、标准形转化、解的判断各一道,