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

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

2、則計(jì)算量相當(dāng)大，步驟煩瑣，容易出錯(cuò)。在Excel中建立電子表格模型，并利用它提供的“規(guī)劃求解”工具，能輕松快捷地求解模型的解。例如，某玻璃制品公司有三個(gè)工廠，公司目前決定停止不贏利產(chǎn)品的生產(chǎn)并 撤出生產(chǎn)能力來(lái)生產(chǎn)兩種新開發(fā)的產(chǎn)品：玻璃門和雙把窗。估計(jì)三個(gè)工廠每周可 用來(lái)生產(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è)門的單位利潤(rùn)是300元，窗的單位利潤(rùn)是500元，問(wèn)每周兩 種新產(chǎn)品數(shù)量的哪種組合能使總利潤(rùn)最大？這是一個(gè)典型的產(chǎn)品組合問(wèn)題，現(xiàn)將問(wèn)題中的有關(guān)數(shù)據(jù)列表如下:工廠生產(chǎn)每一個(gè)

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

4、在單元格C9和D9，正好定位在這些產(chǎn)品所在列的數(shù)據(jù)單元格下面，這種含有需要做出決策的單元格是可變單元格。單元格E5：E7是用來(lái)計(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=SUMPR

5、ODUCT(C6 : D6, C9： D9)，E7=SUMPRODUCT(C7 : D7, C9： D9)，E5、E6、E7這些單元格的數(shù)值是依賴于可變單元格的，它們是輸出單元格。單 元格F5、F6、F7中的“W”符號(hào)表示它們左邊的總值不允許超過(guò)列G中的對(duì)應(yīng)數(shù)值，體現(xiàn)了函數(shù)的約束條件。目標(biāo)函數(shù)值（利潤(rùn)）被放在E8單元格，正好在用來(lái)幫助計(jì)算總利潤(rùn)的數(shù)據(jù)單元格右邊， 與列E中的其中它的數(shù)據(jù)相像，它也是 一些乘積的加和，E8=SUMPRODUCT（C8：D89：D9），E8是特殊的輸出單元格，是 顯示目標(biāo)函數(shù)值的，是目標(biāo)單元格。在沒(méi)有計(jì)算之前，可變單元格和輸出單元格 的數(shù)值均顯示為0。圖1：ABCD

6、EFG1玻璃制品公司的產(chǎn)品組合問(wèn)題23生產(chǎn)單位產(chǎn)品的時(shí)間4門窗時(shí)間總數(shù)可得時(shí)間5工廠1100=46工廠2020=127工廠3320=188單位利潤(rùn)30050009結(jié)論00Excel中有一個(gè)叫“規(guī)劃求解”的工具，能快速求解線性規(guī)劃問(wèn)題，步驟如下：1在工具菜單中選擇“規(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)可選擇 “=”。如果還要添加

7、更多的函數(shù)約束就再點(diǎn)擊“添加”按鈕以彈出一個(gè)新的添 加約束對(duì)話框，在這個(gè)例子中沒(méi)有其它約束了。下一步只要點(diǎn)擊“確定”按鈕回 到“規(guī)劃求解”對(duì)話框。3點(diǎn)擊“選項(xiàng)”按鈕，在新彈出的對(duì)話框中，選中“采用線性模型”和“假 定非負(fù)”選項(xiàng)，這就告訴了計(jì)算機(jī)要求解的問(wèn)題是一個(gè)線性規(guī)劃問(wèn)題以及非負(fù)約 束，點(diǎn)擊“確定”再回到“規(guī)劃求解”對(duì)話框。4點(diǎn)擊“求解”按鈕，計(jì)算機(jī)會(huì)在后臺(tái)開始對(duì)問(wèn)題進(jìn)行求解。幾秒鐘之后 會(huì)顯示運(yùn)行結(jié)果，一般而言，它會(huì)顯示已經(jīng)找到一個(gè)最優(yōu)解。如果模型沒(méi)有可行 解或沒(méi)有最優(yōu)解，對(duì)話框會(huì)顯示“規(guī)劃求解找不到可行解”。求解模型之后，最優(yōu)值就代替了可變單元格中的初始值，最優(yōu)解是每周2扇門和6扇窗，目

8、標(biāo)單元格的對(duì)應(yīng)數(shù)值（每周總利潤(rùn)）為 3600元。求解的電子表格模型（圖2）如下：ABCDEFG1玻璃制品公司的產(chǎn)品組合問(wèn)題23生產(chǎn)單位產(chǎn)品的時(shí)間4門窗時(shí)間總數(shù)可得時(shí)間5工廠1102=46工廠20212=127工廠332180 (i=1、2、3, j=1、2、3、4)電子表格模型如圖3:圖3ABCDEFGHI1嬰兒車的配送問(wèn)題2到各配送中心的單位運(yùn)輸成本312344工廠1506040205工廠2209010306工廠33040201078運(yùn)送到各配送中心的單位數(shù)91234總量工廠產(chǎn)量10工廠100000=1211工廠200000=1712工廠300000=1113總量0000014=15中心接受

9、量10101010模型中的單元格C4: F6, C15: F15,以及110: 112分別輸入了單位運(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),G1O=SUMPRODUCT(C1O :F10),G

10、11=SUMPRODUCT(C11: F11), G12=SUMPRODUCT(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ù)的約束。以上模型通過(guò)點(diǎn)擊“規(guī)劃求解”工具，因?yàn)槭亲钚』繕?biāo)單元格 G13,所以 選“最小值”(Min)；在“添加”約束里，添加“ G10: G12=I10: I12 ”和“ C13: F13=C15: F15”，仍然選“采用線性模型”和“假定非負(fù)”，得出如下結(jié)論：(圖 4)ABCDEFGH

11、I1嬰兒車的配送問(wèn)題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è)單位，這樣總的運(yùn)輸成本最低，最低成本是 970元。需要注意的是：用電子表格模型表述函數(shù)約束條件時(shí)，往往用到輸出單元格， 而輸出單元格必須使用 SUMPROD