6_7.htm

组合数学 清华大学研究生课程课件 呵呵

    <td width="8%">P<sub>5</sub></td>
    <td width="8%">P<sub>6</sub></td>
    <td width="8%">P<sub>7</sub></td>
    <td width="8%">P<sub>8</sub></td>
    <td width="8%">　</td>
  </tr>
  <tr>
    <td width="7%">A<sub>6</sub></td>
    <td width="7%">6</td>
    <td width="7%">6</td>
    <td width="7%">(3)</td>
    <td width="8%">3</td>
    <td width="8%">1</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="8%">0</td>
    <td width="8%">1</td>
  </tr>
  <tr>
    <td width="7%">A<sub>7</sub></td>
    <td width="7%">6</td>
    <td width="7%">6</td>
    <td width="7%">6</td>
    <td width="8%">4</td>
    <td width="8%">3</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="8%">　</td>
  </tr>
  <tr>
    <td width="7%">A<sub>8</sub></td>
    <td width="7%">6</td>
    <td width="7%">6</td>
    <td width="7%">2</td>
    <td width="8%">1</td>
    <td width="8%">2</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%">　</td>
  </tr>
  <tr>
    <td width="7%">　</td>
    <td width="7%">　</td>
    <td width="7%">z'=66</td>
    <td width="7%">　</td>
    <td width="8%">-46</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="8%">←λ</td>
  </tr>
</table>
</div>

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

<table border="1" width="90%">
  <tr>
    <td width="7%">B</td>
    <td width="7%">C<sub>B</sub></td>
    <td width="7%">C<sub>B</sub>B<sup>-1</sup></td>
    <td width="7%">C</td>
    <td width="8%">2</td>
    <td width="8%">1</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">6</td>
    <td width="8%">6</td>
    <td width="8%">6</td>
    <td width="8%">β</td>
  </tr>
  <tr>
    <td width="7%">　</td>
    <td width="7%">　</td>
    <td width="7%">　</td>
    <td width="7%">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="8%">P<sub>5</sub></td>
    <td width="8%">P<sub>6</sub></td>
    <td width="8%">P<sub>7</sub></td>
    <td width="8%">P<sub>8</sub></td>
    <td width="8%">　</td>
  </tr>
  <tr>
    <td width="7%">A<sub>1</sub></td>
    <td width="7%">2</td>
    <td width="7%">-28/3</td>
    <td width="7%">1</td>
    <td width="8%">1</td>
    <td width="8%">1/3</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">1/3</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">　</td>
  </tr>
  <tr>
    <td width="7%">A<sub>7</sub></td>
    <td width="7%">6</td>
    <td width="7%">6</td>
    <td width="7%">2</td>
    <td width="8%">0</td>
    <td width="8%">5/3</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">-4/3</td>
    <td width="8%">1</td>
    <td width="8%">0</td>
    <td width="8%">　</td>
  </tr>
  <tr>
    <td width="7%">A<sub>8</sub></td>
    <td width="7%">6</td>
    <td width="7%">6</td>
    <td width="7%">1</td>
    <td width="8%">0</td>
    <td width="8%">(5/3)</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">-1/3</td>
    <td width="8%">0</td>
    <td width="8%">1</td>
    <td width="8%">3/5</td>
  </tr>
  <tr>
    <td width="7%">　</td>
    <td width="7%">　</td>
    <td width="7%">z'=20</td>
    <td width="7%">　</td>
    <td width="8%">　</td>
    <td width="8%">-59/3</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>
  </tr>
</table>
</div>

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

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

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

<table border="1" width="90%">
  <tr>
    <td width="7%">B</td>
    <td width="7%">C<sub>B</sub></td>
    <td width="10%">C<sub>B</sub>B<sup>-1</sup></td>
    <td width="6%">C</td>
    <td width="7%">2</td>
    <td width="7%">1</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">6</td>
    <td width="8%">6</td>
    <td width="8%">6</td>
    <td width="8%">β</td>
  </tr>
  <tr>
    <td width="7%">　</td>
    <td width="7%">　</td>
    <td width="10%">　</td>
    <td width="6%">P<sub>0</sub></td>
    <td width="7%">P<sub>1</sub></td>
    <td width="7%">P<sub>2</sub></td>
    <td width="8%">P<sub>3</sub></td>
    <td width="8%">P<sub>4</sub></td>
    <td width="8%">P<sub>5</sub></td>
    <td width="8%">P<sub>6</sub></td>
    <td width="8%">P<sub>7</sub></td>
    <td width="8%">P<sub>8</sub></td>
    <td width="8%">　</td>
  </tr>
  <tr>
    <td width="7%">A<sub>1</sub></td>
    <td width="7%">2</td>
    <td width="10%">2/5</td>
    <td width="6%">3/5</td>
    <td width="7%">　</td>
    <td width="7%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">0</td>
    <td width="8%">3/5</td>
    <td width="8%">-1/5</td>
    <td width="8%">0</td>
    <td width="8%">　</td>
  </tr>
  <tr>
    <td width="7%">A<sub>5</sub></td>
    <td width="7%">0</td>
    <td width="10%">1/5</td>
    <td width="6%">1</td>
    <td width="7%">　</td>
    <td width="7%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">1</td>
    <td width="8%">-1</td>
    <td width="8%">1</td>
    <td width="8%">-1</td>
    <td width="8%">　</td>
  </tr>
  <tr>
    <td width="7%">A<sub>2</sub></td>
    <td width="7%">1</td>
    <td width="10%">0</td>
    <td width="6%">6/5</td>
    <td width="7%">　</td>
    <td width="7%">　</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">0</td>
    <td width="8%">-4/5</td>
    <td width="8%">3/5</td>
    <td width="8%">0</td>
    <td width="8%">　</td>
  </tr>
  <tr>
    <td width="7%">　</td>
    <td width="7%">　</td>
    <td width="10%">z'=12/5</td>
    <td width="6%">　</td>
    <td width="7%">　</td>
    <td width="7%">　</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>
  </tr>
