2024年5月4日发(作者：龚意蕴)

习 题 三

3.1 试建立下述LP问题的对偶关系表，并写出其对偶问题：

（1）max z=4x

1

+3x

2

+6x

3

s.t.



3x

1

x

2

x

3

60



2x2x3x40



123



2x2xx6

23



1





x

1

0,x

2

0,x

3

0



3x

1

x

2

x

3

2



xxx1



123



x2xx1

23



1





x

1

0,x

2

0,x

3

0



2x

1

x

2

4x

3

2



xx2x1



123





3x

1

x

2

x

3

3





x

1

0,x

2

0,x

3

0



x

1

2x

2

4x

3

10





2x

1

5x

2

3x

3

15



x0,x0,x0

23



1

（2）min w=60x

1

+10x

2

+20x

3

s.t.

（3）min w=5x

1

-3x

2

s.t.

（4）max z=4x

1

+3x

2

+6x

3

s.t.

3.2 试写出下述LP问题的对偶问题：

（1）1.1（1）题 （2）1.5题 （3）2.4（5）题 （4）2.4（7）题

（5）min w=2x

1

+2x

2

+4x

3

s.t.



2x

1

3x

2

5x

3

2



3xx7x3



123





x

1

4x

2

6x

3

5





x

2

0,x

3

0



3x

1

4x

2

4x

3

7x

4

21



2x7x3x8x18



1234





x

1

2x

2

5x

3

3x

4

4





x

1

0,x

2

0,x

4

0

(6) min w=2x

1

+3x

2

+6x

3

+x

4

s.t.

3.3 试证明LP问题（P

2

）是（D

2

）的对偶，（P

2

）是（D

2

）的对偶。

3.4 试写出下述LP问题的对偶问题：

（1）min w=C

T

X

s.t.



AXb





Xa(0)

1 / 4

(2) min z=



cx

i1j1

mn

ijij

s.t.



n





x

ij

a

i

,i1,2,...m



j1



m





x

ij

b

j

,j1,2,...n



i1



x

ij

0







(3) max z=



cx

j

j1

n

j

s.t.



n





a

ij

x

j

b

i

,i1,2,...,r



j1



n





a

ij

x

j

b

i

,ir1,r2,...,m



j1



x0,j1,2,...,s(n)



j





3.5 已知LP问题：

min z= 5x

1

+6x

2

+3x

3

s.t.



5x

1

5x

2

3x

3

50



xxx20



123



7x

1

6x

2

9x

3

30





x

1

x

2

x

3

7



2x4x15x10

23



1



6x

1

5x

2

45





x

2

10x

3

20



x0,x0,x0

23



1

试通过求解其对偶问题来确定该LP问题的最优解。

3.6 已知LP问题：

max z= x

1

+2x

2



x

1

x

2

2



s.t.



x

1

x

2

1



x0,x0

2



1

（1）试证明它与其对偶问题均无可行解。

（2）试构造一个LP问题，使其本身及其对偶问题均无可行解。

3.7 已知（Ⅰ）（Ⅱ）两个LP问题：

（Ⅰ）max z

1

=



cx

j

j1

n

j

2 / 4

s.t.



n





a

ij

x

j

b

i

,i1,2,...,m



j1



x0,j1,2,...,n



j

（Ⅱ）max z

2

=



cx

j

j1

n

j



n





a

ij

x

j

b

i

k

i

,i1,2,...,m



j1



x0,j1,2,...,n



j

其中

a

ij

，

b

i

，

k

i

均为已知常数。

设

z

1

，

z

2

分别为（Ⅰ），（Ⅱ）的最优值，



y

i



（i=1,2,…,m）为（Ⅰ）的对偶问题的最优解，求证：

zz



k

i

y

i



2



1

i1

m

3.8 不用单纯形法，利用对偶性质和其它简便方法求解下述LP问题：

(1) max w=4x

1

+3x

2

+6x

3

s.t.



3x

1

x

2

3x

3

30





2x

1

2x

2

3x

3

40



x0,x0,x0

23



1

(2) max z=x

1

-x

2

+x

3

x

3

4



x

1





x

1

x

2

2x

3

3



x0,x0,x0

23



1

3.9 已知LP问题：max z= 6x

1

+8x

2



5x

1

2x

2

20



s.t.



x

1

2x

2

10



x0,x0

2



1

(1)写出它的对偶问题。

(2)用图解发求解原始、对偶问题。识别两个问题的所有极点解。

(3)用单纯形法求解原始问题。在每个单纯形表中，识别此问题的基本可行解及对偶问题的互补基本解。指

出它们相应于图解法中哪个极点。

(4)按表3-8的格式，列出该问题的全部互补基本解。

(5)用对偶单纯形法求解对偶问题，并将结果与（3）中结果进行对比。

(6)该问题是否满足互补松弛性？为什么？

3.10用对偶单纯形法求解下述LP问题:

(1)min z= x

1

+x

2

3 / 4

s.t.



x

1

2x

2

4



x5



1





3x

1

x

2

6





x

1

0,x

2

0



x

1

x

2

x

3

6



xx

3

4



1



x

2

x

3

3







x

1

0,x

2

0,x

3

0

(2) min z= 3x

1

+2x

2

+x

3

s.t.

(3) 2.4(4)题

3.11 某厂拟生产甲、乙、丙三种产品，都需要在A，B两种设备上加工，有关数据如下表所示：

产品 单耗（台时/件） 设备有效台时

设备

甲 乙 丙

A

B

产值（千元/件）

1 2 1

2 1 2

3 2 1

400

500

（1） 如何充分发挥设备能力，使产品总产值最大？

（2） 若为了提高产量，以每台时350元租金租用外厂A设备，问是否合算？

3.12 用对偶单纯形法求解下述LP问题:

（1）max z= 3x

1

-2x

2

-x

3

s.t.



x

1

x

2

x

3

4



x

2

2x

3

8





x

2

x

3

2







x

1

,x

2

,x

3

0



x

1

x

2

x

3

6



2xx

3

6



1



2x

2

x

3

0







x

1

,x

2

,x

3

0

(2) max z= 2x

1

-x

2

+2x

3

s.t.

(3) max z= 5x

1

-8x

2

-x

3

+4x

4

-11x

5



2x

1

9x

2

7x

3

2x

4

11x

5

5



x6x6x2x9x3



12345

s.t.





x

1

7x

2

8x

3

3x

4

12x

5

4





x

1

,x

2

,x

3

,x

4

,x

5

0

3.13 用交替单纯形法求解3.12题。

4 / 4

2024年5月4日发(作者：龚意蕴)

习 题 三

3.1 试建立下述LP问题的对偶关系表，并写出其对偶问题：

（1）max z=4x

1

+3x

2

+6x

3

s.t.



3x

1

x

2

x

3

60



2x2x3x40



123



2x2xx6

23



1





x

1

0,x

2

0,x

3

0



3x

1

x

2

x

3

2



xxx1



123



x2xx1

23



1





x

1

0,x

2

0,x

3

0



2x

1

x

2

4x

3

2



xx2x1



123





3x

1

x

2

x

3

3





x

1

0,x

2

0,x

3

0



x

1

2x

2

4x

3

10





2x

1

5x

2

3x

3

15



x0,x0,x0

23



1

（2）min w=60x

1

+10x

2

+20x

3

s.t.

（3）min w=5x

1

-3x

2

s.t.

（4）max z=4x

1

+3x

2

+6x

3

s.t.

3.2 试写出下述LP问题的对偶问题：

（1）1.1（1）题 （2）1.5题 （3）2.4（5）题 （4）2.4（7）题

（5）min w=2x

1

+2x

2

+4x

3

s.t.



2x

1

3x

2

5x

3

2



3xx7x3



123





x

1

4x

2

6x

3

5





x

2

0,x

3

0



3x

1

4x

2

4x

3

7x

4

21



2x7x3x8x18



1234





x

1

2x

2

5x

3

3x

4

4





x

1

0,x

2

0,x

4

0

(6) min w=2x

1

+3x

2

+6x

3

+x

4

s.t.

3.3 试证明LP问题（P

2

）是（D

2

）的对偶，（P

2

）是（D

2

）的对偶。

3.4 试写出下述LP问题的对偶问题：

（1）min w=C

T

X

s.t.



AXb





Xa(0)

1 / 4

(2) min z=



cx

i1j1

mn

ijij

s.t.



n





x

ij

a

i

,i1,2,...m



j1



m





x

ij

b

j

,j1,2,...n



i1



x

ij

0







(3) max z=



cx

j

j1

n

j

s.t.



n





a

ij

x

j

b

i

,i1,2,...,r



j1



n





a

ij

x

j

b

i

