图解法与单纯形法改

《图解法与单纯形法改》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的图解法与单纯形解法1线性规划问题的图解法线性规划的基本性质线性规划单纯形法的原理与计算步骤线性规划单纯形法的进一步讨论线性规划特例—运输问题2.1线性规划问题的图解法图解法是用作图的方法求解线性规划问题，一般只适用于具有两个决策变量的线性规划问题。步骤1画直角坐标系步骤2根据约束条件画出可行域步骤3画过坐标原点的目标函数线步骤4确定目标函数的增大方向步骤5让目标函数沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解。x1x2O1020304010203040(15,10)最优解X=(15,10)最优值Z=85

2、例题2.1线性规划问题的图解法用图解法求解如下线性规划问题：例12.1线性规划问题的图解法求解Q3点为（3，3），此时z=152.1线性规划问题的图解法本例中我们用图解法得到的问题的最优解是惟一的。但在线性规划问题的计算中,解的情况还可能出现下列几种:1无穷最优解。如将本例的目标函数改变为则目标函数的图形恰好与(1)平行。因此该线性规划问题有无穷多个最优解,也称具有多重最优解。2.1线性规划问题的图解法2.无界解(有可行解但无有界最优解)。如果本例中约束条件只剩下(2)和(4),其他条件(1)、(3)不再考虑。用图解法求解时,可以看到变量的取值可以无限增大,

3、因而目标函数的值也可以一直增大到无穷。这种情况下称问题具有无界解或无最优解。其原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束。2.1线性规划问题的图解法3.无可行解。如下述线性规划模型：用图解法求解时找不到满足所有约束条件的公共范围，这时问题无可行解。其原因是模型本身有错误,约束条件之间相互矛盾,应检查修正。图解法虽然只能用来求解只具有两个变量的线性规划问题,但它的解题思路和几何上直观得到的一些概念判断,对下面要讲的求解一般线性规划问题的单纯形法有很大启示:线性规划问题求解的基本依据是：线性规划问题的最优解总可在可行域的顶点中寻找，寻找线性规划

4、问题的最优解只需比较有限个顶点处的目标函数值。线性规划问题求解时可能出现四种结局：唯一最优解无穷多个最优解无有界解无解或无可行解如果某一线性规划问题有最优解，可以按照以下思路求解：先找可行域中的一个顶点，计算顶点处的目标函数值，然后判别是否有其他顶点处的目标函数值比这个顶点处的目标函数值更大，如有，转到新的顶点，重复上述过程，直到找不到使目标函数值更大的新顶点为止。线性规划的基本性质凸集对集合C中任意两个点其连线上的所有点都是集合C中的点，则C为凸集。由于的连线可以表示为，因此凸集的数学表达为：对任意的，有则称C为凸集。线性规划的基本性质定理1若线性规划问题

5、存在可行域，则其可行域一定是凸集。引理线性规划问题的可行解X=(x1,x2,…,xn)T为基可行解的充要条件是X的正分量对应的系数列向量是线性独立的。定理2线性规划问题的基可行解对应可行域的顶点。定理3若线性规划问题有最优解，一定存在一个基可行解是最优解。从可行域中的一个基可行解出发，判别它是否已经是最优解，如果不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无解为止。基本思想：2.2线性规划单纯形法的原理与计算步骤3寻找改进的基可行解2最优性检验和解的判别1确定初始基可行解【例2】用单纯形法求下列线性规划的最

6、优解单纯形法的计算步骤：步骤1：求初始基可行解，列出初始单纯形表。对非标准形式的线性规划问题首先要化成标准形式。由于我们总可以设法使约束方程的系数矩阵中包含一个单位矩阵[P1,P2,…,Pm]，以此作为基即可求得问题的一个初始基可行解。必须是标准形式【解】首先化为标准型，加入松驰变量x3、x4则标准型为系数矩阵A及可行基B1r(B1)=2，B1是单位矩阵作为初始基,x3、x4为基变量，x1、x2为非基变量，令x1=0、x2=0由约束方程知x3=40、x4=30得到初始基可行解X(1)=(0,0,40,30)T单纯形法的计算步骤：步骤2最优性检验在单纯形表中，

7、若所有的检验数表中的基可行解即为最优解。若存在并且有，则问题无有界解。计算结束。否则转入下一步。步骤3从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表。步骤4重复步骤2和3，一直到计算结束。进基列出基行bi/ai2，ai2>0θi表1-4(1)XBx1x2x3x4bx3211040x4130130σj3400(2)x3x2σj(3)x1x2σj基变量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/52/5400-1-1将3化为1乘以1/3后得到3018单纯形算法的计算步骤①将线性规划问题化

8、成标准型。②找出或构造一个m阶单位矩阵作为初始可行基