📄 6_5.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§6.5</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"></head><body><p align="center"><font size="4"><b>§6.5 单纯形法和单纯形表格</b></font></p><p> 由上一节我们知道线性规划问题maxZ=CX, AX=b，X≥0若有解，一定可以在顶点上取得.而一个允许解X对应于一个顶点的充要条 件是其正元分量对应的m个A的列向量线性无关．A有n +m列， 从中取m列对应于一个顶点，最多可能有C(m+n,n)种选择．因而用穷举的方法当m， n都比较大时是行不通的．单纯形法的核心思想是不仅将取值范围限制在顶点上， 而且保证每换一个顶点，目标函数值都有所改善．</p><p><b>１．基变量</b><br>顶点X＝( 0 … 0 b<sub>1</sub> b<sub>2</sub> … b<sub>m</sub> )<sup>T</sup> 的非0元称为基变量， 基变量对应的A的列向量称为基．从一个顶点换到相邻顶点的方法是高斯消元法,即用行的初等变换进行列 消元的方法．<br> 用A<sub>1</sub> , A<sub>2</sub> , … , A<sub>n</sub> , A<sub>n+1</sub> , …, A<sub>n+m</sub> 表示A的列向量．用P<sub>0</sub> , P<sub>1</sub> , … , P<sub>n</sub> , P<sub>n+1</sub> , P<sub>n+m</sub>表示 b及A的列向量经过行的初等变换得到的列向量．设<br>P＝ ( P<sub>1</sub> P<sub>2</sub> … P<sub>n</sub> P<sub>n+1</sub> … P<sub>n+m</sub> )．<br>在P中始终有一组构成m阶单位阵的列向量，我们知道对矩阵进行的初等变换相当于左乘 一个适当的可逆矩阵．不难看出，在这里适当的可逆矩阵就是对应的m个线性无关的A 的列构成矩阵的逆矩阵．设X1是S的顶点，不妨设X<sub>1</sub>＝( α<sub>1</sub> α<sub>2</sub> … α<sub>m</sub> 0 … 0 )<sup>T</sup>，其中 α<sub>1</sub> , α<sub>2</sub> , … , α<sub>m</sub> >0，是基变量，它们构成列向量P<sub>0</sub>． 设B是基变量对应的A的列向量的可逆矩阵，也称为基阵．不妨设 B＝( A<sub>1</sub> A<sub>2</sub> … A<sub>m</sub> )． 于是 A＝( B N ) 其中 N＝( A<sub>m+1</sub> … A<sub>m+n</sub> )．<br> 将上述综合起来有<br>B<sup>-1</sup>( b A<sub>1</sub> A<sub>2</sub> … A<sub>n+m</sub> )＝( P<sub>0</sub> P<sub>1</sub> P<sub>2</sub> … P<sub>n+m</sub> )．<br>由前设可知<br>P<sub>0</sub>＝( α<sub>1</sub> α<sub>2</sub> … α<sub>m</sub> )<sup>T</sup>．<br>再设 P<sub>j</sub>＝(α<sub>1j</sub> α<sub>2j</sub> … α<sub>mj</sub> )<sup>T</sup>，<br>这样就有 BP<sub>j</sub>＝A<sub>j</sub>，BP<sub>0</sub>＝b，<br> A<sub>j</sub>＝BP<sub>j</sub>＝ α<sub>1j</sub>A<sub>1</sub>+ α<sub>2j</sub>A<sub>2</sub>+ … + α<sub>mj</sub>A<sub>m</sub><br>b＝ BP<sub>0</sub>＝α<sub>1</sub>A<sub>1</sub>+ α<sub>2</sub>A<sub>2</sub>+ … + α<sub>m</sub>A<sub>m</sub><br>目标函数值 z ( X<sub>1</sub>)＝ c<sub>1</sub>α<sub>1</sub>+ c<sub>2</sub>α<sub>2</sub> … + c<sub>m</sub>α<sub>m</sub> </p><p><b>2．基的选进和退出</b></p><p> X<sub>B</sub>＝P<sub>0</sub> 对应一个顶点，换顶点对应于换基 一般一次进入一个基，退出一个基．在此过程中要保证：<br> &Nbsp; ( 1 ) 满足约束条件<br> &Nbsp; ( 2 )目标函数有所改善<br> 先看A<sub>j</sub>能否进入，再看哪一列该退出．<br>b＝ α<sub>1</sub>A<sub>1</sub>+ α<sub>2</sub>A<sub>2</sub>+ … + α<sub>m</sub>A<sub>m</sub>－αA<sub>j</sub><br>＝－α (α<sub>1j</sub>A<sub>1</sub>+ α<sub>2j</sub>A<sub>2</sub>+ … + α<sub>mj</sub>A<sub>m</sub> )，<br><img src="6_5_1.gif" width="314" height="45"><br>要从原来的顶点换到新的顶点，就得使 b 仍然表示为恰好m个A的列向量的线性组合， 并且在此组合中m个列向量前面的系数都是正的．为此，令<br><img src="6_5_2.gif" width="158" height="56"><br><img src="6_5_3.gif" width="493" height="254"><br> 设C<sub>B</sub>表示X<sub>1</sub>的基变量在目标函数中的系数构成的m维行向量。 根据前设有<br> z(X<sub>2</sub>)＝z(X<sub>1</sub>)＋β( c<sub>j</sub>－C<sub>B</sub>P<sub>j</sub> ),<br>或表示为增量 △Z＝ β( c<sub>j</sub>－C<sub>B</sub>P<sub>j</sub> ),<br>又因为P<sub>j</sub>＝B<sup>-1</sup>A<sub>j</sub>，于是C<sub>B</sub>P<sub>j</sub>＝C<sub>B</sub>B<sup>-1</sup>A<sub>j</sub>． 同时z(X<sub>1</sub>)＝C<sub>B</sub>P<sub>0</sub>＝C<sub>B</sub>B<sup>-1</sup>b．为了讨论方便，令 z<sub>j</sub>＝C<sub>B</sub>P<sub>j</sub>＝C<sub>B</sub>B<sub>-1</sub>A<sub>j</sub>，λ<sub>j</sub>＝c<sub>j</sub>－z<sub>j</sub>，<br>若λ<sub>j</sub>＞0，则A<sub>j</sub>进入基阵可使目标函数增大，<br>若λ<sub>j</sub>＜0，则A<sub>j</sub>进入基阵可使目标函数减小．<br>但当P<sub>j</sub>≤0，则目标函数在优化方向上无界，该问题就无解．</p><p><b>定理</b> 设X＝( α<sub>1</sub> α<sub>2</sub> … α<sub>m</sub> 0 … 0 ) 是线性规 划问题maxZ＝CX，AX＝b，X≥0的一个解.A<sub>1</sub>，A<sub>2</sub>，…，A<sub>m</sub>是X的正元对应的基． 如果λ<sub>j</sub>≤0，j＝1，2，… ，n+m，则X是最大值点 其中λ<sub>j</sub>＝c<sub>j</sub>－C<sub>B</sub>B<sup>-1</sup>A<sub>j</sub>，B＝( A<sub>1</sub> A<sub>2</sub> … A<sub>m</sub> )．</p><p><b>证</b> 设S是线性规划问题的允许解域，任给Y∈S，z(Y)＝CY．根据假设λ<sub>j</sub>≤0，即<br>c<sub>j</sub>≤z<sub>j</sub>，j＝1，2，… ,n＋m．写成矩阵形式就是<br>C≤(C<sub>B</sub>P<sub>1</sub>,C<sub>B</sub>P<sub>2</sub> , … , C<sub>B</sub>P<sub>n+m</sub> )，<br>C≤(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≤ C<sub>B</sub>B<sup>-1</sup>A<sub>j</sub><br>于是<br> CY≤ C<sub>B</sub>B<sup>-1</sup>A<sub>j</sub>Y，<br>CY≤ C<sub>B</sub>B<sup>-1</sup>A<sub>j</sub>b<br>而 B<sup>-1</sup>b＝P<sub>0</sub>，C<sub>B</sub>P<sub>0</sub>＝CX．从而<br> CY≤CX，<br>即X是最大值点． <br> 以上对单纯形法的理论及基本计算步骤进行了讨论． 单纯形法是一个反复迭代的过程，有一定的规律可以遵循，便于化为表上作业 法．为表明前后关系，把前面的符号重新规定如下:<br>问题是：maxz＝c<sub>1</sub>x<sub>1</sub>+c<sub>2</sub>x<sub>2</sub>+… +c<sub>n+m</sub>x<sub>n+m</sub>，<br>约束条件：<br><img src="6_5_4.gif" width="761" height="297"><br>x<sub>1</sub>, x<sub>2</sub> , … , x<sub>n+m</sub>≥0。 </p><p> &nbsp; 其中<br>c<sub>n+1</sub>＝c<sub>n+2</sub>＝… ＝c<sub>n+m</sub>＝0．<br>P<sub>j</sub>＝( a<sub>1j</sub><sup>(0)</sup> a<sub>1j</sub><sup>(0)</sup> ··· ··· a<sub>1j</sub><sup>(0)</sup>)<sup>T</sup> , j＝1 , 2 , … , n+m．<br>P<sub>0</sub>＝( b<sub>1</sub><sup>(0)</sup> b<sub>2</sub><sup>(0)</sup> ··· b<sub>m</sub><sup>(0)</sup>)<sup>T</sup> ．<br>计算步骤：<br>( 1 ) 计算 z<sup>0</sup>及c<sub>j</sub>－z<sub>j</sub>．<br>如果c<sub>j</sub>－z<sub>j</sub>≤0，j＝1 , 2 , … , n+m，则不可能使目标函数有所改善， 故问题的最优解是<br>x<sub>b1</sub>＝b<sub>1</sub><sup>(0)</sup>， x<sub>b2</sub>＝b<sub>2</sub><sup>(0)</sup>，… , x<sub>bm</sub>＝b<sub>m</sub><sup>(0)</sup>，<br>x<sub>j</sub>＝0，j≠b<sub>1</sub> , b<sub>2</sub> , … , b<sub>m</sub> , 1≤ j ≤n+m． 这时目标函数值即为 z<sup>0</sup> <br>( 2 ) 如若不然，进入的基P<sub>j</sub>的选取应满足 c<sub>j</sub>－z<sub>j</sub>＞0, 然而当n很大时，增加了很多计算量，所以也 可以选第一个c<sub>j</sub>－ z<sub>j</sub>＞0．确定了进入基P<sub>j</sub>后,计算 <img src="6_5_5.gif"width="224" height="64"><br>以确定退出的基P<sub>k</sub>．<br>( 3 ) 表中第k行第 j 列元素a<sub>kj</sub><sup>(0)</sup>取作主元素，对第 j 列进行消元． 把所得的结果写入表，返回( 1 )．这样周而复始，直至达到最优． </p><p><b>例 1</b><br>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．</p><p>解:<br></p><table border="1" width="75%"> <tr> <td width="11%">B</td> <td width="11%">C<sub>B</sub></td> <td width="11%">C→</td> <td width="11%">3</td> <td width="11%">6</td> <td width="11%">2</td> <td width="11%">0</td> <td width="11%">0</td> <td width="12%">β</td> </tr> <tr> <td width="11%"> </td> <td width="11%"> </td> <td width="11%">P<sub>0</sub></td> <td width="11%">P<sub>1</sub></td> <td width="11%">P<sub>2</sub></td> <td width="11%">P<sub>3</sub></td> <td width="11%">P<sub>4</sub></td> <td width="11%">P<sub>5</sub></td> <td width="12%"> </td> </tr> <tr> <td width="11%">A<sub>4</sub></td> <td width="11%">0</td> <td width="11%">2</td> <td width="11%">3</td> <td width="11%">4</td> <td width="11%">1</td> <td width="11%">1 </td> <td width="11%">0</td> <td width="12%">1/2</td> </tr> <tr> <td width="11%">A<sub>5</sub></td> <td width="11%">0</td> <td width="11%">1</td> <td width="11%">1</td> <td width="11%">(3)</td> <td width="11%">2</td> <td width="11%">0</td> <td width="11%">1</td> <td width="12%">(1/3)</td> </tr> <tr> <td width="11%"> </td> <td width="11%">z=0</td> <td width="11%"> </td> <td width="11%">3</td> <td width="11%">6</td> <td width="11%">2</td> <td width="11%">0</td> <td width="11%">0</td> <td width="12%">←λ</td> </tr></table><p> </p><table border="1" width="75%"> <tr> <td width="11%">B</td> <td width="11%">C<sub>B</sub></td> <td width="11%">C→</td> <td width="11%">3</td> <td width="11%">6</td> <td width="11%">2</td> <td width="11%">0</td> <td width="11%">0</td> <td width="12%">β</td> </tr> <tr> <td width="11%"> </td> <td width="11%"> </td> <td width="11%">P<sub>0</sub></td> <td width="11%">P<sub>1</sub></td> <td width="11%">P<sub>2</sub></td> <td width="11%">P<sub>3</sub></td> <td width="11%">P<sub>4</sub></td> <td width="11%">P<sub>5</sub></td> <td width="12%"> </td> </tr> <tr> <td width="11%">A<sub>4</sub></td> <td width="11%">0</td> <td width="11%">2/3</td> <td width="11%">(5/3)</td> <td width="11%">0</td> <td width="11%">-5/3</td> <td width="11%">1</td> <td width="11%">-4/3 </td> <td width="12%">(2/5)</td> </tr> <tr> <td width="11%">A<sub>2</sub></td> <td width="11%">6</td> <td width="11%">1/3</td> <td width="11%">1/3</td> <td width="11%">1</td> <td width="11%">2/3</td> <td width="11%">0</td> <td width="11%">1/3</td> <td width="12%">1</td> </tr> <tr> <td width="11%"> </td> <td width="11%">z=2</td> <td width="11%"> </td> <td width="11%">(1)</td> <td width="11%">0</td> <td width="11%">-2</td> <td width="11%">0</td>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -