單純形法例題

單純形法例題例1、目標函數maxz=2x1+3約束條件：x解：首先要將約束條件化為標準形：由此可以看出我們需要加上三個松弛變量，x3maxz=2x1+3x2+0x3+0xx然后要將其初始的單純形表畫出來：c23000θCXbxxxxx0x81210040x1640010-0x12040013c23000由初始單純形表可以看出，x2為換入變量，而xaij=bi(也就是如果與主元素同行，則用現在的值除以主元素即可得到即將要填入的值，否則，就用現在的值減去與主元素構成矩形的邊角上的值的乘積再除以主元素之后的值。例如：上面的第一行所對應的b值為8-(12*2)/4=2,故填入值應該為2。而θi則是由我們根據非基變量的檢驗數的大小，挑選出最大的那個，作為換入變量，然后用b的值除以該換入變量所在的列的所有值，得到θc23000θCXbxxxxx0x21010-1/220x164001043x301001/4-c2000-3/4由于在檢驗數中仍然存在大于等于0的數，而且P1，P5的坐標中有正分量存在，所以需要繼續(xù)進行迭代運算。通過觀察可以看出主元素為1，換入變量為x1，換出變量為xc23000θCXbxxxxx2x21010-1/2-0x800-41243x301001/412c00-201/4由于檢驗數中存在正數，且P5和P3中有正分量存在，所以需要繼續(xù)迭代(換入變量為x5，換出變量為xc23000θCXbxxxxx2x41001/400x400-21/213x2011/2-1/80c00-3/2-1/80此時可以發(fā)現檢驗數中沒有大于0的數，表明已經得到了最優(yōu)解，所以最優(yōu)解是：（4,2,0,0,4），故目標函數值z=2*4+2*3=14合理利用線材問題，現在要做100套鋼架，每套用長為2.9m，2.1m，和1.5m的鋼各一根，已知原料長7.4m，問應如何下料，使用的原材料最??；解：首先我們必須要清楚該問題的需要設立的變量是什么。我們分析一下問題，做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求解的問題是關于如何去進行下料，使得原材料最省，也就是說如何搭配使用這些方案，使得剩余的總長度最少。由此，我們可以將目標函數和約束條件表述出來：目標函數：minz=0.3x2+0.1x3+0.8x4約束條件xCXbxxxxxxxx-Mx50/3005/3-3/2-5/31-1/2-1/310-0.3x500101/2101/20-0x100/3101/312/3001/3-100c00-0.1+5/3M-0.65-3/2M0.1-5/3M00.15-3/2M-4/3M換入變量為x3，換出變量為xc0-0.3-0.1-0.8-0.2-M-M-MθCXbxxxxxxxx-0.1x10001-9/10-13/5-3/10-1/5-0.3x500101/2101/200x3010013/101-1/51/102/5c000-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套鋼架。某晝夜服務的公交線路每天各時間區(qū)段內所需司機和乘務人員數如下表：班次時間所需人數16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030設司機和乘務人員分別在各時間區(qū)段一開始時上班，并連續(xù)工作八個小時，問該公交線路至少配備多少名司機和乘務人員，列出這個問題的線性規(guī)劃模型。解：目標函數：minz=x約束條件:x利用單純形算法求解線性規(guī)劃問題目標函數為：MaxZ=4x1+3約束條件為：2解：首先將線性方程組化為標準形式：添加松弛變量：x3，x4，目標函數：MaxZ=4x1+3x2+0x3+0x約束條件為：2接著將初始單純形表列出：c43000θCXbxxxxx0x1600221008000x250052.50105000x40010001400c43000由上表可以看出，x1為換入變量，而xc43000θCXbxxxxx0x8000210-24000x50002.501-52004x400100010c0300-4由上表可以看出，換入變量為x2，換出變量為xc43000θCXbxxxxx0x400001-4/522003x2000102/5-2-4x40010001400c000-6/52 由上表可以看出，換入變量為x5，換出變量為得到的單純形表如下：c43000θCXbxxxxx0