数学建模--线性规划幻灯片.ppt

《数学建模--线性规划幻灯片.ppt》由会员分享，可在线阅读，更多相关《数学建模--线性规划幻灯片.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模-线性规划第1页，共70页，编辑于2022年，星期六 线性规划问题的提出线性规划问题的提出 线性规划的基本概念线性规划的基本概念 线性规划的数学模型线性规划的数学模型继续继续继续继续返回返回返回返回一一 线性规划问题及其数学模型线性规划问题及其数学模型第2页，共70页，编辑于2022年，星期六问题的提出问题的提出例:生产计划问题第3页，共70页，编辑于2022年，星期六产品产品I产品产品2如何安排生产如何安排生产使利润最大使利润最大？第4页，共70页，编辑于2022年，星期六决策变量（决策变量（Decision variables）目标函数（目标函数（目标函数（目标函数（Objecti

2、ve functionObjective function）约束条件（约束条件（Constraint conditionsConstraint conditions）可行域（可行域（可行域（可行域（Feasible region)Feasible region)最优解（最优解（最优解（最优解（Optimal solution)Optimal solution)基本概念基本概念问题中要确定的未知量，表明规划问题中要确定的未知量，表明规划问题中要确定的未知量，表明规划问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可中的用数量表示的方案、措施，可中的用数量表示的方案、措施，可中的用数量表

3、示的方案、措施，可由决策者决定和控制。由决策者决定和控制。由决策者决定和控制。由决策者决定和控制。它是决策变量的函数它是决策变量的函数它是决策变量的函数它是决策变量的函数指决策变量取值时受到的各种指决策变量取值时受到的各种指决策变量取值时受到的各种指决策变量取值时受到的各种资源条件的限制，通常表达为资源条件的限制，通常表达为资源条件的限制，通常表达为资源条件的限制，通常表达为含决策变量的等式或不等式。含决策变量的等式或不等式。含决策变量的等式或不等式。含决策变量的等式或不等式。满足约束条件的决策满足约束条件的决策满足约束条件的决策满足约束条件的决策变量的取值范围变量的取值范围变量的取值范围变量

4、的取值范围可行域中使目标函可行域中使目标函可行域中使目标函可行域中使目标函数达到最优的决策数达到最优的决策数达到最优的决策数达到最优的决策变量的值变量的值变量的值变量的值第5页，共70页，编辑于2022年，星期六是问题中要确定的未知量，表明是问题中要确定的未知量，表明是问题中要确定的未知量，表明是问题中要确定的未知量，表明规划中的用数量表示的方案、措规划中的用数量表示的方案、措规划中的用数量表示的方案、措规划中的用数量表示的方案、措施，可由决策者决定和控制。施，可由决策者决定和控制。施，可由决策者决定和控制。施，可由决策者决定和控制。第第1步步-确定决策变量确定决策变量设设 I的产量的产量 I

5、I的产量的产量 利润利润第6页，共70页，编辑于2022年，星期六第第2步步-定义目标函数定义目标函数Max Z=x1+x2决策变量决策变量第7页，共70页，编辑于2022年，星期六 Max Z=2 x1+3 x2系数系数第第2步步-定义目标函数定义目标函数第8页，共70页，编辑于2022年，星期六对我们有对我们有何限制何限制?第9页，共70页，编辑于2022年，星期六第第3步步-表示约束条件表示约束条件 x1+2 x2 8 4 x1 16 4 x2 12 x1、x2 0 0第10页，共70页，编辑于2022年，星期六该计划的数学模型该计划的数学模型 目标函数目标函数 Max Z=2x1+3x

6、2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0 x1 x2第11页，共70页，编辑于2022年，星期六线性规划问题的共同特征线性规划问题的共同特征一组决策变量一组决策变量X X表示一个方案表示一个方案,一般一般X X大于大于等于零。等于零。约束条件是线性等式或不等式。约束条件是线性等式或不等式。目标函数是线性的。目标函数是线性的。求目标函数最大化求目标函数最大化或最小化或最小化第12页，共70页，编辑于2022年，星期六 线性规划模型的一般形式线性规划模型的一般形式 第13页，共70页，编辑于2022年，星期六线性规划模型建立步骤 从实际问题中建立数学模

7、型一般有以下三个步骤；从实际问题中建立数学模型一般有以下三个步骤；1.根据影响所要达到目的的因素找到决策变量；根据影响所要达到目的的因素找到决策变量；2.由决策变量和所在达到目的之间的由决策变量和所在达到目的之间的函数函数关系确定目标函数；关系确定目标函数；3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。由决策变量所受的限制条件确定决策变量所要满足的约束条件。第14页，共70页，编辑于2022年，星期六1.1.线性规划的标准形式：线性规划的标准形式：用单纯法求解时，常将标准形式化为：2.线性规划的基本算法线性规划的基本算法单纯形法单纯形法二二.线性规划的基本算法线性规划的基本算法单

8、纯形法单纯形法第15页，共70页，编辑于2022年，星期六引入松弛变量x3,x4,x5,将不等式化为等式,即单纯形标准形:显然A的秩ran(A)=3,任取3个线性无关的列向量,如P3P4P5称为一组基基,记为B.其余列向量称为非基非基,记为N.第16页，共70页，编辑于2022年，星期六于是f=cBxB+cNxN,Ax=BxB+NxN=b,则xB=B-1b-B-1NxN,f=cBB-1b+(cNcBB-1N)xN 若可行基进一步满足:cNcBB-1N0,即:cBB-1N-cN0则对一切可行解x,必有f(x)cBB-1b,此时称基可行解x=(B-1b,0)T为最优解最优解.3.最优解的存在性定理

9、最优解的存在性定理将A的列向量重排次序成A=(B,N),相应x=(xB,xN)T,c=(cB,cN)基对应的变量xB称为基变量基变量,非基对应的变量xN称为非基变量非基变量.定理定理 如果线性规划(1)有最优解，那么一定存在一个基可行解 是最优解.第17页，共70页，编辑于2022年，星期六4.4.基可行解是最优解的判定准则基可行解是最优解的判定准则检验数检验数因为Ax=BxB+NxN=b,得xB=B-1b-B-1NxN,而f=cBxB+cNxN,故f=cBB-1b+(cNcBB-1N)xN第18页，共70页，编辑于2022年，星期六5.5.基可行解的改进基可行解的改进第19页，共70页，编辑

10、于2022年，星期六改进方法：改进方法：返回第20页，共70页，编辑于2022年，星期六练习建立练习建立LPLP数学模型数学模型一、有两个煤厂一、有两个煤厂A A、B B，每月分别供应三个居民，每月分别供应三个居民区区X X、Y Y、Z Z。求运费最少的方案。求运费最少的方案。供需平衡供需平衡第21页，共70页，编辑于2022年，星期六1、LINGO使用简介 LINGO软件是美国的LINDO系统公司（Lindo System Inc）开发的一套用于求解最优化问题的软件包.LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解.LINGO软件的

11、最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快.LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果，这里简单介绍LINGO的使用方法.LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等.一个LINGO程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分，每一部分有其独特的作用和语法规则，读者可以通过查阅相关的参考书或者LINGO的HELP文件详细了解，这里就不展开介绍了.三.线性规划软件求解第22页，共70页，编辑于2022年，星期六LIN

12、GO的主要功能特色为：既能求解线性规划问题，也有较强的求解非线性规划问题的能力；输入模型简练直观；运算速度快、计算能力强；内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式描述大规模的优化模型；将集合的概念引入编程语言，很容易将实际问题转换为LINGO模型；并且能方便地与Excel、数据库等其他软件交换数据.第23页，共70页，编辑于2022年，星期六第一步：启动第一步：启动Lingo屏幕显示如下：屏幕显示如下：标记标记LINGO的外窗口是主框架窗口，的外窗口是主框架窗口，主框架窗口的上面包含所有的命令菜单主框架窗口的上面包含所有的命令菜单和命令工具栏；和命令工具栏；标记标记LI

