以下內容全是口胡，請謹慎觀看 ——From ATP

什么是線性規劃？

參見高中數學必修五第三章

根據ATP的理解。。。線性規劃就是設出一些變量，給出一些對于變量取值的限制，同時給出一個與這些變量相關的目標函數，要求在滿足限制的前提下最大化或最小化目標函數。

舉個例子：設有變量x1,x2,x3$x_1,x_2,x_3$，那么下面這一坨東西：

Maxmize   5?x1+2?x2?3?x3$Maxmize/space/space/space 5*x_1+2*x_2-3*x_3$ 滿足約束： 2?x1+3?x3≤5$2*x_1+3*x_3 /leq 5$ 3?x2?4?x3≤8$3*x_2-4*x_3 /leq 8$ 4?x1?2?x2≤7$4*x_1-2*x_2 /leq 7$ x1,x2,x3≥0$x_1,x_2,x_3 /geq 0$

就是一個線性規劃啦。。（上面那一坨東西是ATP隨便打上去的有沒有解就不一定了= =）

形式化地，設x$x$為n維列向量代表設定的變量，A$A$為m*n的矩陣代表每個限制中每個變量的系數，B$B$為m維列向量代表每個限制中的常數項，C$C$為n維行向量代表目標函數的系數。舉個栗子說，對于上面那一坨東西，它的各個元素表示如下：

A=???20403?23?40??? $$A=/begin{bmatrix} 2 & 0 & 3// 0 & 3 & -4// 4 & -2 & 0// /end{bmatrix}$$ B=???587??? $$B=/begin{bmatrix}5//8//7///end{bmatrix}$$ C=[52?3] $$C=/begin{bmatrix}5 & 2 & -3/end{bmatrix}$$

我們在這里僅討論線性規劃的標準型。線性規劃的標準型表示如下： Maxmize    Cx$Maxmize/space/space/space/space Cx$ S.T.   Ax≤B,x≥0$S.T. /space/space/space Ax /leq B,x /geq 0$

但是很多時候好像遇到的線性規劃并不是標準型？難道它們不能做嗎。。。其實并不是，在大多數情況下，不是標準型的線性規劃都可以通過做一些適當的轉化表示成標準型。比如……

目標函數要求最小化（Minmize$Minmize$）? 似乎可以把所有系數取反，求得答案以后再反回來？ 在某些情況下，下面提到的“對偶定理”會更加好用。

首先線性規劃的限制應該都是大于等于或者小于等于這種形式的（不然計算機怎么搞出“無限接近”這種類型的答案來= =），但是在標準型里面限制都要求是小于等于，如果遇到別的符號？ 如果是帶“≥$/geq$”的限制，直接把所有系數取反就可以；而如果是帶“=”的限制，例如a=b$a=b$，我們可以轉化成a≤b$a /leq b$和b≤a$b /leq a$兩個限制。

總之通過類似這樣的變換我們可以把任意的線性規劃轉化為標準型，并且它們的最優解都是不變的。

求解線性規劃——單純形算法

求解線性規劃最常用的算法是單純形算法。它的理論時間復雜度是指數級別的。。但是跑得奇快無比啊并且也基本上卡不掉。。所以放心大膽用就是了。。

單純形算法的幾何意義很多地方都有解釋。。但是這里ATP主要解釋它在代數方面的原理。

首先，為了對線性規劃使用單純形算法，我們需要把線性規劃轉化為“松弛型”，也就是說把所有的不等式變為等式。以下都用m來表示限制個數，n來表示變量個數。

為了做到這一點，我們對于每一個形如∑i=1nAk,ixi≤Bk$/sum/limits_{i=1}^n A_{k,i}x_i /leq B_k$的限制增加一個叫做“基變量”的東西，把它稱作yk$y_k$。我們保證yk≥0$y_k /geq 0$，那么現在每條限制都變成了形如yk+∑i=1nAk,ixi=Bk$y_k +/sum/limits_{i=1}^n A_{k,i}x_i=B_k$的形式！

相對的那我們就把所有xk$x_k$叫做“非基變量”好了。顯然目標函數只會涉及到非基變量。現在我們做出一個假設就是如果把所有xi$x_i$都取到0，那么它是一組能夠滿足所有限制條件的可行解。——實際情況下很多時候并不是這樣的，這種情況在下面的對偶原理部分中進行討論，現在先假設它是成立的。

那么我們把所有的xi$x_i$都取0，可以計算出目標函數的一個值。但是顯然它不一定是最優的。觀察目標函數，有些xi$x_i$的系數是大于0的，那么如果我們能夠讓這些變量增大，我們就可以得到一組更優的解。但是如果目標函數里面不存在系數為正數的xi$x_i$，那么如果把所有xi$x_i$都取0就能夠得到最優解——所以前面那個假設是必要的。而單純形算法就是要對目標函數和約束條件作出適當的變形，在不改變最優解的情況下把目標函數里面所有的系數都變成負數。

