运筹学基础及应用课件

《运筹学基础及应用课件》由会员分享，可在线阅读，更多相关《运筹学基础及应用课件（138页珍藏版）》请在装配图网上搜索。

1、2022-10-26运筹学基础及应用运筹学基础及应用1管理运筹学管理运筹学OPERATIONS RESEARCHFOR MANAGEMENT SCIENCE 2022-10-26运筹学基础及应用运筹学基础及应用2第一章第一章 线性规划及单纯形法线性规划及单纯形法(Linear Programming&Simplex Method)1 一般线性规划问题的数学模型一般线性规划问题的数学模型2 图解法图解法3 单纯形法原理单纯形法原理4 单纯形法的计算步骤单纯形法的计算步骤5 单纯形法的进一步讨论单纯形法的进一步讨论6 数据包络分析数据包络分析(DEA)7 应用举例应用举例2022-10-26运筹学

2、基础及应用运筹学基础及应用3例2(教材第9页)生产计划问题生产计划问题常山机器加工厂，利用A、B、C三种不同设备加工生产、两种产品。按工艺要求，每生产一个单位的产品，需要占用三种设备2、4、0小时；每生产一个单位的产品，需要占用三种设备2、0、5小时。已知三种设备加工能力分别为12、16、15小时。且每生产一个单位的产品可获取2单位的利润；每生产一个单位的产品可获取2单位的利润。问应当如何安排加工，可使获取的总利润最大？2022-10-26运筹学基础及应用运筹学基础及应用41 1 一般线性规划问题的数学模型一般线性规划问题的数学模型1.1 1.1 引例引例 例例1、生产计划问题、生产计划问题

3、设备能力（小时）设备能力（小时）设备设备A 2 2 12 设备设备B 4 0 16 设备设备C 0 5 15 利润（元）利润（元）2 3问：问：，两种产品各加工多少单位两种产品各加工多少单位,可获最大利润可获最大利润?运筹学基础及应用运筹学基础及应用 2x1+2x2 12 12 s.t.4x1 16 5x2 15 x1，x2 0注意模型特点注意模型特点 max Z=2x1+3x2解解:设产品设产品,产量分别为变量产量分别为变量x1，x2运筹学基础及应用运筹学基础及应用6附例附例 营养配餐问题营养配餐问题假定一个成年人每天需要从食物中获得假定一个成年人每天需要从食物中获得3000千卡的热量、千卡

4、的热量、55克蛋白质和克蛋白质和800毫克毫克的钙。如果市场上只有四种食品可供选择，的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？的前提下使购买食品的费用最小？运筹学基础及应用运筹学基础及应用73000 55 800 运筹学基础及应用运筹学基础及应用83000 55 800 x1x2x3x4运筹学基础及应用运筹学基础及应用9解：设解：设xj为第为第j种食品每天的购入量，则配餐种食品每天的购入量，则配餐问题的线性规划模型为：问题的线

5、性规划模型为：1234123412341234min14632100080090020030005060201055.4002003005008000(j1,.,4)jzxxxxxxxxxxxxstxxxxx12121212max2322124162.t.515,0zxxxxxsxx x例2022-10-26运筹学基础及应用运筹学基础及应用10线性规划模型的特点线性规划模型的特点n决策变量决策变量：向量：向量X=(x1 xn)T 决策人要考虑决策人要考虑和控制的因素，非负和控制的因素，非负n约束条件约束条件：关于：关于X的线性等式或不等式的线性等式或不等式n目标函数目标函数：Z=(x1 xn)

6、为关于为关于X 的线性函数，的线性函数，求求Z极大或极小极大或极小运筹学基础及应用运筹学基础及应用LP问题一般可整理为：111212112122211222c12nnmnmmnmnaaaxxxccbbbmaaaaaa决策变量价值资源系数活动决策变量及各类系数之间的对应关系决策变量及各类系数之间的对应关系运筹学基础及应用运筹学基础及应用上述模型的共同特征：l每一个线性规划问题都用一组决策变量每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值代表一个具体方案。一般表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；这些变量的取值是非负且连续的；l都有关

7、于各种资源和资源使用情况的技术数据，创造新价值都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；的数据；l存在可以量化的约束条件，这些约束条件可以用一组线性等存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示式或线性不等式来表示;l都有一个达到某一目标的要求，可用决策变量的线性函数都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数称为目标函数)来表示。按问题的要求不同，要求目标函数来表示。按问题的要求不同，要求目标函数实现最大化或最小化。实现最大化或最小化。nx,x,x21;(1,;1,)ijjia cb im jn2022-10-26运筹学基础及

8、应用运筹学基础及应用131.2 线性规划问题的数学模型三个组成要素：三个组成要素：1.决策变量决策变量:是决策者为实现规划目标采取的是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。方案、措施，是问题中要确定的未知量。2.目标函数目标函数:指问题要达到的目的要求，表指问题要达到的目的要求，表示为决策变量的函数。示为决策变量的函数。3.约束条件约束条件:指决策变量取值时受到的各种可指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或用资源的限制，表示为含决策变量的等式或不等式。不等式。运筹学基础及应用运筹学基础及应用14线性规划的数学模型由三个要素构成2022-10-

9、26运筹学基础及应用运筹学基础及应用15一般线性规划问题的数学模型：11 11221121 1222221 12212,.,0nnnnmmmnnmna xa xa xba xa xa xbsta xaxaxbx xx （或）（或）（或）目标函数：目标函数：约束条件：约束条件：nn2211xcxcxczminmax）（或运筹学基础及应用运筹学基础及应用161611 max(min)Z ()(i1 2)0 (j 1 2)njjjnijjijjc xa xbmxn 运筹学基础及应用运筹学基础及应用1717一般线性规划(LP)问题模型向量形式)(21ncccC nxxX1 mjjjaaP11mbbb

10、max (min)()b.0 jjzCXp xs tX 其中：运筹学基础及应用运筹学基础及应用1818一般线性规划(LP)问题模型矩阵形式 mnmnaaaaA1111m ax (m in)()b0 ZC XA XX 其中：)(21ncccC nxxX11mbbb 2022-10-26运筹学基础及应用运筹学基础及应用191.3 线性规划问题的标准形式标准形式：标准形式：），（），（n1j0 xm1ibxaxczmaxjin1jjijn1jjj 标准形式特点：标准形式特点：4.决策变量取值非负。决策变量取值非负。1.目标函数为求极大值；目标函数为求极大值；2.约束条件全为等式；约束条件全为等式；3

11、.约束条件右端常数项全为非负；约束条件右端常数项全为非负；2022-10-26运筹学基础及应用运筹学基础及应用20一般线性规划问题如何化为标准型：一般线性规划问题如何化为标准型：1.目标函数求极小值：目标函数求极小值：njjjxcz1min令：令：，即化为：，即化为：zznjjjnjjjxcxczzz11min)max(max2022-10-26运筹学基础及应用运筹学基础及应用212.约束条件为不等式：约束条件为不等式：（1）当约束条件为）当约束条件为“”时时如：如：122221 xx可令：可令：，显然显然1222321xxx03x（2）当约束条件为）当约束条件为“”时时如：如：1812102

12、1xx可令：可令：，显然显然04x181210421xxx 称为称为松弛变量。松弛变量。3x 称为称为剩余变量剩余变量。4x2022-10-26运筹学基础及应用运筹学基础及应用22松弛变量和剩余变量统称为松弛变量松弛变量和剩余变量统称为松弛变量（3）目标函数中松弛变量的系数）目标函数中松弛变量的系数 由于松弛变量和剩余变量分别表示未被充分利由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利用的资源以及超用的资源，都没有转化为价值和利润，因此润，因此在目标函数中系数为零在目标函数中系数为零。2022-10-26运筹学基础及应用运筹学基础及应用233.取值无约束的

13、变量取值无约束的变量 如果变量如果变量 xj 代表某产品当年计划数与代表某产品当年计划数与上一年计划数之差，显然上一年计划数之差，显然 xj 的取值可能是的取值可能是正也可能是负，这时可令：正也可能是负，这时可令：jjjxxx其中：其中：00 xx，令令4.变量变量 xj0jjxx，显然，显然0jx2022-10-26运筹学基础及应用运筹学基础及应用24例例3(教材教材15页页)将下述将下述LP模型化为标准型模型化为标准型123123123123123min232 93 24.32360,0,zxxxxxxxxxstxxxxxx 取值无约束2022-10-26运筹学基础及应用运筹学基础及应用2

14、5解：解：令令，11xxzz00 33333 xxxxx，得标准形式为：得标准形式为：06 33234 22 39 200332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxz，2022-10-26运筹学基础及应用运筹学基础及应用26运筹学基础及应用运筹学基础及应用27运筹学基础及应用运筹学基础及应用28线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）运筹学基础及应用运筹学基

15、础及应用29线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（SimplexSimplex）运筹学基础及应用运筹学基础及应用30线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（Sim

16、plexSimplex）19631963年年DantzigDantzig写成写成“Linear Programming and Linear Programming and ExtensionExtension”运筹学基础及应用运筹学基础及应用31线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（SimplexSimplex）19631963年年DantzigDantzig写成写成“Lin

17、ear Programming and Linear Programming and ExtensionExtension”19791979年苏联的年苏联的KhachianKhachian提出提出“椭球法椭球法”运筹学基础及应用运筹学基础及应用32线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzingDantzing）19511951年提出单纯形算法（年提出单纯形算法（SimplexSimplex）19631963年年DantzingDantzing写成写成

18、“Linear Programming and Linear Programming and ExtensionExtension”19791979年苏联的年苏联的KhachianKhachian提出提出“椭球法椭球法”19841984年印度的年印度的KarmarkarKarmarkar提出提出“投影梯度法投影梯度法”2022-10-26运筹学基础及应用运筹学基础及应用33求解线性规划问题：求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。值中，找出使得目标函数达到最大的值。），（），（njxmibxa

19、xczjinjjijnjjj1 01 max111.4 线性规划问题的解的概念2022-10-26运筹学基础及应用运筹学基础及应用34 可行解：可行解：满足所有约束条件的解称为满足所有约束条件的解称为可行解可行解，所有可，所有可行解的集合称为行解的集合称为可行域可行域。最优解：最优解：使目标函数达到最大值的可行解。使目标函数达到最大值的可行解。基基：约束方程组的一个满秩子矩阵称为规划问题的一：约束方程组的一个满秩子矩阵称为规划问题的一个个基基，基中的每一个列向量称为，基中的每一个列向量称为基向量基向量，与基向量对应，与基向量对应的变量称为的变量称为基变量基变量，其他变量称为，其他变量称为非基变

20、量非基变量。基解：基解：在约束方程组中，令所有非基变量为在约束方程组中，令所有非基变量为0，可以，可以解出基变量的唯一解，这组解与非基变量的解出基变量的唯一解，这组解与非基变量的0共同构成共同构成基解基解。基可行解：基可行解：满足变量非负的基解称为满足变量非负的基解称为基可行解基可行解可行基：可行基：对应于基可行解的基称为对应于基可行解的基称为可行基可行基2022-10-26运筹学基础及应用运筹学基础及应用35例：考察下述线性规划问题：例：考察下述线性规划问题：5,.2,1,01551641222.00032max524132154321ixxxxxxxxtsxxxxxzi2022-10-26

21、运筹学基础及应用运筹学基础及应用36（1）可行解，如可行解，如)15,16,12,0,0()0,4,0,3,3(或或满足约束条件，所以是可行解。满足约束条件，所以是可行解。（2）基基系数矩阵系数矩阵A：100500100400122A54321PPPPP其中其中 100010001),(5431PPPB或或 150004022),(5212PPPB都构成基。而都构成基。而)(431PPP不构成基。不构成基。2022-10-26运筹学基础及应用运筹学基础及应用37（3）基向量、基变量）基向量、基变量521,PPP是对应于基是对应于基的三个基向量，而的三个基向量，而2B521,xxx是对应于这三个

22、基向量的基变量。是对应于这三个基向量的基变量。（4）基解、基可行解、可行基）基解、基可行解、可行基)1516,12,0,0(是对应于基是对应于基1B的一个基解、基可行解。的一个基解、基可行解。)5,0,0,2,4(是对应于基是对应于基2B的一个基解、基可行解。的一个基解、基可行解。21,BB均是可行基均是可行基。练习：练习：P14，例例42022-10-26运筹学基础及应用运筹学基础及应用38 为了便于建立为了便于建立 n 维空间中线性规划问题的概念及维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。先介绍图解

23、法。求解下述线性规划问题：求解下述线性规划问题：0,151641222212121xxxxxx 5 2132maxxxz2 2 线性规划问题的图解法线性规划问题的图解法2022-10-26运筹学基础及应用运筹学基础及应用39画出线性规划问题的可行域：画出线性规划问题的可行域：122221 xx1641x1552x2x1xO1Q2Q3Q4Q342132xxZ目标函数等值线33212zxx2022-10-26运筹学基础及应用运筹学基础及应用401、可行域：、可行域：约束条件所围成的区域约束条件所围成的区域。2、基可行解：、基可行解：对应对应可行域的顶点。可行域的顶点。3、目标函数等值线：、目标函数

24、等值线：332321221zxxxxZ4、目标函数最优值、目标函数最优值:最大截距所对应的最大截距所对应的 。目标函数等值线有无数条，且平行。（观察规律目标函数等值线有无数条，且平行。（观察规律)Z2022-10-26运筹学基础及应用运筹学基础及应用41解的几种情况解的几种情况：(2)2)无穷多最优解无穷多最优解(1)唯一最优解唯一最优解2122maxxxz若目标函数改为：若目标函数改为：约束条件不变，则约束条件不变，则:122221 xx1641x1552x2x1xO1Q2Q3Q4Q342122xxZ目标函数等值线此时，线段此时，线段32QQ上所有点都是最优上所有点都是最优值点。值点。202

