第一章 线性规划与单纯形法

1、主讲主讲: :周晓林周晓林Email:Email:Telel:135888264342021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林22021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林3二、运筹学的历史与发展二、运筹学的历史与发展 国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。 2021-1

2、1-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林42021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林52021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林6 在生产管理方面的应用，最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作生产组织与计划中的数学方法。 但当时并没有引起重视，直到1960年康特洛为奇再次出版了最佳资源利用的经济计算，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖（1975）。 线性规划提出后很快受到经济学家的重视，如二次世界

3、大战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林72021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林8 50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年

4、，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。 在中国，最早的运筹学思想有战国时期的田忌赛马，它是对策论的一个典型例子，北宋时期的丁渭造皇宫，它是统筹规划的一个例子。2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林9三、运筹学的基本内容三、运筹学的基本内容1、线性规划（Linear Program）是一个成熟的分支，它有效的算法单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。2、整数规划(Integrate Program)：在线性规划的基础上，变量加上整数约束3、非线性规划(Nonlinear Program)：目标函数和约束条件是非线性

5、函数，如证券投资组合优化:如何合理投资使风险最小。4、动态规划(Dynamic Program):多阶段决策问题。是美国贝尔曼于1951年提出的。5、图与网络(Graph Theory and Network)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林106、存储模型（Inventory Theory)：主要解决生产中的库存问题，订货周期和订货量等问题。7、排队论(Queue Theory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。8、对策论(Game Theory)：主要研究具有

6、斗争性质的优化问题。9、决策分析(Decision Analysis) ：主要研究定量化决策三、运筹学的工作步骤1、明确目标、收集资料、提出问题2、建立模型3、模型求解与检验4、结果分析与实施2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林112021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林12解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产甲产品的数量 x2=生产乙产品的数量2确定目标函数：工厂的目标是总利润最大 max z=1500 x1+2500 x23确定约束条件： 3x1+2x265（A资源的限制） 2

7、x1+ x2 40（B资源的限制） 3x2 75（C资源的限制）4变量取值限制： 一般情况，决策变量只取正值（非负值） x1 0, x2 0 2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林133x2 752021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林142021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林15方方 案案 2.9m 2.1m 1.5m 合合 计计 余余 料料 1 2 0 1 7.3 0.1 2 1 2 0 7.1 0.3 3 1 1 1 6.5 0.9 4 1 0 3 7.4 0 5 0 3 0 6.3

8、 1.1 6 0 2 2 7.2 0.2 7 0 1 3 6.6 0.8 8 0 0 4 6.0 1.4 2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林16技技术术系系数数右右端端项项价价值值系系数数线线性性规规划划问问题题的的规规模模约约束束行行数数变变量量个个数数: ;: ;: ;: ;:0,),(),(),(.)(max(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf一般表示形式：一般表示形式：2021-11-11 浙江理工大学经管

9、学院周晓林浙江理工大学经管学院周晓林17njxmibxatsxcxfjinjjijnjjj, 2 , 1 , 0, 2 , 1 ,.)(max11其他常用表示形式：其他常用表示形式：2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林18 ),(),();,(.)(max212121212222111211TmTnnmnmmnnbbbbxxxXcccCaaaaaaaaaA0XbAXtsCXxf2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林190000 ),( );,( .)(max210212121010bbbbaaaPxxxXcccC0Xbx

10、PtsCXxfmmjjjjTnnnjjj2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林20njijijbxa1njxmibxatsxcxfjinjjijnjjj,2, 1 ),0(0,2, 1 ,),(.)(max(min)11不不限限这可是这可是个重点个重点哦！哦！njjjxcz1max21b, xj0(j=12n)432021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林211Max zMin zab注意：z与z的解相同但目标函数值相差一负号 z z2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林22l 第第i i

11、个约束的个约束的b bi i 为负值，则该行左右两端系数同时反号，同为负值，则该行左右两端系数同时反号，同时不等号也要反向时不等号也要反向lExample: Example: 4 4=-6 - =-6 - 4 4= 6= 6l 第第i i 个约束为个约束为 型，在不等式左边增加一个非负的变量型，在不等式左边增加一个非负的变量x xn+in+i ，称为松弛变量；同时令称为松弛变量；同时令 c cn+in+i = 0= 0lExample: Example: -2-2 9 9 -2-2=9=9l 第第i i 个约束为个约束为 型，在不等式左边减去一个非负的变量型，在不等式左边减去一个非负的变量x

12、xn+in+i ，称为剩余变量；同时令称为剩余变量；同时令 c cn+in+i = 0= 0lExample: Example: -3-3 4 4 -3-3=4=4l 若若x xj j 0 0，令，令 x xj j= -= -x xj j ，代入非标准型，则有，代入非标准型，则有x xj j 0 0l若若x xj j 不限，令不限，令 x xj j= = x xj j - - x xj j ， x xj j 0 0，x xj j 0 0，代入非标准代入非标准型型2342021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林230, ,20040065300432.423)(m

13、in:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非标准型原非标准型 0,2004006653004432.0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型标准型2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林2450403020103040 x1 2 线性规划的图解法线性规划的图解法3x2 75504030201010203040 x150等值线等值线B1 可行解可行解2 最优解最优解2021-11-11 浙江理工大学经管学院

14、周晓林浙江理工大学经管学院周晓林252021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林263 线性规划问题解的基本性质线性规划问题解的基本性质2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林272021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林28线性规划的线性规划的基矩阵基矩阵、基变量基变量、非基变量非基变量=目标函数约束条件行列式0基矩阵右边常数2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林29012233. .23max321432143214xxxxxxxxtsxxxxz0000320

15、20001010 x1x2x4x3001300321=目标函数约束条件行列式0基矩阵X1,x2,x3为基变量为基变量,x4为非基变量为非基变量2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林302021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林31约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解退化解退化解2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林320,78102.46)(max212212121xxxxxxxtsxxxf 可行解、基解和基本可行解举例可行解、基解和基本可行解

16、举例 系数矩阵系数矩阵:A=1 1 0 01 1 0 1 00 1 0 0 10,78102. .46)(max543215242132121xxxxxxxxxxxxxt sxxxf：标准型x1 x2 x3 x4 x52021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林33 可行解、基解和基本可行解举例可行解、基解和基本可行解举例 系数矩阵系数矩阵:A=1 1 0 01 1 0 1 00 1 0 0 1x1 x2 x3 x4 x5 1 0 0 0 1 0 0 0 1 B=x3 x4 x5 2 1 1 1 0 0 x1 x2 N=A=(B,N)令非基变量令非基变量X1=0,

17、X2=0得得X3=10,X4=8,X5=7,因此可得一基本解因此可得一基本解X=(0,0,10,8,7)T2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林341187654322x1876543O109x2A BCEDFGH123f(x)=36K2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林35二、线性规划问题解的基本性质二、线性规划问题解的基本性质（一）几个基本概念（一）几个基本概念2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林36 。3、顶点：、顶点：设S是凸集, 若S中的点x 不能成为S中任何线段上的内点，

18、则称x为凸集S的顶点。即：若S中的任意两点x(1),x(2) ，不存在数 （0 = 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0此时若系数矩阵中无单位矩阵，则可以引入人工变量。2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林63Max z = c1 x1 + c2 x2 + + cn xn s.

19、t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn 0此时人工变量xn+1 、 xn+2 、. xn+m 的系数向量构成一个m*m的单位矩阵，因此可以作为初始可行基。但是但是2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林642021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林65s.t. a11x1 + a12x2 + a1nxn +

20、 xn+1 = b a21x1 + a22x2 + a2nxn + xn+2 = b2 am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m） Max w = c1 x1 + c2 x2 + + cn xn -M(xn+1 + xn+2 + xn+m )1、大、大M法法2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林66 max z = 3x1 - x2 - x3s.t. x1 - 2x2 + x3 11 -4x1 + x2 + 2x3 3 -2x1 + x3 = 1 x1, x2, x30 max w

21、 = 3x1 - x2 - x3 + 0 x4 + 0 x5 Mx6 Mx7s.t. x1 - 2x2 + x3 +x4 =11 -4x1 + x2 + 2x3 x5 + x6 =3 2x1 + x3 +x7 =1 xj0 （j = 1,2,7） 2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林67 表1 -9 c 3 - 1 - 1 0 0 - M - M 序 号 cB xB x1 x2 x3 x4 x5 x6 x7 b 0 - M - M x4 x6 x7 1 - 4 - 2 - 2 1 0 1 2 1* 1 0 0 0 - 1 0 0 1 0 0 0 1 1 1

22、 3 1 检 验 数 3 - 6 M - 1 + M - 1 + 3 M 0 - M 0 0 4 M 0 - M - 1 x4 x6 x3 3 0 - 2 - 2 1* 0 0 0 1 1 0 0 0 - 1 0 0 1 0 - 1 - 2 1 1 0 1 1 检 验 数 1 - 1 + M 0 0 - M 0 1 -3 M 1 + M 0 - 1 - 1 x4 x2 x3 3* 0 - 2 0 1 0 0 0 1 1 0 0 - 2 - 1 0 2 1 0 - 5 - 2 1 1 2 1 1 检 验 数 1 0 0 0 -1 1 -M - 1 - M 2 3 - 1 - 1 x1 x2 x3

23、 1 0 0 0 1 0 0 0 1 1 /3 0 2 /3 - 2 /3 - 1 - 4 /3 2 /3 1 4 /3 - 5 /3 - 2 - 7 /3 4 1 9 检 验 数 0 0 0 - 1 /3 - 1 /3 1 /3 - M 2 /3 - M - 2 See you next time!See you next time!2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林682021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林69不不是是人人工工变变量量时时当当为为人人工工变变量量时时当当时时目目标标函函数数为为不不是是人人工工变变量量时时当当为为人人工工变变量量时时当当时时目目标标函函数数为为jjjjjjjjxcxcxcxc01max01min2021-11-11 浙江理工大学经管学院周晓林浙江理工大学经管学院周晓林70 max z = 3x1 - x2 - x3s.t. x1 - 2x2 + x3 11 -4x1 + x2 + 2x3 3 -2x1 + x3 = 1 x1, x2, x30 解解 :引入松弛变量引入