运筹学 线性规划 图解法ppt课件.ppt

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