线性规划的对偶问题

线性规划的对偶问题第1页，共99页，2023年，2月20日，星期六一对偶问题的提出:例:某厂生产A.B.C三种畅销产品,每台产品需四种资源,具体数据表：

问怎样安排生产,效益最大？设决策变量得出模型:第2页，共99页，2023年，2月20日，星期六现在工厂考虑不进行生产而把全部可利用的资源都让给其它企业单位,但又希望给这些资源订一个合理价格,既使别的单位愿意买,又使工厂能得到生产这些产品时可以得到的最大效益.这就需建立另一个线性规划模型,设代表销售这四种资源的价格，买方希望总售价尽可能低,即：为了使工厂效益不减少,就要求订时,使这个效益额不低于原来生产一台产品A可以得到的效益,因此满足约束:对B,C产品可列出类似约束.原来生产产品A每台需用的资源按现在的单价计算,每台收益为:第3页，共99页，2023年，2月20日，星期六易见,后一个问题的数据完全由另一问题数据确定.对每一个线性规划问题都伴随有另一个线性规划问题,即：

都伴随一个对偶规划(LD)。定义1:对应着每一个(LP),都存在着线性规划问题(LD)其中是m维行向量,称(LP)为原始线性规划，称(LD)为(LP)的对偶线性规划。因此得到的线性规划问题模型如下:第4页，共99页，2023年，2月20日，星期六下面进一步探讨(LP)与(LD)之间的关系：其对偶问题:

(LD)(LP)第5页，共99页，2023年，2月20日，星期六用下表表示二者之间关系,更为清楚:原始约束max对偶问题minw对偶线性规划问题一定要有一对线性规划问题，没有一个“对偶”的线性规划问题，也就无所谓“原始线性规划问题”如果没有原始线性规划问题，也就无所谓对偶线性规划问题了。第6页，共99页，2023年，2月20日，星期六线性规划的对偶关系具有“对合”性质,什么是对合性质呢?可见，（LP）’与（LP）是同一类型的问题，依照定义1，又可写出（LP）’的对偶线性规划。记为（LD）’（LD）'第7页，共99页，2023年，2月20日，星期六（LD）’又可等价地写成：既（LD）’就是前面的（LP）这表明，对于一个给定的（LP）可以根据对偶规则写出（LD）；而对于新问题（LD），又可根据对偶规则写出其对偶。而此对偶又刚好回到原问题本身。即（LP）的对偶是（LD），（LD）的对偶是（LP）。这就是线性规划对偶关系的“对合”性质。

这样我们可以把一个相互对偶的线性规则中任何一个称为原问题，而把另一个称为对偶问题，称它们互为对偶。

下面我们举例说明怎样由一个规则写出其对偶问题。第8页，共99页，2023年，2月20日，星期六例：写出：mins.t.的对偶规划。解：因目标函数最小化，故先把约束条件都写成“”形式：第9页，共99页，2023年，2月20日，星期六

由于这是个（LD）问题。故其对偶是（LP）问题。对偶函数目标系数由给出的（LD）约束右端列向量（-7，14，3)可得，对偶的约束方程右端常数，向量由（LD）的目标函数系数向量（5，-6，7，1）可得，从而写出（LP）问题：max(LP) (s.t.)第10页，共99页，2023年，2月20日，星期六所以把它们称为一对对称的对偶规划。下面来讨论它们的关系。二（LP）、（LD）的对偶定理

定理1

对于（LP）的任意可行解x及（LD）的任意可行解

u有cx≤ub。证：因x、u满足：Ax≤b,x≥0（1）uA≥cu≥0（2）用u左乘（1），x右乘（2）的：cx≤uAx≤ub故cx≤ub。由于（LP）与（LD） 形式上是等价的 第11页，共99页，2023年，2月20日，星期六定理1给出了（LP）（LD）这对互为对偶的线性规问题目标函数的一个界限。若（LP）有可行解x，则（LD）的目标值u

b就有了下界cx；反之，若（LD）有可行解u，则（LP）的目标值cx就有了上界ub。

推论：若（LP）有无界解，则（LD）无可行解。 若（LD）有无界解，则（LP）无可行解。证：只证前面，后面一样，反证法。 若（LP）有无界解，而（LD）有可行解u0， 而根据定理一，对（LP）的任何可行解x，cx≤u0b 这与（LP）目标函数无上界矛盾。注：这个推论的逆不一定成立。即一对对偶问题中有一个无可行解，不能判定另一个有无界解。第12页，共99页，2023年，2月20日，星期六例：（LP）（LD）上面（LP）无可行解，而（LD）并没有无界解，而是无可行解。第13页，共99页，2023年，2月20日，星期六定理2：证明：第14页，共99页，2023年，2月20日，星期六证明：推论2定理3证明：第15页，共99页，2023年，2月20日，星期六这样（LP）就化成了等价的（*）问题。由于假定（LP）有最优解，则（*）亦有最优解。亦即（*）其中)=1ppB³j{,...0对应的最优基为jB-1(c，组成的m维向量记为，，在其中取出基变量对,…cc,…,cc,...00001应的分量。满足个jjsbB第16页，共99页，2023年，2月20日，星期六第17页，共99页，2023年，2月20日，星期六

第18页，共99页，2023年，2月20日，星期六有定理4证明：第19页，共99页，2023年，2月20日，星期六证毕由此可得如下松紧关系：第20页，共99页，2023年，2月20日，星期六第21页，共99页，2023年，2月20日，星期六对偶松紧关系又称为互补松弛条件。下面通过一个例子说明对偶松弛关系：例（LP）引进松弛变量，（LP）化为：第22页，共99页，2023年，2月20日，星期六用单纯形法解此问题的最优单纯形表：

x1

x2

x3

y1

y2

基变量

CB

XB

1

1

1

0

0

X2

1

2/3

2

1

0

-1/3

2/3

X3

1

2/3

0

0

1

2/3

-1/3

F*=4/3

1

0

0

1/3

1/3

得（LP）的最优解（LP）的对偶：（LD）第23页，共99页，2023年，2月20日，星期六第24页，共99页，2023年，2月20日，星期六又第25页，共99页，2023年，2月20日，星期六可见，用单纯形法迭代的到（LP)最优解时，对偶(LD)的最优解可以直接从（LD)的最优单纯形到表上得到。在问题的松弛变量（y1，y2)的检验数就是对偶(LD)的最优解。这个结果对一般情形也成立。下面予以证明。第26页，共99页，2023年，2月20日，星期六用单纯形求解。得到一个判别数全非负的最优基本解。对应松弛变量yi的判别数又yi在目标函数中系数pn+i为第i分量为1的m维单位列向量。(i=1~m)且一对相互对偶的线性规划（LP）（LD）之间解的可能构形有哪些？这可用对偶定理来回答，因为（LP）（LD）都单独分别有三种可能：第27页，共99页，2023年，2月20日，星期六综合以上对偶定理知：（LP）（LD）之间只可能有下面三种情形：（1）两者都有最优解。（2）两者都没有可行解。（3）一个问题有无界解，另一个问题没有可行解。其他情形都不可能出现了，因为，一个问题有最优解，另一个问题有无界解，或一个问题有最优解，另一个问题无可行解，将与定理3矛盾。如果两个问题都有无界解，将与推论1矛盾。（LP)(LD)Ⅰ.有最优解Ⅱ.有无界解Ⅲ.无可行解ⅠⅡⅢ①②……...③第28页，共99页，2023年，2月20日，星期六4.2非对称及混合型对偶规划一（SLP）的对偶规划：在单纯形法中，我们总是先将（LP）问题化为（SLP）求解，因此，有必要研究（SLP）的对偶规划问题。先将（SLP）：改写成（LP）再根据（LP）的对偶定义写出其对偶规划：第29页，共99页，2023年，2月20日，星期六(LD)这就是(SLP)的对偶线性规划，这一线性规划问题还可进一步简化。引进m维行向量u：那么u就不一定有非负约束了。于是将上面（LD)写成：（SLD)u无限制所以，只要u满足解。前面，我们已证明了(LP)与(LD)这对对偶规划具有对合性质。又因为上面(SLD)与(LD)是等价的,而(SLP)与(LP)是等价的。。则u就称为对偶(SLD)的可行第30页，共99页，2023年，2月20日，星期六(LP)（亦即(SLP)的对偶是(LD)亦即(SLD)。而(LP)与(LD)是对称对偶规划，具有对合性。即(LD)也就是(SLD)的对偶是(LP)(亦即(SLP)）。故知:(SLP)与(SLD)这对对偶规划也具有对合性质的。二(SLP)、(SLD)的对偶定理：下面我们考察前面已证明的关于(LP)(LD)的一些定理，考虑是否对(SLP)(SLD)也成立。定理1

对(SLP)的任意可行解x，(SLD)的任意可行解u。有：

证明：号，对应对偶变量x有非负限制，(SLP),(SLD)是非对称的对偶规划，因为：(SLP)约束取等号。对应对偶变量u无符号限制。(SLD)的约束取第31页，共99页，2023年，2月20日，星期六推论1’：若(SLP)有无界解，则(SLD)无可行解；若(SLD)有无界解，则(SLP)无可行解。其逆不成立。证明：设(SLP)有最优解。则必有最优基可行解（基本定理2.2.2）从而可用单纯形法（包括处理退化，循环的方法）得到(SLP)的一个基本最优解x*,设最优基为B*那么我们证明单纯形乘子是对偶（SLD)的最优解。根据单纯形法原理，对应(SLP)的最优基B*的判别数向量最优解为：从而满足是(SLD)的可行解。定理3’：若(SLP),(SLD)中一个有最优解，则另一个也有最优解，并且两者的目标函数值相等。推论2’：若x*，u*分别是(SLP),(SLD)的可行解，且cx*=u*b。则x*,u*分别是(SLP),(SLD)的最优解。（这些结论的证明与(LP),(LD)类似结论证明一样）定理2’：对偶(SLP),(SLD)有最优解两者同时有可行解。第32页，共99页，2023年，2月20日，星期六亦即(LD)的对偶为(LP)(SLP)根据第一节的定理3知，(LP)即(SLP)有最优解。故得证。并且目标值根据上面的推论2即可知：因此我们证明了若(SLP)有最优解，则(SLD)必有最优解。反之，若(SLD)有最优解u*,则是(SLD)的最优解。的最优解。是(LD)：第33页，共99页，2023年，2月20日，星期六我们由上面定理证明过程可见：若B*是(SLP)的最优基，那么单纯乘子就是(SLD)的最优解。因此我们定义：定义2：对于(SLP)的一个基B，若单纯到乘子为对偶(SLD)的可行解，则称B为对偶可行基。若为对偶(SLD)的最优解，则称B为对偶最优基。上面定理3’的证明表明：(SLP)的最优基B*必是对偶最优基。这个结论在后面的对偶单纯形法迭代中将是十分重要。定理4’：(SLP),(SLD)的可行解x*，u*分别是最优解证明：若x*,u*分别是(SLP),(SLD)的可行解，且满足则由推论2’可知：x*,u*分别是(SLP),(SLD）的最优解。(x*可行，Ax*=b)第34页，共99页，2023年，2月20日，星期六我们下面再细看一下这里的松弛条件：因因此上式等价于：（*）式表明：若u*pj=cj。则必有x*j=0，若x*j>0,则必有第35页，共99页，2023年，2月20日，星期六从而得出如下的松紧关系：（1）若(SLP)有最优解x*，使得对指标j满足x*j>0，则称j对（SLD)是松的。对(SLD)的 一切最优解u*就必有u*pj=cj称j对(SLD)是紧的。（2）若(SLD)有最优解u*,使前对指标j满足u*pj>cj.则称j对(SLD)是松的。对(SLP)的一切最优解x*就必有xj*=0，称j对(SLP)是紧的。从上述对偶定理知：(SLP)，(SLD)这一对对偶规划的解之间也有下面三种情形：（1）两者都有最优解。（2）两者都没有可行解。（3）其中一个有无界解，而另一个无可行解。除此之外，不能再有其他的形式了。其理由与4.1一样。第36页，共99页，2023年，2月20日，星期六上面我们已经讨论过了对称及非对称型对偶规划。但实际问题中会出现两种情形共存的问题，即所谓混合型的对称规划问题。

定义:对于一个线形规划问题,若它的约束包括两个部分,一部分的约束是方程式，另一部分约束是不等式(或),其变量也分两类,其一类有非负限制,另一类没有限制，称这种类型的问题为混合型问题。考虑混合型问题：(I)三混合型对偶线形规划第37页，共99页，2023年，2月20日，星期六.矩阵，分别为分别为，维列向量。分别为维行向量。是维列向量。为写出（I)的对偶。先将（I)化为（LP）的形式，然后根据定义写出（LD)，再化简就可明出（I)的对偶。令均是维列向量。，将（I)写成下面的等价线性规划问题：(LP)第38页，共99页，2023年，2月20日，星期六（LD)依照定义1写出(LP)的对偶(LD)如下：在此(LD)中令有符号限制，从而化为下面形式：则u(2)就没（II)称（I)与(II)为混合型的对偶规划。第39页，共99页，2023年，2月20日，星期六根据上面求混合型对偶规划过程，我们总结出混合型对偶的特点如下：（对偶表）：第40页，共99页，2023年，2月20日，星期六例：写出下面线性规划的对偶规划：（1）（2）先将问题转化为统一形式：即最小化问题约束条件为解：“=””或为“有：第41页，共99页，2023年，2月20日，星期六根据上面的对偶表，其对偶问题有了3个对偶变量4个约束方程具体形式如下：(对应第2，3方程“”号故）第42页，共99页，2023年，2月20日，星期六证明：构造一对对偶规划如下：（1）（2）(即)成立的充要条件是：存在向量满足使得成立。（是一个实常数）四*(不讲授）关于Farkas引理（对偶定理解不等式方程的应用）例1：用对偶定理证明相容不等式组,,推出注意：（1）写出的对偶问题，其系数矩阵必须是原问题的系数矩阵的转置。（2）写出对偶的前一步，问题统一化形式是必须的，否则容易出错。第43页，共99页，2023年，2月20日，星期六。要证明：。充分性条件表明问题（2）有可行解且目标值又已假设相容。表明（1）有可行解x.根据对偶定理1可知两个目标值之间有关系：可见。满足约束。且目标值由对偶定理3知：其对偶（2）也有最优解这样就证明了：,有下界。从而（1）不可能有因相容，表明问题（1）存在可行解x。又满足极小化目标函数无界解。从而有可行解的问题（1）必有最优解。设为第44页，共99页，2023年，2月20日，星期六例2用对偶定理证明，下面两个问题不能同时成立：（1）(2)其中A是mn矩阵,c是n维行向量。证明：构造一对对偶线性规划问题：(LD)（LP)第45页，共99页，2023年，2月20日，星期六（LP)(LD)如果（1）式成立有（2）成立。即：且故（1）成立时，（2）不可能也成立。反之，若（2）成立时，同样不可能有（1）成立。这表明上面一对对偶问题（LP)(LD)的最优值为0。因此这与假设矛盾。(注意：我们容易证明定理1’，

2’，3’，

4’，及推论1’，

2’结论对下面形式的一对对偶问题均成立：第46页，共99页，2023年，2月20日，星期六例3：若Ax=b,x0有解，则无解。证明：构造一对对偶规划问题如下：（SLP)(SLD)若Ax=0，有解，且亦有解。则表明(SLP),(SLD)均有可行解，从而均有最优解，(SLP)最优解为0。则对有：矛盾。故无解。反过来，如果后者有解，则前者无解（例4：用对偶定理证明相容不等式组能推出的充分必要条件是：存在向量，满足：且为一实常数）第47页，共99页，2023年，2月20日，星期六证明：构造一对对偶规划问题如下：（LP)(LD)若数值有上界。因而最大化目标函数问题有最优解，设x*为其一个最优解。则根据对偶定理：(LD)也应有最优解，设为则反之，我们要证：若对因为是（LD)的一个可行解，而当（LP)有可行解。根据对偶定理1，对此x，有：表明（LP)有可行解，目标函则时第48页，共99页，2023年，2月20日，星期六若有解。即(SLP)有可行解。而对此(SLP),其任意可行解也是最优解。根据对偶定理3，知(SLD)也有最优解u，反之，若且对满足的任意u，有表明（SLD)有可行解，且目标值有下界。因而此(SLD)有最优解。根据对偶定理3，即可知：(SLP)也有最优解x，满足：（SLP)(SLD)例5：利用对偶定理证明Farkas引理：有解有解，且对满足的任意u必有。其中A是矩阵，b是m维列向量。证明：构造一对对偶规划向量如下：第49页，共99页，2023年，2月20日，星期六例6：写出（LD)用对偶定理证明这个问题有最优解量的线形组合。证明：其对偶：的对偶，如果这个问题存在可行解x向量c能表成A的行向（LP)(SLP)(LD)SLD)第50页，共99页，2023年，2月20日，星期六从而反之，若存在u，使c表成（*）式。则（LP)有可行解。即（SLP)有可行解。又已设(LD)有可行解。即(SLP)有可行解根据对偶定理2。即知：(SLD),(SLP)均有最优解。从而（LD)有最优解。设上面A1……..Am是A的行向量。我们将原来的一对（LP),(LD)等价的化为如上所示的一对(SLP),(SLD)。这样(LD)有最优解等价与(SLD)有最优解。有根据对偶定理3（SLD)有最优解等价于（SLP)有最优解。而（SLP)有最优解等价与(LP)有最优解。因此，若（LD)有最优解等价于(LP)有最优解u。从而第51页，共99页，2023年，2月20日，星期六4.3对偶单纯形法

