文章目录
- 2.1 对偶规划
- 2.1.1 问题的提出
- 2.1.2 对偶规划的定义
- 49年Abr.W.Tucker
- Princeton的Harold W.kuhn
- 布朗大学的David Gale
- LP都有个影像,称LP对偶规划
- 它是LP的一个有趣的性质
- 对称、影子、映射问题
- 原来的LP称原始问题
- 其对称问题为对偶问题
- 原始与对偶问题
- 是
- 同一问题反映出来的两侧面
2.1 对偶规划
- 线性规划问题都对应一个对偶线性规划问题
- 二者从不同的角度描述相同问题
- 根据同样条件和数据建立不同数学模型
- 一个是求某个目标函数最小
- 另一求另一个目标函数最大
- 当存在有限的最优解时
- 两者最优值=.
- 学习对偶规划会
- 加深我们对单纯形法的理解
- 并导出某些更简单的计算方法
2.1.1 问题的提出
- 各设备有效台时数：12、8、16和12.
- 甲和乙种利润20和30,问如何生产获利最大?
- x 1 x_1 x1和 x 2 x_2 x2表示甲乙产量
max S = 20 x 1 + 30 x 2 \max S=20x_1+30x_2 maxS=20x1+30x2
2 x 1 + 2 x 2 ≤ 12 2x_1+2x_2≤12 2x1+2x2≤12
x 1 + 2 x 2 ≤ 8 x_1+2x_2≤8 x1+2x2≤8
4 x 1 ≤ 16 4x_1≤16 4x1≤16
4 x 2 ≤ 12 4x_2≤12 4x2≤12
x 1 ≥ 0 , x 2 ≥ 0 x_1≥0,x_2≥0 x1≥0,x2≥0
- 工厂不产甲、乙,将设备用于接受出租
- 只收租
- 决策者要给设备台时定价
- y 1 、 y 2 、 y 3 、 y 4 y_1、y_2、y_3、y_4 y1、y2、y3、y4
- 用A、B、C、D的台时生产甲种产品每件可得利润20,
- 那将产甲一件的各设备的台时用于出租就不应低于20元,
- 否则,他宁愿自己生产甲
- 所以
2 y 1 + y 2 + 4 y 3 + 0 y 4 ≥ 20 2y_1+y_2+4y_3+0y_4≥20 2y1+y2+4y3+0y4≥20
同理
2 y 1 + 2 y 2 + 0 y 3 + 4 y 4 ≥ 30 2y_1+2y_2+0y_3+4y_4≥30 2y1+2y2+0y3+4y4≥30
-
因为有市场调节作用
- 他定价在满足前面的条件下尽可能低才能得到其他单位的委托加工或租用
-
若把各设备的所有台时都用于外加工或出租,他只能得到其总收入
Z = 12 y 1 + 8 y 2 + 16 y 3 + 12 y 4 Z=12y_1+8y_2+16y_3+12y_4 Z=12y1+8y2+16y3+12y4的最小 -
综上所述,该问题的数学模型为:
min Z = 12 y 1 + 8 y 2 + 16 y 3 + 12 y 4 \min Z=12y_1+8y_2+16y_3+12y_4 minZ=12y1+8y2+16y3+12y4
2 y 1 + y 2 + 4 y 3 + 0 y 4 ≥ 20 2y_1+y_2+4y_3+0y_4≥20 2y1+y2+4y3+0y4≥20
2 y 1 + 2 y 2 + 0 y 3 + 4 y 4 ≥ 30 2y_1+2y_2+0y_3+4y_4≥30 2y1+2y2+0y3+4y4≥30
y j ≥ 0 , j = 1 , 2 , 3 , 4 y_j≥0,j=1,2,3,4 yj≥0,j=1,2,3,4
2.1.2 对偶规划的定义
- 上例看出,原问题和对偶问题的数学模型是完全对应
- 只是
- 将约東的系数矩阵转置
- 不等号反向
- 模型的约束右端项变为另一个模型的目标函数系数
- 一个是求极大,另一个求极小
-
定义2-1
m i n S = C X min S=CX minS=CX
A X ≥ b AX\ge b AX≥b
X ≥ 0 X\ge 0 X≥0 -
叫他原规划，用 P P P表示
-
A m × n A_{m\times n} Am×n
-
X n × 1 X_{n\times 1} Xn×1
-
b m × 1 b_{m\times 1} bm×1
-
C 1 × n C_{1\times n} C1×n
max Z = λ b \max Z=\lambda b maxZ=λb
λ A ≤ C \lambda A\le C λA≤C
λ ≥ 0 \lambda \ge 0 λ≥0
- 叫P的对偶规划，用 D D D表示。
- 他妈的只有 λ \lambda λ是变来的
本文链接：https://my.lmcjl.com/post/7958.html
4 评论