6_8.htm

随着各行各业的发展和生产需要

    <td width="9%">-1/16</td>
    <td width="9%">-1/8</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
  </tr>
  <tr>
    <td width="8%">A<sub>7</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">1</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">0</td>
    <td width="8%">21/2</td>
    <td width="9%">3/2</td>
    <td width="9%">-1</td>
    <td width="9%">1</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">-3</td>
    <td width="9%">　</td>
    <td width="9%">　</td>
    <td width="9%">　</td>
    <td width="9%">←λ</td>
  </tr>
</table>
</div>

<p>　</p>
<div align="left">

<table border="1" width="85%">
  <tr>
    <td width="8%">B</td>
    <td width="8%">C<sub>B</sub></td>
    <td width="8%">C<sub>B</sub>B<sup>-1</sup></td>
    <td width="8%">C</td>
    <td width="8%">-3/4</td>
    <td width="8%">20</td>
    <td width="8%">-1/2</td>
    <td width="8%">6</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
    <td width="9%">β</td>
  </tr>
  <tr>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">P<sub>0</sub></td>
    <td width="8%">P<sub>1</sub></td>
    <td width="8%">P<sub>2</sub></td>
    <td width="8%">P<sub>3</sub></td>
    <td width="8%">P<sub>4</sub></td>
    <td width="9%">P<sub>5</sub></td>
    <td width="9%">P<sub>6</sub></td>
    <td width="9%">P<sub>7</sub></td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>3</sub></td>
    <td width="8%">-1/2</td>
    <td width="8%">1</td>
    <td width="8%">0</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">0</td>
    <td width="9%">(2)</td>
    <td width="9%">-6</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
  </tr>
  <tr>
    <td width="8%">A<sub>4</sub></td>
    <td width="8%">6</td>
    <td width="8%">-1</td>
    <td width="8%">0</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">1</td>
    <td width="9%">1/3</td>
    <td width="9%">-2/3</td>
    <td width="9%">0</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>7</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">1</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">0</td>
    <td width="9%">2</td>
    <td width="9%">6</td>
    <td width="9%">1</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="9%">-1</td>
    <td width="9%">　</td>
    <td width="9%">　</td>
    <td width="9%">←λ</td>
  </tr>
</table>
</div>

<p>　</p>
<div align="left">

<table border="1" width="85%">
  <tr>
    <td width="8%">B</td>
    <td width="8%">C<sub>B</sub></td>
    <td width="8%">C<sub>B</sub>B<sup>-1</sup></td>
    <td width="8%">C</td>
    <td width="8%">-3/4</td>
    <td width="8%">20</td>
    <td width="8%">-1/2</td>
    <td width="8%">6</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
    <td width="9%">β</td>
  </tr>
  <tr>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">P<sub>0</sub></td>
    <td width="8%">P<sub>1</sub></td>
    <td width="8%">P<sub>2</sub></td>
    <td width="8%">P<sub>3</sub></td>
    <td width="8%">P<sub>4</sub></td>
    <td width="9%">P<sub>5</sub></td>
    <td width="9%">P<sub>6</sub></td>
    <td width="9%">P<sub>7</sub></td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>5</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="9%">1</td>
    <td width="9%">-3</td>
    <td width="9%">0</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>4</sub></td>
    <td width="8%">6</td>
    <td width="8%">2</td>
    <td width="8%">0</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="9%">0</td>
    <td width="9%">(1/3)</td>
    <td width="9%">0</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>7</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">1</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="9%">0</td>
    <td width="9%">2</td>
    <td width="9%">1</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="9%">　</td>
    <td width="9%">-2</td>
    <td width="9%">　</td>
    <td width="9%">←λ</td>
  </tr>
</table>
</div>

<p>　</p>
<div align="left">

