聪明文档网

    聪明文档网

    最新最全的文档下载
    当前位置： 首页> 《管理运筹学》习题2解答

    《管理运筹学》习题2解答

    时间：    下载该word文档
    《管理运筹学》习题2及参考答案
    （复习参考题）一.分别用图解法和单纯形法求解下列线性规划问题：
    minz2x14x24x12x26
    s.t.x1x21

    x12,x2自由

    x2
    x1≤2
    4321
    A
    -2x1+4x2=0
    B
    x1
    x1-x2=1
    解：（一）用图解法求解，过程如下：1.各种约束条件如图1所示，其中线段AB为可行域。A点和B点坐标分别为(4/3,1/3、（2,1）2.画出目标函数的一条等值线：-2x1+4x2=0,如图所示。它向下平移目标函数值z越来越小。
    3.当目标函数平移到A(4/3,1/3点时，z→minz。所以本题有唯一最优解X＝(4/3,1/3，最优目标函数值z*=-2×4/3+4×1/3=-4/3。
    (二用单纯形法求解（用大M法和两阶段法都可），[大M法求解]
    1.将原模型化为标准型（1）令y1=2-x1≥0，
    x2=y2-y3(其中y2,y3≥0………①则x1＝2-y1………②
    将①、②代入原约束条件，并化简整理得到：（2）在③式左边加入松弛变量y4,化为：
    *
    T
    01234-1
    4x1+2x2≥6
    图1
    2y1-y2+y3+y4=1
    ④式不用标准化,已经是标准形式。
    （3）将①、②代入目标函数得：minz=-4+2y1+4y2-4y3+0·y4令w＝-z，则目标函数化为：maxw=4-2y1-4y2+4y3+0·y4所以，标准型即：
    2yyy1………③
    123
    s.t.y1y2y31………④

    yj0j1,2,3
    maxw42y14y24y30y42yyyy1………⑤
    1234

    s.t.y1y2y31

    yj0j1,2,3

    2.在⑤式左边加入人工变量y5，并在目标函数中加入罚因子M(M为很大的正数，则标准型化为规范型，如下所示：maxw42y4y4y0yMy
    12345
    2yyyy1
    1234

    s.t.y1y2y3y51

    yj0j1,2,,5

    3.列单纯形表求解，过程如下：
    cj→
    CB0-M-2
    XBy4y5y1
    B-1b111/21/22/31/3-8/3
    -2y1[2]1-2+M100100
    -4y2-11-4+M-1/2[3/2]010
    4y31-14-M1/2-3/20-10
    0y41001/2-1/21-1/2M1/3-1/3-2/3
    -My50100101/32/3-M+11/3
    θ
    i
    1/21—1/3——
    σj=cj-zj-My5σj=cj-zj-2
    y1
    -4y2σj=cj-zj
    -5+3/2M5-3/2M
    4.结论：因为所有非基变量检验数σj≤0(j=3,4,5，所以当前基可行解(2/3,1/3,0,0,0T就是最优解。相应的x*1＝2-y*1=2-2/3=4/3；x*2=y*2-y*3=1/3-0=1/3；minz=-maxw=-(-8/3+4=-4/3。
    [用两阶段法求解]
    （紧接大M法2步以后）
    3.第一阶段：先列单纯形表求解如下模型：

    maxw1y5
    2yyyy1
    1234

    s.t.y1y2y3y51

    yj0j1,2,,5
    cj→
    CB0
    XBy4
    Bb111/21/22/31/3
    -1
    0y1[2]1110010
    0y2-111-1/2[3/2]3/201
    0y31-1-11/2-3/2-3/20-1
    0y41001/2-1/2-1/21/3-1/3
    -1y50100101/32/3
    θ
    i
    1/21—1/3
    -1y5σj=cj-zj0y1-1y5σj=cj-zj00
    y1y2
    σj=cj-zj00000-1
    因为所有非基变量检验数σj≤0(j=3,4,5，所以停止迭代，此时w=0，可进入第二阶段继续求解。
    第二阶段，去掉人工变量y5，恢复非人工变量目标系数，在以上最后一步基础上继续求解：
    cj→
    CB-2
    XBy1
    Bb2/31/3
    -8/3
    -1
    -2y1100
    -4y2010
    4y30-10
    0y41/3-1/3-2/3
    θ
    i
    ——
    -4y2σj=cj-zj
    4.结论同大M法第4步。

    二.以下各模型目标函数都是求最大值，根据各自的最优表下结论（要判断解的类型）：（1）
    cj→
    CB
    -3
    XBx2
    B-1b9/54/5
    -2x101010
    B-1b3/23/31/2
    x11000
    -3x210015x239/809/16-43/80-43M/80+31/8
    （3）
    cj→CB2
    XBx1
    Bb3/47/27/4
    -1
    -1x33/5-2/5012x30100
    0x4-3/101/5-1/20x43/161/16
    0x51/10-2/51/20x5-1/801/16
    -Mx63/10-1/5
    -Mx7-1/102/5
    -2x1σj=cj-zj（2）
    cj→
    CB100
    XBx1x3
    -M+1/2-M+1/20x600-1-M
    -Mx70010
    -Mx7σj=cj-zj-7/16-3/80-30/16--3M/807M/16
    +1/8-Mx7-3/81/41/8
    2x11000
    -1x20010
    2x30100
    0x4-1/4-1/2-1/45/4
    -Mx51/41/21/4
    0x63/8-1/4-1/8
    0x81/81/4-3/8
    -Mx9-1/8-1/43/8
    2x3-1x2σj=cj-zj
    -M-3/4-3/8-M+3/8-9/8-M+9/8
    解：
    （1）结论：因为所有非基变量检验数σj≤0(j=3,4,5,6,7且σ3＝0、人工变量x6＝x7＝0，所以此问题有无穷多最优解。以x3为进基变量继续迭代，可求出另外一个最优解。
    cj→
    CB
    XB
    Bb9/54/532
    -1
    -2x101001
    -3x21005/32/3
    -1x3[3/5]-2/5010
    0x4-3/101/5-1/2-1/20
    0x5
    -Mx6
    -Mx7-1/102/5-1/61/3
    θi3—
    -3x2-2x1σj=cj-zj-1-2
    x3
    x1σj=cj-zj
    1/103/10-2/5-1/51/6-1/3
    1/20
    1/2-M+1/2-M+1/2
    000-1/2-1/2-M+1/2-M+1/2
    所以，本题最优解其中一个为：X1*=(4/5,9/5,0,0,0,0,0T；
    另一个最优解为：X2*=(2,3,0,0,0,0,0T；maxz=-3×9/5-2×4/5=-1×3-2×2=-7
    （2）结论：因为所有非基变量检验数σj≤0(j=2,4,5,6但人工变量x7=1/2≠0，所以此问题无可行解。
    （3）结论：非基变量检验数σ4＝5/4>0，而ai4≤0(i=1,2,3，故此问题无有限最优解（或为无界解）。
    （复习参考题）三、线性规划问题的建模与求解
    某家具厂要求做60套家具，每套需用长2.5m和1.2m的圆钢各1根。已知每根原料长5m，试问应如何下料，使得做成这60套钢制家具所用原材料最省？要求：（1）请列出套裁方案，并建立该问题的线性规划模型。（2）请将所建模型标准化，并列单纯形表求解，得出
    /

    最小原料根数和相应的各方案下料根数。解：（1）考虑以下几种套裁方案方案下料根数长度
    2.5m1.2m合计料头
    Ⅰ2050
    Ⅱ124.90.1
    Ⅲ044.80.2

    设按照方案Ⅰ、方案Ⅱ、方案Ⅲ下料的原材料分别为x1、x2和x3根，据题意可建立以下线性规划模型：
    minz0.1x20.2x32x1x260
    s.t.2x24x360x,x,x0123

    （2）将上述模型增加剩余变量x4、x5，人工变量x6、x7，化为规范形，如下：（剩余变量设置正确得1分，人工变量设置正确得1分）
    maxz0.1x20.2x3Mx6Mx72x1x2x4x660

    s.t.2x24x3x5x760x0(j1,2,7j

    下面列单纯形表求解：
    Cj→CB-M
    XBx6
    Bb606060
    -1
    0-0.1-0.200-M-M
    x1
    20[2]
    x2
    1211/2M1/2[1/2]0010
    x3
    0[4]010010-120
    x4
    -10-10-M-1/200-1/200
    x5
    0-1-M0-1/4-1/200-1/4-1/201/4-1/2-1/20
    x6
    10-M1001/20-M1/20-M
    x7
    01-M0
    θ-1530
    -Mx7σj=cj-zj-M
    x6
    -0.2x3σj=cj-zj0-0.20
    x1x3x1
    2M3M-0.14M-0.2-M
    1502M3015-31530-3
    100100
    1/4--M+1/2001/4-1/41/2
    6030
    σj=cj-zj-0.1x2σj=cj-zj
    -M+1/20
    -M+1/20

    结论：因为第二步迭代时，σj≤0，人工变量已经出基，但是非基变量x2的检验数σ2＝0，所以本题有多个最优解。以x2为进基变量再进行迭代，就可以得到另一个最优解。最有解
    *
    如下：X1*30,0,15,0,0,0,0,X215,30,0,0,0,0,0
    T
    T
    结论：按照方案Ⅰ、方案Ⅱ、方案Ⅲ下料的原材料分别为30、0和15根，或者分别为15、
    **30和0根，这时所用原料最小根数为x1*x2x33001545

    （复习参考题）四、某公司从三个产地A1，A2，A3将物品运往三个销地B1，B2，B3，产量平衡表和单位运价表如表1所示。问如何调运，使得总运输费用最小？
    表1产销平衡表和单位运价表
    B1B2B3销地Bj
    产地Ai
    A1357A2615A3243
    201020需求量（件）
    产量（件）
    10
    3020
    要求：（1）请建立该问题的线性规划模型，然后再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。
    解：
    （1）设第i个产地（i=1,2,3）到第j个销地（j=1,2,3）的该种商品的数量为xij吨，则可以建立以下模型：
    3
    3
    ij
    minz
    c
    i1
    j1
    xij
    x11x12x1310
    x21x22x2330xxx20313233
    s.t.x11x21x3120xxx10
    2232
    12
    x13x23x3320xij0(i1,2,3;j1,2,3
    （2）因为总产量60（＝10+30+20）大于总需求量50（＝20+10+20），所以本问题不是标准
    运输问题。增加一个虚拟销地，它的单位运价c14＝c24＝c34，需求量为60-50=10。（3）第一步：用最小元素法确定初始方案（方案不唯一，增补的零元素不能位于同行或同列）。
    3(062(2020(0
    51
    (10
    75320(0
    (20
    000
    (10
    0
    410(0
    10
    3020
    (0
    10(0
    0
    (20(0
    (0
    20
    10
    10
    200




    方法二：伏格尔法（最接近最优解）
    3(062(20
    51
    (10
    753
    (20
    000
    (10
    0
    4
    10
    3020
    3(0
    14(201(021(0
    20102010
    132040000

    方法三：西北角法（初始解离最优解较远）
    3(101062
    51
    (10
    0


    20
    10
    10
    200

    753
    (10
    4
    10
    10
    030102000
    (0
    (20(100(100
    20102010
    10010000

    10
    10
    101010

    10

    第二步：求非基变量检验数，验证初始方案（最小元素法求得的初始方案）是否为最优方案。法一：用位势法求检验数。
    求解见下表所示：
    Ui销地销地一销地二销地三销地四
    产地
    x1134527x1400产地一
    36x221x235x2400产地二
    x31244-1310-1产地三
    Vj3150
    因为min(σ33＝σ33=-1<0，所以初始方案并非最优方案，需进一步调整，x33为进基变量。
    法二：用闭回路法求检验数
    036220
    5
    10
    1
    7
    20
    5
    10
    43

    00
    0

    0

    σ12=5-0+0-1=4；σ13=7-0+0-5=2；σ21=6-3+0-0=3；σ32=4-2+3-0+0-1=4（注：图中画出了非基变量x33的闭回路）；σ33=3-2+3-0+0-5=-1；σ34=0-2+3-0=1
    因为min(σ33＝σ33=-1<0，所以初始方案并非最优方案，需进一步调整，x33为进基变量。
    第三步：求θ值，调整方案。过程如下：

    020
    10
    10
    20


    0


    以X33作为进基变量。调整量θ＝min(10,20,20=10，按照上图所示进行调整，选择x14
    作为出基变量。
    方案调整后为方案二，如下：
    1010
    101010

    10
    用位势法可求出方案二非基变量检验数：
    Ui销地销地一销地二销地三销地四
    产地
    x1135537100产地一
    26x221x235x2401产地二
    x31254x33320-1产地三
    Vj304-1
    因为所有非基变量检验数都大于零，所以方案二就是唯一最优方案。
    第四步：
    决策结论：产地一向销地一调拨物资10吨，产地二分别向销地二、销地三调拨物资各10吨，产地二过剩生产的物资为10吨；产地三分别向销地一、销地三调拨物资10吨、10吨。最小总运费＝10×3+10×1+10×5+10×2+10×3=140（百元）。五、（选做题）
    某一最大化线性规划问题在单纯形法计算时，某一次迭代结果如表1所示。其中a,b,c,
    表1
    Cj→
    CB
    XBx3x4
    x6
    σj＝Cj-zj
    B-1bf23
    x12-1ab
    x2c-5-3d
    x31000
    x40100
    x5e-1-4-3
    x60010

    d,e,f是未知数，原问题中要求各变量均非负。问a,b,c,d,e,f应满足什么条件，有下面各解成立？（假定(1-(7问无人工变量）
    (1表中解是非可行基解；(2表中解是唯一最优解；(3表中解为无穷多最优解；(4表中解是退化的基可行解；(5表中解为无界解；(6表中解为可行解但非最优解，只有x1进基且x6出基。写出初等变换后目标函数值总变化。(7一个约束条件有矛盾。(8假定只有一个人工变量，表中解的情况此时能判定为无可行解。
    解：
    （1）基解非负时就是基可行解。故当f<0时表中是非可行基解。
    （2）唯一最优解要求非基变量检验数都小于零。所以f≥0，b<0，d<0。

    （3）无穷多最优解要求非基变量检验数都不大于零且其中至少一个为零，所以
    f≥0，b≤0，d≤0，但b和d中至少有一个为0。（4）f=0或者f>0，b>0且f/2＝3/a。
    （5）无界解对应至少一个非基变量检验数为正数（可以找到进基变量）但其对应的系数列向量中的元素都不大于0（无法求θ，无法确定出基变量），所以f≥0，d>0，c≤0，b≤0；（6）非基变量中选最大正检验数为进基变量，θ值最小的为出基变量。所以f≥0，b>0且b≥d，f/2>3/a，a>0。目标函数值的总变化b×3/a
    （7）当f<0，c≥0,e≥0时，约束方程1明显矛盾。
    （8）当x6为人工变量，且b≤0，d≤0，a≤0；或者x4为人工变量，且必有b<0，d<0（因为b=-M+某数值<0;d=-5M+某数值<0）；（x3不可能为人工变量，否则x1可以为进基变量继续迭代，应为σ1＝2M＋某数值>0）。
    六、（选做题）已知线性规划问题的初始单纯形表（如表1）和用单纯形法迭代过程中得到的表（不一定是最优表，如表2）如下，其中x4和x5是松弛变量，试求括号中a~l的值。表1
    Cj→
    CB
    XBx4x5
    σj＝Cj-zj表2
    Cj→
    CB
    XBx1
    x5
    σj＝Cj-zj
    Bb(f4
    -1

    Bb61
    -1
    x2(c3-1
    x3(d(e2
    x4100
    x5010
    x1(b-1(a
    x1(g(h0
    x22(i-7
    x3-11(j
    x41/21/2(k
    x501(l

    T
    解：可以判断目标系数向量C=(a,-1,2,0,0。记表1中的可行基为B，则
    g211/20
    C-CBB-1A=(a,-1,2,0,0-(a,00,7,j,k,l11/21hi
    cdg1/206f1/20b-1
    B-1b=,BPPP=123
    1/21141/2113eh
    2i
    1
    1
    l是基变量的检验数，而(g,hT是基变量x1的列向量，所以l＝0，g＝1，h＝0。再求解以上方程组，得：
    abcdefghijkl324-2231055-3/20

    七.（选做题）已知某目标函数求最大值的线性规划问题用单纯形法迭代时得到中间某两步的单纯形表如表1所示，试着将表中空白处的数字填上。

    表1
    Cj→CB501
    XBx2x5x6
    B-1b8/314/329/3
    3x12/3-4/35/3
    5x2100
    4x3054
    0x41/3-2/3-2/3
    0x501008/415/41
    0x60010-10/414/41
    σj＝Cj-zj543
    x2x3x1
    -1/304-5/3…………


    15/41-6/41-2/41
    -12/4115/41
    σj＝Cj-zj
    解：从下表中可以看出基变量的顺序分别为x2、x3、x1，所以x1、x2、x3分别对应
    010
    的系数列向量矩阵为，它们对应的检验数σj＝0(j=1,2,3。
    001
    100不妨把上表就看成问题的初始表，则就约束方程组的增广矩阵而言，下表是以B左乘
    上表得到的，这里B是下表的基，由于下表3个基变量依次是为x2、x3、x1，故B是由上表的第2列、第3列和第1列组成，因此：238101041
    1由B0543B1054
    41531504012

    －1
    注：以上求B如果用逆矩阵定义公式较为简单，公式如下：
    1
    -1
    A
    A111A12
    AA13
    A21A22A23
    A31
    A32
    A33
    〔求B－1法二〕如下：
    上表中P2、P5、P6构成单位矩阵，则在下表中找到x2、x5、x6所在列系数列向量，就构成B，如下：
    8/4110/411

    1
    B05/414/41
    012/4115/41
    注：回顾线性代数中逆矩阵的初等变换求法，过程如下：
    －1

    P2P3P1P2
    2
    13(上表中10
    4
    B0530
    504031
    (下表中00E
    010
    010010
    P5P6
    E00
    10经过多次初等行变换01
    85414141
    10415
    41
    4141
    12


    B－1

    于是在下表中Bb位置，41B1b10
    41
    0

    8512
    108/350/41
    414/362/411529/389/41
    -1
    下表中非基变量的检验数可以通过σ=(0,0,0-CBB-1(P4,P5,P6求得。
    81045/4115
    0,0,05,4,3165424/4141
    1521211/41

    因为在下表中所有非基变量检验数σj<0(j=4,5,6，所以它对应的基可行解就是最优解，停止迭代。所以，下表对应的的目标函数值为：
    50/41
    zCBbj5,4,362/4176541
    89/41

    免费下载 Word文档免费下载： 《管理运筹学》习题2解答

    TOP热门搜索

    相关推荐：

    挑战答题

    • ￥29.8

      ￥45 每天只需1.0元
      1个月 推荐

    • ￥9.9

      ￥15
      1天

    • ￥59.8

      ￥90
      3个月

    选择支付方式

    • 微信付款
    会员须知 联系在线客服 登录账号
    郑重提醒：支付后，系统自动为您完成注册

    请使用微信扫码支付(元)

    订单号：
    支付后，系统自动为您完成注册
    遇到问题请联系 在线客服

    常用手机号：
    用于找回密码
    图片验证码：
    看不清？点击更换
    短信验证码：
    新密码：
     
    绑定后可用手机号登录
    请不要关闭本页面，支付完成后请点击【支付完成】按钮
    遇到问题请联系 在线客服

    侵权投诉  © 2013-2019 http://www.tcm999.cn   站点地图 |  手机版

    本站文档均来自互联网及网友上传分享，本站只负责收集和整理，有任何问题可通过上访投诉通道进行反馈