数学模型——线性规划问题

已知线性规划问题

（1）写出该线性规划问题的对偶问题；（2）通过引入松弛变量，将该线性规划化为标准形式；（3）利用单纯形法对之求解，包括给出问题的对偶最优解。

解：(1)

该线性规划问题的对偶问题为：

(2)

原设问题：引入松弛变量S1,S2,S3可得：

(3)利用单纯形法对之求解：

表示入基

原设问题的求解：

x1

x2

x3

s1

s2

s3

b

代号

运算规则

Z

-1

1

2

I0

s1

1

1

1

1

8

I1

s2

-1

1

-1

1

2

I2

s3

0

-1

2 *

1

4

I3

x1

x2

x3

s1

s2

s3

b

代号

运算规则

Z

-1

2

0

0

0

-1

4

I0

-2

S1

1

3/2 *

0

1

0

-1/2

6

I1

-1/2

S2

-1

1/2

0

0

1

1/2

4

I2

+1/2

S3

0

-1/2

1

0

0

1/2

2

I3

*1/2

X1

X2

X3

S1

S2

S3

b

代号

运算规则

Z

-7/3

0

0

-4/3

0

-1/3

-12

I0

-2

S1

2/3

1

0

2/3

0

-1/3

4

I1

2/3

S2

-4/3

0

0

1/3

1

2/3

2

I2

-1/2

S3

0

0

1

1/3

0

1/3

4

I3

+1/2

求的最优解为[0,4,4]最大值为12。

同理可得对偶问题的求解：最优解为[4/3,0,1/3]最小值为12

用Mathematica求解：

原设问题的求解：

对偶问题的求解：