最优化理论教案ch2-2 对偶问题的经济意义.doc

《最优化理论教案ch2-2 对偶问题的经济意义.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、教学目的及要求：明确影子价格的概念意义、理解对偶单纯形法的原理,能正确应用、能熟练准确的就C、b、A中的各元素发生变化来进行灵敏度分析，求出新的最优解。教学重点、难点：对偶单纯形法的原理、灵敏度分析。教学方法:讲授+自学课后作业：page72-73:6（2）、⑷、8§2-3对偶问题的经济意义单纯形法的每步迭代屮，目标函数取值z=和检验数N屮都有乘子Y=（C：B"）T,那么Y的经济意义是什么？设B是线性规划问题MaxZ=CTX.AX

2、1。设儿，儿，儿是空间的点的坐标,H点即为最优点，该问题的最优解是）'i=°，『2=136,y3=52,z=42800§2-4对偶单纯形法1对偶单纯形法的基本思路求解线性规划的单纯形法的思路是：对原问题的一个基木可行解，判别是否所有检验数<0（；=1,•.•,/!）o若是，又基变量屮无非零人工变量，即找到了问题；若为否,再找出相邻的目标函数值更人的基可行解，并继续判别，只要最优解存在，就一岚循环进行到找出最优解为止。2对偶单纯形法的计算步骤设某标准形式的线性规划问题maxz=C7Xsi[AX=h也[X>0存在一个对偶问题的可行基不妨设B=（P,

3、P2,…，5），列出单纯形表（见表2-6）。表2-65基bX]・・•£…Y•••人加+1耳…£q••■•■•1…■0…•■0•■•■as…■■a■■•••■■■■■0…■■■1…•■■0■■•%+1…•■■a…rs■■■%■■•5■■0…■0…■1■%”屮…■%…■cj-50…0…05+1一S+i…57…Cn一S表2-6中必须有J一“50()=1,・・・,/1),勺(「=1,…，加)的值不要求为正。当对心1,…，加，有>0时，即表屮原问题和对偶问题均为最优解。否则，通过变换一个基变最，找出原问题的一个目标函数值较小的相邻基本解。1.,确定换

4、出基的变量—_因为总存在小于0的乙，令侏=min{$},其对应变量£为换出基的变量。i2・确定换入基的变量仃)为了使下一个表屮第厂行基变量为正值，因而只有对应VO(J二加+1,…的非基变量才可以考虑作为换入基的变量。(2)为了使下一个表屮对偶问题的解仍为可行解，令0=minJarj<0(2-12)则兀为换入基的变量，称色，为主元素。3.用换入变量替换换岀变量，得到一个新的基。对新的基再检杳是否所有$(心1,…，加)no。如是，找到了两者的最优解，如为否，冋到第1步再循坏进行。例2・6用对偶单纯形法求解下述线性规划问题：min0=15)[+24).

5、+5y36y2+儿n2m怦

6、+2儿+儿ni.)“2，儿解先将问题改写为max0)=一15)[-24)、一5y3+0y4+0y5_6儿_儿+儿=_2M卜5戸_2儿一儿+儿=_1>0(i=l,・・・,5)列出单纯形表，并用上述对偶单纯形法求解步骤进行计算，其过程见表2-7。表2・7勺T-15-24_500基方y2儿)‘4儿0-20[-6]-1100-1-5-2-101Cj-5-15-24-500-24『21/3011/6-1/600儿-1/3_50[-2/3]-1/315-S-150-1-40-24〉‘21/4-5/410-1/41/4_51/215

7、/2011/2-3/2-15/200-7/2-3/23、对偶单纯形法的优点§2-5灵敏度分析1灵敏度分析的步骤1.将参数的改变计算反映到最终单纯形表上来：具体计算方法是，按下列公式计算出由参数Cl』,Cj的变化而引起的最终单纯形表上有关数字的变化。由单纯形法计算的矩阵描述可得出下列各式：A//=B'[b（2-15）=BS（2-16）（勺一5）=勺一工%（2"）/=

8、2.检杳原问题是否仍为可行解；3.检查对偶问题是否仍为可行解；4.按表2-8所列情况得出结论和决定继续计算的步骤。表2・8原问题对偶间题结论或继续计算的步骤可行解可行解非可行解非可行

9、解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算2分析-的变化线性规划目标函数屮变量系数5的变化仅仅影响到检验数c-S）的变化。所以将5的变化肓接反映到最终单纯形表中，貝可能出现如表2-8中的前两种情况。例2-7在第一章例1・9的美佳公司例子屮，（1）若家电I的利润由2元/件降至1.5元/件，而家电II的利润由1元/件增至2元/件时，美佳公司最优生产计划有何变化；⑵若家电I的利润不变，则家电II的利润在什么范用内变化时，则该公司的最优生产计划将不发

10、生变化。解（1）将家电I,II的利润变化直接反映到最终单纯形表（表1-7）屮得表2-9。表2-9JT1.52000基b咼兀2兀3兀40x