我们已经知道，用单纯形法求线性规划(SLP)最优解，相当于求一个基B，使得满足基变量取值且判别数向量。这样的基B是最优基。由当当即B是最优基：当B既是可行基，又是对偶可行基时。时，B是可行基。（即B是对偶可行基。，）成立的前提条件下，通过对偶基的逐次迭代直到条件行基，因而是最优基。成立，那么此B既是对偶可行基，又是可我们前面介绍的单纯形方法，是在的前提条件下，通过可行基的逐次迭代，直到条件成立，这时B既是可行基有是对偶可行基，因而B是最优基。现在我们考虑用下面的方法求（SLP)的最优基。在条件一什么是对偶单纯形法第52页，共99页，2023年，2月20日，星期六沿这一途径求得(SLP)的基本最优基的方法，称为对偶单纯形法。二对偶单纯形法的迭代原理用对偶单纯形法求解(SLP)，起始于一个对偶可行基B：，也可以列出一张单纯形表，但表中最后一行检验数行非负，即若满足若础，逐次减少XB中负分量的个数，直到最优可行解，或者判断原问题无可行解为止。则已得到最优解，终止。为基，就得到有负分量，那么以此基本解与单纯形法一样，对偶单纯形法也要找出一个枢轴元来进行旋转变换，因而我们可以直接用单纯形法中的逐次迭代公式即：第53页，共99页，2023年，2月20日，星期六2入基、出基变量选择：单纯形法中先定入基变量即先定k，后定出基变量，即后定l;而对偶变单纯形法中，先定出基变量l，后定入基变量k.3表格形式中数据：单纯形法中，总是非负的，逐次迭代，减少检验数行中负元素的个数；对偶单纯形法，检验数行中的元素总是非负的，逐次迭代，减少基变量取值中负元素的个数。这样，由于单纯形法可以在表上进行，对偶单纯形法也可以在表上进行。当然，两者并不是完全相同的，而有各自的特点。我们分三点讨论：1枢轴选择：单纯形法中要求，对偶单纯形法中要求第54页，共99页，2023年，2月20日，星期六

当我们了解了对偶单纯形法和单纯形法之间这些关系以后，我们就可以具体研究对偶单纯形法。考虑以下几个问题：（2）怎样选取枢轴元

为使变换后的新变量不再取负值，应使则确定第l个基变量确为出基变换。当中有负元时，取：（1）怎样选取出基变量：第55页，共99页，2023年，2月20日，星期六(3)入基变换的选取：因对偶单纯形法是通过对偶可行基的迭代，所以迭代后所有检验数非负。即

根据迭代公式因时

因此选取

则确定为入基变量.第56页，共99页，2023年，2月20日，星期六（4）目标函数迭代公式：由于对偶单纯形法的迭代并不是在（SLP)的可行基上进行的，因此考虑(SLP)的目标函数迭代没意义，而应考虑对偶目标值的迭代公式。若迭代后对偶可行基为B,故是对偶可行解。设对偶目标值为,则设迭代后对偶可行基为，对偶目标值为,则：第57页，共99页，2023年，2月20日，星期六与做内积：

其中是新基变量的取值根据单纯形法的迭代公式：（3.2.13）可见，对偶单纯形法迭代后必将使对偶目标值减少。剩下的问题就是要考虑对偶单纯形法的终止准则。因第58页，共99页，2023年，2月20日，星期六定理4.3.1

设B是(SLP）的一个基（或是一个对偶可行基），且中有负分量，即若第s行中的所有系数则(SLP)无可行解。若对偶单纯形法中基变换，则B是最优基，得到最优解。终止。因此，对偶单纯形法的终止准则是：是可行解矛盾。（反证法）如果定理中条件成立时，(SLP)有可行解x0，代入式中的方程有：

证明：对于B，其中J是非变量下标的集合。第59页，共99页，2023年，2月20日，星期六定义4.3.1：若对偶可行基B对应的所有非基变量判别数，则称对偶可行解是非退化的对偶可行解。否则是退化的。对于非退化的对偶可行解，我们有定理：定理4.3.2

若(SLP)有一个新始对偶可行基B，且是非退化的对偶可行解，用对偶单纯形法迭代时，若每次得到的对偶可行解都是非退化的，则对偶单纯形算法必在有限次迭代后终止于下述两种情形之一：或者判断(SLP)无可行解，或得到(SLP)的一个基本最优解。

证明：设对偶单纯形法迭代进行到某一步时，若某基变换则由定理4.3.1知(SLP)无可行解。终止。否则，可进行对偶单纯形法迭代，按上面介绍的枢轴元选取方式，选取枢轴元素,因假定每次得到的对偶可行解均是非退化的，即非基变量的检验数，于是有对偶目标值：我们给出定义：第60页，共99页，2023年，2月20日，星期六这表明每迭代一次对偶目标函数值必然减少，所以迭代过程中对偶可行基不会重复出现，而对偶可行基的数目是有界的。对偶单纯形法是在对偶可行基上进行的，因此必须在有限步内完成。否则，若迭代过程是无限的，就必然会出现两次迭代有同一个对偶可行基的情形。此时，它们对应的对偶单纯形法目标值相等。这是不可能的。这样就证明了对偶单纯形法经有限次迭代后或者判断(SLP)无可行解，或者得到(SLP)的最伏基本可行解，因而对于对偶可行解非退化的情形，对偶单纯形法必在有限步内终止。第61页，共99页，2023年，2月20日，星期六步骤2如有：（否则（SLP）无可行解，迭代中止。）可定出k:

步骤３以为枢轴元进行枢轴运算，用公式三对偶单纯形法的迭代步骤设已知一个对偶可行基B对应及其对应单纯形表，表中判别数步骤１若，则B为最优基，求出了(SLP)的基本最优解，迭代终止。否则令定出l第62页，共99页，2023年，2月20日，星期六

解：引进剩余变量则转化为

例1用对偶单纯形法求解：第63页，共99页，2023年，2月20日，星期六而基变量xB=(-5,-6)T,可见B是对偶可行基.进行对偶单纯形法迭代的原始表如下：为使基变量对应表中的列向量构成基矩阵，已经将表中的两行元素都乘-1进行了转化。故判别数第一步求l使之满足：确定l=2第二步求k使之满足：确定k=1第64页，共99页，2023年，2月20日，星期六第一步：求l,使，定出l=1定出k=2.第二步：求k，使此表中仍有基变换取负值，返回第一步

第三步以为枢轴元进行旋转变换，入基，出基，设新单纯形表如下第65页，共99页，2023年，2月20日，星期六此表中基变量1，2均为正值，故得到了基本最优解x=(1,2,0,0,0)根据对偶定理知：(SLP)的目标最优值与对偶目标最优值相等。因此原用的最优目标值为

第三步：以为枢轴元进行枢轴运算设新单纯形表如下：第66页，共99页，2023年，2月20日，星期六四初始对偶可行基：以上我们的对偶单纯形法均是在设有了一个对偶可行基的基础上进行的，因此如何求出一个初始对偶可行基，使对偶单纯形法可以进行是一个重要问题。下面介绍两种求初始对偶可行基的方法：1.目标函数系数全为负数的剩余变量方法：b的分量可正可负。引进剩余变量y。将问题转化为：第67页，共99页，2023年，2月20日，星期六其中I是

m阶单位阵。Y为m维列向量。取基阵B=I这时，因此有：

从而就是对偶可行解，这样就得到了一个初始对偶可行基，然后就可以采用对偶单纯形法求解原问题。先将约束AX=b化为等价形式得到一个与(SLP)等价的问题：2.人工约束方法：假定B是（SLP)的一个基，B既不是可行基，也不是对偶可行基。在这种情形下怎样进行对偶单纯形法迭代求解原问题呢？上面，我们举的例就是目标函数系数全为负的剩余变量解法。因此不再举例说明。第68页，共99页，2023年，2月20日，星期六其中M为一个充分大的正数(注意：有改进的方法：只将判别数小于0的非基变量相加），得到新问题如下我们增加一个人工变量和一个约束:第69页，共99页，2023年，2月20日，星期六其中有m+1个等式约束和n+1个变量。称之为问题（I）的扩充问题，易见就是（II)的一组基变量。设（I)对应基B的判别数为由判别数定义有：

