📄 6_7.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§6.7</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"></head><body><p align="center"><font size="4"><b>§6.7 二阶段法与大M法</b></font></p><p><b>1．二阶段法</b><br> 线性规划问题的最优解在允许解域的顶点取得．单纯形法的基本思想是从一个顶点出发 找到另一个顶点，使目标函数值有所改善，经过有限步便可得到最优解． 但有一个前提必须先找到一个属于允许解域的顶点．二阶段法的第一阶段设法找到一顶点，第二阶段 从此起步． </p><p><strong>例</strong> <br>minz＝2x<sub>1</sub>＋x<sub>2</sub>，<br>3x<sub>1</sub>＋x<sub>2</sub>≥3<br>4x<sub>1</sub>＋3x<sub>2</sub>≥6<br>x<sub>1</sub>＋2x<sub>2</sub>≥2<br>x<sub>1</sub> , x<sub>2</sub>≥0<br><strong>解</strong><br>除了引入松弛变量x<sub>3</sub> , x<sub>4</sub> , x<sub>5</sub>外，还引入人工变量x<sub>6</sub> , x<sub>7</sub> , x<sub>8</sub>，得到<br>minz＝2x<sub>1</sub>＋x<sub>2</sub>，<br>3x<sub>1</sub>＋x<sub>2</sub> －x<sub>3</sub>＋x<sub>6</sub>＝3<br>4x<sub>1</sub>＋3x<sub>2</sub>－x<sub>4</sub>＋x<sub>7</sub>＝6<br>x<sub>1</sub>＋2x<sub>2</sub>－x<sub>5</sub>＋x<sub>8</sub>＝2<br>x<sub>i</sub>≥0，i＝1 , 2, … , 8<br>第一阶段目标函数设为<br>minz’＝x<sub>6</sub> + x<sub>7</sub> + x<sub>8</sub>，<br>目的在于使x<sub>6</sub> , x<sub>7</sub>,x<sub>8</sub>都退出，从而在原问题的允许解域上找到一个顶点．<br>用改善单纯形法计算得：<br></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%">0</td> <td width="8%">0</td> <td width="8%">0</td> <td width="8%">0</td> <td width="8%">0</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%"> </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>6</sub></td> <td width="7%">1</td> <td width="7%">1</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%">1</td> <td width="7%">1</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%">1</td> <td width="7%">1</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'=11</td> <td width="7%"> </td> <td width="8%">-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="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%">0</td> <td width="8%">0</td> <td width="8%">0</td> <td width="8%">0</td> <td width="8%">0</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%"> </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%">0</td> <td width="7%">-5/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%">1</td> <td width="7%">1</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%">1</td> <td width="7%">1</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'=3</td> <td width="7%"> </td> <td width="8%"> </td> <td width="8%">-10/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="7%">C<sub>B</sub>B<sup>-1</sup></td> <td width="7%">C</td> <td width="8%">0</td> <td width="8%">0</td> <td width="8%">0</td> <td width="8%">0</td> <td width="8%">0</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%"> </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%">0</td> <td width="7%">-1</td> <td width="7%">4/5</td> <td width="8%"> </td> <td width="8%">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%">1</td> <td width="7%">1</td> <td width="7%">1</td> <td width="8%"> </td> <td width="8%">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%">0</td> <td width="7%">-1</td> <td width="7%">3/5</td> <td width="8%"> </td> <td width="8%">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="7%">z'=1</td> <td width="7%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%">-1</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%">0</td> <td width="8%">0</td> <td width="8%">0</td> <td width="8%">0</td> <td width="8%">0</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%"> </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%">0</td> <td width="7%">2/5</td> <td width="7%">3/5</td> <td width="8%"> </td> <td width="8%"> </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="7%">1/5</td> <td width="7%">1</td> <td width="8%"> </td> <td width="8%"> </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%">0</td> <td width="7%">0</td> <td width="7%">6/5</td> <td width="8%"> </td> <td width="8%"> </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="7%">z'=0</td> <td width="7%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%">0</td> <td width="8%">1</td> <td width="8%">1</td> <td width="8%">1</td> <td width="8%">←λ</td> </tr></table></div><p>由上表得一允许解：x<sub>1</sub>=3/5 , x<sub>2</sub>＝6/5，x<sub>3</sub>＝x<sub>4</sub>＝0，x<sub>5</sub>＝1．<br>以( 3/5 , 6/5 , 0 , 0 , 1 )为起始点，开始第二阶段．如下表:<br></p><div align="left"><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%">2</td> <td width="11%">1</td> <td width="11%">0</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>1</sub></td> <td width="11%">2</td> <td width="11%">3/5</td> <td width="11%">1</td> <td width="11%">0</td> <td width="11%">-3/5</td> <td width="11%">1/5</td> <td width="11%">0</td> <td width="12%"> </td> </tr> <tr> <td width="11%">A<sub>5</sub></td> <td width="11%">0</td> <td width="11%">1</td> <td width="11%">0</td> <td width="11%">0</td> <td width="11%">1</td> <td width="11%">-1</td> <td width="11%">1</td> <td width="12%"> </td> </tr> <tr> <td width="11%">A<sub>2</sub></td> <td width="11%">1</td> <td width="11%">6/5</td> <td width="11%">0</td> <td width="11%">1</td> <td width="11%">4/5</td> <td width="11%">-3/5</td> <td width="11%">0</td> <td width="12%"> </td> </tr> <tr> <td width="11%"> </td> <td width="11%">z=12/5</td> <td width="11%"> </td> <td width="11%">0</td> <td width="11%">0</td> <td width="11%">2/5</td> <td width="11%">1/5</td> <td width="11%">0</td> <td width="12%">←λ</td> </tr></table></div><p>故得最优解x<sub>1</sub>＝3/5 , x<sub>2</sub>＝6/5 , x<sub>3</sub>＝x<sub>4</sub>＝0 , x<sub>5</sub>＝1．minz＝12/5<br><br><br><img src="6_7_1.gif" width="385" height="308"> </p><p><b>2. 大M法</b></p><p><img src="6_7_2.gif" width="513" height="708"></p><p> </p><p><strong>例</strong> <br>minz＝2x<sub>1</sub>＋x<sub>2</sub>，<br>3x<sub>1</sub>＋x<sub>2</sub>≥3<br>4x<sub>1</sub>＋3x<sub>2</sub>≥6<br>x<sub>1</sub>＋2x<sub>2</sub>≥2<br>x<sub>1</sub> , x<sub>2</sub>≥0<br><strong>解</strong> <br>引入人工变量x<sub>6</sub> , x<sub>7</sub> , x<sub>8</sub>，<br>min z’＝2x<sub>1</sub>+x<sub>2</sub>+6( x<sub>6</sub>+x<sub>7</sub>+x<sub>8</sub> )，用大M法解得：<br></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>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -