單純形法例題

1、單純形法例題1、 例1、目標(biāo)函數(shù) max z=2x1+3x2約束條件：x1+2x284x1164x212x1，x10解：首先要將約束條件化為標(biāo)準(zhǔn)形：由此可以看出我們需要加上三個(gè)松弛變量，x3，x4，x5，并且它們都大于等于0.得到的標(biāo)準(zhǔn)形式為：max z=2x1+3x2+ 0x3+0x4+0x5x1+2x2+x384x1+x4=164x2+x512x1，x2，x3，x4，x50然后要將其初始的單純形表畫出來：cj23000iCBXBbx1x2x3x4x50x381210040x41640010-0x512040013cj-zj23000由初始單純形表可以看出，x2為換入變量，而x5為換出變量；

2、然后根據(jù)：aij=aij-aljalk*aikilaljalki=l bi=bi-aikalk*blilblalki=l (也就是如果與主元素同行，則用現(xiàn)在的值除以主元素即可得到即將要填入的值，否則，就用現(xiàn)在的值減去與主元素構(gòu)成矩形的邊角上的值的乘積再除以主元素之后的值。例如：上面的第一行所對應(yīng)的b值為8-(12*2)/4=2,故填入值應(yīng)該為2。而i則是由我們根據(jù)非基變量的檢驗(yàn)數(shù)的大小，挑選出最大的那個(gè)，作為換入變量，然后用b的值除以該換入變量所在的列的所有值，得到i列的值。cj23000iCBXBbx1x2x3x4x50x321010-1/220x4164001043x2301001/4-c

3、j-zj2000-3/4由于在檢驗(yàn)數(shù)中仍然存在大于等于0的數(shù)，而且P1，P5的坐標(biāo)中有正分量存在，所以需要繼續(xù)進(jìn)行迭代運(yùn)算。通過觀察可以看出主元素為1，換入變量為x1，換出變量為x3，故得到的單純形表如下：cj23000iCBXBbx1x2x3x4x52x121010-1/2-0x4800-41243x2301001/412cj-zj00-201/4由于檢驗(yàn)數(shù)中存在正數(shù)，且P5和P3中有正分量存在，所以需要繼續(xù)迭代(換入變量為x5，換出變量為x4：得到單純形表如下：cj23000iCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj

4、00-3/2-1/80此時(shí)可以發(fā)現(xiàn)檢驗(yàn)數(shù)中沒有大于0的數(shù)，表明已經(jīng)得到了最優(yōu)解，所以最優(yōu)解是：（4,2,0,0,4），故目標(biāo)函數(shù)值z=2*4+2*3=142、 合理利用線材問題，現(xiàn)在要做100套鋼架，每套用長為2.9m，2.1m，和1.5m的鋼各一根，已知原料長7.4m，問應(yīng)如何下料，使用的原材料最省；解：首先我們必須要清楚該問題的需要設(shè)立的變量是什么。我們分析一下問題，做100套鋼架，需要2.9m長的鋼100根，2.1m的鋼100根，1.5m的鋼100根。而一份原料長度是7.4m，它的截取的方法有多少種，我們可以用表格列舉出來：長度/m下料根數(shù)截取方案123452.91122.12121.5

5、3132所用長度7.47.17.36.67.2剩余長度00.30.10.80.2求解的問題是關(guān)于如何去進(jìn)行下料，使得原材料最省，也就是說如何搭配使用這些方案，使得剩余的總長度最少。由此，我們可以將目標(biāo)函數(shù)和約束條件表述出來：目標(biāo)函數(shù)：min z=0.3x2+0.1x3+0.8x4+0.2x5約束條件x1+x2+2x3=1002x2+x4+2x5=1003x1+x3+3x4+2x5=100x1，x2，x3，x4，x50首先可以寫出線性方程組的矩陣形式：112000201230132發(fā)現(xiàn)不存在單位矩陣，所以要采用人造基的方式，也就是要添加人工變量：x6，x7，x8，那么線性方程組可以表示為：x1+

6、x2+2x3+x6=1002x2+x4+2x5+x7=1003x1+x3+3x4+2x5+x8=100x1，x2，x3，x4，x5，x6，x7，x80，目標(biāo)函數(shù)可以表示為：min z=0x1+0.3x2+0.1x3+0.8x4+0.2x5+Mx6+Mx7+Mx8轉(zhuǎn)換為求目標(biāo)最大化max Z=-0x1-0.3x2-0.1x3-0.8x4-0.2x5-Mx6-Mx7-Mx8然后列出初始單純形表：(注意，加入人工變量之后，它所對應(yīng)的系數(shù)為-M，而非0)cj0-0.3-0.1-0.8-0.2-M-M-MiCBXBbx1x2x3x4x5x6x7x8-Mx610011200100100-Mx7100020

7、12010-Mx810030132001100/3cj-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-MiCBXBbx1x2x3x4x5x6x7x8-Mx6200/3015/3-1-2/310-1/3200/3-Mx710002012010100/20x1100/3101/312/3001/3-cj-zj0-0.3+3M-0.1+5/3M-0.8-0.2+4/3M00-4/3M 換入變量為x2，換出變量為x7，得到的單純形表為：cj0-0.3-0.1-0.8-0.2-M-M-

8、MiCBXBbx1x2x3x4x5x6x7x8-Mx650/3005/3-3/2-5/31-1/2-1/310-0.3x2500101/2101/20-0x1100/3101/312/3001/3-100cj-zj00-0.1+5/3M-0.65-3/2M0.1-5/3M00.15-3/2M-4/3M換入變量為x3，換出變量為x6，得到的單純形表為：cj0-0.3-0.1-0.8-0.2-M-M-MiCBXBbx1x2x3x4x5x6x7x8-0.1x310001-9/10-13/5-3/10-1/5-0.3x2500101/2101/200x13010013/101-1/51/102/5cj

9、-zj000-0.740-M+0.06-M+0.12-M-0.02所以，最優(yōu)解為：（30,50,10，0,0,0,0,0）。也就是說最優(yōu)的下料方案為：按照第一個(gè)方案下料30根，第二種方案下料50根，按照第三種方案下料10根。即需要90根原材料可以制造出100套鋼架。3、 某晝夜服務(wù)的公交線路每天各時(shí)間區(qū)段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下表：班次時(shí)間所需人數(shù)16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間區(qū)段一開始時(shí)上班，并連續(xù)工作八個(gè)小時(shí)，問該公交線路至少配備多

10、少名司機(jī)和乘務(wù)人員，列出這個(gè)問題的線性規(guī)劃模型。解： 目標(biāo)函數(shù)：min z=x1+x2+x3+x4+x5+x6約束條件:x1+x660x1+x270x2+x360x3+x450x4+x520x5+x630x1，x2，x3，x4，x5，x604、 利用單純形算法求解線性規(guī)劃問題目標(biāo)函數(shù)為：Max Z=4x1+3x2約束條件為：2x1+2x216005x1+2.5x22500x1400x1,x20 解：首先將線性方程組化為標(biāo)準(zhǔn)形式：添加松弛變量：x3，x4，x5，得到的方程式為：目標(biāo)函數(shù)：Max Z=4x1+3x2+0x3+0x4+0x5約束條件為：2x1+2x2+ x3=16005x1+2.5x

11、2+x4=2500x1+x5 =400x1, x2,x3, x4,x50 接著將初始單純形表列出：cj43000iCBXBbx1x2x3x4x50x31600221008000x4250052.50105000x540010001400cj-zj43000由上表可以看出，x1為換入變量，而x5為換出變量。然后根據(jù)變換公式可以得到變換之后的單純形表如下：cj43000iCBXBbx1x2x3x4x50x38000210-24000x450002.501-52004x1400100010cj-zj0300-4由上表可以看出，換入變量為x2，換出變量為x4，單純形表如下：cj43000iCBXBbx1x2x3x4x50x3400001-4/522003x22000102/5-2-4x140010001400cj-zj000-6