張小勇， 賈利新

(信息工程大學(xué) 第三學(xué)院，河南 鄭州 450004)

0-1整數(shù)規(guī)劃模型中邏輯表達(dá)式的一些注記

張小勇， 賈利新

(信息工程大學(xué) 第三學(xué)院，河南 鄭州 450004)

從建立0-1整數(shù)規(guī)劃模型的實(shí)際出發(fā)，對該模型中若干邏輯表達(dá)式線性表示、互斥和乘積表達(dá)式轉(zhuǎn)化，以及具體的指派問題中能力限制約束的表示問題進(jìn)行了研究，利用真值表等工具給出了相應(yīng)的結(jié)果.

0-1整數(shù)規(guī)劃；二值變量；真值表

0 引言

優(yōu)化模型是最為重要的數(shù)學(xué)模型之一[1- 2].如果在優(yōu)化模型中決策變量取0和1的二值變量，則稱此模型為0-1整數(shù)規(guī)劃模型.0-1整數(shù)規(guī)劃模型是一類重要的優(yōu)化模型，在指派問題、配送問題等求解中發(fā)揮著重要作用[3]112-115.本文從建立0-1整數(shù)規(guī)劃模型的實(shí)際出發(fā)，對該模型中若干邏輯表達(dá)式線性表示、互斥和乘積表達(dá)式轉(zhuǎn)化以及指派問題中能力限制約束的表示問題進(jìn)行了研究，給出了相應(yīng)的結(jié)果.

1 約束條件的線性邏輯表達(dá)式表示

在0-1整數(shù)規(guī)劃模型的建立過程中，要將已有的約束條件用邏輯表達(dá)式具體地表示出來，同時(shí)要求盡可能使用線性約束，以便于利用各類軟件或智能算法求解模型[4]. 在露天采礦問題[5]中，一個(gè)重要的約束條件為“欲挖下面的1塊，必須先挖取上面的4塊”.設(shè)定上面4塊用二值變量a,b,c,d表示，而下面1塊用e表示，為了深入解決如何用線性邏輯表達(dá)式表達(dá)該約束的問題，考慮更一般的情況，即

“如果完成工作A，則必須完成工作A1,A2,…,An”

(1)

的線性表達(dá)問題.為此，假設(shè)有n項(xiàng)工作A1,A2,…,An.為工作Ai設(shè)定一個(gè)決策變量xi. 如果決策變量xi取0，表示不完成工作Ai，如果xi取1，表示完成工作Ai.考慮在(1)中n=1的情況，即約束條件“如果完成工作A，則必須也完成工作B”的線性表達(dá)問題，設(shè)其可以用A→B表示.考慮蘊(yùn)含式A→B的真值表，A→B為假當(dāng)且僅當(dāng)A真而B假[6]，即a=1且b=0，其他情況下A→B均為真(表1).

表1 A→B的真值表

表的真值表

結(jié)論1 1) 約束條件“如果完成工作A，則必須也完成工作B”可以用表達(dá)式a≤b表示；

2) 約束條件“如果完成工作A，則不能完成工作B”可以用表達(dá)式a+b≤1表示；

3) 約束條件“如果不完成工作A，則必須完成工作B”可以用表達(dá)式a+b≥1表示.

顯然，根據(jù)1)，約束條件“工作A工作B必須同時(shí)完成”等價(jià)于a=b.

注意，“在n個(gè)工作A1,A2,…,An中，選擇完成的工作不超過k(≤n)個(gè)” 可以用∑xi≤k表示；“在n個(gè)工作A1,A2,…,An中，選擇完成的工作恰好為k(≤n)個(gè)”可以用∑xi=k表示.那么“完成工作A1,A2,…,An”等價(jià)于“x1+x2+…+xn=n”；“完成工作A1,A2，…,An的至少一個(gè)”等價(jià)于“x1+x2+…+xn≥1”.把結(jié)論1中的結(jié)果推廣到一般情況，同樣利用蘊(yùn)含式的真值表得到結(jié)論2.

結(jié)論2 1) 約束條件“如果完成工作A，則必須完成工作A1,A2,…,An”用na≤x1+x2+…+xn表示；

2) 約束條件“如果完成工作A，則必須完成工作A1,A2,…,An中至少一個(gè)”可用a≤x1+x2+…+xn表示；

3) 約束條件“如果完成工作A1,A2,…,An，則必須完成工作A”用a+n-1≥x1+x2+…+xn表示；

4) 約束條件“如果完成工作A1,A2,…,An中至少一個(gè)，則必須完成工作A”可用a≥x1+x2+…+xn表示.

需要指出，對于結(jié)論2中的1)，也可用

a≤x1·x2·…·xn，

或者

a≤min{x1,x2,…,xn}

表示，只是非線性表達(dá)式將導(dǎo)致求解的困難.于是，對于露天采礦問題中問題(1),可用

4e≤a+b+c+d

表示.

2 互斥和乘積邏輯表達(dá)式的轉(zhuǎn)化

在某些優(yōu)化問題中還會(huì)遇到互相排斥的條件，此時(shí)可以人為引入0-1變量，使其變?yōu)?-1整數(shù)規(guī)劃.比如對于約束條件“工作A和工作B同時(shí)只能選中一個(gè),即A和B有且僅有一個(gè)可以完成”.令a,b為二值變量，那么可以用a+b=1表示.

