第二章对偶理论

2.1 写出线性规划问题的对偶问题，并进一步写出其对偶问题的对偶问题

(a) min z=2x1+2x2+4x3 (b) max z=5x1+6x2+3x3

s.t. x1+3x2+4x3≥2 s.t. x1+2x2+2x3=5

2x1+x2+3x3≤3 -x1+5x2-3x3≥3

x1+4x2+3x3=5 4x1+7x2+3x3≤8

x1, x2≥0, x3无约束 x1无约束,x2≥0, x3≤0

解：(a)对偶问题的原问题为

max w=2y1+3y2+5y3

s.t. y1+2y2+y3≤2

3y1+y2+4y3≤2

4y1+3y2+3y3=4

y1≥0, y2≤0, y3无约束

(b)原问题的对偶问题为

min w=5y1+3y2+8y3

s.t. y1-y2+4y3=5

2y1+5y2+7y3≥6

2y1-3y2+3y3≤3

y1无约束, y2≤0, y3≥0

2.3 已知线性规划问题：

max z=x1+x2

s.t. -x1+ x2+ x3 ≤2

-2x1+x2- x3 ≤1

x1, x2, x3≥0

试应用对偶理论证明上述线性规划问题最优解为无界。

解：原问题的对偶问题为

min w=2y1+ y2

s.t. -y1- 2y2 ≥1

2y1+ 5y2 ≥1

y1- y2 ≥0

y1, y2≥0

由于约束条件3可得

y1-y2 ≥0 → y1≥y2 → -y1≤-y2 且y2≥0

所以

-y1-2y2 ≤-3y2≤0 （1）

由于约束条件1可得

-y1- 2y2 ≥1 （2）

（1）（2）不等式组无解

第二章 线性规划的对偶理论

随着线性规划应用的逐步深入，人们发现线性规划有一个有趣的特性，就是每一个线性规划问题都存在另一个与之配对、两者有密切联系的线性规划问题.称其中一个为原问题，则另一个被称为对偶问题，这个特性称为线性规划的对偶性，这不仅仅是数学上具有的理论问题，由对偶问题引伸出来的对偶解有着重要的经济意义，也是经济学中重要的概念与工具之一. 对偶理论充分显示出线性规划理论逻辑上的严谨性与结构上的对称性，它是线性规划理论的重要成果.

§1 对偶问题的提出

一、对偶问题的实例

在第一章的例1.1中，讨论了某工厂资源的合理利用问题，建立了LP问题模型：

2125001500maxxxz

s.t. 2123xx≤65

212xx≤40

23x≤75 （2.1）

21,xx≥0

已知最优解为：70000,25,5**2*1zxx.

现从另一个角度考虑这个问题.假定该厂的决策者考虑自己不生产甲、乙两种产品，而把原拟用于生产这两种产品的资源A,B,C全部出售给外单位，则应如何确定这三种资源的价格.

显然，该厂的决策者要考虑两个原则：第一，每种资源所收回的费用应不低于自己生产时可获得的利润；第二，定价不能太高，要对方容易接受.

设321,,yyy分别表示三种资源出售的价格，则由第一个原则，应有如下约束条件：

2123yy≥1500

32132yyy≥2500

321,,yyy≥0

而把原拟用于生产甲、乙产品的三种资源全部售出，总收入为：

37 第3章 对偶理论

§3.1 线性规划的对偶理论

3.1.1 对偶问题的表述

对称形式的对偶：

（L） cxmin (D) wbmax

s.t. bAx s.t. cwA

0x 0w

其中c为n维行向量，A为nm矩阵，b为m维列向量，x表示n维列向量，w表示m维行向量。

称(D)为线性规划(L)的对偶规划问题。

定理1 (L)与(D)互为对偶规划问题。――（对合性）

例 设原问题 对偶问题

0, 12 5 s.t.min

21212121xxxxxxxx

0, 12 1 s.t.5 max

21212121wwwwwwww

非对称形式的对偶：

（LP） cxmin (DP) wbmax

s.t. bAx s.t. cwA

0x

例 设原问题 对偶问题

0,, 523 4 s.t.345min

321321321321xxxxxxxxxxxx

3 42 53 s.t.54 max

21212121wwwwwwww

一般线性规划问题：

可化为上述二者之一讨论其对偶问题，也可直接写出对偶问题，详细的对应法则见教材（陈宝林）124页。 38 直接写出对偶的弊端之一是对偶最优解不易确定，而对称形式和非对称形式对偶的最优解都可由原问题的单纯形乘子确定出来。

第二章 线性规划的对偶理论

2.1 写出下列线性规划问题的对偶问题

max z=2x1+2x2－4x3

x1 + 3x2 + 3x3 ≤30

4x1 + 2x2 + 4x3≤80

x1、x2，x3≥0

解：其对偶问题为

min w=30y1+ 80y2

y1+ 4y2 ≥2

3y1 + 2y2 ≥2

3y1 + 4y2 ≥－4

y1、y2≥0

2.2 写出下列线性规划问题的对偶问题

min z=2x1+8x2－4x3

x1 + 3x2－3x3 ≥30

－x1 + 5x2 + 4x3 = 80

4x1 + 2x2－4x3≤50

x1≤0、x2≥0，x3无限制

解：其对偶问题为

max w=30y1+80 y2+50 y3

y1－ y2 + 4 y3 ≥2

3y1+5y2 + 2y3 ≤8

－3y1 + 4y2－4y3 =－4

y1≥0，y2无限制，y3≤0

2.3 已知线性规划问题

max z=x1+2x2+3x3+4x4

x1 + 2x2 + 2x3 +3x4≤20

2x1 + x2 + 3x3 +2x4≤20

x1、x2，x3，x4≥0

其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。

解：其对偶问题为 min w=20y1+ 20y2

y1 + 2y2 ≥1 （1）

2y1 + y2 ≥2 （2）

2y1 +3y2 ≥3 （3）

3y1 +2y2 ≥4 （4）

y1、y2≥0

将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以

2x3* +3x4* = 20

3x3* +2x4* = 20

解得x3* = x4* = 4。故原问题的最优解为