25、2-10-26运筹学基础及应用运筹学基础及应用42解的几种情况解的几种情况：(4)4)无界解无界解(3)无可行解：无可行解：当可行域为空集时，无可行解。当可行域为空集时，无可行解。若目标函数不变，将若目标函数不变，将约束条件约束条件1和和3去掉，则可行域及解的去掉，则可行域及解的情况见下图。情况见下图。1641x2x1xO1Q2Q3Q4Q342122xxZ目标函数等值线此时，目标函数等此时，目标函数等值线可以向上无穷值线可以向上无穷远处平移，远处平移，Z值无值无界。界。2022-10-26运筹学基础及应用运筹学基础及应用43几点说明：几点说明：1、图解法只能用来求解含有两个决策变量的线性规划问

26、、图解法只能用来求解含有两个决策变量的线性规划问 题。题。2、若最优解存在，则必在可行域的某个顶点处取得。、若最优解存在，则必在可行域的某个顶点处取得。3、线性规划问题的解可能是：唯一最优解、无穷多最优、线性规划问题的解可能是：唯一最优解、无穷多最优解、无最优解、无界解。解、无最优解、无界解。2022-10-26运筹学基础及应用运筹学基础及应用443 3单纯形法原理单纯形法原理凸集：凸集：如果集合如果集合 C 中任意两个点中任意两个点 ，其连线上的所有点，其连线上的所有点也都是集合也都是集合C 中的点。中的点。21,XX上图中（上图中（1）（）（2）是凸集，（）是凸集，（3）（）（4）不是凸集

27、）不是凸集顶点：顶点：如果对于凸集如果对于凸集 C 中的点中的点 X，不存在，不存在C 中的任意其它两中的任意其它两个不同的点个不同的点 ，使得，使得 X 在它们的连线上，这时称在它们的连线上，这时称 X 为凸为凸集的顶点。集的顶点。21XX、3.1 预备知识 2022-10-26运筹学基础及应用运筹学基础及应用453.2 线性规划问题基本定理定理定理1:1:若线性规划问题存在可行解，则问题的可行域是凸集。若线性规划问题存在可行解，则问题的可行域是凸集。证明证明:设设 是线性规划的任意两个可行解，则是线性规划的任意两个可行解，则21,XX0,0,2211XbAXXbAX于是对于任意的于是对于任

