线性规划的对偶问题

第二章 线性规划的对偶问题

习题

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

(1) max z ＝10x1＋ x2＋2x3 (2) max z ＝2x1＋ x2＋3x3＋ x4 st. x1＋ x2＋2 x3≤10 st. x1＋ x2＋ x3 ＋ x4 ≤5

4x1＋ x2＋ x3≤20 2x1－ x2＋3x3 ＝－4 xj ≥0 （j＝1,2,3） x1 － x3＋ x4≥1

x1，x3≥0，x2，x4无约束

(3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3 ≥15

x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3 ≤20

2x1－3x2－7x3 －4x4＝2＝ x1－ x2－ x3＝－5 x1≥0，x4≤0，x2，，x3 无约束 x1≤0， x2≥0，x3 无约束

2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化：

（1）问题的第k个约束条件乘上常数λ（λ≠0）；

（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上； （3）目标函数改变为max z＝λCX（λ≠0）； （4）模型中全部x1用3x'1代换。

2.3 已知线性规划问题 min z＝8x1＋6x2＋3x3＋6x4

st. x1＋2x2 ＋ x4≥3

3x1＋ x2＋ x3＋ x4≥6

x3 ＋ x4＝2

x1 ＋ x3 ≥2

xj≥0（j＝1,2,3,4）

(1) 写出其对偶问题；

(2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。

2.4 已知线性规划问题 min z＝2x1＋x2＋5x3＋6x4 对偶变量

st. 2x1 ＋x3＋ x4≤8 y1 2x1＋2x2＋x3＋2x4≤12 y2

xj≥0（j＝1,2,3,4）

其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。

４７