13、NGO MODEL-LINGO1的子窗的子窗口是一个新的、空白的模型窗口。口是一个新的、空白的模型窗口。第24页，共70页，编辑于2022年，星期六第二步：在模型窗口中输入模型第二步：在模型窗口中输入模型model:max=2*x1+3*x2;4*x1+3*x210;3*x1+5*x212;endMax 2x1+3x2 St.4x1+3x2=10 3x1+5x2=12 x10 x20第25页，共70页，编辑于2022年，星期六第三步：求解模型第三步：求解模型 1)选择菜单选择菜单 LINGO|Solve 或者按工具栏的或者按工具栏的 第26页，共70页，编辑于2022年，星期六 2)LINGO

14、开始编译模型，如有语法错误将返回开始编译模型，如有语法错误将返回一个错误的消息并指明错误出现的位置；如果一个错误的消息并指明错误出现的位置；如果通过编译通过编译,LINGO将激活将激活 Solver运算器运算器 寻求模寻求模型的最优解；型的最优解；3)3)首先出现首先出现solver status solver status 窗口窗口，其作，其作用是监控用是监控solversolver的进展和显示模型的的进展和显示模型的维数等信息；维数等信息；第27页，共70页，编辑于2022年，星期六第28页，共70页，编辑于2022年，星期六4)计算完成后出现计算完成后出现Solution Report窗

15、口显示模型解的详细信息；窗口显示模型解的详细信息；第29页，共70页，编辑于2022年，星期六Solution Report 窗口窗口Global optimal solution found at iteration:2Objective value:7.454545Variable Value Reduced Cost x1 1.272727 0.000000 x2 1.636364 0.000000Row Slack or Surplus Dual Price 1 7.454545 1.000000 2 0.000000 0.9090909E-01 3 0.000000 0.545454

16、5（对目标函数而言对目标函数而言）第30页，共70页，编辑于2022年，星期六LINGO的语法规定、运算符及函数：的语法规定、运算符及函数：（1）求目标函数的最大值或最小值分别用）求目标函数的最大值或最小值分别用MAX=或或MIN=来表示；来表示；（2）每个语句必须以分号）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨结束，每行可以有许多语句，语句可以跨行；行；（3）变量名称必须以字母（）变量名称必须以字母（AZ）开头，由字母、数字（）开头，由字母、数字（09）和下划线所组）和下划线所组成，长度不超过成，长度不超过32个字符，不区分大小写；个字符，不区分大小写；（4）可以给语句加

17、上标号，例如）可以给语句加上标号，例如OBJ MAX=200*X1+300*X2；（5）以惊叹号）以惊叹号“！”开头，以分号开头，以分号“；”结束的语句是注释语句；结束的语句是注释语句；（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；负；（7）LINGO模型以语句模型以语句“MODEL：”开头，以开头，以“END”结束，对于比较简结束，对于比较简单的模型，这两个语句可以省略单的模型，这两个语句可以省略.(8)可以用可以用表示表示表示表示=；Lingo无严格小于，欲使无严格小于，欲使ab，可以适当选取小的正常数可以适

18、当选取小的正常数e 表示表示成成a+eb，第31页，共70页，编辑于2022年，星期六(9)LINGO(9)LINGO(9)LINGO(9)LINGO编辑器用编辑器用编辑器用编辑器用 蓝色蓝色蓝色蓝色显示显示显示显示LINGOLINGOLINGOLINGO关键字关键字关键字关键字;绿色绿色绿色绿色显示显示显示显示注释注释注释注释 ;其他文本用黑色其他文本用黑色其他文本用黑色其他文本用黑色 匹配的括号匹配的括号匹配的括号匹配的括号用用用用红色红色红色红色高亮度显示高亮度显示高亮度显示高亮度显示(10)(10)(10)(10)标准运算符标准运算符标准运算符标准运算符算术运算符：算术运算符：算术运算

