线性规划的图解法与单纯形解法

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

1、运筹学OperationsResearch王　慧东南大学经济管理学院电子商务系暨管理工程研究所13814011801,wh_whq@126.com1线性规划的图解法与单纯形解法线性规划问题的图解法线性规划单纯形解法的原理线性规划单纯形解法的计算步骤单纯形法计算的矩阵描述线性规划单纯形求解的大M法线性规划单纯形求解的两阶段法线性规划单纯形求解可能的循环现象2线性规划问题的图解法图解法，就是用作图的方法求解线性规划问题。简单、直观的图解法一般只适用于具有两个决策变量的线性规划问题。用图解法求解实际线性规划问题，一般按照如下基本步骤：S

2、tep1画直坐标系；Step2根据约束条件画出可行域；Step3画过坐标原点的目标函数线；Step4确定目标函数值的增大方向(目标函数线法线方向)Step5目标函数线沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解。3x1x2O1020304010203040(15,10)最优解X=(15,10)最优值Z=85例2.14246x1x2246最优解X=(3,1)最优值Z=5(3,1)minZ=x1+2x2例2.25246x1x2246X（2）＝（3,1）X（1）＝（1,3）minZ=5x1+5x2

3、例2.3有无穷多个最优解即具有多重解,通解为0≤α≤1当α=0.5时Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)6246x1x2246无界解(无最优解)maxZ=x1+2x2例2.47x1x2O10203040102030405050无可行解即无最优解maxZ=10x1+4x2例2.58由以上例题可知，线性规划的解有4种形式：1.有唯一最优解(例2.1例2.2)2.有多重解(例2.3)3.有无界解(例2.4)4.无可行解(例2.5)1、2情形为有最优解3、4情形为无最优解9由图解法得到的启示线性规划问题求解的

4、基本依据是：线性规划问题的最优解总可在可行域的顶点中寻找。寻找线性规划问题的最优解只需比较有限个顶点处的目标函数值。线性规划问题求解时可能出现四种结局：唯一最优解、无穷多个最优解、无有界解、无解或无可行解。如果某一线性规划问题有最优解，我们可以按照这样的思路来求解：先找可行域中的一个顶点，计算顶点处的目标函数值，然后判别是否有其它顶点处的目标函数值比这个顶点处的目标函数值更大，如有，转到新的顶点，重复上述过程，直到找不到使目标函数值更大的新顶点为止。101.通过图解法了解线性规划有几种解的形式2.作图的关键有三点(1)可行解区域要

5、画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动11线性规划单纯形解法的原理单纯形方法的基本思想从可行域中的一个基可行解出发，判别它是否已经是最优解，如不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无解为止。单纯形算法必须解决三个方面的问题：1.如何确定初始的基可行解？2.如何进行解的最优性判别？3.如何寻找改进的基可行解？12确定初始的基可行解标准型的线性规划问题系数矩阵中存在一个单位阵以单位阵为一初始可行基。令非基变量取值为零，便得到一基可行解。13【例2

6、.6】用单纯形法求下列线性规划的最优解14【解】化为标准型，加入松驰变量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)T15以上得到的一组基可行解是不是最优解，可以从目标函数中的系数看出。目标函数Z=3x1+4x2中x1的系数大于零，如果x1为一正数，则Z的值就会增大，同样若x2不为零为一正数，也能使Z的值增大；因此只要目标函数中非基变量的系数大于零，那么目

7、标函数就没有达到最大值，即没有找到最优解，判别线性规划问题是否达到最优解的数称为检验数，记作σj,j=1,2…,n。本例中σ1=3,σ2=4,σ3=0,σ4=0。最优解判断标准当所有检验数σj≤0（j=1，…，n）时，基本可行解为最优解。当目标函数中有基变量xi时，利用约束条件将目标函数中的xi消去即可求出检验数。检验数目标函数用非基变量表达时的变量系数16进基列出基行bi/ai2，ai2>0θi表1-4(1)XBx1x2x3x4bx3211040x4130130σj3400(2)x3x2σj(3)x1x2σj基变量110001/

8、301/3105/31-1/3405/30-4/330103/5-1/51801-1/52/5400-1-1将3化为1乘以1/3后得到301817最优解X=(18，4，0，0)T，最优值Z=70O20301040(3,4)X(3)=(18,4)最优