基于0- 1 變量函數在線性優化求解中的應用研究

熊慶如

（浙江東方職業技術學院基礎部，浙江 溫州 325011）

優化求解是線性規劃的一個通行的做法，是從可行解中尋找最優解的一種數學方法。它涉及目標函數、約束條件、決策變量這幾個因素。優化求解方法一般有兩類：第一類是求最優解，它包括數學規劃和動態規劃；第二類是求近似求解，它包括啟發式算法和metaheuristics。至于選取哪種方法，是要在具體實踐中加以考量。

1 問題的引入

數學規劃是若干個變量在滿足一些等式或不等式限制的條件下，使一個或多個目標函數取得最大值或最小值。

其中，會出現可行解（或可行域）和最優解（或最優域），求解過程有許多軟件可以使用，通常，LINGO用的比較多。下面結合例子加以說明。

譬如：有7 天時間可安排復習4 門課程，每天只能復習一門課程，每門課程至少復習一天。各門課程復習天數與可能提高分數之間的關系如下表：

課程 1 天 2 天 3 天 4 天語文 3 5 6 7英語 5 5 6 9數學 2 4 7 8政治 6 7 9 9

如何制定復習計劃，才能使得所有課程提高的總分盡可能大？

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

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

但是，目標函數的足標有決策變量xj，不便于求解。問題在于假設不好！

倘若把它變為一個二維變量：

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

雖然上面這個式子是正確的，但不符合數學規劃規范，為此，這需要使用0-1 變量的技巧。

2 0-1 變量函數

優先條件

（1）僅當0-1 變量y取值1 時，0-1 變量x才取值1（案例：我現在要開一個商店，這個商店為你服務。因此，只有商店開出來后，才能說為你服務）這里，x取1 是以y取1 為前提的。

處理辦法：x≤y

（2）擴展：僅當0-1 變量y取值1 時，n 個0-1 變量x1，x2，…，xn中的任一個才取值1。（案例：商店開出來以后，服務n 個小區，）

現在回到原來的問題：

定義決策變量：

現在把時間安排的案例稍作改動，變為：有T 天時間可安排復習n 門課程，每天只能 復習一門課程。在t 天時間復習第j 門課程可使該門課程提高Pjt分，在不同天中復習同一門課程的效果可以累加。如何制定復習計劃，才能使得所有課程提高的總分盡可能大？

3 0-1 變量函數的改進

（這個函數在經濟學中，當x=0，表示不生產，成本當然為0；當x＞0 時，成本分固定成本與可變成本，是線性的。所以，出來的是分段函數。這個分段函數在規劃中是很麻煩的事情，主要是因為它不是連續的。當x=0 時，成本當然為0，但在x＞0 時，自變量x接近0 的時候，其成本卻是c2，這在線性規劃中不好處理）

這時，用0-1 變量可以處理：

這里，y不是獨立的，它與x是有關系的。因此，需要揭示出它們之間的關系。如果不揭示出來，就會出現錯誤。現在要使費用最小化，你沒有這個關系的話，比如，x取0 的時候，y 取0，x 大于0 時，y取1。但是，x大于0，y等于0，費用很低。x大于0 時，c2這個成本肯定是要有的。因此，x與y的關系也要寫到規劃里面去，雖然說，x與y都是變量，但是它們不是獨立的，它們是相互有影響的，不能把它們去掉。如果照搬if，x=0，y=0；if，x＞0，y=1，那在數學規劃里面沒有這種邏輯的條件的式子（if）,這樣是不能操作的。因此，要把條件（含if的式子）的式子進行轉換。

那么如何將這種邏輯關系式表達成線性規劃式呢？

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

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

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

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

但是，在多數情況下，這個條件是不需要的。

因為，目標函數形如：minf（x），即使不列入該約束，若最優解中x=0，同時又y=0。我們的擔心是否會出現：x=0?y=1 呢？

由于y=1?x＞0 與x=0?y=0 是互為逆否命題，所以，不會出現x=0?y=1

因此，目標函數形如：minf（x），只需要寫x≥My，不需要寫x≥εy。

這就是分段函數的處理辦法。

線性化

可以將之表達成：y1=1 且y2=1

但是這個且也是不行的，進一步表達成：y1y2=1，這是一個非線性函數。

在lingo軟件中，非線性函數難實施。因此需要將它轉化成線性函數。

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

4 問題的解決

現在回到時間分配問題。

假設xij（i，j=1，2，3，4）表示第i 門課復習j 天，pj（j=1，2，3，4）表示某門課程復習天數。

目標函數：

應用lingo軟件編制程序，可以得到最優解為23，具體方案是：第1 門課復習2 天，第2 門課復習1 天，第3 門課復習3 天，第4 門課復習1 天。

數學規劃求解優化問題有許多優點。它可以借助計算機和軟件求解一些具體實例，體現對問題的理解和為求解所作的準備，利用數學規劃的理論和方法分析解決問題。同時，現有的優化軟件只能求出部分數學規劃的最優解，建立合適的數學規劃模型需要一定的經驗和技巧，數學規劃可能掩蓋問題固有的性質。應用數學規劃方法的常見問題：數學規劃不是求解優化問題的唯一方法和最有效方法，可運用組合、解析方法求解或能設計多項式時間算法的問題未必需要給出數學規劃。數學規劃無法在合理的時間內求解出最優解或可行解的問題不適合采用數學規劃的方法求解。