刘舒燕：运筹学-线性规划基础

1、运运 筹筹 学学刘舒燕刘舒燕武汉理工大学管理学院武汉理工大学管理学院第一部分第一部分 线性规划线性规划（Linear Programming，简称，简称LP）线性规划的发展线性规划的发展1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题1947年，Dantzig提出求解线性规划的单纯形法1950-1956年，主要研究线性规划的对偶理论1958年，发表整数规划的割平面法1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论 和算法的基础。1979年，Khachiyan，1984年，Karmarka研究成功线性规划的多项式算法。线性规划研究的主要问

2、题线性规划研究的主要问题 一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。 实际上，上述两类问题是一个问题的两个不同的方面，都是在给定实际上，上述两类问题是一个问题的两个不同的方面，都是在给定的一组约束条件下求问题的最优解（的一组约束条件下求问题的最优解（ max 或或 min ）。）。 另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。第一章第一章 线性规划基础线性规划基础例1.1 （生产计划问题生产计划问题）某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润。问：应如何安排生产计划，才能使 总利润

3、最大？ 1.1 线性规划的基本概念线性规划的基本概念一、问题的提出一、问题的提出解：解：1.决策变量：设产品I、II的产量分 别为 x1、x22.目标函数：设总利润为z，则有： max z = 2 x1 + 3 x23.约束条件： x1 + 2x2 8 4x1 16 4x2 12 x1， x20例1.2 （配料问题配料问题）某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量：要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。解：解：1.决策变量：设四种原料的使用 量分别为： x1、x2 、x3 、x42.

4、目标函数：设总成本为z，则有： min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.约束条件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x40 药物原料ABC单位成本（元吨）甲1235乙2016丙1417丁1228二、数学模型二、数学模型1.决策变量： X = (x1,x2,.,xn)T2.目标函数：max (minz) = c1 x1 + c2 x2 + . + cnxn3.约束条件： a11x1 + a12 x2 +.+ a1n xn (=) b1 a21x1 +