19、符：算术运算符：*/+-*/+-*/+-*/+-逻辑运算符：逻辑运算符：逻辑运算符：逻辑运算符：#EQ#NE#(#EQ#NE#(#EQ#NE#(#EQ#NE#(相等，不等）相等，不等）相等，不等）相等，不等）为真为真为真为真#GE#GT#GE#GT#GE#GT#GE#GT#（左边大于或等于，左边大于）（左边大于或等于，左边大于）（左边大于或等于，左边大于）（左边大于或等于，左边大于）为真为真为真为真#LE#LT#LE#LT#LE#LT#LE#LT#（左边小于或等于，左边小于）（左边小于或等于，左边小于）（左边小于或等于，左边小于）（左边小于或等于，左边小于）为真为真为真为真#NOT#AND#O

20、R#NOT#AND#OR#NOT#AND#OR#NOT#AND#OR#（取反，取交（积），取并（和）取反，取交（积），取并（和）取反，取交（积），取并（和）取反，取交（积），取并（和）)第32页，共70页，编辑于2022年，星期六(11).(11).(11).(11).变量界定函数变量界定函数变量界定函数变量界定函数lingolingolingolingo变量默认域为非负实数变量默认域为非负实数变量默认域为非负实数变量默认域为非负实数free(variable)free(variable)free(variable)free(variable)取消默认域，使变量可以取任意实数取消默认域，使变量

21、可以取任意实数取消默认域，使变量可以取任意实数取消默认域，使变量可以取任意实数gin(variable)gin(variable)gin(variable)gin(variable)限制变量取整数值限制变量取整数值限制变量取整数值限制变量取整数值bin(variable)bin(variable)bin(variable)bin(variable)限制变量取值为限制变量取值为限制变量取值为限制变量取值为0 0 0 0，1 1 1 1bnd(low,variable,up)bnd(low,variable,up)bnd(low,variable,up)bnd(low,variable,up)限制

22、变量于一个有限的范围限制变量于一个有限的范围限制变量于一个有限的范围限制变量于一个有限的范围第33页，共70页，编辑于2022年，星期六例题例题1：某工厂在计划期内要安排生产某工厂在计划期内要安排生产A、B两种产品，已知生产单位两种产品，已知生产单位产品所需设备台时及对甲、乙两种原材料的消耗，有关数据如表产品所需设备台时及对甲、乙两种原材料的消耗，有关数据如表1.1.问：问：应如何安排生产计划，使工厂获利最大？应如何安排生产计划，使工厂获利最大？产品 资源AB可利用资源设备128台时甲4016公斤乙0412公斤单位利润2元3元建立线性规划问题的数学模型，用建立线性规划问题的数学模型，用LING

23、O求出最优解并做相求出最优解并做相应的分析应的分析.第34页，共70页，编辑于2022年，星期六问题问题1.1设计划生产设计划生产A,B两种产品分别为两种产品分别为x1,x2，则建立线性规划问题，则建立线性规划问题数学模型数学模型模型：max S=2x1+3x2在在LINGO的的MODEL窗口内输入如下模型：窗口内输入如下模型：model:max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=”的不等式，左边减右边的差值为的不等式，左边减右边的差值为Surplus（剩余），当约束条（剩余），当约束条件两边相等时，松弛或剩余的值等于零件两边相等时，松弛或剩余的值等于零.“Du

