《线性规划与单纯形法 (2)精选PPT.ppt》由会员分享，可在线阅读，更多相关《线性规划与单纯形法 (2)精选PPT.ppt（115页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于线性规划与单纯关于线性规划与单纯形法形法(2)第1页，讲稿共115张，创作于星期三2运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线线 性性 规规 划及单纯形法划及单纯形法Linear ProgrammingLinear Programming第一章第一章第2页，讲稿共115张，创作于星期三3Chapter1 线性规划线性规划(Linear Programming)(Linear Programming)LP的数学模型的数学模型 图解法图解法 单纯形法单纯形法 单纯形法的进一步讨论单纯形法的进一步讨论 LP模型的应用模型的应用本章主要内容：本章主要内容：第3页，讲稿共
2、115张，创作于星期三4线性规划问题的数学模型线性规划问题的数学模型1.规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、物力生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划等各种资源得到充分利用，获得最大的效益，这就是规划问题。问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用最）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源少的资源 （如资金、设备、原标材料、人工、时间等）去完（如资金、
3、设备、原标材料、人工、时间等）去完成确定的任务或目标成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多益（如产品量最多 、利润最大、利润最大.）第4页，讲稿共115张，创作于星期三5线性规划问题的数学模型线性规划问题的数学模型例例1.1 如图所示，如何截取如图所示，如何截取x使铁皮所围成的容积最使铁皮所围成的容积最大？大？x xa a第5页，讲稿共115张，创作于星期三6线性规划问题的数学模型线性规划问题的数学模型例例1.2 某厂生产两种产品，下某厂生产两种产品，下表给出了单位产品所需资
4、源及单表给出了单位产品所需资源及单位产品利润位产品利润 问：应如何安排生产计划，才问：应如何安排生产计划，才能使总利润最大？能使总利润最大？解：解：1.1.决策变量：设产品决策变量：设产品I I、IIII的产量的产量 分别为分别为 x1、x22.2.目标函数：设总利润为目标函数：设总利润为z z，则有：，则有：max z=2 x1+x23.3.约束条件：约束条件：5x2 15 6x1+2x2 24 x1+x2 5 x1，x20第6页，讲稿共115张，创作于星期三7线性规划问题的数学模型线性规划问题的数学模型例例1.3 已知资料如下表所示，问已知资料如下表所示，问如何安排生产才能使利润最大如何安
5、排生产才能使利润最大？或如何考虑利润大，产品好销。？或如何考虑利润大，产品好销。设 备产 品 A B C D利润（元）2 1 4 0 2 2 2 0 4 3 有 效 台 时12 8 16 12解：解：1.1.决策变量：设产品决策变量：设产品I I、IIII的产量分别的产量分别为为 x1、x22.2.目标函数：设总利润为目标函数：设总利润为z z，则有：，则有：max z=2 x1+x23.3.约束条件：约束条件：x10,x202x1+2x212x1+2x284x1164x212第7页，讲稿共115张，创作于星期三8线性规划问题的数学模型线性规划问题的数学模型例例1.4 某厂生产三种药物，这某厂
6、生产三种药物，这些药物可以从四种不同的原料中些药物可以从四种不同的原料中提取。下表给出了单位原料可提提取。下表给出了单位原料可提取的药物量取的药物量 解：解：要求：生产要求：生产A种药物至少种药物至少160单单位；位；B种药物恰好种药物恰好200单位，单位，C种种药物不超过药物不超过180单位，且使原料单位，且使原料总成本最小。总成本最小。1.1.决策变量：设四种原料的使用决策变量：设四种原料的使用 量分别为：量分别为：x1、x2、x3、x42.2.目标函数：设总成本为目标函数：设总成本为z min z=5 x1+6 x2+7 x3+8 x43.3.约束条件：约束条件：x1+2x2+x3+x4
7、 160 2x1 +4 x3+2 x4 200 3x1 x2+x3+2 x4 180 x1、x2、x3、x4 0第8页，讲稿共115张，创作于星期三9 例例1.5 某航运局现有船只种类、数量以及计划期内各条航线的货运某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：量、货运成本如下表所示：航线号船队类型编队形式货运成本（千元队）货运量（千吨）拖轮A型驳船B型驳船1112362521436202322472404142720船只种类船只数拖 轮30A型驳船34B型驳船52航线号合同货运量12002400问：应如何编队，才能既完成合同任务，又使总货运成本为最小？问：应如何
8、编队，才能既完成合同任务，又使总货运成本为最小？线性规划问题的数学模型线性规划问题的数学模型第9页，讲稿共115张，创作于星期三10 解：解：设设xj为第为第j j号类型船队的队数（号类型船队的队数（j=1=1，2 2，3 3，4 4），），z 为总货运成本为总货运成本则：则：minz=36x1+36x2+72x3+27x4x1+x2+2x3+x4302x1+2x3344x2+4x3+4x45225x1+20 x220040 x3+20 x4400 xj 0（j=1,2,3,4）线性规划问题的数学模型线性规划问题的数学模型第10页，讲稿共115张，创作于星期三11线性规划问题的数学模型线性规划
9、问题的数学模型2.2.2.2.线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量 Decision variables Decision variables 目标函数目标函数目标函数目标函数 Objective functionObjective function约束条件约束条件约束条件约束条件 ConstraintsConstraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变
10、量的）问题的目标函数是多个决策变量的线性线性线性线性函数，通常是求函数，通常是求函数，通常是求函数，通常是求最大值或最小值；最大值或最小值；最大值或最小值；最大值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不等式或等不等式或等不等式或等不等式或等式。式。式。式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？第11页，讲稿共115张，创作于星期三12线性规划问题的数学模型线性
11、规划问题的数学模型3.3.3.3.建模条件建模条件建模条件建模条件(1)(1)优化条件优化条件优化条件优化条件：问题所要达到的目标能用线型函数描述，且能够用极：问题所要达到的目标能用线型函数描述，且能够用极：问题所要达到的目标能用线型函数描述，且能够用极：问题所要达到的目标能用线型函数描述，且能够用极值值值值 （max max 或或或或 minmin）来表示；）来表示；）来表示；）来表示；(2)(2)限定条件限定条件限定条件限定条件：达到目标受到一定的限制，且这些限制能够用：达到目标受到一定的限制，且这些限制能够用：达到目标受到一定的限制，且这些限制能够用：达到目标受到一定的限制，且这些限制能
12、够用决策变量的线性等式或线性不等式表示；决策变量的线性等式或线性不等式表示；决策变量的线性等式或线性不等式表示；决策变量的线性等式或线性不等式表示；(3)(3)选择条件选择条件选择条件选择条件：有多种可选择的方案供决策者选择，以便找出最优：有多种可选择的方案供决策者选择，以便找出最优：有多种可选择的方案供决策者选择，以便找出最优：有多种可选择的方案供决策者选择，以便找出最优方案。方案。方案。方案。第12页，讲稿共115张，创作于星期三13线性规划问题的数学模型线性规划问题的数学模型4.4.4.4.建模步骤建模步骤建模步骤建模步骤(1)(1)确定决策变量确定决策变量确定决策变量确定决策变量：即需
13、要我们作出决策或选择的量。一般情况下，：即需要我们作出决策或选择的量。一般情况下，：即需要我们作出决策或选择的量。一般情况下，：即需要我们作出决策或选择的量。一般情况下，先从目标函数考虑决策变量；先从目标函数考虑决策变量；先从目标函数考虑决策变量；先从目标函数考虑决策变量；(2)(2)写出目标函数写出目标函数写出目标函数写出目标函数：即问题所要达到的目标，并明确是：即问题所要达到的目标，并明确是：即问题所要达到的目标，并明确是：即问题所要达到的目标，并明确是max max 还是还是还是还是 minmin。(3)(3)找出所有限定条件找出所有限定条件找出所有限定条件找出所有限定条件：即决策变量受
14、到的所有的约束；：即决策变量受到的所有的约束；：即决策变量受到的所有的约束；：即决策变量受到的所有的约束；第13页，讲稿共115张，创作于星期三14线性规划问题的数学模型线性规划问题的数学模型约束条件：约束条件：约束条件：约束条件：5.5.5.5.线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：目标函数：目标函数：目标函数：目标函数：第14页，讲稿共115张，创作于星期三15线性规划问题的数学模型线性规划问题的数学模型向量形式：向量形式：向量形式：向量形式：其中：其中：第15页，讲稿共115张，创作于星期三16线性规划问题
15、的数学模型线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：第16页，讲稿共115张，创作于星期三17线性规划问题的数学模型线性规划问题的数学模型6.线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1)目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。第17页，讲稿共115张，创作于星期三18线性规划问题的数学模型线性规划问题的数学模型（2 2 2 2）如何化标准形式）如何化标准形式）如何化标准形式）
16、如何化标准形式 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标函数乘以(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：变量的变换变量的变换第18页，讲稿共115张，创作于星期三19线性规划问题的数学模型线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量 常量常量 bi0 的变换的变换:约束方程两边乘以约束方程两边乘以（1）
17、第19页，讲稿共115张，创作于星期三20线性规划问题的数学模型线性规划问题的数学模型例例1.6 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式用用 替换替换 ，且，且 解解:（）因为（）因为x3无符号要求无符号要求，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以第20页，讲稿共115张，创作于星期三21线性规划问题的数学模型线性规划问题的数学模型(2)第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(3)第二个约束条件是第二个约束条件是“”号，在号，在“”左
18、端减去剩余变量左端减去剩余变量x5，x50；(4)第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将右端常将右端常数项化为正数；数项化为正数；(5)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;第21页，讲稿共115张，创作于星期三22线性规划问题的数学模型线性规划问题的数学模型标准形式如下：标准形式如下：第22页，讲稿共115张，创作于星期三23 例例1.7 将下列线性规划问题化为标准形式将下列线性规
19、划问题化为标准形式为无约束（无非负限制）为无约束（无非负限制）线性规划问题的数学模型线性规划问题的数学模型第23页，讲稿共115张，创作于星期三24 解解:用用 替换替换 ，且，且 ，将第将第3 3个约束方程两边乘以（个约束方程两边乘以（1 1）将极小值问题反号，变为求极大值将极小值问题反号，变为求极大值标准形式如下：标准形式如下：引入变量引入变量线性规划问题的数学模型线性规划问题的数学模型第24页，讲稿共115张，创作于星期三25 例例1.8 将线性规划问题化为标准型将线性规划问题化为标准型解：解：线性规划问题的数学模型线性规划问题的数学模型第25页，讲稿共115张，创作于星期三26 例例1
20、.9 将线性规划问题化为标准型将线性规划问题化为标准型解：解：Minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x4396x2+2x3+3x4-58x1,x3 ,x40；x2无约束 Maxz=3x15x2+5x2”8x3+7x4s.t.2x13x2+3x2”+5x3+6x4+x5=284x1+2x2-2x2”+3x3-9x4-x6=39-6x2+6x2”-2x3-3x4-x7=58x1,x2,x2”,x3,x4,x5,x6,x70线性规划问题的数学模型线性规划问题的数学模型第26页，讲稿共115张，创作于星期三27线性规划问题的数学模
21、型线性规划问题的数学模型7.7.线性规划问题的解线性规划问题的解线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一的方程组中找出一个解，使目标函数个解，使目标函数(1)达到最大值。达到最大值。第27页，讲稿共115张，创作于星期三28线性规划问题解的概念线性规划问题解的概念 可行解可行解：满足约束条件：满足约束条件、的解为可行解。所有可行解的集合的解为可行解。所有可行解的集合为可行域。为可行域。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基：基：设设A为约束条件为约束条件的的mn阶系数矩
22、阵阶系数矩阵(m04010换出行将3化为15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/52/540011第51页，讲稿共115张，创作于星期三52单纯形法的计算步骤单纯形法的计算步骤例例1.13 用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。第52页，讲稿共115张，创作于星期三53单纯形法的计算步骤单纯形法的计算步骤cj12100icB基变量bx1x2x3x4x50 x4152-32100 x520
23、1/31501121000 x42x220 x x2 221/3150120753017131/309022560 x x1 111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第53页，讲稿共115张，创作于星期三54变成标准型变成标准型单纯形法的计算步骤单纯形法的计算步骤例例1.14 用单纯形法求解用单纯形法求解第54页，讲稿共115张，创作于星期三55约束方程的系数矩阵约束方程的系数矩阵 为基变量为基变量为非基变量为非基变量I I 为单位矩阵且线性独立为单位矩阵且线性独立单纯形法的计算步骤单纯形法的计算步骤第55页，讲稿共115张，创作于星期三56
24、第56页，讲稿共115张，创作于星期三57第57页，讲稿共115张，创作于星期三58第58页，讲稿共115张，创作于星期三59单纯形法的计算步骤单纯形法的计算步骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握线性规划问题的标准化熟练掌握线性规划问题的标准化 3.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤第59页，讲稿共115张，创作于星期三60单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法第60页，讲稿共115张，创作于星期三61单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法人工变量法
25、：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为的变量称为人工变量人工变量，构成的可行基称为，构成的可行基称为人工基人工基，用，用大大MM法法或或两阶段法两阶段法求解，这种用人工变量作桥梁的求解方法称求解，这种用人工变量作桥梁的求解
26、方法称为为人工变量法人工变量法。第61页，讲稿共115张，创作于星期三62大大 M 法法约束条件：约束条件：“”减一个剩余变量后，再加一个人工变量减一个剩余变量后，再加一个人工变量“”加一个人工变量加一个人工变量目标函数：目标函数：人工变量的系数为人工变量的系数为“M”，即罚因子，即罚因子若原线性规划问题有最优解则人工变量必为若原线性规划问题有最优解则人工变量必为0。第62页，讲稿共115张，创作于星期三63MaxZ=-3x1+x3-Mx6-Mx7 x1+x2+x3+x4 =4 -2x1+x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7MaxZ=-3x1+x3 x
27、1+x2+x34 -2x1+x2-x31 3x2+x3=9 xi 0,j=1,2,3增加人工变量后，线性规划问题中就存在一个增加人工变量后，线性规划问题中就存在一个B B为单位矩阵，为单位矩阵，阵，后面可以根据我们前面所讲的单纯形法来进行求解。阵，后面可以根据我们前面所讲的单纯形法来进行求解。标准化标准化及变形及变形第63页，讲稿共115张，创作于星期三64cj-30100-M-MCBXBbix1x2x3x4x5x6x70 x441111000-Mx61-21-10-110-Mx790310001j-3-2M4M100 3x2入，入，x6出出-M041 0 x40 x2-Mx73 30211-
28、10j6M-304M+10-4M -x1入，入，x7出出3M01-21-10-1101660403-311 0 x40 x2-3x100001-1/21/2-1/2j0030-M-3/2 9x3入，入，x1出出3/2-M+1/23011/30001/33/21102/301/2-1/21/6-0 x40 x21x300001-1/21/2-1/2j-9/2000-M+3/4-3/4-M-1/45/2-1/2100-1/41/41/43/23/20103/4-3/41/4所以：所以：所以：所以：X*=(xX*=(x2 2,x,x3 3,x,x4 4)T T=(5/2,3/2,0)=(5/2,3/
29、2,0)T T Z*=3/2 Z*=3/2第64页，讲稿共115张，创作于星期三65 第一阶段：第一阶段：暂不考虑原问题是否存在基可行解，给原问题暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为小化），人工变量的价值系数一般为1，约束条件和原问题，约束条件和原问题的一样。的一样。当第一阶段中目标函数的最优值当第一阶段中目标函数的最优值0，即人工变量，即人工变量0，则，则转入第二阶段；若第一阶段中目标函数的最优值不等于转入第二阶段；若第一阶段中目标函数的最优值不等于0，
30、即人工变量不等于即人工变量不等于0，则判断原问题为无解。，则判断原问题为无解。第二阶段：第二阶段：将第一阶段计算所得的单纯形表划去人工变量将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。段的初始单纯形表，进行进一步的求解。两两 阶阶 段段 法法第65页，讲稿共115张，创作于星期三66辅辅 助助 问问 题题第66页，讲稿共115张，创作于星期三67 辅辅 助助 问问 题题 与与 原原 问问 题题 的的 关关 系系第67页，讲稿共115张，创作于星期三68求求 辅辅
31、 助助 问问 题题 的的 三三 种种 情情 况况第68页，讲稿共115张，创作于星期三69求解辅助问题，得到辅助问求解辅助问题，得到辅助问题的最优解题的最优解引进人工变量引进人工变量x6，x7，构造辅助问题，构造辅助问题，辅助问题的目标函数为所有人工辅助问题的目标函数为所有人工变量之和的极小化变量之和的极小化MaxW=0?原问题没有可行解。原问题没有可行解。把辅助问题的最优解作为原问题把辅助问题的最优解作为原问题的初始基础可行解的初始基础可行解用单纯形法求解原问题，得到原问题用单纯形法求解原问题，得到原问题的最优解的最优解否否是两阶段法的算法流程图两阶段法的算法流程图MaxZ=-3x1+x3
32、x1+x2+x34 -2x1+x2-x31 3x2+x3=9 xi 0,j=1,2,3MaxW=-x6-x7 x1+x2+x3+x4 =4-2x1+x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7第69页，讲稿共115张，创作于星期三70cj00000-1-1CBXBbix1x2x3x4x5x6x70 x441111000-1x61-21-10-110-1x790310001(第一阶段）单纯形表第一阶段）单纯形表1 1j-24000 3x2入，入，x6出出-1041 0 x40 x2-1x7330211-10j6040-4 x1入，入，x7出出301-21-10-
33、1101660403-311 0 x40 x20 x100001-1/21/2-1/2j0000-10-13011/30001/31102/301/2-1/21/6所以：已得最优解，且人工变量为非基变量，则可去掉所以：已得最优解，且人工变量为非基变量，则可去掉所以：已得最优解，且人工变量为非基变量，则可去掉所以：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。人工变量，得原问题的一个即可行基。人工变量，得原问题的一个即可行基。人工变量，得原问题的一个即可行基。第70页，讲稿共115张，创作于星期三71（第二阶段）单纯形表（第二阶段）单纯形表2 2cj-30100CB
34、XBbix1x2x3x4x50 x400001-1/20 x23011/300-3x11102/301/2j00303/2 -93/2 0 x40 x21x35/2-1/2100-1/400001-1/23/23/20103/4x3入，入，x1出出j-9/2000-3/4所以：所以：X*=(x2,x,x3,x4)T T=(5/2,3/2,0)T Z*=3/2第71页，讲稿共115张，创作于星期三72单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例1.10 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在单系数
35、矩阵中不存在单位矩阵，无法建立初位矩阵，无法建立初始单纯形表。始单纯形表。第72页，讲稿共115张，创作于星期三73单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍绍的的单单纯纯形形法法求解该模型，计算结果见下表。求解该模型，计算结果见下表。第73页，讲稿共115张，创作于星期三
36、74单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M-Mx63-650-1013/50 x58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/500 x531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3第74页，讲稿共115张，创作于
37、星期三75单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例1.11 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在单系数矩阵中不存在单位矩阵，无法建立初位矩阵，无法建立初始单纯形表。始单纯形表。第75页，讲稿共115张，创作于星期三76单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理
38、解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍绍的的单单纯纯形形法法求求解解该该模模型，计算结果见下表。型，计算结果见下表。第76页，讲稿共115张，创作于星期三77单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z-4M3-6M-1+M-1+3M0-M000 x4103-20100-1-Mx610100-11-21-1x31-2010001Z-M-11-1+M00-M0-3M+1
39、第77页，讲稿共115张，创作于星期三78单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-1x31-2010001Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+2/3第78页，讲稿共115张，创作于星期三79单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法 用计算机处理数据时，只能用很大的数代替用计算机处理
40、数据时，只能用很大的数代替M,可能造成计算机可能造成计算机上的错误，故多采用上的错误，故多采用两阶段法两阶段法。第一阶段：第一阶段：在原线性规划问题中加入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型：对上述模型求解（单纯形法），若对上述模型求解（单纯形法），若=0,说明问题存在基可行解，说明问题存在基可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。可以进行第二个阶段；否则，原问题无可行解，停止运算。第79页，讲稿共115张，创作于星期三80单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法第一阶段的线性规划问题可写为：第一阶段的线性规划问题可写为：第一
41、阶段单纯形法迭代的过程见下表第一阶段单纯形法迭代的过程见下表（注意：没有化为极大化问题）（注意：没有化为极大化问题）第80页，讲稿共115张，创作于星期三81单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-2010001146-1-301000 x4103-20100-11x610100-11-210 x31-201000110-1001030 x4123001-22-50 x210100-11-20 x31-201000000000011第81页，
42、讲稿共115张，创作于星期三82单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法 第二阶段：第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。（用单纯形法计算）。例：例：第82页，讲稿共115张，创作于星期三83单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法cj3-1-100cBxBbx1x2x3x4x50 x4123001-24-1x210100-1-1x31-20100Z-21000-13x
43、141001/3-2/3-1x210100-1-1x390012/3-4/3Z2000-1/3-1/3第二阶段：第二阶段：最优解为（最优解为（4 1 9 0 0），目标函数），目标函数 Z=2第83页，讲稿共115张，创作于星期三84单纯形法的进一步讨论单纯形法的进一步讨论 通过大法或两阶段法求初始的基本可行解。但是如果通过大法或两阶段法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有人工变量，或者在大法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。该
44、线性规划就不存在可行解。无可行解无可行解 第84页，讲稿共115张，创作于星期三85C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0-M-M x4x7x8 643 1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 6/1-3/1 Z-7M-6-4M-15-M -3+M -2+M -1-2M 0 -M -M 0 0 0-M-2 x4x7x2 343 1 0 2 1 0 1 0 -11 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 3/14/1-Z Z -3+M 0
45、 -3-M 0 -M -2 0 2-M-3-M-2 x1x7x2 313 1 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 例例单纯形法的进一步讨论单纯形法的进一步讨论运算到检验数全负为止，仍含有人工变量，无可行解。运算到检验数全负为止，仍含有人工变量，无可行解。第85页，讲稿共115张，创作于星期三86单纯形法的进一步讨论单纯形法的进一步讨论 无最优解与无可行解时两个不同的概念。无最优解与无可行解时两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指无可行解是指原规划不存
46、在可行解，从几何的角度解释是指 线性规划问题的可行域为空集；线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目无最优解则是指线性规划问题存在可行解，但是可行解的目 标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。者无穷小）。无最优解也称为有限最优解，或无界解。判别方法：无最优解判别定理判别方法：无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在某个大于零的检验数，但是该检验
47、数所对应的非基变量行存在某个大于零的检验数，但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零，则该线性规划问题的系数列向量的全部系数都为负数或零，则该线性规划问题 无最优解无最优解 无最优解无最优解第86页，讲稿共115张，创作于星期三87C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z02200因因 但但 所以原问题无最优解所以原问题无最优解单纯形法的进一步讨论单纯形法的进一步讨论第87页，讲稿共115张，创作于星期三88 退化退化 即计算出的即计算出的（用于确定换出变量）存在有两个以上相同的最小比值，会（用于确定换出变量
48、）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是造成下一次迭代中由一个或几个基变量等于零，这就是退化退化（会产生退化（会产生退化解）。解）。为避免出现计算的循环，勃兰特为避免出现计算的循环，勃兰特(Bland)提出一个简便有效的规则（摄动提出一个简便有效的规则（摄动法原理）：法原理）：当存在多个当存在多个 时，选下标最小的非基变量为换入变量；时，选下标最小的非基变量为换入变量；(2)当当值出现两个以上相同的最小值时，选下标最小的基变量为换出变值出现两个以上相同的最小值时，选下标最小的基变量为换出变量。量。单纯形法的进一步讨论单纯形法的进一步讨论第88页，讲稿共
49、115张，创作于星期三89000-242-8030Z-5-60-420-805Z10001001x3 212060-2411x1 3321300-803x5 00-30-425-800Z1100 1001x7 00106-1-2410 x1 30-1130-3-800 x5 0-11001001x7 000106-1-2410 x6 0000136-4-3210 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C 第第一一次次迭迭代代中中使使用用了了摄摄动动法法原原理理，选选择择下下标标为为6的的基基变变量量x6离离基。基。可得最优解可得最优解maxZ
50、=，单纯形法的进一步讨论单纯形法的进一步讨论第89页，讲稿共115张，创作于星期三90 无穷多最优解无穷多最优解 若若线线性性规规划划问问题题某某个个基基本本可可行行解解所所有有的的非非基基变变量量检检验验数数都都小小于于等等于于零零，但但其其中中存存在在一一个个检检验验数数等等于于零零，那那么么该该线线性性规规划划问题有无穷多最优解。问题有无穷多最优解。例：最优表：例：最优表：非基变量检验非基变量检验数数，所以有无穷多所以有无穷多最优解。最优解。C 1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -10 1 0 1 01 0 0 -2 12/