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

張小勇， 賈利新

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

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

張小勇， 賈利新

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

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

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

0 引言

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

1 約束條件的線性邏輯表達式表示

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

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

(1)

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

表1 A→B的真值表

表的真值表

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

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

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

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

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

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

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

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

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

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

a≤x1·x2·…·xn，

或者

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

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

4e≤a+b+c+d

表示.

2 互斥和乘積邏輯表達式的轉化

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

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

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

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

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

中同時只能有一個滿足，那么引入n個二值變量ti,

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

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

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

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

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

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

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

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

4 結束語

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

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

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

[3] 《運籌學》教材編寫組.運籌學[M]. 北京：清華大學出版社,1990.

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

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

[6] 方世昌.離散數(shù)學[M].西安：西安電子科技大學出版社,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

國家自然科學基金(10501053)

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

10.3969/j.issn.1007-0834.2014.04.002

O221.1

A

1007-0834(2014)04-0008-03