再设（II)在基变量下对应判别数为，因在(II)的目标函数中的系数为0，故第70页，共99页，2023年，2月20日，星期六因B既不是(I)的可行基，也不是对偶可行基。所以(I)中的有负值，判别数中也有负值。从而由上面的推导知(II)的基变量所对应的基既不是(II)的可行基，也不是对偶可行基。这是因为：这一组基变量取值为，M,其中有负值，判别数其中也有负值。下面我们证明：(II)中以为出基变量，为入基变量做枢轴运算后，扩充问题(II)的基变量就对应了一个对偶可行基。其中k要求满足：

在(II)中是第m+1个基变量，以为出基变量，即表明l=m+1.而这一行的约束为第71页，共99页，2023年，2月20日，星期六即当是迭代前后的非基变量时，有：判别数为

即非基变量的系数全为1。那么以为枢轴元，进行枢轴运算得：基变量为枢轴运算后，为非基变量，检验数为：第72页，共99页，2023年，2月20日，星期六新基变量对应的判别数均为0。即故有：第73页，共99页，2023年，2月20日，星期六由于扩充问题(II)有对偶可行解，那么由对偶定理，(II)的目标函数有上界，因而扩充问题(II)不可能有无界解，那么利用对偶单纯形法求解扩充问题的只有两种可能结果：或者扩充问题无可行解，或者找到扩充问题的最优解。下面讨论扩充问题与原问题的关系：１.若扩充问题没有可行解，则原问题也没有可行解。可见，（II)经过上面的枢轴运算，所得新基对应的判别数全部非负，即，因而(II)有了初始对偶可行基，从而可以采用对偶单纯形法求解扩充问题(II)了。第74页，共99页，2023年，2月20日，星期六证明：（反证法）若(II)无可行解，而（I)有可行解

