2-运筹学LP-Bai-Di

1、运 筹 学( Operations Research ),管理工程系核心课程,Chapter1 线性规划 (Linear Programming),LP问题的提出 图解法 单纯形法 单纯形法的进一步讨论 LP模型的应用举例,本章主要内容：,线性规划问题的数学模型,1. 规划问题,生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。,线性规划通常解决下列两类问题：,（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标,（2）在一定的资源条件限制下，如何组织安排生产获得最

2、好的经济效益（如产品量最多 、利润最大.）,线性规划问题的数学模型,例1 窗户问题：三个工厂分别进行三种生产：工厂1生产产品1是铝窗，工厂2生产产品2是木窗，工厂3做组装产品的工作。具体数据如下表，应如何安排生产计划，使总的利润最大？,线性规划问题的数学模型,例2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m，两工厂之间有一条流量为每天200万m的支流，见图。 第一化工厂每天排放污水2万m，第二化工厂每天排放污水1.4万m。污水从工厂1流到工厂2前会有20%的自然净化。根据环保要求，河水中污水的含量应不大于0.2%。而工厂1和工厂2处理污水的成本分别为1000元/m和800

3、元/m。问两个工厂各应处理多少污水才能使处理污水的总费用最低？,线性规划问题的数学模型,2. 线性规划的数学模型由三个要素构成,决策变量 Decision variables 目标函数 Objective function 约束条件 Constraints,其特征是： （1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值； （2）问题的约束条件是一组多个决策变量的线性不等式或等式。,怎样辨别一个模型是线性规划模型？,线性规划问题的数学模型,目标函数：,约束条件：,3. 线性规划数学模型的一般形式,简写为：,线性规划问题的数学模型,向量形式：,其中：,线性规划问题的数学模型,矩阵

4、形式：,其中：,线性规划问题的数学模型,3. 线性规划问题的标准形式,特点： (1) 目标函数求最大值（有时求最小值） (2) 约束条件都为等式方程 (3) 右端常数项bi都大于或等于零 (4) 决策变量xj为非负。,线性规划问题的数学模型,（2）如何化标准形式,目标函数的转换,如果是求极小值即 ，则可将目标函数乘以(-1)，可化为求极大值问题。,也就是：令 ，可得到上式。,即,若存在取值无约束的变量 ，可令 其中：,变量的变换,线性规划问题的数学模型,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量 的变换,可令 ，显然,线性规划问题的数学模型,例3 将下列线性规划问题

5、化为标准形式,Min Z= 2x1+ 3x2 S.T. 2x1 + 2x2 8 4x1 12 x2 -16 x10 , x2 无约束,图解法,线性规划问题的求解方法,一 般 有 两种方法,图 解 法 单纯形法,两个变量、直角坐标 三个变量、立体坐标,适用于任意变量、但必需将 一般形式变成标准形式,下面我们分析一下简单的情况 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。,图解法,例4 用图解法求解线性规划问题（窗户问题）,Max Z= 3x1+ 5x2 S.T. x1 4 2x2 12 3x1 + 2x2 1

6、8 x1, x2 0,图解法,解：给决策变量任意一个数值的我们就称为解（无论是否可行） 可行解：满足所有限制条件的解 不可行解：至少不满足一个限制条件的解 可行域：所有可行解的集合 最优解：可行域中使得目标函数值达到最优的点 无穷多最优解：至少有两个解是顶点 无界解：可行域可伸展到无穷 无解或无可行解：不存在满足所有约束的公共解域,图解法,学习要点： 1. 通过图解法了解线性规划有几种解的形式 （唯一最优解；无穷多最优解；无界解；无可行解） 2. 作图的关键有三点： (1) 可行解区域要画正确 (2) 目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动,基、基向量和非基向量、基变量

7、和非基变量,A是mn阶的系数矩阵，其秩为m。若B是A中的m阶的满秩子矩阵，即B是由A中的个线性独立的系数列向量组成，则称之为线性规划问题的一个基。不失一般性，令B mm =P1，P2Pm,基中的列向量Pj(j=1m)称为基向量，与之对应的变量xj (j=1m)为基变量。A中其余不包含在B中的列向量Pj(j=m+1n)为非基向量，与之对应的xj (j=m+1n) 是非基变量。,可见系数矩阵中m个线性独立的列向量可组成一个基，LP问题基的个数不会超过 个,单纯形法,基解：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数

8、不超过 基可行解：满足变量非负约束条件的基本解，简称基可行解。 可行基：对应于基可行解的基称为可行基。,线性规划问题的数学模型,例：指出下列线性规划问题的基、基变量、 基本解、基本可行解、可行基。,Max Z= 2x1+ 3x2 S.T. 2x1+ 2x2 +x3= 12 x1+2x2 +x4= 8 3x2 +x5= 9 xj 0，j=1，2,线性规划问题的数学模型,例：已知线性规划问题，表中哪些是可行解？哪些是基解？哪些是基可行解？,Max Z= x1+ 3x3 S.T. x1+ x3 = 5 x1+2x2 +x4 = 10 x2 +x5 = 4 xj 0，j=1，2，3，4，5,单纯形法基

