單純形法例題

1、單純形法例題1、例1、目、目標(biāo)函數(shù)函數(shù)maxz=23xx約束條件：束條件：xx≤x≤x≤x，x≥解：首先要將約束條件化為標(biāo)準(zhǔn)形：由此可以看出我們需要加上三個(gè)松弛變量，x3，.得到的標(biāo)準(zhǔn)形式為：x4，x5，并且它們都大于等于0maxz=23000x1x2x3x4x5x12x2x3＝84x1x4=164x2x5＝12x1，x2，x3，x4，x5≥0然后要將其初始的單純形表畫(huà)出來(lái)：cj23000CBXBbx1x2x3x4x5i0x381210

2、040x416400100x5120[4]0013cjzj23000由初始單純形表可以看出，為換入變量，而為換出變量；然后根據(jù)：x2x5=aijaija?(≠l)a(=)bi=biaik?bl(≠l)b(=)(也就是如果與主元素同行，則用現(xiàn)在的值除以主元素即可得到即將要填入的值，否則，就用現(xiàn)在的值減去與主元素構(gòu)成矩形的邊角上的值的乘積再除以主元素之后的值。例如：上面的第一行所對(duì)應(yīng)的b值為8(122)4=2故填入值應(yīng)該為2。而則是i由我們

3、根據(jù)非基變量的檢驗(yàn)數(shù)的大小，挑選出最大的那個(gè)，作為換入變量，然后用b的值除以該換入變量所在的列的所有值，得到列的值。icj23000CBXBbx1x2x3x4x5i0x32[1]0101220x416400104首先可以寫(xiě)出線性方程組的矩陣形式：發(fā)現(xiàn)不存在單位矩陣，所以[112000201230132]要采用人造基的方式，也就是要添加人工變量：，那么線性方程組可以表x6，x7，x8示為：，目標(biāo)函數(shù)可以表示為：minz=0.30.1x1x

4、22x3x6=1002x2x42x5x7=1003x1x33x42x5x8=100x1，x2，x3，x4，x5，x6，x7，x8≥00x1x20.80.2Mx3x4x5x6Mx7Mx8轉(zhuǎn)換為求目標(biāo)最大化maxZ=0.30.10.80.2M0x1x2x3x4x5x6Mx7Mx8然后列出初始單純形表：(注意，加入人工變量之后，它所對(duì)應(yīng)的系數(shù)為M，而非0)cj00.30.10.80.2MMMCBXBbx1x2x3x4x5x6x7x8iMx61

5、0011200100100Mx710002012010Mx8100[3]01320011003cjzj4M0.33M0.13M0.84M0.24M000換入變量為，換出變量為，得到單純形表為：x1x8cj00.30.10.80.2MMMCBXBbx1x2x3x4x5x6x7x8iMx62003015312310132003Mx71000[2]01201010020x1100310131230013cjzj00.33M0.153M0.80