管理学第一章-线性规划课件

运筹学——管理科学与工程系经济与管理学院浙江科技学院经济管理学院管工系运筹学——管课堂要求1.要求学生上课不迟到，不早退，不得旷课；2.上课认真听讲，要求每位同学都做笔记；3.上课不得讲话，看书，玩手机等与课堂无关的内容；4.课后要求独自完成作业，不得抄袭或不做课后作业。1/8/20232课堂要求1.要求学生上课不迟到，不早退，不得旷课；1/8/2参考资料1.胡运权主编，运筹学教程（第三版），清华大学出版社；2.周华任主编，运筹学解题指导，清华大学出版社；3.运筹学习题集（修订版），清华大学出版社；4.熊伟编著，运筹学，机械工业出版社；5.运筹学——数据、模型、决策，科学出版社。1/8/20233参考资料1.胡运权主编，运筹学教程（第三版），清华大学出版社前言—运筹学简介运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。求解结果….求解结果….建立模型求解模型修改模型求解结果….修改模型实际问题数学模型1/8/20234前言—运筹学简介运筹学是管理科学的重要理论基础和应用手段，是运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是OperationalResearch，在美国称为OperationsResearch。1/8/20235运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，OperationsResearch就转义成为“作业研究”。我国把OperationsResearch译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、对偶问题，整数规划、运输问题、动态规划、图与网络分析。1/8/20236战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划授课主要内容目录：绪论（1）第一章 线性规划（12）第二章 对偶问题（10）第三章 运输问题（6）第五章 整数规划（6）第七章 动态规划（8）第八章图与网络分析（8）上课总课时：51课时课程设计1周（下学期开学前）1/8/20237授课主要内容目录：上课总课时：51课时课程设计1周（下学第一章线性规划及单纯形法1.1线性规划问题及其数学模型1.2图解法1.3单纯形法原理1.4单纯形法计算步骤1.5单纯形法进一步讨论1/8/20238第一章线性规划及单纯形法1.1线性规划问题及其数学模型本章学习要求能建立实际问题的数学规划模型理解线性规划模型的特点，标准型掌握线性规划的图解法及其几何意义掌握单纯形法原理掌握运用单纯形表计算线性规划问题的步骤及解法能用二阶段法和大M法求解线性规划问题。掌握任何基可行解原表及单纯形表的对应关系1/8/20239本章学习要求能建立实际问题的数学规划模型1/8/202391.1线性规划问题及其数学模型举例说明线性规划数学模型的标准形式1/8/2023101.1线性规划问题及其数学模型举例说明1/8/202310一、线性规划问题举例说明生产计划问题配料问题背包问题运输问题指派问题下料问题1/8/202311一、线性规划问题举例说明生产计划问题1/8/202311例1：美佳公司－生产计划问题1、确定决策变量——通常由目标问题分解设x1代表生产Ⅰ种家电数量；x2代表生产Ⅱ种家电数量；2、分析并表达限制条件，包括约束条件——通常由等式或不等式表示。0x1+5x2≤156x1+2x2≤24x1+x2≤5x1≥0,x2≥03、分析目标——是利润最大化MaxZ=2x1+x21/8/202312例1：美佳公司－生产计划问题1、确定决策变量——通常由目标问例2：捷运公司表1－2所需仓库面积1、确定决策变量——通常由目标问题分解每个月有不同的租用方案，共有4个月需要租用仓库。则：表1－3租金与期限的关系1/8/202313例2：捷运公司表1－21、确定决策变量——通常由目标问题分1.生产计划问题（ProductionPlanning）某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：maxz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1,x2,x3,x4≥01/8/2023141.生产计划问题（ProductionPlanning）2.配料问题（MaterialBlending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（％），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（％）如下表：要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。minz=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.76x4≥3.20Cr的含量下限约束2.04x1+1.12x2+3.57x3+4.33x4≥2.10Mn的含量下限约束5.82x1+3.06x2+4.27x3+2.73x4≥4.30Ni的含量下限约束x1+x2+x3+x4=100物料平衡约束x1,x2,x3,x4≥01/8/2023152.配料问题（MaterialBlending）某工厂要3.背包问题（KnapsackProblem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。设三种物品的件数各为x1，x2，x3件，总价值为z。maxz=17x1+72x2+35x3s.t.10x1+41x2+20x3≤50x1，x2，x3≥0x1，x2，x3为整数这是一个整数规划问题（IntegerProgramming）。这个问题的最优解为：x1=1件，x2=0件，x3=2件，最高价值z=87元1/8/2023163.背包问题（KnapsackProblem）一只背包最4.运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：求总运费最低的运输方案。A1A2B3B2B135吨25吨10吨30吨20吨2354781/8/2023174.运输问题（Transportation）某种物资从两个设从两个供应地到三个需求地的运量（吨）如下表：minz=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35供应地A1x21+x22+x23=25供应地A2x11+x21=10需求地B1x12+x22=30需求地B2x13+x23=20需求地B3x11,x12,x13,x21,x22,x23≥01/8/202318设从两个供应地到三个需求地的运量（吨）如下表：minz=2这个问题的最优解表示如下：最小总运费为：z=3×30+5×5+4×10+8×15=275元A1A2B3B2B135吨25吨10吨30吨20吨23547830吨5吨10吨15吨1/8/202319这个问题的最优解表示如下：最小总运费为：z=3×30+5×55.指派问题（AssignmentProblem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：1/8/2023205.指派问题（AssignmentProblem）有n项张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。设：1/8/202321张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，设：maxz=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44s.t. x11+x12+x13+x14=1(1)x21+x22+x23+x24=1(2)x31+x32+x33+x34=1(3)x41+x42+x43+x44=1(4)x11+x21+x31+x41=1(5)x12+x22+x32+x42=1(6)x13+x23+x33+x43=1(7)x14+x24+x34+x44=1(8)xij=0,11/8/202322设：maxz=92x11+68x12+85x13+76x16.下料问题

