运筹学作业-王程130404026(2)

x2.(2,2)2/3O1x1

51x1?z经过点（2,2）时，z取得唯一最优解。 661.2将下述线性规划问题化成标准形式。

当x2?（1）minz??3x1?4x2?2x3?5x4?4x1?x2?2x3?x4??2?x?x?x?2x?14?1234 s.t.???2x1?3x2?x3?x4?2?x1,x2,x3?0,x4无约束?

解：上述问题中令z'??z,x4?x4'?x4'',其中x4'?0,x4''?0,则该问题的标准形式为

maxz'?3x1?4x2?2x3?5x4'?5x4''??4x1?x2?2x3?x4'?x4''?2?x?x?x?2x'?2x''?x?14?123445s.t.?

?2x?3x?x?x'?x''?x?2123446???x1,x2,x3,x4',x4'',x5,x6?0（2）minz?2x1?2x2?3x3??x1?x2?x3?4? s.t.??2x1?x2?x3?6

?x?0,x?0,x无约束23?1解：上述问题中令z'??z,x1'??x1,x3?x3'?x3'',其中x3'?0,x3''?0,则该问题的标准形式为maxz'?2x1?2x2?x3'?x3''?x1'?x2?x3'?x3''?4?s.t.?2x1?x2?x3'?x3''?x4?6

?x',x,x',x'',x?0?123341.3 对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。

（）1maxz?3x1?5x2?x1 ?x3?4? 2x ?x?12?24 s.t.??3x1?2x2?x5?18?xj?0 j?1,?,5 ?（2）minz?5x1?2x2?3x3?2x4?x1?2x2?3x3?4x4?7? s.t.?2x1?2x2?x3?2x4?3

? x?0 (j?1,?,4)?j解：（1）该线性规划问题的全部基解见下表中的①～⑧，打√者为基可行解，注*者为最优解，z* =36。

序号①②③④⑤⑥⑦⑧x124400046x263696000x32004440-2x4060-60121212x500-6061860z36*2742453001218可行？√√××√√√×（2）该线性规划问题的标准形式为：

maxz'??5x1?2x2?3x3?2x4?x1?2x2?3x3?4x4?7?

s.t.?2x1?2x2?x3?2x4?3? x?0 (j?1，?,4)?j

其全部基解见下表中的①～⑥，打√者为基可行解，注*者为最优解，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）中，若目标函数变为maxz?cx1?dx2，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。

cczzk??x??x??kx?解：由目标函数maxz?cx1?dx2可得：2 ，其中 。 11dddd3⑴当??k?0 时，可行域的顶点A使目标函数达到最优；

453⑵当??k?? 时，可行域的顶点B使目标函数达到最优；

245⑶当???k?? 时，可行域的顶点C使目标函数达到最优；

2⑷当c?0,d?0或c?0,d?0时，最优解为O点 。

1.6 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。

（1）minz?2x1?3x2?x3?x1?4x2?2x3?8? s.t.?3x1?2x2 ?6

? x,x,x?0?123（1）解：大M法：（2）maxz?10x1?15x2?12x3?5x1?3x2?x3?9??5x?6x?15x?15?123 s.t.??2x1?x2?x3?5??x1,x2,x3?0 在上述线性规划问题的约束条件中减去剩余变量x4、x5,再分别加上人工变量x6、x7，得 minz?2x1?3x2?x3?0x4?0x5?Mx6?Mx7?x1?4x2?2x3?x4?x6?8? s.t.?3x1?2x2?x5?x7?6?x,x,x,x,x,x,x?0?1234567其中M是一个任意大的正数，据此可列出初始单纯形表如下： cj 2 3 1 0 0 M CB XB b x1 x2 x3 x4 x5 x6 M x6 M x7 cj-zj 3 x2 M x7 cj-zj 3 x2 9/5 2 x1 4/5 cj-zj 2 2 8 6 1 3 2-4M 1/4 [5/2] 55?M 42 M x7 0 1 0 0 1 0 θi 2 3 8 4/5 [4] 2 3-6M 1 0 0 2 0 1-2M 1/2 -1 -1 0 M -1/4 1/2 0 -1 M 0 -1 M 1 0 0 1/4 -1/2 33M? 24131M? ?M 2420 1 0 1 0 0 3/5 -2/5 0 -3/10 1/5 1/2 1/10 -2/5 1/2 3/10 -1/5 M-1/2 -1/10 2/5 M-1/2 ?49?由单纯形表的计算结果得：最优解X*??,,0,0,0,0,0? ,

?55?49目标函数最优值z*?2??3??7

55TX存在非基变量检验数?3=0，故该线性规划问题有无穷多最优解。

两阶段法：先在上述线性规划问题的约束条件中减去剩余变量x4,x5,再分别加上人工变量x6,x7,得第一阶段的数学模型 min w=x6?x7?x1?4x2?2x3?x4?x6?8? s.t.?3x1?2x2?x5?x7?6?x,x,x,x,x,x,x?0?1234567 据此可列出单纯初始形表如下： cj 0 0 0 CB XB b x1 x2 x3 1 x6 1 x7 cj-zj 0 x2 1 x7 cj-zj 0 x2 9/5 0 x1 4/5 cj-zj 2 2 8 6 1 3 -4 1/4 [5/2] 5- 20 x4 -1 0 1 -1/4 1/2 ?1 20 x5 0 -1 1 0 -1 1 1 x6 1 0 0 1/4 -1/2 3 21 x7 0 1 0 0 1 0 θi 2 3 8 4/5 [4] 2 -6 1 0 0 2 0 -2 1/2 -1 1 0 1 0 *1 0 0 3/5 -2/5 0 -3/10 1/5 0 T1/10 -2/5 0 3/10 -1/5 1 -1/10 2/5 1 ?49?第一阶段求得的最优解X??，，0，0，0，0，0?，目标函数的最优值w*?0，因人

?55??49?工变量x6?x7?0，所以?，，0，0，0，0，0?是原线性规划问题的基可行解。于是可

?55?T