5、 a22 x2 +.+ a2n xn (=) b2 am1x1 + am2 x2 +.+ amn xn (=) bm x1,x2,xn0三、模型特点三、模型特点1 都用一组决策变量X = (x1,x2,xn)T表示某一方案，且决策变量取值非负； 具有以上三个特征的数学模型称为线性规划具有以上三个特征的数学模型称为线性规划2 都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数； 根据目标要求的不同，可以是求max，也可以是求min；3 都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等 式来表示。其它形式其它形式),2, 1(0),2, 1(max(min)11njxm

6、ibxaxczjnjijijnjjj求和形式求和形式矩阵形式矩阵形式0 max(min)XbAXCXznxxxX21决策变量决策变量常数项常数项nbbbb21系数矩阵系数矩阵 nmijmnmmnnaaaaaaaaaaA212222111211价值系数价值系数ncccC21其中其中：1.2 线性规划数学模型的建立线性规划数学模型的建立一、建模条件一、建模条件1 优化条件优化条件：问题所要达到的目标能用线型函数描述，且能够用极值 （max 或 min）来表示；2 限定条件限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的 线性等式或线性不等式表示；3 选择条件选择条件：有多种可选择的方案

7、供决策者选择，以便找出最优方案。二、建模步骤二、建模步骤1 确定决策变量：确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目 问什么就设什么为决策变量。2 找出所有限定条件：找出所有限定条件：即决策变量受到的所有的约束；3 写出目标函数：写出目标函数：即问题所要达到的目标，并明确是max 还是 min。三、建模案例三、建模案例例例1.3 （生产计划问题生产计划问题）某工厂生产A、B两种产品，有关资料如下所示：设总成本为设总成本为z，A、B产品销量为产品销量为x1、x2，产品产品C的销售量为的销售量为x3，报废量为，报废量为x4，则：，则： max z = 4 x1 + 10 x2 +

8、 3 x3 2 x4 2x1 + 3x2 12 3x1 + 4x2 24 2x2 +x3 + x4 = 0 x3 5 x1、x2 、x3 、x40船只种类船只数拖 轮30A型驳船34B型驳船52航线号合同货运量12002400航线号船队类型编队形式货运成本（千元队）货运量（千吨）拖轮A型驳船B型驳船1112362521436202322472404142720问：应如何编队，才能既完成合同任务，又使总货运成本为最小？例1.4 （合理组织船舶运行问题合理组织船舶运行问题）某航运局现有船只种类、数量以及计划期 内各条航线的货运量、货运成本如下表所示：解：设：xj为第 j 号类型船队的队数（j =

9、1，2，3，4），z 为总货运成本则： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 302x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1 + 20 x2 200 40 x3 + 20 x4 400 xj 0 j = 1,2,3,4(变量为整数)用单纯形法可求得：用单纯形法可求得： x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最优值：最优值：z = 954即：四种船队类型的队数分别是即：四种船队类型的队数分别是 8、0、7、6，此时可使总货运成本为最小，为此时可使总货运成本为最小，为954千元。千

10、元。例1.5 （合理下料问题合理下料问题）某厂需要做100套钢架，每套用长为2.9m、2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，可使所用的原材料最省？解：1）最简单的方法是：在每一根原材料上截取2.9m、2.1m、1.5m元钢各一根，每根余料头0.9m，为了做100套钢架，用料100根，共有90m料头。2）但若采用套裁的方法，则可节约原材料。如以下套裁方案： 方案方案长度长度mIIIIIIIVV2.92.11.5合计合计料头料头017.30.11207.40.31000213237.27.16.60.00.20.82应选择应选择哪种下哪种下料方案料方案呢呢?显然显然,应

11、混合使用应混合使用各种下料方案各种下料方案,而而不能只采用其中不能只采用其中一种方案。一种方案。3）数学模型min z = 0.1x1 + 0.3x20.2x40.8x5 2x1 + x2 +x3 100 2x2 + 2x4 x5 100 x1 3x32x43x5 100 xj 0 j = 1,2,3,4,5(变量为整数)决策变量：设按第 j 种方案下料的原材料根数为xj（ j 1,2,3,4,5 ）目标函数：要求原材料最省，则以所余料头最少为目标： min z 0.1x10.3x20.0 x30.2x40.8x5约束条件：采用各种方案截取的三种规格的元钢数各为100根，则数学模型为：1.3

12、线性规划图解法线性规划图解法一、解题步骤一、解题步骤4 将最优解代入目标函数，求出最优值。1 在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共 部分，称为可行域，可行域中的点称为可行解。若无公共部分，则无可 行域，从而无可行解。2 标出目标函数值增加的方向。3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方 向平行移动，找与可行域最后相交的点，该点就是最优解。目标函数的梯度方向。目标函数的梯度方向。例例1x1 + 2x2 8 4x1 16 4x2 12 x1， x20 max z = 2 x1 + 3 x2最优解：最优解：X*= (4,2)T最优值：最优值：z*

13、= 14二、算例二、算例例例2x1 + 2x2 8 4x1 16 4x2 12 x1， x20 max z = 2 x1 + 4 x2该问题有无穷多个最优解（在可行域内，该问题有无穷多个最优解（在可行域内， 直线直线 x12x28上的点都是最优解）上的点都是最优解） 最优值：最优值：z* 2(x12x2)28 16目标函数等值线最后与可行域的边界目标函数等值线最后与可行域的边界 x12x28重合重合例例3在例1中增加约束条件2x1 + x2 4 无可行域，因而无可行解无可行域，因而无可行解 该问题无最优解该问题无最优解例例42x1 + x2 4 x1 x2 2 x1， x20 max z =

14、x1 + x2 目标函数的等值线与可行域无最后交点目标函数的等值线与可行域无最后交点 该问题有可行解，但无最优解。该问题有可行解，但无最优解。小结：小结：1 线性规划问题的解有以下几种情况：线性规划问题的解有以下几种情况：有最优解有最优解无最优解无最优解有唯一最优解有唯一最优解有无穷多个最优解有无穷多个最优解无可行解，因而无最优解无可行解，因而无最优解有可行解，但无最优解有可行解，但无最优解例1例2例3例42 图解法的适用范围：图解法的适用范围：求解两个变量的线性规划问题求解两个变量的线性规划问题问题问题:应如何求解应如何求解多个变量的多个变量的线性规划问线性规划问题题 ？ 目标函数与可行域最

15、后有唯一交点目标函数与可行域最后有唯一交点 目标函数与可行域最后有两个以上交点目标函数与可行域最后有两个以上交点 约束条件无公共区域约束条件无公共区域 约束条件有公共区域，但目标函数与可行域无最后交点约束条件有公共区域，但目标函数与可行域无最后交点1.4 线性规划解的概念及性质线性规划解的概念及性质1 可行解（可行解（ feasible solution ）：）：满足线性规划约束条件的解称为可行解可行解。一、线性规划解的概念一、线性规划解的概念2 最优解（最优解（optimal solution）：使线性规划目标函数达到最优的可行解称为 最优解最优解。3 基本解（基本解（basic solut

16、ion）：以线性规划约束等式的系数矩阵A中任意m行m 列组成的mm满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量（basic variable），其余变量称为非基变量，令非基变量为零，可求得基变 量的值，这样求出的解称为基本解基本解。 4 基本可行解（基本可行解（basic feasible solution）： 满足非负约束的基本解称为基本可行解基本可行解。若约束等式中有若约束等式中有n个个变量，变量，m个约束，则个约束，则基本解的个数基本解的个数 即有有限个基本解即有有限个基本解mnC基本可行解的个数也是有限个基本可行解的个数也是有限个令非基变量 x10，x2 0则得：X (0, 0,

17、 3, 1 )T基本解基本解2）取满秩子矩阵 为基矩阵，0112322PPB则：基变量为x2、x3，非基变量为x1、x4令非基变量 x10，x4 0则得：X (0, 1, 5, 0 )T基本解基本解基本可行解基本可行解不是基本可行解不是基本可行解例例 讨论下述约束方程的解 x1 2x2 x3 3 2x1 x2 x4 1解解系数矩阵为：10120121A1）取满秩子矩阵 为基矩阵，1001431PPB则：基变量为x3、x4，非基变量为x1、x23）X (1/2, 1/2, 3/2, 1/2)T不是基本解不是基本解可行解可行解不是基本可行解不是基本可行解1 可行解与最优解：最优解一定是可行解，但可

18、行解不一定是最优解。二、线性规划解之间的关系二、线性规划解之间的关系基本解不一定是可行解，可行解也不一定是基本解。2 可行解与基本解：3 可行解与基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解解一定是基本解，但基本解不一定是基本可行解。4 基本解与基本可行解：5 最优解与基本解：最优解不一定是基本解，基本解也不一定是最优解。问题：最优解与基本可行解？非可行解可行解基本可行解基本解三、线性规划解的性质三、线性规划解的性质定理定理1 线性规划的可行域 R 是一个凸集，且有有限个顶点。定理定理2 X是线性规划可行域 R 顶点的充要条件是 X 线性规划的基本可行解。定理定理3 若线性规划有最优解，则必有基本最优解。定理定理4 若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线 上也达到最优。线性规划问题的可行域是一个凸集。线性规划问题的可行域是一个凸集。线性规划的每一个基本可行解对应凸集的每一个顶点。线性规划的每一个基本可行解对应凸集的每一个顶点。若线性规划有最优解