《运筹学教学课件 线性规划学习课件ppt》由会员分享，可在线阅读，更多相关《运筹学教学课件 线性规划学习课件ppt（61页珍藏版）》请在金锄头文库上搜索。
1、线 性 规 划Linear Programing 运筹学基本内容v线性规划的基本性质及其图解法v单纯形法v对偶问题v灵敏度分析第一章 线性规划的基本性质v线性规划问题及模型v二维线性规划的求解：图解法v线性规划的标准形式v线性规划问题解及其性质线性规划研究问题v主要研究解决有限资源的最佳分配问题，即如何对有限资源作出最佳方式的调配和最有力地使用，以便最充分地发挥资源的效能，以获取最佳的经济效益。v生产计划问题v运输问题v配料问题v下料问题v食谱问题v产品配套问题(1) 生产计划问题v应如何安排生产这两种产品才能获利最多？ 产品车间单耗（工时/件）生产能力（工时/天）甲乙A108B0212C34
2、36利润（百元/件）35问题分析数学模型为(2) 运输问题v设两个粮库供应三个粮店，供应量、需求量和运费如下表所示，问如何安排运输计划，可使总运费最少？建立数学模型 粮店 单价（百元）粮库B1B2B3供应量（吨）A118252028A221222429需求量（吨）121530问问 题题 分分 析析数学模型数学模型(3) 配料问题v某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有A、B、C三种化学成分，其含量以及产品中各成分含量的最低量如下表所示。甲、乙两种原料成本见下表。厂方希望总成本大到最小，则应如何配制该产品。 原料成分成份含量（%）产品成分
3、最低含量（%）甲乙A1234B232C3155成本(元/千克)32问题分析数学模型线性规划问题的特点1、（非负的）决策变量2、求极值的目标函数3、线性的约束条件一般模型线性规划的图解max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域目标函数等值线最优点（最优解）64-860x1x2图解法的步骤v可行域图形地确定所有约束条件共同构成的图形成为可行域可行域所有点（包括边界）均是可行解v目标函数的等值线与最优点的确定令Z取不同值，得到一组平行的等值线沿目标函数值增大的方向移动等值线，当韩淑芝最大时与可行域的交点即为最优点。v最优点的求解在图上观测最优点的坐标通过
4、解方程组得出最优点坐标值可行域的几种情况v无界域 x1 + 2x2 4 s.t. x1 - 2x2 5 x1, x2 014235123x1 x2x1 + 2x2 4x1 - 2x2 5可行域的几种情况v有界域2846102410x1 3x1 + 4x2 36x1 812 682x2 12可行域的几种情况v空集s.t. x1 + 2x2 4 x1 - 2x2 5 x1, x2 014235123x1 x2x1 + 2x2 4x1 - 2x2 5最优点的几种情况v唯一解v多重解v无界解v无可行解线性规划的多重解max z=x1+x2s.t. x1+ x26-x1+2x28x1 0, x20可行域
5、目标函数等值线最优点（最优解）64-860x1x2 max z = 2x1 + x2s.t. x1 + x2 2 x1 - 2x2 0 x1 , x2 0线性规划无界解14235123x1 x2x1 + x2 2z = 2x1+x2x1 - 2x2 0无可行解vMax z=x1+x2vs.t. x1 + 2x2 4 x1 - 2x2 5 x1, x2 014235123x1 x2x1 + 2x2 4x1 - 2x2 5Z=x1+x2线性规划的标准形式线性规划标准型的简写形式v求和符号形式线性规划标准型的简写形式v向量形式线性规划标准型的简写形式v矩阵形式线性规划标准型的简写形式v集合形式线性规
6、划的模型v线性规划模型的结构v目标函数 ：max，minv约束条件：,=,v变量符号：0, unr, 0v线性规划的标准形式v目标函数：maxv约束条件：=v变量符号：0非标准形LP问题的标准化例题非标准形LP问题的标准化v目标函数最小化 最大化：z=-zv不等式约束 等式约束v变量为负约束、无符号约束 非负约束v右端常数小于零 非负等式两边均乘-1松弛变量剩余变量练习: 将下列线性规划问题化成标准型 1、 min Z= 5x1+ x2 + x3 3x1+ x2 - x37 - 3x1 + x2 6 s.t x1 + 2x2 4 x2-3, x1无限制,x3 02、 max Z= -x1+4
7、x2 s.t x1- 2x2+4x3-6 x2+3x3 = 3 x1 ,x20, x3无限制线性规划问题的解及其性质v1. 线性规划的解线性规划的解v2. 线性规划的基与基本可行解线性规划的基与基本可行解v3. 线性规划的基本定理线性规划的基本定理线性规划解的定义线性规划解的定义v(1) 满足线性规划问题所有约束条件的解是该问题的满足线性规划问题所有约束条件的解是该问题的可行解可行解。X=(X1,X2,XN)Tv(2)线性规划问题全部可行解的集合构成线性规划线性规划问题全部可行解的集合构成线性规划问题的问题的可行域可行域（或称可行解集）。或称可行解集）。 R = x Ax = b, x 0 v
8、(3) 使目标函数达到极值的可行解称为线性规划问题的使目标函数达到极值的可行解称为线性规划问题的最优最优解解。v(4) 若对任意大的若对任意大的 M 0，都存在可行解使得该线性规划的都存在可行解使得该线性规划的目标函数值目标函数值 z = cx M, 则该线性规划问题则该线性规划问题无界无界。线性规划的基与基本可行解线性规划的基与基本可行解基的基的定义定义：给定线性规划问题给定线性规划问题P：maxc x |Ax =b,x 0A是是m n 满满秩秩矩矩阵阵,n m，如如果果B 是是其其中中任任一一个个m m满秩子矩阵，则称满秩子矩阵，则称B是是P的一个基。的一个基。基变量与非基变量基变量与非基
9、变量假假定定B 由由A 中中前前m 个个列列向向量量构构成成，约约束束矩矩阵阵可可划分为：划分为：A=( B,N )与与基基B 对应的变量称为对应的变量称为基变量基变量，用，用xB 表示表示；与非基与非基N 对应的对应的变量称为变量称为非基变量，非基变量，用用xN 表示表示。基本解基本解基基本本可可行行解解满足非负条件的基本解为满足非负条件的基本解为基本可行解，基本可行解，该解对应的基该解对应的基 B 为为可可行基。行基。如果基本可行解如果基本可行解X0则称该基本可行解为非退化解。则称该基本可行解为非退化解。非基变量为零，满足函数约束条件的解为非基变量为零，满足函数约束条件的解为基本解基本解。
10、考虑线性规划模型范例标准形考虑线性规划模型范例标准形 Max z = 3 xMax z = 3 x1 1 + 5 x+ 5 x2 2 s.t. x s.t. x1 1 + x + x3 3 = 8 = 8 x x2 2 + x + x4 4 = 12 = 12 3x 3x1 1+ + 4x4x2 2 + x+ x5 5 = 36 = 36 x x1 1 , x, x2 2 , x, x3 3 , x , x4 4 , x, x5 5 0 0 注意，线性规划的基本解、基本可行解（极注意，线性规划的基本解、基本可行解（极点）和可行基只与线性规划问题标准形式的约束点）和可行基只与线性规划问题标准形式
11、的约束条件有关。条件有关。 A = PA = P1 1,P,P2 2,P,P3 3,P,P4 4,P,P5 5= = A A矩阵包含以下矩阵包含以下1010个个3 33 3的子矩阵：的子矩阵： B B1 1=p=p1 1，p p2 2，p p3 3 B B2 2=p=p1 1，p p2 2，p p4 4 B B3 3=p=p1 1，p p2 2，p p5 5 B B4 4=p=p1 1，p p3 3，p p4 4 B B5 5=p=p1 1，p p3 3，p p5 5 B B6 6=p=p1 1，p p4 4，p p5 5 B B7 7=p=p2 2，p p3 3，p p4 4 B B8 8=
12、p=p2 2，p p3 3，p p5 5 B B9 9=p=p2 2，p p4 4，p p5 5 B B1010=p=p3 3，p p4 4，p p5 5 由于由于B B5 5、B B9 9的行列式的值为的行列式的值为0 0，不是基变量。不是基变量。非基变量为非基变量为0 0，得到对应基，得到对应基B B的解。如下的解。如下 x x(1) (1) = (4,6,4,0,0)= (4,6,4,0,0)T T （对应（对应B B1 1） x x(2)(2) = (8,3,0,6,0) = (8,3,0,6,0)T T （对应（对应B B2 2） x x(3)(3) = (8,6,0,0,-12)
13、= (8,6,0,0,-12)T T （对应（对应B B3 3） x x(4) (4) = (12,0,-4,12,0)= (12,0,-4,12,0)T T ( (对应对应B B4 4） x x(6) (6) = (8,0,0,12,3)= (8,0,0,12,3)T T （对应（对应B B6 6） x x(7)(7) = (0,9,8,-6,0) = (0,9,8,-6,0)T T （对应（对应B B7 7） x x(8)(8) = (0,6,8,0,12) = (0,6,8,0,12)T T （对应（对应B B8 8） x x(10)(10)= (0,0,8,12,36)= (0,0,8
14、,12,36)T T （对应（对应B B1010） 是基本解。是基本解。2846102410x1 x1 812 68X1X7X8X3X10X6X2X4可行解可行解 基本基本基本基本可行解可行解可行解可行解基本解基本解3.线性规划解的基本性质线性规划解的基本性质定定义义1：设设x1,.,xk 是是n维维欧欧氏氏空空间间中中的的k 个个点点，若若存存在在 1,., k，且且满满足足0 i 1,i =1,.,k， i=1，使得使得： x = 1x1+.+ k xk则称则称x 是是x1,.,xk 的的凸组合凸组合。定义定义2：集合集合C En 称为凸集，如果对任意称为凸集，如果对任意x1, x2 C
15、,0 1,有有 x1 +(1- )x2 C。Cx2x1凸凸集集没没有有凹凹陷陷部部分分，该该集集合合内内任任取取两两点点连连线上的任何点都应该在集合内。线上的任何点都应该在集合内。在凸集中，不能表示为不同点的凸组合的点在凸集中，不能表示为不同点的凸组合的点称为凸集的极点，用严格的定义描述如下。称为凸集的极点，用严格的定义描述如下。定义定义3设设S为一凸集，且为一凸集，且X S，X1 S，X2 S。对于对于0 1，若，若X= X1+(1- )X2则必定有则必定有X=X1=X2，则称则称X为为S的一个的一个极点极点。可以证明，线性规划的可行域以及最优解有以下性质：可以证明，线性规划的可行域以及最优
16、解有以下性质： （1）、若线性规划的）、若线性规划的可行域非空可行域非空，则可行域，则可行域必定为一必定为一凸集凸集；（2）、若若线线性性规规划划的的可可行行域域非非空空，则则至至多多有有有有限限个个极点极点；（3）、若线性规划）、若线性规划有最优解有最优解，则至少有，则至少有一个极点是一个极点是最优解。最优解。这样，求线性规划最优解的问题，从在可行域内无这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为限个可行解中搜索的问题转化为在其可行域的有限个在其可行域的有限个极点上搜索的问题。极点上搜索的问题。性质性质1：线性规划问题所有可行解组成的线性规划问题所有可行解组成的集
17、合集合S =x |Ax= b , x 0 是是凸集。凸集。线性规划的可行域是由有限个线性规划的可行域是由有限个(m个个)超半超半空间的交集形成的。如果线性规划问题的可空间的交集形成的。如果线性规划问题的可行域不空，是一个在行域不空，是一个在n 维空间的凸多面体，这维空间的凸多面体，这类凸集又称为类凸集又称为多面凸集多面凸集。性质性质2：x 是线性规划问题基本可行解的充要是线性规划问题基本可行解的充要条件是条件是x 为可行域为可行域S =x |Ax = b, x 0 的的极点。极点。 这个结论被称为线性规划的这个结论被称为线性规划的基本定理基本定理，它的重要性在于把可行域的极点这一几何概它的重要
18、性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来。念与基本可行解这一代数概念联系起来。性质性质3：给定线性规划给定线性规划P：maxcx |Ax = b , x 0 A是秩为是秩为m 的的m n 矩阵。矩阵。(i)若若P存存在在可可行行解解，则则必必存存在在基基本本可行解。可行解。(ii)若若P存存在在最最优优解解，则则必必存存在在最最优优基基本可行解。本可行解。性质性质4、若线性规划问题的可行域、若线性规划问题的可行域R，则R至少有一个极至少有一个极点。点。R可行域非空集，表明可行域非空集，表明线性性规划划问题有可行解，有可行解，则由性由性质3与性与性质2即可推出即可推出这条
19、性条性质。性性质5：线性性规划划问题可行域可行域R的极点数目必的极点数目必为有限多个。有限多个。基基本可行解与极点一一本可行解与极点一一对应阐述了阐述了可行域的极点只有可行域的极点只有有限个有限个，并且，并且说明可以说明可以通过求基本可行解的线性代数的方法来得到可行域的一通过求基本可行解的线性代数的方法来得到可行域的一切极点切极点，从而有可能进一步获得最优极点。，从而有可能进一步获得最优极点。几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线：一组平行线 目标函数值
20、等于一个常数的解讨论复习线性代数内容复习线性代数内容: :列向量列向量 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的秩的秩 设A为一个mn阶矩阵(mn)若矩阵中最大线性 无关列向量个数为k,则称矩阵A的秩为k,记 为rank(A)=k.本章小结v重点：线性规划的要素、图解法、解的性质、标准形及其转化v难点：线性规划模型的建立v作业： 建立模型、图解法、标准形转化、解的判断各一道
