线性规划的对偶问习题.docx

欢迎阅读

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

习题

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

x

x

x32x1 2maxz＝10x

x

3

2x

1 2

maxz＝2x

＋ ＋3x＋

1324st. x

1

3

2

4

＋x＋2x

≤10 st. x

＋x＋x ＋x ≤5

1 2

4x＋x＋x

3

≤20 2x

1 2 3

—x＋3x

4

＝－4

1 2 3 1 2 3

1xxj1x ≥0 （j＝1,2,3） x

1

x

x

j

1

— ＋ ≥

3 4

x2xx0 x

x

2

x

x

0 x

11 3

1

， 无约束

34

3

12342minz＝3x

1

2

3

4

2

＋2x

－3x

＋4x

minz＝－5x

－6x

－7x

st. x－2x＋3x＋4x≤3 st. －x＋5x－3x

≥15

1 2 3 4 1 2 3

341232x＋3x＋4x≥－5 －5x－6x＋10x

3

4

1

2

3

2

≤20

2x－3x

－7x

－4x＝2

x－x－x

＝－5

1 2 3 4 ＝ 1 2 3

x≥0，x≤0，x ，x 无约束 x≤0，x≥0，x

无约束

1 4 2， 3 1 2 3

已知线性规划问题maxz＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶

问题的解的变化：

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

将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；

目标函数改变为maxz＝λCX（λ≠0）；

模型中全部x1用3 x代换。

1

已知线性规划问题minz＝8x

＋6x

＋3x

＋6x

st. x

1

＋2x

2 3 4

＋x≥3

1

3x1

2 4

xxx6＋ ＋ ＋ ≥

x

x

x

6

2 3 4

xx2＋ ＝

x

x

2

3 4

xx2＋ ≥

x

x

2

1 3

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

j

写出其对偶问题；

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

x的最优解。

x

1已知线性规划问题minz＝2x

1

＋＋5x＋6x

对偶变量

342st.2x

3

4

2

＋x＋x

≤8 y

1 3 4 1

2x4232x1＋2x＋＋2x≤12 y

2

x

4

2

3

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

j

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

2

2

3

1考虑线性规划问题 maxz＝2x

1

＋4x

＋3x

2st. 3x1＋4x

2

＋2x

≤60

3x322x1＋ ＋2x

3

x

3

2

≤40

231x＋3x＋2x≤80

2

3

1

jx≥0（j＝1,2,3）

j

写出其对偶问题

用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；

欢迎阅读

欢迎阅读

用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；

比较（2）和（3）计算结果。

12已知线性规划问题 maxz＝10x＋5x

1

2

2st. 3x1＋4x≤9

2

25x1＋2x≤8

2

jx≥0（j＝1,2）

j

用单纯形法求得最终表如下表所示：

x1 x2 x3 x4 b

3

x2 0 1 14

1

x1 1 0

— 1

7

5 25

?=c-Z 0 0 — —

j j j 14 14

试用灵敏度分析的方法分别判断：

c目标函数系数

c

1

或c2

分别在什么范围内变动，上述最优解不变；

约束条件右端项

bb1

b

b

，，当一个保持不变时，另一个在什么范围内变化，上述最

2

优基保持不变；

1 2问题的目标函数变为maxz＝12x＋4x

1 2

约束条件右端项由?9?变为?11?时上述最优解的变化。

? ? ? ?

?8?

?19?

线性规划问题如下：maxz＝—5x＋5x＋13x

321 2 3

3

2

1xst. x

1

x

＋＋3x≤20 ①

2312x1＋4x＋10x≤90 ②

2

3

x≥0（j＝1,2,3）

j

先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化？

约束条件①的右端常数由20变为30；

约束条件②的右端常数由90变为70；

目标函数中x的系数由13变为8；

3

（4）x的系数列向量由（—1，12）T变为（0，5）T；

1

增加一个约束条件③：2x＋3x＋5x≤50；

1 2 3

将原约束条件②改变为：10