線性規(guī)劃問題的兩種求解方式

1、線性規(guī)劃問題的兩種求解方式線性規(guī)劃是運籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個重 要分支，它是輔助人們進行科學(xué)管理的一種數(shù)學(xué)方法。線性規(guī)劃所研究的是：在 一定條件下，合理安排人力物力等資源，使經(jīng)濟效果達到最好。一般地，求線性 目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題。解決線性規(guī)劃問題常用的方法是圖解法和單純性法，而圖解法簡單方便，但 只適用于二維的線性規(guī)劃問題，單純性法的優(yōu)點是可以適用于所有的線性規(guī)劃問 題，缺點是單純形法中涉及大量不同的算法，為了針對不同的線性規(guī)劃問題，計 算量大，復(fù)雜繁瑣。在這個計算機高速發(fā)展的階段，利用Excel建立電子表格模 型，并

2、利用它提供的“規(guī)劃求解”工具，能輕松快捷地求解線性模型的解。無論利用哪種方法進行求解線性規(guī)劃問題，首先都需要對線性規(guī)劃問題建立 數(shù)學(xué)模型，確定目標(biāo)函數(shù)和相應(yīng)的約束條件，進而進行求解。從實際問題中建立 數(shù)學(xué)模型一般有以下三個步驟；1、根據(jù)所求目標(biāo)的影響因素找到?jīng)Q策變量；2、由決策變量和所求目標(biāo)的函數(shù)關(guān)系確定目標(biāo)函數(shù)；3、由決策變量所受的限制條件確定決策變量所要滿足的約束條件。以下是分別利用單純形法和Excel表格中的“規(guī)劃求解”兩種方法對例題進 行求解的過程。例題：某工廠在計劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所 需的設(shè)備臺時分別為1臺時、2臺時，所需原材料A分別為4單位、0單位，

3、所 需原材料B分別為0單位、4單位，工廠中設(shè)備運轉(zhuǎn)最多臺時為8臺時，原材料 A、B的總量分別為16單位、12單位。每生產(chǎn)出I、II產(chǎn)品所獲得的利潤為2和 3,問I、II兩種產(chǎn)品的生產(chǎn)數(shù)量的哪種組合能使總利潤最大？這是一個典型的產(chǎn)品組合問題，現(xiàn)將問題中的有關(guān)數(shù)據(jù)列表1-1如下：表1-1III限量設(shè)備128臺時原材料A4016單位原材料B0412單位所獲利潤23首先對例題建立數(shù)學(xué)模型。問題的決策變量有兩個：產(chǎn)品I的生產(chǎn)數(shù)量和產(chǎn)品II的生產(chǎn)數(shù)量；目標(biāo)是總利潤最大；需滿足的條件是：(1)兩種產(chǎn)品使用設(shè)備的臺時 =臺時限量值(2)生 產(chǎn)兩種產(chǎn)品使用原材料A、B的數(shù)量 =0。一設(shè)x1、x2分別表示產(chǎn)品I、

4、II的產(chǎn)量，由于資源限量的限制，可用不等式表示資源總量的約束條件：x1+2 x2 8 ； 4 x1 16 ； 4 x2 12 ；該工廠的目標(biāo)是在不超過所有資源限量的條件下，如何確定產(chǎn)量x1、x2以得到最大的利潤。若用z表示利潤，這時z=2x1+3x2綜合上述，該問題可用數(shù)學(xué)模型表示為：目標(biāo)函數(shù) max z=2x1+3x2滿足約束條件：f x1+2 x2 84 x1 16| 4 x2 0利用單純形法進行求解，則例題的標(biāo)準型為：maxZ=2x 1+3x2+0 x3+0 x4+0 x5x1+2 x2+x3=84 x1+x4T64 x2+x5=12x. 0 j=1,2,5(1)根據(jù)標(biāo)準型，取松弛變量x

5、3,x4,x5為基變量，它對應(yīng)的單位矩陣為基，這就得 到初始基可行解X(0)=(0,0,8,16,12)t將有關(guān)數(shù)字填入表中，得到初始單純形表，見表1-2表1-2c230000CbXbbx1x2x3x4x50 x381210040 x41640010一0X512040013。23000(2)因檢驗數(shù)都大于零，且須找出換入換出變量，繼續(xù)進行計算;Max(。1,。2)=max(2,3)=3，對應(yīng)的 變量x2為換入變量，計算。=min(8/2,-,12/4)=3所以它所在行對應(yīng)的x5為換出變量。x2所在列和x5所在行的交叉處4稱為主 元素。(4)以4為主元素進行初等行變換，使P2變換為(0,0,1)

6、 t，在XB列中將x2 替換x5，于是得到新表1 -3。c230000CbXbbx1x2x3x4x50 x321010-1/220 x4164001043x.301001/4一。2000-3/4b 列的數(shù)字是 x3=2, x4 =16, x2=3于是得到新的基可行解X(1)=(0,3,2,16,0)t,目標(biāo)函數(shù)的取值z=9(5)檢查表1-3的所有。，這時有。j2 ；說明x1應(yīng)為換入變量。重復(fù)(2)(4)的計 算步驟，得表1-4。c230000CbXbbx1x2x3x4x52x121010-1/2一0 x4800-41243x2301001/412。00-201/4c230000CBXbbx1x

7、2x3x4x52x141001/400 x5400-21/213x22011/2-1/80000-3/2-1/80(4)表1-4最后一行的所有檢驗數(shù)已為負數(shù)或零，這表示目標(biāo)函數(shù)值已不可能再 增大，于是得到最優(yōu)解X*=X(3)=(4,2,0,0,4)t目標(biāo)函數(shù)值z=14二、利用Excel表格進行線性規(guī)劃求解將單純形表中的有關(guān)數(shù)據(jù)輸入到Excel中，建立如圖1所示的電子表格模型。 被輸入已知數(shù)據(jù)的單元格是數(shù)據(jù)單元格，如單元格C5:D8,G5:G7。決策變量(即 兩種產(chǎn)品每周的生產(chǎn)量)放在單元格C9和D9，正好定位在這些產(chǎn)品所在列的數(shù) 據(jù)單元格下面，這種含有需要做出決策的單元格是可變單元格。單元格E

8、5:E7 是用來計算各個工廠每周的總生產(chǎn)時間，如單元格E5就是用C5:D5和C9:D9的 對應(yīng)數(shù)值各自相乘再總加得到。Excel中有一個叫SUM PRODUC I的函數(shù)能對相 等行數(shù)和相等列數(shù)的兩個變化范圍的單元格中的值乘積后進行加和。被加和的每 個值是對每一個變化范圍的一些值和對應(yīng)位置的第二個變化范圍的一些值的積。 如E5=SUM PRODUCT(C5:D5,C9:D9)是把C5:D5變化范圍的每個值與C9:D9變 化范圍中對應(yīng)的每個值相乘，然后各個積相加。同樣E6=SUM PRODUCT(C6:D6,C9:D9)，E7=SUM PRODU CT(C7:D7,C9:D9)，E5、E6、E7這

9、些單元格的數(shù)值是依賴于可變單元格的，它們是輸出單元格。單 元格F5、F6、F7中的“=”符號表示它們左邊的總值不允許超過列G中的對應(yīng) 數(shù)值，體現(xiàn)了函數(shù)的約束條件。目標(biāo)函數(shù)值(利潤)被放在E8單元格，正好在用 來幫助計算總利潤的數(shù)據(jù)單元格右邊，與列E中的其它的數(shù)據(jù)相象，它也是一 些乘積的加和，E8=SUM PRODUCT(C8 : D8,C9 : D9)，E8是特殊的輸出單元格，是顯示目標(biāo)函數(shù)值的，是目標(biāo)單元格。在沒有計算之 前，可變單元格和輸出單元格的數(shù)值均顯示為0。圖1ABCDEFG1234III使用資源量資源總量5設(shè)備120=86A400=167B040=128所荻利潤2309結(jié)論ouEx

10、cel中有一個叫“規(guī)劃求解”的工具，能快速求解線性規(guī)劃問題，步驟如 下：1在工具菜單中選擇“規(guī)劃求解”，會彈出一個對話框。在對話框中，將 E8鍵入目標(biāo)單元格，將C9:D9鍵入可變單元格，既然目標(biāo)是要最大化目標(biāo)單元 格，還必須選中“最大值”。2點擊對話框中的“添加”按紐，彈出添加約束對話框，將約束條件具體 化。左端輸入范圍E5:E7，右端輸入范圍G5:G7，中間的符號可選擇“=”。如 果還要添加更多的函數(shù)約束就再點擊“添加”按鈕以彈出一個新的添加約束對話 框，在這個例子中沒有其它約束了。下一步只要點擊“確定”按鈕回到“規(guī)劃求 解”對話框。3點擊“選項”按鈕，在新彈出的對話框中，選中“采用線性模型

11、”和“假 定非負”選項，這就告訴了計算機要求解的問題是一個線性規(guī)劃問題以及非負約 束，點擊“確定”再回到“規(guī)劃求解”對話框。4點擊“求解”按鈕，計算機會在后臺開始對問題進行求解。幾秒鐘之后 會顯示運行結(jié)果，一般而言，它會顯示已經(jīng)找到一個最優(yōu)解。如果模型沒有可行 解或沒有最優(yōu)解，對話框會顯示“規(guī)劃求解找不到可行解”。求解模型之后，最 優(yōu)值就代替了可變單元格中的初始值，最優(yōu)解是每周4個I產(chǎn)品和2個II產(chǎn)品， 目標(biāo)單元格的對應(yīng)數(shù)值（最大利潤）為14。求解的電子表格模型（圖2）如下：圖2ABCDEG1234III使用資源量資源總量5設(shè)備128=86A4016=167B048=128所獲利潤23149結(jié)論42線性規(guī)劃問題的數(shù)學(xué)模型是描述實際問題的抽象的數(shù)學(xué)形式，它反映了客觀 事物數(shù)量間的本質(zhì)規(guī)律。電子表格模型和數(shù)學(xué)模型兩種形式是等價的。電子表格 模型的建