第一章线性规划及单纯形法课件

案例：确定潘得罗索工业公司的产品组合案例：确定潘得罗索工业公司的产品组合 潘得罗索工业公司是一家墨西哥公司，截至在潘得罗索工业公司是一家墨西哥公司，截至在20192019年的销售，年的销售，公司公司生产了全国胶合板产量的四分之一生产了全国胶合板产量的四分之一，与其他胶合板生产厂商一样，与其他胶合板生产厂商一样，潘得罗索工业公司的许多产品根据厚度和所用木材的质量而有所不同。潘得罗索工业公司的许多产品根据厚度和所用木材的质量而有所不同。因为产品在一个竞争的环境中进行销售，产品的价格由市场决定，所因为产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以以产品的价格每月都有很大的变化产品的价格每月都有很大的变化。结果导致。结果导致每项产品对公司整体利每项产品对公司整体利润的贡献也有很大的变动润的贡献也有很大的变动。从从19801980年开始，潘得罗索工业公司管理部门年开始，潘得罗索工业公司管理部门每个月使用线性每个月使用线性规划指导下个月的产品组合决策规划指导下个月的产品组合决策。线性规划的数学模型考虑了这一决。线性规划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的可得数量。然后策的所有相关限制条件，包括生产产品所需的有限的可得数量。然后对模型求解，对模型求解，找出可行并且最大可能利润（找出可行并且最大可能利润（largest possible largest possible profitprofit）的产品组合）的产品组合。采用线性规划后，潘得罗索工业公司的成绩是显著的。改进采用线性规划后，潘得罗索工业公司的成绩是显著的。改进的产品组合使公司的的产品组合使公司的总利润增加了总利润增加了20%20%，线性规划的其他贡献包括，线性规划的其他贡献包括更更好的原材料利用，更好的资本投资，和更好的人员利用好的原材料利用，更好的资本投资，和更好的人员利用。7/13/202411 一般线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标。（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）。7/13/202421一般线性规划问题的数学模型例1 如图所示，用一块边长为a的正方形铁皮做一个容器，如何截取x使铁皮围成的容器容积最大？x xa a7/13/202431一般线性规划问题的数学模型例例2 常山机器厂生产常山机器厂生产I、两种产品。这两种产品都两种产品。这两种产品都要分别在要分别在A、B、C三种不同设备上加工。按工艺资料三种不同设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时和利规定，单件产品在不同设备上加工所需要的台时和利润如下表所示，企业决策者应如何安排生产计划，使润如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？设 备产 品 A B C利润（元）I I 2 4 0 2 2 0 5 3 有 效 台 时 12 16 157/13/202441一般线性规划问题的数学模型 解：设x1、x2分别为I I、两种产品的产量，则数学模型为：max Z=2xmax Z=2x1 1+3x+3x2 2 x x1 1 0,x 0,x2 2 0 0s.t.s.t.2x 2x1 1+2x+2x2 2 12 12 4x 4x1 1 16 16 5x 5x2 2 15 157/13/202451一般线性规划问题的数学模型2.2.2.2.线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量 Decision variables Decision variables 目标函数目标函数目标函数目标函数 Objective function Objective function约束条件约束条件约束条件约束条件 Constraints Constraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性线性线性函数，通常是求最函数，通常是求最函数，通常是求最函数，通常是求最大值或最小值；大值或最小值；大值或最小值；大值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不等式或等式；不等式或等式；不等式或等式；不等式或等式；（3 3 3 3）决策变量为可控的连续变量。）决策变量为可控的连续变量。）决策变量为可控的连续变量。）决策变量为可控的连续变量。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？(Linear (Linear (Linear (Linear Programming LP)Programming LP)Programming LP)Programming LP)7/13/202461一般线性规划问题的数学模型目标函数：目标函数：目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：7/13/202471一般线性规划问题的数学模型向量形式：向量形式：向量形式：向量形式：其中：其中：7/13/202481一般线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：7/13/202491一般线性规划问题的数学模型3.线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1)目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2)约束条件都为等式方程约束条件都为等式方程(3)右端常数项右端常数项bi都大于或等于零都大于或等于零(4)决策变量决策变量xj为非负。为非负。7/13/2024101一般线性规划问题的数学模型 如何化标准形式？如何化标准形式？如何化标准形式？如何化标准形式？目标函数的转目标函数的转换换 如果是求极小值即如果是求极小值即 ，则可，则可将目标函数乘以将目标函数乘以(-1)(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：变量的变变量的变换换7/13/2024111一般线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令 ，显然，显然7/13/2024121一般线性规划问题的数学模型例例3 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式用用 替换替换 ，且，且 解解:（）因为（）因为x3无符号要求无符号要求，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以 （2）因为）因为x10，标准型中要求变量非负，所以，标准型中要求变量非负，所以7/13/2024131一般线性规划问题的数学模型(3)第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(4)第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变量左端减去剩余变量x5，x50；(5)第第3个约束方程右端常数项为个约束方程右端常数项为-6，方程两边同乘以，方程两边同乘以(-1),将右将右端常数项化为正数；端常数项化为正数；(6)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;7/13/2024141一般线性规划问题的数学模型标准形式如下：标准形式如下：7/13/2024151一般线性规划问题的数学模型4.线性规划问题的解线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组的方程组中找出一个解，使目标函数中找出一个解，使目标函数(1)达到最大值。达到最大值。7/13/2024161一般线性规划问题的数学模型 可行解可行解：满足：满足约束条件约束条件、的解为可行解。所有可行解的解为可行解。所有可行解的集合为的集合为可行域可行域。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基：基：设设A为为约束条件约束条件的的mn阶系数矩阵阶系数矩阵(m0换换出出行行将将5化为化为1,乘以乘以1/5 x2x3x4300 3 3 0 1 0 0 0 1 0 0 1/5 1/5 6 2 0 1 0-2/5164 0 0 10 2 0 0 0 -3/534 x12x40 x23 3 3 1 0 1/2 0 1 0 1/2 0-1/5-1/5 4 0 0 -2 1 4/5 3 0 1 0 0 1/5 0 0 -1 0 -3/57/13/2024394 单纯形法的计算步骤用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。7/13/2024404 单纯形法的计算步骤cj12100icB基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x220 x x2 22 2 1/3150120753017131/30 -90-22560 x x1 111017/31/31250128/9-1/92/335/300-98/9-1/9-7/37/13/2024414 单纯形法的计算步骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤 作业：（作业：（P47）1.37/13/2024425 单纯形法的进一步讨论人工变量法人工变量法：人工变量法：前面讨论了在标准型中系数矩阵前面讨论了在标准型中系数矩阵有单位矩阵有单位矩阵，很容，很容易确定一组基可行解。在实际问题中有些模型并不含有单易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种件的等式左端加一组虚拟变量，得到一组基变量。这种人人为加的变量为加的变量称为称为人工变量人工变量，构成的可行基称为，构成的可行基称为人工基人工基，用，用大大M M法或两阶段法求解，这种用人工变量作桥梁的求解方法法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。称为人工变量法。7/13/2024435 单纯形法的进一步讨论人工变量法例例6 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。7/13/2024445 单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。7/13/202445cj-30100-M-MCBXBbx1x2x3x4x5x6x7i0 x4411110004-Mx61-21-10-1101-Mx7903100013-3-2M4M 10-M000 x4330211-1010 x21-21-10-110-Mx7660403-3116M-3 04M+103M-4M00 x400001-1/21/2-1/20 x23011/30001/39-3x11102/301/2-1/21/63/200303/2-M-3/21/2-M0 x400001-1/21/2-1/20 x21-2100-1101x33/23/20103/4-3/41/4-9/2000-3/43/4-M-1/4-M7/13/2024465 单纯形法的进一步讨论解的判别解的判别解的判别（MaxMax型）型）：1）唯一最优解唯一最优解判别：最优表中所有非基变量的检验数非零判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。则线性规划具有唯一最优解。2）无穷多最优解无穷多最优解判别：最优表中存在非基变量的检验数为判别：最优表中存在非基变量的检验数为零零,则线则性规划具有多重最优解（或则线则性规划具有多重最优解（或多重最优解多重最优解）。）。3）无界解无界解判别：某个判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无无可可行行解解的的判判断断：当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且存在人工变量在基，且不为且存在人工变量在基，且不为0时，表明原问题无可行解。时，表明原问题无可行解。5）退化解退化解的判别：存在某个基变量为零的基本可行解。的判别：存在某个基变量为零的基本可行解。7/13/202447检验数反号，即-令负检验数中最小的对应的变量进基；-当检验数均大于等于零时为最优。或者转换为Max型，再求解Min型单纯形表与Max型的区别仅在于：解的判别解的判别（Min型）：5 单纯形法的进一步讨论解的判别7/13/2024485 单纯形法的进一步讨论学习要点：学习要点：1.掌握人工变量法掌握人工变量法大大M法法2.能准确根据单纯形表中的检验数判别所解问能准确根据单纯形表中的检验数判别所解问题的解的类型题的解的类型 作业：作业：(P48)1.6（列初始单纯形表）（列初始单纯形表），1.7（a）(大大M法法)7/13/2024495 单纯形法的进一步讨论单纯形法计算的向量矩阵描述非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0 基变量非基变量XBXNXsCBXBB-1 bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1矩阵形式表述的线性规划标准型：矩阵形式表述的线性规划标准型：单纯性表迭代过程：单纯性表迭代过程：左乘左乘B-17/13/2024505 单纯形法的进一步讨论单纯形法计算的向量矩阵描述cj23000cB基bx1x2x3x4x50 x312221000 x416400100 x5150500123000例例10 用单纯形法求例用单纯形法求例5线性规划问题的初始单纯形表和线性规划问题的初始单纯形表和最终单纯形表如下所示：最终单纯形表如下所示：cj23000cB基bx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/500-10-1/57/13/2024515 单纯形法的进一步讨论单纯形法计算的向量矩阵描述则则7/13/2024525 单纯形法的进一步讨论学习要点：学习要点：1.能根据初始和最终单纯形表找出能根据初始和最终单纯形表找出B-1，会利用，会利用公式计算检验数。公式计算检验数。作业：作业：1.8，1.127/13/2024537 应用举例1.1.混合配料问题混合配料问题例例13 某糖果厂用原料某糖果厂用原料A、B、C加工成不同牌号加工成不同牌号的糖果甲、乙、丙。有关参数如下表所示，问该厂的糖果甲、乙、丙。有关参数如下表所示，问该厂每月生产这三种各多少千克，使该厂获利最大。每月生产这三种各多少千克，使该厂获利最大。试建立该问题的线性规划模型。试建立该问题的线性规划模型。甲甲乙乙丙丙原料成本原料成本（元（元/kg）每月限制用每月限制用量（量（kg）A60%30%22000B1.52500C 20%50%60%11200加工费加工费（元（元/kg）0.50.40.3售价（售价（元元/kg）3.42.852.25其中，百分数表示各糖果中各原料的含量其中，百分数表示各糖果中各原料的含量7/13/2024547 应用举例解：设解：设 x xij ij 表示生产第表示生产第j j 种糖果使用的第种糖果使用的第 i i种原料的质量，种原料的质量，则则Max Z=（3.4-0.5）(x11+x21+x31)+（2.85-0.4）(x12+x22+x32)+（2.25-0.3）（）（x13+x23+x33）-2（x11+x12+x13）-1.5(x21+x22+x23)-1(x31+x32+x33)s.t.x11+x12+x13 2000 x21+x22+x23 2500 x31+x32+x331200 x110.6（x11+x21+x31）x31 0.2（x11+x21+x31）x120.3（x12+x22+x32）x32 0.5（x12+x22+x32）x33 0.6（x13+x23+x33）xij0 （i=1，2，3；j=1，2，3）每月限制用量每月限制用量各糖果中各原料的含量各糖果中各原料的含量7/13/2024557 应用举例 例例14 14 兴安公司有一笔兴安公司有一笔3030万元的资金，考虑今后三年内用于下列四个万元的资金，考虑今后三年内用于下列四个项目的投资：（假定项目的投资：（假定3030万元在第一年初投资完）万元在第一年初投资完）甲：三年的每年年初投资，每年获利为投资额的甲：三年的每年年初投资，每年获利为投资额的20%20%，其本利可，其本利可用于下一年投资。用于下一年投资。乙：第一年初投入，第二年末收回，本利合计为投资额的乙：第一年初投入，第二年末收回，本利合计为投资额的150%150%。，。，但投资限额不超过但投资限额不超过1515万元。万元。丙：第二年初投入，第三年末收回，本利合计为投资额的丙：第二年初投入，第三年末收回，本利合计为投资额的160%160%。，。，但投资限额不超过但投资限额不超过2020万元。万元。丁：第三年初投入，年末收回，可获利丁：第三年初投入，年末收回，可获利40%40%，但限额为，但限额为1010万元。万元。试为该公司确定一个使三年末本利和为最大的投资组合方案。试为该公司确定一个使三年末本利和为最大的投资组合方案。2.2.投资项目的组合问题投资项目的组合问题7/13/202456设设 x xijij第第 i i 年投资于第年投资于第 j j 项目上的资金量，则项目上的资金量，则Max Z=1.2 x31+1.6 x2 3+1.4 x34s.t.x11+x12=300,000 x21+x23=1.2 x11 x31+x34=1.2x21+1.5x12 x12 150,000 x23 200,000 x34 100,000 xij 0,(i=1,2,3;j=1,2,3,4)x11x12x21x23x31x34123430,0007 应用举例第第 i 年初投资额年初投资额各项目投资限额各项目投资限额7/13/2024577 应用举例学习要点：学习要点：1.能准确地将所论的实际问题用相应的线性规能准确地将所论的实际问题用相应的线性规划的数学模型表示出来划的数学模型表示出来 作业：作业：(P49)1.13，1.147/13/202458