📄 6_6.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§6.6</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"></head><body><p align="center"><font size="4"><b>§6.6 改善的单纯形法表格</b></font></p><p> 单纯形法至今依然是线性规划的有效算法．但其中有些计算是不必要的．单纯形法在进<br>行列消元时相当于左乘以某一基矩阵B的逆．所以计算B<sup>－１</sup>是关键．若求得B<sup>－1</sup>, 便可计算<br>P<sub>j</sub>＝B<sup>－1</sup>A<sub>j</sub>，λ<sub>j</sub>＝C<sub>j</sub>－Z<sub>j</sub>＝C<sub>j</sub>－C<sub>B</sub>B<sup>－1</sup>A<sub>j</sub>．<br>因而计算λ<sub>j</sub>时C<sub>B</sub> B<sup>－1</sup>是公共部分，可以先计算．因为<br>C<sub>B</sub>B<sup>－1</sup>A<sub>j</sub>＝ (C<sub>B</sub>B<sup>－1</sup>) A<sub>j</sub>＝ C<sub>B</sub>( B<sup>－1</sup>A<sub>j</sub> )，<br>故在原有的单纯形表格中要增加一列C<sub>B</sub> B<sup>－1,</sup>但B<sup>－1</sup>可存于A中的m阶单位矩阵的单元中．<br> 对于线性规划问题改善的单纯形法计算步骤如下：<br>( a )计算B<sup>－1</sup>，B<sup>－1</sup>b，<br>( b )计算C<sub>B</sub>B<sup>－1</sup>, C<sub>B</sub>B<sup>－1</sup>b，<br>( c )计算λ<sub>j</sub>＝C<sub>j</sub>－C<sub>B</sub>B<sup>－1</sup>A<sub>j</sub>，j＝1 , 2 , … ,n+m.若所有λ<sub>j</sub>≤0，计算结束．由P<sub>0</sub>所确定的Z(X)<br>便是所求的目标函数最大值．否则令<br>c<sub>j</sub>－z<sub>j</sub>＝max{ c<sub>l</sub>－ z<sub>l</sub>｜c<sub>l</sub>－ z<sub>l</sub>＞0}.<br>( d ) P<sub>j</sub>＝B<sup>－1</sup>A<sub>j</sub>，计算相应的λ，确定主元素及退出基，设为P<sub>k</sub>，以A<sub>j</sub>取代A<sub>k</sub>，返回( a )．<br><br> 这里并为涉及如何计算以A<sub>j</sub>取代A<sub>k</sub>后的<br>基矩阵B的逆B<sup>－1</sup>．它相当于已知矩阵Bold＝( b<sub>1</sub> b<sub>2</sub> ··· b<sub>k</sub> ··· b<sub>m</sub> )<br>的逆B<sup>－1</sup><sub>old</sub>．若用一列矩阵b取代其中b<sub>k</sub>．得B<sub>new</sub>＝( b<sub>1</sub> b<sub>2</sub> ··· b ··· b<sub>m</sub> )．<br>以下求B<sup>－1</sup><sub>new</sub> ．令<br>B<sub>old</sub>Y＝P<br>则 Y＝ B<sup>－1</sup><sub>old</sub>P＝( y<sub>1</sub> y<sub>2</sub> ··· y<sub>m</sub> )<br>作<br><img src="6_6_1.gif" width="486" height="340"><br>显然有 B<sub>old</sub>E<sub>k</sub>＝B<sub>new</sub>,所以 B<sup>－1</sup><sub>new</sub> ＝E<sup>－1</sup><sub>k</sub> B<sup>－1</sup><sub>old</sub> .</p><p>可从Jordan矩阵求逆的方法中获得E<sup>－1</sup><sub>k</sub> ．<br>即通过行变换从<br>( E<sub>k</sub> E<sub>(m)</sub>)→ (E<sub>(m)</sub> E<sup>－1</sup><sub>k</sub> ) <br>同理可得B<sup>－1</sup><sub>new</sub> 如下：<br>( E<sub>(m)</sub> B<sup>－1</sup><sub>old</sub> )→(E<sub>(m)</sub> E<sup>－1</sup><sub>k</sub>B<sup>－1</sup><sub>old</sub>) ＝(E<sub>(m)</sub> B<sup>－1</sup><sub>new</sub> ) <br>且容易求得<br><img src="6_6_2.gif" width="581" height="340"><br></p><p>实际可得求B<sup>－1</sup><sub>new</sub> 的紧凑表格<br>( Y B<sup>－1</sup><sub>old</sub> ) → ( E<sub>k</sub> B<sup>－1</sup><sub>new</sub> )<br>其中E<sub>k</sub>＝( 0 0 ··· 0 1 0 ··· 0 ),其中的1是第k个元素.<br>单纯表格法与改善的单纯表格法的区别在于前者计算所有的P<sub>j</sub>，<br>j＝1 , 2 , … , n+m．后者先算B<sup>－1</sup>，P<sub>0</sub>，再算C<sub>B</sub>B<sup>－1</sup>，找出一<br>个满足λ<sub>j</sub>＝c<sub>j</sub>－C<sub>B</sub>B<sup>－1</sup>A<sub>j</sub>＞0的A<sub>j</sub>，只计算P<sub>j</sub>＝ B<sup>－1</sup>A<sub>j</sub>,两者都通过计算<br>λ＝min{ α<sub>i</sub>/α<sub>ij</sub>｜α<sub>ij</sub> ＞0}来确定退出基A<sub>k</sub>，通过行变换将P<sub>j</sub>变成e<sub>k</sub>，<br>同时用同样的行变换将B<sup>－1</sup>变成B'<sub>－1</sub>，P<sub>0</sub>变成P<sup>’</sup><sub>0</sub>，从而进入下一轮迭代．<br><br></p><p><b>例 1</b> maxz＝3x<sub>1</sub>+ 6x<sub>2</sub>+ 2x<sub>3</sub><br>3x<sub>1</sub>+ 4x<sub>2</sub>+ x<sub>3</sub>≤2，<br>x<sub>1</sub>+ 3x<sub>2</sub> + 2x<sub>3</sub>≤1，<br>x<sub>1</sub> , x<sub>2</sub> , x<sub>3</sub>≥0．<br>用改善的单纯形法表格求解如下：<br><strong>解</strong> 引进松弛变量x<sub>4</sub> , x<sub>5</sub>．问题变为：<br>maxz＝3x<sub>1</sub>+ 6x<sub>2</sub>+ 2x<sub>3</sub> + 0x<sub>4</sub> +0x<sub>5</sub>，<br>3x<sub>1</sub>+ 4x<sub>2</sub>+ x<sub>3</sub>+ x<sub>4</sub>＝2，<br>x<sub>1</sub>+ 3x<sub>2</sub> + 2x<sub>3</sub>+ x<sub>5</sub>＝1，<br>x<sub>1</sub> , x<sub>2</sub> , x<sub>3</sub> , x<sub>4</sub> , x<sub>5</sub>≥0．<br>1. z<sup>0</sup>＝C<sub>B</sub>P<sub>0</sub>＝(0 0)(2 1)<sup>T</sup>＝0；<br>2. Z<sub>j</sub>＝C<sub>B</sub>P<sub>j</sub>＝0，j＝1 , 2 , … , 5<br> λ<sub>j</sub>＝c<sub>j</sub>－z<sub>j</sub>＝c<sub>j</sub>，j＝1 , 2 , … , 5．<br> ∧<sup>(0)</sup>=C＝( 0 , 0 , 3, 6 ,2 )． λ<sub>1</sub>＝3＞0,A<sub>1</sub>进入<br>3. λ<sup>(0)</sup>＝2／3, A<sub>4</sub>退出；z<sup>(1)</sup>＝z<sup>(0)</sup>+ λ<sup>(0)</sup>λ<sub>1</sub><sup>(0)</sup>＝2<br>4． 以a<sub>11</sub>为主元，消元．<br> ( P<sup>(0)</sup> P<sub>0</sub><sup>(0)</sup> ) ＝(A b) →(P<sup>(1)</sup> P<sub>0</sub><sup>(1)</sup>) <br>5． ∧<sup>(0)</sup>→∧<sup>(1)</sup> ＝( 1 ,0 ,0 ,2 , 1 )， λ<sub>2</sub>＝2＞0,A<sub>2</sub>进入．<br>6． λ<sup>(1)</sup>＝(1/3)／(5/3)＝1/5，A<sub>5</sub>退出． </p><p> z<sup>(２)</sup>＝z<sup>(１)</sup>+ λ<sup>(１)</sup>λ<sub>２</sub><sup>(１)</sup>＝12/5，以a<sub>22</sub>为主元，<br> 消元． ( P<sup>(1)</sup> P<sub>0</sub><sup>(1)</sup> )→ (P<sup>(2)</sup> P0<sup>(2)</sup> ) <br> ∧<sup>(1)</sup>→∧<sup>(2)</sup>＝(－3/5，－6/5，0 , 0 , －1)<br>过程用表法表示：<br><br></p><div align="left"><table border="1" width="85%"> <tr> <td width="10%">B</td> <td width="10%">C<sub>B</sub></td> <td width="10%">C<sub>B</sub>B<sup>-1</sup></td> <td width="10%">C</td> <td width="10%">3</td> <td width="10%">6</td> <td width="10%">2</td> <td width="10%">0</td> <td width="10%">0</td> <td width="10%">β</td> </tr> <tr> <td width="10%"> </td> <td width="10%"> </td> <td width="10%"> </td> <td width="10%">P<sub>0</sub></td> <td width="10%">P<sub>1</sub></td> <td width="10%">P<sub>2</sub></td> <td width="10%">P<sub>3</sub></td> <td width="10%">P<sub>4</sub></td> <td width="10%">P<sub>5</sub></td> <td width="10%"> </td> </tr> <tr> <td width="10%">A<sub>4</sub></td> <td width="10%">0</td> <td width="10%">0</td> <td width="10%">2</td> <td width="10%">(3)</td> <td width="10%">4</td> <td width="10%">1</td> <td width="10%">0</td> <td width="10%">0</td> <td width="10%">(2/3)</td> </tr> <tr> <td width="10%">A<sub>5</sub></td> <td width="10%">0</td> <td width="10%">0</td> <td width="10%">1</td> <td width="10%">1</td> <td width="10%">3</td> <td width="10%">2</td> <td width="10%">0</td> <td width="10%">1</td> <td width="10%">1</td> </tr> <tr> <td width="10%"> </td> <td width="10%"> </td> <td width="10%">z=0</td> <td width="10%"> </td> <td width="10%">3</td> <td width="10%"> </td> <td width="10%"> </td> <td width="10%"> </td> <td width="10%"> </td> <td width="10%">←λ</td> </tr></table></div><p> </p><div align="left"><table border="1" width="85%"> <tr> <td width="10%">B</td> <td width="10%">C<sub>B</sub></td> <td width="10%">C<sub>B</sub>B<sup>-1</sup></td> <td width="10%">C</td> <td width="10%">3</td> <td width="10%">6</td> <td width="10%">2</td> <td width="10%">0</td> <td width="10%">0</td> <td width="10%">β</td> </tr> <tr> <td width="10%"> </td> <td width="10%"> </td> <td width="10%"> </td> <td width="10%">P<sub>0</sub></td> <td width="10%">P<sub>1</sub></td> <td width="10%">P<sub>2</sub></td> <td width="10%">P<sub>3</sub></td> <td width="10%">P<sub>4</sub></td> <td width="10%">P<sub>5</sub></td> <td width="10%"> </td> </tr> <tr> <td width="10%">A<sub>1</sub></td> <td width="10%">3</td> <td width="10%">1</td> <td width="10%">2/3</td> <td width="10%">1</td> <td width="10%">4/3</td> <td width="10%"> </td> <td width="10%">1/3</td> <td width="10%">0</td> <td width="10%">1/2</td> </tr> <tr> <td width="10%">A<sub>5</sub></td> <td width="10%">0</td> <td width="10%">0</td> <td width="10%">1/3</td> <td width="10%">0</td> <td width="10%">(5/3)</td> <td width="10%"> </td> <td width="10%">-1/3</td> <td width="10%">1</td> <td width="10%">1/5</td> </tr> <tr> <td width="10%"> </td> <td width="10%"> </td> <td width="10%">z=2</td> <td width="10%"> </td> <td width="10%"> </td> <td width="10%">2</td> <td width="10%"> </td> <td width="10%"> </td> <td width="10%"> </td> <td width="10%">←λ</td> </tr></table></div><p> </p><div align="left"><table border="1" width="85%"> <tr> <td width="10%">B</td> <td width="10%">C<sub>B</sub></td> <td width="10%">C<sub>B</sub>B<sup>-1</sup></td> <td width="10%">C</td> <td width="10%">3</td> <td width="10%">6</td> <td width="10%">2</td> <td width="10%">0</td> <td width="10%">0</td> <td width="10%">β</td> </tr> <tr> <td width="10%"> </td> <td width="10%"> </td> <td width="10%"> </td> <td width="10%">P<sub>0</sub></td> <td width="10%">P<sub>1</sub></td> <td width="10%">P<sub>2</sub></td> <td width="10%">P<sub>3</sub></td> <td width="10%">P<sub>4</sub></td> <td width="10%">P<sub>5</sub></td> <td width="10%"> </td> </tr> <tr> <td width="10%">A<sub>1</sub></td> <td width="10%">3</td> <td width="10%">3/5</td> <td width="10%">2/5</td> <td width="10%"> </td> <td width="10%">0</td> <td width="10%"> </td> <td width="10%">3/5</td> <td width="10%">-4/5</td> <td width="10%"> </td> </tr> <tr> <td width="10%">A<sub>2</sub></td> <td width="10%">6</td> <td width="10%">6/5</td> <td width="10%">1/5</td> <td width="10%"> </td> <td width="10%">1</td> <td width="10%"> </td> <td width="10%">-1/5</td> <td width="10%">3/5</td> <td width="10%"> </td> </tr> <tr> <td width="10%"> </td> <td width="10%"> </td> <td width="10%">z=12/5</td> <td width="10%"> </td> <td width="10%">0</td> <td width="10%">0</td>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -