请教运筹学的单纯形表法?看书里的看不怎么懂!麻烦会的朋友加以自己的理解通俗一点讲解单纯形表法!

来源:学生作业帮助网 编辑:六六作业网 时间:2024/05/15 02:40:22
请教运筹学的单纯形表法?看书里的看不怎么懂!麻烦会的朋友加以自己的理解通俗一点讲解单纯形表法!请教运筹学的单纯形表法?看书里的看不怎么懂!麻烦会的朋友加以自己的理解通俗一点讲解单纯形表法!请教运筹学的

请教运筹学的单纯形表法?看书里的看不怎么懂!麻烦会的朋友加以自己的理解通俗一点讲解单纯形表法!
请教运筹学的单纯形表法?
看书里的看不怎么懂!麻烦会的朋友加以自己的理解通俗一点讲解单纯形表法!

请教运筹学的单纯形表法?看书里的看不怎么懂!麻烦会的朋友加以自己的理解通俗一点讲解单纯形表法!
学运筹学的前提是要掌握线性代数.
那就先简单介绍一下做法吧:
1.将min 后面的部分的系数,取相反数(这一行数也称作为检验数)
2.接下来就是将检验数这一行下面的矩阵化到含有单位矩阵的形式,即含有1,0
3.每次化的时候要注意,化成1,0的那一列上面对应的检验数一定要通过矩阵的初级变换将该数化为零.
4.直到所有的检验数都小于零,这时候检验数这一行所对应的RHS就是最优值.
5.含有1,0的那一列1所对应的RHS为该x的解,其余的用零来填满.
e.g.
x1 x2 x3 RHS
-1 -2 -1 |-1
-5 0 1 |-9
-3 1 0 |-4
此时,检验数小于零,z0=-1为最优解,x=(0,-4,-9)是基本可行解.
这样说应该还算清楚的吧~
"如果我发现不是最优解,把一个原来的基变量出基,移入新的基变量,如何产生新的单纯形表"关于这个问题,我们在检验数大于零的那一列,用检验数除以下面是正数的数,得到那个商最小,就采用那个数作为新的转轴元,将此数上下的数都通过矩阵的初级变换化为零,即可得到新的单纯形表

我是前一阵自学的单纯形法,估计我的回答能够“通俗”。
1,想用单纯形法表解线性规划,得先把所有的不等式转划为“标准型”的约束方程:
a.求min的,改为求其相反数的max
b.如果b值是小于0的,那么两端同乘-1,不等号改向。
例 2*x1+3*x2≥-13 ,转化为 -2*x1-3*x2≤13
c.如果不等式是≤,那么加上一...

全部展开

我是前一阵自学的单纯形法,估计我的回答能够“通俗”。
1,想用单纯形法表解线性规划,得先把所有的不等式转划为“标准型”的约束方程:
a.求min的,改为求其相反数的max
b.如果b值是小于0的,那么两端同乘-1,不等号改向。
例 2*x1+3*x2≥-13 ,转化为 -2*x1-3*x2≤13
c.如果不等式是≤,那么加上一个系数为1的“松弛变量”,
如果不等式是=,那么就加上一个系数为1的“人工变量”,
如果不等式是≥,那么就加上一个系数为-1的“松弛变量”
再加上一个系数为1的“人工变量”
后添加这些变量的目的,就是为了每个方程,都有一个系数为“1”的变量(不包括-1),而且这些后加入的系数为“1”的变量,在其它方程的系数都为“0”。
“这样,这些变量就可以组成一个可行基,后面的b值,也就是可行解”这句话,得思考一下,才能明白。。。
需要思考的东西在下面:所谓的基,就是让非基变量都等于0,那么所有的方程,都可以化简为“只有基变量”的方程,例如
k11*x1+k12*x2+k13*x3+1*x4+0*x5+0*x6 =b1
k21*x1+k22*x2+k23*x3+0*x4+1*x5+0*x6 =b2
k31*x1+k32*x2+k33*x3+0*x4+0*x5+1*x6 =b3
无论k11,k12,k13,k21,k22,k23,k31,k32,k33有多么复杂,但因为令x1,x2,x3=0,所以x1,x2,x3这三列变量可以直接无视,转化为
1*x4+0*x5+0*x6 =b1
0*x4+1*x5+0*x6 =b2
0*x4+0*x5+1*x6 =b3
那么这个解,也就是x1,x2,x3=0,x4=b1,x5=b2,x6=b3,这起码就是一个“基解”了
因为之前做的工作“b.如果b值是小于0的,那么两端同乘-1,不等号改向”,所有的b值都被你变成≥0的数了,所以解出来的x4,x5,x6都≥0,那么当然也就是“可行解”,因为你在加入这些变量的时候,就是假定一切变量都≥0,如果解出来一个某个x的数,是<0的,那么肯定就不是“可行解”了,为就是之前需要把b值变为正数的原因
单纯形法表,也是这个道理,不断的改变每个方程的“基变量”--如果想让某个变量做为“基变量”,就得把它在这个方程里的系数转化为 1,把它在其它方程里的系数,转化为0,这样后面的b值,就是这个变量的值了。
2,单纯形法表,你打开我另一个回答看参考一下
http://zhidao.baidu.com/question/144835247.html
第一行:那些-1,1,-1,0,0,0就是目标函数中,各变量的系数。
第三-五行:就是三个约束方程中,各变量的系数。
第三行对应第一个方程,这方程中X4系数为1,且X4在其它方程的系数为0,所以让X4做基变量----那么在第三行的第二列,写上X4,,,在第三行的第一列,写上X4在第一行所对应的数字“0”
第四,五行,同上。
最后一行就是所谓的“检验数”,算法是
第1行数字 - 三行本列×三行1列 - 四行本列×四行1列 - 五行本列×五行1列
(用第三个表的验算一下就清楚了)
把所有非基变量(即x1,x2,x3)的检验数都算出来之后,选最大的一个,做为入基变量,很显然,X2是入基变量,
再用每行的 b列的数字 除以 X2所以列的数字,就得出最后一列的那个“西塔”值,这时,得选最小的那行做为出基变量,显然,X4是出基变量。。。。
这就是第一行,第二格,X2-X4代表的意思。这两个变量“迭代互换”
所谓“迭代”,说起来麻烦,其实也很简单,就是把第一行的方程中X2的系数变通过除法为1,并且通过与其它方程相加减,把其它方程中的X2的系数变为0,这样X2就算“入基”了
这就是表2的由来:
第一个表,第三行中,X2的系数本来就是1,那么,这个方程就不用变换了(假设系数是-2,那需要把方程两边---即所有系数与b值---同时除以-2)
第一个表,第四行中,X2的系数是1,那么用这行所有系数与第三行的相减,就可以把这行的X2的系数变为0
第一个表,第五行中,X2的系数是0,不用变换了。
这样就得到表2,其它东西,依照表1的填。
然后就是不断的“迭代”。。一直到所有的非基变量检验数都是负数了,那么也就得到了最优解了。
打的很累。
其实已经很通俗了,如果还看不懂,可以通过百度消息再联系。

收起