如何在Excel中建立并求解線性規(guī)劃模型

1、如何在Excel中建立并求解線性規(guī)劃模型 劉桂蓮摘要：數(shù)學(xué)中線性規(guī)劃問題的求解一直是很繁瑣的，功能強(qiáng)大的Excel軟件為我們提供了一種很好的求解方法，但這種方法卻很少被人了解。本文就如何在Excel中建立并求解線性規(guī)劃模型作了較詳盡的論述。關(guān)鍵詞：線性規(guī)劃 數(shù)學(xué)模型 電子表格模型 規(guī)劃求解 Excel線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，它的應(yīng)用已愈來愈深入到社會(huì)生產(chǎn)和經(jīng)濟(jì)活動(dòng)的各個(gè)領(lǐng)域。描述線性規(guī)劃問題的抽象的數(shù)學(xué)式子是線性規(guī)劃問題的數(shù)學(xué)模型。建立數(shù)學(xué)模型后，求解滿足約束條件的目標(biāo)函數(shù)的最優(yōu)解是解決線性規(guī)劃問題的關(guān)鍵。數(shù)學(xué)中常用的方法是圖解法和單純形法，而圖解法只適用于兩個(gè)變量的目標(biāo)函數(shù)，單純形法則計(jì)

2、算量相當(dāng)大，步驟煩瑣，容易出錯(cuò)。在Excel中建立電子表格模型，并利用它提供的“規(guī)劃求解”工具，能輕松快捷地求解模型的解。例如，某玻璃制品公司有三個(gè)工廠，公司目前決定停止不贏利產(chǎn)品的生產(chǎn)并撤出生產(chǎn)能力來生產(chǎn)兩種新開發(fā)的產(chǎn)品：玻璃門和雙把窗。估計(jì)三個(gè)工廠每周可用來生產(chǎn)新產(chǎn)品的時(shí)間分別為4小時(shí)、12小時(shí)、18小時(shí)，而每扇門需工廠1生產(chǎn)時(shí)間1個(gè)小時(shí)和工廠3生產(chǎn)時(shí)間3個(gè)小時(shí)，每扇窗需工廠2和工廠3生產(chǎn)時(shí)間各為2個(gè)小時(shí)，預(yù)測(cè)門的單位利潤是300元，窗的單位利潤是500元，問每周兩種新產(chǎn)品數(shù)量的哪種組合能使總利潤最大？這是一個(gè)典型的產(chǎn)品組合問題，現(xiàn)將問題中的有關(guān)數(shù)據(jù)列表如下：工廠生產(chǎn)每一個(gè)單位產(chǎn)品所需的時(shí)

3、間每周用得時(shí)間門窗11小時(shí)04小時(shí)202小時(shí)12小時(shí)33小時(shí)2小時(shí)18小時(shí)單位利潤300元500元問題的決策變量有兩個(gè)：每周門的生產(chǎn)數(shù)量和窗的生產(chǎn)數(shù)量，目標(biāo)是總利潤最大，需滿足的條件是：三個(gè)工廠每周用于生產(chǎn)新產(chǎn)品的時(shí)間每周可得時(shí)間每周門、窗的生產(chǎn)數(shù)量均0。設(shè)每周門的生產(chǎn)數(shù)量為x，窗的生產(chǎn)數(shù)量為y，則該問題的數(shù)學(xué)模型即為：最大化利潤P =300 x+500y，約束條件：x4，2y12，3x+2y18，x0和y0。將上表的有關(guān)數(shù)據(jù)輸入到Excel中，建立如圖1所示的電子表格模型。被輸入已知數(shù)據(jù)的單元格是數(shù)據(jù)單元格，如單元格C5：D8，G5：G7。決策變量（即兩種產(chǎn)品每周的生產(chǎn)量）放在單元格C9和D

4、9，正好定位在這些產(chǎn)品所在列的數(shù)據(jù)單元格下面，這種含有需要做出決策的單元格是可變單元格。單元格E5：E7是用來計(jì)算各個(gè)工廠每周的總生產(chǎn)時(shí)間，如單元格E5就是用C5：D5和C9：D9的對(duì)應(yīng)數(shù)值各自相乘再總加得到。Excel中有一個(gè)叫SUMPRODUCT的函數(shù)能對(duì)相等行數(shù)和相等列數(shù)的兩個(gè)變化范圍的單元格中的值乘積后進(jìn)行加和。被加和的每個(gè)值是對(duì)第一個(gè)變化范圍的一些值和對(duì)應(yīng)位置的第二個(gè)變化范圍的一些值的積。如E5=SUMPRODUCT(C5：D5，C9：D9)是把C5：D5變化范圍的每個(gè)值與C9：D9變化范圍中對(duì)應(yīng)的每個(gè)值相乘，然后各個(gè)積相加。同樣E6=SUMPRODUCT(C6：D6，C9：D9)，

5、E7=SUMPRODUCT(C7：D7，C9：D9)，E5、E6、E7 這些單元格的數(shù)值是依賴于可變單元格的，它們是輸出單元格。單元格F5、F6、F7中的“”符號(hào)表示它們左邊的總值不允許超過列G中的對(duì)應(yīng)數(shù)值，體現(xiàn)了函數(shù)的約束條件。目標(biāo)函數(shù)值（利潤）被放在E8單元格，正好在用來幫助計(jì)算總利潤的數(shù)據(jù)單元格右邊，與列E中的其中它的數(shù)據(jù)相像，它也是一些乘積的加和，E8=SUMPRODUCT(C8:D8，C9:D9)，E8是特殊的輸出單元格，是顯示目標(biāo)函數(shù)值的，是目標(biāo)單元格。在沒有計(jì)算之前，可變單元格和輸出單元格的數(shù)值均顯示為0。圖1：ABCDEFG1玻璃制品公司的產(chǎn)品組合問題23生產(chǎn)單位產(chǎn)品的時(shí)間4門

6、窗時(shí)間總數(shù)可得時(shí)間5工廠1100=46工廠2020=127工廠3320在工具菜單中選擇“規(guī)劃求解”，會(huì)彈出一個(gè)對(duì)話框。在對(duì)話框中，將E8鍵入目標(biāo)單元格，將C9：D9鍵入可變單元格，既然目標(biāo)是要最大化目標(biāo)單元格，還必須選中“最大值”（Max）2點(diǎn)擊對(duì)話框中的“添加”按紐（Add），彈出添加約束對(duì)話框，將約束條件具體化。左端輸入范圍E5：E7，右端輸入范圍G5：G7，中間的符號(hào)可選擇“點(diǎn)擊“選項(xiàng)”按鈕，在新彈出的對(duì)話框中，選中“采用線性模型”和“假定非負(fù)”選項(xiàng)，這就告訴了計(jì)算機(jī)要求解的問題是一個(gè)線性規(guī)劃問題以及非負(fù)約束，點(diǎn)擊“確定”再回到“規(guī)劃求解”對(duì)話框。4點(diǎn)擊 “求解”按鈕，計(jì)算機(jī)會(huì)在后臺(tái)開始

7、對(duì)問題進(jìn)行求解。幾秒鐘之后會(huì)顯示運(yùn)行結(jié)果，一般而言，它會(huì)顯示已經(jīng)找到一個(gè)最優(yōu)解。如果模型沒有可行解或沒有最優(yōu)解，對(duì)話框會(huì)顯示“規(guī)劃求解找不到可行解”。求解模型之后，最優(yōu)值就代替了可變單元格中的初始值，最優(yōu)解是每周2扇門和6扇窗，目標(biāo)單元格的對(duì)應(yīng)數(shù)值（每周總利潤）為3600元。求解的電子表格模型（圖2）如下：圖2ABCDEFG1玻璃制品公司的產(chǎn)品組合問題23生產(chǎn)單位產(chǎn)品的時(shí)間4門窗時(shí)間總數(shù)可得時(shí)間5工廠1102=46工廠20212=127工廠33218=188單位利潤30050036009結(jié)論26線性規(guī)劃問題的數(shù)學(xué)模型是描述實(shí)際問題的抽象的數(shù)學(xué)形式，它反映了客觀事物數(shù)量間的本質(zhì)規(guī)律。電子表格模型

