📄 6_10.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§6.10</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"><link rel="stylesheet" href="style.css"></head><body><p align="center"><font size="4"><b>§6.10 对偶单纯形法</b></font></p><p> 对于问题: max z＝CX，AX≤b，X≥0;当b中有负元时，<br>就要用二阶段法．现介绍一种对偶单纯形法，它适用<br>于b中有负元的情况．假如松弛变量后，变成AX＝b ,<br>X≥0;若 λ<sub>j</sub>＝ c<sub>j</sub>－z<sub>j</sub>≤0，j＝1 , … , n+m．<br>即∧＝(λ<sub>1</sub> λ<sub>2</sub> … λ<sub>n+m</sub>)≤0<br>已知单纯形表如下：<br></p><div align="left"><table border="1" width="75%"> <tr> <td width="16%">C<sub>B</sub></td> <td width="16%">P<sub>0</sub></td> <td width="17%">P<sub>1</sub></td> <td width="17%">P<sub>2 ........</sub></td> <td width="17%">P<sub>k .......</sub></td> <td width="17%">P<sub>n</sub></td> </tr> <tr> <td width="16%"><span class="overline">C</span><sub>1</sub></td> <td width="16%">b<sub>1</sub></td> <td width="17%">a<sub>11</sub></td> <td width="17%">a<sub>12</sub> <sub>........</sub></td> <td width="17%">a<sub>1k</sub><sup> <sub> </sup>........</sub></td> <td width="17%">a<sub>1n</sub></td> </tr> <tr> <td width="16%"><span class="overline">C</span><sub>2</sub></td> <td width="16%">b<sub>2</sub></td> <td width="17%">a<sub>21</sub></td> <td width="17%">a<sub>22</sub> <sub>........</sub></td> <td width="17%">a<sub>1k</sub> <sub>........</sub></td> <td width="17%">a<sub>1n</sub></td> </tr> <tr> <td width="16%"><sub>........</sub></td> <td width="16%"><sub>........</sub></td> <td width="17%"><sub>........</sub></td> <td width="17%"><sub>........</sub></td> <td width="17%"><sub>........</sub></td> <td width="17%"><sub>........</sub></td> </tr> <tr> <td width="16%"><span class="overline">C</span><sub>r</sub></td> <td width="16%">b<sub>r</sub></td> <td width="17%">a<sub>r1</sub></td> <td width="17%">a<sub>r2</sub> ..........</td> <td width="17%">a<sub>rk</sub> ...........</td> <td width="17%">a<sub>rn</sub> </td> </tr> <tr> <td width="16%"><sup>...........</sup></td> <td width="16%"><sup>...........</sup></td> <td width="17%"><sup>...........</sup></td> <td width="17%"><sup>...........</sup></td> <td width="17%"><sup>...........</sup></td> <td width="17%"><sup>...........</sup></td> </tr> <tr> <td width="16%"><span class="overline">C</span><sub>m</sub></td> <td width="16%">b<sub>m</sub></td> <td width="17%">a<sub>m1</sub></td> <td width="17%">a<sub>m2</sub> ..........</td> <td width="17%">a<sub>mk</sub> ........</td> <td width="17%">a<sub>mn</sub> </td> </tr> <tr> <td width="16%"> </td> <td width="16%"><sub>z<sup>(0)</sup></sub></td> <td width="17%">c<sub>1</sub>-z<sub>1</sub></td> <td width="17%">c<sub>2</sub>-z<sub>2</sub> ......</td> <td width="17%">c<sub>k</sub>-z<sub>k</sub> ........</td> <td width="17%">c<sub>n</sub>-z<sub>n</sub></td> </tr></table></div><p> </p><p>其中b<sub>r</sub>＜0，a<sub>rk</sub>＜0，c<sub>i</sub>－z<sub>i</sub>≤0，i＝1 , … , n．以a<sub>rk</sub>为主元素作行消元得：<br></p><div align="left"><table border="1" width="75%"> <tr> <td width="20%"><span class="overline">C</span><sub>B</sub></td> <td width="20%">P<sub>0</sub></td> <td width="20%">P<sub>1</sub></td> <td width="20%">P<sub>k</sub></td> <td width="20%">P<sub>n</sub></td> </tr> <tr> <td width="20%"><span class="overline">C</span><sub>1</sub></td> <td width="20%">b<sub>1</sub>-(b<sub>r</sub>/a<sub>rk</sub>)a<sub>1k</sub></td> <td width="20%">a<sub>11</sub>-(a<sub>r1</sub>/a<sub>rk</sub>)a<sub>1k</sub> ....</td> <td width="20%">0 ....</td> <td width="20%">a<sub>1n</sub>-(a<sub>rn</sub>/a<sub>rk</sub>)a<sub>1k</sub> </td> </tr> <tr> <td width="20%"><span class="overline">C</span><sub>2</sub></td> <td width="20%">b<sub>2</sub>-(b<sub>r</sub>/a<sub>rk</sub>)a<sub>2k</sub></td> <td width="20%">a<sub>21</sub>-(a<sub>r1</sub>/a<sub>rk</sub>)a<sub>2k</sub> ....</td> <td width="20%">0 ....</td> <td width="20%">a<sub>2n</sub>-(a<sub>rn</sub>/a<sub>rk</sub>)a<sub>2k</sub> ....</td> </tr> <tr> <td width="20%">.....</td> <td width="20%">......</td> <td width="20%">......</td> <td width="20%">......</td> <td width="20%">.....</td> </tr> <tr> <td width="20%"><span class="overline">C</span><sub>k</sub></td> <td width="20%">b<sub>r</sub>/a<sub>rk</sub></td> <td width="20%">a<sub>r1</sub>/a<sub>rk</sub></td> <td width="20%">1 ....</td> <td width="20%">a<sub>rn</sub>/a<sub>rk</sub></td> </tr> <tr> <td width="20%"><sub>.....</sub></td> <td width="20%"><sub>......</sub></td> <td width="20%"><sub>......</sub></td> <td width="20%">......</td> <td width="20%"><sub>......</sub></td> </tr> <tr> <td width="20%"><span class="overline">C</span><sub>m</sub></td> <td width="20%">b<sub>m</sub>-(b<sub>r</sub>/a<sub>rk</sub>)a<sub>mk</sub></td> <td width="20%">a<sub>m1</sub>-(a<sub>r1</sub>/a<sub>rk</sub>)a<sub>mk</sub> ....</td> <td width="20%">0 ....</td> <td width="20%">a<sub>mn</sub>-(a<sub>rn</sub>/a<sub>rk</sub>)a<sub>mk</sub> </td> </tr> <tr> <td width="20%"> </td> <td width="20%">z</td> <td width="20%">c<sub>1</sub>-<span class="overline">z</span><sub>1<sup> ........</sup></sub></td> <td width="20%">0 ....</td> <td width="20%">c<sub>n</sub>-<span class="overline">z</span><sub>n</sub></td> </tr></table></div><p> </p><p><img src="6_10_1.gif" width="342" height="642" alt="6_10_1.gif (9182 bytes)"></p><p><strong>例</strong> <br>min z＝3x<sub>1</sub> + x<sub>2</sub><br>x<sub>1</sub> + x<sub>2</sub>≥1<br>2x<sub>1</sub> + 3x<sub>2</sub>≥2，x<sub>1</sub> , x<sub>2</sub>≥0<br>max w＝－3x<sub>1</sub>－x<sub>2</sub><br>－x<sub>1</sub>－x<sub>2</sub>≤－1<br>－2x<sub>1</sub>－3x<sub>2</sub>≤－2，x<sub>1</sub> , x<sub>2</sub>≥0<br><strong>解</strong><br>引进松弛变量 x<sub>3</sub>，x<sub>4</sub>．<br>Max w＝3x<sub>1</sub>＋x<sub>2</sub><br>－x<sub>1</sub>－x<sub>2</sub> ＋x<sub>3</sub>＝－1<br>－2x<sub>1</sub>－3x<sub>2</sub> ＋x<sub>4</sub>＝－2，x<sub>1</sub> ,… , x<sub>4</sub>≥0<br>右端常数都为负数，但c<sub>k</sub>－z<sub>k</sub>≤0 , k＝1 ,2, 3, 4．<br>其中 c<sub>1</sub>－z<sub>1</sub>＝－3，c<sub>2</sub>－z<sub>2</sub>＝－1，c<sub>3</sub>－z<sub>3</sub>＝0，c<sub>4</sub>－z<sub>4</sub>＝0．<br>对于b<sub>2</sub>＝－2，有<br>min { 3/2 , 1/3 }＝1/3．<br>故选－3为主元素，进行主元素消去法，过程如下表：<br></p><div align="left"><table border="1" width="75%"> <tr> <td width="12%">B</td> <td width="12%">C<sub>B</sub></td> <td width="12%">C</td> <td width="12%">1</td> <td width="13%">2</td> <td width="13%">0</td> <td width="13%">0</td> <td width="13%">0</td> </tr> <tr> <td width="12%"> </td> <td width="12%"> </td> <td width="12%">P<sub>0</sub></td> <td width="12%">P<sub>1</sub></td> <td width="13%">P<sub>2</sub></td> <td width="13%">P<sub>3</sub></td> <td width="13%">P<sub>4</sub></td> <td width="13%">P<sub>5</sub></td> </tr> <tr> <td width="12%">A<sub>3</sub></td> <td width="12%">0</td> <td width="12%">-6</td> <td width="12%">(-3)</td> <td width="13%">-4</td> <td width="13%">1</td> <td width="13%">0</td> <td width="13%">0</td> </tr> <tr> <td width="12%">A<sub>4</sub></td> <td width="12%">0</td> <td width="12%">-3</td> <td width="12%">-1</td> <td width="13%">-3</td> <td width="13%">0</td> <td width="13%">1</td> <td width="13%">0</td> </tr> <tr> <td width="12%">A<sub>5</sub></td> <td width="12%">0</td> <td width="12%">-2</td> <td width="12%">-2</td> <td width="13%">-1</td> <td width="13%">0</td> <td width="13%">0</td> <td width="13%">1</td> </tr> <tr> <td width="12%"> </td> <td width="12%"> </td> <td width="12%"> </td> <td width="12%">1</td> <td width="13%">2</td> <td width="13%">0</td> <td width="13%">0</td> <td width="13%">0</td> </tr></table></div><p> </p><div align="left"><table border="1" width="75%"> <tr> <td width="12%">B</td> <td width="12%">C<sub>B</sub></td> <td width="12%">C</td> <td width="12%">1</td> <td width="13%">2</td> <td width="13%">0</td> <td width="13%">0</td>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -