最全运筹学习题及答案

第 17 页 共 64 页

表 1—1 饲料 蛋白质（克） 矿物质（克） 维生素（毫克） 价格（元/公斤） 1 3 1 0.5 0.2 2 2 0.5 1 0.7 3 1 0.2 0.2 0.4 4 6 2 2 0.3 5 18 0.5 0.8 0.8 解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可。 解题过程：minz?0.2x1?0.7x2?0.4x3?0.3x4?0.8x5 ?3x1?2x2?x3?6x4?18x5?700?x?0.5x?0.2x?2x?0.5x?30?2345 s..t?10.5x?x?0.2x?2x?0.8x?10012345??x1,x2,x3,x4,x5?0?

第二章（67页）

2.1用改进单纯形法求解以下线性规划问题。

（1）Max z=6x1-2x2+3x3 2x1-x2+3x3?2

x1+4x3?4 x1，x2，x3?0 （2）min z=2x1+x2 3x1+x2=3 4x1+3x2?6

x1+2x2?3 x1,x2?0

解： （1）

先化成标准型：

Max z=6x1-2x2+3x3+0x4+0x5 s.t. 2x1-x2+2x3+x4=2

第 18 页 共 64 页

x1+4x3+x5=4 x1,x2,x3,x4,x5 ?0

?10?T令B0=（P4，P5）=?? XB0=（x4,x5),CB0=(0,0)

?01??2?12?TXN0=(P1,P2,P3)=?xxx) , =（，， N123?0?104??10??2?CN0=(6,-2,3)，B0?1=?b,=?0??

01???4?非基变量的检验数

CN0CB0B0?1N0CN0?N=-==(6,-2,3) 0因为x1的检验数等于6，是最大值，所以，x1为换入变量， B?10?2??2??1b0=??；B0P1=??

?4??1?由?规则得： ?=1

x4为换出变量。

?20?TB1=(P4，P5)=??,XB1=（x1,x5)，CB1=(6,0). ?11?N1=(P4,P2,P3), XN1=（x4，x2，x3)T

?0.50??1?CN1=(0，-2，3)，B1?1=?b,=?1??

?0.51???3?非基变量的检验数 ?N1=（-3，1，-3）

因为x2的检验数为1，是正的最大数。所以x2为换入变量；

??0.5?B?10P2=??

0.5??由?规则得：

?=6

所以x5是换出变量。

第 19 页 共 64 页

?2?1?TXB2=(P1，P2)=?xx),=（,，CB2=(6,-2). B12?2?10?N2=(P4,P5，P3), XN2=（x4，x5，x3)T CN2=(0，0，3)，B2?1?01??4?=??,b2=?? ?12???6?非基变量的检验数 ?N2=（-2，-2，-9）

非基变量的检验数均为负数，愿问题已达最优解。

?4?最优解X= ??

?6?即：X=（4,6,0)T

目标函数最优值 max z=12 （2） 解 ：

Min z=2x1+x2+0x3+Mx4+Mx5+0x6 S.T. 3x1+x2+x4=3 4x1+3x2-x3+x5=6 x1+2x2+x6=3 x1,x2,x3,x4,x5, x6?0

M是任意大的正数。

（非基变量检验数计算省略）

原问题最优解是X=（0.6，1.2，0） 目标函数最优值： z=12/5 2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数字填上。 3 5 4 0 0 0 c jCB XB x2 x5 5 0 b 8/3 14/3 x1 x2 x3 x4 x5 x6 2/3 -4/3 1 0 0 5 1/3 -2/3 0 1 0 0 第 20 页 共 64 页

0 x6 cj-zj 20/3 5/3 -1/3 0 0 . . . 4 4 -2/3 -5/3 0 0 1 0 x2 x3 x1 cj-zj 15/41 -6/41 -2/41 8/41 5/41 -12/41 -10/41 4/41 15/41 解： cj 3 b 8/3 14/3 20/3 x1 5 x2 4 x3 0 x4 0 x5 0 x6 CB XB x2 x5 x6 cj-zj 5 0 0 . . . 5 4 3 x2 x3 x1 cj-zj 80/41 50/41 44/41 0 0 1 0 1 0 0 0 0 1 0 0 15/41 -6/41 -2/41 -45/41 2.3写出下列线性规划问题的对偶问题。 （1）min z= 2 x1+2 x2+4 x3