2023年12月19日发(作者：车辆识别品牌)

精品文档

一、已知线性规划问题（25分）

maxz?x1?5x2?3x3?4x4?2x1?3x2?x3?2x4?800?5x?4x?3x?4x?1200

?1234st.??3x1?4x2?5x3?3x4?1000??x1,x2,x3,x4?0（1）求线性规划问题的最优解；5

（2）求对偶问题的最优解；5

（3）当?b3??150时最优基是否发生变化？为什么？5

（4）求C2 的灵敏度范围；5

（5）如果X3的系数由[1，3，5]变为[1，3，2]最优解是否改变，若改变求新的最优解；5

二、考虑线性规划问题，（15）

maxz?5x1?12x2?4x3?x1?2x2?x3?5

?st.?2x1?4x2?3x3?2?x,x,x?0?123用单纯型法求解，得其终表如下：

X4为松弛变量，X5为人工变量。

（1）上述模型的对偶模型为？

（2）对偶模型的最优解为？

（3）当两种资源分别单独增加一单位时，目标函数值分别增加？

（4）最优基的逆矩阵B-1=?

（5）如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？

精品文档

精品文档

T三、线性规划问题maxf(x)?Cx,Ax?b,x?0,

设X0 为该问题的最优解，若目标函数中用C* 带替C后，问题的最优解变为X* ，求证：

(C*?C)T(X*?X0)?0(10分)

四、求V1到各点的最短路。（10分）

五、证明任何有n个节点n条边的简单图中必存在圈。（10分）

六、求下图所示的网络中，每条弧旁边的数字是(cij,fij)，（15分）

V2

(2,2)

(3,1)

(4,3)

V1

（1）确定所有的截集；

（2）求最小截集的容量；

（3）证明指出的流是最大流

七、试解二次规划（15分）

(3,3)

(1,0)

Vt

VS

(5,2)

(2,2)

V3

minf(x)?2x12?4x1x2?4x22?6x1?3x2?x1?x2?3?st.?4x1?x2?9?x,x?0?12

精品文档

精品文档

问题答案：

1. 解：

（1）首先把问题转化成标准型：

maxz?x1?5x2?3x3?4x4?2x1?3x2?x3?2x4?x5?800?5x?4x?3x?4x?x?1200

?12346st.??3x1?4x2?5x3?3x4?x7?1000??x1,x2,x3,x4,x5,x6,x7?0用单纯型法求解最优解：

初始单纯型表

CB

0

0

0

XB

X5

X6

X7

Cj-Zj

最终单纯型表

0

4

5

X5

X4

X2

Cj-Zj

100

200

100

b

800

1200

1000

1

1/4

2

-3/4

-13/4

1

X1

2

5

3

5

0

0

1

0

5

X2

3

4

4

3

-13/4

-2

11/4

-11/4

3

X3

1

3

5

4

0

1

0

0

4

X4

2

4

3

0

1

0

0

0

0

X5

1

0

0

0

1/4

1

-3/4

-1/4

0

X6

0

1

0

0

-1

-1

1

-1

0

X7

0

0

1

最优解为（0，100，0，200）；

（2）由互补松弛性可得，其对偶问题最优解为：（0，1/4，1）；

（3）当?b3??150时

?11/4?1??0??150???????B?1?b??01?1???0?150???

?03/41???150???150????????100?150??250??????1所以B(b??b)??200?150???350?

?100?150???50?????因此可得出最优基发生变化，因为b3??50?0，需要用对偶单纯型法继续求解；

（4）若保证最优基不变，需要满足以下条件：

精品文档

精品文档

??7?3/4(5??c2)?0?11?11/4(5??c)?0?2 从而得出-1

???4?3/4(5??c2)?0??4?(5??c2)?0（5）X3的系数发生变化：

?11/4?1??1???1/4???????p3\'?B?1p3??01?1???3???1?

?03/41??2???1/4???????同时计算P3的检验数为：c3?CBB?1P3\'?1/4?0，因此可以得出尚未得到最优解，用单纯型法继续求解：

初始单纯型表

CB XB b

0

4

5

X5

X4

X2

Cj-Zj

最终单纯型表

0

3

5

X5

X3

X2

Cj-Zj

2. 解：

（1）上述模型的对偶模型为：

150

200

150

100

200

100

1

X1

1/4

2

-3/4

-13/4

3/4

2

-1/4

-15/4

5

X2

0

0

1

0

0

0

1

0

3

X3

-1/4

1

-1/4

1/4

0

1

0

0

4

X4

0

1

0

0

1/4

1

1/4

-1/4

0

X5

1

0

0

0

1

0

0

0

0

X6

1/4

1

-3/4

-1/4

1/2

1

-1/2

-1/2

0

X7

-1

-1

1

-1

-5/4

-1

3/4

-3/4

最优解为（0，150，200，0）；

minw?5y1?2y2?y1?2y2?5?2y?y?12

?12st.??y1?3y2?4??y1?0,y2无约束*（2）由单纯型表可以看出，y1??(?29/5)?29/5，由于

ys1?x1?0;ys2?x2?0,而x1?0;x2?0,

所以，ys1?0;ys2?0,

则对偶问题的第一、二个约束是紧的，可解出y2??2/5

*T*将y1,y2代入第三个约束，满足约束条件，则y?(y1,y2)?(29/5,?2/5),w?141/5

精品文档

精品文档

（3）5和2

?2/5?1/5?（4）B???

