線性規劃及單純形法

線性規劃是最優化問題的一種特殊情形，實質是從多個變數中選取一組合適的變數作為解，使得這組變數滿足一組確定的線性式（約束條件），而且使一個線性函式（目標函式）達到最優

〇． 前言

不少人對線性規劃問題還只有初高中“圖解法”的印象，能使用影像直觀明了地解題自然是一種好方法，相信很多人都認為一種好方法夠解決需要解決的問題不就足矣了嗎，其實我也不例外，這也是我開始接觸時的疑惑，但學了一陣子后，我思索了，確實，相比較幾何和組合推理，代數學確實在非數學專業的學生看來不夠討喜，盡管代數學相當強大、相當普適……單純形法就是代數的一個小小縮影，它似乎表面上讓線性規劃問題變得比“圖解法”要復雜得多，但是其超強的普適性著實迷人，我們用計算機來解決線性規劃問題可能只要一句編程，但其背后的數學原理卻如此豐富，我們光線性規劃問題就學了9周（還沒上完），可見它背后的數學文化還是相當值得深挖研討的……<其實為了應試【捂嘴】>
因為單純形法經過本人預習復習后已經有些開竅了，并成功用大M法解決了我的大作業，所以在此不過多贅述，有興趣可以去了解【我更傾向于你沒興趣，看完你就知道了】不過鑒于這周要測驗，而對偶問題還是迷迷糊糊的我決定開始摸魚做筆記<說白了就是應試>，希望敲完這篇，我可以把線性規劃的對偶理論啃下來吧……<說白了還是為了應試>

果然，第一次還是給了數學……哎嘿~~

一． 對偶問題的提出

無論從理論或是實踐角度，對偶理論是線性規劃中的一個最重要和有趣的概念，支持對偶理論的基本思想是，每一個線性規劃問題都存在一個與其對偶的問題，在求出一個問題解的時候，也同時給出了另一問題的解，下面通過實際例子看待對偶問題的經濟意義，
<書本上的例子實在是過于晦澀難懂，于是在網上摘了一點好理解的“栗子”……>

【例一】
某工廠用甲乙兩種資源生產A、B、C、D四種產品，現有資源數、單位產品所需資源數以及單位產品可獲得利潤如下表所示，問如何組織生產能夠使得利潤最大？

根據題意列出的線性規劃不等式是這樣的（大家不用去推出這個公式，目的在于和下文的對偶問題公式形成對比）：

但是現在如果從另一個角度考慮問題，假設該廠不生產A、B、C、D四種產品，而是將甲、乙兩種資源出租給其他單位，其原則是：識別的單位愿意租，又使本單位獲利不低于原利潤，問如何給甲、乙兩種資源定價最合理？

根據題意列出的線性規劃不等式是這樣的：

可以發現，兩個問題下的線性規劃公式很相似（具體的如何轉換會在下文予以說明），那么兩個問題具有什么樣的實際意義呢？可以考慮該廠的目的現在是想要出租資源但是要保證價格不低于資源變成產品所帶來的收益，也就是說第二個問題所求出來的最小(優)值應該是第一個問題求出的最大(優)值，換句話說我們可以通過原問題的對偶問題的最優值來獲得原問題的最優值，但為什么要這樣做呢？直接用原問題來求得最優值不可以嗎？這就是我們第二個問題所涉及的了，

【例二】
① ：仔細對比上圖兩種式子可以發現，圖一中的變數較多而且約束條件較少，相信大家都做過線性規劃的問題，不難發現變數越少，約束條件越多對于我們的求解就越有利，這里也是這個道理，通過將原問題轉換成為其對偶問題，可以使得更加有利于我們求解線性規劃問題，并且從問題一的解答中我們了解到兩種問題“本是同根生”，所以對偶問題其實是有利于我們計算復雜線性規劃問題的一種"輔助"方式，但是，對偶問題一定比原問題變數要少嗎？并不是這樣的，但是我們可以非常容易的判斷出該問題的對偶問題會不會更簡單，這個方法涉及到對偶問題的轉換，我們在第三個問題中進行解答，
② ：其實有時不僅僅是為了減少變數的個數，有的問題甚至必須要通過轉換稱為對偶問題才能夠解決(博主目前的水平下，非數學專業)，比如為了將原式化成標準式時會出現(不)等式右端出現負數的情況，這時如果僅用單純形法是不能夠解決的，因此從這個角度來看，為應對考試對偶問題是必須要學習的，