9、本原理,凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。,单纯形法基本原理,定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。 定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。 定理3：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）,单纯形法基本原理, 对于任意一个至少有一个最优解的问题，我们就只关注顶点。 单纯形法是一个不断循环的运算过程。 尽量用原点作为初始点（方便） 只找相邻的点移动，因为计算比较容易（限制条件有相同），所以单纯形法只在可行域的边界上移动 有两个方向可以选择的时候，通常选择大的提高率来移动 若

10、相邻的顶点都比该解差的时候，那就是最优解,单纯形法的计算步骤,单纯形法的思路,找出一个初始可行解,是否最优,转移到另一个基本可行解 （找出更大的目标函数值）,最优解,是,否,循 环,核心是：变量迭代,结束,单纯形法的计算步骤,单纯形表,单纯形法的计算步骤,例1.8 用单纯形法求下列线性规划的最优解,解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:,单纯形法的计算步骤,2）求出线性规划的初始基可行解，列出初始单纯形表。,检验数,单纯形法的计算步骤,3）进行最优性检验,如果表中所有检验数 ，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。,4）从一个基可行解转换到另一个目标

11、值更大的基可行解，列出新的单纯形表,确定换入基的变量。选择 ，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即： ，其对应的xk作为换入变量。 确定换出变量。根据下式计算并选择 ，选最小的对应基变量作为换出变量。,单纯形法的计算步骤,用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。 5）重复3）、4）步直到计算结束为止。,单纯形法的计算步骤,换入列,bi /ai2，ai20,40,10,换出行,将3化为1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5

12、/3,0,4/3,乘以1/3后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,单纯形法的计算步骤,例1.9 用单纯形法求解,解：将数学模型化为标准形式：,不难看出x4、x5可作为初始基变量，列单纯形表计算。,单纯形法的计算步骤,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9,-1/9,-7/3,单纯形法的计算步骤,学习要点： 1. 线性规划解的概念以及3个基本定理 2. 熟练掌握单纯形法的解

13、题思路及求解步骤,单纯形法的进一步讨论人工变量法,人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。,单纯形法的进一步讨论人工变量法,例1.10 用大M法解下列线性规划,解：首先将数学模型化为标准形式,系数矩阵中不存在单位矩阵，无法建立初始单纯形表。,单纯形法的进一步讨论人工变量法,故人为添加两个单位向量，得到人工变量单纯形

14、法数学模型：,其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。,单纯形法的进一步讨论人工变量法,两阶段法,在用计算机求解时，M是用一个很大的数字来表示无限大的，但是如果LP模型中的系数也很大，容易导致误差。两阶段法可解决这问题。 例：第一阶段：以人工变量加和为目标函数的最小化问题。 Min x6+x7 Max -x6 -x7 x1+x2+x3 +x4 =4 -2x1+x2 - x3 - x5 + x6 =1 3x2 +x3 +x7 =9 xi0，i17 在此阶段若存在最优解，必为人工变量X6 X70

15、，此时目标函数0。这个最优解满足原问题的约束条件，又是原问题的基解，因此就是原问题的基可行解。,第一阶段最优解为1 3 0 0 0 0 0T,最终表,若在第一阶段的最终表中，所有检验数0,但基变量中还有非零的人工变量，第一阶段目标函数0，说明原问题无可行解。,第二阶段：将基可行解代入原问题目标函数继续迭代 将第一阶段的最终单纯形表中的人工变量所在列去除，且将目标函数改为原问题目标函数，继续迭代。,3 0 1 0 0,0 0 3,单纯形法的进一步讨论人工变量法,解的判别： 1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的

16、检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个k0且aik（i=1，2,m）则线性规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。,线性规划模型的应用,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。,要求解问题的目标函数能用数值指标来反映，且为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述,线性规划在管理中的应用,人力资源分配问题,例1.11 某昼夜服务的公交线路每天各时间段

17、内所需司机和乘务人员人数如下表所示：,设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?,线性规划在管理中的应用,解：设xi表示第i班次时开始上班的司机和乘务人员人数。,此问题最优解：x150， x220， x350， x40， x520， x610，一共需要司机和乘务员150人。,线性规划在管理中的应用,2. 生产计划问题,某厂生产、三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品可在A、B任何一种设备上加工；产品

18、可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。,线性规划在管理中的应用,线性规划在管理中的应用,解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：,线性规划在管理中的应用,目标是利润最大化，即利润的计算公式如下：,带入数据整理得到：,线性规划在管理中的应用,因此该规划问题的模型为：,线性规划在管理中的应用,3. 套裁下料问题,例：现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？,解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同