打開《運籌學》課本，第一章教的便是求解線性規劃問題最有效的算法——單純形法。

自此，任何看似很複雜的問題隻要轉變成線性規劃問題，便能高效求解，發好期刊。

可實際在科研建模時，目标函數或是約束條件，極大概率會出現非線性的形式。

此時若選擇采用啟發式算法求解，就相當于放棄了求精确解，也放棄了投好期刊。

因此，了解并懂得何種形式可以轉化為線性和如何轉化，是非常重要的。

總的來說，具有：

分段函數形式、

絕對值函數形式、

最小/大值函數形式、

邏輯或形式、

含有0-1變量的乘積形式、

混合整數形式

以及分式目标函數，均可實現線性化。

線性化的主要手段其實就兩點，一點是引入0-1變量，另一點是引入很大的整數M。

靈活運用這兩點會呈現非常巧妙且神奇的線性化技巧，希望你也能感受到其中的數學之美。

鑒于以上内容較多，故分兩期進行闡述，本期先闡述較為簡單的幾種。

1.分段函數

若一種産品的采購有固定成本K，那麼其采購成本應分為不采購和采購兩段：

其線性化方法簡單且巧妙：（分類讨論y=0和y=1即可理解）

其中，y是引入的輔助0-1變量，M是一個很大的整數。

注：如果當x=0時，成本不是0而是a。此時的分段函數形式也是可以線性化的，聰明的你知道如何轉化嗎？如果沒想到辦法，歡迎私信交流。

2.絕對值函數

要求線性化如下數學模型：

方法1：用yi代替絕對值部分

方法2：用ui、vi代替

高中或是高數課上學過如下定理：

定理：

則之前數學模型可以線性化為：

3.MaxMin/MinMax函數

以下圖的MaxMin函數為例，基于k 項min CX（矩陣寫法省略了求和号，打不了轉置符号，望大家理解）函數的值，再取其中的最大值。

該形式下的線性化方法是：用z 替代min CX函數，這樣z 便 ≤ CX，又由目标函數是取最大的z，從而限制住z 不會取到0，而隻會取滿足條件的z。MinMax函數同理。

此時數學感覺良好的同學可能已經意識到這類似于高數課上的夾逼定理（判斷極限是否存在），進一步也可能意識到，如果換為MaxMax和MinMin函數，以上這套思路就行不通了。

實際也确實是這樣，線性化MaxMax和MinMin函數較為複雜一些，需要借助下面第四點線性化邏輯或的思維。

4.邏輯或

該部分主要針對約束條件（含有邏輯或）的線性化操作。通常，邏輯或兩端的約束存在三種情形。

情形1：邏輯或兩段均為≤，即：

此時線性化方法為：

引入u 和v 兩個0-1變量和大M。分類讨論u 和v 取0或1的四種情形便能理解以上過程。思路非常巧妙，希望大家多悟幾遍并消化。

情形2：一端為≤，一端為=，即：

此時線性化方法為：

可見，多添加一個≥的式子即可。那麼，情形3如何處理相信大家也猜到了。

情形3：兩端均為=，即：

此時線性化方法為：

5.MaxMax/MinMin函數

該部分綜合運用了前述技巧。 以MaxMax函數為例：

首先，令z =max CX，但若此時約束條件寫成z ≥ CX的形式是不行的，因為這樣會讓z 取值到無窮大，故一定要寫出“z ≤ 某個值”的形式。

這時，就需要引入0-1變量和大M，如上圖所示。大家領悟一下。

而yk求和≥1的含義是“至少有一個成立”。實際計算時，隻會有一個k 讓yk=1，其餘yk為0。具體原因，也是夾逼定理的思想，大家多多領會。

同理，MinMin函數的線性化過程如下。

注意，這裡是加号。yk=0該約束不起作用，隻有當yk=1時才會起作用。

後記

篇幅有限，Max/Min函數、含有0-1變量的乘積形式、混合整數形式以及分式目标函數的線性化操作留在下一期講。

總的來說，在遇到非線性問題時，建議大家多多嘗試引入0-1變量和大M的方法。至于構造時是采用≥還是≤，是加還是減的形式（指± M(1 ± y），是需要自己多多嘗試的。

最後，祝大家都能通過線性化技巧發表高水平期刊，祝疫情早日結束。

不聞不若聞之，聞之不若見之；

見之不若知之，知之不若行之。

我是科研小飛，期待您的關注。

歡迎微信搜索“科研小飛”，獲取第一手科研分享文章。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!