📄 6_9.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§6.9</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"></head><body><p align="center"><font size="4"><b>§6.9 对偶原理</b></font></p><p><strong>１．对偶概念</strong><br>问题P：max z＝CX，AX≤b，X≥0，<br>问题D：min w＝Yb，YA≥c，Y≥0．<br>其中 A＝( a<sub>ij</sub> )<sub>m×n</sub>，b＝( b<sub>i</sub> )<sub>m×1</sub>，C＝( c<sub>j</sub> )<sub>1×n</sub>，X＝( x<sub>j</sub> )<sub>n×1</sub>，Y＝(y<sub>i</sub>)<sub>1×m</sub>．<br><strong>定义 问题D称为问题P的对偶问题．<br></strong>D等价于 max w＝( －b<sup>T</sup> )Y<sup>T</sup>，(－A<sup>T</sup>)Y<sup>T</sup>≤－C<sup>T</sup>，Y<sup>T</sup>≥0，<br>按定义，这个问题的对偶问题就是<br>min z＝－CX，X<sup>T</sup> (－A<sup>T</sup> )≥(－b<sup>T</sup> )<sup>T</sup>，X≥0。<br>即 max z＝CX，AX≤b，X≥0。<br>由此可知，D，P互为对偶问题。<br>２．对偶问题的经济解释<br>( P') min z ＝CX，AX≥b，X≥0：消费者<br>( D') max w＝Yb，YA≤c，Y≥0：工厂<br>A＝( a<sub>ij</sub> )<sub>m×n</sub>，m种营养素，n种食品．<br>a<sub>ij</sub>：第 j 种食品中含第 i 种营养素的比例<br>B：营养素需要量表，C：食品价格表，<br>X：消费者对每种食品的购买量表，<br>Y：营养素工厂制定的营养素销售价格表．<br>∑ a<sub>ij</sub>x<sub>j</sub>≥b<sub>i</sub>，i＝1 , … ,m．消费者所购食品应满足对第 i 种营养素的需要．<br>∑a<sub>ij</sub>y<sub>i</sub>≤c<sub>j</sub>，j＝1, … , n．第 j 种食品用营养素代替应比买这种食品不贵．<br>Yb≤Y(AX)＝(YA)X≤CX</p><p><br><strong>3．非对称的对偶问题<br></strong>在前面提出的对偶问题是对称的，还有一种非对称的对偶问题．<br><br><strong>定理</strong> 问题 (P<sub>1</sub>) maxz＝CX，AX＝b，X≥0的对偶问题是<br>min w＝Yb，YA≥C． (D<sub>1</sub>).(D<sub>1</sub>)中Y无非负的限制．<br><strong></strong></p><p><strong>证</strong> ( P<sub>1</sub> )中的AX＝b等价于AX≤b,AX≥b<br>或 (A -A)<sup>T</sup>X≤(b -b)<sup>T</sup>．<br>而maxz＝CX，(A -A)<sup>T</sup>X≤(b -b)<sup>T</sup>，X≥0，(P<sub>1</sub>)<br>的对偶问题按照定义为<br>min w＝( Y<sub>1</sub>┆Y<sub>2</sub> ) (b -b)<sup>T</sup>，( D )<br>( Y<sub>1</sub>┆Y<sub>2</sub> ) (A -A)<sup>T</sup>≥C，Y<sub>1</sub>≥0，Y<sub>2</sub>≥0．<br>而( Y<sub>1</sub>┆Y<sub>2</sub> )(b -b)<sup>T</sup>＝( Y<sub>1</sub>－Y<sub>2</sub> )b，<br>( Y<sub>1</sub>┆Y<sub>2</sub> )(A -A)<sup>T</sup>＝( Y<sub>1</sub>－Y<sub>2</sub>)A，令<br>Y＝Y<sub>1</sub>－Y<sub>2</sub>,( D )即为<br>min w＝Yb<br>YA≥c， Y无非负限制 <br></p><p><strong>4．对偶定理<br></strong>在前面讨论对偶问题的经济意义时已经说明<br>了 CX≤(YA)X＝Y(AX)≤Yb，X≥0．<br><br><strong>定理</strong> 设X，Y分别是问题（P），（D）的<br>允许解，则X，Y分别是(P)，(D)的最优解的<br>充要条件是CX＝Yb．<br><br><strong>证</strong> 充分性：若CX＝Yb，则X是(P)的最优<br>解，否则存在X<sub>1</sub>，CX<sub>1</sub>＞CX＝Yb，与前面<br>的命题矛盾．同理，Y是(D)的最优解.<br>必要性：设X，Y分别是(P)，(D)的最优解．<br>在(P)中引入松弛变量X<sub>s</sub>，<br>max z＝( C┆0 ) (X X<sub>s</sub>)<sup>T</sup>,<br>( A┆I )(X X<sub>s</sub>)<sup>T</sup>＝b， (X X<sub>s</sub>)<sup>T</sup>≥0．<br>( A┆I )＝( A<sub>1</sub> , …,A<sub>n+m</sub> )设B是最优解对应<br>的一个基矩阵．X<sub>B</sub>＝B<sup>－1</sup>b．C<sub>B</sub>X<sub>B</sub>＝CX．<br>B<sup>－1</sup>( A┆I┆b )＝( P<sub>1</sub>… P<sub>n+m</sub>┆P<sub>0</sub> )，令<br>Y<sub>B</sub>＝C<sub>B</sub>B<sup>－1</sup>．下证Y<sub>B</sub>是(D)的一个最优解．<br>由于XB是最优解，故有 c<sub>j</sub>－z<sub>j</sub>≤0，j＝1,…n+m．<br>( z<sub>1</sub> z<sub>2</sub> … z<sub>n+m</sub> )≥( C┆0),<br>(C<sub>B</sub>B<sup>－1</sup>A<sub>1</sub> C<sub>B</sub>B<sup>－1</sup>A<sub>2</sub> … C<sub>B</sub>B<sup>－1</sup>A<sub>n+m</sub> )≥(C┆0)<br>C<sub>B</sub>B<sup>－1</sup>( A┆I )≥( C┆0 )<br>即C<sub>B</sub>B<sup>－1</sup>A≥C， C<sub>B</sub>B<sup>－1</sup>≥0<br>即Y<sub>B</sub>A≥C，Y<sub>B</sub>≥0．∴Y<sub>B</sub>是(D)的允许解．<br>Y<sub>b</sub>b＝ C<sub>B</sub>B<sup>－1</sup>b＝C<sub>B</sub>X<sub>B</sub>＝CX<br>所以Y<sub>B</sub>是 (D)的最优解．<br></p><p><strong>推论</strong> 互为对偶问题的(P)和(D)必有下列情况之一成立．<br>１．两个问题都有允许解，则其最优解的函数值相等．<br>２．一问题有允许解，但目标函数无界，其对偶问题无允许解；<br>３．两个问题都无允许解．<br><br><strong>５．影子价格<br></strong>重温 2中所赋予(P’) (D’)问题的经济意义．<br>m种食品，n种营养素,A＝( a<sub>ij</sub> )<sub>m×n</sub>，a<sub>ij</sub>每单位第 j 种食<br>品含第 i 种营养素的量<br>C：食品价格表；b：营养素需要量表；<br>X：食品购买量；Y：营养素销售价格<br>P’：min z＝CX，AX≥b，X≥0：消费者<br>D’：maxw＝Yb，YA≤c，Y≥0：营养素厂<br>X<sub>opt</sub>＝B<sup>－1</sup>b , Y<sub>opt</sub>＝C<sub>B</sub>B<sup>－1</sup>, ☆<sub>w</sub>/☆<sub>b</sub>＝C<sub>B</sub>B<sup>－1</sup><br>营养素销售价格见解地由食品价格所决定．故Y<sub>opt</sub>可称为食品价格的影子价格．<br></p><p><strong>6．例<br></strong>min w＝y<sub>1</sub>＋2y<sub>2</sub>，<br>3y<sub>1</sub>＋4y<sub>2</sub>≥6<br>y<sub>1</sub>＋3y<sub>2</sub>≥3<br>2y<sub>1</sub>＋ y<sub>2</sub>≥2<br>y<sub>1</sub> , y<sub>2</sub>≥0<br>引进松弛变量y<sub>3</sub> , y<sub>4</sub> ,y<sub>5</sub>及人工变量y<sub>6</sub> , y<sub>7</sub> ,y<sub>8</sub><br>min w<sub>1</sub>＝y<sub>1</sub>+2y<sub>2</sub>+y<sub>6</sub>+y<sub>7</sub>+y<sub>8</sub><br>3y<sub>1</sub>＋4y<sub>2</sub>－y<sub>3</sub>+ y<sub>6</sub>＝6<br>y<sub>1</sub>＋3y<sub>2</sub>－y<sub>4</sub> + y<sub>7</sub>＝3<br>2y<sub>1</sub>＋ y<sub>2</sub>－y<sub>5</sub>＋y<sub>8</sub>＝2<br>y<sub>1</sub> , … , y<sub>8</sub>≥0<br>其单纯形表如下：<br></p><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%">1</td> <td width="8%">2</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%">6</td> <td width="8%">3</td> <td width="8%">4</td> <td width="8%">-1</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> </tr> <tr> <td width="7%">A<sub>7</sub></td> <td width="7%">1</td> <td width="7%">1</td> <td width="7%">3</td> <td width="8%">1</td> <td width="8%">(3)</td> <td width="8%"> </td> <td width="8%">-1</td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%">1</td> <td width="8%"> </td> <td width="8%">1</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%">2</td> <td width="8%">1</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%">1</td> <td width="8%"> </td> </tr> <tr> <td width="7%"> </td> <td width="7%"> </td> <td width="7%">w<sub>1</sub>=11</td> <td width="7%"> </td> <td width="8%"> </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> </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%">1</td> <td width="8%">2</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%">2</td> <td width="8%">5/3</td> <td width="8%">0</td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%">1</td> <td width="8%">-4/3</td> <td width="8%">0</td> <td width="8%"> </td> </tr> <tr> <td width="7%">A<sub>2</sub></td> <td width="7%">0</td> <td width="7%">-5/3</td> <td width="7%">1</td> <td width="8%">1/3</td> <td width="8%">1</td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%">0</td> <td width="8%">1/3</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%">(5/3)</td> <td width="8%">0</td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%">0</td> <td width="8%">-5/3</td> <td width="8%">1</td> <td width="8%">5/3</td> </tr> <tr> <td width="7%"> </td> <td width="7%"> </td> <td width="7%">w<sub>1</sub>=3</td> <td width="7%"> </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> <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%">1</td> <td width="8%">2</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%">1</td> <td width="8%">0</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%">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%">4/5</td> <td width="8%">0</td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%">1/5</td> <td width="8%">0</td> <td width="8%">2/5</td> <td width="8%">-1/5</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%">3/5</td> <td width="8%">1</td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%"> </td> <td width="8%">-3/5</td> <td width="8%">0</td> <td width="8%">-1/5</td> <td width="8%">3/5</td> <td width="8%"> </td> </tr> <tr> <td width="7%"> </td> <td width="7%"> </td> <td width="7%">w<sub>1</sub>=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>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -