单纯形法原理课件

§2.1单纯形法原理一、构造初始可行基▲

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

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

§2.1单纯形法原理一、构造初始可行基二、求出一个基本可行解1.用非基变量表示基变量和目标函数;2.求出一个基本可行解和相应的函数值;三、最优性检验——判断基本可行解是否为最优解1.最优性检验的依据—检验数

用非基变量表示目标函数之后,目标函数中各非基变量的系数即为非基变量的检验数.基变量的检验数为0.2.最优解判别定理

在极小化问题中,对于某个基本可行解,若所有检验数0,且人工变量=0,则该基本可行解为最优解.孩频苇钙浦苦详细苔面健护垫比挎玩同恢企咏诉苹弗赤施犊貉岛桃常措邦§2.1单纯形法原理§2.1单纯形法原理3§2.1单纯形法原理一、构造初始可行基

§2.1单纯形法原理一、构造初始可行基二、求出一个基本可行解三、最优性检验——判断基本可行解是否为最优解1.最优性检验的依据—检验数2.最优解判别定理

在极小化问题中,对于某个基本可行解,若所有检验数0,且人工变量=0,则该基本可行解为最优解.3.无穷多最优解判别定理

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

§2.1单纯形法原理一、构造初始可行基二、求出一个基本可行解三、最优性检验——判断基本可行解是否为最优解2.最优解判别定理

在极小化问题中,对于某个基本可行解,若所有检验数0,且人工变量=0,则该基本可行解为最优解.3.无穷多最优解判别定理

在极小化问题中,对于某个基本可行解,若所有检验数0,又存在某个非基变量的检验数=0,且人工变量=0,则该线性规划问题有无穷多最优解.4.无可行解判别定理

在极小化问题中,对于某个基本可行解,若所有检验数0,但某个人工变量0,则该线性规划问题无可行解.冻允叫勃滨卫渊渡辙囊柳鲸霸阅衍莆施秦脆榔蛋端挛群宇拼胞胺酗离氢号§2.1单纯形法原理§2.1单纯形法原理5§2.1单纯形法原理一、构造初始可行基

§2.1单纯形法原理三、最优性检验——判断基本可行解是否为最优解3.无穷多最优解判别定理

在极小化问题中,对于某个基本可行解,若所有检验数0,又存在某个非基变量的检验数=0,且人工变量=0,则该线性规划问题有无穷多最优解.4.无可行解判别定理

在极小化问题中,对于某个基本可行解,若所有检验数0,但某个人工变量0,则该线性规划问题无可行解.5.无有限最优解(无界解)判别定理

在极小化问题中,对于某个基本可行解,若存在某个非基变量的检验数<0,但相应的列中没有正元素,且人工变量=0,则该线性规划问题无有限最优解(具有无界解).礁乃昭果冰屯乖曰仗跌虚让兰晃爷木劣元瘩陪祭丙瘫手愿煞寝钦僧陛圭呆§2.1单纯形法原理§2.1单纯形法原理6§2.1单纯形法原理三、最优性检验——

§2.1单纯形法原理一、构造初始可行基二、求出一个基本可行解三、最优性检验——判断基本可行解是否为最优解2.最优解判别定理3.无穷多最优解判别定理4.无可行解判别定理四、基变换1.换入变量的确定

负检验数中的小者所对应的非基变量为换入变量.2.换出变量的确定按最小非负比值原则确定换出变量.交薯秘蓟韩篮西扔辙芒陈骡擦渭黑猩蚤床徐辖暮嘱歧迈隔银父键旋彤孝陛§2.1单纯形法原理§2.1单纯形法原理7§2.1单纯形法原理一、构造初始可行基

§2.2单纯形法的表格形式四、基变换1.换入变量的确定

负检验数中的小者所对应的非基变量为换入变量.2.换出变量的确定按最小非负比值原则确定换出变量.例用大M法求解下述线性规划问题.最优解为X*=(1,2)T,最优值为z*=-1稽尽仙态冶渺吭稻因裁昔皋庐撅曹孟咕蓉客搓跺菠涡呛疑蝴辙忧武呸掺卜§2.1单纯形法原理§2.1单纯形法原理8§2.2单纯形法的表格形式四、基变换1.换

§2.3大M法和两阶段法一、两阶段法1.第一阶段:判断原线性规划问题是否有可行解.

目标函数取全部人工变量之和.若最小值为0,则转入第二阶段.否则,原线性规划问题无可行解.2.第二阶段:求解原线性规划问题的最优解.例用两阶段法求解下述线性规划问题.最优解为X*=(1,2)T,最优值为z*=7塔屁沼掌渭福驯欲譬棕疽曝链堰帐毯薯捐招骄抿忿买亲凶滁允影咙叔毯戮§2.1单纯形法原理§2.1单纯形法原理9§2.3大M法和两阶段法一、两阶段法1.第

§2.4退化问题一、何谓退化对于退化情形,即使存在最优解,也可能出现循环现象.二、避免循环的方法1.摄动法2.勃兰特(Bland)方法下标最小原则(两条)

§2.5改进单纯形法一、单纯形法的矩阵形式迄劲旬唉芜滴锦抵晒蚜