运筹学—106人工变量法.ppt

信息系刘康泽信息系 刘康泽人工变量法人工变量法信息系刘康泽人工变量法（无初始可行基求最优解）前面所介绍的单纯形方法是：当线性规划问题有一个现成的可行基时，如何去求解线性规划问题的最优解然而，当一个线性规划问题不存在现成的初始可行基，甚至连判断约束方程组的 系数矩阵A 是否满秩、有无可行解都很困难时，就要采用下面的人工变量先求原线性规划问题的第一个可行基，然后再用上述的单纯形方法，去求最优解或判定无最优解 一、大M 法基本思想:在约束条件中添加人工变量 yi ， 将yi 作为基变量，迅速得到 一组初始可行基，使得单纯形算法能够顺利实施 信息系刘康泽注意到人工变量是后加入到原约束方程中的变量，它破坏了 原有的约束条件，同时还要求它对目标函数的取值不造成影响 因此必须让人工变量 yi 尽快出基，成为非基变量，因为非基变量 的取值为0，从而达到不破坏原有约束且对目标函数的取值不造成 影响的目的具体的说：若经过换基迭代．基变量中无人工变量，则原问 题有可行解若基变量中还有人工变量，并且检验数已经全部是 非正数，则原问题元可行解 为此我们修改目标函数，在目标函数中加一个惩罚项 M yi ， 其中M 是一个可以任意大的正数，只要目标函数中还存在大M ， 则问题将达不到最小值，这样在实现目标函数最小化的过程中， 将迫使人工变量逐逐个替换出基。

最终得到一组完全由原问题中 的变量构成的初始可行基继续使用单纯形算法，便可以得到问 题的最优解或判定问题无解信息系刘康泽注意：在换基迭代中，一旦人工变量全部化成非基变量，就可将人工变量所在的列从单纯形表中删除若此时尚未得到原问 题的最优解，则继续换基迭代，直至求出最优解或判定无最优为 止例、用大M方法求解线性规划问题：解：引入松弛变量x3, x4及剩余变量x5 ，( 松弛变量与剩余变量不是人工变量 ) 将最大化改为最小化，问题化成标准型：信息系刘康泽因无现行的初始可行基，故引入人工变量 y1 , y2 ，使原问题进一步化成如下形式： 信息系刘康泽64000－M －M x32310000100 x43201000120 y1100001014 y20100－10122列出原始数据表:（不是单纯形表，因为基变量的检验数不是0）6＋M4＋M00－M00 x32310000100 x43201000120 y1100001014 y20100－10122将第3行及第4行的－M倍加到检验数行，便得到初始单纯形表:x1 换基迭代：得下一张单纯形表信息系刘康泽04＋M00－M－5－M0－84＋22M x303100－2072 x402010－4054 x1100001014 y20100－101220000－4－6－M－4－ M－172 x300103－2－372 x400012－4－254 x1100001014 x20100－10122x2 此时人工变量已全部出基, 划去人工变量, 得原问题的初始可行基原 问 题 中 的 变 量信息系刘康泽0000－4－172 x30010372 x40001254 x11000014 x20100－122这已经是原问题的最优表，最优解为: x1 =14 , x2 =22。

最优值为: f = 172信息系刘康泽例： 用大M方法求解线性规划问题标准化:添加人工变量 y 有：得原始数据表：信息系刘康泽1100－M0x3－111000y－310－1131－3M1+M0－M03Mx3－111000 y－310－113x2 2－2M0－1－M－M03Mx2－111000 y－20－1－113信息系刘康泽因为检验数都≤0，所以此表对应的基为最优基，其中人工变量 y ＝ 3M ≠ 0 ， 人工变量 y 仍留在基中， 于是原线性规划问题无可行解一般地，设问题为：对每一个约束方程分别加入人工变量信息系刘康泽问题（2）达到最优解，但有些人工变量的取值不为 0 ， 即人工变量没有完全出基，此时原问题（1）无可行解问题（2）的某张单纯形表中的检验数λk ≥ 0，且λk下方的 系数列≤0，又人工变量全部取 0，此时原问题（1）无界问题（2）的某张单纯形表中的检验数λk ≥ 0，且λk下方的 系数列≤0， ，但有些人工变量不等于 0 ，此时原问题（1）无可行解问题（2）达到最优解 , 且人工变量全部取 0 ，此时在最优表中划去人工变量所在的列，余下的就是原问题的最优单纯形 表，由此得到原问题（1）的最优解。

对问题（2）使用单纯形方法，可能出现如下几种情况：信息系刘康泽二、两阶段法基本思想:两阶段方法是在原线性规划问题引入人工变量以后用两个阶 段来求解问题的一种方法 设原问题为：第二阶段：如果第一阶段表明原问题存在可行基，则在第一 阶段得到可行基对应的单纯形表上，去掉人工变量所在的行与列 ，再从这个原问题的可行基出发，用单纯形方法去求解原问题的 最优解第一阶段：引入人工变量，构造一个辅助问题，用单纯形方 法求解辅助问题，其目的是为了判断原问题是否存在可行基； 信息系刘康泽构造辅助问题如下：引入人工变量称基 为人造基，显然辅助问题（2）有现成的初始可行基： 对应的基解是：信息系刘康泽问题（2）是一个标准的具有m+n个变量的线性规划问题，目 标函数 有一个明显的下界Z ＝0，因此 问题（2）必定有最优解于是可用单纯形法去求解它称这个求 解过程为第一阶段在该阶段中逐步将人工变量迭代出基，而使原 问题中的变量成为基变量注1 】 问题（2）的约束中增加条件 其目的在于：在第一阶段的迭代中记录原问题目标函数的非 基变量表示，从而在第一阶段结束时直接得到原问题初始单纯形 表中的检验数。

注2】 为得到第一阶段的初始单纯形表，往往先写出问题（ 2）的原始数据表，然后将原始数据表中对应人工变量的行加到首 行（检验数行）即可信息系刘康泽问题（2）的原始数据表：00…0－1－1…－10－c1 －c2 …－cn 0a11a12…a1n10…0b1a21a22…a2n010b2 ……………………… am1am2…amn00…1bm将原始数据表中对应人工变量的行加到首行（目标行）得：信息系刘康泽…00…0－c1 －c2 …－cn 0a11a12…a1n10…0b1a21a22…a2n01…0b2 ………………………am1am2…amn00…1bm第一阶段的初始单纯形表：信息系刘康泽值得注意的是：用单纯形方法求出的第一阶段（辅助问题） 的最优基不是原线性规划问题的最优基这个最优基与原线性规划问题的最优基有什么关系？ 事实上，求解辅助问题可能出现如下三种情况：（1）若在辅助问题的最优基中最小值取到下界 0 , 且人工变量 全部出基，即人工变量全部成为非基变量， 而对应的 m 个基变量 全部为原问题中的 x 变量 则这m 个基变量就是原问题的初始可 行基此时只要在辅助问题最优单纯形表中划去人工变量对应的列 以及首行，便得到原问题初始可行基和所对应的单纯形表。