如果在某個(gè)優(yōu)化問題中約束條件f(x)≤0，g(x)≤0只能兩者選一，可以引入二值變量t，令

tf(x)+(1-t)g(x)≤0,t∈{0,1}，

便可把兩個(gè)約束在同一問題中統(tǒng)一.更一般地，如果n個(gè)約束

fi(x)≤0,i=1,2,…,n

中同時(shí)只能有一個(gè)滿足，那么引入n個(gè)二值變量ti,

如果約束條件是乘積形式，比如b3=b2b1,bi∈{0,1}，此時(shí)如何轉(zhuǎn)化為線性約束？寫出4種b1,b2的組合和b3相應(yīng)的取值，可得

b3≤b2,b3≤b1,b3≥b1+b2-1.

類似地，可以分析乘積約束b=bn…b2b1,bi∈{0,1}的線性表示法.

3 指派問題中能力限制約束的表示

假設(shè)cij表示在指派問題中第i人完成第j項(xiàng)工作的所用時(shí)間(最小化問題中)或帶來的收益(最大化問題中).有時(shí)會(huì)遇到第i人不能完成第j項(xiàng)工作的約束，此時(shí)如何確定對應(yīng)的cij的取值.

例1[3]126第i人不能完成第j項(xiàng)工作，此時(shí)將不會(huì)帶來任何的收益或者有任何的付出，是否第i人不能完成第j項(xiàng)工作等價(jià)于cij=0？假設(shè)第1人不能完成第4項(xiàng)工作，將效率矩陣中的c14=4改為c14=0，求解后得到x14=1，這與假設(shè)矛盾.考慮極端的情況，假設(shè)所有的cij=0，那么此時(shí)隨意安排xij，都會(huì)取到相同的目標(biāo)函數(shù)值0.特別地，取xii=1，也會(huì)得到目標(biāo)函數(shù)值為0，這意味著指定第i人完成第i項(xiàng)工作，與所有cij=0矛盾.

如果第i人不能完成第j項(xiàng)工作時(shí)令cij取負(fù)數(shù)，兩者是否等價(jià).同樣將c14=4改為c14=-2，求解后得到x14=1，矛盾.

第i人不能完成第j項(xiàng)工作，即要保證在解中xij=0.在最小化問題中，根據(jù)求解指派問題的匈牙利算法，cij所在的第i行或者第j列cij最大，這樣無論如何變換，cij所在的位置不可能為0，從而可以保證xij=0，于是在理論上應(yīng)該令cij=+∞或者cij=-∞.在實(shí)際中只需要求cij相對于其他系數(shù)cij充分大(最小化問題)或者充分小(最大化問題)，即取cij為一個(gè)大的整數(shù)或者大的負(fù)數(shù)即可.在例1中將c14=4改為90，經(jīng)過計(jì)算得到x14=0，達(dá)到了預(yù)期目的.

4 結(jié)束語

在建立0-1整數(shù)規(guī)劃模型的過程中，本文所提到的約束條件的邏輯表達(dá)式的表示和轉(zhuǎn)化問題會(huì)經(jīng)常遇到.通過羅列蘊(yùn)含式的真值表，或者條件的所有組合以及相應(yīng)的結(jié)論，歸納出對應(yīng)條件的邏輯表達(dá)式.

[1] MEERSCHAERT M M.數(shù)學(xué)建模方法與分析[M].劉來福，楊淳，黃海洋，譯.北京：機(jī)械工業(yè)出版社,2008：12-17.

[2] 胡運(yùn)紅.數(shù)學(xué)建模中的最優(yōu)化理論[J].運(yùn)城學(xué)院學(xué)報(bào),2005,23(5):45-48.

[3] 《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(xué)[M]. 北京：清華大學(xué)出版社,1990.

[4] 袁新生,邵大宏,郁時(shí)煉.LINGO和EXCEL在數(shù)學(xué)建模中的應(yīng)用[M]. 北京：科學(xué)出版社,2001:89-95.

[5] 劉翔,徐香勤.基于改進(jìn)遺傳算法的露天采礦優(yōu)化[J].河南教育學(xué)院學(xué)報(bào)：自然科學(xué)版,2007，16(2)：25-28.

[6] 方世昌.離散數(shù)學(xué)[M].西安：西安電子科技大學(xué)出版社,1985:12-35.

Some Notes on Logical Expressionin the 0-1 Integer Programming Model

ZHANG Xiao-yong， JIA Li-xin

(TheThirdInstitute,InformationEngineeringUniversity,Zhengzhou450004,China)

From the practice of modeling 0-1 integer programming, the linear denotation of logical expression, transformation of mutual exclusion and multiply expression are researched, especially the expression of ability constrained condition in assignment problem. Based on the truth table the corresponding conclusions are given.

0-1 integer programming; two-valued variable; truth table

2014-06-01

國家自然科學(xué)基金(10501053)

張小勇(1979—)，男，陜西西安人，信息工程大學(xué)第三學(xué)院講師.

10.3969/j.issn.1007-0834.2014.04.002

O221.1

A

1007-0834(2014)04-0008-03