现将1m长的钢切成A＝0.4m,B=0.3m，C=0.2m长的三种钢，其中A，B，C三种钢分别需要20根，45根和50根，问如何进行切割使得需要的1m钢为最少？解：将1m的钢分别切成A，B，C三种钢的可能方案如下：设第i种方案进行切割的1m钢的为xi根；minZ=0.1x3+0.1x5+0.1x7s.t.2x1+x2+x3+x4≥202x2+x3+3x5+2x6+x7≥45x1+x3+3x4+2x6+3x7+5x8≥50xi≥0(i=1,2……8)1/8/2023236.下料问题解：将1m的钢分别切成A，B，C三种钢小结线性规划问题要求目标函数和约束方程必须是线性函数，隐含如下假定：比例性假定：每个决策变量对目标函数的贡献与决策变量的值成比例。每个变量对约束条件左端的贡献与变量的值成比例；可加性假定：任何变量对目标函数的贡献都与其他决策变量的值无关。一个变量对每个约束条件左端的贡献与该变量的值无关。连续性假定（可除性假定）：允许每个决策变量值使用分数值。确定性假定：已经确切知道每个参数（价值系数，工艺系数，右侧常数）线性规划数学模型三个要素：决策变量目标函数约束条件1/8/202324小结线性规划问题要求目标函数和约束方程必须是线性函数，隐含如课堂习题P451.131.14(1)课后作业P461.14(2)1.151/8/202325课堂习题1/8/202325二、线性规划模型标准形式min(max)z=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≥(≤,＝)b1a21x1+a22x2+……+a2nxn≥(≤,＝)b2……am1x1+am2x2+……+amnxn≥(≤,＝)bmx1,x2,……,xn≥0(≤,Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：1.一般形式1/8/202326二、线性规划模型标准形式min(max)z=c1x1+c22.线性规划的标准形式目标函数为极大化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥01/8/2023272.线性规划的标准形式目标函数为极大化，约束条件全部为等号约3.线性规划模型用矩阵和向量表示maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥0价值系数工艺系数矩阵资源约束1/8/2023283.线性规划模型用矩阵和向量表示maxz=c1x1+c2x线性规划模型用矩阵和向量表示（续）因此，线性规划模型可以写成如下矩阵和向量的形式MaxZ=CXs.t.AX=bX≥01/8/202329线性规划模型用矩阵和向量表示（续）因此，线性规划模型可以写成4.线性规划模型总结线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,≤0,Free线性规划的标准形式目标函数：max约束条件 ：=变量符号 ：≥0MaxZ=CXs.t.AX=bX≥0

1/8/2023304.线性规划模型总结线性规划模型的结构MaxZ=CX1/5.线性规划问题的标准化极小化目标函数转化为极大化小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束变量没有符号限制（Free）的标准化变量小于等于0的标准化1/8/2023315.线性规划问题的标准化极小化目标函数转化为极大化1/8/2minz=2x1-3x2+x3令z’=-z，z’=-2x1+3x2-x3新的目标函数maxz’=-2x1+3x2-x3取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。极小化目标函数问题转化为极大化目标函数例如，对于以下两个线性规划问题Maxz=2x1+3x2s.t.x1+x2≤3x2≤1(A)x1,x2≥0Minz’=-2x1-3x2s.t.x1+x2≤3x2≤1(B)x1,x2≥0它们的最优解都是x1=2,x2=1，但(A)的最大化的目标函数值为maxz=7，(B)的最小化的目标函数值为minz’=-71/8/202332minz=2x1-3x2+x3极小化目标函数问题转化2x1+3x2-4x3≤5引进松弛变量(Slackvariable)x4≥02x1+3x2-4x3+x4=5如果有一个以上小于等于约束，要引进不同的松弛变量。例如：2x1+3x2-4x3≤53x1-2x2+5x3≤8在两个约束中分别引进松弛变量x4，x5≥02x1+3x2-4x3+x4=53x1-2x2+5x3+x5=8小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束将不等式约束变为等式约束。例如：2x1+3x2-4x3≥53x1-2x2+5x3≥8在两个约束的左边分别减去剩余变量x4，x5≥02x1+3x2-4x3-x4=53x1-2x2+5x3-x5=81/8/2023332x1+3x2-4x3≤5小于等于约束条件转化为等号没有符号限制的变量，用两个非负变量之差表示。例如：minz=x1+2x2-3x3s.t.2x1+3x2-4x3≤53x1-2x2+5x3≥8x1≥0,x2:free,x3≥0先将目标函数转化为极小化，并在约束中引进松弛变量，把不等式约束变为等式。Maxz’=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=53x1-2x2+5x3-x5=8x1≥0,x2:free,x3,x4,x5≥0变量没有符号限制(Free)的标准化1/8/202334没有符号限制的变量，用两个非负变量之差表示。例如：变量没有符 Maxz’=-x1-2x2+3x3 s.t.2x1+3x2-4x3+x4=5 3x1-2x2+5x3-x5=8x1≥0,x2:free,x3,x4,x5≥0然后，令x2=x2’-x2”，其中x2’,x2”≥0。代入模型，消去x2 Maxz’=-x1-2(x’2-x”2)+3x3 s.t.2x1+3(x’2-x”2)-4x3+x4=5 3x1-2(x’2-x”2)+5x3-x5=8 x1,x’2,x”2,x3,x4,x5≥0整理，得到标准形式： Maxz’=-x1-2x’2+x”2+3x3 s.t.2x1+3x’2-3x”2-4x3+x4=5 3x1-2x’2+2x”2+5x3-x5=8 x1,x’2,x”2,x3,x4,x5≥01/8/202335 Maxz’=-x1-2x2+3x31/8/202335 minz=x1+2x2-3x3 s.t.2x1+3x2-4x3≤5 3x1-2x2+5x3≥8 x1≥0,x2≤0,x3≥0 maxz’=-x1-2x2+3x3 s.t.2x1+3x2-4x3+x4=5 3x1-2x2+5x3-x5=8 x1≥0,x2≤0,x3,x4,x5≥0令x2=-x’2，x’2≥0,代入模型 maxz’=-x1+2x’2+3x3 s.t.2x1-3x’2-4x3+x4=5 3x1+2x’2+5x3-x5=8 x1≥0,x’2≥0,x3,x4,x5≥0变量小于等于0的的标准化1/8/202336 minz=x1+2x2-3x3变量小于等于0的的标准化1课堂习题P431.21/8/202337课堂习题1/8/2023371.2图解法相关概念和图解法步骤线性规划问题图解法求解的几种结果结论1/8/2023381.2图解法相关概念和图解法步骤1/8/202338模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。可行解：一个线性规划问题有解，是指能找出一组xj(j=1,2……,n)满足约束条件，称这组xj为问题的可行解。可行域：通常线性规划问题总是含有多个可行解，全部可行解的集合为可行域。最优解：可行域中使目标函数为最优的可行解为最优解。图解法的步骤：建立坐标系，确定比例尺；画出各约束条件的边界，定出可行域；画出目标函数的一根等值线，平移得出最优解；算出目标函数最优值。1.相关概念和图解法步骤1/8/202339模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法线性规划的图解max z=x1+3x2s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解654321123456-8-7-6-5-4-3-2-10x1x2z=6z=3z=9z=12问题：1、线性规划的最优解是否可能位于可行域的内部？2、线性规划的最优解是否可能位于可行域的边界上？1/8/202340线性规划的图解max z=x1+3x2可行域目标函数等值线唯一最优解无穷多最优解无界解（→可行域无界）无解（无可行解）2.线性规划问题图解法求解的几种结果1、唯一最优解（封闭）2、多个最优解（封闭）3、唯一最优解（开放）4、多个最优解（开放）5、目标函数无界（开放）6、无可行解1/8/202341唯一最优解2.线性规划问题图解法求解的几种结果1、唯一最优解线性规划问题解的形式:唯一最优解，无穷多最优解，无界解，无可行解；若LP的可行域存在，即有可行解，则可行域是一个凸集；若LP的最优解存在，则一定可以在可行域的某个顶点达到，如果在某两个顶点上达到最优，则该LP有无穷多最优解；用图解法求解LP时，如果可行域封闭，可比较可行域的顶点的目标函数值，得到最优解；注意用图解法如果可以得到封闭的可行域，则定有最优解存在；如果可行域不封闭，则解的三种形式都可能出现，必须用目标函数等值线的平移来判断。3.结论1/8/202342线性规划问题解的形式:唯一最优解，无穷多最优解，无界解，无可举例：1.maxZ=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0唯一最优解2.maxZ=x1+x2-2x1+x2≤4x1-x2≤2x1,x2≥0无界解3.maxZ=3x1+9x2x1+3x2≤22-x1+x2≤4x1,x2≥0无穷多最优解

4.maxZ=x1+x2x1+x2≤12x1+2x2≥4x1,x2≥0无解1/8/202343举例：3.maxZ=3x1+9x24.maxZ=x1+x课后作业P431.11/8/202344课后作业1/8/2023441.3单纯形法原理LP解的相关概念凸集及其顶点几个基本定理单纯形法迭代原理1/8/2023451.3单纯形法原理LP解的相关概念1/8/202345x3=0x4=0max

z=x1+2x2s.t.x1+x23x21x1,x20max

z=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,x2,x3,x40x1=0,x2=0x3=3,x4=1x1=0,x4=0x2=1,x3=2x2=0,x3=0x1=3,x4=1x3=0,x4=0x1=2,x2=1x1=0,x3=0x2=3,

x4=-2x2=0x1=0OABCD一.LP解的相关概念1.可行域，可行解，最优解1/8/202346x3=0x4=0maxz=x1+2x2maxz=x1+2LP问题数学模型因此：可行解：满足（1.7）（1.8）的解称为LP的可行解；可行域：全部可行解的集合；最优解：使目标函数(1.6)达到最大值的可行解1/8/202347LP问题数学模型因此：1/8/202347定义1：从n个变量中任取m个变量xi1,xi2,…,xim，若这m个变量对应的系数列向量Pi1,Pi2,…,Pim线性无关，即对应系数列向量行列式≠0，则称B=(Pi1,Pi2,…,Pim)为基矩阵，简称基，xi1,xi2,…,xim为基变量，其余n-m变量为非基变量。定义2：在约束方程(1.7)中，令所有非基变量为0，根据克莱姆法则，则(1.7)有唯一解。令xi1＝α1,xi2＝α2,…,xim＝αm，称为一组基解。基可行解：满足（1.8）中的基解为基可行解，即基解中每一分量均非负。可行基：基可行解对应的基。退化解：基变量中有分量为0的解。线性规划的基可行解就是可行域的顶点。2.基，基变量，非基变量；基解，基可行解，可行基1/8/202348定义1：从n个变量中任取m个变量xi1,xi2,…,xim，maxz=x1+2x2s.t.x1+x23x2

1x1,x2

0maxz=x1+2x2s.t.x1+x2+x3=3x2

+x4=1x1,x2,x3,x40x1=0,x2=0x3=3,x4=1基可行解x1=0,x4=0x2=1,x3=2基可行解x2=0,x3=0x1=3,x4=1基可行解x3=0,x4=0x1=2,x2=1基可行解x1=0,x3=0x2=3,x4=-2是基解，但不是可行解OABx3=0x4=0x2=0x1=0CD可行域1/8/202349maxz=x1+2x2maxz=x1+2x2x1=0,1.maxZ=2x1+3x2x1+x3＝5x1+2x2+x4＝10x2+

x5＝4xi≥0最优解为x1＝2，x2＝4，x3＝3，Z＝191/8/2023501.maxZ=2x1+3x2最优解为x1＝2，x2＝4，二.凸集和顶点1.凸集如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x1，x2的连线可以表示为：αx1＋（1－α）x2(0＜α＜1)数学解析式为：x1

∈C，x2

∈C，有αx1＋（1－α）x2∈C(0＜α＜1)，则C为凸集。2.顶点如果集合C中不存在任何两个不同的点x1，x2，使x为这两点连线上的一个点，称x为顶点。对任何x1

∈C，x2

∈C，不存在x=αx1＋（1－α）x2(0＜α＜1)，则称x为凸集的顶点。1/8/202351二.凸集和顶点1.凸集1/8/202351三.几个基本定理定理1：若线性规划问题存在可行解，则问题的可行域是凸集引理：线性规划问题的可行解X＝(x1,x2,……xn)为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇异的）。1/8/202352三.几个基本定理定理1：若线性规划问题存在可行解，则问题的可定理2：线性规划问题的基可行解X对应线性规划问题可行域的顶点。分两步：1）顶点→基可行解2）基可行解→顶点反证法：1）假设X0是可行域的顶点，X0不是基可行解，X0的前k个分量大于0，其余为0，因不是基可行解，则存在所以X0不是可行域的顶点，与假设矛盾，则X0必为基可行解。1/8/202353定理2：线性规划问题的基可行解X对应线性规划问题可行域的顶点2）假设X0是基可行解，X0不是顶点。假设X0是一个基可行解，设X0的前m个分量为正，令X0=(x1,x2,…,xm,0,…,0)T,因为不是顶点，则X0可以表示成另外两个点X(1)，X(2)的凸组合，且P1,…,Pm线性无关。所以X不能表示成可行域中另外两点的凸组合，与假设相矛盾，则X必为可行域的顶点。1/8/2023542）假设X0是基可行解，X0不是顶点。所以X不能表示成可行域定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。X0为LP的最优解，Z*=CX0，如果X0不是基可行解，则定有X(1)＝X0-ta,X(2)=X0+ta为可行解，则有CX(1)=CX0+tCa≤CX0CX(2)=CX0-tCa≤CX0则必有tCa=0所以X0，X(1)，X(2)均为最优解，如果X(1)，X(2)不是基可行解，继续下去，则必可以找到基可行解为最优解。1/8/202355定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解四.单纯形法迭代原理迭代基础：如果LP存在最优解，则一定有一个基可行最优解，且对应LP可行域的顶点。（可行，基解，最优）1.确定初始基可行解基解，可行解1/8/202356四.单纯形法迭代原理迭代基础：如果LP存在最优解，则一定有一2.最优性检验和解的判别非基变量检验数1/8/2023572.最优性检验和解的判别非基变量检验数1/8/202357由检验数可以判断解的最优性情况（1）因为所有Xj≥0，当所有σj<0时，则Z≤Z0,则该基可行解对应最优解；（2）因为所有Xj≥0，当σj≤

0且存在σj＝0（j=m+1,…,n)时，则该线性规划问题有无穷多最优解。（3）对基可行解X0,若存在某个σk>0,且所有aik≤0(Pj≤0),i=1,2,…,m，则该问题无界。（4）因为所有Xj≥0，当存在σj>0时，则该基可行解不是最优解，需要寻找另一个基可行解；1/8/202358由检验数可以判断解的最优性情况（4）因为所有Xj≥0，当存在3.基变换变换目的：使目标函数Z值得到改善，接近最优解，一次基变换，是从该顶点到相邻顶点，即一次基变换仅变换一个基变量。换入变量的确定σk>0,aik至少一个大于0，若σk=Max{σj|σj>0},则xk为换入变量。换出变量的确定令xk=θ>0,xj=0,j=m+1,…,n,j≠k则xi=bi-aik

θ≥0，i=1,…,m当aik

≤0时，θ可任取；当aik>0时，θ<则xl为换出变量。系数变换1/8/2023593.基变换变换目的：使目标函数Z值得到改善，接近最优解，一次以alk为主元进行初等行变换1/8/202360以alk为主元进行初等行变换1/8/202360习题1.8；1.61/8/202361习题1/8/2023611.4单纯形法计算步骤求初始基可行解最优性检验基变换1/8/2023621.4单纯形法计算步骤求初始基可行解1/8/202362单纯形法原理—单纯形法总结STEP0找到一个初始的基础可行解，确定基变量和非基变量。转STEP1。STEP1将目标函数和基变量分别用非基变量表示。转STEP2。STEP2如果目标函数中所有非基变量的检验数全部为非正数，则已经获得最优解，如果全为负数，则为唯一最优解，运算终止。；如果有为0的非基变量检验数，则有无穷多最优解。运算终止。如果有某非基变量检验数为正，且工艺系数全非正，则无界，运算终止。

否则，选取检验数为正数最大的非基变量进基。转STEP3。STEP3选择最小比值对应的基变量离基，进行系数初等行变换，得新的基可行解，转STEP1。1/8/202363单纯形法原理—单纯形法总结STEP0找到一个初始一.求初始基可行解1.当约束条件为“≤”时，直接在约束不等式左边加上非负的松弛变量，使约束方程的系数矩阵很容易找到一个单位矩阵，求出一个初始基可行解。2.当约束条件为“≥时，直接在约束不等式左边减去非负的剩余变量，此情况下很难找到一个单位矩阵，为求出初始基可行解，为此需要引入人工变量，以方便构成初始基可行解的一个基。为了不改变问题的性质，对引入人工变量Xi”的线性规划问题，需要在目标函数中减去MXi”,M为足够大的正数，称罚因子，促使Xi”最终必为0。3.当约束条件为”=“时，同样需要引入人工变量，以方便构成初始基可行解的一个基。目标函数需要减去罚因子。1/8/202364一.求初始基可行解1.当约束条件为“≤”时，直接在约束不等式二.最优性检验（1）若所有σj<0时，则已得唯一最优解，计算终止；如果基变量中存在非0人工变量，则无解。（2）当所有σj≤

0且存在σj＝0（j=m+1,…,n)时，则已得最优解，且有无穷多最优解，计算终止。（3）若存在某个σk>0,且所有aik≤0(Pj≤0),i=1,2,…,m，则该问题无界，计算终止。（4）当存在σj>0时，且有aik>0,继续第三步；1/8/202365二.最优性检验（1）若所有σj<0时，则已得唯一最优解，计算三.基变换用单纯形法按上述步骤求解时，可采用表格形式，这样更直观，易于避免错误，该表格称为单纯形表。1/8/202366三.基变换用单纯形法按上述步骤求解时，可采用表格形式，这样更例σj21000[]-45[]x1入，x4出σj01/30-1/30[]x2入，x5出3123/2[]σj000-1/4-1/2所以：X*=(x1,x2,x3)T=(7/2,3/2,15/2)TZ*=17/21/8/202367例σj21000[]-45[]x1入，x4出σ例:1.4(1)σj10500[]38/5[]x1入,x4出σj010-2[]x2入,x3出3/24σj00-5/14-25/14所以：X*=(x1,x2)T=(1,3/2)TZ*=35/2[]0:(0,0)C:(0,9/4)A:(8/5,0)B:(1,3/2)x1x2对应0对应A对应B1/8/202368例:1.4(1)σj10500[]38/5[课堂作业1.4(1)课后作业P431.4（2）1/8/202369课堂作业1/8/2023691.5单纯形法的进一步讨论一、人工变量法（大M法）约束条件：“≥”→减一个剩余变量后，再加一个人工变量“＝”→加一个人工变量目标函数：人工变量的系数为“－M”，即罚因子若线性规划问题有最优解则人工变量必为0。1/8/2023701.5单纯形法的进一步讨论一、人工变量法（大M法）1/8/MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3增加人工变量后，线性规划问题中就存在一个B为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。MaxZ=-3x1+x3-Mx6-Mx7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,7标准化及变形1/8/202371MaxZ=-3x1+x3增加人工变量后，线性规划问题中就存在单纯形表σj-3-2M4M100[]3x2入，x6出-M041[]σj6M-304M+10-4M[]-x1入，x7出3M011[]σj0030-M-3/2[]9x3入，x1出3/2-M+1/23/2-[]σj-9/2000-M+3/4-3/4-M-1/4所以：X*=(x2,x3,x4)T=(5/2,3/2,0)TZ*=3/21/8/202372单纯形表σj-3-2M4M100[]3x2入，x6出二、两阶段法第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。当第一阶段中目标函数的最优值＝0，既人工变量＝0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，既人工变量不等于0，则判断原问题为无解。第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。1/8/202373二、两阶段法1/8/202373求解辅助问题，得到辅助问题的最优解引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化MaxW=0?原问题没有可行解。把辅助问题的最优解作为原问题的初始基础可行解用单纯形法求解原问题，得到原问题的最优解否是两阶段法的算法流程图MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3MaxW=-x6-x7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,71/8/202374求解辅助问题，得到辅助问题的最优解引进人工变量x6，x7，构(第一阶段）单纯形表1σj-24000[]3x2入，x6出-1041[]σj6040-4[]－x1入，x7出3011[]σj0000-10-1所以：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。1/8/202375(第一阶段）单纯形表1σj-24000[]3x2入，（第二阶段）单纯形表2σj00303/2[]-93/2[]x3入，x1出σj-9/2000-3/4所以：X*=(x2,x3,x4)T=(5/2,3/2,0)TZ*=3/21/8/202376（第二阶段）单纯形表2σj00303/2[]-93/2目标函数极小化时解的最优性判别；退化解的判别；无可行解的判别；无界的判别；无穷多最优解的判别；唯一最优解的判别.三、单纯形法计算中的几个问题当所有非基变量的σj≥0时为最优解；最优解中基变量有取值为0的值时；最优解中人工变量为非0的基变量时；存在某个σk>0，且所有的aik≤0时；得最优解时，有检验数为0的非基变量；得最优解时，所有非基变量检验数为负；1/8/202377目标函数极小化时解的最优性判别；三、单纯形法计算中的几个问题σj4045025100/340[3]x2入，x3出σj000-5因为σj全≥0,且σ1=0,则有无穷多最优解。

所以：X*=(0,80/3,20,0,0),Z*=1700例:0-10……1/8/202378σj4045025100/340[3]x2入，x3出σσj1100-50[]x1入，x4出σj020-1因为σ2=2,且ai2全≥0

所以：无界例:1/8/202379σj1100-50[]x1入，x4出σj020-例:下表为一极大化问题对应的单纯形表讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解为：唯一最优解；无穷多最优解；退化解；无界；无可行解；X3换入，x2换出A4<0,a5<0,a6≥0a6≥0,a4≤0,a5≤0a4.a5=0a4≤0,a5≤0,a6=0a6≥0,a5>0,a2≤0,a3≤0a4≤0,a5≤0,x4或x2为人工变量，a6≥0；x1为人工变量a6>0A4>0,a4>a5;a6/a1>2→a1>0a6≥0→a1≤01/8/202380例:下表为一极大化问题对应的单纯形表讨论在a1,a2,a3,课后作业P431.71/8/202381课后作业1/8/202381运筹学——管理科学与工程系经济与管理学院浙江科技学院经济管理学院管工系运筹学——管课堂要求1.要求学生上课不迟到，不早退，不得旷课；2.上课认真听讲，要求每位同学都做笔记；3.上课不得讲话，看书，玩手机等与课堂无关的内容；4.课后要求独自完成作业，不得抄袭或不做课后作业。1/8/202383课堂要求1.要求学生上课不迟到，不早退，不得旷课；1/8/2参考资料1.胡运权主编，运筹学教程（第三版），清华大学出版社；2.周华任主编，运筹学解题指导，清华大学出版社；3.运筹学习题集（修订版），清华大学出版社；4.熊伟编著，运筹学，机械工业出版社；5.运筹学——数据、模型、决策，科学出版社。1/8/202384参考资料1.胡运权主编，运筹学教程（第三版），清华大学出版社前言—运筹学简介运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。求解结果….求解结果….建立模型求解模型修改模型求解结果….修改模型实际问题数学模型1/8/202385前言—运筹学简介运筹学是管理科学的重要理论基础和应用手段，是运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是OperationalResearch，在美国称为OperationsResearch。1/8/202386运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，OperationsResearch就转义成为“作业研究”。我国把OperationsResearch译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、对偶问题，整数规划、运输问题、动态规划、图与网络分析。1/8/202387战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划授课主要内容目录：绪论（1）第一章 线性规划（12）第二章 对偶问题（10）第三章 运输问题（6）第五章 整数规划（6）第七章 动态规划（8）第八章图与网络分析（8）上课总课时：51课时课程设计1周（下学期开学前）1/8/202388授课主要内容目录：上课总课时：51课时课程设计1周（下学第一章线性规划及单纯形法1.1线性规划问题及其数学模型1.2图解法1.3单纯形法原理1.4单纯形法计算步骤1.5单纯形法进一步讨论1/8/202389第一章线性规划及单纯形法1.1线性规划问题及其数学模型本章学习要求能建立实际问题的数学规划模型理解线性规划模型的特点，标准型掌握线性规划的图解法及其几何意义掌握单纯形法原理掌握运用单纯形表计算线性规划问题的步骤及解法能用二阶段法和大M法求解线性规划问题。掌握任何基可行解原表及单纯形表的对应关系1/8/202390本章学习要求能建立实际问题的数学规划模型1/8/202391.1线性规划问题及其数学模型举例说明线性规划数学模型的标准形式1/8/2023911.1线性规划问题及其数学模型举例说明1/8/202310一、线性规划问题举例说明生产计划问题配料问题背包问题运输问题指派问题下料问题1/8/202392一、线性规划问题举例说明生产计划问题1/8/202311例1：美佳公司－生产计划问题1、确定决策变量——通常由目标问题分解设x1代表生产Ⅰ种家电数量；x2代表生产Ⅱ种家电数量；2、分析并表达限制条件，包括约束条件——通常由等式或不等式表示。0x1+5x2≤156x1+2x2≤24x1+x2≤5x1≥0,x2≥03、分析目标——是利润最大化MaxZ=2x1+x21/8/202393例1：美佳公司－生产计划问题1、确定决策变量——通常由目标问例2：捷运公司表1－2所需仓库面积1、确定决策变量——通常由目标问题分解每个月有不同的租用方案，共有4个月需要租用仓库。则：表1－3租金与期限的关系1/8/202394例2：捷运公司表1－21、确定决策变量——通常由目标问题分1.生产计划问题（ProductionPlanning）某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：maxz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1,x2,x3,x4≥01/8/2023951.生产计划问题（ProductionPlanning）2.配料问题（MaterialBlending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（％），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（％）如下表：要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。minz=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.76x4≥3.20Cr的含量下限约束2.04x1+1.12x2+3.57x3+4.33x4≥2.10Mn的含量下限约束5.82x1+3.06x2+4.27x3+2.73x4≥4.30Ni的含量下限约束x1+x2+x3+x4=100物料平衡约束x1,x2,x3,x4≥01/8/2023962.配料问题（MaterialBlending）某工厂要3.背包问题（KnapsackProblem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。设三种物品的件数各为x1，x2，x3件，总价值为z。maxz=17x1+72x2+35x3s.t.10x1+41x2+20x3≤50x1，x2，x3≥0x1，x2，x3为整数这是一个整数规划问题（IntegerProgramming）。这个问题的最优解为：x1=1件，x2=0件，x3=2件，最高价值z=87元1/8/2023973.背包问题（KnapsackProblem）一只背包最4.运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：求总运费最低的运输方案。A1A2B3B2B135吨25吨10吨30吨20吨2354781/8/2023984.运输问题（Transportation）某种物资从两个设从两个供应地到三个需求地的运量（吨）如下表：minz=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35供应地A1x21+x22+x23=25供应地A2x11+x21=10需求地B1x12+x22=30需求地B2x13+x23=20需求地B3x11,x12,x13,x21,x22,x23≥01/8/202399设从两个供应地到三个需求地的运量（吨）如下表：minz=2这个问题的最优解表示如下：最小总运费为：z=3×30+5×5+4×10+8×15=275元A1A2B3B2B135吨25吨10吨30吨20吨23547830吨5吨10吨15吨1/8/2023100这个问题的最优解表示如下：最小总运费为：z=3×30+5×55.指派问题（AssignmentProblem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：1/8/20231015.指派问题（AssignmentProblem）有n项张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。设：1/8/2023102张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，设：maxz=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44s.t. x11+x12+x13+x14=1(1)x21+x22+x23+x24=1(2)x31+x32+x33+x34=1(3)x41+x42+x43+x44=1(4)x11+x21+x31+x41=1(5)x12+x22+x32+x42=1(6)x13+x23+x33+x43=1(7)x14+x24+x34+x44=1(8)xij=0,11/8/2023103设：maxz=92x11+68x12+85x13+76x16.下料问题

现将1m长的钢切成A＝0.4m,B=0.3m，C=0.2m长的三种钢，其中A，B，C三种钢分别需要20根，45根和50根，问如何进行切割使得需要的1m钢为最少？解：将1m的钢分别切成A，B，C三种钢的可能方案如下：设第i种方案进行切割的1m钢的为xi根；minZ=0.1x3+0.1x5+0.1x7s.t.2x1+x2+x3+x4≥202x2+x3+3x5+2x6+x7≥45x1+x3+3x4+2x6+3x7+5x8≥50xi≥0(i=1,2……8)1/8/20231046.下料问题解：将1m的钢分别切成A，B，C三种钢小结线性规划问题要求目标函数和约束方程必须是线性函数，隐含如下假定：比例性假定：每个决策变量对目标函数的贡献与决策变量的值成比例。每个变量对约束条件左端的贡献与变量的值成比例；可加性假定：任何变量对目标函数的贡献都与其他决策变量的值无关。一个变量对每个约束条件左端的贡献与该变量的值无关。连续性假定（可除性假定）：允许每个决策变量值使用分数值。确定性假定：已经确切知道每个参数（价值系数，工艺系数，右侧常数）线性规划数学模型三个要素：决策变量目标函数约束条件1/8/2023105小结线性规划问题要求目标函数和约束方程必须是线性函数，隐含如课堂习题P451.131.14(1)课后作业P461.14(2)1.151/8/2023106课堂习题1/8/202325二、线性规划模型标准形式min(max)z=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≥(≤,＝)b1a21x1+a22x2+……+a2nxn≥(≤,＝)b2……am1x1+am2x2+……+amnxn≥(≤,＝)bmx1,x2,……,xn≥0(≤,Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：1.一般形式1/8/2023107二、线性规划模型标准形式min(max)z=c1x1+c22.线性规划的标准形式目标函数为极大化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥01/8/20231082.线性规划的标准形式目标函数为极大化，约束条件全部为等号约3.线性规划模型用矩阵和向量表示maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x