《数据模型与决策》复习题及参考答案

一、某系统由8 个子系统组成部分,已知8 个子系统间的可达矩阵R如下。现根据可达矩阵R,求出8 个子系统的结构模型。

1?1?0??0??0?0??0?0???020101000030010010040001000051010111160010010071000001180??0?0??0? 0??0?0??1??123R?45678解:根据可达矩阵R得如下数据表1(3与6相同,去掉6选3为代表元素)

寻找各级的最高级要素集 ——第一级的可达集与前因集 要素SJ 1 2 3 4 5 7 8 数据表1 R(SJ)(对应R行中的1) A(SJ)(对应R列中的1) R∩A 1,5,7 2 3,5 2,4 5 5,7 5,7,8 1 2,4 3 4 3,5,7 1,7 8 1 2 3 4 5 7 8 由数据表1知,第一级要素为:2,5 。在数据表1中,去掉要素2和5后,得数据表2。

数据表2 要素SJ 1 3 4 R(SJ)(对应R行中的1) A(SJ)(对应R列中的1) R∩A 1,7 3 4 1 3 4 1 3 4 第 26 页共40页

7 8 7 7,8

1,7 8 7 8 由数据表2知,第二级要素为:3,4,7 。在数据表2中,去掉要素3、4和7后,得数据表3。

数据表3 要素SJ 1 8 R(SJ)(对应R行中的1) A(SJ)(对应R列中的1) R∩A 1 8

由数据表3知,第三级要素为:1,8。

对缩减可达矩阵R'按每行元素为1的项目多少,由少到多依次排序得到排序后的缩减可达矩阵R\如下: 级间排序的可达矩阵 25473182?1?0??1??0?0??0?0?501011114001000070001011300001001000001080??0?0?? 0?0??0?1??1 8 1 8 由排序后的缩减可达矩阵R\建立R表达的结构模型(并将要素6加入)如下图1所示:

2 5 4 7 3 6 1 8

二、 光明木材加工厂生产圆桌和衣柜两种产品。已知生产一张圆桌需要木工4

第 27 页共40页

图1 R表达的结构模型

小时和油漆工2小时,生产一张衣柜需要木工3小时和油漆工1小时 。一张圆桌的利润是10元,一张衣柜的利润是6元。而工厂每月只能提供木工10小时,油漆工4小时。请制定出一个月生产方案,在现有条件下,使其获得的利润最大?试建立其数学模型,并用图解法给出最优解。

解:设该加工厂每月生产圆桌和衣柜的数量分别为:x1,x2,则所获的总利润为Z:依题意得下表: 木工(小时) 油漆工(小时) 利润(元) 圆桌 衣柜 总限量 其数学型为: 4 3 10 2 1 4 10 6 MaxZ?10x1?6x24x1?3x2?10??2x1?x2?4??x?0,x?0且为整数2?15 4 3 2 1 0 s.t

用图解法求解如下: 1、建立直角坐标系。

2、画出可行域S。

3、在可行域S上找出最优解:

X*=(1,2),最优值Z*=10×1+6×2=22(元)。 即该加工厂每月生产圆桌和衣柜的数量分别 为1张和2张,则所获的总利润为22元。

T

(1,2) 0 1 2 3 4 5

(作图得2分) 三、 用单纯形法求解下列线性规划问题的最优解:

MaxZ?3x1?x2?4x1?2x2?8??3x1?x2?10 ?x?0,x?02?1s.t解:将LP问题化为标准型得:

第 28 页共40页

MaxZ?3x1?x2?4x1?2x2??8x3???x4?10 ?3x1?x2?x1?0,x2?0,x3?0,x4?0??s.t作单纯形表如下:

Cj CB 0 0 3 0 XB X3 X4 λ X1 X4 λ Bb 8 10 0 2 4 -6 -1 3 1 0 0 X1 (4) 3 3 ↑ 1 0 0 X2 2 1 1 1/2 -1/2 -1/2 X3 1 0 0 1/4 -3/4 -3/4 X4 0 1 0 0 1 0 8/4=2→ 10/3=3.33 由上表可知:因为所有的λj≤0(j=1,2,3,4),得LP问题的最优解为: *T*

X0=(2,0,0,4),最优值Z0=6。

所以,原LP问题的最优解为:X*=(2,0)T,最优值Z*=6。

四、 已知线性规划问题为:

MinZ?6y1?8y2s.t?y1?2y2?4? 2y?2y?6?12?y?0,y?02?1(1)、写出它的对偶问题。

(2)、用对偶单纯形法求解该线性规划问题的最优解。 解:根据LP得: X1 x2 Ⅵ Ⅵ 0 0 y1≥0 1 2 ≤6 y2≥0 2 2 ≤8 Ⅵ Ⅵ min 4 6 max 第 29 页共40页

由上表可得:LP的对偶问题为:

MaxZ?4x1?6x2?x1?2x2?6??2x1?2x2?8 ?x?0,x?02?1

s.t

将原LP问题化为标准形得:

Miax?Z??6y1?8y2??y1?2y2?y??43???y??6分 ??2y1?2y24?y1?0,y2?0,y3?0,y4?0??s.tCj CB 0 0 0 -6 -8 -6 XB y3 y4 λ θ y3 y1 λ y2 y1 λ B-1b -6 -8 0 0 y1 y2 y3 1 0 0 1 0 -3/4 -1 0 -2 y4 0 1 0 -1/2 -1/2 0 6 1/2 -1 -2 → → -4 -1 -2 -2 -8 4 (-1) 1 -1/2 2↑ 1 0 0 -6 (-2) 0 -1 3 18 1 3 20 -6 3↑ 0 1 0 0 1 0 由上表可知:因为所有的λj≤0(j=1,2,3,4),得LP问题的最优解为: Y0*=(2,1,0,0)T,最优值Z0*=-20。

所以,原LP问题的最优解为:Y=(2,1),最优值Z=20。

*

T

*

第 30 页共40页

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4