24、al Price”的意思是对偶价格（或称的意思是对偶价格（或称为影子价格），上述报告中为影子价格），上述报告中Row2的松弛值为的松弛值为0，表明生产甲产品，表明生产甲产品4单位、乙产单位、乙产品品2单位，所需设备单位，所需设备8台时已经饱和，对偶价格台时已经饱和，对偶价格1.5的含义是：如果设备增加的含义是：如果设备增加1台台时，能使目标函数值增加时，能使目标函数值增加1.5.报告中报告中Row4的松弛值为的松弛值为4，表明生产甲产品，表明生产甲产品4单位、单位、乙产品乙产品2单位，所需原材料乙单位，所需原材料乙8公斤还剩余公斤还剩余4公斤，因此增加原材料乙不会使目公斤，因此增加原材料乙不会

25、使目标函数值增加，所以对偶价格为标函数值增加，所以对偶价格为0.第38页，共70页，编辑于2022年，星期六用用MATLAB优化工具箱解线性规划优化工具箱解线性规划minz=cX 1、模型：命令：x=linprog（c，A，b）2、模型：minz=cX 命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=，b=.第39页，共70页，编辑于2022年，星期六3、模型：minz=cX VLBXVUB命令：1x=linprog（c，A，b，Aeq,beq,VLB，VUB）2 x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：1若没有等式约

26、束:,则令Aeq=,beq=.2其中X0表示初始点4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.第40页，共70页，编辑于2022年，星期六解解 编写编写M文件文件xxgh1.m如下：如下：c=-0.4-0.28-0.32-0.72-0.64-0.6;A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08;b=850;700;100;900;Aeq=;beq=;vlb=0;0;0;0;0;0;vub=;x,fval=linprog(c,A,b,Ae

27、q,beq,vlb,vub)ToMatlab(xxgh1)第41页，共70页，编辑于2022年，星期六 投资的收益和风险投资的收益和风险 四四四四.线性规划应用举例线性规划应用举例线性规划应用举例线性规划应用举例第42页，共70页，编辑于2022年，星期六(二二)、基本假设和符号规定、基本假设和符号规定第43页，共70页，编辑于2022年，星期六(三三)、模型的建立与分析、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即maxqixi|i=1，2,n4.模型简化：第44页，共70页，编辑于2022年，星期六第45页，共70页，编辑于2022年，星期六(四四)、模型、模型1

28、1的求解的求解 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：第46页，共70页，编辑于2022年，星期六a=0;while(1.1-a)1c=-0.05-0.27-0.19-0.185-0.185;Aeq=11.011.021.0451.065;beq=1;A=00.025000;000.01500;0000.0550;00000.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);ax=xQ=-valpl

29、ot(a,Q,.)，axis(00.100.5)，holdona=a+0.001;endxlabel(a),ylabel(Q)ToMatlab（xxgh5）第47页，共70页，编辑于2022年，星期六计算结果：计算结果：第48页，共70页，编辑于2022年，星期六(五五)、结果分析结果分析返回4 4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和 收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度收益x0 x1x2x3x4 0

30、.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2 2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。第49页，共70页，编辑于2022年，星期六实验作业实验作业某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人15

31、0名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.返回第50页，共70页，编辑于2022年，星期六 图解法图解法 线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果 由图解法得到的启示由图解法得到的启示2 线性规划的图解法线性规划的图解法继续继续继续继续返回返回返回返回第51页，共70页，编辑于2022年，星期六例例1的数学模型的数学模型 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2

32、x2 8 4x1 16 4x2 12 x1、x2 0 0 x1 x2第52页，共70页，编辑于2022年，星期六9 8 7 6 5 4 3 2 1 0|123456789x1x2x1+2x2=8(0,4)(8,0)目标函数目标函数目标函数目标函数 Max Max Z=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x2 8 4x x1 1 16 16 4 4x x2 2 12 x x1 1、x x2 0 0 0 04x1=164 x2=12图解法图解法第53页，共70页，编辑于2022年，星期六9 8 7 6 5 4 3 2 1 0 x2 目标函数目标