,ir1,r2,...,m



j1



x0,j1,2,...,s(n)



j





3.5 已知LP问题：

min z= 5x

1

+6x

2

+3x

3

s.t.



5x

1

5x

2

3x

3

50



xxx20



123



7x

1

6x

2

9x

3

30





x

1

x

2

x

3

7



2x4x15x10

23



1



6x

1

5x

2

45





x

2

10x

3

20



x0,x0,x0

23



1

试通过求解其对偶问题来确定该LP问题的最优解。

3.6 已知LP问题：

max z= x

1

+2x

2



x

1

x

2

2



s.t.



x

1

x

2

1



x0,x0

2



1

（1）试证明它与其对偶问题均无可行解。

（2）试构造一个LP问题，使其本身及其对偶问题均无可行解。

3.7 已知（Ⅰ）（Ⅱ）两个LP问题：

（Ⅰ）max z

1

=



cx

j

j1

n

j

2 / 4

s.t.



n





a

ij

x

j

b

i

,i1,2,...,m



j1



x0,j1,2,...,n



j

（Ⅱ）max z

2

=



cx

j

j1

n

j



n





a

ij

x

j

b

i

k

i

,i1,2,...,m



j1



x0,j1,2,...,n



j

其中

a

ij

，

b

i

，

k

i

均为已知常数。

设

z

1

，

z

2

分别为（Ⅰ），（Ⅱ）的最优值，



y

i



（i=1,2,…,m）为（Ⅰ）的对偶问题的最优解，求证：

zz



k

i

y

i



2



1

i1

m

3.8 不用单纯形法，利用对偶性质和其它简便方法求解下述LP问题：

(1) max w=4x

1

+3x

2

+6x

3

s.t.



3x

1

x

2

3x

3

30





2x

1

2x

2

3x

3

40



x0,x0,x0

23



1

(2) max z=x

1

-x

2

+x

3

x

3

4



x

1





x

1

x

2

2x

3

3



x0,x0,x0

23



1

3.9 已知LP问题：max z= 6x

1

+8x

2



5x

1

2x

2

20



s.t.



x

1

2x

2

10



x0,x0

2



1

(1)写出它的对偶问题。

(2)用图解发求解原始、对偶问题。识别两个问题的所有极点解。

(3)用单纯形法求解原始问题。在每个单纯形表中，识别此问题的基本可行解及对偶问题的互补基本解。指

出它们相应于图解法中哪个极点。

(4)按表3-8的格式，列出该问题的全部互补基本解。

(5)用对偶单纯形法求解对偶问题，并将结果与（3）中结果进行对比。

(6)该问题是否满足互补松弛性？为什么？

3.10用对偶单纯形法求解下述LP问题:

(1)min z= x

1

+x

2

3 / 4

s.t.



x

1

2x

2

4



x5



1





3x

1

x

2

6





x

1

0,x

2

0



x

1

x

2

x

3

6



xx

3

4



1



x

2

x

3

3







x

1

0,x

2

0,x

3

0

(2) min z= 3x

1

+2x

2

+x

3

s.t.

(3) 2.4(4)题

3.11 某厂拟生产甲、乙、丙三种产品，都需要在A，B两种设备上加工，有关数据如下表所示：

产品 单耗（台时/件） 设备有效台时

设备

甲 乙 丙

A

B

产值（千元/件）

1 2 1

2 1 2

3 2 1

400

500

（1） 如何充分发挥设备能力，使产品总产值最大？

（2） 若为了提高产量，以每台时350元租金租用外厂A设备，问是否合算？

3.12 用对偶单纯形法求解下述LP问题:

（1）max z= 3x

1

-2x

2

-x

3

s.t.



x

1

x

2

x

3

4



x

2

2x

3

8





x

2

x

3

2







x

1

,x

2

,x

3

0



x

1

x

2

x

3

6



2xx

3

6



1



2x

2

x

3

0







x

1

,x

2

,x

3

0

(2) max z= 2x

1

-x

2

+2x

3

s.t.

(3) max z= 5x

1

-8x

2

-x

3

+4x

4

-11x

5



2x

1

9x

2

7x

3

2x

4

11x

5

5



x6x6x2x9x3



12345

s.t.





x

1

7x

2

8x

3

3x

4

12x

5

4





x

1

,x

2

,x

3

,x

4

,x

5

0

3.13 用交替单纯形法求解3.12题。

4 / 4