28、意的 ，设，设 ，则，则 )10(,0)1(21XXXbbbAXAXXXAAX)1()1()1(2121所以所以 也是问题的可行解，即可行域是凸集。也是问题的可行解，即可行域是凸集。21)1(XXX2022-10-26运筹学基础及应用运筹学基础及应用46引理引理:线性规划问题的可行解线性规划问题的可行解 X为基可行解的充要条件是为基可行解的充要条件是X的的正分量所对应的系数列向量线性无关。正分量所对应的系数列向量线性无关。证明证明:设设 （1 1）必要性显然。必要性显然。（2 2）设设 A A 的秩为的秩为m m。可行解。可行解 X X 的前的前 k k 个分量为正，且它们对应个分量为正，且它

29、们对应的系数列向量的系数列向量 线性无关，则线性无关，则 。当当 时，时，恰好构成一组基，而恰好构成一组基，而 就是这组基对应的基可行解。就是这组基对应的基可行解。TnxxxX),.,(21)kPPP,.,21mk mk mPPP,.,21TmxxxX)0,.0,.,(21 当当 时，在时，在 基础上从其余列向量中可以找出基础上从其余列向量中可以找出个线性无关的向量，恰好构成一组基，而个线性无关的向量，恰好构成一组基，而 X 就是这组基对应的基可行解。就是这组基对应的基可行解。mk kPPP,.,21km2022-10-26运筹学基础及应用运筹学基础及应用47定理定理2:线性规划问题的基可行解

30、线性规划问题的基可行解 X 对应线性规划问题可行对应线性规划问题可行 域（凸集）的顶点。域（凸集）的顶点。i证明证明:问题即是要证明问题即是要证明:X是基可行解是基可行解 X是可行域顶点，也即要证明是可行域顶点，也即要证明其逆否命题：其逆否命题：X不是基可行解不是基可行解 X不是可行域顶点不是可行域顶点。（1 1）X不是基可行解不是基可行解 X不是可行域顶点。不是可行域顶点。假设假设X是可行解，但不是基可行解，是可行解，但不是基可行解，X 的前的前 k 个分量为正个分量为正,其余分量为其余分量为0，则有则有又又X不是基可行解，所以由引理知，正分量对应的列向量不是基可行解，所以由引理知，正分量对

31、应的列向量线性相关。即存在一组不全为零的数线性相关。即存在一组不全为零的数 ，使得，使得)1(1kiiibxPkPPP,.,21)2(01kiiiP2022-10-26运筹学基础及应用运筹学基础及应用48用非零常数用非零常数 乘以上式得：乘以上式得：（1）+（3）得：）得：（1）-（3）得：）得：令令选择合适的选择合适的 ，使得所有的，使得所有的于是于是 均是可行解，并且均是可行解，并且 ，所以，所以 X 不是可行不是可行域顶点。域顶点。)3(01kiiiP)4()(.)()(1111kikkkiiibPxPxPx)5()(.)()(1111kikkkiiibPxPxPx0,.,0),(),.