33、函数目标函数目标函数 Max Z=2=2x1 1+3+3x x2 约束条件约束条件 x x1 1+2x x2 2 8 8 4 4x1 1 16 16 4x x2 12 12 x x1 1、x x2 2 0 0 0 0|123456789x1x1+2x2=84x1=164 x2=12可行域可行域图解法图解法第54页，共70页，编辑于2022年，星期六9 8 7 6 5 4 3 2 1 0|123456789x1x2 目标函数目标函数目标函数目标函数 Max Max Z=2=2x x1 1+3x2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x1 1 16 1

34、6 4x2 12 x1 1、x x2 2 0 0 0 0 x1+2x2=84x1=164 x2=12可行域可行域BCDEA图解法图解法第55页，共70页，编辑于2022年，星期六9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数 Max Z Z=2=2x x1 1+3+3x2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x2 0 0 0 0|123456789x1x1+2x2=84x1=164 x2=12BCDEA2x1+3x2=6图解法图解法第56页，共70页，编辑于2022

35、年，星期六9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x1 1+3x x2 约束条件约束条件约束条件约束条件 x x1 1+2+2x2 2 8 8 4 4x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0|123456789x1x1+2x2 84x1=164 x2=12BCDEAx1+2x2=8 4x1=16最优解最优解(4,2)图解法图解法第57页，共70页，编辑于2022年，星期六图解法求解步骤图解法求解步骤由全部约束条件作图求出可行域；由全部约束条件作图求出可行域；作目标函数等值线，确

36、定使目标函数最作目标函数等值线，确定使目标函数最优的移动方向；优的移动方向；平移目标函数的等值线，找出最优点，平移目标函数的等值线，找出最优点，算出最优值。算出最优值。第58页，共70页，编辑于2022年，星期六线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果(a)唯一唯一最优解最优解 x26 5 4 3 2 1 0|123456789x1第59页，共70页，编辑于2022年，星期六(b)无穷多无穷多最优解最优解6 5 4 3 2 1 0 x2|123456789x1线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果第60页，共70页，编辑于2022年，星期六 (c)

37、无界解无界解 Max Max Z Z=x x1+x x2 2 -2-2x1 1+x x2 2 4 x1-x2 2 2 2 x x1、x x2 2 0 0 0 0 x2x1线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果第61页，共70页，编辑于2022年，星期六(d)无可行解无可行解 Max Max Z Z=2=2x x1 1+3x x2 x x1 1+2 +2 x x2 2 8 8 4 4 x x1 1 16 16 4 4x x2 2 12 -2-2x x1 1+x x2 2 4 4 x x1、x x2 2 0 0 可行域为空集可行域为空集可行域为空集可行域为空集线性规划问题求

38、解的线性规划问题求解的 几种可能结果几种可能结果第62页，共70页，编辑于2022年，星期六可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在可行域的顶点得到。可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的所有点都是最优解。所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函解题思路：找出凸集的顶点，计算其目标函数值，比较即得。数值，比较即得。第63页，共70页，编辑于2022年，星期六练习：练习：用图解法求解用图解法求解LP问题问题 Max Z=34 x1

39、+40 x24 x1+6 x2 48 2 x1+2 x2 182 x1+x2 16x1、x2 0 0第64页，共70页，编辑于2022年，星期六图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2=482x1+2x2=182x1+x2=16第65页，共70页，编辑于2022年，星期六图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2=482x1+2x2=182x1+x2=16可行域可行域ABCDE第66页，共70页，编辑于2022年，星期六图

40、解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2=182x1+x2=16ABCDE(8,0)(0,6.8)34x1+40 x2=272第67页，共70页，编辑于2022年，星期六图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2=182x1+x2=16ABCDE(8,0)(0,6.8)第68页，共70页，编辑于2022年，星期六图解法图解法（练习）（练习）x218 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2=182x1+x2=16ABCDE(8,0)(0,6.8)最优解最优解(3,6)4x1+6x2=48 2x1+2x2=18第69页，共70页，编辑于2022年，星期六2 线性规划的图解法线性规划的图解法返回返回返回返回第70页，共70页，编辑于2022年，星期六