经济学图解法与单纯形法.pptx

,一般只适用于具有两个决策变量的线性规划问题。步骤1画直角坐标系步骤2根据约束条件画出可行域步骤3画过坐标原点的目标函数线步骤4确定目标函数的增大方向步骤5让目标函数沿着增大方向平行移动,与可行域相交且有最大目标函数值的顶点,即为线性规划问题的最优解。x1x2O1020304010203040(15,10)最优解X=(15,10)最优值Z=:(3,3),此时z=。但在线性规划问题的计算中,解的情况还可能出现下列几种:1无穷最优解。如将本例的目标函数改变为则目标函数的图形恰好与(1)平行。因此该线性规划问题有无穷多个最优解,也称具有多重最优解。(有可行解但无有界最优解)。如果本例中约束条件只剩下(2)和(4),其他条件(1)、(3)不再考虑。用图解法求解时,可以看到变量的取值可以无限增大,因而目标函数的值也可以一直增大到无穷。这种情况下称问题具有无界解或无最优解。其原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束。。如下述线性规划模型:用图解法求解时找不到满足所有约束条件的公共范围,这时问题无可行解。其原因是模型本身有错误,约束条件之间相互矛盾,应检查修正。图解法虽然只能用来求解只具有两个变量的线性规划问题,但它的解题思路和几何上直观得到的一些概念判断,对下面要讲的求解一般线性规划问题的单纯形法有很大启示:线性规划问题求解的基本依据是:线性规划问题的最优解总可在可行域的顶点中寻找,寻找线性规划问题的最优解只需比较有限个顶点处的目标函数值。线性规划问题求解时可能出现四种结局:唯一最优解无穷多个最优解无有界解无解或无可行解如果某一线性规划问题有最优解,可以按照以下思路求解:先找可行域中的一个顶点,计算顶点处的目标函数值,然后判别是否有其他顶点处的目标函数值比这个顶点处的目标函数值更大,如有,转到新的顶点,重复上述过程,直到找不到使目标函数值更大的新顶点为止。(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动从可行域中的一个基可行解出发,判别它是否已经是最优解,如果不是,寻找下一个基可行解,并且同时努力使目标函数得到改进,如此迭代下去,直到找到最优解或判定问题无解为止。基本思想: