基于0- 1 變量函數(shù)在線性優(yōu)化求解中的應(yīng)用研究

熊慶如

（浙江東方職業(yè)技術(shù)學(xué)院基礎(chǔ)部，浙江 溫州 325011）

優(yōu)化求解是線性規(guī)劃的一個(gè)通行的做法，是從可行解中尋找最優(yōu)解的一種數(shù)學(xué)方法。它涉及目標(biāo)函數(shù)、約束條件、決策變量這幾個(gè)因素。優(yōu)化求解方法一般有兩類：第一類是求最優(yōu)解，它包括數(shù)學(xué)規(guī)劃和動(dòng)態(tài)規(guī)劃；第二類是求近似求解，它包括啟發(fā)式算法和metaheuristics。至于選取哪種方法，是要在具體實(shí)踐中加以考量。

1 問題的引入

數(shù)學(xué)規(guī)劃是若干個(gè)變量在滿足一些等式或不等式限制的條件下，使一個(gè)或多個(gè)目標(biāo)函數(shù)取得最大值或最小值。

其中，會(huì)出現(xiàn)可行解（或可行域）和最優(yōu)解（或最優(yōu)域），求解過程有許多軟件可以使用，通常，LINGO用的比較多。下面結(jié)合例子加以說明。

譬如：有7 天時(shí)間可安排復(fù)習(xí)4 門課程，每天只能復(fù)習(xí)一門課程，每門課程至少復(fù)習(xí)一天。各門課程復(fù)習(xí)天數(shù)與可能提高分?jǐn)?shù)之間的關(guān)系如下表：

課程 1 天 2 天 3 天 4 天語文 3 5 6 7英語 5 5 6 9數(shù)學(xué) 2 4 7 8政治 6 7 9 9

如何制定復(fù)習(xí)計(jì)劃，才能使得所有課程提高的總分盡可能大？

對(duì)這個(gè)問題一般化處理：有T天時(shí)間可用于復(fù)習(xí)n 門課程，每天只能復(fù)習(xí)一門課程，每門課程至少復(fù)習(xí)一天。用t 天時(shí)間復(fù)習(xí)j門課程，可使該門課程提Pjt高分。如何制定復(fù)習(xí)計(jì)劃，才能使得所有課程提高的總分盡可能大？

決策變量：xj為第j 門課程復(fù)習(xí)天數(shù)j=1，2，3，4…，xj為正整數(shù)，x1=3，x2=1，x3=2，x4=1

但是，目標(biāo)函數(shù)的足標(biāo)有決策變量xj，不便于求解。問題在于假設(shè)不好！

倘若把它變?yōu)橐粋€(gè)二維變量：

則原來的可行解x1=3，x2=1，x3=2，x4=1 就成：

雖然上面這個(gè)式子是正確的，但不符合數(shù)學(xué)規(guī)劃規(guī)范，為此，這需要使用0-1 變量的技巧。

2 0-1 變量函數(shù)

優(yōu)先條件

（1）僅當(dāng)0-1 變量y取值1 時(shí)，0-1 變量x才取值1（案例：我現(xiàn)在要開一個(gè)商店，這個(gè)商店為你服務(wù)。因此，只有商店開出來后，才能說為你服務(wù)）這里，x取1 是以y取1 為前提的。

處理辦法：x≤y

（2）擴(kuò)展：僅當(dāng)0-1 變量y取值1 時(shí)，n 個(gè)0-1 變量x1，x2，…，xn中的任一個(gè)才取值1。（案例：商店開出來以后，服務(wù)n 個(gè)小區(qū)，）

現(xiàn)在回到原來的問題：

定義決策變量：

現(xiàn)在把時(shí)間安排的案例稍作改動(dòng)，變?yōu)椋河蠺 天時(shí)間可安排復(fù)習(xí)n 門課程，每天只能 復(fù)習(xí)一門課程。在t 天時(shí)間復(fù)習(xí)第j 門課程可使該門課程提高Pjt分，在不同天中復(fù)習(xí)同一門課程的效果可以累加。如何制定復(fù)習(xí)計(jì)劃，才能使得所有課程提高的總分盡可能大？

3 0-1 變量函數(shù)的改進(jìn)

（這個(gè)函數(shù)在經(jīng)濟(jì)學(xué)中，當(dāng)x=0，表示不生產(chǎn)，成本當(dāng)然為0；當(dāng)x＞0 時(shí)，成本分固定成本與可變成本，是線性的。所以，出來的是分段函數(shù)。這個(gè)分段函數(shù)在規(guī)劃中是很麻煩的事情，主要是因?yàn)樗皇沁B續(xù)的。當(dāng)x=0 時(shí)，成本當(dāng)然為0，但在x＞0 時(shí)，自變量x接近0 的時(shí)候，其成本卻是c2，這在線性規(guī)劃中不好處理）

這時(shí)，用0-1 變量可以處理：

這里，y不是獨(dú)立的，它與x是有關(guān)系的。因此，需要揭示出它們之間的關(guān)系。如果不揭示出來，就會(huì)出現(xiàn)錯(cuò)誤。現(xiàn)在要使費(fèi)用最小化，你沒有這個(gè)關(guān)系的話，比如，x取0 的時(shí)候，y 取0，x 大于0 時(shí)，y取1。但是，x大于0，y等于0，費(fèi)用很低。x大于0 時(shí)，c2這個(gè)成本肯定是要有的。因此，x與y的關(guān)系也要寫到規(guī)劃里面去，雖然說，x與y都是變量，但是它們不是獨(dú)立的，它們是相互有影響的，不能把它們?nèi)サ簟Ｈ绻瞻醝f，x=0，y=0；if，x＞0，y=1，那在數(shù)學(xué)規(guī)劃里面沒有這種邏輯的條件的式子（if）,這樣是不能操作的。因此，要把條件（含if的式子）的式子進(jìn)行轉(zhuǎn)換。

那么如何將這種邏輯關(guān)系式表達(dá)成線性規(guī)劃式呢？

我們剛才寫了式子：y=1 當(dāng)且僅當(dāng)x＞0。這是一個(gè)充要條件，它包含兩層意思：

x＞0?y=1 和y=1?x＞0。

首先，x＞0?y=1，（利用前面學(xué)過的：僅當(dāng)0-1 變量y取值1 時(shí)，0-1 變量x 才能取值1，用式子x≤y 表示），類似地，我們得出：x≤My，其中M滿足x≤M，那么M是一個(gè)非常大的數(shù)，M比題目中所有數(shù)都大，或者說是x的集合的上限。

其次，y=1?x＞0，是難以做到的。但是，將它稍稍改變一下為，y=1?x≥ε（ε 是一個(gè)很小的數(shù)），類似地，只要x≥εy，就能得到解決。

但是，在多數(shù)情況下，這個(gè)條件是不需要的。

因?yàn)椋繕?biāo)函數(shù)形如：minf（x），即使不列入該約束，若最優(yōu)解中x=0，同時(shí)又y=0。我們的擔(dān)心是否會(huì)出現(xiàn)：x=0?y=1 呢？

由于y=1?x＞0 與x=0?y=0 是互為逆否命題，所以，不會(huì)出現(xiàn)x=0?y=1

因此，目標(biāo)函數(shù)形如：minf（x），只需要寫x≥My，不需要寫x≥εy。

這就是分段函數(shù)的處理辦法。

線性化

可以將之表達(dá)成：y1=1 且y2=1

但是這個(gè)且也是不行的，進(jìn)一步表達(dá)成：y1y2=1，這是一個(gè)非線性函數(shù)。

在lingo軟件中，非線性函數(shù)難實(shí)施。因此需要將它轉(zhuǎn)化成線性函數(shù)。

其含義是：y=1 當(dāng)且僅當(dāng)y1=y2=1，充分性是y≤y1，y≤y2；必要性是y≥y1+y2-1。將充分性與必要性放到一起的三個(gè)式子就線性化了：y≤y1，y≤y2，y≥y1+y2-1

4 問題的解決

現(xiàn)在回到時(shí)間分配問題。

假設(shè)xij（i，j=1，2，3，4）表示第i 門課復(fù)習(xí)j 天，pj（j=1，2，3，4）表示某門課程復(fù)習(xí)天數(shù)。

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

應(yīng)用lingo軟件編制程序，可以得到最優(yōu)解為23，具體方案是：第1 門課復(fù)習(xí)2 天，第2 門課復(fù)習(xí)1 天，第3 門課復(fù)習(xí)3 天，第4 門課復(fù)習(xí)1 天。

數(shù)學(xué)規(guī)劃求解優(yōu)化問題有許多優(yōu)點(diǎn)。它可以借助計(jì)算機(jī)和軟件求解一些具體實(shí)例，體現(xiàn)對(duì)問題的理解和為求解所作的準(zhǔn)備，利用數(shù)學(xué)規(guī)劃的理論和方法分析解決問題。同時(shí)，現(xiàn)有的優(yōu)化軟件只能求出部分?jǐn)?shù)學(xué)規(guī)劃的最優(yōu)解，建立合適的數(shù)學(xué)規(guī)劃模型需要一定的經(jīng)驗(yàn)和技巧，數(shù)學(xué)規(guī)劃可能掩蓋問題固有的性質(zhì)。應(yīng)用數(shù)學(xué)規(guī)劃方法的常見問題：數(shù)學(xué)規(guī)劃不是求解優(yōu)化問題的唯一方法和最有效方法，可運(yùn)用組合、解析方法求解或能設(shè)計(jì)多項(xiàng)式時(shí)間算法的問題未必需要給出數(shù)學(xué)規(guī)劃。數(shù)學(xué)規(guī)劃無法在合理的時(shí)間內(nèi)求解出最優(yōu)解或可行解的問題不適合采用數(shù)學(xué)規(guī)劃的方法求解。