运筹学第一章作业解答

际恩陆2020/2/271运筹学作业主讲：陆际恩Tel：13592990256Email：[e-mail]运筹帷幄之中决胜千里之外际恩陆2020/2/272教材P43习题1.1：⑴、⑵；1.2：⑴、⑵；1.3：⑴；1.4：⑵；1.7：⑷；1.8；1.13；1.15；第一章作业际恩陆2020/2/273教材P431.1用图解法求解下列LP问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。0,423664.32min)1(21212121xxxxxxstxxz:,:21如右所示坐标系并按比例作图为坐标画直角平面为横坐标以变量解xx从右图可看出,当(x1,x2)=(1.2,0.2)到(x1,x2)=(1.5,0)时,具有无穷多最优解,Z=3。1x2x12211.53x1+2x2=44x1+6x2=6Z=2x1+3x2（1.2，0.2）际恩陆2020/2/2740,124322.23max)2(21212121xxxxxxstxxz:,:21如右所示坐标系并按比例作图为坐标画直角平面为横坐标以变量解xx从右图可看出,此题无可行解。1x2x24423x1+4x2=122x1+x2=213际恩陆2020/2/2751.2将下列LP问题化成标准形式无约束43214321432143214321,0,,232142224.5243min)1(xxxxxxxxxxxxxxxxstxxxxz:,,0,0,,:4'44'44形式为该问题的标准问题的转化规则按照其中上述问题中令解LPxxxxxZZ际恩陆2020/2/2760,,,,,,2321422224.0055243max)1(654'432164'432154'43214'4321654'4321xxxxxxxxxxxxxxxxxxxxxxxxstxxxxxxxz际恩陆2020/2/277无约束321321321321,0,0624.322min)2(xxxxxxxxxstxxxz:,,0,0,,,:3'33'331'1的标准形式为该问题问题的转化规则按照中其上述问题中令解LPxxxxxxxZZ际恩陆2020/2/2780,,,,624.03322max)1(43'32'143'32'13'32'143'32'1xxxxxxxxxxxxxxstxxxxxz际恩陆2020/2/2796,,1j0x0xx310x2x4xx89x3x6x3x12.stx2xx3zmax)1(j61532143213211.3对下列线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。际恩陆2020/2/27101000030204180036312)P,P,P,P,P,P(:),P,P,P,P,P,P(⑴:654321654321即用矩阵表示为首先将约束条件的系数解问题存在多少个基解则立的子矩阵能组合成多少个线性独判断LPPPPPPP⑵,),,,,,(654321际恩陆2020/2/27110,)0,5,3,0,0,0(:0530,3048102631293:,100020003),,(1)1(6543211632153214654zX，xxx，x，xxxxxxxxxxxxPPP①T它同时也是一基可行解可得一个基解得令非基变量故有线性独立因为际恩陆2020/2/27123672632z,0，0，0，67，632，0。X，67x，67x632x0x，0，x，xxx0x3x210x4xx8x39x6x3x12:,0034186312)P,P,P(②2T233216546153214321321所以它不是一基可行解因为可得一个基解得令非基变量故有线性独立因为际恩陆2020/2/271310z,)0，0,7,0,10,0(X，，7x，7x10x0x，0，x，xxx0x3x2x410xx8x69x3x3x12:,0030183312)P,P,P(③3T)3(44216536153234214211不可能有最优解所以它不是一基可行解因可得一个基解得令非基变量故有线性独立因为际恩陆2020/2/2714302303z,)0，5.3,0,0,3,0(X:，5.3x3x0x，0，x，xxx0x3x410x2xx8x3x69x3x12:,0032180312)P,P,P(④2T)4(5216436135214321521同时也是一基可行解可得一个基解得令非基变量故有线性独立因为际恩陆2020/2/271545121512048213,)4210,0,0,4,1221(:4214122100324108369312:,1030180312),,(5)5(6215436153214321621z，X，xxx，，x，xxxxxxxxxxxxPPP⑤T但它并不是一基可行解可得一个基解得令非基变量故有线性独立因为际恩陆2020/2/27165z,0，0，8，5.2，0，0X：，,8x5.2x0x：，0，x，xxx0x3x2x10x4x8x39x3x6x12:,0030483612)P,P,P(⑥6T64316526152312431431其基解为但不是基可行解是一个基解得令非基变量故有线性独立因为际恩陆2020/2/271735.12003，Z0，8，0，5.1，0，0X：,8x5.1x0x：，0，x，xxx0x3x10x2x4x8x3x39x6x12:,0032480612)P,P,P(⑦3T75316426125314231531也是一个基可行解为是一个基解得令非基变量故有线性独立因为际恩陆2020/2/271825.02013z3，0，0，5.0，0，1X：,,3x5.0x1x：，0，x，xx0xx3x2x10x4x8x3x39x6x12:,1030480612)P,P,P(⑧8T86315426152314231631基解的结果是但不是基可行解是一个基解得令非基变量故有线性独立因为际恩陆2020/2/2719002003，Z)0，2，3,0,0,0(X:，2x3x0x，0x,，xxx0x3x4x10x2x8x6x39x3x12:,0032080312)P,P,P(⑨4T)9(5416326132513241541它同时也是一基可行解可得一个基解得令非基变量故有线性独立因为际恩陆2020/2/2720415z,)415,0，2,0,0,45(X:，415x2x45x，0，x，xx0xx3x2x4x10x8x6x39x3x12:,1030080312)P,P,P(⑩10T)10(64153261532132416　41它也不是一基可行解可得一个基解得令非基变量故有线性独立因为际恩陆2020/2/2721故不能求解线性不独立因为,000041363　)P,P,P(⑾432故也不能求解线性也不独立因为,000241063　)P,P,P(⑿532际恩陆2020/2/272236723160z,0，0，0，67，316，0X：，，0x67x316x：，0，x，xxx30xx2x810x4xx3x129x6x3：,100041063　)P,P,P(⒀11T116325411651324132632基解的结果是但它不是一基可行解可得一个基解可得令非基变量故有线性独立因为际恩陆2020/2/2723将上述解列表如下，表中所有解都是基解x1x2x3x4x5x6解的性质Z000350032/6-7/60000100-70003003.5021/12-400021/400-2.5800001.508010-0.50030003205/400-2015/4016/3-7/6000基可行解基解基解最优解基解基解最优解基可行解基可行解基解基解031035/4-532015/43际恩陆2020/2/27240x,x24x2x615x5x3.stxx2zmax2212121211.4分别用图解法和单纯形求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。际恩陆2020/2/2725解：⑴用图解法求解：①以x1为横坐标，以x2为纵坐标画图如下x2x1036912369126x1+2x2=243x1+5x2=15Q3（15/4，3/4）Q2（5，0）Q1（4，0）Q4（0，3）Q5（0，12）际恩陆2020/2/2726cj2100相当于Z=2x1+x2CBXBbx1x2x3x4相当于O(0,0)Z=00x31535100x4246201σj=cj－zj21000x33041-1/2相当于Q1(4,0)Z=82x1411/301/6σj=cj－zj01/30-1/31x23/4011/4-1/8相当于Q3(15/4,3/4)Z=33/42x115/410-1/121/24σj=cj－zj000-3/2⑵用单纯形法求解，过程如下表所示：最优解：Z=2x1+x2=2*15/4+3/4=33/4，即Q3点。际恩陆2020/2/27270x,x,x5xxx215x15x6x59xx3x5.stx12x15x10zmax43213213213213211.7分别用单纯形中的大M法和两阶段法求解下述线性规划问题，并指出属哪一类解。际恩陆2020/2/2728解：⑴先用大M法求解。0x,x,x,x,x,x5xxxx215xx15x6x59xxx3x5.stx12x15x10zmax654321632153214321321①把原问题化为标准型这个矩阵中不含有单位矩阵，因此很难找到初始基。对于这种线性规划问题的系数矩阵不含有单位矩阵的情况，我们往往采用添加人工变量的方法，来人为构造一个单位矩阵。这样的方法就是人工变量法。际恩陆2020/2/2729为了构造出单位矩阵，在系数矩阵中添加一列单位列向量，系数矩阵变为：1100112001015650001135PPPPPPP7654321线性规划问题的约束条件就变为：0x,x,x,x,x,x,x5xx-xx32x1