1.6 对偶性及对偶单纯形法

该问题的对偶问题：
max g = 3000 y1+55y2+800y3 s.t. 1000 y1+50y2+400y3 14 800 y1+60y2+200y3 6 (4.4) 900 y1+20y2+300y3 3 200 y1+10y2+500y3 2 y1，y2，y3 0
min S=12x1+8x2 +16x3+12x4 s.t. 2x1+ x2 +4x3 2 2x1+2x2 + 4x4 3 x 1， x 2 ， x 3 ， x 4 0 y1 y2
解：该问题的对偶问题：
max g = 2y1 + 3y2 s.t. 2y1 + 2y2 12 y1 + 2y2 8 4y1 16 4y2 12 y 1，y 2 0
令y2 = y2’- y2” 得到 max g = 5 y1 + 4y2 s.t. y1 + 2y2 2 y1 3 -y1+ y2 -5 y1 0 ，y2 无非负约束
此类问题称为非对称型对偶问题。 前面的问题称为对称型对偶问题。
例2-7：写出下列线性规划问题的对 偶问题
min S = 3x1 - 2x2 + x3 s.t. x1+ 2x2 = 1 y1 2x2 -x3 -2 y2 2x1 +x3 3 y3 x1- 2x2 + 3x3 4 y4 x1，划的对偶关系：
（I） Max S=Cx s.t. Ax b （4.5） x0 (II) Min g=yb s.t.
Atyct
（4.6）
y 0
（4.5)(4.6)称作互为对偶问题。其中一个 称为原问题，另一个称为它的对偶问题。
a11 a12 …. a1n
b1
A=
a21 a22 …. a2n
该问题的对偶问题：
max g = 2 y1 - 3y2 s.t. 2y1- 3y2 1 3y1- y2 2 5y1- 7y2 3 y 1，y 2 0
例2-6：写出下列线性规划问题的 对偶问题 min S = 2x1 + 3x2 - 5x3 s.t. x1+ x2 - x3 5 2x1+ x3 = 4 x1 ， x2 ，x3 0
对偶问题的基本定理 定理 (最优准则) 若原问题的某一个可行解与对 偶问题的某一可行解的目标函数 值相等,则它们分别是原问题与 对偶问题的最优解.
对偶问题的基本定理 定理 (对偶定理)课本Th2.5.1 若原问题有最优解,则对偶问 题也有最优解,且最优值相等.
原问题与对偶问题解的对应关系
问 题 与 解 的 状 态 原 有 最 问 无 题 无 可 优 解 界 行 解 对 偶 问 题 有 最 优 解 一 定 不 可 能 不 可 能 无 界 无 可 行 解 不 可 能 可 能 可 能
如果模型(4.1)称为原问题，
则模型(4.2)称为对偶问题。
任何线性规划问题都有对偶问题，
而且都有相应的意义。
例2 .2 营养配餐问题 假定一个成年人每天需要从食物中 获得3000千卡的热量、55克蛋白质和 800毫克的钙。如果市场上只有四种食 品可供选择，它们每千克所含的热量和 营养成分和市场价格见下表。问如何选 择才能在满足营养的前提下使购买食品 的费用最小？
该问题的对偶问题(4.4)经济意义可解释 为：市场上有一厂商生产三种可代替食 品中的热量、蛋白质和钙的营养素，该 厂商希望它的产品既有市场竞争力，又 能带来最大利润，因此需要构造一个模 型来研究定价问题。以上模型的变量为 各营养素单位营养量的价格，目标函数 反映厂商利润最大的目标，约束条件反 映市场的竞争条件，即：用于购买与某 种食品营养价值相同的营养素的价格应 小于该食品的市场价格。
4 y1 + 2y2 50
3 y1 + y2 30
y 1, y 2 0
得到另外一个数学模型：
min s = 120y1 + 50y2
s.t. 4 y1 + 2y2 50 3 y1 + y2 30 (4.2)
y 1, y 2 0
模型(4.1)和模型(4.2) 既有区别又有 联系。联系在于它们都是关于家具 厂的模型并且使用相同的数据，区 别在于模型反映的实质内容是不同 的。模型(4.1)是站在家具厂经营者 立场追求销售收入最大，模型(4.2) 是则站在家具厂对手的立场追求所 付的租金最少。
min S = 3x1 - 2x2 + x3 s.t. x1+2x2 = 1 y1 -2x2 + x3 2 y2 2x1 +x3 3 y3 x1-2x2 +3x3 4 y4 x1，x2 0 ， x3 无非负限制
解: 综合运用对偶原则得到 max g=y1+2y2 +3y3 +4y4 s.t. y1 + 2y3 +y4 3 2y1-2y2 -2y4 -2 y2+y3 +3y4 =1 y2, y3, y4 0 ，y1 无非负约束
餐问题的线性规划模型为： min S=14x1+6x2 +3x3+2x4 s.t.1000x1+800x2+900x3+200x4 3000 50x1+ 60x2 +20x3+ 10x4 55 (4.3) 400x1+200x2 +300x3+500x4800 x1 ，x2 ， x3 ， x4 0
各种食物的营养成分表
序 号
食 品 名 称 热 量 蛋 白 质
（ 克 ）
钙
（ 毫 克 ）
（ 千 卡 ）
价 格 （ 元 ）
1 2 3 4
猪 肉 鸡 蛋 大 米 白 菜
1000 800 900 200
50 60 20 10
400 200 300 500
14 6 3 2
解：设xj为第j种食品每天的购入量，则配
例2-5：写出下列线性规划问题的 对偶问题 min S = x1 + 2x2 + 3x3 s.t. 2x1+3x2 + 5x3 2 3x1+ x2 + 7x3 3 x1 ， x2 ， x3 0
解：用（-1）乘以第二个约束方程 两边
min S=x1+2x2 +3x3 s.t. 2x1+3x2 + 5x3 2 y1 -3x1- x2 - 7x3 -3 y2 x1 ， x2 ， x3 0
假设 y1, y2 分别表示每个木工和 油漆工工时的租金，则所付租金最 小的目标函数可表示为： min s = 120 y1 + 50 y2 目标函数中的系数 120，50 分别表 示可供出租的木工和油漆工工时数。
该企业家所付的租金不能太低， 否则家具厂的管理者觉得无利可图 而不肯出租给他。因此他付的租金 应不低于家具厂利用这些资源所能 得到的利益：
2.对偶问题的基本定理
(对称性定理)课本Th2.5.2
对偶问题的对偶就是原问题.
对偶问题的基本定理 推理一:对偶问题中,任意一个可 行解,都产生了另一个问题的目标 函数的界。 推理二:若原问题和对偶问题都有 可行解,则它们都有最优解。 推理三:若互为对偶问题中任意一 个有可行解,但无最优解,则另一 个就无可行解。
行约束的个数为m 第i个行约束取“≤” 第ι个行约束取“＝”
对偶变量的个数为m 第i个变量yi ≥0 第ι个变量yι无限制
原变量的个数为n 第j个变量xj ≥0 第k个变量xk无限制
行约束的个数为n 第j个行约束取“≥” 第k个行约束取“＝”
例2-3：写出下列线性规划问题的 对偶问题
min S=12x1+8x2 +16x3+12x4 s.t. 2x1+ x2 +4x3 2 2x1+2x2 +4x4 3 x 1， x 2 ， x 3 ， x 4 0
例2-9：用对偶单纯形法解下列线性 规划问题 min S = x1 + 4x2 + 3x4 s.t. x1+2x2 -x3 +x4 3 -2x1 -x2 +4x3 +x4 2 x1 ， x2 ， x3 ， x4 0
解：此题可用人工变量方法求，但也 可用对偶单纯形法。 max S’ = -x1- 4x2 - 3x4 s.t. -x1-2x2 +x3 -x4 +x5 = -3 2x1 +x2 -4x3 -x4 +x6= -2 x1，x2 ,x3，x4 ，x5 ,x6 0
解：将原问题的约束方程写成不等式 约束形式： min S = 2x1 + 3x2 - 5x3 s.t. x1+x2-x3 5 y1 2x1 +x3 4 y2’ -2x1 -x3 -4 y2” x1，x2 ,x3 0
引入变量 y1 , y2’，y2” 写出对偶问题
max g=5 y1+ 4y2’- 4y2” s.t. y1 +2y2’- 2y2” 2 y1 3 -y1 + y2’- y2” -5 y 1 ， y 2 ’， y 2 ” 0
计算检验数全为非正，称为对偶可行； 而常数项全是负数，称为原始不可行。
Cj CB XB 0 0 σ x5 x6
-1 x1 -1 2 -1
-4 x2 -2 1 -4
0 x3 1 -4 0
-3 x4 -1 -1 -3
0 x5 1 0 0
数学模型
max g = 50x1 + 30x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 (4.1) x1,x2 0