第1章线性规划

1、第一章第一章 线性规划线性规划(Linear Programming)线性规划问题及其数学模型线性规划问题及其数学模型线性规划图解法线性规划图解法线性规划问题解的性质线性规划问题解的性质 单纯形法单纯形法 单纯形法的其他问题讨论单纯形法的其他问题讨论 线性规划应用举例线性规划应用举例 WinQSBWinQSB软件应用软件应用线性规划的基本特点线性规划的基本特点uLPLP是运筹学中应用最广泛的方法之一；是运筹学中应用最广泛的方法之一；uLPLP是运筹学中最基本的方法之一，网络分析、整是运筹学中最基本的方法之一，网络分析、整数规划、目标规划和多目标规划等都是以数规划、目标规划和多目标规划等都是以L

2、PLP为基为基础的；础的；u解决稀缺资源最优分配的有效方法，是付出的费解决稀缺资源最优分配的有效方法，是付出的费用最小或获得的收益最大用最小或获得的收益最大线性规划的研究对象线性规划的研究对象u有一定的人力、财力、资源条件下，如何合理安有一定的人力、财力、资源条件下，如何合理安排使用，效益最高；排使用，效益最高；u某项任务确定后，如何安排人、财、物，使之最某项任务确定后，如何安排人、财、物，使之最省省典型应用典型应用合理利用线材问题：如何下料，使用材最少？配料问题：在原料供应量的限制下，如何获得最大利润？投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物、财等，使获利

3、最大劳动力安排：用最少的劳动力来满足工作的安排运输问题：如何制定调整方案，使总运费最小？第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型 一、线性规划问题的提出一、线性规划问题的提出p有多少种配比方案？为什麽？有多少种配比方案？为什麽？p何为最好？何为最好？ 产产 品品资资 源源 甲甲乙乙每天可用于产品生产每天可用于产品生产的资源量的资源量设备设备1116材料材料A3236材料材料B565利润（元）利润（元）9070【例例1-11-1】已知已知某企业生产某企业生产资料如下表所示，问如何安排生产资料如下表所示，问如何安排生产才能企业使利润最大？才能企业使利润最大？数学模型：数学模型

4、： x1 0 , x2 0s.t.设甲产品的生产量为设甲产品的生产量为x x1 1, ,乙产品的生产量为乙产品的生产量为x x2 2，则：，则：217090maxxxz1621 xx362321 xx6552x 【例例1-21-2】设某种动物每天需要摄入的蛋白质、矿物质、维设某种动物每天需要摄入的蛋白质、矿物质、维生素的最低量及生素的最低量及A A、B B、C C、D D、E E五种饲料每公斤营养成分的含五种饲料每公斤营养成分的含量及单位价格如下表所示。要求既满足该种动物每天营养成分量及单位价格如下表所示。要求既满足该种动物每天营养成分的需要量，又使总的费用最省。的需要量，又使总的费用最省。

5、目标函数：目标函数： 满足约束条件满足约束条件 ABCDE每天最低摄入量(克)蛋白质(克)矿物质(克)维生素(克)310.520.5110.20.2622180.50.870030100价格(元/千克)27438设设 为第为第j j种饲料的每天使用量种饲料的每天使用量，则：，则：jx5432183472minxxxxxz0,1008 . 022 . 05 . 0305 . 022 . 05 . 07001862354321543215432154321xxxxxxxxxxxxxxxxxxxx jx二、线性规划问题数学模型的一般形式二、线性规划问题数学模型的一般形式3.3.线性规划问题数学模型的

6、组成要素：线性规划问题数学模型的组成要素： (1) (1)变量，或称决策变量变量，或称决策变量，它们是问题中所要解决的未知量，它们是问题中所要解决的未知量，表明规划中用数量表示的方案、措施，可由决策者决定和控制；表明规划中用数量表示的方案、措施，可由决策者决定和控制； (2 (2) )目标函数目标函数，是决策变量的函数，按问题的目标不同分别是决策变量的函数，按问题的目标不同分别在这个函数前加上在这个函数前加上maxmax或或minmin； (3) (3)约束条件约束条件，由一组含决策变量的等式或不等式组成，由一组含决策变量的等式或不等式组成，表明决策变量取值时所受到的各种资源条件的限制。表明决

7、策变量取值时所受到的各种资源条件的限制。 假定线性规划问题中含有假定线性规划问题中含有n n个决策变量个决策变量x xj j(j(j1 1，n)n)，在目标函数中在目标函数中x xj j的系数为的系数为c cj j(c(cj j通常称为价值系数通常称为价值系数) )；有；有m m种资源种资源的限制，每种资源数量用的限制，每种资源数量用b bi i(i=1,.m)(i=1,.m)表示；用表示；用a aijij表示变量表示变量x xj j取值为取值为1 1个单位时所消耗或含有的第个单位时所消耗或含有的第i i种资源的数量，通常称种资源的数量，通常称a aijij为技术系数或消耗系数。为技术系数或消