然后 开始对原问题的求解，这就是第二阶段2）若在辅助问题的最优基中还含有人工变量 y ，但最小值取 到下界0 , 这时人工变量 y 的取值一定为0 （属于退化情况） ，信息系刘康泽因此辅助问题的这个最优基还不是原问题的基（因为原变量 还未能完全进基），更谈不上是原问题的可行基这时可用主元消去法把原问题中某些非基变量引进基，而替 换出基变量中的人工变量再开始第二阶段的单纯形法注3】：由于人工变量的取值为0，在替换该人工变量出基迭代中，不影响其它变量的取值及目标函数值，也就是说迭代后仍 然保持最优解和最优值因此在选择主元时不必遵循单纯形法所 规定的进出基原则只要保证人工变量出基，而原变量进基就可 以了3）若辅助问题对应于最优基的目标函数值大于零，即最优 解min Z＞0，这说明基变量中有人工变量（人工变量的取值大于 0），此时原问题无可行解信息系刘康泽例、某产品重量150克，要用A、B两种原料制戊，每单位原 料成本A种为2元，B种为8元该产品至少需要含14单位的B种原 料，最多需要含20单位的A种原料每单位原料的重量：A种5克 ，B种为10克为使成本最小，该产品中A、B两种原料应各占多 少?解：设 x1, x2 分别为A、B 两种原料的使用量，则问题的数 学模型为引入松弛变量x3及剩余变量x4 ，使问题化成标准型:信息系刘康泽因无现行的初始可行基，引入人工变量 y1, y2，构造辅助 问题：信息系刘康泽0000－1－10 －2－8000 y1 5100010150x310100020 y3 010－101145110－100164 －2－8000 y1 5100010150x310100020 y3 010－10114第一阶段开始第一阶段的初始单纯形表为：原始数据表为：信息系刘康泽011－5－10064 0－82040 y1 010－501050x110100020 y3 010－10114001／2－1－11／1009 00－2080x2 01－1／201／1005x110100020y3 001／2－1－1／1019信息系刘康泽00000－10 000－4116 x2 010－10114x110021／502x3001－2－1／5218因为第一阶段的检验数都≤0 ，所以此时的基为最优基，且最优解Z ＝0 ，由于人工变量都巳出基，故可进入第二阶段：划去辅助问题目标行（Z 所在的行），划去人工变量所在的列，得原问题相对应的单纯形表：信息系刘康泽又因为检验数已全部非正，所以此时的基已是原问题的最 优基，且最优解为 x1＝ 2， x2 ＝14 ，最优值为 f ＝116 。

也 就是使用2单位的A 种原料和 14 单位的 B 种原料时，可使所 需的产品成本达到最小，最小值为116元 000－4116 x2 010－114x110022 x3001－218信息系刘康泽解：无现行初始可行基，引入人工变量 y1, y2 ，得辅助问题：例、信息系刘康泽第一阶段开始原始数据表为： 00000－1 －10 13－1000 y1 01210104 x5 －12111004 y2 3031001431520008 13－1000 y1 01210104 x5 －12111004 y2 30310014第一阶段的初始单纯形表为：信息系刘康泽－2101／300－5／34／3 2301／304／3 y1 －2101／301－2／34／3 x5 －2202／310－1／38／3 x31011／3001／34／3－1000－1／20－3／20 500－2／3－3／2－8／3 y1 －1000－1／21－1／20 x2－1101／31／20－1／64／3 x31011／3001／34／3因第一阶段的检验数都≤0 ，所以此时的基为最优基，但人工变量 y1 还在基 中，选择 －1作为主元，作换基迭代（此时不必遵循单纯形法所的进出基原则）人 工 变 量 还 在 基 中信息系刘康泽00000－1－10 000－2／3－4－8／3 x1 10001／2－11／20 x20101／31－11／34／3 x30011／3－1／21－1／64／3000－2／3－4－8／3 x1 10001／20 x20101／314／3 x30011／3－1／24／3由于人工变量都巳出基，故可进入第二阶段：划去辅助问 题目标行及人工变量所在的列， 得原问题的单纯形表：此表已是原问题的最优表，最优解,最优值为信息系刘康泽例、用两阶段法求解线性规划问题：引入松弛变量，将问题化成标准型：信息系刘康泽因无现行的初始可行基，故构造辅助线性规划问题00000－1－10 1－20000 y1 －12－1－10101 y2 －1 －210－1016原始数据表：信息系刘康泽－200－1－1007 1－20000 y1 －12－1－10101 y2 －1 －210－1016。