數(shù)學(xué)模型中的0、1變量的使用的案例

惠高峰

摘要：本文通過優(yōu)化問題的求解，講述了線性規(guī)劃的數(shù)學(xué)模型中0、1變量的使用方法和技巧，并利用LINGO軟件進(jìn)行了編程測(cè)試，提高數(shù)學(xué)模型中變量的使用方法。

關(guān)鍵詞：Lingo軟件 0、1變量

數(shù)學(xué)優(yōu)化問題在管理數(shù)學(xué)當(dāng)中是一個(gè)并不復(fù)雜的問題，但是對(duì)于變量的使用，尤其是0、1變量的使用，學(xué)生們會(huì)產(chǎn)生很大迷惑，以下通過一些例子來講述一下0、1變量的靈活使用。公司在各地有4項(xiàng)業(yè)務(wù)，選定了4位業(yè)務(wù)員去處理。由于業(yè)務(wù)能力、經(jīng)驗(yàn)和其它情況不同，4位業(yè)務(wù)員去處理4項(xiàng)業(yè)務(wù)的費(fèi)用（單位：元）各不相同，見右表。

應(yīng)當(dāng)怎樣分派任務(wù)，才能使總的費(fèi)用最?。?/p>

問題分析與求解：這是一個(gè)最優(yōu)指派問題。引入如下變量：xij=1 若分派第i個(gè)人做每j項(xiàng)業(yè)務(wù)0 若不分派第i個(gè)人做第j項(xiàng)業(yè)務(wù)

設(shè)矩陣a（4，4）為指派矩陣，其中a（i，j）為第i個(gè)業(yè)務(wù)員做第j項(xiàng)業(yè)務(wù)的業(yè)務(wù)費(fèi)。則可以建立如下模型：

minZ=■■aijxij s.t■xij=1 j=1，2，3，4■xij=1 i=1，2，3，4xij=0或1 i，j=1，2，3，4

LINGO程序如下：

MODEL：

SETS：

person/1..4/；

task/1..4/；

assign（person，task）：a，x；

ENDSETS

DATA：

a=1100，800，1000，700，

600，500，300，800，

400，800，1000，900，

1100，1000，500，700；

ENDDATA

min=@sum（assign：a*x）；

@for（person（i）：@sum（task（j）：x（i，j））=1）；

@for（task（j）：@sum（person（i）：x（i，j））=1）；

@for（assign（i，j）：@bin（x（i，j）））；

END

得到的結(jié)果如下：

x（1，1）=0，x（1，2）=0，x（1，3）=0，x（1，4）=1；

x（2，1）=0，x（2，2）=1，x（2，3）=0，x（2，4）=0；

x（3，1）=1，x（3，2）=0，x（3，3）=0，x（3，4）=0；

x（4，1）=0，x（4，2）=0，x（4，3）=1，x（4，4）=0；

最小費(fèi)用為2100元。

即第1個(gè)業(yè)余員做第4項(xiàng)業(yè)務(wù)，第2個(gè)業(yè)余員做第2項(xiàng)業(yè)務(wù)，即第3個(gè)業(yè)余員做第1項(xiàng)業(yè)務(wù)，第4業(yè)余員做第3項(xiàng)業(yè)務(wù)?？傎M(fèi)用達(dá)到最小，為2100元。

有五項(xiàng)設(shè)計(jì)任務(wù)可供選擇。各項(xiàng)設(shè)計(jì)任務(wù)的預(yù)期完成時(shí)間分別為3，8，5，4，10（周）設(shè)計(jì)報(bào)酬分別為7，17，11，9，21（萬(wàn)元）。設(shè)計(jì)任務(wù)只能一項(xiàng)一項(xiàng)地進(jìn)行，總的期限為20周。選擇任務(wù)時(shí)必須滿足下面要求：①至少完成3項(xiàng)設(shè)計(jì)任務(wù)。②若選擇任務(wù)1，必須同時(shí)選擇任務(wù)2。③任務(wù)3和任務(wù)4不能同時(shí)選擇。

應(yīng)當(dāng)選擇哪些任務(wù)，才能使總的設(shè)計(jì)報(bào)酬最大？

分析與求解：這是一個(gè)0-1整數(shù)規(guī)劃問題。

設(shè)0-1變量xi如下：xi=0 第i項(xiàng)設(shè)計(jì)任務(wù)未選上1 第i項(xiàng)設(shè)計(jì)任務(wù)被選上

設(shè)各項(xiàng)設(shè)計(jì)任務(wù)的完成時(shí)間為ti（i=1，2，…，5）表示，設(shè)計(jì)報(bào)酬為mi（i=1，2，…，5）表示。則容易得到目標(biāo)函數(shù)：maxZ=■mixi。根據(jù)題目要求分別列出約束條件如下：

總期限為避免20周，則約束條件為■tixi？燮20

至少完成3項(xiàng)設(shè)計(jì)任務(wù)，則■xi？叟3

若選擇任務(wù)1，必須同時(shí)選擇任務(wù)2，則x2？叟x1。

任務(wù)3和任務(wù)4不能同時(shí)選擇，則x3+x4？燮1，該約束表達(dá)式表明任務(wù)3和任務(wù)4至多只能選擇1個(gè)。

因此對(duì)該問題建立的數(shù)學(xué)模型如下：

maxZ=■mixi s.t■tixi？燮20■xi？叟3x2？叟x1x3+x4？燮1x1，x2，x3，x4=0或1

LINGO程序如下：

MODEL：

SETS：

mat/1..5/：m，t，x；

ENDSETS

DATA：

m=7，17，11，9，21； ！定義報(bào)酬數(shù)組；

t=3，8，5，4，10； ！定義完成時(shí)間；

ENDDATA

max=@SUM（mat（i）：m（i）*x（i））； ！定義目標(biāo)函數(shù)；

@SUM（mat（i）：t（i）*x（i））<=20；！期限約束 ；

@SUM（mat（i）：x（i））>=3； ！至少完成3項(xiàng)任務(wù)；

x（2）>=x（1）； ！若選擇任務(wù)1，必須同時(shí)選擇任務(wù)2；

x（3）+x（4）<=1； ！任務(wù)3和任務(wù)4不能同時(shí)選擇；

@FOR（mat（i）：@BIN（x（i）））； ！使各變量為0-1變量；

END

得到的解為x（1）=1，x（2）=1，x（3）=1，x（4）=0，x（5）=0。最大報(bào)酬為35萬(wàn)元。

即在滿足各種約束條件下，選擇設(shè)計(jì)任務(wù)1，2，3，可使總報(bào)酬達(dá)到最大為35萬(wàn)元。

參考文獻(xiàn)：

[1]肖華勇.實(shí)用數(shù)學(xué)建模與軟件應(yīng)用[M].西安：西北工業(yè)大學(xué)出版社，2008.

[2]周義倉(cāng)，郝孝良.數(shù)學(xué)建模實(shí)驗(yàn)[M].西安：西安交通大學(xué)出版社，2007.