运筹学 线性规划 图解法.pptx
第二节 图解法 对模型中只含2个变量的线性规划问题，可以通过在平面上作图的方法求解。第1页/共22页 一、图解法的步骤 1.等直线法 第2页/共22页x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03Q21.建立平面直角坐标系；4向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。2.找出表示每个约束的半平面，所有半平面的交集是可行域（全体可行解的集合）；3.画出目标函数的等值线；第3页/共22页2.试算法x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2最优解在顶点达到：O点：X1=0,X2=0,Z=0Q1:X1=4,X2=0,Z=8Q2:X1=4,X2=2,Z=14Q3:X1=2,X2=3,Z=10Q4:X1=0,X2=3,Z=6第4页/共22页二、线性规划问题解的存在情况1.存在唯一最优解x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2第5页/共22页2.有无穷多最优解 若将例1目标函数变为 max z=2x1+4x2，则问题变为存在无穷多最优解。如图:x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q2第6页/共22页 3.有无界解z 可行域可伸展到无穷，由此目标函数值也可增大至无穷。这种情况下问题的最优解无界。产生无界解的原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束条件。第7页/共22页 例如：max Z=2x1+2x2 s.t.-2x1+x24 x1-x2 2 x1，x2 00 x1x2第8页/共22页例如：min z=60 x1+50 x2 2x1+4x2 80 3x1+2x2 60 x1，x2 00 x1x2无界不一定无最优解x1=10,x2=15 z=1350第9页/共22页模型的约束条件之间存在矛盾，建模时有错误。4.无可行解（可行域为空集）第10页/共22页 例如：max Z=x1+2x2 -x1-x22 2x1+x24 x1，x2 00 x1x2第11页/共22页 三、由图解法得到的启示 图解法虽只能用来求解只具有两个变量的线性规划问题，但它的解题思路和几何上直观得到的一些概念判断，对下面要讲的单纯形法有很大启示：1求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解。（见下页图示所示）2若线性规划问题的可行域存在，则可行域是一个凸集。3若线性规划问题的最优解存在，则最优解或最优解之一(如果有无穷多的话)一定是可行域的凸集的某个顶点。4解题思路是，先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更大的另一顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。第12页/共22页 (d)可行域无界 (e)可行域无界 (f)可行域为空集 多个最优解 目标函数无界 无可行解 (a)可行域有界 (b)可行域有界 (c)可行域无界 唯一最优解 多个最优解 唯一最优解第13页/共22页某厂利用A、B两种原料，生产甲、乙两种产品，有关数据如下：课堂作业：用图解法求解下列问题产品名称甲 乙单位产品消耗原料原料名称可供利用的原料数量（吨/日）681 22 1AB产品售价（千元/T）3 2根据市场调查，有如下资料：1.乙产品的需求量至多 2 吨/日;2.乙产品的需求量比甲产品的需求量至多大 1 吨/日。求该厂产值最大的生产方案。第14页/共22页 max Z=3x1+2x2 x1+2x26 2x1+x28 x22 x2-x11 x1，x200 x1x2X1=10/3,x2=4/3Z=12.67第15页/共22页线性代数基础知识补充与回顾第16页/共22页一、克莱姆规则 含有含有n n个未知数个未知数x x1 1,x,x2 2,x xn n的的n n个线性方程的个线性方程的方程组如下式所示：方程组如下式所示：第17页/共22页 克莱姆法则克莱姆法则 如果上述线性方程组的系数行列式不等于零，即如果上述线性方程组的系数行列式不等于零，即有：有：那么，上述方程组有唯一解：其中Dj（j=1，2，n）是把系数行列式D中的第j列的元素用方程组的常数项代替后得到的n阶行列式.第18页/共22页定理一:如果线性方程组的系数行列式D不等于零，则上述方程组一定有解，且解是唯一的。定理二:如果上述方程组无解或有两个不同的解，则它的系数行列式必为零。第19页/共22页二、矩阵的秩定义定义1 1 在在矩阵A中，任取k行与k列(K=m,k=n)，位于这些行列交叉处的k的平方个元素，不改变他们在A中所处的位置次序而得到的k阶行列式，称为矩阵A的k阶子式。第20页/共22页 定义二:设在矩阵中有一个不等于设在矩阵中有一个不等于0 0的的r r阶子式阶子式D D，并，并且所有的且所有的r+1r+1阶子式（如果存在）全等于零，那阶子式（如果存在）全等于零，那么么D D称为矩阵称为矩阵A A的最高阶非零子式，数的最高阶非零子式，数r r称为矩阵称为矩阵A A的秩。的秩。第21页/共22页感谢您的观看！第22页/共22页