8、耗系数。 nnxcxcxcz2211 (min) max目标函数：目标函数：约束条件：约束条件：线性规划线性规划问题的问题的数学模型的一般形式：数学模型的一般形式：11212111 )( bxaxaxann 22222121 )( bxaxaxannmnmnmmbxaxaxa )( 22110 ,21nxxx为目标函数；为资源约束；为非负约束。为目标函数；为资源约束；为非负约束。x xj j决策变量；决策变量；c cj j价值系数；价值系数；a aijij技术（消耗）系数；技术（消耗）系数；b bi i资源常量，资源常量，b bi i0线性规划模型的简写形式为线性规划模型的简写形式为：njjj

9、xc1 z min)(max 或目标函数：目标函数：约束条件：约束条件：)21(j0)21(i )(1nxmbxajnjijij、式中：式中：) , , , (21ncccCnxxX1 mjjjaap1 mbbb1用向量形式表达时，模型可写为用向量形式表达时，模型可写为： 0 )(. (min) max1XbxptsCXznjjj，或矩阵形式为：矩阵形式为：mnmmnnaaaaaaaaaA212222111211CXz min)( max或 0 )(.XbAXts或其中：其中：A A为约束方程组（约束条件）的系数矩阵。为约束方程组（约束条件）的系数矩阵。三、线性规划问题的标准形式三、线性规划问

10、题的标准形式njjjxczMax1), 1(0), 1(. .1njxmibxatsjnjijij化一般形式为标准形式的方法：化一般形式为标准形式的方法： 1 1、目标函数为求极小值，即为、目标函数为求极小值，即为: :njjjxcz1minnjjjxczMax1因为求因为求Min zMin z，等价于求，等价于求Max(-z)Max(-z)，令，令z z=-z=-z，即化为：，即化为：2 2右端项右端项b bi i0 0 只需将等式或不等式两端同乘只需将等式或不等式两端同乘(-1)(-1)，则等式右端项必大于，则等式右端项必大于零。零。 3 3约束条件为不等式：约束条件为不等式： 当约束条件

11、为当约束条件为“”时，需将约束条件左端加松弛变量；时，需将约束条件左端加松弛变量； 当约束条件为当约束条件为“”时，需将约束条件左端减去剩余变时，需将约束条件左端减去剩余变量。量。4 4取值无约束的变量取值无约束的变量 可令可令x xx x-x-x”，其中，其中x x00，x x”0 0 5 5对对x0 x0的情况的情况 令令x x-x-x，显然，显然x x0 0 【例例1-31-3】将下述线性规划化为标准形式将下述线性规划化为标准形式 解：解：上述问题中令：上述问题中令：取值无约束321321321321321, 0, 0632442392. .32minxxxxxxxxxxxxtsxxxz

12、ZZ 得到得到 ZZmax11xx 333xxx 在第一个约束条件的左端加入一个松弛变量在第一个约束条件的左端加入一个松弛变量 )0(44xx在第二个约束条件是左端减去一个剩余变量在第二个约束条件是左端减去一个剩余变量 )0(55xx将第三个约束条件两端同乘将第三个约束条件两端同乘“-1-1” 该问题的标准形式为：该问题的标准形式为： 0,63324422392. .00332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz第二节第二节 线性规划线性规划图解法图解法一、什么是图解法一、什么是图解法二、图解法步骤二、图解法步骤【

13、例例1-41-4】用图解法求解下列线性规划问题：用图解法求解下列线性规划问题： 三、图解法举例三、图解法举例 图解法的步骤可概括为：图解法的步骤可概括为： ( (一一) )建立平面直角坐标系；建立平面直角坐标系； ( (二二) )利用约束条件，确定线性规划问题解的可行域；利用约束条件，确定线性规划问题解的可行域； ( (三三) )绘制目标函数的等值线和法线；绘制目标函数的等值线和法线； ( (四四) )沿法线方向移动目标函数等值线至可行域的边缘，沿法线方向移动目标函数等值线至可行域的边缘，寻求问题最优解。若该问题存在最优解，则在可行域的边缘得寻求问题最优解。若该问题存在最优解，则在可行域的边缘

14、得到问题的最优解。到问题的最优解。 0,655362316. .7090max212212121xxxxxxxtsxxz)()()()(dcba0 x2 x10,6553623167090max212212121xxxxxxxxxz)()()()(dcba(a)(b)(c)(4,12)可行域可行域等值线等值线 最优解：最优解：x1 = 4， x2 = 12最优目标函数值：最优目标函数值：z = 1200z = 12000 x2 x1(a)(b)(c)四、四、线性规划问题解的可能结果线性规划问题解的可能结果 （一）无穷多最优解（一）无穷多最优解0,6553623166090max21221212

15、1xxxxxxxxxz)()()()(dcba (二二)无界解无界解0,6556090max21221xxxxxz (三三)无解无解2123maxxxz0,622212121xxxxxx五、图解法求解线性规划问题给我们的启示五、图解法求解线性规划问题给我们的启示p线性规划的可行域是一个什么形状？ 多边形，而且是“凸”形的多边形。p最优解在什么位置获得？ 在边界，而且是在某个顶点获得。思考结论：p线性规划的约束集（即可行域）是一个凸多面体。凸多面体是凸集的一种。所谓凸集是指：集中任两点的连 线仍属此集。p线性规划的最优解（若存在的话）必能在可行域的顶点获得。因为，由图解法可知，只有当目标直线平移

16、到边界时， 才能使目标函数值z达到最大限度的优化。问题：本性质有何重要意义？ 它使得在可行域中寻优的工作由“无限”上升为“有 限”，从而为线性规划的算法设计提供了重要基础。p线性规划解的几种情况线性规划解的几种情况1、可行域为封闭的有界区域(a)有唯一的最优解；(b)有一个以上的最优解；2、可行域为非封闭的无界区域(a)有唯一的最优解；(b)有一个以上的最优解；(c)目标函数无界（即虽有可行解，但在可行域中，目标函数可以无限增大或无限减小），因而没有最优解。3、可行域为空集，因而没有可行解。第三节第三节 线性规划问题解的性质线性规划问题解的性质 1. .满足所有约束满足所有约束条件（包括非负条

17、件）条件（包括非负条件）的解。的解。 可行解的集合称为可行可行解的集合称为可行集，或可行域。集，或可行域。 2. .使目标函数达使目标函数达到极值的解（理应属于到极值的解（理应属于可行解集）。可行解集）。9040B30 x2x1O4x1+5x2 2003x1+10 x2 3009x1+4x2 36010040 50可行解可行解可行域可行域最优解最优解原原LP：Max Z=7x1+12x2 s.t. 0,300103200543604921212121xxxxxxxxm为约束方程的个数，为约束方程的个数， n为变量的个数，为变量的个数，约束方程组约束方程组的系数矩阵的系数矩阵A（ m n ），且

18、），且m 0 x5=60 因此因此。 这种用来确定出基变量的规则称为这种用来确定出基变量的规则称为 。 新的基变量新的基变量x1,x5x1,x5；新的非基变量；新的非基变量x2,x3,x4x2,x3,x4； 写出写出 当用非基变量表示目标函数的表达式中，当用非基变量表示目标函数的表达式中，时，时，当前的基本可行解就是当前的基本可行解就是! ! 为什麽？为什麽？ 分析用非基变量表示目标函数的表达式，分析用非基变量表示目标函数的表达式，如果如果，基本思路基本思路: : 先找出一个基可行解，判断其是否为最优解，如果为否，则先找出一个基可行解，判断其是否为最优解，如果为否，则转换到相邻的基可行解，并使

19、目标函数值不断增大，直到找到最转换到相邻的基可行解，并使目标函数值不断增大，直到找到最优解为止。优解为止。二、单纯形法的求解步骤二、单纯形法的求解步骤1.1.确定初始基可行解确定初始基可行解 njjjxcz1max)4 . 1 (), 1(0)3 . 1 (1njxbxPjnjjj对于标准形的线性规划问题：对于标准形的线性规划问题： 约束条件的变量的系数矩阵中总会存在一个单位矩阵：约束条件的变量的系数矩阵中总会存在一个单位矩阵：100010001),(21mPPP 当约束条件均为当约束条件均为号时，加上松弛变量号时，加上松弛变量x xs1s1,x,xs2s2, ,x,xsmsm的系数的系数矩阵

20、即为单位矩阵。矩阵即为单位矩阵。mPP,1mxx,1nmmxxx,21称为基向量，同其对应的变量称为基向量，同其对应的变量称为基变量，称为基变量，模型中的其它变量模型中的其它变量称为非基变量。称为非基变量。用非基变量表示基变量可得到：用非基变量表示基变量可得到：nmnmmmmmmmmnnmmmmnnmmmmxaxaxabxxaxaxabxxaxaxabx22,11,222, 211, 222122, 111, 111TmTnmmbbxxxxX)0 , 0 ,(),(111)0(令所有非基变量等于零，即可找到一个解令所有非基变量等于零，即可找到一个解: :简写为：简写为：ninmmimmiiix

21、axaxabx22,11,(1.5)2.2.最优性检验最优性检验 将将(1.5)(1.5)式代入目标函数：式代入目标函数： njjjxcZ1nmjjjmiiixcxc11nmjjjminmjjijiixcxabc111nmjjmiijijmiiixaccbc111设：设：miijiacz10则：则：jjjzc 检验数检验数miijijjacc1设：设：miijiacz10则：则：jjjzc 检验数检验数miijijjacc1 TmkbbbX0 , 0 ,21nmjxj, 10j0lm 定理定理1.51.5（无穷多最优解）（无穷多最优解）设设 为对应为对应于基于基B B的一个基可行解，且对于一切

22、的一个基可行解，且对于一切 有有 ，同时又存在某个非基变量的检验数同时又存在某个非基变量的检验数 ，则线性规划问题存，则线性规划问题存在无穷多最优解。在无穷多最优解。 TmkbbbX0 , 0 ,21nmjxj, 10j kX 定理定理1.41.4（最优解）（最优解）设设 为对应于基为对应于基B B的的一个基可行解，且对于一个基可行解，且对于 一切有一切有 ，则，则 为线为线性规划问题的最优解。性规划问题的最优解。 TmkbbbX0 , 0 ,210lmmialmi, 10, 定理定理1.61.6（无界解）（无界解）设设 为对应于基为对应于基B B的的一个基可行解，存在某个非基变量的检验数一个

23、基可行解，存在某个非基变量的检验数 ，且，且有有 ，则线性规划问题具有无界解。，则线性规划问题具有无界解。3.3.寻找新的基可行解寻找新的基可行解 确定进基变量确定进基变量 lmjjnmj, 1, 0max对应的变量对应的变量 为进基变量。为进基变量。lmx确定离基变量确定离基变量 lmhhlmilmiiabmiaab, 1, 0min对应的变量对应的变量 为离基变量。为离基变量。hx迭代计算迭代计算 lmPlmha,lmha,lmP 对于列向量对于列向量 ，以，以 为主元素，将为主元素，将 变为变为1 1，其余变为，其余变为0 0，即将向量，即将向量 变换为单位向量。变换为单位向量。 重复重

24、复2 2、3 3直到所有的检验数小于等于直到所有的检验数小于等于0 0为止，则问题得到最为止，则问题得到最优解。优解。 第第1 1步：确定初始基可行解，列出初始单纯形表。步：确定初始基可行解，列出初始单纯形表。 为了书写规范和便于计算，对单纯形法的计算设计了一种为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表。专门表格，称为单纯形表。 jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001Ziibc0 0 ijijjacc 二、单纯形表二、单纯形表 第第2 2步：最优性检验。步：最优性检验。

25、如表中所有检验数如表中所有检验数j j00，且基变量中不含有人工变量时，且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。对基变量中含人工变表中的基可行解即为最优解，计算结束。对基变量中含人工变量时的解的最优性检验将在下一节中讨论。当表中存在量时的解的最优性检验将在下一节中讨论。当表中存在j j00又又P Pj j000，对应的变量，对应的变量x xj j就可作为换入基的变量，就可作为换入基的变量，当有一个以上检验数大于零时，一般从中找出最大一个当有一个以上检验数大于零时，一般从中找出最大一个k k。0|maxjjlmlmx作为进基变量作为进基变量( (也称换入变量也称换入变量)

26、 )确定进基变量。确定进基变量。 确定离基变量。确定离基变量。 根据最小根据最小的规则确定：的规则确定： lmhhlmilmiiaboaab,|minhx确定确定是离基的变量是离基的变量( (也称换出变量也称换出变量) )。lmha,元素元素 决定了从一个基可行解到相邻基可行解的转移去向，决定了从一个基可行解到相邻基可行解的转移去向，取名主元素。取名主元素。 以以a ah,m+lh,m+l，为主元素进行迭代。，为主元素进行迭代。 迭代计算迭代计算 第第4 4步：重复第步：重复第2 2，3 3两步，直到所有的检验数小于等于两步，直到所有的检验数小于等于0 0时，时，计算结束。计算结束。【例例1-

27、51-5】用单纯形法求解线性规划问题用单纯形法求解线性规划问题 0,6553623167090max212212121xxxxxxxxxz解：解：将上述问题化为标准形式有：将上述问题化为标准形式有： 0,6553623167090max543215242132121xxxxxxxxxxxxxxxz其约束条件系数矩阵为：其约束条件系数矩阵为： 100500102300111列出初始单纯形表为：列出初始单纯形表为： cj 90 70 0 0 0 cBxBb x1 x2 x3 x4 x5000 x3x4x5163665 1 1 1 0 0 3 2 0 1 0 0 5 0 0 1j i36/316/1

28、0900 x3x1x5 j90070000651215001001/32/370901x2x1x5 j401/31-1/300100-30012181312013-10500-1551410-2100-300-20-1/2Max z2xl+x2 0,21xx52x 2461x 1552x22xx1例：利用单纯形法求解下列问题例：利用单纯形法求解下列问题化为标准型化为标准型 0,54321xxxxx 15532xx 0002max54321xxxxxz 552xxx1 24641xx 2x2cj 2 1 0 0 0 cBxBb x1 x2 x3 x4 x5000 x3x4x515245 0 5

29、1 0 0 6 2 0 1 0 1 1 0 0 1j i24/65/1020 x3x1x5 j2010001412/30-1/61001/61/3021x3x1x2 j150510001/30-1/303123/215/20015/4-15/23/2010-1/43/27/21001/4-1/2000-1/4-1/2建立初始单纯形表如下：建立初始单纯形表如下：第五节第五节 单纯形法的其他问题讨论单纯形法的其他问题讨论一、关于标准形为最小化问题一、关于标准形为最小化问题目标函数为最小化的标准形式，最优性检验的判别定理目标函数为最小化的标准形式，最优性检验的判别定理 ： TmkbbbX0 , 0

30、,21nmjxj, 10j kX 定理定理1.71.7（最优解）（最优解）设设 为对应于基为对应于基B B的一个基可行解，且对于一切的一个基可行解，且对于一切 有有 ，则，则 为线性规划问题的最优解。为线性规划问题的最优解。 TmkbbbX0 , 0 ,21nmjxj, 1 0j0lm 定理定理1.81.8（无穷多最优解）（无穷多最优解）设设 为对为对应于基应于基B B的一个基可行解，且对于一切的一个基可行解，且对于一切 有有 ，同时又存在某个非基变量的检验数，同时又存在某个非基变量的检验数 ，则线，则线性规划问题存在无穷多最优解。性规划问题存在无穷多最优解。 TmkbbbX0 , 0 ,21

31、0lmmialmi, 10, 定理定理1.91.9（无界解）（无界解）设设 为对应于基为对应于基B B的一个基可行解，存在某个非基变量的检验数的一个基可行解，存在某个非基变量的检验数 ，且，且有有 ，则线性规划问题具有无界解。，则线性规划问题具有无界解。二、人工变量法二、人工变量法 【例例1-61-6】用单纯形法求解线性规划问题用单纯形法求解线性规划问题 0,12210243423max321321321321321xxxxxxxxxxxxxxxz解：解：将其化成标准形式有将其化成标准形式有 0,1221024340023max543213215321432154321xxxxxxxxxxxx

32、xxxxxxxxxz 上述标准化模型中，不存在单位矩阵，为构造单位矩阵，则上述标准化模型中，不存在单位矩阵，为构造单位矩阵，则需要通过添加人工变量的方法，人为构造一个单位矩阵，该方需要通过添加人工变量的方法，人为构造一个单位矩阵，该方法即所谓的人工变量法。法即所谓的人工变量法。 1. 1.大大M M法法 大大M M法又称惩罚法，其法又称惩罚法，其基本思想基本思想是：约束条件加入人工变量是：约束条件加入人工变量后，为使目标函数取值不受影响，给定它们在求最大值后，为使目标函数取值不受影响，给定它们在求最大值(max)(max)的的目标函数中的系数为目标函数中的系数为(-M)(-M)(称为惩罚因子，

33、称为惩罚因子，M M为任意大的正数为任意大的正数) )，以作为对基变量中存在人工变量的惩罚，从而迫使人工变量从以作为对基变量中存在人工变量的惩罚，从而迫使人工变量从基变量中分离出来，否则目标函数将不能实现最大化。基变量中分离出来，否则目标函数将不能实现最大化。 添加人工变量后，例添加人工变量后，例1-61-6的数学模型形式变为：的数学模型形式变为： 0,1221024340023max765432173215321643217654321xxxxxxxxxxxxxxxxxxxxMxMxxxxxxz列出初始单纯形表如下：列出初始单纯形表如下： cj32-100- M- McBxBbx1X2x3x

34、4x5x6x7- Mx64-431-101040 x5101-1201005- Mx712-2100011j3-2M2+M-1+2M-M000-mx60 x5- 1x3ji38-60-101-1-330010-2-2100011- 2M5-6M5M-M000213/58/32x20 x5-1x3j-6/53/510-1/501/5-1/531/5003/51-3/5-7/511/5-2/501-2/502/53/550000-M1-M53/531/32x21301012-1-33x131/310015/3-1-7/3-1x319/300102/30-1/3j000-5-25/35-M38/3-

35、M 计算机处理数据时，只能用很大的数代替计算机处理数据时，只能用很大的数代替M, ,可能造成计算可能造成计算机上的错误，故多采用两阶段法。机上的错误，故多采用两阶段法。 2 2、两阶段法、两阶段法第一阶段：第一阶段：添加人工变量，重新构造目标函数添加人工变量，重新构造目标函数 将原问题加入人工变量，构造仅含人工变量的新的目标函将原问题加入人工变量，构造仅含人工变量的新的目标函数，并要求实现最小化。新的目标函数形式如下：数，并要求实现最小化。新的目标函数形式如下： mnnnxxxw21min), 1, 2 , 1(02211222222121111212111mnnnjxbxxaxaxabxxa

36、xaxabxxaxaxajmmnnmnmmnnnnnn 求解上述线性规划问题。若求解上述线性规划问题。若w=0w=0，则原线性规划问题存在，则原线性规划问题存在基可行解，计算转入第二阶段；若基可行解，计算转入第二阶段；若w0w0，则原线性规划问题无，则原线性规划问题无可行解，计算停止。可行解，计算停止。 第二阶段：第二阶段：对原目标函数求解对原目标函数求解 在第一阶段的最终单纯形表中，将才在第一阶段的最终单纯形表中，将才c cj j行的数字换为原目标行的数字换为原目标函数的系数，并且去掉表中含有人工变量的列，继续求解。函数的系数，并且去掉表中含有人工变量的列，继续求解。 将例将例1-61-6问

37、题利用两阶段法进行求解。问题利用两阶段法进行求解。 第一阶段：添加人工变量，重新构造目标函数。例第一阶段：添加人工变量，重新构造目标函数。例1-61-6用两用两阶段法求解时，第一阶段的线性规划问题可写为：阶段法求解时，第一阶段的线性规划问题可写为： 0,122102434min7654321732153216432176xxxxxxxxxxxxxxxxxxxxxxw将上述数学模型标准化后，用单纯形法求解过程见下表：将上述数学模型标准化后，用单纯形法求解过程见下表： cj00000- 1-1cBxBbx1X2x3x4x5x6x7- 1x64-431-101040 x5101-1201005- 1

38、x712-2100011j-212-1000-1x60 x50 x3ji38-60-101-1-330010-2-210001-2-65-100013/58/30 x20 x50 x3j-6/53/510-1/501/5-1/531/5003/51-3/5-7/511/5-2/501-2/502/53/500000-1-153/5可以看出：可以看出：W=0W=0，该问题有解；转入第二阶段。，该问题有解；转入第二阶段。cj32-100cBxBbx1x2x3x4x52x23/5-6/510-1/500 x531/53/5003/51-1x311/5-2/501-2/50j500002x213010

39、123x131/310015/31x319/300102/3j000-5-22/3i第二阶段：第二阶段： 得最优解。得最优解。 将第一阶段得到的最终单纯形表的人工变量列去掉，将目将第一阶段得到的最终单纯形表的人工变量列去掉，将目标标C Cj j行换为原怒表函数的系数，再进行迭代。行换为原怒表函数的系数，再进行迭代。31/3三、单纯形法计算中退化与循环问题三、单纯形法计算中退化与循环问题 1 1、单纯形法计算中按最小比值来确定离基变量时，有时存、单纯形法计算中按最小比值来确定离基变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就会出现一在两个以上相同的最小比值，这样在下一次迭代中就会出

40、现一个或多个基变量等于零的情形，这就出现了所谓的退化解。当个或多个基变量等于零的情形，这就出现了所谓的退化解。当存在退化解时，就有可能出现迭代计算的循环。存在退化解时，就有可能出现迭代计算的循环。 勃兰特规则：勃兰特规则： (1) (1)当存在多个当存在多个 且相等时，选取且相等时，选取 中下标值最小中下标值最小的变量作为进基变量；的变量作为进基变量； 0j0j (2) (2)当按当按规则计算出现两个或两个以上相同的最小比值时，规则计算出现两个或两个以上相同的最小比值时，选取下标值最小的变量作为离基变量。选取下标值最小的变量作为离基变量。 2 2、为确定出基变量要计算比值，该比值、为确定出基变

41、量要计算比值，该比值= =解解答列元素答列元素/ /主元列元素。主元列元素。 1212121min2.220(1,2)jzxxxxs txxxj （ ）12123124LPmax2.220(1,2,3,4)jzxxxxxs txxxxj 标标准准化化：15用用单单纯纯形形方方法法解解下下列列线线性性规规例例划划问问题题。四、解的其它情况四、解的其它情况列列单单纯纯形形表表：12343411000211100221011100jBBjjjCCXbxxxxxxcz 220iiiibaa (1)列列单单纯纯形形表表：11140(0,2,0,4),2Xzxxx 1 1此此表表已已是是最最优优表表。但但

42、非非基基变变量量 的的检检验验数数=0=0。选选择择 为为进进基基变变量量，只只有有为为出出基基变变量量，旋旋转转变变换换如如下下。(2)123424110002111004101100102jBBjjjCCXbxxxxxxcz 列列单单纯纯形形表表：123421110006012104101100102jBBjCCXbxxxxxx 2120(4,6,0,0) ,2LP(1)TXzXXX 此此表表也也是是最最优优表表。有有无无穷穷最最优优解解：(3)jjcz1212122max25.25100(1,2)jzxxxxs txxxj （ ）12123124LPmax25.25100(1,2,3,4

43、)jzxxxxxs txxxxj 标标准准化化：列列单单纯纯形形表表：123434210005111001025012100jBBjjjCCXbxxxxxxcz 110iiiibaa 列列单单纯纯形形表表：123431210001003 211 20515 201 20601jBBjjjCCXbxxxxxxcz LP有有进进基基变变量量，而而无无出出基基变变量量。无无最最优优解解。20 (1,2)iai121212max0.330(1,2)jzxxxxs txxxj ( (2 2) ) 5x解解（2 2）标标准准化化后后，增增加加人人工工变变量量 ：1251231245max0.330(1,2

44、,3,4,5)jzxxMxxxxs txxxxxj (2) (2) 12345351100001110033101113100jBBjjjCMCXbxxxxxxMxczMMM 1BCC B A (1,1,0,0,)(0,)MM-11100-11100-310-11-310-11(1,1,0,0,)(3,0,)MMMMM(13,1,0,0)MMM12345251100101110032011122010jBBjjjCMCXbxxxxxxMxczMMM LP5maxx 所所有有的的检检验验数数0,0,此此表表为为最最优优表表（问问题题）, ,但但人人工工变变量量 (=3)(=3)仍仍为为基基变变量

45、量, ,则则原原无无可可行行解解。12123123(2)min221.260(1,2,3)jzxxxxxs txxxxj - -1123461376752221260(1,2,3,4,5,6,7(n2mi)jxxxxxxxxxxxxxxxj 123456767000001111121101016121010172001100jBBCCXbxxxxxxxxx jjjcz 0j 则则原原问问题题无无可可行行解解，从从而而无无最最优优解解。70min 此此表表已已为为最最优优表表，121211212max2030310150,30,40,0.zxxxxxxxx x标数约条目函束件练习练习1 1：单纯

46、形表求解下列线性规划问题：单纯形表求解下列线性规划问题121212212max5050300,2400,250,0.zxxxxxxxx xs.t练习练习2 2：用单纯形法表求解下面的线性规划问：用单纯形法表求解下面的线性规划问题。题。1122111111112211221112max. .,.,00mmmmnnmmnnmmnnmmmmmnnmmnizc xc xc xcxc xxaxa xbxaxa xbs txaxaxbx xxxb （）LP设设为为：12121(,.,),(,.,0,.,0)mTmmiiBP PPXb bbzc 显显然然初初始始可可行行基基为为初初始始基基可可行行解解为为五

47、、单纯形法小结五、单纯形法小结1111(1,2,.,)max()niiijjj mmnmiijiijjij mixba ximzc bcc ax 或或写写为为：max()BNBNzC bCC A X01max()njjjj mzzcz x 111101()BNBNBjjNnj mBzC B bCC B N xxB bB Nzxx 记记相相应应于于基基 下下的的消消去去为为系系统统为为：判判断断最最优优及及换换基基变变换换：01max()njjjj mzzczx 0jjjcz 当当所所有有的的检检验验数数时时，得得到到最最优优；0kkkkczx 当当有有检检验验数数时时，换换基基变变换换：为为进

48、进基基变变量量1min0milikliiklklkbbaxaaa 为为出出基基变变量量 为为旋旋转转中中心心；第六节第六节 线性规划应用举例线性规划应用举例l合理利用线材问题：合理利用线材问题：如何下料如何下料使用材最少。使用材最少。l配料问题：配料问题：在原料供应量的限在原料供应量的限制下如何获取最大利润。制下如何获取最大利润。l投资问题：投资问题：从投资项目中选取从投资项目中选取方案，使投资回报最大。方案，使投资回报最大。线性规划线性规划-l产品生产计划：产品生产计划：合理利用人力、物力、合理利用人力、物力、财力等，使获利最大。财力等，使获利最大。l劳动力安排：劳动力安排：用最少的劳动力来

49、满足用最少的劳动力来满足工作的需要。工作的需要。l运输问题：运输问题：如何制定调运方案，使总如何制定调运方案，使总运费最小。运费最小。 数学规划的建模有许多共同点，要遵循下列原则： (1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。 (2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误和公式错误。 (3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑

50、。 建立线性规划模型的过程可以分为四个步骤： (1)设立决策变量； (2)明确约束条件并用决策变量的线性等式或不等式表示； (3)用决策变量的线性函数表示目标，并 确 定 是 求 极 大 （ M a x ） 还 是 极 小（Min）； (4)根据决策变量的物理性质研究变量是否有非负性。一、混合配料问题一、混合配料问题 【例例1-71-7】某工厂要用三种原材料某工厂要用三种原材料C C、P P、H H混合调配出三种混合调配出三种不同规格的产品不同规格的产品A A、B B、D D。已知产品的规格、产品单价、每天。已知产品的规格、产品单价、每天能供应的原材料数量及原材料单价如表能供应的原材料数量及原

51、材料单价如表1-101-10、表、表1-111-11所示。问所示。问该厂如何安排生产，利润收入最大？该厂如何安排生产，利润收入最大？表表1-1025不限D原材料P不超过50%35原材料C不少于25%B原材料P不超过25%50原材料C不少于50%A单价(元/kg)规格要求产品名称表表1-113560H25100P65100C单价(元/kg)每天最大供应量(kg)原材料名称解：解：设设A Ac c表示表示A A产品中产品中C C的成分，其数量用的成分，其数量用x x1 1表示；表示； A AP P表示表示A A产品中产品中P P的成分，其数量用的成分，其数量用x x2 2表示；表示； A AH H

52、表示表示A A产品中产品中H H的成分，其数量用的成分，其数量用x x3 3表示；表示； B BC C表示表示B B产品中产品中C C的成分，其数量用的成分，其数量用x x4 4表示；表示； B BH H表示表示B B产品中产品中H H的成分，其数量用的成分，其数量用x x6 6表示；表示； B BP P表示表示B B产品中产品中P P的成分，其数量用的成分，其数量用x x5 5表示；表示； D DC C表示表示D D产品中产品中D D的成分，其数量用的成分，其数量用x x7 7表示；表示； D DH H表示表示D D产品中产品中H H的成分，其数量用的成分，其数量用x x9 9表示表示. .

53、 D DP P表示表示D D产品中产品中P P的成分，其数量用的成分，其数量用x x8 8表示；表示； 321xxxAAAAHPC654xxxBBBBHPC987xxxDDDDHPC依据题意，得：依据题意，得： 依据产品规格要求得：依据产品规格要求得： HPCCAAAA21HPCPAAAA41HPCCBBBB41HPCPBBBB210212121HPCAAA0414341HPCAAA0414143HPCBBB0212121HPCBBB整理得：整理得： 100CCCDBA100PPPDBA60HHHDBA依据原材料每天供应量限制得：依据原材料每天供应量限制得：该问题的线性规划数学模型为：该问题的

54、线性规划数学模型为： 963852741987654321352565253550maxxxxxxxxxxxxxxxxxxxz9 , 2 , 10601001000212121041414304143410212121963852741654654321321jxxxxxxxxxxxxxxxxxxxxxxj二、生产计划安排问题二、生产计划安排问题 【例例1-81-8】某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A A、B B两两道工序加工。设道工序加工。设A A工序可分别在设备工序可分别在设备A A1 1或或A A2 2上完成，有上完成，有B B1 1、B B2 2、B B3 3三种

55、设备可用于完成三种设备可用于完成B B工序。已知产品工序。已知产品可在可在A A、B B任何一种任何一种设备上加工；产品设备上加工；产品可在任何规格的可在任何规格的A A设备上加工，但完成设备上加工，但完成B B工工序时，只能在序时，只能在B B1 1设备上加工；产品设备上加工；产品只能在只能在A A2 2与与B B2 2设备上加工。设备上加工。加工单位产品所需工序时间及其它各项数据见下表，试安排最加工单位产品所需工序时间及其它各项数据见下表，试安排最优生产计划，使该厂获利最大。优生产计划，使该厂获利最大。设备产品设备有效台时设备加工费A151060000.05A27912100000.03B

56、16840000.06B241170000.11B3740000.05原料费（元/件）0.250.350.50售价（元/件）1.252.002.80 解：解：设产品设产品、的产量分别为的产量分别为x x1 1,x,x2 2,x,x3 3件。件。 产品产品有有6 6种加工方案，分别利用设备种加工方案，分别利用设备(A(A1 1,B,B1 1)(A)(A1 1,B,B2 2)(A)(A1 1,B,B3 3)(A)(A2 2，B B1 1)(A)(A2 2,B,B2 2)(A)(A2 2,B,B3 3) )，各方案加工的产，各方案加工的产品品数量用数量用X Xllll，x x1212，x x1313

57、，x x1414，x x1515，x x1616表示；产品表示；产品有有2 2种加工种加工方案，即方案，即(A(A1 1,B,B1 1)(A)(A2 2,B,B1 1) )，加工数量用，加工数量用x x2121，x x2222表示；产品表示；产品只有只有1 1种加工方案种加工方案(A(A2 2,B,B2 2) )，加工数量等于，加工数量等于x x3 3。 222121615141312111xxxxxxxxxx 工厂的盈利为产品售价减去相应的原料费和设备加工费。产工厂的盈利为产品售价减去相应的原料费和设备加工费。产品加工量只受设备有效台时的限制。故可建立如下线性规划模型：品加工量只受设备有效台

58、时的限制。故可建立如下线性规划模型： )(35. 00 . 2()(25. 025. 1 (max2221161514131211xxxxxxxxz)12977(03. 0)10555(05. 0)05. 080. 2(22211514211312113xxxxxxxxx)12977(03. 0)10555(05. 0)05. 080. 2(22211514211312113xxxxxxxxx040007770004440008666100001297776000105551613315122221141132216151421131211ijxxxxxxxxxxxxxxxxxxx三、生产与存

59、贮问题三、生产与存贮问题 解：解：设设x xijij为为i i种产品种产品j j月份在正常时间内生产的数量，月份在正常时间内生产的数量， 为为第第i i种产品种产品j j月份在加班时间内生产的数量。该厂盈利总额为生月份在加班时间内生产的数量。该厂盈利总额为生产的产的5 5种产品销售价减去成本和库存费用。问题的限制条件有两种产品销售价减去成本和库存费用。问题的限制条件有两项：一是各个月的正常和加班的允许工时，二是满足交货要求。项：一是各个月的正常和加班的允许工时，二是满足交货要求。本例的线性规划模型可表示为本例的线性规划模型可表示为: : ijx 【例例1-91-9】某厂签订了某厂签订了5 5种

60、产品种产品(i(i1 1，5)5)上半年的交货合上半年的交货合同。已知各产品在第同。已知各产品在第j j月月(j(j1 1，6)6)的合同交货量的合同交货量D Dijij，该月，该月售价售价s sijij、成本价、成本价c cijij及生产及生产1 1件时所需工时件时所需工时a aijij。该厂第。该厂第j j月的正常月的正常生产工时为生产工时为t tj j，但必要时可加班生产，第，但必要时可加班生产，第j j月允许的最多加班工月允许的最多加班工时不超过时不超过 ，并且加班时间内生产出来的产品每件成本增加额，并且加班时间内生产出来的产品每件成本增加额外费用外费用 元；若生产出来的产品当月不交货