《数学建模线性规划及单纯型法精品文稿.ppt》由会员分享，可在线阅读，更多相关《数学建模线性规划及单纯型法精品文稿.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模线性规划及单纯型法第1页，本讲稿共71页目录一一.线性规划问题及其模型线性规划问题及其模型二二.线性规划的基本算法线性规划的基本算法单纯形法单纯形法三三.线性规划数学软件求解线性规划数学软件求解四四.线性规划应用举例线性规划应用举例第2页，本讲稿共71页 线性规划问题的提出线性规划问题的提出 线性规划的基本概念线性规划的基本概念 线性规划的数学模型线性规划的数学模型继续继续继续继续返回返回返回返回一一 线性规划问题及其数学模型线性规划问题及其数学模型第3页，本讲稿共71页问题的提出问题的提出例:生产计划问题第4页，本讲稿共71页产品产品I产品产品2如何安排生产如何安排生产使利润最大使利
2、润最大？第5页，本讲稿共71页决策变量（决策变量（决策变量（决策变量（Decision variablesDecision variables）目标函数（目标函数（目标函数（目标函数（Objective functionObjective function）约束条件（约束条件（约束条件（约束条件（Constraint conditionsConstraint conditions）可行域（可行域（可行域（可行域（Feasible region)Feasible region)最优解（最优解（最优解（最优解（Optimal solution)Optimal solution)基本概念基本概念问题
3、中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表明规划中的用数量表示的方明规划中的用数量表示的方明规划中的用数量表示的方明规划中的用数量表示的方案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定和控制。和控制。和控制。和控制。它是决策变量的函数它是决策变量的函数它是决策变量的函数它是决策变量的函数指决策变量取值时受到的各种指决策变量取值时受到的各种指决策变量取值时受到的各种指决策变量取值时受到的各种资源条件的限制，通常表达为资源条件的限制，通常表达为资源条件的限制，通常表达为资源条件的限制，通常表达为含决
4、策变量的等式或不等式。含决策变量的等式或不等式。含决策变量的等式或不等式。含决策变量的等式或不等式。满足约束条件的决策满足约束条件的决策满足约束条件的决策满足约束条件的决策变量的取值范围变量的取值范围变量的取值范围变量的取值范围可行域中使目标函可行域中使目标函可行域中使目标函可行域中使目标函数达到最优的决策数达到最优的决策数达到最优的决策数达到最优的决策变量的值变量的值变量的值变量的值第6页，本讲稿共71页是问题中要确定的未知量，表是问题中要确定的未知量，表是问题中要确定的未知量，表是问题中要确定的未知量，表明规划中的用数量表示的方案、明规划中的用数量表示的方案、明规划中的用数量表示的方案、明
5、规划中的用数量表示的方案、措施，可由决策者决定和控制。措施，可由决策者决定和控制。措施，可由决策者决定和控制。措施，可由决策者决定和控制。第第1步步-确定决策变量确定决策变量设设 I的产量的产量 II的产量的产量 利润利润第7页，本讲稿共71页第第2步步-定义目标函数定义目标函数Max Z=x1+x2决策变量决策变量第8页，本讲稿共71页 Max Z=2 x1+3 x2系数系数第第2步步-定义目标函数定义目标函数第9页，本讲稿共71页对我们有对我们有何限制何限制?第10页，本讲稿共71页第第3步步-表示约束条件表示约束条件 x1+2 x2 8 4 x1 16 4 x2 12 x1、x2 0 0
6、第11页，本讲稿共71页该计划的数学模型该计划的数学模型 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0 x1 x2第12页，本讲稿共71页线性规划问题的共同特征线性规划问题的共同特征一组决策变量一组决策变量X X表示一个方案表示一个方案,一般一般X X大于大于等于零。等于零。约束条件是线性等式或不等式。约束条件是线性等式或不等式。目标函数是线性的。目标函数是线性的。求目标函数最大化求目标函数最大化或最小化或最小化第13页，本讲稿共71页 线性规划模型的一般形式线性规划模型的一般形式 第14页，本讲稿共71页线性
7、规划模型建立步骤 从实际问题中建立数学模型一般有以下三个步骤；从实际问题中建立数学模型一般有以下三个步骤；1.根据影响所要达到目的的因素找到决策变量；根据影响所要达到目的的因素找到决策变量；2.由决策变量和所在达到目的之间的由决策变量和所在达到目的之间的函数函数关系确定目标函数；关系确定目标函数；3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。由决策变量所受的限制条件确定决策变量所要满足的约束条件。第15页，本讲稿共71页1.1.线性规划的标准形式：线性规划的标准形式：用单纯法求解时，常将标准形式化为：2.线性规划的基本算法线性规划的基本算法单纯形法单纯形法二二.线性规划的基本算法
8、线性规划的基本算法单纯形法单纯形法第16页，本讲稿共71页引入松弛变量引入松弛变量x3,x4,x5,将不等式化为等式将不等式化为等式,即单纯形标准形即单纯形标准形:显然显然A的秩的秩ran(A)=3,任取任取3个线性无关的列向量个线性无关的列向量,如如P3P4P5称为称为一组基一组基,记为记为B.其余列向量称为非基其余列向量称为非基,记为记为N.第17页，本讲稿共71页于是于是f=cBxB+cNxN,Ax=BxB+NxN=b,则则xB=B-1b-B-1NxN,f=cBB-1b+(cNcBB-1N)xN 若可行基进一步满足若可行基进一步满足:cNcBB-1N0,即即:cBB-1N-cN0则对一切
9、可行解则对一切可行解x,必有必有f(x)cBB-1b,此时称基可行解此时称基可行解x=(B-1b,0)T为最优解为最优解.3.最优解的存在性定理最优解的存在性定理将将A的列向量重排次序成的列向量重排次序成A=(B,N),相应相应x=(xB,xN)T,c=(cB,cN)基对应的变量基对应的变量xB称为基变量称为基变量,非基对应的变量非基对应的变量xN称为非基变量称为非基变量.定理定理1 1 如果线性规划如果线性规划(1)(1)有可行解，那么一定有基可行解有可行解，那么一定有基可行解.定理定理2 2 如果线性规划如果线性规划(1)(1)有最优解，那么一定存在一个基可行解有最优解，那么一定存在一个基
10、可行解 是最优解是最优解.第18页，本讲稿共71页4.4.基可行解是最优解的判定准则基可行解是最优解的判定准则因为因为f=cBB-1b+(cNcBB-1N)xN，即即f-0 xB+(cBB-1N-cN)xN=cBB-1b检验数检验数第19页，本讲稿共71页5.5.基可行解的改进基可行解的改进第20页，本讲稿共71页改进方法：改进方法：返返回回第21页，本讲稿共71页练习建立练习建立LPLP数学模型数学模型一、有两个煤厂一、有两个煤厂A A、B B，每月分别供应三个居每月分别供应三个居民区民区X X、Y Y、Z Z。求运费最少的方案。求运费最少的方案。供需平衡供需平衡第22页，本讲稿共71页1、
11、LINGO使用简介使用简介 LINGO软件是美国的软件是美国的LINDO系统公司（系统公司（Lindo System Inc）开）开发的一套用于求解最优化问题的软件包发的一套用于求解最优化问题的软件包.LINGO除了能用于求解除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解性和非线性方程（组）的求解.LINGO软件的最大特色在于它允软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快许优化模型中的决策变量为整数，而且执行速度快.LINGO内置内置了一种建立最优化模型的语言，可以
12、简便地表达大规模问题，利了一种建立最优化模型的语言，可以简便地表达大规模问题，利用用LINGO高效的求解器可快速求解并分析结果，这里简单介绍高效的求解器可快速求解并分析结果，这里简单介绍LINGO的使用方法的使用方法.LINGO可以求解线性规划、二次规划、非线性规划、整数规划、可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等图论及网络优化和排队论模型中的最优化问题等.一个一个LINGO程序一般会包含集合段、数据输入段、优化目标和程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分，每一部分有其独特的作约束段、初始段和数据预处
13、理段等部分，每一部分有其独特的作用和语法规则，读者可以通过查阅相关的参考书或者用和语法规则，读者可以通过查阅相关的参考书或者LINGO的的HELP文件详细了解，这里就不展开介绍了文件详细了解，这里就不展开介绍了.三.线性规划软件求解第23页，本讲稿共71页LINGO的主要功能特色为：既能求解线性规划问题，也有较的主要功能特色为：既能求解线性规划问题，也有较强的求解非线性规划问题的能力；输入模型简练直观；运算强的求解非线性规划问题的能力；输入模型简练直观；运算速度快、计算能力强；内置建模语言，提供几十个内部函数，速度快、计算能力强；内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式
14、描述大规模的优化模型；从而能以较少语句，较直观的方式描述大规模的优化模型；将集合的概念引入编程语言，很容易将实际问题转换为将集合的概念引入编程语言，很容易将实际问题转换为LINGO模型；并且能方便地与模型；并且能方便地与Excel、数据库等其他软件交、数据库等其他软件交换数据换数据.第24页，本讲稿共71页第一步：启动第一步：启动Lingo屏幕显示如下：屏幕显示如下：标记标记LINGO的外窗口是主框架窗口，的外窗口是主框架窗口，主框架窗口的上面包含所有的命令菜单主框架窗口的上面包含所有的命令菜单和命令工具栏；和命令工具栏；标记标记LINGO MODEL-LINGO1的子窗的子窗口是一个新的、空
15、白的模型窗口。口是一个新的、空白的模型窗口。第25页，本讲稿共71页第二步：在模型窗口中输入模型第二步：在模型窗口中输入模型model:model:max=2*x1+3*x2;max=2*x1+3*x2;4*x1+3*x210;4*x1+3*x210;3*x1+5*x212;3*x1+5*x212;endendMax2x1+3x2St.4x1+3x2=103x1+5x2=12x10 x20第26页，本讲稿共71页第三步：求解模型第三步：求解模型 1)选择菜单选择菜单 LINGO|Solve 或者按工具栏的或者按工具栏的 第27页，本讲稿共71页 2)LINGO开始编译模型，如有语法错误将返回开
16、始编译模型，如有语法错误将返回一个错误的消息并指明错误出现的位置；如果一个错误的消息并指明错误出现的位置；如果通过编译通过编译,LINGO将激活将激活 Solver运算器运算器 寻求寻求模型的最优解；模型的最优解；3)3)首先出现首先出现solver status solver status 窗口窗口，其作，其作用是监控用是监控solversolver的进展和显示模型的的进展和显示模型的维数等信息；维数等信息；第28页，本讲稿共71页第29页，本讲稿共71页4)计算完成后出现计算完成后出现Solution Report窗口显示模型解的详细信息；窗口显示模型解的详细信息；第30页，本讲稿共71页
17、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.5454545第31页，本讲稿共71页LINGO的语法规定、运算符及函数：的语法规定、运算符及函数：（1）
18、求目标函数的最大值或最小值分别用）求目标函数的最大值或最小值分别用MAX=或或MIN=来表来表示；示；（2）每个语句必须以分号）每个语句必须以分号“；”结束，每行可以有许多语句，语句结束，每行可以有许多语句，语句可以跨行；可以跨行；（3）变量名称必须以字母（）变量名称必须以字母（AZ）开头，由字母、数字（）开头，由字母、数字（09）和）和下划线所组成，长度不超过下划线所组成，长度不超过32个字符，不区分大小写；个字符，不区分大小写；（4）可以给语句加上标号，例如）可以给语句加上标号，例如OBJ MAX=200*X1+300*X2；（5）以惊叹号）以惊叹号“！”开头，以分号开头，以分号“；”结束
19、的语句是注释语句；结束的语句是注释语句；（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；量都非负；（7）LINGO模型以语句模型以语句“MODEL：”开头，以开头，以“END”结束，对于结束，对于比较简单的模型，这两个语句可以省略比较简单的模型，这两个语句可以省略.(8)可以用可以用表示表示表示表示=；Lingo无严格小于，欲使无严格小于，欲使ab，可以适当选取小的正常数可以适当选取小的正常数e 表示成表示成a+eb，第32页，本讲稿共71页(9)LINGO(9)LINGO(9)LINGO(9)LINGO编辑器用编辑器用
20、编辑器用编辑器用 蓝色蓝色蓝色蓝色显示显示显示显示LINGOLINGOLINGOLINGO关键字关键字关键字关键字;绿色绿色绿色绿色显示显示显示显示注释注释注释注释 ;其他文本用黑色其他文本用黑色其他文本用黑色其他文本用黑色 匹配的括号匹配的括号匹配的括号匹配的括号用用用用红色红色红色红色高亮度显示高亮度显示高亮度显示高亮度显示(10)(10)(10)(10)标准运算符标准运算符标准运算符标准运算符算术运算符：算术运算符：算术运算符：算术运算符：*/+-*/+-*/+-*/+-逻辑运算符：逻辑运算符：逻辑运算符：逻辑运算符：#EQ#NE#(#EQ#NE#(#EQ#NE#(#EQ#NE#(相等，
21、不等）相等，不等）相等，不等）相等，不等）为真为真为真为真#GE#GT#GE#GT#GE#GT#GE#GT#（左边大于或等于，左边大于）（左边大于或等于，左边大于）（左边大于或等于，左边大于）（左边大于或等于，左边大于）为真为真为真为真#LE#LT#LE#LT#LE#LT#LE#LT#（左边小于或等于，左边小于）（左边小于或等于，左边小于）（左边小于或等于，左边小于）（左边小于或等于，左边小于）为真为真为真为真#NOT#AND#OR#NOT#AND#OR#NOT#AND#OR#NOT#AND#OR#（取反，取交（积），取并（和）取反，取交（积），取并（和）取反，取交（积），取并（和）取反，取交
22、（积），取并（和）)第33页，本讲稿共71页(11).(11).(11).(11).变量界定函数变量界定函数变量界定函数变量界定函数lingolingolingolingo变量默认域为非负实数变量默认域为非负实数变量默认域为非负实数变量默认域为非负实数free(variable)free(variable)free(variable)free(variable)取消默认域，使变量可以取任意实数取消默认域，使变量可以取任意实数取消默认域，使变量可以取任意实数取消默认域，使变量可以取任意实数gin(variable)gin(variable)gin(variable)gin(variable)限制
23、变量取整数值限制变量取整数值限制变量取整数值限制变量取整数值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)限制变量于一个有限的范围限制变量于一个有限的范围限制变量于一个有限的范围限制变量于一个有限的范围第34页，本讲稿共71页例题例题1：某工厂在计划期内要安排生产某工厂在计划期内要安排生产A、B
24、两种产品，已知生两种产品，已知生产单位产品所需设备台时及对甲、乙两种原材料的消耗，有关数产单位产品所需设备台时及对甲、乙两种原材料的消耗，有关数据如表据如表1.1.问：应如何安排生产计划，使工厂获利最大？问：应如何安排生产计划，使工厂获利最大？产品 资源AB可利用资源设备128台时甲4016公斤乙0412公斤单位利润2元3元建立线性规划问题的数学模型，用建立线性规划问题的数学模型，用LINGO求出最优解并做相求出最优解并做相应的分析应的分析.第35页，本讲稿共71页问题问题1.1设计划生产设计划生产A,B两种产品分别为两种产品分别为x1,x2，则建立线性规划，则建立线性规划问题数学模型问题数学
25、模型模型：模型：max S=2x1+3x2在在LINGO的的MODEL窗口内输入如下模型：窗口内输入如下模型：model:max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=”的不等式，左边减右边的差值为的不等式，左边减右边的差值为Surplus（剩余），（剩余），当约束条件两边相等时，松弛或剩余的值等于零当约束条件两边相等时，松弛或剩余的值等于零.“Dual Price”的的意思是对偶价格（或称为影子价格），上述报告中意思是对偶价格（或称为影子价格），上述报告中Row2的松弛值的松弛值为为0，表明生产甲产品，表明生产甲产品4单位、乙产品单位、乙产品2单位，所需设备单位，
26、所需设备8台时已经台时已经饱和，对偶价格饱和，对偶价格1.5的含义是：如果设备增加的含义是：如果设备增加1台时，能使目标函台时，能使目标函数值增加数值增加1.5.报告中报告中Row4的松弛值为的松弛值为4，表明生产甲产品，表明生产甲产品4单位、单位、乙产品乙产品2单位，所需原材料乙单位，所需原材料乙8公斤还剩余公斤还剩余4公斤，因此增加原材料公斤，因此增加原材料乙不会使目标函数值增加，所以对偶价格为乙不会使目标函数值增加，所以对偶价格为0.第39页，本讲稿共71页用MATLAB优化工具箱解线性规划min z=cX 1、模型：命令：命令：x=linprog（c，A，b）2、模型：min z=cX
27、 命令：命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=，b=.第40页，本讲稿共71页3、模型：min z=cX VLBXVUB命令：命令：1x=linprog（c，A，b，Aeq,beq,VLB，VUB）2x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：1 若没有等式约束:,则令Aeq=,beq=.2其中X0表示初始点 4、命令：、命令：x,fval=linprog()返回最优解及处的目标函数值返回最优解及处的目标函数值fval.第41页，本讲稿共71页解解编写编写M文件文件xxgh1.m如下：如下：c=-0.4-0.28
28、-0.32-0.72-0.64-0.6;A=0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08;b=850;700;100;900;Aeq=;beq=;vlb=0;0;0;0;0;0;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh1)第42页，本讲稿共71页 投资的收益和风险 四四四四.线性规划应用举例线性规划应用举例线性规划应用举例线性规划应用举例第43页，本讲稿共71页(二)、基本假设和符号规定第44页，本讲稿共71页(三)、模型的建立与分析1.总体风
29、险用所投资的总体风险用所投资的Si中最大的一个风险来衡量中最大的一个风险来衡量,即即maxqixi|i=1，2,n4.模型简化：模型简化：第45页，本讲稿共71页第46页，本讲稿共71页(四)、模型1的求解 由于由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从的风险度。我们从a=0开始，以步长开始，以步长a=0.001进行循环搜索，编制程序如下：进行循环搜索，编制程序如下：第47页，本讲稿共71页a=0;while(1.1-a)1 c=-0.05-0.27-0.19-0.185-0.185;A
30、eq=1 1.01 1.02 1.045 1.065;beq=1;A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)ToMatlab（xxgh5）第48页，本讲稿共71页计算结果：第49页，本讲稿共71页(五)、结果分析返返回回4.4
31、.在在a=0.006a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和 收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是大约是a a*=0.6%=0.6%，Q Q*=20%=20%，所对应投资方案为，所对应投资方案为:风险度风险度收益收益x0 x1x2x3x40.00600.201900.24000
32、.40000.10910.22123.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。于不同风险的承受能力，选择该风险水平下的最优投资组合。2.2.当投资越分散时，投资者承担的风险越小，这与题意一致。即当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。风险大，收益也大。第50页，本讲稿共71页
33、实验作业 某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.返 回第51页，本讲稿共71页 图解法图解法 线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果 由图解法得到的启示由图解法得到的启示2 线性规划的图解法线性规划的图解法继续继续继续继
34、续返回返回返回返回第52页，本讲稿共71页例例1的数学模型的数学模型 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0 x1 x2第53页，本讲稿共71页9 8 7 6 5 4 3 2 1 0|123456789x1x2x1+2x2=8(0,4)(8,0)目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2
35、 0 0 0 04x1=164 x2=12图解法图解法第54页，本讲稿共71页9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0|123456789x1x1+2x2=84x1=164 x2=12可行域可行域图解法图解法第55页，本讲稿共71页9 8 7 6 5 4 3 2 1 0|123456789x1x2 目标函数目标函
36、数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0 x1+2x2=84x1=164 x2=12可行域可行域BCDEA图解法图解法第56页，本讲稿共71页9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x
37、1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0|123456789x1x1+2x2=84x1=164 x2=12BCDEA2x1+3x2=6图解法图解法第57页，本讲稿共71页9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0|123456789x1x1+2x2 84x1=1
38、64 x2=12BCDEAx1+2x2=8 4x1=16最优解最优解(4,2)图解法图解法第58页，本讲稿共71页图解法求解步骤图解法求解步骤由全部约束条件作图求出可行域；由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最作目标函数等值线，确定使目标函数最优的移动方向；优的移动方向；平移目标函数的等值线，找出最优点，平移目标函数的等值线，找出最优点，算出最优值。算出最优值。第59页，本讲稿共71页线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果(a)唯一唯一最优解最优解 x26 5 4 3 2 1 0|123456789x1第60页，本讲稿共71页(b)无穷多无穷多
39、最优解最优解6 5 4 3 2 1 0 x2|123456789x1线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果第61页，本讲稿共71页 (c)无界解无界解 Max Max Z Z=x x1 1+x x2 2 -2-2x x1 1+x x2 2 4 4 x x1 1-x x2 2 2 2 x x1 1、x x2 2 0 0 0 0 x2x1线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果第62页，本讲稿共71页(d)无可行解无可行解 Max Max Z Z=2=2x x1 1+3+3x x2 2 x x1 1+2 +2 x x2 2 8 8 4 4 x x1 1
40、 16 16 4 4x x2 2 12 12 -2-2x x1 1+x x2 2 4 4 x x1 1、x x2 2 0 0 0 0 可行域为空集可行域为空集可行域为空集可行域为空集线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果第63页，本讲稿共71页可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在可行域的顶点得到。可行域的顶点得到。可行域的顶点得到。可行域
41、的顶点得到。若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的所有点都是最优解。所有点都是最优解。所有点都是最优解。所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函解题思路：找出凸集的顶点，计算其目标函解题思路：找出凸集的顶点，计算其目标函解题思路：找出凸集的顶点，计算其目标函数值，比较即得。数值，比较即得。数值，比较即得。数值，比较即得。第64页，本讲稿共71页练习：练习：用图解法求解用图解法求解LP问题问题 Max Z=34 x1+40 x24 x1+6 x2 48 2 x1+2
42、x2 182 x1+x2 16x1、x2 0 0第65页，本讲稿共71页图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2=482x1+2x2=182x1+x2=16第66页，本讲稿共71页图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2=482x1+2x2=182x1+x2=16可行域可行域ABCDE第67页，本讲稿共71页图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x2
43、4x1+6x2 482x1+2x2=182x1+x2=16ABCDE(8,0)(0,6.8)34x1+40 x2=272第68页，本讲稿共71页图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2=182x1+x2=16ABCDE(8,0)(0,6.8)第69页，本讲稿共71页图解法图解法（练习）（练习）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第70页，本讲稿共71页2 线性规划的图解法线性规划的图解法返回返回返回返回第71页，本讲稿共71页