则是扩充问题(II)的可行解，矛盾。故成立。２.若扩充问题有最优解是原来的可行解。用代入目标函数后，若与M无关,则是原问题的最优解。第75页，共99页，2023年，2月20日，星期六例２：用人工约束的方法求解下面问题：要求从基开始。解：第76页，共99页，2023年，2月20日，星期六扩充问题如下:第77页，共99页，2023年，2月20日，星期六列出扩充问题单纯形表如下：以人工变量为出基变量，为入基变量，因为作枢轴运算得新表如下：第78页，共99页，2023年，2月20日，星期六此表中所有检验数（非负）因而已得到扩充问题的对偶可行基，基变量但此基非可行基，因基变量，在此表基础上进行对偶单纯形迭代如下：选取l=2，（因只有选取k=5,(因第79页，共99页，2023年，2月20日，星期六进行枢轴运算的新表如下：第二表第80页，共99页，2023年，2月20日，星期六与M无关，故得出了原问题的最优解最优值：在第二表中基变量x4=-1/3<0取l=3,k=3(只有=-1/3<0）做枢轴运算如下：第三表第81页，共99页，2023年，2月20日，星期六例3求线性规划问题：这个问题有一个明显的基：基本解：对应的判别数向量：-（1，-1，0，0）=（-1，1，0，0）第82页，共99页，2023年，2月20日，星期六以新增变量x5为出基变量。因只有故只有k=1即以x1为入基变量，作枢轴运算的新表如下：可见此基B也不是对偶可行基,增加一个变量x5和一个约束得到扩充问题的单纯形表如下：第83页，共99页，2023年，2月20日，星期六此表中所检验的数均非负，故对应的基本解为对偶可行解。其中基变量x4=-3<0故取l=-2(第二个变量）又只有故取k=2即以x4

出基，x2入基作枢轴运算得：第84页，共99页，2023年，2月20日，星期六此表中检验数均非负，基变量取值均非负。故为扩充问题的最优表。这样我们得到扩充问题的最优解即是否为原问题的最优解呢？我们计算其对应的目标植f与M有关不是原问题的最优解易证当M>=5时，对应的x*都是原问题的可行解。而当Mf*+表明原问题目标函数值在可行域上无上界。因此无有限最优可行解。第85页，共99页，2023年，2月20日，星期六X1可行域X2第86页，共99页，2023年，2月20日，星期六事实上，将原问题的约束条件中松弛变量x

3

x

4

去掉，并在平面上画出其可行域，易知：原问题的可行域无界，其中含有半直线；x2=3，x2>=2。在其上目标值f=x1-3趋于正无穷，当x1趋近正无穷时。同样说明目标函数在可行域上无上界，因而无最优解，***********************************************第87页，共99页，2023年，2月20日，星期六4.4对偶问题的经济意义----影子价格考虑以下一对对偶问题：若x*、u*分别为(LP)、(LD)的最优解。则：因此:或这表明如果右端常数项向量b中某一常数项bi增加一个单位，则函数的最优值f*的变化量为ui*定义影子价格为约束条件常数项增加一个单位而产生的目标函数最优值的变化。因此，对偶变量ui表明了约束条件的影子价格。影子价格是针对某一具体的约束条件而言的。第88页，共99页，2023年，2月20日，星期六而问题中所有其他数值不变，因此影子价格可以被理解为目标函数最优值对资源的一阶偏导。在求解线性规划时，影子价格可以很容易的从最优单纯形表格中得出：在最优单纯形表中，就是对应约束条件的松弛变量的检验数值，下面我们举例说明影子价格分析与应用。例1，某工厂经理对该厂生产的两种产品用线性规划来确定最优的产量方案，根据产品的单位产值和生产的三种资源供应限量，建立模型如下：第89页，共99页，2023年，2月20日，星期六第90页，共99页，2023年，2月20日，星期六解：利用单纯形法解此问题，得其初始表和最终表如下：第91页，共99页，2023年，2月20日，星期六这说明最优生产方案是；第一种生产35件，第二种生产10件，总产值：215。又从前面的分析知；