8、和數(shù)學(xué)模型兩種形式是等價(jià)的。電子表格模型的建立不是唯一的，是非常靈活的，一個(gè)好的電子表格模型能直觀，簡(jiǎn)便地反映線性規(guī)劃問題的實(shí)質(zhì).這兩種形式導(dǎo)致了不同但互補(bǔ)的分析問題的方法，但用“規(guī)劃求解”工具會(huì)達(dá)到事半功倍的效果。再如：某廠家擁有三個(gè)生產(chǎn)嬰兒車的工廠，并運(yùn)往四個(gè)配送中心，三個(gè)工廠每月的產(chǎn)量分別是12、17、11個(gè)運(yùn)輸單位，同時(shí)每個(gè)配送中心每月要接受10個(gè)運(yùn)輸單位的貨物，從每一個(gè)工廠到每一個(gè)配送中心的單位運(yùn)輸成本如下所示：到各配送中心的單位運(yùn)輸成本（元）工廠1234150604020220901030330402010確定每月從每一個(gè)工廠之中要運(yùn)送多少運(yùn)輸單位的嬰兒車給相應(yīng)的配送中心的最佳方案

9、，使總的運(yùn)輸成本最小。用xij（i=1、2、3，j=1、2、3、4）表示從工廠運(yùn)送到配送中心j的貨物量，那么各工廠運(yùn)送到各配送中心的貨物量如下表：工廠1234工廠產(chǎn)量1X11X12X13X14122X21X22X23X24173X31X32X33X3411配送中心接受量10101010該線性規(guī)劃的數(shù)學(xué)模型是： 確定xij（i=1、2、3，j=1、2、3、4）的值，使目標(biāo)函數(shù)C成本=50 x11+60 x12+40 x13+20 x14+20 x21+90 x22+10 x23+30 x24+30 x31+40 x32+20 x33+10 x34有最小值。約束條件是：x11+x12+x13+x1

10、4=12x21+x22+x23+x24=17x31+x32+x33+x34=11x11+x21+x31=10 x12+x22+x32=10 x13+x23+x33=10 x14+x24+x34=10 xij0（i=1、2、3，j=1、2、3、4）電子表格模型如圖3：圖3ABCDEFGHI1嬰兒車的配送問題2到各配送中心的單位運(yùn)輸成本312344工廠1506040205工廠2209010306工廠33040201078運(yùn)送到各配送中心的單位數(shù)91234總量工廠產(chǎn)量10工廠100000=1211工廠200000=1712工廠300000=1113總量0000014=15中心接受量10101010模

11、型中的單元格C4：F6，C15：F15，以及I10：I12分別輸入了單位運(yùn)輸成本，中心接受量及工廠產(chǎn)量的數(shù)值，它們是數(shù)據(jù)單元格。12個(gè)決策變量（各工廠送到各分配中心的單位數(shù)）放在單元格C10：F12中，它們是可變單元格，起始值設(shè)置為0單元格C13：F13及G10：G12是輸出單元格C13=SUMPRODUCT(C10：C12),D13= SUMPRODUCT(D10：D12),E13= SUMPRODUCT(E10：E12),F13= SUMPRODUCT(E10：E12),G10=SUMPRODUCT(C10：F10), G11=SUMPRODUCT(C11：F11), G12=SUMPRO

12、DUCT(C12：F12), G13是目標(biāo)單元格（總成本），它正好是數(shù)據(jù)單元格C4：F6和可變單元格C10：F12對(duì)應(yīng)數(shù)值相乘再加和得到,即G13=SUMPRODUCT（C4：F6，C10：F12），模型中的等號(hào)體現(xiàn)了函數(shù)的約束。以上模型通過點(diǎn)擊“規(guī)劃求解”工具，因?yàn)槭亲钚』繕?biāo)單元格G13，所以選“最小值”（Min）；在“添加”約束里，添加“G10：G12=I10：I12”和“C13：F13=C15：F15”，仍然選“采用線性模型”和“假定非負(fù)”，得出如下結(jié)論：（圖4） 圖4ABCDEFGHI1嬰兒車的配送問題2到各配送中心的單位運(yùn)輸成本312344工廠1506040205工廠2209010306工廠33040201078運(yùn)送到各配送中心的單位數(shù)91234總量工廠產(chǎn)量10工廠10201012=1211工廠21007017=1712工廠3083011=1113總量1010101097014=15中心接受量10101010即工廠1運(yùn)送到配送中心2和配送中心4分別為2和10個(gè)單位；工廠2運(yùn)送到配送中心1和配送中心3分別為10和7個(gè)單位；工廠3運(yùn)送到配送中心2和配送中心3分別8和3個(gè)單位，這