蘇州其然軟件開發(fā)培訓(xùn)

自學(xué)java與java培訓(xùn)該如何選擇

從事IT培訓(xùn)行業(yè)這些年，身邊經(jīng)常有朋友來咨詢，問現(xiàn)在是否可以加入這個(gè)高薪行業(yè)，Java學(xué)習(xí)難不難，需要哪些條件?

在軟件開發(fā)設(shè)計(jì)行業(yè)當(dāng)中，使用**多的編程語(yǔ)言就屬Java軟件開發(fā)了，很多人都想在Java編程開發(fā)領(lǐng)域?qū)で笠环莨ぷ鳌?/span>

Java是當(dāng)前世界上比較流行的計(jì)算機(jī)編程語(yǔ)言，Java徹底改變了人們的生活，國(guó)內(nèi)的開發(fā)人才需求量仍然在不斷的增長(zhǎng)，主要原因還是在于移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，衍生出一大批的新生企業(yè)，創(chuàng)業(yè)公司，預(yù)計(jì)在未來5年內(nèi)Java軟件開發(fā)人才的需求將會(huì)遠(yuǎn)大于供給，其中java程序員、java工程師**為缺乏。

自學(xué)java與java培訓(xùn)是兩個(gè)繞不開的話題，兩者的區(qū)別，前者知識(shí)是自己搜尋的，買書看或者網(wǎng)上找視頻看，而后者，技術(shù)知識(shí)是老師教的，作為一個(gè)普通大學(xué)生實(shí)際上任何人都能夠自學(xué)，只不過聰明程度和堅(jiān)持的時(shí)間長(zhǎng)短不同，花費(fèi)的時(shí)間長(zhǎng)一點(diǎn)短一點(diǎn)而已。

學(xué)習(xí)關(guān)乎到時(shí)間和金錢，沒有效果和質(zhì)量的培訓(xùn)，其實(shí)是沒有任何意義的。Java培訓(xùn)班有哪些呢?市面上的Java培訓(xùn)良莠不齊，選擇時(shí)應(yīng)該慎重些。Java致力于打造符合企業(yè)需求的全能型人才。課程定位定位中高級(jí)JAVA開發(fā)工程師，課程內(nèi)容涉及面廣，內(nèi)容深。課程涵蓋了Java、Web，數(shù)據(jù)庫(kù)，企業(yè)流行框架，Java等企業(yè)**佳實(shí)踐、云計(jì)算大數(shù)據(jù)課程、內(nèi)容由淺入深，剖析原理，讓學(xué)員掌握實(shí)用技術(shù)，做企業(yè)和社會(huì)需要的稀缺人才。

此外，Java培訓(xùn)將為你提供就業(yè)保障，開設(shè)有就業(yè)指導(dǎo)課，設(shè)有專門的就業(yè)指導(dǎo)老師，在畢業(yè)前期，畢業(yè)之際，就業(yè)老師會(huì)為你做專門的就業(yè)指導(dǎo)，更有職業(yè)素養(yǎng)課程，不僅將你打造成Java開發(fā)技術(shù)達(dá)人，更是一位懂得職場(chǎng)之道的合格就業(yè)者。還有豐富的Java學(xué)習(xí)視頻免費(fèi)為你提供學(xué)習(xí)。

線性規(guī)劃——單純形算法の板子

>

以下內(nèi)容全是口胡，請(qǐng)謹(jǐn)慎觀看 ——From ATP

什么是線性規(guī)劃？

參見高中數(shù)學(xué)必修五第三章

根據(jù)ATP的理解。。。線性規(guī)劃就是設(shè)出一些變量，給出一些對(duì)于變量取值的限制，同時(shí)給出一個(gè)與這些變量相關(guān)的目標(biāo)函數(shù)，要求在滿足限制的前提下**大化或**小化目標(biāo)函數(shù)。

