單純形法例題

1、單純形法例題時間:2021.03.01創(chuàng)作：歐陽語2、例 1、目標函數(shù) maxz=2xi+3x2fXt + 2X2 w 8、4xi W 164x2 W 12約束條件：X, Xi M 0解：首先要將約束條件化為標準形：由此可以看出我們需要加上三個松弛變量,X3 X4X5.并且它們都大于等于0.得到的標準形式為:maxz=2xi+3X2+0x3+0x4+0xs然后要將其初始的單純形表畫出來:ci23000qCb&bX1x2x3x4x50x38120040X41640010-0X512000132L±00由初始單純形表可以看出2為換入變量，而勺為換出變量；然后根據(jù):（也就是如果與主

2、元素同行”則用現(xiàn)在的值除以主元素 即可得到即將要填入的值，否則，就用現(xiàn)在的值減去 與主元素構成矩形的邊角上的值的乘積再除以主元素 之后的值。例如：上面的第一行所對應的b值為 8(12*2)/4二2,故填入值應該為2。而則是由我們根據(jù) 非基變量的檢驗數(shù)的大小，挑選出最大的那個，作為 換入變量，然后用b的值除以該換入變量所在的列的 所有值,得到咧的值。ci23000%CBXBbX1x2x3X4x50x32KB010-1/220x4164001043x2301001/4-Cj-Zj2000-3/4由于在檢驗數(shù)中仍然存在大于等于0的數(shù)，而且P1 ,P5的坐標中有正分量存在,所以需要繼續(xù)進行迭代運通過觀

3、察可以看出主元素為1,換入變量為勺，換出變量為勺，故得到的單純形表如下:ci23000CbXbbXx2x3X4x52X121010-1/2-0X48004m43X2301001/41200201/4由于檢驗數(shù)中存在正數(shù)，且P5和P3中有正分量存在,所以需要繼續(xù)迭代(換入變量為勺，換出變量為":得到單純形表如下：ci230000、CbXbbXx2x3X4x52X11001/40040021/213X22011/2-1/80ci_zi003/2-1/80此時可以發(fā)現(xiàn)檢驗數(shù)中沒有大于0的數(shù)，表明已經(jīng)得到了最優(yōu)解,所以最優(yōu)解是:(420Q4 ),故目標函數(shù)值 z=2*4+2*3二 143、合

4、理利用線材問題,現(xiàn)在要做100套鋼架,每套用長 為2.9m , 2.1m ,和1.5m的鋼各一根，已知原料長 7.4m z問應如何下料，使用的原材料最??；解：首先我們必須要清楚該問題的需要設立的變量是 什么。我們分析一下問題,做100套鋼架，需要2.9m 長的鋼100根，2.1m的鋼100根，1.5m的鋼100 根。而一份原料長度是7.4m ”它的截取的方法有多少 種,我們可以用表格列舉出來：長度/m下料根數(shù)截取方案123452.91122.12121.53132所用長度7.47.17.36.67.2剩余長度00.30.10.80.2求解的問題是關于如何去進行下料,使得原材料最省, 也就是說如

5、何搭配使用這些方案，使得剩余的總長度 最少。由此，我們可以將目標函數(shù)和約束條件表述出 來：目標函數(shù)：minz=0.3x2+0.1x3+0.8x4+0.2x5X + X2 + 2X3 = 100約束條件2x2 + X4 + 2x5 = 10° 3xi + X3 + 3x4 + 2x5 = 100 x2. x3, x4> X5 M 0首先可以寫出線性方程組的矩陣形式:現(xiàn)不存在單位矩陣”所以要采用人造基的方式”也就是要添加人工變量:X® X7. X8 z那么線性方程組可以表示為,目標函數(shù)可以表示X + X2 + 2X3 + X6 二 1002x2 + X4 + 2x5 +

6、X7 二 1003X1 + X3 + 3X4 + 2X5 + X8 二 100xb x2, X3, X4. x5, x6, x7. X8 M 0為:minz=°xi+0.3x2+0.1x3+0.8x4+0.2x5+Mx6+ Mx8轉換為求目標最大化maxZ= " Oxi 03%2 - 0.1x3 * 0.8x4 ° 0.2x5 Mx6 Mx7- Mxs然后列出初始單純形表：（注意，加入人工變量之后,它所對應的系數(shù)為而非0）q0-0.3-0.1-0.8-0.2MMMCBXbbXx2x3X4X5x6X7X8MX610011200100100MX710002012010

7、-Mx8羅R0132001100/3Cjp4M-0.3+3-0.1+3M-0.8+4M-0.2+4M000換入變量為勺，換出變量為七，得到單純形表為：ci0-0.3-0.108-0.2-M-M-MqCbXbbX1x2x3x4x5x6x?x8Mx6200/3015/3-1-2/310/3200/3MX71000012010100/20X1100/3101/312/3001/3-CjZj0-0.3+3M-0.1+5/3M0.8-0.2 +4/3M004/3M換入變量為迄，換出變量為><7 ,得到的單純形表為：換入變量為勺，換出變量為心z得到的單純形表為：ci0-0.3-0.1-0.8-

8、0.2-MCbXbbX1x2x3x4x5x6x?x80.1x310001-9/103/5-3/10J/50.3x2500101/2101/200X13010013/101-1/51/102/5CjT000-0.740-M +0.06-M +0.12-M-0.02所以，最優(yōu)解為：（30,50,10,0Q0Q0 也就是說最 優(yōu)的下料方案為：按照第一個方案下料30根，第二種 方案下料50根，按照第三種方案下料10根。即需要 90根原材料可以制造出100套鋼架。4、某晝夜服務的公交線路每天各時間區(qū)段內所需司機和歐陽語創(chuàng)編乘務人員數(shù)如下表:班次時間所需人數(shù)16:00-10:0060210:00-14:0

9、070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030設司機和乘務人員分別在各時間區(qū)段一開始時上班， 并連續(xù)工作八個小時，問該公交線路至少配備多少名 司機和乘務人員，列出這個問題的線性規(guī)劃模型。解：目標函數(shù):minz=x1 + x2 + x3 + x4 + x5 + x6X + X6 M 60Xi +X2 三 70X2 + X3 M 60x3 + x450x4 + x520X5+X6 M 30約束條件:x2. x3. x4. x5. x6 A 05、利用單純形算法求解線性規(guī)劃問題目標函數(shù)為：MaxZ=4xi+3x22x1 + 2x2 W

10、 16005xt + 2.5x2 W 2500Xi w 400約束條件為：xvx2 > 0解：首先將線性方程組化為標準形式:添加松弛變量:X3 , X. X5 ,得到的方程式為：目標函數(shù)：Max Z=4xi+3x2+0x3+0x4+0x52xt + 2x? + X3 = 16005X + 2.5x2 + x4 = 2500約束條件為:Xj + x5 = 400xvx2,x3, x4,x5 > 0接看將初始單純形表列出:Cj43C0c0、CbXbbX1x2X3X4X50X31600221008000X4250052.50105000X5400I1J000140043000由上表可以看出，"為換入變量，而><5為換出變量。然 后根據(jù)變換公式可以得到變換之后的單純形表如下：43C00CbXbbX1x2X3X4X50X38000210-24000X4500012501-52004X1400100010ci_zj03004由上表可以看出，換入變量為邊，換出變量為"，單純 形表如下：Cj4300cCBXbbX1X2;<50x3400001-4/52003x22000102/52-4X140010001400000-6/5箜由上表可以看出，換入變量為§ ,換出