單純形法例題

1、單純形法例題1、 例1、目標函數(shù) max z=2x1+3x2約束條件：x1+2x284x1164x212x1，x10解：首先要將約束條件化為標準形：由此可以看出我們需要加上三個松弛變量，x3，x4，x5，并且它們都大于等于0.得到的標準形式為：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)在的值減去與主元素構成矩形的邊角上的值的乘積再除以主元素之后的值。例如：上面的第一行所對應的b值為8-(12*2)/4=2,故填入值應該為2。而i則是由我們根據(jù)非基變量的檢驗數(shù)的大小，挑選出最大的那個，作為換入變量，然后用b的值除以該換入變量所在的列的所有值，得到i列的值。cj23000iCBXBbx1x2x3x4x50x321010-1/220x4164001043x2301001/4-c

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

4、00-3/2-1/80此時可以發(fā)現(xiàn)檢驗數(shù)中沒有大于0的數(shù)，表明已經得到了最優(yōu)解，所以最優(yōu)解是：（4,2,0,0,4），故目標函數(shù)值z=2*4+2*3=142、 合理利用線材問題，現(xiàn)在要做100套鋼架，每套用長為2.9m，2.1m，和1.5m的鋼各一根，已知原料長7.4m，問應如何下料，使用的原材料最?。唤猓菏紫任覀儽仨氁宄搯栴}的需要設立的變量是什么。我們分析一下問題，做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求解的問題是關于如何去進行下料，使得原材料最省，也就是說如何搭配使用這些方案，使得剩余的總長度最少。由此，我們可以將目標函數(shù)和約束條件表述出來：目標函數(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，目標函數(shù)可以表示為：min z=0x1+0.3x2+0.1x3+0.8x4+0.2x5+Mx6+Mx7+Mx8轉換為求目標最大化max Z=-0x1-0.3x2-0.1x3-0.8x4-0.2x5-Mx6-Mx7-Mx8然后列出初始單純形表：(注意，加入人工變量之后，它所對應的系數(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)的下料方案為：按照第一個方案下料30根，第二種方案下料50根，按照第三種方案下料10根。即需要90根原材料可以制造出100套鋼架。3、 某晝夜服務的公交線路每天各時間區(qū)段內所需司機和乘務人員數(shù)如下表：班次時間所需人數(shù)16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030設司機和乘務人員分別在各時間區(qū)段一開始時上班，并連續(xù)工作八個小時，問該公交線路至少配備多

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