【例三】
接下來我們將進入實戰，直接用實體來講解原問題的對偶問題是如何化成的，首先我們以下面這個線性規劃問題為例：

1. 對偶問題的目標函式和原問題是相反的，原問題是min則對偶問題為max，并且變數的個數也會發生改變，系數是原問題不等式右端的b值(僅僅是化為對偶問題是不需要將原問題化作標準式的)，根據以上得出目標函式：
   
2. 接下來是寫約束條件，約束條件的書寫是最容易出錯的地方，我們先寫等式的左端，對偶問題等式的左端是根據原問題等式左端豎著來寫的；等式的右端就是直接用原問題目標函式中的系數(先不考慮符號),也就是看如下畫紅框的部分：
   
3. 根據原問題豎著的系數來作為對偶問題每個等式中變數的系數；原問題目標函式的系數，可以得出如下（先仔細看下紅框里的資料是如何得到的）：
   
4. 接著是最為重點的約束條件中的符號和變數的范圍符號，這兩點是根據如下來進行變換：
   
   解釋： 根據max型別寫min型別的變數符號時，要根據max的約束條件符號，并且與之相反；寫min的約束條件符號時，要根據max型別的變數符號，并且與之相同，反之亦然，另外無約束對應的是‘ = ’，最終得到：
   
   至此，我們已經講完了對偶問題的轉換方法，下面再舉一個max型別轉換成min型別的例子，大家可以對照練習加深印象，
   
   <因為殼子比較菜又比較摸魚還不會舉“栗子”，所以第一部分的“栗子”都是從優秀博主家摘的……后面有走心原創哦~~>

二． 對稱形式下對偶問題的一般形式

<你們最愛的 純數學理論來辣~~~>
定義：滿足下列條件的線性規劃問題稱為具有對稱形式：其變數均具有非負約束，其約束條件當目標函式求極大時均取“≤”號，當目標函式求極小時均取“≥”號，
對稱形式下線性規劃原問題的一般形式為：

用yi(i=1,…,m)代替第i種資源的估價，則其對偶問題的一般形式為：

用矩陣形式表示，對稱問題的線性規劃問題的原問題為：

其對偶問題為：

上述對偶問題中令w’=-w，可改寫為：

將上述對稱形式下線性規劃的原問題與對偶問題進行比較，可以列出如下表的對應關系：

如將其作為原問題，并按上表所列對應關系寫出它的對偶問題則有：

再令z=-z’，則上式可改寫為：

可見對偶問題的對偶即原問題，因此將表中右端的線性規劃問題作為原問題，寫出其左端形式的對偶問題，

三． 非對稱形式的原-對偶問題關系

因為并非所有線性規劃問題具有對稱形式，故下面討論一般情況下線性規劃問題如何寫出其對偶問題，考慮下面例子：
<隨便舉個栗子啊>
【例四】 寫出下述線性規劃問題的對偶問題：

解：

為了寫出對偶問題，思路是先將其轉化成對稱形式，再按上表的對應關系來寫，因例中目標函式為max，故約束條件應變換為“≤”號，所有的變數均應為≥0.為此：
<emmm…好像忘了給方程標號了…隨手就標，養成好習慣>

<好了，go on…>

（1）約束條件b兩端乘上“-1”；
（2）將約束條件c先等價轉換為x1+x2+x3≤4和x1+x2+x3≥4，再變換為x1+x2+x3≤4和-x1-x2-x3≤-4；
（3）令x2’=-x2，所以x2’≥0；
（4）令x3=x3’-x3’’，其中x3’≥0，x3’'≥0，

由此【例四】可變換成具有如下對稱形式的線性規劃問題：

令對應上述4個約束條件的對偶變數分別為y_1,y_2^’,y_3’,y_3^’’，按表的對應關系寫出其對偶問題為：

再令y2=y2’,y3=y3’-y3’’,將第三四個約束條件改為一個等式-5y1-6y2’+y3=3，于是有：

將上述對偶問題同【一】的原問題對比發現，無論對稱或非對稱的線性規劃問題在寫出其對偶向題時，表中前4行的對應關系都適用，區別的只是約束條件的形式與其對應變數的取值，根據本例中約束和變數的對應關系，下面將對稱或不對稱線性規劃原問題同對偶問題的對應關系，統一歸納為下表所示形式：

<看到這里是不是感jio要吐了……而這才只到如何寫線性規劃的對偶問題，你還沒解呢……急啥，快到性質了……>

四． 對偶問題的基本性質

<這里才是你真正應該感jio到要吐的地方…>
<還是決定手寫，這里敲公式多半會哭死……>

1. 弱對偶性

·弱對偶性的推論：
（1） 原問題任一可行解的目標函式值時其對偶問題目標函式值的下界；反之對偶問題任一可行解的目標函式值是其原問題目標函式值的上界，<有點兒繞，但不是不好理解>
（2） 如原問題有可行解且目標函式值無界（具有無界解），則其對偶問題無可行解；反之對偶問題有可行解且目標函式值無界，則原問題無可行解（注意：本點性質的逆不成立，當對偶問題無可行解時，其原問題或具有無界解或無可行解，反之亦然），
（3） 若原問題有可行解而其對偶問題無可行解，則原問題目標函式值無界；反之對偶問題有可行解而其原問題無可行解時，其對偶問題的目標函式值無界，

2. 最優性

3. 強對偶性（或稱對偶原理）

若原問題及其對偶問題均具有可行解，則兩者均具有最優解，且它們最優解的目標函式值相等，

證 由于兩者均有可行解，根據弱對偶性的推論（1），對原問題的目標函式值具有上界，對偶問題的目標函式值具有下界，因此兩者均具有最優解，當原問題為最優解時，其對偶問題的解為可行解，且有z=w，由最優性知，這時兩者的解均為最優解，

4. 互補松弛性

5.基解互補性
原問題及其對偶問題之間存在一對互補的基解，其中原問題的松弛變數對應對偶問題的變數對偶問題的剩余變數對應原問題的變數.這些互相對應的變數如果在一個問題的解中是基變數則在另一個問題的解中是非基變數；將這對互補的集解分別帶入原問題和對偶問題的目標函式中有 z = w

五． 對偶問題的單純形法描述

<聽嗦考試必考……但其實我并不熟悉，慌~~>
既然是只菜狗，那就參考一下大佬的吧：
參考鏈接：
對偶問題的單純形法

六． 影子價格

首先，我們先要認識到互補松弛性的作用：
① 簡化求對偶問題最優解程序 : 已知一個線性規劃問題的最優解 , 可以 簡化求另外一個問題最優解的程序 , 避免使用兩次單純形法求解 ;
② 影子價格問題 : 使用互補松弛定理可以進行一些 經濟解釋 , 如影子價格問題 ;
影子價格 是 對偶問題的 經濟解釋 ;

影子價格是對偶問題的變數值
<懶了，不想舉“栗子”了，有關邊際價格的“栗子”還挺多的，有興趣可以在*“參考”*里摘摘>

七． 利用Matlab解決線性規劃問題

因為畢竟是計算機系的在讀小學生，那就提一嘴實戰應用咯，因為linprog這個函式比較常用，也是建模賽事中最最最基礎的數學模型了，所以對于大家也不陌生，不過你想要用好它可不止單純會敲一個linprog那么easy，至少你要知道線性規劃的標準型，這樣才能套對引數，合理求解線性規劃問題，
所以簡單截個圖：<就是懶？不（shi）是（de）>

八． 參考

鏈接[1]: https://blog.csdn.net/qq_43539633/article/details/109150749
鏈接[2]: https://blog.csdn.net/PursueLuo/article/details/112251520
鏈接[3]: https://blog.csdn.net/weixin_43848054/article/details/105748797
鏈接[4]: https://blog.csdn.net/shulianghan/article/details/112096559
《運籌學教程》 胡運權 郭耀煌