1/52/5???1（5）如果原问题增加一个变量，则对偶问题增加一个约束，因此其可行域要么减小，要不不变，但绝不会增大。

3. 证明：

(C*?C)T(X*?X0)?C*TX*?C*TX0?CTX*?CTX0?(CX?CX)?(CX?CX)因为X0 和X*都满足Ax?b,x?0, 所以X0 和X*都是两个问题的可行解。

T0T**T**T0

又因为X0

是maxf(x)?Cx,Ax?b,x?0,最优解，而且原问题求最大，

因此可得出：f(x)?f(x)?(CX?CX)?0

同理可得出：

0*T0T*Tf(x*)?f(x0)?(C*TX*?C*TX0)?0

所以可以得出：

(CTX0?CTX*)?(C*TX*?C*TX0)?0因此得证：(C?C)(X?X)?0

4. 解：用Dijkstra算法求解可得

V1到V2的最短路为V1-V2，最短距离11，

V1到V3的最短路为V1-V3，最短距离9，

V1到V4的最短路为V1-V4，最短距离10，

V1到V5的最短路为V1-V4-V5，最短距离21，

V1到V6的最短路为V1-V3-V6，最短距离20，

V1到V7的最短路为V1-V4-V5-V7，最短距离25，

具体步骤省略。

5. 证明：设有V1，V2，V3，…Vn个点，构成简单图G(V,E)，假设图中不存在圈，

若简单图为连通图，由树的定义无圈的连通图为树，并且简单图G无环五多重边，因此可知G为树，由树的定义可得：q(G)=P(G)-1=n-1，与已知图有n条边矛盾，因此可得假设精品文档

*T*0

精品文档

不成立，图中一定存在圈；

若简单图为非连通图，则至少有两个连通分图，由于每个连通分图无圈，则可得每个连通分图都为一颗树，设有k个连通子图，k≥2；T1,T2,T3，…Tk，

由树定义可得：q(G1)=P(G1)-1；

q(G2)=P(G2)-1；

q(G3)=P(G3)-1；

…

q(Gk)=P(Gk)-1；

等式左右两边相加得：q(G1)+ q(G2)+ q(G3)+…+ q(Gk)=P(G1)+P(G2)+P(G3)+…+P(Gk)-k；

q(G)=n-k，k≥2；与已知条件图有n条边不符，因此，假设不成立

所以问题得证

6. 解：

（1）首先确定所有的截集与对应的容量：

①若v1?{vs}，则其截集为

其容量为(v1,v1)??(vs,v1),(vs,v2)?

c(v1,v1)?cs1?cs2?4?2?6

，则其截集为

②若v1??vs,v1?

其容量为(v1,v1)??(v1,v2),(vs,v2),(v1,v3)?

c(v1,v1)?cs2?c12?c13?2?3?2?7

，则其截集为

③若v1??vs,v1,v2?

其容量为(v1,v1)??(v2,vt),(v1,v3)?

c(v1,v1)?c2t?c13?2?3?5

，则其截集为

④若v1??vs,v1,v2,v3?

其容量为(v1,v1)??(v2,vt),(v3,vt)?

c(v1,v1)?c2t?c13?5?3?8

，则其截集为

⑤若v1??vs,v2?

精品文档

(v1,v1)??(vs,v1),(v2,vt)?

精品文档

其容量为c(v1,v1)?c2t?cs1?4?3?7

，则其截集为

⑥若v1??vs,v2,v3?

其容量为(v1,v1)??(v2,vt),(v3,vt),(vs,v1)?

c(v1,v1)?c2t?cs1?c3t?4?5?3?12

，则其截集为

⑦若v1??vs,v3?

其容量为(v1,v1)??(v3,v2),(v3,vt),(vs,v1),(vs,v2)?

c(v1,v1)?c32?c3t?cs1?cs2?4?2?5?1?12

，则其截集为

⑧若v1??vs,v1,v3?

其容量为(v1,v1)??(vs,v2),(v1,v2),(v3,v2),(v3,vt)?

c(v1,v1)?c32?c3t?c12?cs2?3?2?5?1?11

（2）由（1）所求，最小截集的容量为

c(v1,v1)?minc(v1,v1)?5**v?v,v,v,v??s121??v3,vt?。 其中1**??

（3）根据最大流量最小截量定理，最大流量为

v(f*)?c(v1*,v1*)?5

7. 解：首先将二次规划转化为线性规划求解，因此将上述二次规划改写为

1minf(x)?(4x12?8x1x2?8x22)?6x1?3x22??x1?x2?3?0?st.??4x1?x2?9?0?x,x?0?12

可知目标函数为严格凸函数，此外

c1??6,c2??3,c11?4,c22?2c12?c21??4,b1?3,a11??1,a12??1b2?9,a21??4,a22??1

由于C1，C2小于零，故引入的人工变量Z1，Z2前面取负号，得到的线性问题如下：

精品文档

精品文档

ming(z)?z1?z2??y3?4y4?y1?4x1?4x2?z1??6??y?y?y?4x?4x?z??3342122??st.??x1?x2?x3?3?0??4x?x?x?9?0124?

??x1,x2,x3,x4,y1,y2,y3,y4,z1,z2?0解线性规划问题得：

39*21*3,x2?,x3?0,x4*?,20202021z1*?0,z2*?0,y3*?,y4*?0,

5441f(x*)??40x1*?

精品文档

更多推荐

问题,对偶,变量,截集,求解,增加