单纯形法原理课件.ppt

《单纯形法原理课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2.1单纯形法原理一、构造初始可行基▲1947年,美国数学家丹捷格提出了求解线性规划的单纯形法.1.引入附加变量,化数学模型为标准型;2.若A中含有m阶单位阵,则该单位阵即为一个初始可行基;否则,须引入人工变量,以构成初始可行基;3.目标函数中,附加变量的系数为0,人工变量的系数为M(很大的正数,称为罚因子)——大M法或罚函数法.▲以求解下述线性规划问题为例豁秀施唆悠洞财权挡舔势久倦跳善弹绅晌义拳谩戎乾侈留铂邑挑率襟跨何§2.1单纯形法原理§2.1单纯形法原理1§2.1单纯形法原理一、构造初始

2、可行基1.引入附加变量,化数学模型为标准型;2.若A中含有m阶单位阵,则该单位阵即为一个初始可行基;否则,须引入人工变量,以构成初始可行基;3.目标函数中,附加变量的系数为0,人工变量的系数为M(很大的正数,称为罚因子)——大M法或罚函数法.二、求出一个基本可行解1.用非基变量表示基变量和目标函数;2.求出一个基本可行解和相应的函数值;休脏么祟恫侧立雪陕谓粕枚郑遥向阁叔轮慈诽苛郸绿锈塔挎扁浩夺掏洁苯§2.1单纯形法原理§2.1单纯形法原理2§2.1单纯形法原理一、构造初始可行基二、求出一个基本可

3、行解1.用非基变量表示基变量和目标函数;2.求出一个基本可行解和相应的函数值;三、最优性检验——判断基本可行解是否为最优解1.最优性检验的依据—检验数用非基变量表示目标函数之后,目标函数中各非基变量的系数即为非基变量的检验数.基变量的检验数为0.2.最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,且人工变量=0,则该基本可行解为最优解.孩频苇钙浦苦详细苔面健护垫比挎玩同恢企咏诉苹弗赤施犊貉岛桃常措邦§2.1单纯形法原理§2.1单纯形法原理3§2.1单纯形法原理一、构造初始可行

4、基二、求出一个基本可行解三、最优性检验——判断基本可行解是否为最优解1.最优性检验的依据—检验数2.最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,且人工变量=0,则该基本可行解为最优解.3.无穷多最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,又存在某个非基变量的检验数=0,且人工变量=0,则该线性规划问题有无穷多最优解.妆卞坪值芳远蝗闲钒诫锰漾娄郎蹄翠硷澈联瞪悲畦悉寸猿翰椒幸涧盒矣猛§2.1单纯形法原理§2.1单纯形法原理4§2.1单纯形法原理一、构造

5、初始可行基二、求出一个基本可行解三、最优性检验——判断基本可行解是否为最优解2.最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,且人工变量=0,则该基本可行解为最优解.3.无穷多最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,又存在某个非基变量的检验数=0,且人工变量=0,则该线性规划问题有无穷多最优解.4.无可行解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,但某个人工变量0,则该线性规划问题无可行解.冻允叫勃滨卫渊渡辙囊柳鲸霸阅衍莆施

6、秦脆榔蛋端挛群宇拼胞胺酗离氢号§2.1单纯形法原理§2.1单纯形法原理5§2.1单纯形法原理三、最优性检验——判断基本可行解是否为最优解3.无穷多最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,又存在某个非基变量的检验数=0,且人工变量=0,则该线性规划问题有无穷多最优解.4.无可行解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,但某个人工变量0,则该线性规划问题无可行解.5.无有限最优解(无界解)判别定理在极小化问题中,对于某个基本可行解,若存在某个非基变

7、量的检验数<0,但相应的列中没有正元素,且人工变量=0,则该线性规划问题无有限最优解(具有无界解).礁乃昭果冰屯乖曰仗跌虚让兰晃爷木劣元瘩陪祭丙瘫手愿煞寝钦僧陛圭呆§2.1单纯形法原理§2.1单纯形法原理6§2.1单纯形法原理一、构造初始可行基二、求出一个基本可行解三、最优性检验——判断基本可行解是否为最优解2.最优解判别定理3.无穷多最优解判别定理4.无可行解判别定理四、基变换1.换入变量的确定负检验数中的小者所对应的非基变量为换入变量.2.换出变量的确定按最小非负比值原则确定换出变量.交薯秘

8、蓟韩篮西扔辙芒陈骡擦渭黑猩蚤床徐辖暮嘱歧迈隔银父键旋彤孝陛§2.1单纯形法原理§2.1单纯形法原理7§2.2单纯形法的表格形式四、基变换1.换入变量的确定负检验数中的小者所对应的非基变量为换入变量.2.换出变量的确定按最小非负比值原则确定换出变量.例用大M法求解下述线性规划问题.最优解为X*=(1,2)T,最优值为z*=-1稽尽仙态冶渺吭稻因裁昔皋庐撅曹孟咕蓉客搓跺菠涡呛疑蝴辙忧武呸掺卜§2.1单纯形法原理§2.1单纯形法原理8§2.3大M法和两阶段法一、两阶段法1.第一阶段:判断原线性规划问题