运筹学作业-王程130404026

运筹学作业王程信管1302130404026目录运筹学作业..................................................................................1第一章线性规划及单纯形法...................................................3第二章线性规划的对偶理论与灵敏度分析.........................24第三章运输问题...................................................................53第四章目标规划.....................................................................63第五章整数规划...................................................................73第六章非线性规划.................................................................85第七章动态规划...................................................................94第八章图与网络分析.............................................................97第九章网络计划.....................................................................99第一章线性规划及单纯形法1.1分别用图解法和单纯形法求下列线性规划问题，⑴指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解；⑵当具有限最优解时，指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。121212121min23466s.t.324,0zxxxxxxxx（）1212121,22max3222s.t.34120zxxxxxxxx（）121212123max105349s.t.528,0zxxxxxxxx（）121212124max5622s.t.232,0zxxxxxxxx（）解：⑴图解法：2233x1x1x21.(6/51/5)OO当212133xxz经过点6155（，）时，z最小，且有无穷多个最优解。⑵图解法：x142123x2O该问题无可行解。⑶图解法：x13C(5/8,0)4B(1,3/2)x2A(0,9/4)O当21125xxz经过点312（，）时，z取得唯一最优解。单纯形法：在上述问题的约束条件中分别加入松弛变量34,xx，化为标准型：12341231241234max10+500349s.t.528,,,0zxxxxxxxxxxxxxx由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所示：CB00010510XBx3x4x3x1x2x1b9821/58/53/21x13501010x24214/52/5100x310105/14-1/7-5/14x401-3/51/5-3/142/7-25/14θi38/53/241050010500010-2Cjcj-zjcj-zjcj-zj**33(,1,0,0),10512022(0,0,9,8)821(,0,,0)553(1,,0,0)2TTTTXZXOXCXB（0）（1）（2）单纯形表的计算结果表明：单纯形表迭代的第一步得，表示图中原点（0,0）单纯形表迭代的第二步得，表示图中点单纯形表迭代的第三步得，表示图中点⑷图解法：x112/3(2,2).Ox2当215166xxz经过点2,2（）时，z取得唯一最优解。1.2将下述线性规划问题化成标准形式。12341234123412341234min3425422214s.t.232,,0,zxxxxxxxxxxxxxxxxxxxx（1）无约束',44'4'',4'0,4''0,zzxxxxx解：上述问题中令其中则该问题的标准形式为12344123441234451234461234456max'3425'5''42'''22'2''14s.t.23'''2,,,','',,0zxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1231231231232min2234s.t.260,0,zxxxxxxxxxxxx（）无约束1133333',',''','0,''0,zzxxxxxxx解：上述问题中令其中则该问题的标准形式为123312331233412334max'22'''''''4s.t.2'''6',,','',0zxxxxxxxxxxxxxxxxxx1.3对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。1213241251max354212s.t.321801,,5jzxxxxxxxxxxj（）1234123412342min52322347s.t.22230(1,,4)jzxxxxxxxxxxxxxj（）解：（1）该线性规划问题的全部基解见下表中的①～⑧，打√者为基可行解，注*者为最优解，z*=36。x124400046x263696000x32004440-2x4060-60121212x500-6061860√√××√√√×可行？*z362742453001218序号①②③④⑤⑥⑦⑧（2）该线性规划问题的标准形式为：123412341234max'52322347s.t.22230(1,4)jzxxxxxxxxxxxxxj，其全部基解见下表中的①～⑥，打√者为基可行解，注*者为最优解，z*=5。x1000-1/32/5-4x20-1/2-1/20011/2x3102011/50x412011/600　Z＇-5-5-5-2-43/531√×√×√×可行？①②③④⑤⑥*序号*1.4题1.1（3）中，若目标函数变为12maxzcxdx，讨论,cd的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。解：由目标函数12maxzcxdx可得：211czzxxkxddd，其中ckd。⑴当304k时，可行域的顶点A使目标函数达到最优；⑵当5324k时，可行域的顶点B使目标函数达到最优；⑶当52k时，可行域的顶点C使目标函数达到最优；⑷当0,0cd或0,0cd时，最优解为O点。1.6分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。123123121231min23428s.t.326,,0zxxxxxxxxxxx（）1231231231231232max101512539561515s.t.25,,0zxxxxxxxxxxxxxxx（）456712345671234612571234567,min2300428s.t.326,,,,,,0xxxxzxxxxxMxMxxxxxxxxxxxxxxxxx（1）解：大M法：在上述线性规划问题的约束条件中减去剩余变量、再分别加上人工变量、，得其中M是一个任意大的正数，据此可列出初始单纯形表如下：cj23100MMθiCBXBbx1x2x3x4x5x6x7MMx6x78613[4]220-100-1100123cj-zj2-4M3-6M1-2MMM003Mx2x7221/4[5/2]101/2-1-1/41/20-11/4-1/20184/5cj-zj5542M012M3142MM3324M032x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5cj-zj0001/21/2M-1/2M-1/2由单纯形表的计算结果得：最优解*49,,0,0,0,0,055TX,目标函数最优值*4923755zX存在非基变量检验数3=0，故该线性规划问题有无穷多最优解。4567671234612571234567,,min=428s.t.326,,,,,,0xxxxwxxxxxxxxxxxxxxxxxx两阶段法：先在上述线性规划问题的约束条件中减去剩余变量,再分别加上人工变量,得第一阶段的数学模型据此可列出单纯初始形表如下：cj0000011θiCBXBbx1x2x3x4x5x6x711x6x78613[4]220-100-1100123cj-zj-4-6-2110001x2x7221/4[5/2]101/2-1-1/41/20-11/4-1/20184/5cj-zj5-20112132000x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5cj-zj0000011第一阶段求得的最优解*490000055TX，，，，，，，目标函数的最优值*0w，因人工变量670xx，所以490000055T，，，，，，是原线性规划问题的基可行解。于是可以进行第二阶段计算，将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，如下表：cj23100θiCBXBbx1x2x3x4x532x2x19/54/501103/5-2/5-3/101/51/10-2/5cj-zj0001/21/2由表中计算可知，原线性规划问题的最优解*490000055TX，，，，，，，目标函数的最优值*4923755z，由于存在非基变量检验数3=0，故该线性规划问题有无穷多最优解。456712345671234122,,,,max10+15120005395615s.t.MxxxxzxxxxxxMxxxxxxxx（）解：大法：在上述线性规划问题的约束条件中加上松弛变量减去剩余变量再加上人工变量得351236712345671525,,,,,,0xxxxxxxxxxxxx其中M是一个任意大的正数，据此可列出单纯形表如下：cj101512000-MθiCBXBbx1x2x3x4x5x6x700-Mx4x5x79155[5]-52361115110001000-10019/5-5/2cj-zj10+2M15+M12+M00-M0100-Mx1x5x79/5247/51003/59-1/51/5[16]3/51/51-2/501000-100193/27/3cj-zj095M310+5M225M0M01012-Mx1x3x73/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001cj-zj02743880M0217816M53880MM0由单纯性表的最终表可以看出，所有非基变量检验数0j，且存在人工变量712x，故原线性规划问题无可行解。4567712341235123671234567,,,min=539561515s.t.25,,,,,,0xxxxwxxxxxxxxxxxxxxxxxxxxx