舉個(gè)例子：設(shè)有變量x1,x2,x3 $x_1,x_2,x_3，那么下面這一坨東西： </p> <p> <nobr>Maxmize&nbsp;&nbsp;&nbsp;5?x1 2?x2?3?x3</nobr> <script type="math/tex" id="MathJax-Element-4">Maxmize\space\space\space 5*x_1 2*x_2-3*x_3 滿足約束： <nobr>2?x1 3?x3≤5</nobr> <script type="math/tex" id="MathJax-Element-5">2*x_1 3*x_3 \leq 5 <nobr>3?x2?4?x3≤8</nobr> <script type="math/tex" id="MathJax-Element-6">3*x_2-4*x_3 \leq 8 <nobr>4?x1?2?x2≤7</nobr> <script type="math/tex" id="MathJax-Element-7">4*x_1-2*x_2 \leq 7 <nobr>x1,x2,x3≥0</nobr> <script type="math/tex" id="MathJax-Element-8">x_1,x_2,x_3 \geq 0 </p> <p> 就是一個(gè)線性規(guī)劃啦。。（上面那一坨東西是ATP隨便打上去的有沒有解就不一定了= =） </p> <p> 形式化地，設(shè)<nobr>x</nobr> <script type="math/tex" id="MathJax-Element-9">x為n維列向量代表設(shè)定的變量，<nobr>A</nobr> <script type="math/tex" id="MathJax-Element-10">A為m*n的矩陣代表每個(gè)限制中每個(gè)變量的系數(shù)，<nobr>B</nobr> <script type="math/tex" id="MathJax-Element-11">B為m維列向量代表每個(gè)限制中的常數(shù)項(xiàng)，<nobr>C</nobr> <script type="math/tex" id="MathJax-Element-12">C為n維行向量代表目標(biāo)函數(shù)的系數(shù)。舉個(gè)栗子說，對(duì)于上面那一坨東西，它的各個(gè)元素表示如下： </p> <p> <nobr>A=???20403?23?40???</nobr> <script type="math/tex; mode=display" id="MathJax-Element-13">A=\begin{bmatrix} 2 & 0 & 3\ 0 & 3 & -4\ 4 & -2 & 0\ \end{bmatrix} <nobr>B=???587???</nobr> <script type="math/tex; mode=display" id="MathJax-Element-14">B=\begin{bmatrix} 5\8\7\\end{bmatrix} <nobr>C=[52?3]</nobr> <script type="math/tex; mode=display" id="MathJax-Element-15">C=\begin{bmatrix} 5 & 2 & -3 \end{bmatrix} </p> <p> 我們?cè)谶@里僅討論線性規(guī)劃的標(biāo)準(zhǔn)型。線性規(guī)劃的標(biāo)準(zhǔn)型表示如下： <nobr>Maxmize&nbsp;&nbsp;&nbsp;&nbsp;Cx</nobr> <script type="math/tex" id="MathJax-Element-16">Maxmize\space\space\space\space Cx <nobr>S.T.&nbsp;&nbsp;&nbsp;Ax≤B,x≥0</nobr> <script type="math/tex" id="MathJax-Element-17">S.T. \space\space\space Ax \leq B,x \geq 0 </p> <p> 但是很多時(shí)候好像遇到的線性規(guī)劃并不是標(biāo)準(zhǔn)型？難道它們不能做嗎。。。其實(shí)并不是，在大多數(shù)情況下，不是標(biāo)準(zhǔn)型的線性規(guī)劃都可以**做一些適當(dāng)?shù)霓D(zhuǎn)化表示成標(biāo)準(zhǔn)型。比如…… </p> <p> 目標(biāo)函數(shù)要求**小化（<nobr>Minmize</nobr> <script type="math/tex" id="MathJax-Element-18">Minmize）? 似乎可以把所有系數(shù)取反，求得答案以后再反回來？ 在某些情況下，下面提到的“對(duì)偶定理”會(huì)更加好用。 </p> <p> 首先線性規(guī)劃的限制應(yīng)該都是大于等于或者小于等于這種形式的（不然計(jì)算機(jī)怎么搞出“無限接近”這種類型的答案來= =），但是在標(biāo)準(zhǔn)型里面限制都要求是小于等于，如果遇到別的符號(hào)？ 如果是帶“<nobr>≥</nobr> <script type="math/tex" id="MathJax-Element-19">\geq”的限制，直接把所有系數(shù)取反就可以；而如果是帶“=”的限制，例如<nobr>a=b</nobr> <script type="math/tex" id="MathJax-Element-20">a=b，我們可以轉(zhuǎn)化成<nobr>a≤b</nobr> <script type="math/tex" id="MathJax-Element-21">a \leq b和<nobr>b≤a</nobr> <script type="math/tex" id="MathJax-Element-22">b \leq a兩個(gè)限制。 </p> <p> 總之**類似這樣的變換我們可以把任意的線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)型，并且它們的**優(yōu)解都是不變的。 </p> <h2 id="求解線性規(guī)劃單純形算法"> 求解線性規(guī)劃——單純形算法 </h2> <p> 求解線性規(guī)劃**常用的算法是單純形算法。它的理論時(shí)間復(fù)雜度是指數(shù)級(jí)別的。。但是跑得奇快無比啊并且也基本上卡不掉。。所以放心大膽用就是了。。 </p> <p> 單純形算法的幾何意義很多地方都有解釋。。但是這里ATP主要解釋它在代數(shù)方面的原理。 </p> <p> 首先，為了對(duì)線性規(guī)劃使用單純形算法，我們需要把線性規(guī)劃轉(zhuǎn)化為“松弛型”，也就是說把所有的不等式變?yōu)榈仁健Ｒ韵露加胢來表示限制個(gè)數(shù)，n來表示變量個(gè)數(shù)。 </p> <p> 為了做到這一點(diǎn)，我們對(duì)于每一個(gè)形如<nobr>∑i=1nAk,ixi≤Bk</nobr> <script type="math/tex" id="MathJax-Element-23">\sum\limits_{i=1}^n A_{k,i}x_i \leq B_k的限制增加一個(gè)叫做“基變量”的東西，把它稱作<nobr>yk</nobr> <script type="math/tex" id="MathJax-Element-24">y_k。我們保證<nobr>yk≥0</nobr> <script type="math/tex" id="MathJax-Element-25">y_k \geq 0，那么現(xiàn)在每條限制都變成了形如<nobr>yk ∑i=1nAk,ixi=Bk</nobr> <script type="math/tex" id="MathJax-Element-26">y_k \sum\limits_{i=1}^n A_{k,i}x_i=B_k的形式！ </p> <p> 相對(duì)的那我們就把所有<nobr>xk</nobr> <script type="math/tex" id="MathJax-Element-27">x_k叫做“非基變量”好了。顯然目標(biāo)函數(shù)只會(huì)涉及到非基變量。現(xiàn)在我們做出一個(gè)假設(shè)就是如果把所有<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-28">x_i都取到0，那么它是一組能夠滿足所有限制條件的可行解?！獙?shí)際情況下很多時(shí)候并不是這樣的，這種情況在下面的對(duì)偶原理部分中進(jìn)行討論，現(xiàn)在先假設(shè)它是成立的。 </p> <p> 那么我們把所有的<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-29">x_i都取0，可以計(jì)算出目標(biāo)函數(shù)的一個(gè)值。但是顯然它不一定是**優(yōu)的。觀察目標(biāo)函數(shù)，有些<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-30">x_i的系數(shù)是大于0的，那么如果我們能夠讓這些變量增大，我們就可以得到一組更優(yōu)的解。但是如果目標(biāo)函數(shù)里面不存在系數(shù)為正數(shù)的<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-31">x_i，那么如果把所有<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-32">x_i都取0就能夠得到**優(yōu)解——所以前面那個(gè)假設(shè)是必要的。而單純形算法就是要對(duì)目標(biāo)函數(shù)和約束條件作出適當(dāng)?shù)淖冃危诓桓淖?*優(yōu)解的情況下把目標(biāo)函數(shù)里面所有的系數(shù)都變成負(fù)數(shù)。 </p> <p> 先貼代碼，在下面解釋： </p> double Simplex(){ int l,e; double t; while (true){ e=n 1; for (int i=1;i&lt;=n;i ) if (C[i]&gt;eps){e=i;break;} if (e==n 1) break; t=inf;l=0; for (int i=1;i&lt;=m;i ) if (A[i][e]&gt;eps&amp;&amp;t&gt;B[i]/A[i][e]){ t=B[i]/A[i][e];l=i; } if (t==inf) return inf; pivot(l,e); } return v; } <p> 上面的Simplex過程是單純形算法的主過程。首先每次先找到**個(gè)系數(shù)大于0的非基變量。這里有一個(gè)叫做Bland法則的東西，就是說一定要選**個(gè)系數(shù)大于0的，不然容易被特殊數(shù)據(jù)卡成死循環(huán)。。然而ATP并沒有試過= = </p> <p> 選中的這個(gè)非基變量就是上面的e。如果沒有找到這樣的變量，說明算法已經(jīng)完成了，目標(biāo)函數(shù)中的所有系數(shù)都變成負(fù)數(shù)了，就可以退出了。否則我們要把目標(biāo)函數(shù)中<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-33">x_e的系數(shù)變成負(fù)數(shù)。上面提到過，當(dāng)前的初始可行解為所有變量都取0，那么我們想要做的是盡量增大某個(gè)系數(shù)為正數(shù)的變量，也就是當(dāng)前選擇的<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-34">x_e。但是<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-35">x_e**大可以增大到多大呢？這就要看約束條件了。接下來的一步就是枚舉所有約束條件了?？紤]每個(gè)含有<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-36">x_e的約束條件<nobr>∑i=1nAk,ixi≤Bk</nobr> <script type="math/tex" id="MathJax-Element-37">\sum\limits_{i=1}^n A_{k,i}x_i \leq B_k，因?yàn)橐呀?jīng)保證所有的<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-38">x_i都是大于0的，所以要讓<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-39">x_e盡量增大當(dāng)然要把除了<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-40">x_e的所有變量都取0。那么當(dāng)前約束下<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-41">x_e能夠取到的**大值就是<nobr>BkAk,e</nobr> <script type="math/tex" id="MathJax-Element-42">B_k \over A_{k,e}。 </p> <p> 不同的約束條件產(chǎn)生的<nobr>BkAk,e</nobr> <script type="math/tex" id="MathJax-Element-43">B_k \over A_{k,e}是不一樣的，顯然為了正確地“增大”<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-44">x_e，我們需要找到所有約束條件產(chǎn)生的**小的<nobr>BkAk,e</nobr> <script type="math/tex" id="MathJax-Element-45">B_k \over A_{k,e}。如果找不到，就說明<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-46">x_e**大可以增大到正無窮，這個(gè)線性規(guī)劃就是無解的。 </p> <p> 否則我們能夠找到一個(gè)約束條件<nobr>l</nobr> <script type="math/tex" id="MathJax-Element-47">l，滿足<nobr>BlAl,e</nobr> <script type="math/tex" id="MathJax-Element-48">B_l \over A_{l,e}是**緊的那個(gè)限制。那么我們就要開始對(duì)約束條件進(jìn)行變形了。變形能夠進(jìn)行的基礎(chǔ)就是因?yàn)樘砑恿嘶兞?nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-49">y_l使得所有約束條件變成了“=”的形式，我們可以隨便把每一項(xiàng)挪來挪去加加減減，都不會(huì)改變這個(gè)約束條件的本質(zhì)。 </p> <p> 基變量<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-50">y_l的作用還不止如此，我們接下來要做的變形工作實(shí)際上是要用<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-51">y_l替換掉<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-52">x_e，也就是改變基變量與非基變量的集合，使得<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-53">y_l成為新的一個(gè)非基變量，<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-54">x_e成為新的一個(gè)基變量。這樣一來就肯定要把整個(gè)約束條件表示成為<nobr>xe=...</nobr> <script type="math/tex" id="MathJax-Element-55">x_e=...的形式，而因?yàn)橐婚_始<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-56">x_e和<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-57">y_l在等號(hào)同側(cè)而現(xiàn)在變成了異側(cè)，那么<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-58">y_l的系數(shù)肯定就變成了相反數(shù)。那把它往目標(biāo)函數(shù)里一代的時(shí)候，就會(huì)有一個(gè)基變量的系數(shù)變成負(fù)數(shù)了！ </p> <p> 于是上面的pivot過程就是來做這樣的變形的。這玩意兒好像學(xué)名叫“轉(zhuǎn)軸”操作，好像來源于單純形算法的幾何意義。。不管它不管它。 </p> <p> pivot過程是這樣的： </p> void pivot(int l,int e){ B[l]/=A[l][e]; for (int i=1;i&lt;=n;i ) if (i!=e) A[l][i]/=A[l][e]; A[l][e]=1/A[l][e]; for (int i=1;i&lt;=m;i ) if (i!=l&amp;&amp;fabs(A[i][e])&gt;eps){ B[i]-=B[l]*A[i][e]; for (int j=1;j&lt;=n;j ) if (j!=e) A[i][j]-=A[l][j]*A[i][e]; A[i][e]=-A[l][e]*A[i][e]; } v =C[e]*B[l]; for (int i=1;i&lt;=n;i ) if (i!=e) C[i]-=C[e]*A[l][i]; C[e]=-C[e]*A[l][e]; } <p> 這里的<nobr>l,e</nobr> <script type="math/tex" id="MathJax-Element-59">l,e意義和上面相同。在pivot過程的**步，我們需要先對(duì)選定的這個(gè)約束條件<nobr>l</nobr> <script type="math/tex" id="MathJax-Element-60">l進(jìn)行變形，把它由<nobr>yk ∑i=1nAl,ixi=Bl</nobr> <script type="math/tex" id="MathJax-Element-61">y_k \sum\limits_{i=1}^n A_{l,i}x_i=B_l的形式變成<nobr>xe=?1×∑i=1,i≠enAl,ixi?yl Bl</nobr> <script type="math/tex" id="MathJax-Element-62">x_e=-1 \times \sum\limits_{i=1,i \neq e}^n A_{l,i}x_i-y_l B_l的形式，這樣才能把它扔到別的含有<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-63">x_e的約束中進(jìn)行替換。 </p> <p> 為了替換方便我們要把<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-64">x_e的系數(shù)變?yōu)?，那么就要把所有的變量都除以<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-65">x_e原來的系數(shù)<nobr>Al,e</nobr> <script type="math/tex" id="MathJax-Element-66">A_{l,e}。而對(duì)于<nobr>Al,e</nobr> <script type="math/tex" id="MathJax-Element-67">A_{l,e}這個(gè)位置的數(shù)字我們又需要特殊處理。因?yàn)槲覀円?nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-68">x_e替換為<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-69">y_l，所以還要把<nobr>Al,e</nobr> <script type="math/tex" id="MathJax-Element-70">A_{l,e}這個(gè)位置變成<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-71">y_l應(yīng)該有的系數(shù)。<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-72">y_l原本系數(shù)為1，現(xiàn)在當(dāng)然就要變成<nobr>1Al,e</nobr> <script type="math/tex" id="MathJax-Element-73">1 \over A_{l,e}啦。 </p> <p> 這樣我們就完成了過程的**步，也就是上面代碼里前4行的內(nèi)容。 </p> <p> 接下來我們要對(duì)所有除了約束條件<nobr>l</nobr> <script type="math/tex" id="MathJax-Element-74">l以外的約束條件進(jìn)行變形。枚舉所有不是<nobr>l</nobr> <script type="math/tex" id="MathJax-Element-75">l并且<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-76">x_e的系數(shù)不是0的約束條件，我們要把<nobr>xe=...</nobr> <script type="math/tex" id="MathJax-Element-77">x_e=...這個(gè)式子給帶進(jìn)去消掉<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-78">x_e。設(shè)當(dāng)前的約束為<nobr>i</nobr> <script type="math/tex" id="MathJax-Element-79">i，那么我們就可以把約束i中含有<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-80">x_e的項(xiàng)<nobr>Ai,e?xe</nobr> <script type="math/tex" id="MathJax-Element-81">A_{i,e}*x_e給利用上面提到的式子給<nobr>xe=?1×∑i=1,i≠enAl,ixi?yl Bl</nobr> <script type="math/tex" id="MathJax-Element-82">x_e=-1 \times \sum\limits_{i=1,i \neq e}^n A_{l,i}x_i-y_l B_l替換掉。 </p> <p> 很容易發(fā)現(xiàn)替換以后約束條件<nobr>i</nobr> <script type="math/tex" id="MathJax-Element-83">i中除了<nobr>Ai,e</nobr> <script type="math/tex" id="MathJax-Element-84">A_{i,e}以外的項(xiàng)j，全都減去了<nobr>Ai,e?Al,j</nobr> <script type="math/tex" id="MathJax-Element-85">A_{i,e}*A_{l,j}，而常數(shù)項(xiàng)<nobr>Bi</nobr> <script type="math/tex" id="MathJax-Element-86">B_i減去了<nobr>Ai,e?Bl</nobr> <script type="math/tex" id="MathJax-Element-87">A_{i,e}*B_l。而同樣的，對(duì)于<nobr>Ai,e</nobr> <script type="math/tex" id="MathJax-Element-88">A_{i,e}這一項(xiàng)我們要特殊處理，把它變成現(xiàn)在<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-89">y_l這個(gè)變量該有的系數(shù)，也就是<nobr>?Al,e?Ai,e</nobr> <script type="math/tex" id="MathJax-Element-90">-A_{l,e}*A_{i,e}。 </p> <p> **后是對(duì)于目標(biāo)函數(shù)的處理，同樣是把<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-91">x_e消掉，把<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-92">y_l引入。而我們用一個(gè)單獨(dú)的變量v來記錄目標(biāo)函數(shù)中的常數(shù)項(xiàng)，一開始目標(biāo)函數(shù)中是沒有常數(shù)項(xiàng)的，隨著我們的代換會(huì)出現(xiàn)一個(gè)漸漸增大的常數(shù)項(xiàng)。顯然<nobr>Bl</nobr> <script type="math/tex" id="MathJax-Element-93">B_l就是貢獻(xiàn)常數(shù)項(xiàng)的東西，每次操作它會(huì)為常數(shù)項(xiàng)貢獻(xiàn)<nobr>Ce?Bl</nobr> <script type="math/tex" id="MathJax-Element-94">C_e*B_l這么多。然后接下來的代換過程就是和上面替換<nobr>Ai,e</nobr> <script type="math/tex" id="MathJax-Element-95">A_{i,e}的時(shí)候相似的了，這里不再贅述（ATP覺得自己?jiǎn)碌囊呀?jīng)夠多的了qwq） </p> <p> **后當(dāng)目標(biāo)函數(shù)中所有系數(shù)都變成負(fù)數(shù)的時(shí)候，記錄的v就是線性規(guī)劃的**優(yōu)解啦。 </p> <h2 id="對(duì)偶原理"> 對(duì)偶原理 </h2> <p> 前面我們所有的討論都基于一個(gè)假設(shè)：所有非基變量取0是一組可行解。 </p> <p> 但是很多時(shí)候我們會(huì)碰到這樣的線性規(guī)劃： <nobr>Minmize&nbsp;&nbsp;&nbsp;&nbsp;Cx</nobr> <script type="math/tex" id="MathJax-Element-96">Minmize\space\space\space\space Cx <nobr>S.T.&nbsp;&nbsp;&nbsp;Ax≥B,x≥0</nobr> <script type="math/tex" id="MathJax-Element-97">S.T. \space\space\space Ax \geq B,x \geq 0 </p> <p> 把所有系數(shù)取反？但是取反這種操作是不會(huì)改變約束條件的本質(zhì)的。這個(gè)時(shí)候我們就會(huì)用到對(duì)偶原理了 </p> <p> 形式化的，對(duì)偶原理就是說： </p> <p> <nobr>Minmize&nbsp;&nbsp;&nbsp;&nbsp;Cx</nobr> <script type="math/tex" id="MathJax-Element-98">Minmize\space\space\space\space Cx <nobr>S.T.&nbsp;&nbsp;&nbsp;Ax≥B,x≥0</nobr> <script type="math/tex" id="MathJax-Element-99">S.T. \space\space\space Ax \geq B,x \geq 0 和 <nobr>Maxmize&nbsp;&nbsp;&nbsp;&nbsp;BTx</nobr> <script type="math/tex" id="MathJax-Element-100">Maxmize\space\space\space\space B^Tx <nobr>S.T.&nbsp;&nbsp;&nbsp;ATy≤CT,y≥0</nobr> <script type="math/tex" id="MathJax-Element-101">S.T. \space\space\space A^Ty \leq C^T,y \geq 0 </p> <p> 這兩個(gè)線性規(guī)劃是等價(jià)的。 </p> <p> 顯然，如果我們遇到了一個(gè)這種所有非基變量取0不是可行解的線性規(guī)劃，我們可以用對(duì)偶原理把它“轉(zhuǎn)”一下，就會(huì)變成一個(gè)所有非基變量取0是可行解的線性規(guī)劃，就可以用單純形求解了。 </p> <p> 證明？好像不大會(huì)用到，ATP也不會(huì)。。。 </p> <p> 不過想要理解一下對(duì)偶原理的話，這篇文章還是不錯(cuò)的[戳這里]。。。 </p> <h2 id="貼幾個(gè)板子題吧"> 貼幾個(gè)板子題吧 </h2> BZOJ1061 志愿者招募 BZOJ1618 防守戰(zhàn)線 BZOJ3265 志愿者招募加強(qiáng)版 BZOJ3550 Vacation <h2 id="據(jù)說網(wǎng)絡(luò)流都可以用線性規(guī)劃做"> 據(jù)說網(wǎng)絡(luò)流都可以用線性規(guī)劃做？ </h2> <p> 參考曹欽翔《線性規(guī)劃與網(wǎng)絡(luò)流》。。。 </p> <p> ATP其實(shí)沒怎么看那個(gè)。。。 </p> <p> 主要問題是感覺里面說的基本上就是如何把現(xiàn)成的網(wǎng)絡(luò)流模型改造成線性規(guī)劃。。。 </p> <p> 但是既然都有了網(wǎng)絡(luò)流模型干嘛還要改線性規(guī)劃啊。。。(?Д?*)? </p> <h2 id="據(jù)說線性規(guī)劃也可以用費(fèi)用流做"> 據(jù)說線性規(guī)劃也可以用費(fèi)用流做？ </h2> <p> 這種方法是ATP一開始看線性規(guī)劃的時(shí)候稀里糊涂學(xué)過來的。。也沒大用過。。在這里提一句吧。。 </p> <p> 例：BZOJ1061 志愿者招募 </p> <p> 用費(fèi)用流做線性規(guī)劃的時(shí)候，我們要做的**步仍然是列出不等式并且把它們轉(zhuǎn)化成松弛型。接下來以這個(gè)題的樣例來舉例說明操作過程。 </p> <p> 首先設(shè)每一種志愿者的招募人數(shù)為<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-121">x_i，我們可以列出這樣的三個(gè)松弛型約束條件： </p> <nobr>P1：x1?y1=2</nobr> <script type="math/tex" id="MathJax-Element-122">P_1：x_1-y_1=2 <nobr>P2：x1 x2?y2=3</nobr> <script type="math/tex" id="MathJax-Element-123">P_2：x_1 x_2-y_2=3 <nobr>P3：x2 x3?y3=4</nobr> <script type="math/tex" id="MathJax-Element-124">P_3：x_2 x_3-y_3=4 <p> 添加兩個(gè)約束條件<nobr>P0=0,P4=0</nobr> <script type="math/tex" id="MathJax-Element-125">P_0=0,P_4=0，然后用<nobr>Pi 1?Pi</nobr> <script type="math/tex" id="MathJax-Element-126">P_{i 1}-P_i，我們就得到了一組新的等式： </p> <nobr>P1?P0：x1?y1=2</nobr> <script type="math/tex" id="MathJax-Element-127">P_1-P_0：x_1-y_1=2 <nobr>P2?P1：x2?y2 y1=1</nobr> <script type="math/tex" id="MathJax-Element-128">P_2-P_1：x_2-y_2 y_1=1 <nobr>P3?P2：?x1 x3?y3 y2=1</nobr> <script type="math/tex" id="MathJax-Element-129">P_3-P_2：-x_1 x_3-y_3 y_2=1 <nobr>P4?P3：?x2?x3 y3=?4</nobr> <script type="math/tex" id="MathJax-Element-130">P_4-P_3：-x_2-x_3 y_3=-4 <p> 我們把它們化成這種形式是有原因的，因?yàn)槲覀兦蠼獾姆椒ㄊ蔷W(wǎng)絡(luò)流，而這組等式滿足一個(gè)十分關(guān)鍵的性質(zhì)——它們相加的和等于0。這可以和網(wǎng)絡(luò)流中的流量平衡結(jié)合起來。那么我們可以把上面的每個(gè)等式看成一個(gè)點(diǎn)并且按照變量的正負(fù)進(jìn)行連邊，并且設(shè)定“流出為正，流入為負(fù)”，那么源點(diǎn)S作為唯一只有流出流量的點(diǎn)，它流出的流量可以看成等式右邊那些正數(shù)；匯點(diǎn)T作為唯一只有流入流量的點(diǎn)，它流入的流量可以看成等式右邊那些負(fù)數(shù)。然后我們找到每個(gè)變量<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-131">x_i和<nobr>yi</nobr> <script type="math/tex" id="MathJax-Element-132">y_i正值和負(fù)值出現(xiàn)的等式<nobr>Ps</nobr> <script type="math/tex" id="MathJax-Element-133">P_s和<nobr>Pt</nobr> <script type="math/tex" id="MathJax-Element-134">P_t，然后連一條<nobr>Ps</nobr> <script type="math/tex" id="MathJax-Element-135">P_s到<nobr>Pt</nobr> <script type="math/tex" id="MathJax-Element-136">P_t的邊。而這道題因?yàn)橛?*小化費(fèi)用的要求，所以我們?cè)谶吷霞淤M(fèi)用。對(duì)于每個(gè)<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-137">x_i，每使用一單位流量就要增加<nobr>vi</nobr> <script type="math/tex" id="MathJax-Element-138">v_i的費(fèi)用，而<nobr>yi</nobr> <script type="math/tex" id="MathJax-Element-139">y_i是添加的輔助變量，對(duì)結(jié)果沒有影響，所以費(fèi)用為0即可。 </p> <p> 其實(shí)這個(gè)過程就是將費(fèi)用流問題轉(zhuǎn)線性規(guī)劃問題的逆過程。。 </p> </p> <p> <b>相關(guān)推薦：</b> </p> <hr /> <p> <a href="http://k67r.cn/px189_jssz/" target="_blank">蘇州JAVA培訓(xùn)</a>&nbsp; &nbsp;<a href="http://k67r.cn/px189_jssz/" target="_blank">蘇州JAVA培訓(xùn)班</a>&nbsp; &nbsp;<a href="http://k67r.cn/px189_jssz/" target="_blank">蘇州JAVA培訓(xùn)機(jī)構(gòu)</a> </p>$