用MA TLAB解決規(guī)劃問題的通用方法

趙喜清,劉守義,韓振芳

(1.河北北方學(xué)院信息科學(xué)與工程學(xué)院,河北張家口075000;2.河北北方學(xué)院學(xué)報(bào)編輯部,河北張家口075000;3.河北北方學(xué)院理學(xué)院,河北張家口075000)

利用Excel提供的規(guī)劃求解法可以解運(yùn)籌學(xué)中的許多問題,方法簡(jiǎn)捷、精度較高[1],但對(duì)于有無窮多最優(yōu)解的問題,該方法只能給出其中的一個(gè)解.另外,Excel規(guī)劃求解將使用“在插入”試用值的迭代數(shù)值的方法,涉及可變單元格和觀察由約束單元并獲得最佳的單元格計(jì)算結(jié)果.每次試驗(yàn)稱為一個(gè)“迭代”,Microsoft Excel規(guī)劃求解將執(zhí)行廣泛的觀察所得的輸出的分析和輸入,這樣的純“試驗(yàn)和錯(cuò)誤”方法將需要一個(gè)非常長(zhǎng)的時(shí)間[2](尤其對(duì)于問題涉及許多可變單元格和約束).

1 EXCEL規(guī)劃求解的過程

EXCEL規(guī)劃求解步驟：

1)加載“規(guī)劃求解”宏、引用“規(guī)劃求解”工具.

2)設(shè)置“規(guī)劃求解參數(shù)”.

將“設(shè)置目標(biāo)單元格”指向設(shè)定目標(biāo)利潤(rùn)值的單元格;將“可變單元格”即指向所設(shè)定的“產(chǎn)量值”(未知數(shù))的單元格;將上述的資源約束條件,用 EXCEL語言引入“約束”;設(shè)置規(guī)劃求解“選項(xiàng)”參數(shù),根據(jù)實(shí)際情況,選擇“采用線性模型”和“假定非負(fù)”兩個(gè)選擇項(xiàng).

3)求解參數(shù)設(shè)定后,由EXCEL自動(dòng)求解,得出最終結(jié)果.

以“合理配餐問題”為例,說明 EXCEL規(guī)劃求解的過程.

合理配餐問題是非常復(fù)雜的問題,涉及的因素很多,如一公司飼養(yǎng)實(shí)驗(yàn)用的動(dòng)物以供出售,已知這些動(dòng)物的生長(zhǎng)對(duì)飼料中的三種營(yíng)養(yǎng)成分蛋白質(zhì),礦物質(zhì),維生素特別敏感,每個(gè)動(dòng)物每天至少需要蛋白質(zhì)70 g,礦物質(zhì)3 g,維生素10 mg,該公司能買到五種不同的飼料,每種飼料1 kg所含的營(yíng)養(yǎng)成分及每種飼料成本如表1所示：

在分析了約束條件后,確定目標(biāo)函數(shù),建立數(shù)學(xué)模型,以下為EXCEL求解過程 (見圖2)：

表1 一公司飼養(yǎng)動(dòng)物營(yíng)養(yǎng)成分

表2 EXCEL求解過程

從上求解過程可以得到最優(yōu)解為：

X1=2.84286E-12,X2=0,X3=1.77636E-15,X4=39.74358943,X5=25.64102599,

目標(biāo)函數(shù)的最優(yōu)值為：247.4358982.

在整個(gè)求解過程中,需確定目標(biāo)函數(shù)單元格及“可變單元格”區(qū)域位置兩處單元格位置,當(dāng)然要正確地輸入約束條件和確定所求的目標(biāo)是最大還是最小才可求得正確結(jié)果.但對(duì)于有無窮多最優(yōu)解的問題,該方法只能給出其中的一個(gè)解[3].

2 用單純形法求解

2.1 建立數(shù)學(xué)模型[4]

設(shè)Xj(j=1,2,3,4,5)表示10千克混合飼料中所含的第j種飼料的數(shù)量.

析約束條件：

當(dāng)然對(duì)變量Xj(j=1,2,3,4,5)的要求應(yīng)為非負(fù).

目標(biāo)函數(shù)：

min f=2 X1+7 X2+4 X3+3 X4+5 X5

數(shù)學(xué)模型：

2.2 用單純形法求解[5]

1)引入松弛變量將化標(biāo)準(zhǔn)形

在標(biāo)準(zhǔn)形中,約束條件的等式約束是一個(gè)含有5個(gè)變量、2個(gè)等式的線性方程組,系數(shù)矩陣的秩為2,所以有3個(gè)基變量,另外2個(gè)非基變量.

2)非基變量置0,求得一個(gè)基本可行解

3)建立初始單純形表 (見表3)

將約束部分 (即線性方程組)的系數(shù)矩陣等式右邊的常數(shù)、檢驗(yàn)數(shù)以及目標(biāo)函數(shù)值,填入表3中,得到某組基變量對(duì)應(yīng)的單純形表.

表3 初始單純形表

4)初等變換

將轉(zhuǎn)軸點(diǎn)變成1,并且以轉(zhuǎn)軸點(diǎn)所在的行為基準(zhǔn)行,將表中入基變量所在列的其他數(shù)包括檢驗(yàn)數(shù)都變?yōu)?,結(jié)果就是新基變量對(duì)應(yīng)的單純形表 (見表4).

5)迭代,直到檢驗(yàn)數(shù)非負(fù),可得問題的最優(yōu)解

表中檢驗(yàn)數(shù)都大于等于0,所以已經(jīng)是最優(yōu),它的最優(yōu)解為X1=2,X2=3,X3=0,目標(biāo)函數(shù)的最優(yōu)值為max f=13(見表5)

表4 關(guān)于新基的單純形表

表5 最優(yōu)解

3 用MA TLAB解決規(guī)劃問題通用函數(shù)

MA TLAB是一種應(yīng)用于數(shù)學(xué)計(jì)算及計(jì)算結(jié)果可視化處理的面向?qū)ο蟮母咝阅苡?jì)算機(jī)語言,它以矩陣和向量為基本數(shù)據(jù)單位,從而提高程序的向量化程度,提高計(jì)算效率,尤其適合于線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問題的算法的編寫,以及數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理法[6].

在以上算法的支持下,給出MA TLAB解決規(guī)劃問題通用函數(shù).

說明：

1)函數(shù)使用條件：全部變量、常數(shù)項(xiàng)非負(fù),約束為不等式

2)函數(shù)參數(shù)說明：A為單純形表,a為函數(shù)系數(shù)距陣,m和n分別為非基變量個(gè)數(shù)和基變量個(gè)數(shù).

上函數(shù)可獲得最佳的單元格的可能值,在數(shù)解決方案過程中的各個(gè)階段使用線性近似值問題函數(shù);這些近似值線性實(shí)際函數(shù)時(shí)都完全相同.

[1] 唐五湘,程桂枝.Excel在管理決策中的應(yīng)用 [M].北京：電子工業(yè)出版社,2005：30-35

[2]張光澄.非線性最優(yōu)化計(jì)算方法 [M].北京：高等教育出版社,2005：82-95

[3]謝金星,薛毅.優(yōu)化建模LINDO/LINGO軟件 [M].北京：清華大學(xué)出版社,2005：47-63

[4]趙靜,但琦.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) [M].北京：高等教育出版社,2008：56-66

[5]李靜萍,謝邦昌.多元統(tǒng)計(jì)分析方法與應(yīng)用 [M].北京：中國(guó)人民大學(xué)出版社,2008：112-132

[6]張志涌,徐彥琴.MATLAB教程 [M].北京：北京航空航天大學(xué)出版社,2004：135-167