《管理运筹学讲义：线性规划》由会员分享，可在线阅读，更多相关《管理运筹学讲义：线性规划（70页珍藏版）》请在金锄头文库上搜索。
1、1,第一讲 线性规划,第一章 线性规划的数学模型 第一节 线性规划一般模型 第二节 线性规划的图解法 第三节 线性规划的标准型 第四节 线性规划解的概念 第二章 线性规划的单纯形法 第一节 单纯形法原理 第二节 表格单纯形法 第三节 人工变量问题 第四节 单纯形法补遗 第三章 线性规划的对偶理论 第四章 线性规划灵敏性分析,2,第一章 线性规划的数学模型,线性规划 Linear Programming LP 规划论中的静态规划 解决有限资源的最佳分配问题 求解方法： 图解法 单纯形解法,3,第一章 线性规划的数学模型,第一节 线性规划一般模型 第二节 线性规划的图解法 第三节 线性规划的标准型
2、 第四节 线性规划解的概念,4,第一节 线性规划一般模型,一、线性规划问题的三个要素,决策变量 决策问题待定的量值称为决策变量。 决策变量的取值要求非负。 约束条件 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。 约束条件是决策方案可行的保障。 LP的约束条件，都是决策变量的线性函数。 目标函数 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。 目标函数是决策变量的线性函数。 有的目标要实现极大，有的则要求极小。,5,第一节 线性规划一般模型,例1. 生产计划问题 某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，
3、相关数据如表所示： 问如何安排甲、乙两产品的产量，使利润为最大。,二、线性规划模型的构建,6,第一节 线性规划一般模型,(1)决策变量。要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲产品产量，x2为乙产品产量。 (2)约束条件。生产这两种产品受到现有生产能力的制约，用量不能突破。 生产单位甲产品的零部件需耗用A车间的生产能力1工时， 生产单位乙产品不需耗用A车间的生产能力， A车间的能力总量为8工时，则A车间能力约束条件表述为 x1 8 同理，B和C车间能力约束条件为 2x2 12 3x1 +4 x2 36,建立模型,7,第一节 线性规划一般模型,(3)目标函数。目标是利润
4、最大化，用Z表示利润，则 maxZ= 3x1 +5 x2 (4)非负约束。甲乙产品的产量不应是负数，否则没有实际意义，这个要求表述为 x1 0， x2 0,8,第一节 线性规划一般模型,某名牌饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。,例2. 运输问题,9,第一节 线性规划一般模型,(1)决策变量。设从Ai到Bj的运输量为xij， (2)目标函数。运费最小的目标函数为 minZ=6x11+3x12+2
5、x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)约束条件。产量之和等于销量之和,故要满足： 供应平衡条件,x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3,销售平衡条件,x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=4,非负性约束 xij0 (i=1,2,3；j=1,2,3,4),10,第一节 线性规划一般模型,用一组非负决策变量表示一个决策问题， 存在一定的等式或不等式的线性约束条件， 有一个希望达到的目标，可表示成
6、决策变量的线性函数。可能是最大化，也可能是最小化。 线性规划一般模型的代数式 为：,三、线性规划的一般模型,max(min)Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn (,)b1 a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn(,)bm x1,x2,xn ()0,11,第二节 线性规划的图解法,图解法即是用图示的方法来求解线性规划问题。 一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。,一、图解法的基本步骤,12,第二节 线性规划的图解法,1. 可行域的确定,五
7、边形OABCD内(含边界)的任意一点 (x1，x2) 都是满足所有约束条件的一个解，称之可行解 。,满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。,13,第二节 线性规划的图解法,2. 最优解的确定,目标函数 Z= 3x1 +5 x2 代表以Z为参数的一族平行线。,等值线：位于同一直线上的点的目标函数值相同。 最优解：可行解中使目标函数最优(极大或极小)的解,14,第二节 线性规划的图解法,由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。 可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。 目标函
8、数最优值一定在可行域的边界达到，而不可能在其内部。,二、几点说明,15,第二节 线性规划的图解法,三 、解的可能性,唯一最优解：只有一个最优点。 多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。,16,第二节 线性规划的图解法,无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）,三 、解的可能性（续）,17,第二节 线性规划的图解法,无可行解：若约束条件相互矛盾，则可行域为空集,三 、解的可能性（续）,18,第三节 线性规划的标准型,线性规划问题的数学模型有各种不同的形式，如 目标函数有极大化和极小化； 约束条件有“”、“
9、”和“”三种情况； 决策变量一般有非负性要求，有的则没有。 为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为： 目标函数极大化， 约束条件为等式， 右端常数项bi0， 决策变量非负。,一 、标准型,19,第三节 线性规划的标准型,1. 代数式,二、标准型的表达方式 有代数式、矩阵式：,简记,20,第三节 线性规划的标准型,2. 矩阵式,21,第三节 线性规划的标准型,目标函数极小化问题 minZ=CTX，只需将等式两端乘以 -1 即变为极大化问题。 因为minZ=-max (-Z)=CTX，令Z= -Z，则maxZ=-CX 右端常数项非正 两端同乘以 -1 约束
10、条件为不等式 当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式变成了等式； 当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。 决策变量xk没有非负性要求 令xk=xk-x k， xk=xk，x k 0，用xk、x k 取代模型中xk,三、非标准型向标准型转化,22,第三节 线性规划的标准型,例1 的标准型,x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0,maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5,23,minZ= x1 +2 x2 +3 x3 x1 +2
11、 x2 + x35 2x1 +3 x2 + x36 -x1 - x2 - x3 -2 x1 0, x30,第三节 线性规划的标准型,24,第三节 线性规划的标准型,标准化2 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x35 2x1 +3 (x2-x 2) + x36 - x1 - (x2-x 2) - x3 -2 x1, x2,x 2 , x3 0 标准化3 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x35 2x1 +3 (x2-x 2 ) + x36 x1 + (x2-x 2 ) + x3 2 x
12、1, x2, x 2, x3 0,25,第三节 线性规划的标准型,标准化4 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 0 标准化5 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 , x5 0,26,第
13、三节 线性规划的标准型,标准化6 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6= 2 x1, x2, x 2, x3, x4 , x5 , x6 0 标准化7 maxZ= -x1 -2 (x2-x 2) - 3x3+0 x4+0 x5+0 x6 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6 = 2 x1, x
14、2, x 2, x3, x4 , x5 , x6 0,27,第四节 线性规划解的概念,可行解： 满足约束条件AX=b, X0的解。 最优解： 使目标函数最优的可行解，称为最优解。 基 mn，且m个方程线性无关，即矩阵A的秩为m；根据线性代数定理可知，nm，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。,一、线性规划解的概念,28,第四节 线性规划解的概念,线性方程组的增广矩阵,例1 的标准型 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0
15、,单位矩阵,29,第四节 线性规划解的概念,基矩阵： 系数矩阵A中任意m列所组成的m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。 或称为一个基，用B表示。 称基矩阵的列为基向量，用Pj表示(j=1,2,m) 。,的基矩阵B最多C53=10，如下：,30,第四节 线性规划解的概念,基变量： 与基向量Pj相对应的m个变量xj称为基变量， 其余的m-n个变量为非基变量。 基解： 令所有非基变量等于零，对m个基变量所求的解， 对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。 结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。,基变量是x3, x4, x5 非基变量是x1, x2
16、 令非基变量x1=x2=0，得到一个基解 x3=8，x4=12， x5=36,31,第四节 线性规划解的概念,基可行解：满足非负性约束的基解称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优基：最优解对应的基矩阵，称为最优基。,非 可 行 解,可 行 解,基 解,32,第四节 线性规划解的概念,定理1.若线性规划问题存在可行域，则其可行域一定是凸集。 定理2.线性规划问题的基可行解对应可行域的顶点。 定理3.若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。,二、线性规划的基本定理,线性规划问题可以有无数个可行解，最优解只可能在顶点上达到，而有限个顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解即可。 从一个顶点出发找到一个可行基，得到一组基可行解，拿目标函数做尺度衡量一下看是否最优。 如若不是，则向邻近的顶点转移，换一个基再行求解、检验，如此迭代循环目标值逐步改善，直至求得最优解。,三、线性规划的解题思路,33,第二章 线性规划单纯形法,单纯形法(Simplex Method)是美国人丹捷格 (G.Dantzig)1947年创建的 这种方法简捷、规
