利用弱对偶定理证明线性规划问题最优目标函数值不大于30

弱对偶定理:设X和Y分别是原问题P和对偶问题D的可行解,则必有CX≤Yb。

证明:对于原问题和对偶问题模型(1-11)和(2-2),X是原问题的可行解,则有AX≤b,X≥0;Y是对偶问题的可行解,则有YA≥C,Y≥0。在AX≤b两端同时左乘Y,有YAX≤Yb;在YA≥C两端同时右乘X,有YAX≥CX。因此,不等式CX≤YAX≤Yb成立,即CX≤Yb。

推论:P和D有最优解的充要条件是它们同时具有可行解。

证明:

①必要条件。若P和D有最优解,则它们同时有可行解。由于最优解是在可行解中获得的,因此有最优解,就有可行解。

②充分条件。若P和D同时有可行解,那么它们有最优解。根据弱对偶定理(CX≤Yb)可知,对偶问题的任意一个可行解Y对应的目标函数值都是原问题目标函数值的上界,所以一定存在X,使原问题目标函数值最大,即原问题具有最优解。反之,原问题的任意一个可行解X对应的目标函数值都是对偶问题目标函数值的下界,因此也一定存在Y,使对偶问题目标函数值达到最小,即对偶问题具有最优解。

【例2-8】试用对偶性质证明下面线性规划问题的最优目标函数值不大于30。(www.xing528.com)

证明:若原问题最优目标函数值不大于某一数值,说明本题的最优目标函数值存在上界。根据弱对偶定理,原问题的目标函数值一定不超过其对偶问题的目标函数值。因此,证明的关键在于找到对偶问题的一个可行解,该可行解对应目标函数值等于30。证明步骤如下:

①写出原问题的对偶模型。

因原问题存在两个约束条件,因此设对偶问题变量为x1,x2,则对偶模型为:

②找到对偶问题目标函数值为30的可行解。

观察并找到对偶问题目标函数值为30的一个可行解,如X(1)＝(1,2)T和X(2)＝(1．5,1．5)T等。根据弱对偶定理,30是原问题目标函数值的上界,即原问题最优目标函数值不超过30。