</table>
</div>

<p>故问题的解是：x<sub>1</sub>＝3/5,　x<sub>2</sub>＝6/5,min z＝12/5<br>
<br>
由上面的解题过程可以看出，大M法的主要优点是不用分阶段，<br>
而缺点是不知道M取多大合适．<br>
</p>

<p><strong>例</strong>　<br>
max z＝2x<sub>1</sub>+x<sub>2</sub>+x<sub>3</sub>，<br>
4x<sub>1</sub>＋6x<sub>2</sub>＋3x<sub>3</sub> ≤8<br>
x<sub>1</sub>－9x<sub>2</sub>＋x<sub>3</sub> ≤－3<br>
－2x<sub>1</sub>－3x<sub>2</sub>＋5x<sub>3</sub> ≤－4<br>
x<sub>1</sub> , x<sub>2</sub> , x<sub>3</sub> ≥0<br>
解　<br>
引入松弛变量 x<sub>4</sub> , x<sub>5</sub> , x<sub>6</sub>．得<br>
4x<sub>1</sub>＋6x<sub>2</sub>＋3x<sub>3</sub> ＋x<sub>4</sub>＝8 (1)<br>
x<sub>1</sub>－9x<sub>2</sub>＋x<sub>3</sub> ＋x<sub>5</sub>＝－3 (2)<br>
－2x<sub>1</sub>－3x<sub>2</sub>＋5x<sub>3</sub> ＋x<sub>6</sub>＝－4 (3)<br>
<br>
(2)－(3)得 3x<sub>1</sub>－6x<sub>2</sub>－4x<sub>3</sub>＋x<sub>5</sub>－x<sub>6</sub>＝1 
(4)<br>
－(3)得　2x<sub>1</sub>＋3x<sub>2</sub>－5x<sub>3</sub>－x<sub>6</sub>＝4 (5)<br>
在(5)中引入一个人工变量x<sub>7</sub>，约束条件变成：<br>
<img src="6_7_3.gif" width="260" height="214"> </p>

<p><strong>１．用二阶段法</strong><br>
(1)第一阶段 minz'＝x<sub>7</sub>，用改善单纯形法求得一个顶点．过程如下．<br>
</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%">0</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="9%">0</td>
    <td width="9%">0</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%">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>6</sub></td>
    <td width="9%">P<sub>4</sub></td>
    <td width="9%">P<sub>5</sub></td>
    <td width="9%">P<sub>7</sub></td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>4</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">8</td>
    <td width="8%">4</td>
    <td width="8%">6</td>
    <td width="8%">3</td>
    <td width="8%">0</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>5</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">1</td>
    <td width="8%">(3)</td>
    <td width="8%">-6</td>
    <td width="8%">-4</td>
    <td width="8%">-1</td>
    <td width="9%">0</td>
    <td width="9%">1</td>
    <td width="9%">0</td>
    <td width="9%">1/3</td>
  </tr>
  <tr>
    <td width="8%">A<sub>7</sub></td>
    <td width="8%">1</td>
    <td width="8%">1</td>
    <td width="8%">4</td>
    <td width="8%">2</td>
    <td width="8%">3</td>
    <td width="8%">-5</td>
    <td width="8%">-1</td>
    <td width="9%">0</td>
    <td width="9%">0</td>
    <td width="9%">1</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="8%">z'=4</td>
    <td width="8%">　</td>
    <td width="8%">-2</td>
    <td width="8%">　</td>
    <td width="8%">　</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>　</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%">0</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="9%">0</td>
    <td width="9%">0</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%">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>6</sub></td>
    <td width="9%">P<sub>4</sub></td>
    <td width="9%">P<sub>5</sub></td>
    <td width="9%">P<sub>7</sub></td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>4</sub></td>
    <td width="8%">0</td>
    <td width="8%">0</td>
    <td width="8%">20/3</td>
    <td width="8%">0</td>
    <td width="8%">14</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="9%">1</td>
    <td width="9%">-4/3</td>
    <td width="9%">0</td>
    <td width="9%">　</td>
  </tr>
  <tr>
    <td width="8%">A<sub>1</sub></td>
    <td width="8%">0</td>
    <td width="8%">-2/3</td>
    <td width="8%">1/3</td>
    <td width="8%">1</td>
    <td width="8%">-2</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%">1</td>
    <td width="8%">1</td>
    <td width="8%">10/3</td>
    <td width="8%">0</td>
    <td width="8%">(7)</td>
    <td width="8%">　</td>
    <td width="8%">　</td>
    <td width="9%">0</td>
    <td width="9%">-2/3</td>