《二次规划法两阶段法ppt培训课件》由会员分享，可在线阅读，更多相关《二次规划法两阶段法ppt培训课件（147页珍藏版）》请在金锄头文库上搜索。
1、第四节解线性规划问题的进一步讨论$4.1两阶段法及关于单纯形方法的几点说明$4.2线性规划问题的对偶及对偶单纯形法$4.3练性规划问题的灵敏度分祈粉品课程沥苏学戳$4.1两阶段法及关于单纯形方法的几点说明(0两阶段法第一个阶段是判断线性规划是否有可行解,如果没有可行解,当然就没有基本可行解,计算停止;如果有可行解,按第一阶段的方法可以求得一个初始的基本可行解,使运算进入第二阶段.第二阶段是从这个初始的基本可行解开始,使用单纯形方法或者判定线性规划问题无界,或者求得一个最优解.狼品课程通荞学广设原问题为mincrxSJAr=5(六0)(L4.0E第一阶段是对问题(L.4.1)增加力个人工变量x=
2、(rurtr.Xnm)“后,解如下的辅助问题emin8二乏二动f8十x一日(1.4.2)x0,x,三0犊品课程运苏学E一ZP问题(L.4.1)与它的辅助LP问题(1.4.2)之间的关系Cx刀“xeD=)二0AX口)(L4.D)X么0北者名=|e工Imin“皿二E嘉【,Iminlg一0sdxr+亚=50L42)多犊品课程通茵学Gamin8二ZxH8dnr+林二D(L4.2)x么0,六0m+n个变量的标准形式线性规划人工变量对应的m列构成了一个m阶单位矩阵50第-个基本可行解为x=0,x,=5g=艺5目标函数有下界g0问题(L4.2)必有最优解“狼品课程通茵学G问题(L.4.2)解的情形情形1最优
3、值g=0,目人工变量xjj=n+LD.n+力)皆为非基变量,此时我们已得到原问题(L4.D)的一个基本可行解把人工变量对应的列从单纯形表中去撞,然后直接转入第二阶段:即对原目标函数z=crx应用通常的单纯形法狼品课程通茵学一问题(1.4.2)解的情形情形2最优值g0,说明原问题没有可行解.这时或者原问题的约李方程组不相容,即有秩(4)秩(4,8);或者方程组虽相容,但没有非负解.总之,此时可行区域D=4,/运算结束.情形3最优值g=0,但某些人工变量虽然取值为零,但仍是基变量.狼品课程通莎学GA=(Aho.pnmJ70rn人工变量厅=0a丿0(LSsE)“旋转9=0g值不变蕙】一藁】E翼蕙弋_E薰+/髂sL二史nn|0粉品课程沥苏学E人L,n秩(4)m砂H丿秩(4)=秩(口)m在前几节讨论中我们总假定秩(4)=m,Dx4b,但是对于实阳问题木说,一般地并不知道约丞方程三&组是否满足这些假定.这其实关系不大,上面的分析使我们知道,在寻求初始解的第一阶段总能解决这两个问题.犊品课程运苏学G例1.4.1求解min二5xrl十21xr3英庞颂一加师Cps一4=2l十加十2一s二工二么015犊品课程运苏学
