大学精品课件：第一章 线性规划.ppt

1、2023-3-11运筹学运筹学电子讲义电子讲义 管理科学与工程系管理科学与工程系 经济与管理学院经济与管理学院2023-3-12课堂要求课堂要求1.要求学生上课不迟到，不早退，不得旷要求学生上课不迟到，不早退，不得旷课；课；2.上课认真听讲，要求每位同学都做笔记；上课认真听讲，要求每位同学都做笔记；3.上课不得讲话，看书，玩手机等与课堂上课不得讲话，看书，玩手机等与课堂无关的内容；无关的内容；4.课后要求独自完成作业，不得抄袭或不课后要求独自完成作业，不得抄袭或不做课后作业。做课后作业。2023-3-13参考资料参考资料1.胡运权主编，运筹学教程（第三版），清华大学胡运权主编，运筹学教程（第三

2、版），清华大学出版社；出版社；2.周华任主编，运筹学解题指导，清华大学出版社；周华任主编，运筹学解题指导，清华大学出版社；3.运筹学习题集（修订版），清华大学出版社；运筹学习题集（修订版），清华大学出版社；4.熊伟编著，运筹学，机械工业出版社；熊伟编著，运筹学，机械工业出版社；5.运筹学运筹学数据、模型、决策，科学出版社。数据、模型、决策，科学出版社。2023-3-14绪论绪论一、运筹学的产生与发展一、运筹学的产生与发展二、运筹学的定义二、运筹学的定义“Operational Research”,简称简称“OR”“运筹学是应用分析、实验、量化的方法，对管运筹学是应用分析、实验、量化的方法，对管

3、理系统中人力、物力、财力等资源进行统筹安理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现排，为决策者提供有依据的最优方案，以实现最有效的管理最有效的管理”我国管理百科全书我国管理百科全书2023-3-15三、运筹学研究的基本方法三、运筹学研究的基本方法分析和表述问题分析和表述问题建立模型建立模型实施实施检验检验确定模型确定模型的有效范围的有效范围不通过不通过通过通过求解模型求解模型2023-3-16四、运筹学研究的主要内容四、运筹学研究的主要内容 线性规划线性规划 运输问题运输问题 多目标规划多目标规划 整数规划整数规划 非线性规划非线性规划 动态规划动态规划

4、图与网络分析图与网络分析 网络计划网络计划 排队论排队论 库存理论库存理论 对策论对策论 决策分析决策分析2023-3-17目录：目录：p第一章第一章线性规划线性规划p第二章第二章对偶问题对偶问题p第三章第三章运输问题运输问题p第四章第四章整数规划整数规划p第五章第五章动态规划动态规划p第六章第六章图与网络分析图与网络分析2023-3-18五、运筹学在经济管理中应用的主要课题五、运筹学在经济管理中应用的主要课题 生产计划生产计划 库存管理库存管理 运输问题运输问题 人事管理人事管理 市场营销市场营销 财务和会计财务和会计2023-3-19第一章第一章 线性规划线性规划p线性规划问题线性规划问题

5、p线性规划模型线性规划模型p线性规划的图解法线性规划的图解法p可行域的性质可行域的性质p线性规划的基本概念线性规划的基本概念p基础解、基础可行解基础解、基础可行解p单纯形求解单纯形求解2023-3-110第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型一、线性规划问题的引入一、线性规划问题的引入n生产计划问题生产计划问题n配料问题配料问题n背包问题背包问题n运输问题运输问题n指派问题指派问题n下料问题下料问题2023-3-1111.生产计划问题（生产计划问题（Production Planning）产品甲产品甲产品乙产品乙产品丙产品丙产品丁产品丁设备能力设备能力（小时）（小时）设

6、备设备A1.51.02.41.02000设备设备B1.05.01.03.58000设备设备C1.53.03.51.05000利润（元利润（元/件）件）5.247.308.344.18某工厂拥有某工厂拥有A、B、C三种类型的设备，生产甲、乙、三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：用的时数如下表所示：求使得总利润最大的生产计划。求使得总利润最大的生产计划。2023-3-112设四种产品的产量分别为设四种产品

7、的产量分别为x1，x2，x3，x4，总利润为总利润为z，线性规划模型为：，线性规划模型为：Maxz=5.24x1+7.30 x2+8.34x3+4.18x4s.t.1.5x1+1.0 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.5x1+3.0 x2+3.5x3+1.0 x45000 x1,x2,x3,x40目标函数目标函数资源约束条件资源约束条件变量非负约束变量非负约束这个问题的最优解为：这个问题的最优解为：x1=294.12件，件，x2=1500件，件，x3=0，x4=58.82件件最大利润为：最大利润为：z=12737.06元。

8、元。产品甲产品甲产品乙产品乙产品丙产品丙产品丁产品丁设备能力设备能力（小时）（小时）设备设备A1.51.02.41.02000设备设备B1.05.01.03.58000设备设备C1.53.03.51.05000利润（元利润（元/件）件）5.247.308.344.18决策变量决策变量2023-3-1132.配料问题（配料问题（Material Blending）某工厂要用四种合金某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为原料，经熔炼成为新的不锈钢为新的不锈钢G。这四种原料含铬（。这四种原料含铬（Cr）、锰（）、锰（Mn）和）和镍（镍（Ni）的含量（），这四种原料的单价以及新的不

9、）的含量（），这四种原料的单价以及新的不锈钢锈钢G所要求的所要求的Cr、Mn、Ni的最低含量（）如下表：的最低含量（）如下表：T1T2T3T4GCr3.214.532.191.76320Mn2.041.123.574.33210Ni5.823.064.272.73430单价（元单价（元/公斤）公斤）115978276要求配要求配100公斤不锈钢公斤不锈钢G，并假定在配制过程中没有损，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。耗。求使得总成本最低的配料方案。2023-3-114min z=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.

10、76x4320 Cr的含量下限约束的含量下限约束 2.04x1+1.12x2+3.57x3+4.33x4210 Mn的含量下限约束的含量下限约束 5.82x1+3.06x2+4.27x3+2.73x4430 Ni的含量下限约束的含量下限约束 x1+x2+x3+x4=100 物料平衡约束物料平衡约束 x1,x2,x3,x40设四种原料分别选取设四种原料分别选取x1，x2，x3，x4公斤，总成本为公斤，总成本为z。这个问题的最优解为：这个问题的最优解为：x1=26.58,x2=31.57,x3=41.84，x4=0（公斤）（公斤）,最低成本为最低成本为z=9549.87元。元。问题：如果某一种成分

11、的含量既有下限，又有上限怎么办？问题：如果某一种成分的含量既有下限，又有上限怎么办？T1T2T3T4GCr3.214.532.191.76320Mn2.041.123.574.33210Ni5.823.064.272.73430单价（元单价（元/公斤）公斤）1159782762023-3-1153.背包问题（背包问题（Knapsack Problem）一只背包最大装载重量为一只背包最大装载重量为50公斤。现有三种物品，每公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：种物品数量无限。每种物品每件的重量、价格如下表：物品物品1物品物品2物品物品3重量（公斤重量（公斤/件）件

12、）104120价值（元价值（元/件）件）177235求背包中装入每种物品各多少件，使背包中物品总价值求背包中装入每种物品各多少件，使背包中物品总价值最高。最高。2023-3-116设三种物品的件数各为设三种物品的件数各为x1，x2，x3件，总价值为件，总价值为z。max z=17x1+72x2+35x3s.t.10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数为整数这是一个整数规划问题（这是一个整数规划问题（Integer Programming）。）。这个问题的最优解为：这个问题的最优解为：x1=1件，件，x2=0件，件，x3=2件，最高价值件，最高价值z=87

13、元元物品物品1物品物品2物品物品3重量（公斤重量（公斤/件）件）104120价值（元价值（元/件）件）1772352023-3-1174.运输问题（运输问题（Transportation）某种物资从两个供应地某种物资从两个供应地A1，A2运往三个需求地运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：应地到每个需求地每吨物资的运输价格如下表：运价（元运价（元/吨）吨）B1B2B3供应量（吨）供应量（吨）A123535A247825需求量（吨）需求量（吨）10302060求总运费最低的运

14、输方案。求总运费最低的运输方案。2023-3-118A1A2B3B2B135吨吨25吨吨10吨吨30吨吨20吨吨235478运价（元运价（元/吨）吨）B1B2B3供应量（吨）供应量（吨）A123535A247825需求量（吨）需求量（吨）103020602023-3-119设从两个供应地到三个需求地的运量（吨）如下表：设从两个供应地到三个需求地的运量（吨）如下表：B1B2B3A1x11x12x13A2x21x22x23运价（元运价（元/吨）吨）B1B2B3供应量（吨）供应量（吨）A123535A247825需求量（吨）需求量（吨）103020602023-3-120min z=2x11+3x1

15、2+5x13+4x21+7x22+8x23s.t.x11+x12+x13 =35 供应地供应地A1 x21+x22+x23=25 供应地供应地A2 x11 +x21 =10 需求地需求地B1 x12 +x22 =30 需求地需求地B2 x13 +x23=20 需求地需求地B3 x11,x12,x13,x21,x22,x230 运价（元运价（元/吨）吨）B1B2B3供应量（吨）供应量（吨）A123535A247825需求量（吨）需求量（吨）103020602023-3-121运量（吨）运量（吨）B1B2B3供应量（吨）供应量（吨）A130535A2101525需求量（吨）需求量（吨）103020

16、60这个问题的最优解表示如下：这个问题的最优解表示如下：最小总运费为：最小总运费为：z=330+55+410+815=275元元A1A2B3B2B135吨吨25吨吨10吨吨30吨吨20吨吨23547830吨吨5吨吨10吨吨15吨吨2023-3-1225.指派问题（指派问题（Assignment Problem）有有n项任务由项任务由n个人完成，每项任务交给一个人，每人都有一项任个人完成，每项任务交给一个人，每人都有一项任务。由务。由i个人完成个人完成j项任务的成本（或效益）为项任务的成本（或效益）为cij。求使总成本最。求使总成本最小（或总效益最大）的分配方案。小（或总效益最大）的分配方案。设

17、：设：项任务个人被指派完成第第项任务个人不从事第第ji1ji0 xij102112111111,xm,.,ixn,.,jx.t.sxczmax(min)ijnjijmiijninjijij2023-3-123张、王、李、赵四位老师被分配教语文、数学、物理化学张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四平均成绩如下表。要求确定哪一位老师上哪一门

18、课，使四门课的平均总成绩最高。门课的平均总成绩最高。语文语文数学数学物理物理化学化学张张92688576王王82917763李李83907465赵赵936183752023-3-124门课个老师教第第门课个老师不教第第ji1ji0 xij设：设：语文语文数学数学物理物理化学化学张张x11x12x13x14王王x21x22x23x24李李x31x32x33x34赵赵x41x42x43x44max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t

19、.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,12023-3-125最优解为：最优解为：x14=1，x23=1，x32=1，x41=1，max z=336即张老师教化学，王老师教语文，李老师教数学，赵老师即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。教语文。语文语文数学数学物理物理化

20、学化学张张0001王王0010李李0100赵赵1000四门课的总分可以达到四门课的总分可以达到336分。分。语文语文数学数学物理物理化学化学张张92688576王王82917763李李83907465赵赵936183752023-3-1266.下料问题下料问题 现将现将1m长的钢切成长的钢切成A0.4m,B=0.3m，C=0.2m长的三种长的三种钢，其中钢，其中A，B，C三种钢分别需要三种钢分别需要20根，根，45根和根和50根，根，问如何进行切割使得需要的问如何进行切割使得需要的1m钢为最少？钢为最少？2023-3-127 解：将解：将1m的钢分别切成的钢分别切成A，B，C三种钢的可能方三种

21、钢的可能方案如下：案如下：方案方案12345678A21110000B02103210C10130235剩料剩料000.100.100.10设第设第i种方案进行切割的种方案进行切割的1m钢的为钢的为xj根；根；minZ=x1+x2+x8 s.t.2x1+x2+x3+x420 2x2+x3+3x5+2x6+x745 x1+x3+3x4+2x6+3x7+5x850 xj 0(i=1,28)2023-3-128二、线性规划一般模型二、线性规划一般模型1、三个要素：、三个要素：决策变量、目标函数、约束条件决策变量、目标函数、约束条件2、一般表达式：、一般表达式：max(min)z=c1x1+c2x2+

22、cnxns.t.a11x1+a12x2+a1nxn (,)b1 a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn (,)bm x1,x2,xn 0(,Free)2023-3-129线性规划模型的目标函数必须是线性规划模型的目标函数必须是变量的线性函数，约束条件必须变量的线性函数，约束条件必须是变量的线性等式或不等式。如是变量的线性等式或不等式。如右的问题就不是线性规划问题：右的问题就不是线性规划问题：0 x,x,x9x4+x+x8xx+x+x2.t.sxx2+x3=zmin32132113212121几个习惯称呼：几个习惯称呼：目标函数：目标函数：z=cz=c

23、1 1x x1 1+c+c2 2x x2 2+c+cn nx xn n价值系数：价值系数：cj(j=1,n)单位活动单位活动J的效益的效益价值向量：价值向量：C=（c1，c2，cn）技术系数：技术系数：ai单位第单位第j种活动消耗第种活动消耗第i种资源的数量种资源的数量技术矩阵：技术矩阵：A=（aij）mn右端常数：右端常数：bi第第i种资源分配的可利用量种资源分配的可利用量右端向量：右端向量：b=（b1，b2，bm）T2023-3-130三、线性规划的标准形式三、线性规划的标准形式1、定义、定义目标函数为极大化，约束条件全部为等号约束，所目标函数为极大化，约束条件全部为等号约束，所有变量全部

24、是非负的，这样的线性规划模型称为标有变量全部是非负的，这样的线性规划模型称为标准形式准形式maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 2023-3-131线性规划模型标准形式用矩阵和向量表示线性规划模型标准形式用矩阵和向量表示mnmmnnaaaaaaaaaA212222111211m21bbbbncccC,.,21n21xxxX2023-3-132线性规划模型标准形式用矩阵和向量表示（续）线性规划模型标准形式用矩阵和向量表示（续）nnnnxcxc

25、xcxxxcccCXz22112121bbbbxaxaxaxaxaxaxaxaxaxxxaaaaaaaaaAXmnmnmmnnnnnmnmmnn.2122112222121121211121212222111211因此，线性规划模型可以写成如下矩阵和向量的形式因此，线性规划模型可以写成如下矩阵和向量的形式MaxZ =CXs.t.AX=b X0 2023-3-1332、线性规划问题的标准化线性规划问题的标准化极小化目标函数转化为极大化极小化目标函数转化为极大化小于等于约束条件转化为等号约束小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束大于等于约束条件转化为等号约束变量没有符号限制（

26、变量没有符号限制（Free）的标准化）的标准化变量小于等于变量小于等于0的标准化的标准化2023-3-134 min z=2x1-3x2+x3令令 z=-z，z=-2x1+3x2-x3新的目标函数新的目标函数 max z=-2x1+3x2-x3取得极小化的最优解时，这个最优解同时使原目标函数取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。值相差一个负号。极小化目标函数问题转化为极大化目标函数极小化目标函数问题转化为极大化目标函数2023-3-135例如，对于以下两个线性规划问题例如，

27、对于以下两个线性规划问题min z=2x1+3x2s.t.x1+x23 x21 (A)x1,x20max z=-2x1-3x2s.t.x1+x23 x21 (B)x1,x20它们的最优解都是它们的最优解都是x1=2,x2=1，但，但(A)的最大化的目标函数的最大化的目标函数值为值为max z=7，(B)的最小化的目标函数值为的最小化的目标函数值为min z=-72023-3-136 2x1+3x2-4x35引进松弛变量引进松弛变量(Slack variable)x4=5-(2x1+3x2-4x3)，把松弛变量，把松弛变量x4加在约束条件左边，就可以将小加在约束条件左边，就可以将小于等于约束变为

28、等式。于等于约束变为等式。2x1+3x2-4x3+x4=5由此可以知道，松弛变量由此可以知道，松弛变量x40。如果有一个以上小于。如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。等于约束，要对于每一个约束引进不同的松弛变量。例如：例如：2x1+3x2-4x35 3x1-2x2+5x38在两个约束中分别引进松弛变量在两个约束中分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8小于等于约束条件转化为等号约束小于等于约束条件转化为等号约束2023-3-137将不等式约束变为等式约束。例如：将不等式约束变为等式约束。例如：2x1+3x2

29、-4x35 3x1-2x2+5x38在两个约束的左边分别减去剩余变量在两个约束的左边分别减去剩余变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8强调：在标准化的过程中我们为了使约束条件变为等强调：在标准化的过程中我们为了使约束条件变为等号约束而人为加上的松驰变量和剩余变量在实际中没号约束而人为加上的松驰变量和剩余变量在实际中没有意义，所以它们的价值系数都为有意义，所以它们的价值系数都为0。大于等于约束条件转化为等号约束大于等于约束条件转化为等号约束2023-3-138没有符号限制的变量，用两个非负变量之差表示。例如：没有符号限制的变量，用两个非负变量之差

30、表示。例如：min z=x1+2x2-3x3s.t.2x1+3x2-4x35 3x1-2x2+5x38 x10,x2:free,x30先将目标函数转化为极大化，并在约束中引进松弛变量和先将目标函数转化为极大化，并在约束中引进松弛变量和剩余变量，把不等式约束变为等式。剩余变量，把不等式约束变为等式。Max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10,x2:free,x3,x4,x50变量没有符号限制变量没有符号限制(Free)的标准化的标准化2023-3-139Max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+

31、x4 =5 3x1-2x2+5x3-x5=8 x10,x2:free,x3,x4,x50然后，令然后，令x2=x2-x2”，其中，其中x2,x2”0。代入模型，消去。代入模型，消去x2Max z=-x1-2(x2-x”2)+3x3s.t.2x1+3(x2-x”2)-4x3+x4 =5 3x1-2(x2-x”2)+5x3 -x5=8 x1,x2,x”2,x3,x4,x50整理，得到标准形式：整理，得到标准形式：Max z=-x1-2x2+x”2+3x3s.t.2x1+3x2-3x”2-4x3+x4 =5 3x1-2x2+2x”2+5x3 -x5=8 x1,x2,x”2,x3,x4,x502023

32、-3-140min z=x1+2x2-3x3s.t.2x1+3x2-4x35 3x1-2x2+5x38 x10,x20,x30max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10,x20,x3,x4,x50令令 x2=-x2，x20,代入模型代入模型max z=-x1+2x2+3x3s.t.2x1-3x2-4x3+x4 =5 3x1+2x2+5x3 -x5=8 x10,x20,x3,x4,x50变量小于等于变量小于等于0 0的的标准化的的标准化2023-3-141线性规划模型总结线性规划模型总结线性规划模型的结构线性规划模型的

33、结构n目标函数目标函数：max，minn约束条件：约束条件：,=,n变量符号：变量符号：0,0,Free线性规划的标准形式线性规划的标准形式n目标函数：目标函数：maxn约束条件约束条件：=n变量符号变量符号：0FreeXbAXt sCXz,0)(),(.max(min)MaxZ =CXs.t.AX=b X0 2023-3-142第二节第二节 图解法图解法 适用范围适用范围：对于模型中只有两个变量的线性规：对于模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。划问题，可以通过在平面上作图的方法求解。可行解可行解：一个线性规划问题有解，是指能找出一：一个线性规划问题有解，是指能找

34、出一组组xj(j=1,2,n)，满足约束条件，称这组，满足约束条件，称这组xj为问为问题的可行解。题的可行解。可行域可行域：通常线性规划问题总是含有多个可行解，：通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域。称全部可行解的集合为可行域。最优解最优解：可行域中使目标函数为最优的可行解为：可行域中使目标函数为最优的可行解为最优解。最优解。图解法的思路图解法的思路：在二维坐标系中先找出问题的：在二维坐标系中先找出问题的可行域可行域,然后在可行域中利用目标函数等值线求出然后在可行域中利用目标函数等值线求出最优解。最优解。2023-3-143线性规划的图解法线性规划的图解法 max z

35、=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域可行域目标函数等值线目标函数等值线最优解最优解6543211 2 3 4 5 6-8 -7 -6 -5 -4 -3-2 -1 0 x1x2z=6z=3z=9z=12问题：问题：1、线性规划的最优解是否可能位于可行域的内部？、线性规划的最优解是否可能位于可行域的内部？2、线性规划的最优解是否可能位于可行域的边界上？、线性规划的最优解是否可能位于可行域的边界上？2023-3-144线性规划可行域和最优解的几种情况线性规划可行域和最优解的几种情况1、可行域封闭、可行域封闭 唯一最优解唯一最优解2、可行域封闭、可行域封闭 多个最优

36、解多个最优解3、可行域开放、可行域开放 唯一最优解唯一最优解4、可行域开放、可行域开放 多个最优解多个最优解5、可行域开放、可行域开放 目标函数无界目标函数无界6、无可行解、无可行解2023-3-145举例：举例：1.maxZ=2x1+x2 5x215 6x1+2x2 24 x1+x2 5 x1,x20唯一最优解唯一最优解2.maxZ=x1+x2 -2x1+x2 4 x1-x2 2 x1,x20无界解无界解 3.maxZ=3x1+9x2 x1+3x2 22 -x1+x2 4 x1,x20无穷多最优解无穷多最优解 4.maxZ=x1+x2 x1+x2 1 2x1+2x24 x1,x20无解无解2

37、023-3-146解的可行性和松弛变量符号的关系解的可行性和松弛变量符号的关系A(1,2.5)B(2,1)C(1.5,3)max z=2x1+3x2s.t.x1+x24 (1)-x1+x21 (2)x1,x20max z=2x1+3x2s.t.x1+x2+x3 =4 -x1+x2 -x4=1 x1,x2,x3,x40引进松引进松弛变量弛变量约束条件约束条件(1)约束条件约束条件(2)D(3,2)A(1,2.5)满足所有约束条件，满足所有约束条件，x3=0.5,x4=0.5B(2,1)满足满足(1)，不满足，不满足(2)，x3=1,x4=-2C(1.5,3)不满足不满足(1),满足满足(2)，x

38、3=-0.5,x4=0.5D(3,2)不满足不满足(1)和和(2)，x3=-1,x4=-2结论：如果一个解满足一个约束条件，相应结论：如果一个解满足一个约束条件，相应的松弛变量大于等于的松弛变量大于等于0。如果一个解不满足。如果一个解不满足一个约束条件，相应的松弛变量小于一个约束条件，相应的松弛变量小于0。0 1 2 3 4-14321x2x12023-3-147第三节第三节 单纯形法原理单纯形法原理一、一、LP问题的解的概念问题的解的概念1、可行解：满足约束条件的解、可行解：满足约束条件的解X叫可行解。叫可行解。可行域：由所有可行解组成的集合。可行域：由所有可行解组成的集合。2、最优解：使目

39、标函数达到最优的可行解。、最优解：使目标函数达到最优的可行解。3、基：设技术矩阵、基：设技术矩阵Amn的秩为的秩为m(设设nm),即即R（A）=m，B是是A的一个的一个mm阶的满秩子矩阶的满秩子矩阵，就称阵，就称B是是LP问题的一个基。问题的一个基。),.,(21212222111211mmmmmmmpppaaaaaaaaaB2023-3-148补充补充:矩阵及其秩矩阵及其秩 向量组的线性无关与线性相关向量组的线性无关与线性相关 给定向量组给定向量组A:a1,a2,am,如果存在不全为零如果存在不全为零的数的数 k1,k2,km,使使k1 a1+k2 a2+km am=0，则称向量组，则称向量

40、组A是线性相关的是线性相关的,否则称它是线性否则称它是线性无关。无关。矩阵的秩矩阵的秩 若矩阵若矩阵A的的n个列向量中有个列向量中有r 个线性无关（个线性无关（r=n）。）。而所有个数大于而所有个数大于r的列向量组都线性相关，则称数的列向量组都线性相关，则称数r为矩阵为矩阵A的秩，记的秩，记R(A)=r。2023-3-1494、基向量：其中所对应的向量、基向量：其中所对应的向量 p1，pm 非基向量：其余向量非基向量：其余向量 pm+1，pn5、基变量：基向量所对应的变量。、基变量：基向量所对应的变量。XB=（x1，xm）非基变量：非基向量所对应的变量。非基变量：非基向量所对应的变量。XN=（

41、xm+1，xn）6、基解（见板书）、基解（见板书）7、基可行解：满足非负条件的基解叫基可行解。、基可行解：满足非负条件的基解叫基可行解。8、可行基：对应于基可行解的基称为可行基。、可行基：对应于基可行解的基称为可行基。2023-3-150max z=x1+2x2s.t.x1+x23 x2 1 x1,x2 0max z=x1+2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x3,x40 x1=0,x2=0 x3=3,x4=1基可行解x1=0,x4=0 x2=1,x3=2基可行解x2=0,x3=0 x1=3,x4=1基可行解x3=0,x4=0 x1=2,x2=1基可行解x1=0

42、,x3=0 x2=3,x4=-2是基解，但不是可行解OABx3=0 x4=0 x2=0 x1=0CD可行域2023-3-151例例.maxZ=2x1+3x2 x1 +x35 x1+2x2 +x4 10 x2 +x5 4 xi 0思考思考:这个问题会有几个基解这个问题会有几个基解?又会有几个基可行解又会有几个基可行解?2023-3-152解：解：x1x2x3x4x5Z是否为基可行解是否为基可行解10051040204520123500541040550115510 050420652.5001.517.575403 02282430016最优解为最优解为x1 5，x22.5，x3 0，Z17.5

43、2023-3-153二、凸集及其顶点二、凸集及其顶点1.凸集凸集 如果集合如果集合C中任意两点中任意两点x1，x2，其连线上的所有点也都是，其连线上的所有点也都是集合集合C中的点，则称中的点，则称C为凸集，其中为凸集，其中x1，x2的连线可以表的连线可以表示为：示为：x x1 1 （1 1）x x2 2(0(0 1)1)数学解析式为：数学解析式为：x1 C C，x2 C C，有有x x1 1 （1 1）x x2 2C C (0 (0 1)1)，则，则C C为凸集。为凸集。2023-3-1542.顶点顶点 如果集合如果集合C中任意两点中任意两点x1，x2，使，使x为这两点连线上的一为这两点连线上

44、的一个点，对任何个点，对任何x1 C C，x2 C C，不存在，不存在 x=x=x x1 1 （1 1）x x2 2(0(0 1)1)，则称，则称x为凸集的顶点。为凸集的顶点。2023-3-155三、几个基本定理三、几个基本定理定理定理1：若线性规划问题存在可行解，则问题的可行域是凸：若线性规划问题存在可行解，则问题的可行域是凸集。集。引理：线性规划问题的可行解引理：线性规划问题的可行解X(x1,x2,xn)为基可行解为基可行解的充要条件是的充要条件是X的正分量所对应的系数列向量是线性独立的正分量所对应的系数列向量是线性独立的。的。定理定理2：线性规划问题的基可行解：线性规划问题的基可行解X对

45、应线性规划问题可行域对应线性规划问题可行域的顶点。的顶点。定理定理3：若线性规划问题有最优解，一定存在一个基可行解：若线性规划问题有最优解，一定存在一个基可行解是最优解。是最优解。2023-3-156可行域顶点的数量可行域顶点的数量如果线性规划有如果线性规划有50个变量，个变量，20个约束条件，全部是等号个约束条件，全部是等号约束。按照以上的算法，每计算一个基解，要从约束。按照以上的算法，每计算一个基解，要从50个变量中选个变量中选择择30个非基变量等于个非基变量等于0，剩下，剩下20个变量，如果相应的个变量，如果相应的2020行列式不等于行列式不等于0，则通过计算一个，则通过计算一个20 2

46、0的线性方程组得到基的线性方程组得到基变量。要穷尽所有的基解，最多可能要计算的线性方程组的个变量。要穷尽所有的基解，最多可能要计算的线性方程组的个数为数为1320501074302050C.!假设每计算一个假设每计算一个2020线性组需要线性组需要1秒钟，计算以上所有方程秒钟，计算以上所有方程组需要的时间为组需要的时间为（年）61310513652436001074.由于极点的个数随着约束条件的增加而很快增加，用搜索所有由于极点的个数随着约束条件的增加而很快增加，用搜索所有极点来求出线性规划最优解，实际上并不是一个可行的方法。极点来求出线性规划最优解，实际上并不是一个可行的方法。2023-3-

47、157单纯形法原理示意图单纯形法原理示意图顶点顶点4，最优解，最优解初始顶点初始顶点1顶点顶点2顶点顶点3其实，不必搜索可行域的其实，不必搜索可行域的每一个顶点，只要从一个顶点每一个顶点，只要从一个顶点出发，沿着使目标函数改善的出发，沿着使目标函数改善的方向，到达下一个相邻的顶点。方向，到达下一个相邻的顶点。如果相邻的所有顶点都不能改如果相邻的所有顶点都不能改善目标函数，这个顶点就是最善目标函数，这个顶点就是最优顶点。用这样的搜索策略，优顶点。用这样的搜索策略，可以大大减少搜索顶点的个数。可以大大减少搜索顶点的个数。按照这样的搜索策略建立按照这样的搜索策略建立的算法，叫做单纯形法。的算法，叫做

48、单纯形法。单纯形法可以有效地减少单纯形法可以有效地减少搜索顶点的个数。搜索顶点的个数。目标函数改善目标函数改善目标函数改善目标函数改善目标函数改善目标函数改善第四节第四节 单纯形法单纯形法2023-3-158一、确定初始基可行解一、确定初始基可行解1、在、在A中观察是否存在一个单位矩阵中观察是否存在一个单位矩阵E，并，并确定初始基。确定初始基。2、如果、如果A中不存在现成的单位矩阵，我们要中不存在现成的单位矩阵，我们要构造一个。构造一个。例：例：maxZ=6x1+5x2 x1+3x290 2x1+x275 2x1+2x2 80 x1,x20maxZ=6x1+5x2 x1+3x2+x3 90 2

49、x1+x2 +x4 75 2x1+2x2 +x580 xi0找一个基可行解，找一个基可行解，X（0，0，90，75，80）T，Z=02023-3-159以矩阵形式表示单纯形的迭代过程以矩阵形式表示单纯形的迭代过程 max=CXmax=CX s.t s.t.AX=b.AX=b X0 X0A=(B,N),X=(XA=(B,N),X=(XB B,X,XN N)T T,C=(CC=(CB B,C,CN N)，则左式可写为，则左式可写为 max=Cmax=CB BX XB B+C+CN NX XN N s.t.BX s.t.BXB B+NX+NXN N=b=b X XB B,X,XN N00将基变量用非

50、基变量表示将基变量用非基变量表示 X XB B=B=B-1-1b-Bb-B-1-1NXNXN N代入目标函数，得代入目标函数，得 =C=CB B(B(B-1-1b-Bb-B-1-1NXNXN N)+C)+CN NX XN N =C =CB BB B-1-1b+(Cb+(CN N-C-CB BB B-1-1N)XN)XN N所以令所以令=CN-CBB-1N为对应基为对应基B的所有的所有X的判别向量，的判别向量，其中任一分量其中任一分量j=cj-CBB-1pj 为变量为变量xj关于基关于基B的判别数，的判别数，j=1,2,-,n。如果所有的检验数都小于如果所有的检验数都小于0，则当前解为最优解。，