先貼代碼，在下面解釋：

上面的Simplex過程是單純形算法的主過程。首先每次先找到第一個系數大于0的非基變量。這里有一個叫做Bland法則的東西，就是說一定要選第一個系數大于0的，不然容易被特殊數據卡成死循環。。然而ATP并沒有試過= =

選中的這個非基變量就是上面的e。如果沒有找到這樣的變量，說明算法已經完成了，目標函數中的所有系數都變成負數了，就可以退出了。否則我們要把目標函數中xe$x_e$的系數變成負數。上面提到過，當前的初始可行解為所有變量都取0，那么我們想要做的是盡量增大某個系數為正數的變量，也就是當前選擇的xe$x_e$。但是xe$x_e$最大可以增大到多大呢？這就要看約束條件了。接下來的一步就是枚舉所有約束條件了。考慮每個含有xe$x_e$的約束條件∑i=1nAk,ixi≤Bk$/sum/limits_{i=1}^n A_{k,i}x_i /leq B_k$，因為已經保證所有的xi$x_i$都是大于0的，所以要讓xe$x_e$盡量增大當然要把除了xe$x_e$的所有變量都取0。那么當前約束下xe$x_e$能夠取到的最大值就是BkAk,e$B_k /over A_{k,e}$。

不同的約束條件產生的BkAk,e$B_k /over A_{k,e}$是不一樣的，顯然為了正確地“增大”xe$x_e$，我們需要找到所有約束條件產生的最小的BkAk,e$B_k /over A_{k,e}$。如果找不到，就說明xe$x_e$最大可以增大到正無窮，這個線性規劃就是無解的。

否則我們能夠找到一個約束條件l$l$，滿足BlAl,e$B_l /over A_{l,e}$是最緊的那個限制。那么我們就要開始對約束條件進行變形了。變形能夠進行的基礎就是因為添加了基變量yl$y_l$使得所有約束條件變成了“=”的形式，我們可以隨便把每一項挪來挪去加加減減，都不會改變這個約束條件的本質。

基變量yl$y_l$的作用還不止如此，我們接下來要做的變形工作實際上是要用yl$y_l$替換掉xe$x_e$，也就是改變基變量與非基變量的集合，使得yl$y_l$成為新的一個非基變量，xe$x_e$成為新的一個基變量。這樣一來就肯定要把整個約束條件表示成為xe=...$x_e=...$的形式，而因為一開始xe$x_e$和yl$y_l$在等號同側而現在變成了異側，那么yl$y_l$的系數肯定就變成了相反數。那把它往目標函數里一代的時候，就會有一個基變量的系數變成負數了！

于是上面的pivot過程就是來做這樣的變形的。這玩意兒好像學名叫“轉軸”操作，好像來源于單純形算法的幾何意義。。不管它不管它。

pivot過程是這樣的：

這里的l,e$l,e$意義和上面相同。在pivot過程的第一步，我們需要先對選定的這個約束條件l$l$進行變形，把它由yk+∑i=1nAl,ixi=Bl$y_k +/sum/limits_{i=1}^n A_{l,i}x_i=B_l$的形式變成xe=?1×∑i=1,i≠enAl,ixi?yl+Bl$x_e=-1 /times /sum/limits_{i=1,i /neq e}^n A_{l,i}x_i-y_l+B_l$的形式，這樣才能把它扔到別的含有xe$x_e$的約束中進行替換。

為了替換方便我們要把xe$x_e$的系數變為1，那么就要把所有的變量都除以xe$x_e$原來的系數Al,e$A_{l,e}$。而對于Al,e$A_{l,e}$這個位置的數字我們又需要特殊處理。因為我們要把xe$x_e$替換為yl$y_l$，所以還要把Al,e$A_{l,e}$這個位置變成yl$y_l$應該有的系數。yl$y_l$原本系數為1，現在當然就要變成1Al,e$1 /over A_{l,e}$啦。

這樣我們就完成了過程的第一步，也就是上面代碼里前4行的內容。

接下來我們要對所有除了約束條件l$l$以外的約束條件進行變形。枚舉所有不是l$l$并且xe$x_e$的系數不是0的約束條件，我們要把xe=...$x_e=...$這個式子給帶進去消掉xe$x_e$。設當前的約束為i$i$，那么我們就可以把約束i中含有xe$x_e$的項Ai,e?xe$A_{i,e}*x_e$給利用上面提到的式子給xe=?1×∑i=1,i≠enAl,ixi?yl+Bl$x_e=-1 /times /sum/limits_{i=1,i /neq e}^n A_{l,i}x_i-y_l+B_l$替換掉。

