苏州其然软件开发培训

自学java与java培训该如何选择

从事IT培训行业这些年，身边经常有朋友来咨询，问现在是否可以加入这个高薪行业，Java学习难不难，需要哪些条件?

在软件开发设计行业当中，使用**多的编程语言就属Java软件开发了，很多人都想在Java编程开发领域寻求一份工作。

Java是当前世界上比较流行的计算机编程语言，Java彻底改变了人们的生活，国内的开发人才需求量仍然在不断的增长，主要原因还是在于移动互联网的快速发展，衍生出一大批的新生企业，创业公司，预计在未来5年内Java软件开发人才的需求将会远大于供给，其中java程序员、java工程师**为缺乏。

自学java与java培训是两个绕不开的话题，两者的区别，前者知识是自己搜寻的，买书看或者网上找视频看，而后者，技术知识是老师教的，作为一个普通大学生实际上任何人都能够自学，只不过聪明程度和坚持的时间长短不同，花费的时间长一点短一点而已。

学习关乎到时间和金钱，没有效果和质量的培训，其实是没有任何意义的。Java培训班有哪些呢?市面上的Java培训良莠不齐，选择时应该慎重些。Java致力于打造符合企业需求的全能型人才。课程定位定位中高级JAVA开发工程师，课程内容涉及面广，内容深。课程涵盖了Java、Web，数据库，企业流行框架，Java等企业**佳实践、云计算大数据课程、内容由浅入深，剖析原理，让学员掌握实用技术，做企业和社会需要的稀缺人才。

此外，Java培训将为你提供就业保障，开设有就业指导课，设有专门的就业指导老师，在毕业前期，毕业之际，就业老师会为你做专门的就业指导，更有职业素养课程，不仅将你打造成Java开发技术达人，更是一位懂得职场之道的合格就业者。还有丰富的Java学习视频免费为你提供学习。

线性规划——单纯形算法の板子

>

以下内容全是口胡，请谨慎观看 ——From ATP

什么是线性规划？

参见高中数学必修五第三章

根据ATP的理解。。。线性规划就是设出一些变量，给出一些对于变量取值的限制，同时给出一个与这些变量相关的目标函数，要求在满足限制的前提下**大化或**小化目标函数。