<table border="1" width="85%">
  <tr>
    <td width="8%">B</td>
    <td width="8%">C<sub>B</sub></td>
    <td width="8%">C<sub>B</sub>B<sup>-1</sup></td>
    <td width="8%">C</td>
    <td width="8%">-3/4</td>
    <td width="8%">20</td>
    <td width="8%">-1/2</td>
    <td width="8%">6</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
    <td width="9%">β</td>
  </tr>
  <tr>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">P<sub>0</sub></td>
    <td width="8%">P<sub>1</sub></td>
    <td width="8%">P<sub>2</sub></td>
    <td width="8%">P<sub>3</sub></td>
    <td width="8%">P<sub>4</sub></td>
    <td width="9%">P<sub>5</sub></td>
    <td width="9%">P<sub>6</sub></td>
    <td width="9%">P<sub>7</sub></td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>5</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">1/4</td>
    <td width="8%">-8</td>
    <td width="8%">-1</td>
    <td width="8%">9</td>
    <td width="9%">1</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>6</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">1/2</td>
    <td width="8%">-12</td>
    <td width="8%">-1/2</td>
    <td width="8%">3</td>
    <td width="9%">0</td>
    <td width="9%">1</td>
    <td width="9%">0</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>7</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">1</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">(1)</td>
    <td width="8%">0</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
    <td width="9%">1</td>
    <td width="9%">1</td>
  </tr>
  <tr>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">0</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">-1/2</td>
    <td width="8%">　</td>
    <td width="9%">　</td>
    <td width="9%">　</td>
    <td width="9%">　</td>
    <td width="9%">←λ</td>
  </tr>
</table>
</div>

<p>显然，目标函数始终没有改善。<br>
<strong></strong></p>

<p><strong>3．小扰动法．</strong><br>
<strong>定理</strong>　存在 ☆<sub>0</sub>＞0，只要☆∈(0 ,☆<sub>0</sub> )，线性规划问题 
<br>
maxz＝CX<br>
AX＝b＋AE<br>
X≥0．<br>
是非退化的，其中E＝(☆ ☆<sup>2</sup> … ☆<sup>n+m</sup> ),可以认为 b＋AE＞0<br>
注意：① AX＝b, b≥0，对于b的0元，A对应行左起非0元是正数，若为负可两边同乘－1．故b＋AE＞0．<br>
② ( A ┆b＋AE )　　　( P┆P0＋PE )<br>
③当β取O(☆<sup>i</sup>)时，实际只要看P中行向量按字典序的大小．<br>
P<sub>( i )</sub>：P的第 i 行．<br>
P<sub>i</sub>：P的第 i 列．<br>
b<sub>i</sub>＝b<sub>j</sub>＝0，a<sub>k</sub>进入，看P<sub>(i)</sub>/α<sub>ik</sub>,P<sub>(j)</sub>/α<sub>jk</sub>哪一个字典序小，<br>
α<sub>ik</sub>＞0， α<sub>jk</sub>＞0，字典序小的退出． <br>
因而可略去AE，而观察P的行的字典序的大小，用字典序或小扰动法<br>
时无法用改善的单纯形表格．字典序就是小扰动．</p>

<p><br>
<strong>证</strong>　设B<sub>i</sub>是A中的m列构成的可逆矩阵．<br>
i＝1 , 2, … ,k．k≤C(m+n,m)．<br>
AX<sub>i</sub>＝A(X<sub>Bi</sub> X<sub>Ni</sub>)<sup>T</sup>＝( B<sub>i</sub> ┆N<sub>i</sub> 
) (X<sub>Bi</sub> X<sub>Ni</sub>)<sup>T</sup>＝B<sub>i</sub>X<sub>Bi</sub><br>
＝b＋B<sub>i</sub>E<sub>Bi</sub>＋N<sub>i</sub>E<sub>Ni</sub>，又因为<br>
X<sub>bi</sub>＝B<sub>i</sub><sup>－1</sup>b＋E<sub>bi</sub>＋B<sub>i</sub><sup>－1</sup>N<sub>i</sub>E<sub>Ni</sub>，右边的每个ε的多项式，<br>
m个多项式有最小正根☆<sub>i</sub>．令☆<sub>0</sub>＝min{☆<sub>i</sub>｜i＝1 
, 2, … ,k}．<br>
当☆∈( 0, ☆<sub>0</sub>)时，X<sub>bi</sub>中无0元．即对应的线性规划问题是非退化的．<br>
证毕．<br>
</p>

<p>小扰动法和二阶段法是不同的．在退化情况下，可能出现循环不已的情形，<br>
此时，用二阶段法无能为力，而小扰动法能从退化情况中摆脱出来．<br>
<br>
<strong>4．Bland方法</strong>．<br>
( a )　若干基可进入，选下标最小的进入；<br>
( b )　若干基可退出，选小标最小的退出；<br>
遵循此规则，可避免循环．<br>
</p>
</body>
</html>