线性规划习题附答案.doc

习题

MACROBUTTONMTEditEquationSection2SEQMTEqn\r\hSEQMTSec\r1\hSEQMTChap\r2\h2-1判断下列说法是否对的：

任何线性规划问题存在并具有惟一的对偶问题；?

对偶问题的对偶问题一定是原问题；?

根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；?

若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；?

若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；?

应用对偶单纯形法计算时，若单纯形表中某一基变量xi0，又xi所在行的元素所有大于或等于零，则可以判断其对偶问题具有无界解。?

若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增长5个单位时，相应的目的函数值将增大5k；?

已知yi为线性规划的对偶问题的最优解，若yi0，说明在最优生产计划中第i种资源已经完全耗尽；若yi=0，说明在最优生产计划中的第i种资源一定有剩余。?

2-2将下述线性规划问题化成标准形式。

解：(1)令，增长松弛变量，剩余变量，则该问题的标准形式如下所示：

(2)令，，，增长松弛变量，则该问题的标准形式如下所示：

2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解相应图解法中可行域的哪一顶点。

解：(1)图解法

最优点为B点，最优解为x1=1,x2=3/2，最优值为35/2。

单纯形表计算过程：

?初始单纯形表（相应O点）

z’

x1

x2

x3

x4

RHS

z’

1

-10

-5

0

0

0

x3

0

3

4

1

0

9

9/3

x4

0

[5]

2

0

1

8

8/5

?第一次迭代（相应A点）

z’

x1

x2

x3

x4

RHS

z’

1

0

-1

0

2

16

x3

0

0

[14/5]

1

-3/5

21/5

21/5/14/5

x1

10

1

2/5

0

1/5

8/5

8/5/4/5

?第二次迭代（相应B点，即最优解）

z’

x1

x2

x3

x4

RHS

z’

1

0

0

5/14

25/14

35/2

x2

5

0

1

5/14

-3/14

3/2

x1

10

1

0

-1/7

2/7

1

(2)图解法

最优点为B点，最优解为x1=15/4,x2=3/4，最优值为33/4。

单纯形表计算过程：

?初始单纯形表（相应O点）

z’

x1

x2

x3

x4

RHS

z’

1

-2

-1

0

0

0

x3

0

3

5

1

0

15

15/3

x4

0

[6]

2

0

1

24

24/6

?第一次迭代（相应A点）

z’

x1

x2

x3

x4

RHS

z’

1

0

-1/3

0

1/3

8

x3

0

0

[4]

1

-1/2

3

3/4

x1

2

1

1/3

0

1/6

4

4/1/3

?第二次迭代（相应B点，即最优解）

z’

x1

x2

x3

x4

RHS

z’

1

0

0

1/12

7/24

33/4

x2

1

0

1

1/4

-1/8

3/4

x1

2

1

0

-1/12

5/24

15/4

2-4已知线性规划问题，写出其对偶问题：

（1）

(2)

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

(2)原问题的对偶问题为：

2-5运用对偶理论求解以下各问题：

（1）已知线性规划问题：

其最优解为

（a）求k的值；

（b）写出并求出其对偶问题的最优解。

解：原问题的对偶问题为：

设该对偶问题的三个人工变量为，由于原问题的最优解中的，则根据互补松弛性，所增长的人工变量，则：

，。

此外，原问题的最优值，也为对偶问题的最优值，即：。

结合上述三式可得：

（2）已知线性规划问题：

其对偶问题的最优解为，。

试根据对偶理论求出原问题的最优解。

解：一方面写出原问题的对偶问题如下：

由于该对偶问题的最优解为，代入对偶问题的约束条件中可得

，即对偶问题中的松弛变量。则根据互补松弛性可知，原问题中的决策变量必为0。

将=0代入原问题中的约束条件，可得：

。又由于均不为0，则同样根据互补松弛性可知，。则有：。求解该方程组可得：。

（3）已知线性规划问题:

试根据对偶问题性质证明上述线性规划问题目的函数值无界。

解：一方面写出原问题的对偶问题如下：

由于该对偶问题中前两个约束条件所拟定的可行域为空集，可知该对偶问题无解。则根据对偶性质可知，原问题无解可无界。

此外，必为原问题的解之一，则可证原问题无界。

2-6已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2