很容易發現替換以后約束條件i$i$中除了Ai,e$A_{i,e}$以外的項j，全都減去了Ai,e?Al,j$A_{i,e}*A_{l,j}$，而常數項Bi$B_i$減去了Ai,e?Bl$A_{i,e}*B_l$。而同樣的，對于Ai,e$A_{i,e}$這一項我們要特殊處理，把它變成現在yl$y_l$這個變量該有的系數，也就是?Al,e?Ai,e$-A_{l,e}*A_{i,e}$。

最后是對于目標函數的處理，同樣是把xe$x_e$消掉，把yl$y_l$引入。而我們用一個單獨的變量v來記錄目標函數中的常數項，一開始目標函數中是沒有常數項的，隨著我們的代換會出現一個漸漸增大的常數項。顯然Bl$B_l$就是貢獻常數項的東西，每次操作它會為常數項貢獻Ce?Bl$C_e*B_l$這么多。然后接下來的代換過程就是和上面替換Ai,e$A_{i,e}$的時候相似的了，這里不再贅述（ATP覺得自己啰嗦的已經夠多的了qwq）

最后當目標函數中所有系數都變成負數的時候，記錄的v就是線性規劃的最優解啦。

對偶原理

前面我們所有的討論都基于一個假設：所有非基變量取0是一組可行解。

但是很多時候我們會碰到這樣的線性規劃： Minmize    Cx$Minmize/space/space/space/space Cx$ S.T.   Ax≥B,x≥0$S.T. /space/space/space Ax /geq B,x /geq 0$

把所有系數取反？但是取反這種操作是不會改變約束條件的本質的。這個時候我們就會用到對偶原理了

形式化的，對偶原理就是說：

Minmize    Cx$Minmize/space/space/space/space Cx$ S.T.   Ax≥B,x≥0$S.T. /space/space/space Ax /geq B,x /geq 0$ 和 Maxmize    BTx$Maxmize/space/space/space/space B^Tx$ S.T.   ATy≤CT,y≥0$S.T. /space/space/space A^Ty /leq C^T,y /geq 0$

這兩個線性規劃是等價的。

顯然，如果我們遇到了一個這種所有非基變量取0不是可行解的線性規劃，我們可以用對偶原理把它“轉”一下，就會變成一個所有非基變量取0是可行解的線性規劃，就可以用單純形求解了。

證明？好像不大會用到，ATP也不會。。。

不過想要理解一下對偶原理的話，這篇文章還是不錯的[戳這里]。。。

貼幾個板子題吧

據說網絡流都可以用線性規劃做？

參考曹欽翔《線性規劃與網絡流》。。。

ATP其實沒怎么看那個。。。

主要問題是感覺里面說的基本上就是如何把現成的網絡流模型改造成線性規劃。。。

但是既然都有了網絡流模型干嘛還要改線性規劃啊。。。(?Д?*)?

據說線性規劃也可以用費用流做？

這種方法是ATP一開始看線性規劃的時候稀里糊涂學過來的。。也沒大用過。。在這里提一句吧。。

例：BZOJ1061 志愿者招募

用費用流做線性規劃的時候，我們要做的第一步仍然是列出不等式并且把它們轉化成松弛型。接下來以這個題的樣例來舉例說明操作過程。

首先設每一種志愿者的招募人數為xi$x_i$，我們可以列出這樣的三個松弛型約束條件：

添加兩個約束條件P0=0,P4=0$P_0=0,P_4=0$，然后用Pi+1?Pi$P_{i+1}-P_i$，我們就得到了一組新的等式：

我們把它們化成這種形式是有原因的，因為我們求解的方法是網絡流，而這組等式滿足一個十分關鍵的性質——它們相加的和等于0。這可以和網絡流中的流量平衡結合起來。那么我們可以把上面的每個等式看成一個點并且按照變量的正負進行連邊，并且設定“流出為正，流入為負”，那么源點S作為唯一只有流出流量的點，它流出的流量可以看成等式右邊那些正數；匯點T作為唯一只有流入流量的點，它流入的流量可以看成等式右邊那些負數。然后我們找到每個變量xi$x_i$和yi$y_i$正值和負值出現的等式Ps$P_s$和Pt$P_t$，然后連一條Ps$P_s$到Pt$P_t$的邊。而這道題因為有最小化費用的要求，所以我們在邊上加費用。對于每個xi$x_i$，每使用一單位流量就要增加vi$v_i$的費用，而yi$y_i$是添加的輔助變量，對結果沒有影響，所以費用為0即可。

其實這個過程就是將費用流問題轉線性規劃問題的逆過程。。