第3章 线性规划n3.1 LP的基本概念n3.2线性规划问题的图解法n3.3 单纯形表上作业法n3.4 大M法和两阶段法n3.5单纯形法的进一步探讨n3.6 计算机求解n3.7 习题课Date南京工业大学管理科学与工程学院 潘郁教授第3章 线性规划n线性规划的发展n1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产 效率问题1947年，Dantzig提出求解线性规划的单纯形法1950-1956年，主要研究线性规划的对偶理论1958年，发表整数规划的割平面法n1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规 划问题理论和算法的基础。n1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多 项式算法。Date南京工业大学管理科学与工程学院 潘郁教授3.1 LP(linear programming)的基本概念LP是在有限资源的条件下，合理分配和利 用资源，以期取得最佳的经济效益的优 化方法。 LP有一组有待决策的变量，一个线性的目标函数，一组线性的约束条件。Date南京工业大学管理科学与工程学院 潘郁教授线性规划研究的主要问题n一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。n另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。n 实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（ max 或 min ）。Date南京工业大学管理科学与工程学院 潘郁教授例1.1 某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润 问：应如何安排生产计划，才能使总利润最大？ 例题1生产计划问题解：1.决策变量：设产品I、II的产量分别为 x1、x22.目标函数：设总运费为z，则有：max z = 2 x1 + 3 x23.约束条件：x1 + 2x2 8 4x1 164x2 12x1， x203.1.1 LP的数学模型Date南京工业大学管理科学与工程学院 潘郁教授例题2 某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量（配方问题）要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。解：1.决策变量：设四种原料的使用量分别为： x1、x2 、x3 、x42.目标函数：设总成本为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 丁1228Date南京工业大学管理科学与工程学院 潘郁教授例题3：人员安排问题n医院护士24小时值班，每次值班8小时。不同时段需要的护士人 数不等。据统计：序号时段最少人数安排人数 1061060X1 2101470X2 3141860X3 4182250X4 5220220X5 6020630x6Date南京工业大学管理科学与工程学院 潘郁教授例题3建模n目标函数：min Z=x1+x2+x3+x4+x5+x6n约束条件： x1+x2 70x2+x3 60x3+x4 50x4+x5 20x5+x6 30x6+x1 60 非负性约束：xj 0,j=1,2,6Date南京工业大学管理科学与工程学院 潘郁教授例题4合理下料问题n料长7.4米，截成2.9、2.1、1.5米各200根。如 何截取余料最少？关键：设变量。方案 料型1 2 3 4 5 6 7 82.9米 2.1米1.5米1 2 0 1 0 1 0 00 0 2 2 1 1 3 03 1 2 0 3 1 0 4合计残料7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.00 0.1 0.2 0.3 0.8 0.9 1.1 1.4Date南京工业大学管理科学与工程学院 潘郁教授例题4建模设：xj为采用第 j种方案的根数（j = 1，2，8），z 为总残料量则： min z = 0.1x2 + 0.2x3 + 0.3x4 + 0.8x5 + 0.9x6 + 1.1x7 +1.4x8x1 +2 x2 + x4 + x6 2002x3 +2 x4 + x5 + x6 + 3x7 2003x1 + x2 + 2x3 +3 x5 + x6 +4 x8 200xj 0 j = 1,2,8Date南京工业大学管理科学与工程学院 潘郁教授船只种类船只数拖 轮30A型驳船34B型驳船52航线号合同货运量12002400航线号船队 类型编队 形式货运成本 （千元队）货运量 （千吨）拖轮A型 驳船B型 驳船 111236252143620232247240 4142720问：应如何编队，才能既完成合同任务，又使总货运成本为最小？例题5 某航运局现有船只种类、数量以及计划期内各条航线的货运量、货 运成本如下表所示：Date南京工业大学管理科学与工程学院 潘郁教授例题5建模设：xj为第 j 号类型船队的队数（j = 1，2，3，4），z 为总货运成本则： min z = 36x1 + 36x2 + 72x3 + 27x4x1 + x2 + 2x3 + x4 302x1 + 2x3 344x2 + 4x3 + 4x4 5225x1 + 20x2 20040x3 + 20x4 400xj 0 j = 1,2,3,4用单纯形法可求得：x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最优值：z = 954即：四种船队类型的队数分别是8、0、7、6，此时可使总货运成本为最小，为954千元。Date南京工业大学管理科学与工程学院 潘郁教授线性规划模型特点1 都用一组决策变量X = (x1,x2,xn)T表示某一方案； 满足以上三个条件的数学模型称为线性规划2 都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3 都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。Date南京工业大学管理科学与工程学院 潘郁教授3.2线性规划问题的名词和图解法max z= x1+3x2s.t. x1+x26-x1+2x28x1,x20Date南京工业大学管理科学与工程学院 潘郁教授4 将最优解代入目标函数，求出最优值。1 在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点称为可行解。2 标出目标函数值增加的方向。3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。图解法解题步骤Date南京工业大学管理科学与工程学院 潘郁教授可行域 (可行解全体)基本可行解 (可行域顶点、极点)基本解Date南京工业大学管理科学与工程学院 潘郁教授令非基变量 x10，x2 0则得：X (0, 0, 3, 1 )T基本解则：基变量为x2、x3，非基变量为x1、x4令非基变量 x10，x4 0则得：X (0, 1, 5, 0 )T基本解 不是基本可行解基本可行解例 讨论下述约束方程的解x1 2x2 x3 32x1 x2 x4 1解系数矩阵为：则：基变量为x3、x4，非基变量为x1、x23）X (1/2, 1/2, 3/2, 1/2)T不是基本解可行解不是基本可行解Date南京工业大学管理科学与工程学院 潘郁教授3.2.2 线性规划的基本名词1 可行解（ feasible solution ）：满足线性规划约束条件的解称为可行解。2可行域：可行解的集合3 最优解（optimal solution）：使线性规划目标函数达到最优的可行解。4 基本解（basic solution）：以线性规划约束等式的系数矩阵A中任意m行m列组成的mm满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量（basic variable），其余变量称为非基变量，令非基变量为零，可求得基变量的值，这样求出的解称为基本解。 5基本可行解（basic feasible solution）：满足非负约束的基本解称为基本可行解。若约束等式中有n 个变量，m个约束 ，则基本解的个数 Date南京工业大学管理科学与工程学院 潘郁教授基础解、基础可行解max z=x1+3x2D s.t. x1+ x2+x3=6 B -x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0E O x2=0 ADate南京工业大学管理科学与工程学院 潘郁教授1 可行解与最优解： 最优解一定是可行解，但可行解不一定是最优解。线性规划解之间的关系基本解不一定是可行解，可行解也不一定是基本解。2 可行解与基本解：3 可行解与基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，但基本解不一定是基本可行解。4 基本解与基本可行解：5 最优解与基本解：最优解不一定是基本解，基本解也不一定是最优解。问题：最优解与基本可行解？非可行解可行解基本可行解基本解Date南京工业大学管理科学与工程学院 潘郁教授几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集 ： 凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线 ： 一组平行线 目标函数值等于一个常 数的解Date南京工业大学管理科学与工程学院 潘郁教授线性规划解的性质定理1 线性规划的可行域 R 是一个凸集，且有有限个顶点。定理2 X是线性规划可行域 R 顶点的充要条件是 X 线性规划的基本可行解。定理3 若线性规划有最优解，则必有基本最优解。定理4 若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线上也达到最优。线性规划问题的可行域是一个凸集。线性规划的每一个基本可行解对应凸集的每一个顶点。若线性规划有最优解，则一定在凸集的某个（些）顶点上达到最优。若线性规划在两个顶点以上达到最优,则一定有无穷多个最优解。最优解一定是基本可行解，但基本可行解不一定是最优解。Date南京工业大学管理科学与工程学院 潘郁教授解的形态(d)可行域无界 (e)可行域无界 (f)可行域为空