其次章习题运筹学

本文格式为Word版，下载可任意编辑——其次章习题运筹学其次章习题

12、对于下面的线性规划问题，以B??A2,A3,A6?为基写出相对应的典式。

?minx1?2x2?x3??s.t.3x1?x2?2x3?x4?7???2x1?4x2?x5?12??4x?3x?8x?x?101236??xj?0,j?1?6?解：由题可以知：

?3?12100??TA???240010??C??1?21000?

???438001??取一个基B??A4A5??120??3?12?A6?，即：B??400?且N???240?

???????381????438??TTCB???210?CN??100?

在matlab中可以计算得到：

1??00??4?1?1T?1B??0?b?B?1b??35?39?

8?2?7??4?1???4???5TT?1TCBb??1CBBN?CN???4TT?1T由Z?CBb?CBBN?CNxN可得典式的目标函数：

123???8???513Z??1?x1?x4?x5

428由xB?B?1NxN?b可得：

1?1?x?x?x5?3?2124?11?5x?x?x?x5?5?13428?47?25?x?4x?x5?x6??394?214?由此与题中线性规划问题相对应的典式为：

513?minZ??1?x?x?x514?428??s.t.?11?x1?x2?x5?3??24?511?x1?x3?x4?x5?5?428?257??x1?4x4?x5?x6??3924??xj?0,j?1,?,6?

14、用单纯形法求解线面的线性规划问题，并在平面上画出迭代点走过的路线。

?min?s.t.?????????z??2x1?x22x1?5x2?60x1?x2?183x1?x2?44x2?10x1,x2?0?minz??2x1?x2?s.t.2x?5x?x?60123??x1?x2?x4?18??3x?x?x?44125??x2?x6?10?xj?0,j?1,?,6??解：由题先将题中线性规划问题化为标准形：

?2?1由此可写出A，即为：A???3??051111000010000100?0??0??1?则可以得出B??A3A4A5A6?是一个单位矩阵，且b??60184410?＞0，

T所以基B是可行基，x3,x4,x5,x6为基变量，x1,x2为非基变量。基B对应的基本可

T行解为：x??0060184410?，其目标函数值z0?0。方程组Ax?b已是

典式，得到一张单纯形表如下：

xxx

210x251x110x3*10x010

123x4

x5

x6

RHS

3456001000001000001060184410由题可知，N??A1TA2?，cB??0000?cT?1?N???2T?1T检验数可由?k?cBBN?cN可得：?1?2不是负数，则当前解不是最优解，A1列

中有三个元素大于零，取：

?bbb??601844?44min?1,2,3??min?,,???213?3?a11a21a31?故转轴元为a31，x1为进基变量，x5为出基变量。

???A目前的新基为B3

x3x1A4x2A1

A6?,进行旋转变换后得下表：

xxxx

3456RHS000130100000100?232300001?88313323??923103443x41?3131x0x56131010

9210?44?它对应的基本可行解为:x??0010?,其目标函数值为

33?3?z0??881。但?2?为正数，仍不是最优解，此时以a22为转轴元，x2为进基变33T量，x4为出基变量，进行旋转变化得下表：

3x1

x2

x3

x4

12x5

12x6

RHS00010001000??00001?1816x013?2323?23?21212119652x4010x51?2?32836152x6

11915??835它对应的基本可行解为：x???00?，目标函数值为

62??62z0??181，此时检验数向量?为负数，故为最优解。6T

16、用单纯形法求解以下线性规划问题：

?min??s.t.??（1）、????z??2x1?x2?x33x1?x2?x3?60x1?x2?2x3?10x1?x2?x3?20xj?0,j?1,2,3

解：由题先将题中线性规划问题化为标准形：

?min??s.t.??????

z??2x1?x2?x33x1?x2?x3?x4x1?x2?2x3x1?x2?x3?x5?60?10?x6?20

xj?0,j?1,2,3,4,5,6?311100??1?12023由此可以得到矩阵A??????11?1001??

则可以得出B??A4A5且b??601020?＞0，所以基BA6?是一个单位矩阵，

T是可行基，x4,x5,x6为基变量，x1,x2,x3为非基变量。基B对应的基本可行解为：

Tx??00061020?，其目标函数值z0?0。

由此写出最初的单纯性表：

xx

21x31x1*-1x11

124x3

x4

x5

x6

RHS

56-11210100001000010601020由题可知，N??A1A2TA3?，cB??000?cT?11?N???2T?1T检验数可由?k?cBBN?cN可得：?1?2不是负数，则当前解不是最优解，A1列

中有三个元素大于零，取：

?bbb??601020?min?1,2,3??min?,,??10

?311??a11a21a31?故转轴元为a21，x1为进基变量，x5为出基变量。进行旋转变换后得下表：

xx

03x04x1-1x02*

1241x3

x4

x5

x6

RHS

6-5-52-3T0100-2-31-10001-20301010它对应的基