单纯形法例题

《单纯形法例题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单纯形法例题1、例1、目标函数maxz=2x1+3x2约束条件：x1+2x2≤84x1≤164x2≤12x1，x1≥0解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量，x3，x4，x5，并且它们都大于等于0.得到的标准形式为：maxz=2x1+3x2+0x3+0x4+0x5x1+2x2+x3＝84x1+x4=164x2+x5＝12x1，x2，x3，x4，x5≥0然后要将其初始的单纯形表画出来：cj23000θiCBXBbx1x2x3x4x50x381210040x41640010-0x5120400

2、13cj-zj23000由初始单纯形表可以看出，x2为换入变量，而x5为换出变量；然后根据：aij=aij-aljalk*aiki≠laljalki=lbi=bi-aikalk*bli≠lblalki=l(也就是如果与主元素同行，则用现在的值除以主元素即可得到即将要填入的值，否则，就用现在的值减去与主元素构成矩形的边角上的值的乘积再除以主元素之后的值。例如：上面的第一行所对应的b值为8-(12*2)/4=2,故填入值应该为2。而θi则是由我们根据非基变量的检验数的大小，挑选出最大的那个，作为换入变量，然后用b的值除以该

3、换入变量所在的列的所有值，得到θi列的值。cj23000θiCBXBbx1x2x3x4x50x321010-1/220x4164001043x2301001/4-cj-zj2000-3/4由于在检验数中仍然存在大于等于0的数，而且P1，P5的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1，换入变量为x1，换出变量为x3，故得到的单纯形表如下：cj23000θiCBXBbx1x2x3x4x52x121010-1/2-0x4800-41243x2301001/412cj-zj00-201/4由于检

4、验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代(换入变量为x5，换出变量为x4：得到单纯形表如下：cj23000θiCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/80此时可以发现检验数中没有大于0的数，表明已经得到了最优解，所以最优解是：（4,2,0,0,4），故目标函数值z=2*4+2*3=141、合理利用线材问题，现在要做100套钢架，每套用长为2.9m，2.1m，和1.5m的钢各一根，已知原料长7.4m，问应如何下

5、料，使用的原材料最省；解：首先我们必须要清楚该问题的需要设立的变量是什么。我们分析一下问题，做100套钢架，需要2.9m长的钢100根，2.1m的钢100根，1.5m的钢100根。而一份原料长度是7.4m，它的截取的方法有多少种，我们可以用表格列举出来：长度/m下料根数截取方案123452.91122.12121.53132所用长度7.47.17.36.67.2剩余长度00.30.10.80.2求解的问题是关于如何去进行下料，使得原材料最省，也就是说如何搭配使用这些方案，使得剩余的总长度最少。由此，我们可以将目标函数和

6、约束条件表述出来：目标函数：minz=0.3x2+0.1x3+0.8x4+0.2x5约束条件x1+x2+2x3=1002x2+x4+2x5=1003x1+x3+3x4+2x5=100x1，x2，x3，x4，x5≥0首先可以写出线性方程组的矩阵形式：112000201230132发现不存在单位矩阵，所以要采用人造基的方式，也就是要添加人工变量：x6，x7，x8，那么线性方程组可以表示为：x1+x2+2x3+x6=1002x2+x4+2x5+x7=1003x1+x3+3x4+2x5+x8=100x1，x2，x3，x4，x5

7、，x6，x7，x8≥0，目标函数可以表示为：minz=0x1+0.3x2+0.1x3+0.8x4+0.2x5+Mx6+Mx7+Mx8转换为求目标最大化maxZ=-0x1-0.3x2-0.1x3-0.8x4-0.2x5-Mx6-Mx7-Mx8然后列出初始单纯形表：(注意，加入人工变量之后，它所对应的系数为-M，而非0)cj0-0.3-0.1-0.8-0.2-M-M-MθiCBXBbx1x2x3x4x5x6x7x8-Mx610011200100100-Mx710002012010--Mx810030132001100/3c

8、j-zj4M-0.3+3M-0.1+3M-0.8+4M-0.2+4M000换入变量为x1，换出变量为x8，得到单纯形表为：cj0-0.3-0.1-0.8-0.2-M-M-MθiCBXBbx1x2x3x4x5x6x7x8-Mx6200/3015/3-1-2/310-1/3200/3-Mx710002012010100/20x1100