32、,(112kkxxX0,.,0),(),.,(111kkxxX),.,2,1(,0kixii21,XX212121XXX2022-10-26运筹学基础及应用运筹学基础及应用49（2）X不是可行域顶点不是可行域顶点 X不是基可行解不是基可行解。设设 不是可行域的顶点，因而可以找到可行域内不是可行域的顶点，因而可以找到可行域内另两个不同的点另两个不同的点 ，使得使得 ，用分量表示即为：用分量表示即为：TkxxxX)0,.0,.,(210),.,(21TnyyyY0),.,(21TnzzzZ0)1(ZYX),.,2,1,10(,0)1(njzyxjjj易知，当易知，当 时，必有时，必有 所以所以0j

33、x,0jy),.,1(,0nkjzj,)0,.0,.,(21TkyyyY TkzzzZ)0,.0,.,(21所以所以)1(1kjjjbyP)2(1kjjjbzP于是（于是（1）-（2）得）得kjjjjPzy10)(而而 不全为零，于是知不全为零，于是知 线性相关，线性相关，X不是基可行解。不是基可行解。jjzy kPPP,.,212022-10-26运筹学基础及应用运筹学基础及应用50定理定理3:若线性规划问题有最优解，一定存在一个基可行解是若线性规划问题有最优解，一定存在一个基可行解是 最优解。最优解。引理：引理：有界有界 凸集中的任何一点均可表示成顶点的凸组合。凸集中的任何一点均可表示成顶

34、点的凸组合。证明证明:假设假设 是可行域顶点，是可行域顶点，不是可行域顶点不是可行域顶点，且目标，且目标函数在函数在 处达到最优，即处达到最优，即 。kXXX,.,210X0X0CXz 由引理知：由引理知：可表示为可表示为 的凸组合，即的凸组合，即0XkXXX,.,21kiiikkXXXX1221101,0,.因此因此kikiiiiiCXXCCX110假设假设 是所有是所有 中最大者，则中最大者，则mCXiCXkimmikiiiCXCXCXCX1102022-10-26运筹学基础及应用运筹学基础及应用51而而 是目标函数的最大值，所以是目标函数的最大值，所以 也是最大值，也是最大值，也即，目标

35、函数在可行域的某个顶点达到了最优。也即，目标函数在可行域的某个顶点达到了最优。0CX0CXCXm从上述三个定理可以看出，要求线性规划问题的最从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。标函数值即可，最大的就是我们所要求的最优解。2022-10-26运筹学基础及应用运筹学基础及应用523.3 确定初始基可行解寻求最优解的思路：寻求最优解的思路：线性规划问题的最优解一定会在线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然基可行解中取得，我们先

36、找到一个初始基可行解。然后设法转换到另一个基可行解，并使得目标函数值不后设法转换到另一个基可行解，并使得目标函数值不断增大，直到找到最优解为止。断增大，直到找到最优解为止。设给定线性规划问题：设给定线性规划问题：），（），（njxmibxaxczjinjjijnjjj101max11 2022-10-26运筹学基础及应用运筹学基础及应用53因此约束方程组的系数矩阵为：因此约束方程组的系数矩阵为：100010001212222111211mnmmnnaaaaaaaaa添加松弛变量得其标准形为：添加松弛变量得其标准形为：），（），（njxmibxxaxxczjisinjjijmisinjjj1 0

37、1 0max1112022-10-26运筹学基础及应用运筹学基础及应用54由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组基，就可以求出一个基可行解：基，就可以求出一个基可行解：TmbbX,0,01说明：说明：如果约束条件不全是如果约束条件不全是 形式，如含所有形式，如含所有 形式，形式，则无法找到一个单位阵做为一组基，这时需要添加人工变量。则无法找到一个单位阵做为一组基，这时需要添加人工变量。后面的内容介绍。后面的内容介绍。,称其为初始基可行解。称其为初始基可行解。2022-10-26运筹学基础及应用运筹学基础及应用553.4 从初

38、始基可行解转换为另一个基 可行解 思路：思路：对初始基可行解的系数矩阵进行初等行变换，构造对初始基可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。基变量，求出其数值，就是一个新的基可行解。设有初始基可行解设有初始基可行解 ，并可设前，并可设前m 个个 分量非零，即分量非零，即 ，于是，于是),.,()0()0(2)0(1)0(nxxxX)0,.,0,x,.,x,x(X)0(m)0(2)0(1)0()1(1)0(miiibxP2022-10-26运筹学基础及应用运筹学

39、基础及应用56 由构造初始可行基的方法知前由构造初始可行基的方法知前m 个基向量恰好是一个单位个基向量恰好是一个单位阵，所以约束方程组的增广矩阵为阵，所以约束方程组的增广矩阵为mnmnnjmmmjmjmbbbaaaaaaaaa.1.00.0.100.0121,2,1,1,21,2,11,1bPPPPPPnjmm.121由于由于任意系数列向量任意系数列向量均可由均可由基向量组基向量组线性表示，则非基向线性表示，则非基向量中的量中的 用用基向量组基向量组线性表示为：线性表示为：jP)n,.,1mj(,0PaPPaPm1iiijjm1iiijj2022-10-26运筹学基础及应用运筹学基础及应用57

40、)2(0)(1miiijjPaP设有设有 ，则，则0（1）+（2）得：）得：)3()()(1)0(11)0(bPPaxPaPxPjimiijimiiijjmiii由此式可知，我们找到了满足约束方程组的另一个解由此式可知，我们找到了满足约束方程组的另一个解 ，)1(X)0,.,0,.,()0(2)0(21)0(1)1(mjmjjaxaxaxX要使其成为要使其成为可行解可行解，只要对所有，只要对所有i=1,2,m ，下式成立，下式成立0)0(ijiax要使其成为要使其成为基可行解基可行解，上面，上面m个式中至少有一个取个式中至少有一个取零。零。（基可行解中非零分量的个数不超过（基可行解中非零分量的

41、个数不超过m 个。）个。）（与（与 比较）比较）)0,.,0,x,.,x,x(X)0(m)0(2)0(1)0(2022-10-26运筹学基础及应用运筹学基础及应用58只要取只要取ljlijijiaxaax)0()0(0min于是前于是前m个分量中的第个分量中的第l个变为零，其余非负，第个变为零，其余非负，第j个分量为个分量为正，于是非零分量的个数正，于是非零分量的个数 ，并可证得，并可证得线性无关，所以线性无关，所以 是新的基可行解。是新的基可行解。jmllPPPPPP,.1121)1(Xm2022-10-26运筹学基础及应用运筹学基础及应用593.4 最优性检验和解的判别设有基可行解设有基可

42、行解TnxxxX00201)0(,)0,.,0,.,()0(2)0(21)0(1)1(mjmjjaxaxaxX比较两者对应的目标函数值，哪一个更优？比较两者对应的目标函数值，哪一个更优？miiixcz10)0(miijijjijmiiiacczcaxcz1)0(10)1()()(2022-10-26运筹学基础及应用运筹学基础及应用602）若对所有的）若对所有的 ，则，则 ，就是最优解。就是最优解。0)(1miijijjacc)0()1(zz)0(zmiijijjacc1是判断是否达到最优解的标准，是判断是否达到最优解的标准，称为称为检验数。检验数。1）当）当 时，时，目标函数值得到，目标函数值

43、得到了改进，了改进，不是最优解，需要继续迭代。不是最优解，需要继续迭代。0)(1miijijjacc)0()1(zz)0(z易知易知2022-10-26运筹学基础及应用运筹学基础及应用61当所有当所有 时，现有顶点对应的基可行解即为最优时，现有顶点对应的基可行解即为最优解。解。当所有当所有 时，又对某个非基变量时，又对某个非基变量 有有 则该线性规划问题有无穷多最优解。则该线性规划问题有无穷多最优解。3.如果存在某个如果存在某个 ，又，又 向量的所有分量向量的所有分量 ，对任意对任意 ，恒有，恒有 ，则存在无界，则存在无界解。解。kx0j0j0k0jjP0ija000ijiax结论结论2022

44、-10-26运筹学基础及应用运筹学基础及应用624 单纯形法的计算步骤单纯形法的计算步骤 Max(min)Z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b b1 1a21x1+a22x2+a2nxn=b b2 2 am1x1+am2x2+amnxn=b bm mxj j 0(0(j=1,n)设有线性规划问题：设有线性规划问题：2022-10-26运筹学基础及应用运筹学基础及应用63(1)(1)找到初始可行基，建立初始单纯形表找到初始可行基，建立初始单纯形表.(4)(4)重复重复二、三两步，直至找到最优解二、三两步，直至找到最优解。4 单纯形法的计算步骤单纯形法的计算步骤(

45、2)(2)进行最优性检验。进行最优性检验。计算检验数，若所有计算检验数，若所有 0 则得最优解，结束则得最优解，结束.否则转下步否则转下步.若某若某 0 0 而而 0 0，则最优解无界，结束，则最优解无界，结束.否则转下步否则转下步.kkPj(3)(3)从一个可行解转换到另一个目标函数值更大的从一个可行解转换到另一个目标函数值更大的基可行解。基可行解。由最大增加原则确定进基变量；由最小比值原则选择出基变由最大增加原则确定进基变量；由最小比值原则选择出基变量；以量；以 为主元素进行换基迭代。为主元素进行换基迭代。lka2022-10-26运筹学基础及应用运筹学基础及应用64001(1)(1)找到

46、初始可行基，建立初始单纯形表找到初始可行基，建立初始单纯形表.0CBCBXbZbCBmccc21mxxx21mbbb21mcc.1mxx.1nmxxj1x.m 21miijijacc1100nmccj1c.mjjjaaa211,1,21,1mmmmaaamnnnaaa21miininacc1mimiimacc11,10mlPPPP.21是初始基。是初始基。2022-10-26运筹学基础及应用运筹学基础及应用65(2)(2)进行最优性检验进行最优性检验计算检验数，若所有计算检验数，若所有 0 则得最优解，结束则得最优解，结束.否则转下步否则转下步.若某若某 0 0 而而 0 0，则最优解无界，结

47、束，则最优解无界，结束.否则转下步否则转下步.kkPjmiijijjacc1检验数的计算方法：检验数的计算方法：基变量的检验数一定为基变量的检验数一定为0。判断是否达到最优时，只要考虑。判断是否达到最优时，只要考虑非基变量检验数。非基变量检验数。2022-10-26运筹学基础及应用运筹学基础及应用66(3)(3)从一个可行解转换到另一个目标函数值更大的从一个可行解转换到另一个目标函数值更大的基可行解。基可行解。由最小比值原则选择出基变量；由最小比值原则选择出基变量；lklikikiiabaab/0/minkjjjkx0max进基变量由最大增加原则确定进基变量：由最大增加原则确定进基变量：当某些

48、非基变量的检验数当某些非基变量的检验数 时，为使目标函数值时，为使目标函数值增加地更快，一般选择增加地更快，一般选择正检验数中最大者正检验数中最大者对应的非基变对应的非基变量进基量进基 ，成为新的基变量。，成为新的基变量。0j为确保新的基可行解的非零分量非负，按下述规则求得最小为确保新的基可行解的非零分量非负，按下述规则求得最小比值比值 ，其所对应的原基变量中的，其所对应的原基变量中的 出基。出基。lx于是，新的一组基是：于是，新的一组基是：kmllPPPPPP,.11212022-10-26运筹学基础及应用运筹学基础及应用67以以 为主元素进行换基迭代：为主元素进行换基迭代：即利用初等行变换

49、将进基变量即利用初等行变换将进基变量 所在的系数列变为单位所在的系数列变为单位列向量，而列向量，而 变为变为1 1。这样原来基矩阵中的。这样原来基矩阵中的 就不再就不再是单位向量，取而代之的是是单位向量，取而代之的是 ，这样就找到了一组新的，这样就找到了一组新的基。基。lkakxlkalPkP(4)(4)重复重复二、三两步，直至找到最优解二、三两步，直至找到最优解。说明：说明：若目标函数是求最小，可以不必将其转变为求若目标函数是求最小，可以不必将其转变为求 最大，但在使用单纯形法求解时，确定进基变最大，但在使用单纯形法求解时，确定进基变 量，应找量，应找负检验数中最小者，负检验数中最小者，并应

50、以并应以检验数检验数 全部为正全部为正作为判别最优的条件。作为判别最优的条件。2022-10-26运筹学基础及应用运筹学基础及应用68解解 将将模型标准化模型标准化附例附例12121212max358212.3436,0zxxxxstxxx x12345132412512345max350008212.3436,0zxxxxxxxxxstxxxx x x x x2022-10-26运筹学基础及应用运筹学基础及应用691202010Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5350008101003634001x3x4x5000035000-12/2=636/4=9作出初始单纯形表

51、，进行迭代作出初始单纯形表，进行迭代检验数最大比值最小miijijjacc1lklikikiiabaab/0/min12345132412512345max350008212.3436,0zxxxxxxxxxs txxxxxxxx2022-10-26运筹学基础及应用运筹学基础及应用7012300-21810100检验数检验数 j60101/20 x3x2x5050-30300-5/208-4Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=92022-10-26运筹学基础及应用运筹学

52、基础及应用71Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数检验数 j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1唯一最优解唯一最优解 :X*=(4,6,4,0,0)T，Z*=422022-10-26运筹学基础及应用运筹学基础及应用72n特殊情况：（1）出现两个或两个以上相同的最大出现两个或两个以上相同的最大 ，此，此时可任选一个时可任选一个 所对应的变量作为进基变量。所对应的变量作为进基变量。（2）利用利用 规则决定出

53、基变量时，出现两个或规则决定出基变量时，出现两个或两个以上的最小比值两个以上的最小比值 ，则迭代后，会出现一，则迭代后，会出现一个或几个基变量等于零的情况，我们称此为退化个或几个基变量等于零的情况，我们称此为退化现象。进而可能会出现迭代过程的循环，致使永现象。进而可能会出现迭代过程的循环，致使永远达不到最优解。远达不到最优解。出现退化现象时，可考虑采用出现退化现象时，可考虑采用“勃兰特勃兰特”规则规则决决定进基变量和出基变量的选择。定进基变量和出基变量的选择。jj2022-10-26运筹学基础及应用运筹学基础及应用735.1 5.1 人工变量人工变量 n用单纯形法解题时，需要有一个单位阵作为初

54、用单纯形法解题时，需要有一个单位阵作为初始基。始基。n当约束条件都是当约束条件都是“”时，加入松弛变量就形成时，加入松弛变量就形成了初始基。了初始基。n但实际存在但实际存在“”或或“”型的约束，没有现成型的约束，没有现成的单位矩阵的单位矩阵。n采用人造基的办法：添加采用人造基的办法：添加5 5 单纯形法的进一步讨论单纯形法的进一步讨论 2022-10-26运筹学基础及应用运筹学基础及应用74人工单位矩阵的构造方法人工单位矩阵的构造方法 在在“”的不等式约束中减去一个剩余变量后可变为等的不等式约束中减去一个剩余变量后可变为等式约束，但此剩余变量的系数是（式约束，但此剩余变量的系数是（-1-1），

55、所以再加入一），所以再加入一个人工变量，其系数是（个人工变量，其系数是（+1+1），因而在系数矩阵中可得），因而在系数矩阵中可得到一个相应的单位向量，以便构成初始单位阵，即初始到一个相应的单位向量，以便构成初始单位阵，即初始基矩阵。基矩阵。在原本就是在原本就是“=”的约束中可直接添加一个人工变量，的约束中可直接添加一个人工变量，以便得到初始基矩阵。以便得到初始基矩阵。注意：注意：人工变量是在等式中人为加进的，只有它等于人工变量是在等式中人为加进的，只有它等于0 0时，时，约束条件才是它本来的意义。约束条件才是它本来的意义。求解带人工变量的线性规划有两种方法：求解带人工变量的线性规划有两种方法：

56、大大M M法法 两阶段法两阶段法2022-10-26运筹学基础及应用运筹学基础及应用755.2 5.2 大大M M法法没有单位矩阵，不符合构造初始基的条件，需加入人工变没有单位矩阵，不符合构造初始基的条件，需加入人工变量量 。人工变量最终必须等于人工变量最终必须等于0 0才能保持原问题性质不变。为保证才能保持原问题性质不变。为保证人工变量为人工变量为0 0，在目标函数中令其系数为（，在目标函数中令其系数为（-M-M）。）。（求最小值问题中，人工变量系数取（求最小值问题中，人工变量系数取M M）M M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，为无限大的正数，这是一个惩罚项，倘若人工变量

57、不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解就没有可行解，当然亦无最优解。2022-10-26运筹学基础及应用运筹学基础及应用76例例解线性规划解线性规划0,93124.3max3213232132131xxxxxxxxxxxtsxxZ解解化为标准型化为标准型0,93124.3max54321325321432131xxxxxxxxxxxxxxxtsxxZ此时无单位

58、矩阵作为初始基。此时无单位矩阵作为初始基。2022-10-26运筹学基础及应用运筹学基础及应用77添加人工变量，构造初始基：添加人工变量，构造初始基：131234123523767671max3421.39,.,0ZxxxxxxxxxxstMxMxxxxxxx 注意：若求最小值问题，则目标函数中人工变量系数取注意：若求最小值问题，则目标函数中人工变量系数取M。2022-10-26运筹学基础及应用运筹学基础及应用78-30100-M-Mx1x2x3x4x5x6x71111000-21-10-1100310001初始单纯形表：初始单纯形表：jCCBXBb0 x44-Mx61-Mx79-3-2M4M

59、10-M0041330211-10-21-10-11060403-311-10 x430 x21-Mx76-3+6M01+4M03M-3M0131234123523767671m a x3421.39,.,0Zxxxxxxxxxxs tM xM xxxxxxx 2022-10-26运筹学基础及应用运筹学基础及应用79-30100-M-Mx1x2x3x4x5x6x7jCCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60 x400 x23-3x11-3/2000-3/4-M+3/4-M-1/40 x400

60、 x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/42022-10-26运筹学基础及应用运筹学基础及应用80此时人工变量全部出基，并已达最优条件。此时人工变量全部出基，并已达最优条件。最优解为最优解为)25,25,0(X，最优值为，最优值为25Z注意：注意：计算机上使用大计算机上使用大M法时，需要用机器最大字长的数字法时，需要用机器最大字长的数字代替代替M，但当某些系数与之较接近时，还是可能会出错。，但当某些系数与之较接近时，还是可能会出错。另外一种求解带人工变量的线性规划问题的方法不会出现这种另外一种求解带人工变量的线性规划

61、问题的方法不会出现这种问题问题-两阶段法两阶段法。2022-10-26运筹学基础及应用运筹学基础及应用81例例解线性规划解线性规划解解按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4,x5 的辅助问题如下：的辅助问题如下：123123123123max323236.24,0zxxxxxxstxxxx x x123123123124555344max323236.24,0,MxMxxzxxxxxxstxxxxx x xxx2022-10-26运筹学基础及应用运筹学基础及应用82作出单纯形表，进行迭代作出单纯形表，进行迭代Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5

62、3-1-2-M-M632-31041-21013+4M-1-2-2M00 x4x5-M-M24检验数检验数 j212/3-11/3020-8/32-1/310-3-8M/3 1+2M-1-4M/30 x1x53-M123123123124555344max323236.24,0,MxMxxzxxxxxxstxxxxx x xxx2022-10-26运筹学基础及应用运筹学基础及应用83检验数检验数 j212/3-11/3020-8/32-1/310-3-8M/3 1+2M-1-4M/30 x1x53-M-1检验数检验数 j31-2/301/61/210-4/31-1/61/20-5/30-M-5

63、/6-M-1/2x1x33-2最优解最优解 :X*=(3,0,1)T，Z*=72022-10-26运筹学基础及应用运筹学基础及应用845.3 5.3 两阶段法两阶段法 第一阶段：第一阶段：构造目标函数只含人工变量的线构造目标函数只含人工变量的线 性规划问题，求解后判断原线性性规划问题，求解后判断原线性 规划问题是否有基本可行解，若规划问题是否有基本可行解，若 有，则进行第二阶段有，则进行第二阶段 ；第二阶段：第二阶段：将第一阶段的最终单纯形表所对将第一阶段的最终单纯形表所对 应的解，去掉人工变量，作为第应的解，去掉人工变量，作为第 二阶段的初始单纯形表的初始基二阶段的初始单纯形表的初始基 可行

64、解，进行单纯形法的迭代。可行解，进行单纯形法的迭代。2022-10-26运筹学基础及应用运筹学基础及应用85 解解（1）化标准型、并添加人工变量得：化标准型、并添加人工变量得：（此处未将目标变为（此处未将目标变为MAX）例：例：1212112123min23350125.2600,0Zxxxxxstxxx x x121213456761273512746,min23350125.2600,0,xxxzxxxxxstxxxMxxMxxxxxxxx2022-10-26运筹学基础及应用运筹学基础及应用86（2）构造第一阶段问题：）构造第一阶段问题：说明：说明：原问题目标函数无论是求原问题目标函数无论

65、是求MAXMAX还是求还是求MINMIN，构造的，构造的 第一阶段问题目标函数都是第一阶段问题目标函数都是求最小求最小MINMIN。3453456767671211212min350125.2600,0,xxxstxxxxx xxxxxxxxx x x2022-10-26运筹学基础及应用运筹学基础及应用87求解第一阶段问题：求解第一阶段问题：2022-10-26运筹学基础及应用运筹学基础及应用88此时所得可行解目标函数值为此时所得可行解目标函数值为0 0，故原规划问题有基可行，故原规划问题有基可行解。转入第二步。解。转入第二步。2022-10-26运筹学基础及应用运筹学基础及应用89（3）去掉

66、人工变量，得到第二阶段的单纯形表，在此）去掉人工变量，得到第二阶段的单纯形表，在此 基础上继续求解。基础上继续求解。最优解为：最优解为：125,100,250421xxx2022-10-26运筹学基础及应用运筹学基础及应用905.4 5.4 关于解的不同情况的判别关于解的不同情况的判别 1 1、无穷多最优解、无穷多最优解例：例：0,15 5 16 41222212121xxxxxx2133maxxxz解：解：将问题化为标准型：将问题化为标准型：0.,15x 5 16x 41222515241321xxxxxxx2133maxxxz2022-10-26运筹学基础及应用运筹学基础及应用912022-10-26运筹学基础及应用运筹学基础及应用92从上表中可知，已达最优解，为从上表中可知，已达最优解，为 ，而而 ，若将，若将 选为进基变量迭代后，可得另一最优选为进基变量迭代后，可得另一最优解解 。)5,0,0,2,4(1Z044x)0,4,0,3,3(2Z上述两最优解分别对应两个顶点，而两点连线上的点均上述两最优解分别对应两个顶点，而两点连线上的点均是最优解，故有无穷多最优解。是最优解，故有无