举个例子：设有变量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> 就是一个线性规划啦。。（上面那一坨东西是ATP随便打上去的有没有解就不一定了= =） </p> <p> 形式化地，设<nobr>x</nobr> <script type="math/tex" id="MathJax-Element-9">x为n维列向量代表设定的变量，<nobr>A</nobr> <script type="math/tex" id="MathJax-Element-10">A为m*n的矩阵代表每个限制中每个变量的系数，<nobr>B</nobr> <script type="math/tex" id="MathJax-Element-11">B为m维列向量代表每个限制中的常数项，<nobr>C</nobr> <script type="math/tex" id="MathJax-Element-12">C为n维行向量代表目标函数的系数。举个栗子说，对于上面那一坨东西，它的各个元素表示如下： </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> 我们在这里仅讨论线性规划的标准型。线性规划的标准型表示如下： <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> 但是很多时候好像遇到的线性规划并不是标准型？难道它们不能做吗。。。其实并不是，在大多数情况下，不是标准型的线性规划都可以**做一些适当的转化表示成标准型。比如…… </p> <p> 目标函数要求**小化（<nobr>Minmize</nobr> <script type="math/tex" id="MathJax-Element-18">Minmize）? 似乎可以把所有系数取反，求得答案以后再反回来？ 在某些情况下，下面提到的“对偶定理”会更加好用。 </p> <p> 首先线性规划的限制应该都是大于等于或者小于等于这种形式的（不然计算机怎么搞出“无限接近”这种类型的答案来= =），但是在标准型里面限制都要求是小于等于，如果遇到别的符号？ 如果是带“<nobr>≥</nobr> <script type="math/tex" id="MathJax-Element-19">\geq”的限制，直接把所有系数取反就可以；而如果是带“=”的限制，例如<nobr>a=b</nobr> <script type="math/tex" id="MathJax-Element-20">a=b，我们可以转化成<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两个限制。 </p> <p> 总之**类似这样的变换我们可以把任意的线性规划转化为标准型，并且它们的**优解都是不变的。 </p> <h2 id="求解线性规划单纯形算法"> 求解线性规划——单纯形算法 </h2> <p> 求解线性规划**常用的算法是单纯形算法。它的理论时间复杂度是指数级别的。。但是跑得奇快无比啊并且也基本上卡不掉。。所以放心大胆用就是了。。 </p> <p> 单纯形算法的几何意义很多地方都有解释。。但是这里ATP主要解释它在代数方面的原理。 </p> <p> 首先，为了对线性规划使用单纯形算法，我们需要把线性规划转化为“松弛型”，也就是说把所有的不等式变为等式。以下都用m来表示限制个数，n来表示变量个数。 </p> <p> 为了做到这一点，我们对于每一个形如<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的限制增加一个叫做“基变量”的东西，把它称作<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，那么现在每条限制都变成了形如<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> 相对的那我们就把所有<nobr>xk</nobr> <script type="math/tex" id="MathJax-Element-27">x_k叫做“非基变量”好了。显然目标函数只会涉及到非基变量。现在我们做出一个假设就是如果把所有<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-28">x_i都取到0，那么它是一组能够满足所有限制条件的可行解。——实际情况下很多时候并不是这样的，这种情况在下面的对偶原理部分中进行讨论，现在先假设它是成立的。 </p> <p> 那么我们把所有的<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-29">x_i都取0，可以计算出目标函数的一个值。但是显然它不一定是**优的。观察目标函数，有些<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-30">x_i的系数是大于0的，那么如果我们能够让这些变量增大，我们就可以得到一组更优的解。但是如果目标函数里面不存在系数为正数的<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就能够得到**优解——所以前面那个假设是必要的。而单纯形算法就是要对目标函数和约束条件作出适当的变形，在不改变**优解的情况下把目标函数里面所有的系数都变成负数。 </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过程是单纯形算法的主过程。首先每次先找到**个系数大于0的非基变量。这里有一个叫做Bland法则的东西，就是说一定要选**个系数大于0的，不然容易被特殊数据卡成死循环。。然而ATP并没有试过= = </p> <p> 选中的这个非基变量就是上面的e。如果没有找到这样的变量，说明算法已经完成了，目标函数中的所有系数都变成负数了，就可以退出了。否则我们要把目标函数中<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-33">x_e的系数变成负数。上面提到过，当前的初始可行解为所有变量都取0，那么我们想要做的是尽量增大某个系数为正数的变量，也就是当前选择的<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**大可以增大到多大呢？这就要看约束条件了。接下来的一步就是枚举所有约束条件了。考虑每个含有<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，因为已经保证所有的<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尽量增大当然要把除了<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-40">x_e的所有变量都取0。那么当前约束下<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> 不同的约束条件产生的<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，我们需要找到所有约束条件产生的**小的<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**大可以增大到正无穷，这个线性规划就是无解的。 </p> <p> 否则我们能够找到一个约束条件<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}是**紧的那个限制。那么我们就要开始对约束条件进行变形了。变形能够进行的基础就是因为添加了基变量<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-49">y_l使得所有约束条件变成了“=”的形式，我们可以随便把每一项挪来挪去加加减减，都不会改变这个约束条件的本质。 </p> <p> 基变量<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-50">y_l的作用还不止如此，我们接下来要做的变形工作实际上是要用<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成为新的一个非基变量，<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-54">x_e成为新的一个基变量。这样一来就肯定要把整个约束条件表示成为<nobr>xe=...</nobr> <script type="math/tex" id="MathJax-Element-55">x_e=...的形式，而因为一开始<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在等号同侧而现在变成了异侧，那么<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-58">y_l的系数肯定就变成了相反数。那把它往目标函数里一代的时候，就会有一个基变量的系数变成负数了！ </p> <p> 于是上面的pivot过程就是来做这样的变形的。这玩意儿好像学名叫“转轴”操作，好像来源于单纯形算法的几何意义。。不管它不管它。 </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过程的**步，我们需要先对选定的这个约束条件<nobr>l</nobr> <script type="math/tex" id="MathJax-Element-60">l进行变形，把它由<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的约束中进行替换。 </p> <p> 为了替换方便我们要把<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-64">x_e的系数变为1，那么就要把所有的变量都除以<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-65">x_e原来的系数<nobr>Al,e</nobr> <script type="math/tex" id="MathJax-Element-66">A_{l,e}。而对于<nobr>Al,e</nobr> <script type="math/tex" id="MathJax-Element-67">A_{l,e}这个位置的数字我们又需要特殊处理。因为我们要把<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}这个位置变成<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-71">y_l应该有的系数。<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-72">y_l原本系数为1，现在当然就要变成<nobr>1Al,e</nobr> <script type="math/tex" id="MathJax-Element-73">1 \over A_{l,e}啦。 </p> <p> 这样我们就完成了过程的**步，也就是上面代码里前4行的内容。 </p> <p> 接下来我们要对所有除了约束条件<nobr>l</nobr> <script type="math/tex" id="MathJax-Element-74">l以外的约束条件进行变形。枚举所有不是<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的系数不是0的约束条件，我们要把<nobr>xe=...</nobr> <script type="math/tex" id="MathJax-Element-77">x_e=...这个式子给带进去消掉<nobr>xe</nobr> <script type="math/tex" id="MathJax-Element-78">x_e。设当前的约束为<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的项<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> 很容易发现替换以后约束条件<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}以外的项j，全都减去了<nobr>Ai,e?Al,j</nobr> <script type="math/tex" id="MathJax-Element-85">A_{i,e}*A_{l,j}，而常数项<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。而同样的，对于<nobr>Ai,e</nobr> <script type="math/tex" id="MathJax-Element-88">A_{i,e}这一项我们要特殊处理，把它变成现在<nobr>yl</nobr> <script type="math/tex" id="MathJax-Element-89">y_l这个变量该有的系数，也就是<nobr>?Al,e?Ai,e</nobr> <script type="math/tex" id="MathJax-Element-90">-A_{l,e}*A_{i,e}。 </p> <p> **后是对于目标函数的处理，同样是把<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引入。而我们用一个单独的变量v来记录目标函数中的常数项，一开始目标函数中是没有常数项的，随着我们的代换会出现一个渐渐增大的常数项。显然<nobr>Bl</nobr> <script type="math/tex" id="MathJax-Element-93">B_l就是贡献常数项的东西，每次操作它会为常数项贡献<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}的时候相似的了，这里不再赘述（ATP觉得自己啰嗦的已经够多的了qwq） </p> <p> **后当目标函数中所有系数都变成负数的时候，记录的v就是线性规划的**优解啦。 </p> <h2 id="对偶原理"> 对偶原理 </h2> <p> 前面我们所有的讨论都基于一个假设：所有非基变量取0是一组可行解。 </p> <p> 但是很多时候我们会碰到这样的线性规划： <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> 把所有系数取反？但是取反这种操作是不会改变约束条件的本质的。这个时候我们就会用到对偶原理了 </p> <p> 形式化的，对偶原理就是说： </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> 这两个线性规划是等价的。 </p> <p> 显然，如果我们遇到了一个这种所有非基变量取0不是可行解的线性规划，我们可以用对偶原理把它“转”一下，就会变成一个所有非基变量取0是可行解的线性规划，就可以用单纯形求解了。 </p> <p> 证明？好像不大会用到，ATP也不会。。。 </p> <p> 不过想要理解一下对偶原理的话，这篇文章还是不错的[戳这里]。。。 </p> <h2 id="贴几个板子题吧"> 贴几个板子题吧 </h2> BZOJ1061 志愿者招募 BZOJ1618 防守战线 BZOJ3265 志愿者招募加强版 BZOJ3550 Vacation <h2 id="据说网络流都可以用线性规划做"> 据说网络流都可以用线性规划做？ </h2> <p> 参考曹钦翔《线性规划与网络流》。。。 </p> <p> ATP其实没怎么看那个。。。 </p> <p> 主要问题是感觉里面说的基本上就是如何把现成的网络流模型改造成线性规划。。。 </p> <p> 但是既然都有了网络流模型干嘛还要改线性规划啊。。。(?Д?*)? </p> <h2 id="据说线性规划也可以用费用流做"> 据说线性规划也可以用费用流做？ </h2> <p> 这种方法是ATP一开始看线性规划的时候稀里糊涂学过来的。。也没大用过。。在这里提一句吧。。 </p> <p> 例：BZOJ1061 志愿者招募 </p> <p> 用费用流做线性规划的时候，我们要做的**步仍然是列出不等式并且把它们转化成松弛型。接下来以这个题的样例来举例说明操作过程。 </p> <p> 首先设每一种志愿者的招募人数为<nobr>xi</nobr> <script type="math/tex" id="MathJax-Element-121">x_i，我们可以列出这样的三个松弛型约束条件： </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> 添加两个约束条件<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> 我们把它们化成这种形式是有原因的，因为我们求解的方法是网络流，而这组等式满足一个十分关键的性质——它们相加的和等于0。这可以和网络流中的流量平衡结合起来。那么我们可以把上面的每个等式看成一个点并且按照变量的正负进行连边，并且设定“流出为正，流入为负”，那么源点S作为唯一只有流出流量的点，它流出的流量可以看成等式右边那些正数；汇点T作为唯一只有流入流量的点，它流入的流量可以看成等式右边那些负数。然后我们找到每个变量<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正值和负值出现的等式<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的边。而这道题因为有**小化费用的要求，所以我们在边上加费用。对于每个<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的费用，而<nobr>yi</nobr> <script type="math/tex" id="MathJax-Element-139">y_i是添加的辅助变量，对结果没有影响，所以费用为0即可。 </p> <p> 其实这个过程就是将费用流问题转线性规划问题的逆过程。。 </p> </p> <p> <b>相关推荐：</b> </p> <hr /> <p> <a href="//www.auscyc.com/px/px189_jssz/" target="_blank">苏州JAVA培训</a>&nbsp; &nbsp;<a href="//www.auscyc.com/px/px189_jssz/" target="_blank">苏州JAVA培训班</a>&nbsp; &nbsp;<a href="//www.auscyc.com/px/px189_jssz/" target="_blank">苏州JAVA培训机构</a> </p>$