matlab常用算法-106人工变量

信息系刘康泽人工变量法人工变量法（无初始可行基求最优解）

前面所介绍的单纯形方法是：当线性规划问题有一个现成的可行基时，如何去求解线性规划问题的最优解。然而，当一个线性规划问题不存在现成的初始可行基，甚至连判断约束方程组的系数矩阵A是否满秩、有无可行解都很困难时，就要采用下面的人工变量先求原线性规划问题的第一个可行基，然后再用上述的单纯形方法，去求最优解或判定无最优解。一、大M

法基本思想:

在约束条件中添加人工变量yi

，将yi

作为基变量，迅速得到一组初始可行基，使得单纯形算法能够顺利实施。

注意到人工变量是后加入到原约束方程中的变量，它破坏了原有的约束条件，同时还要求它对目标函数的取值不造成影响。因此必须让人工变量

yi

尽快出基，成为非基变量，因为非基变量的取值为0，从而达到不破坏原有约束且对目标函数的取值不造成影响的目的。

具体的说：若经过换基迭代．基变量中无人工变量，则原问题有可行解。若基变量中还有人工变量，并且检验数已经全部是非正数，则原问题元可行解。

为此我们修改目标函数，在目标函数中加一个惩罚项M

yi

，其中M

是一个可以任意大的正数，只要目标函数中还存在大M，则问题将达不到最小值，这样在实现目标函数最小化的过程中，将迫使人工变量逐逐个替换出基。最终得到一组完全由原问题中的变量构成的初始可行基。继续使用单纯形算法，便可以得到问题的最优解或判定问题无解。

注意：在换基迭代中，一旦人工变量全部化成非基变量，就可将人工变量所在的列从单纯形表中删除。若此时尚未得到原问题的最优解，则继续换基迭代，直至求出最优解或判定无最优为止。

例、用大M方法求解线性规划问题：解：引入松弛变量x3,

x4及剩余变量x5

，(松弛变量与剩余变量不是人工变量)将最大化改为最小化，问题化成标准型：

因无现行的初始可行基，故引入人工变量y1,y2

，使原问题进一步化成如下形式：64000－M－Mx32310000100x43201000120y1100001014y20100－10122

列出原始数据表:（不是单纯形表，因为基变量的检验数不是0）6＋M4＋M00－M00x32310000100x43201000120y1100001014y20100－10122将第3行及第4行的－M倍加到检验数行，便得到初始单纯形表:x1

换基迭代：得下一张单纯形表04＋M00－M－5－M0－84＋22Mx303100－2072x402010－4054x1100001014y20100－101220000－4－6－M－4－M－172x300103－2－372x400012－4－254x1100001014x20100－10122x2

此时人工变量已全部出基,划去人工变量,得原问题的初始可行基原问题中的变量0000－4－172x30010372x40001254x11000014x20100－122这已经是原问题的最优表，最优解为:

x1=14,

x2=22。

最优值为:f

=172。例：用大M方法求解线性规划问题标准化:

添加人工变量y

有：得原始数据表：1100－M0x3－111000y－310－1131－3M1+M0－M03Mx3－111000y－310－113x2

2－2M0－1－M－M03Mx2－111000y－20－1－113

因为检验数都≤0，所以此表对应的基为最优基，

其中人工变量y

＝3M

≠0，人工变量y

仍留在基中，于是原线性规划问题无可行解。一般地，设问题为：对每一个约束方程分别加入人工变量<2>问题（2）达到最优解，但有些人工变量的取值不为0，即人工变量没有完全出基，此时原问题（1）无可行解。<3>问题（2）的某张单纯形表中的检验数λk≥0，且λk下方的系数列≤0，又人工变量全部取0，此时原问题（1）无界。<4>问题（2）的某张单纯形表中的检验数λk≥0，且λk下方的系数列≤0，，但有些人工变量不等于0，此时原问题（1）无可行解。<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）若辅助问题对应于最优基的目标函数值大于零，即最优解minZ＞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－8000y1

5100010150x310100020y3

010－101145110－100164－2－8000y1

5100010150x310100020y3

010－10114第一阶段开始第一阶段的初始单纯形表为：原始数据表为：011－5－100640－82040y1

010－501050x110100020y3

010－10114001／2－1－11／100900－2080x2

01－1／201／1005x110100020y3

001／2－1－1／101900000－10000－4116x2

010－10114x110021／502x3001－2－1／5218

因为第一阶段的检验数都≤0，所以此时的基为最优基，

且最优解Z＝0，

由于人工变量都巳出基，故可进入第二阶段：

划去辅助问题目标行（Z

所在的行），

划去人工变量所在的列，

得原问题相对应的单纯形表：

又因为检验数已全部非正，所以此时的基已是原问题的最优基，且最优解为

x1＝2，x2

＝14，最优值为f

＝116。也就是使用2单位的A种原料和14单位的B种原料时，可使所需的产品成本达到最小，最小值为116元。000－4116x2

010－114x110022x3001－218

解：无现行初始可行基，引入人工变量y1,

y2

，得辅助问题：例、第一阶段开始原始数据表为：00000－1－1013－1000y1

01210104x5

－12111004y2

303100143152000813－1000y1

01210104x5

－12111004y2

30310014第一阶段的初始单纯形表为：－2101／300－5／34／32301／304／3y1

－2101／301－2／34／3x5

－2202／310－1／38／3x31011／3001／34／3－1000－1／20－3／20500－2／3－3／2－8／3y1

－1000－1／21－1／20x2－1101／31／20－1／64／3x31011／3001／34／3

因第一阶段的检验数都≤0，所以此时的基为最优基，但人工变量y1

还在基中，选择－1作为主元，作换基迭代（此时不必遵循单纯形法所的进出基