运筹学习题答案一

习题一

1.1 讨论下列问题：

（1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A有5台，利用率为0.8,设备B有7台，利用率为0.85,其它条件不变，数学模型怎样变化．

（2）在例1.2中，如果设xj(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化．

（3）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路．

（4）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化．

（5）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化．

1.2 工厂每月生产A、B、C三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．

表1－23

产品 资源 材料(kg) 设备(台时) 利润(元/件) A 1.5 3 10 B 1.2 1.6 14 C 4 1.2 12 资源限量 2500 1400 根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大．

【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为

maxZ?10x1?14x2?12x3?1.5x1?1.2x2?4x3?2500?3x?1.6x2?1.2x3?1400?1? ?150?x1?250??260?x2?310?120?x?1303???x1,x2,x3?01.3 建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格

及数量如表1－24所示：

每套窗架需要材料 需要量（套） 200 表1－24 窗架所需材料规格及数量 型号A 型号B 长度数量(根) （m） A1：1.7 2 A2：1.3 3 长度(m) B1：2.7 B2：2.0 150 2 3 数量(根) 问怎样下料使得（1）用料最少；（2）余料最少． 【解】 第一步：求下料方案，见下表。 方案 一 二 三 四 五 六 七 八 九 十 十一 十二 十三 十四 需要量 B1:2.7m 2 1 1 1 0 0 0 0 0 0 0 B2:2m 0 1 0 0 3 2 2 1 1 1 0 A1:1.7m 0 0 1 0 0 1 0 2 1 0 3 A2:1.3m 0 1 1 2 0 0 1 0 1 3 0 0 0 2 2 0 0 1 3 0 0 0 4 300 450 400 600 余料 0.6 0 0.3 0.7 0 0.3 0.7 0.6 1 0.1 0.9 0 第二步：建立线性规划数学模型 设xj（j=1,2,…，14）为第j种方案使用原材料的根数，则 （1）用料最少数学模型为

140.4 0.8 minZ??xj?1j?2x1?x2?x3?x4?300? ?x2?3x5?2x6?2x7?x8?x9?x10?450??x3?x6?2x8?x9?3x11?2x12?x13?400?x?x?2x?x?x?3x?2x?3x?4x?600347910121314?2??xj?0,j?1,2,?,14用单纯形法求解得到两个基本最优解

X(1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 (2)

X=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 （2）余料最少数学模型为

minZ?0.6x1?0.3x3?0.7x4???0.4x13?0.8x14?2x1?x2?x3?x4?300??x2?3x5?2x6?2x7?x8?x9?x10?450 ??x3?x6?2x8?x9?3x11?2x12?x13?400?x?x?2x?x?x?3x?2x?3x?4x?600347910121314?2??xj?0,j?1,2,?,14用单纯形法求解得到两个基本最优解

X(1)=( 0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550根 (2)

X=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根 显然用料最少的方案最优。

1.4某企业需要制定1～6月份产品A的生产与销售计划。已知产品A每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A的单件成本与售价如表1－25所示。

表1－25 1 2 3 4 5 6 月份 产品成本(元/件) 300 330 320 360 360 300 销售价格(元/件) 350 340 350 420 410 340 （1）1～6月份产品A各生产与销售多少总利润最大，建立数学模型； （2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。 【解】设xj、yj（j＝1，2，?，6）分别为1～6月份的生产量和销售量，则数学模型为

maxZ??300x1?350y1?330x2?340y2?320x3?350y3?360x4?420y4?360x5?410y5?300x6?340y6?x1?800??x1?y1?x2?800?x?y?x?y?x?80011223??x1?y1?x2?y2?x3?y3?x4?800?x?y?x?y?x?y?x?y?x?80012233445?1?x1?y1?x2?y2?x3?y3?x4?y4?x5?y5?x6?800（1）???x1?y1?200??x?y?x?y?200122?1??x1?y1?x2?y2?x3?y3?200???x1?y1?x2?y2?x3?y3?x4?y4?200??x?y?x?y?x?y?x?y?x?y?2001122334455???x1?y1?x2?y2?x3?y3?x4?y4?x5?y5?x6?y6?200?x,y?0;j?1,2,?,6?jj

（2）目标函数不变，前6个约束右端常数800改为1000，第7～11个约束右端常数200改为0，第12个约束“≤200”改为“＝－200”。

1.5 某投资人现有下列四种投资机会, 三年内每年年初都有3万元（不计利息）可供投资： 方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20％，下一年可继续将本息投入获利；

方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50％，下一年可继续将本息投入获利，这种投资最多不超过2万元；

方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60％，这种投资最多不超过1.5万元；

方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30％，这种投资最多不超过1万元．

投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型. 【解】是设xij为第i年投入第j项目的资金数，变量表如下

第1年 第2年 项目一 x11 x21 项目二 x12 项目三 x23 x34 项目四 第3年 x31 数学模型为 maxZ?0.2x11?0.2x21?0.2x31?0.5x12?0.6x23?0.3x34?x11?x12?30000???1.2x11?x21?x23?30000??1.5x?1.2x?x?x?3000012213134???x12?20000?x?15000?23?x34?10000???xij?0,i?1,?,3;j?1,?4

最优解X=(30000，0，66000，0，109200，0)；Z＝84720

1.6 炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合，辛烷值不低于94，每桶利润5元，见表1－26。

表1－26 成品油 高级汽油 中石脑油 半成品油 辛烷值 蒸汽压：公斤／平方厘米 利润(元/桶) 重整汽油 裂化汽油 ≥94 一般汽油 中石脑油 重整汽油 裂化汽油 ≥84 航空煤油 一般煤油 轻油、裂化轻油、裂化油、重油、残油、重油、残油按10:4:3:1油 调合而成 ≤1 1.5 5 4.2 3 半成品油的辛烷值、气压、及每天可供应数量见表1－27。 表1－27

1中石脑油 2重整汽油 3裂化汽油 4轻油 5裂化油 6重油 半成品油 辛烷值 80 115 105 蒸汽压：公斤／ 1.0 1.5 0.6 平方厘米 每天供应数量2000 1000 1500 1200 1000 1000 (桶) 问炼油厂每天生产多少桶成品油利润最大，建立数学模型。 解 设xij为第i（i＝1,2,3,4）种成品油配第j(j=1,2,?,7)种半成品油的数量（桶）。 总利润：

7残油 0.05 800 Z?5(x11?x12?x13)?4.2(x21?x22?x23)?3(x34?x35?x36?x37)?1.5(x44?x45?x46?x47)高级汽油和一般汽油的辛烷值约束

80x11?115x12?105x13)x11?x12?x13?94,84?80x21?115x22?105x23x21?x22?x23?94

航空煤油蒸气压约束

x34?1.5x35?0.6x36＋0.05x37x34?x35?x36＋x37?1

一般煤油比例约束

x44:x45:x46:x47?10:4:3:1

即

x44x45?104,x45x46?43,x46x47?31

半成品油供应量约束

x11?x21?2000x12?x22?1000x13?x23?1500x34?x44?1200 x35?x45?1000x36?x46?1000x37?x47?800整理后得到

maxZ?5x11?5x12?5x13?4.2x21?4.2x22?4.2x23?3x34?3x35?3x36?3x37?1.5x44?1.5x45?1.5x46?1.5x47??14x11?21x12?11x13?0???14x21?21x22?11x23?0??4x?31x?21x?0212223??0.5x35?0.4x36?0.95x37?0?4x?10x?045?44?3x45?4x46?0??x46?3x47?0??x11?x21?2000?x?x?100022?12?x13?x23?1500??x34?x44?1200?x?x?10003545??x36?x46?1000?x?x?80047?37??xij?0;i?1,2,3,4;j?1,2,?,7

1.7 图解下列线性规划并指出解的形式：

maxZ?2.5x1?2x2?2x1?x2?8?(1) ?0.5x1?1.5??x1?2x2?10?x,x?0?12

【解】最优解X＝（2，4）；最优值Z=13

1.8 将下列线性规划化为标准形式

maxZ?x1?4x2?x3?2x1?x2?3x3?20(1)??5x1?7x2?4x3?3??10x1?3x2?6x3??5?x?0,x?0,x无限制23?1

'''【解】（1）令x3?x3?x3,x4,x5,x6为松驰变量 ，则标准形式为

maxZ?x1?4x2?x3?x3'''?2x1?x2?3x3?3x3?x4?20?''' ?5x1?7x2?4x3?4x3?x5?3?'''??10x1?3x2?6x3?6x3?x6?5?x,x,x',x'',x,x,x?0?1233456'''minZ?9x1?3x2?5x3?|6x1?7x2?4x3|?20? (2) ?x1?5

??x1?8x2??8?x?0,x?0,x?023?1【解】（2）将绝对值化为两个不等式，则标准形式为

maxZ???9x1?3x2?5x3?6x1?7x2?4x3?x4?20??6x1?7x2?4x3?x5?20? ??x1?x6?5??x?8x?82?1??x1,x2,x3,x4,x5,x6?0maxZ?2x1?3x2?1?x1?5 (3)???x1?x2??1?x?0,x?02?1【解】方法1：

maxZ?2x1?3x2?x1?x3?1? ?x1?x4?5??x1?x2?1?x,x,x,x?0?1234方法2：令x1??x1?1,有x1＝x1??1,x1??5?1?4 maxZ?2(x1??1)?3x2?x1??4???(x1??1)?x2??1?x,x?0?12则标准型为

maxZ?2?2x1??3x2?x1??x3?4???x1??x2?0?x?,x,x?0?123maxZ?min(3x1?4x2,x1?x2?x3)?x1?2x2?x3?30?(4) ?4x1?x2?2x3?15??9x1?x2?6x3??5?x无约束,x、x?023?1

??x1??，线性规划模型变为 【解】令y?3x1?4x2,y?x1?x2?x3,x1?x1maxZ?y?y?3(x1??x1??)?4x2?y?x1??x1???x2?x3?? ?x1??x1???2x2?x3?30?????4(x1?x1)?x2?2x3?15?9(x??x??)?x?6x??51123???x1?,x1??,x2、x3?0标准型为

maxZ?y?y?3x1??3x1???4x2?x4?0?y?x1??x1???x2?x3?x5?0?? ?x1??x1???2x2?x3?x6?30?????4x1?4x1?x2?2x3?x7?15??9x??9x???x?6x?x?511238???x1?,x1??,x2,x3,x4,x5,x6,x7,x8?0

1.9 设线性规划

maxZ?5x1?2x2?2x1?3x2?x3?50 ?4x?2x?x?60?124?x?0,j?1,?,4?j?2取基B1?(P1，P3)???41??2?、B2＝?0??40?分别指出B1和B2对应的基变量和非基变量，?，1?求出基本解，并说明B1、B2是不是可行基．

【解】B1：x1，x3为基变量，x2，x4为非基变量,基本解为X=（15，0，20，0）T，B1是可行基。B2：x1,x4是基变量，x2,x3为非基变量，基本解X=（25，0，0，－40）T，B2不是可行基。

1.10分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点．

maxZ?x1?3x2??2x1?x2?2 (1)?

2x?3x?12?12?x,x?0?12【解】图解法

单纯形法： C(j) C(i) 0 0 3 0 3 1 对应的顶点： 基可行解 、X(1)=（0，0，2，12） 1 Basis X3 X4 X2 X4 X2 X1 X1 -2 2 1 -2 [8] 7 0 1 0 3 X2 [1] 3 3 1 0 0 1 0 0 0 X3 1 0 0 1 -3 -3 0.25 -0.375 -0.375 0 X4 0 1 0 0 1 0 0.25 0.125 -0.875 b 2 12 0 2 6 6 7/2 3/4 45/4 Ratio 2 4 M 0.75 C(j)-Z(j) C(j)-Z(j) C(j)-Z(j) 可行域的顶点 （0，0） （0，2） (37,) 42、X=（0，2，0，6，） X(3)=（3737、,,0,0) 42454(2)最优解X?(,),Z?42

minZ??3x1?5x2?x1? (2) ?x1??x1?x?1?2x2?6?4x2?10?x2?4?0,x2?0

【解】图解法

单纯形法： C(j) Basis X3 X4 X5 C(j)-Z(j) X3 X2 X5 C(j)-Z(j) X1 X2 X5 C(j)-Z(j) X1 X2 X4 C(j)-Z(j) -3 -5 0 -3 -5 0 0 -5 0 C(i) 0 0 0 -3 X1 1 1 1 -3 [0.5] 0.25 0.75 -1.75 1 0 0 0 1 0 0 0 -5 X2 2 [4] 1 -5 0 1 0 0 0 1 0 0 0 1 0 0 0 X3 1 0 0 0 1 0 0 0 2 -0.5 -1.5 3.5 -1 1 -3 2 0 X4 0 1 0 0 -0.5 0.25 -0.25 1.25 -1 0.5 [0.5] -0.5 0 0 1 0 0 X5 0 0 1 0 0 0 1 0 0 0 1 0 2 -1 2 1 b 6 10 4 0 1 2.5 1.5 -12.5 2 2 0 -16 2 2 0 -16

Ratio 3 2.5 4 2 10 2 M 4 0

对应的顶点： 基可行解 、X(1)=（0，0，6，10，4） 可行域的顶点 （0，0） 、X=（0，2.5，1，0，1.5，） X(3)=（2，2，0，0，0） X(4)=（2，2，0，0，0） 最优解：X=（2，2，0，0，0）；最优值Z＝－16 该题是退化基本可行解，5个基本可行解对应4个极点。

1.11用单纯形法求解下列线性规划

maxZ?3x?4x?x?2x1?3x2?x3?1(1)??x1?2x2?2x3?3?x?0,j?1,2,3?j【解】单纯形表： (2)（0，2.5） (2，2) （2，2）

C(j) Basis X4 X5 C(j)-Z(j) X2 X5 C(j)-Z(j) X1 X5 C(j)-Z(j) 3 0 4 0 C(i) 0 0 3 X1 2 1 3 [2/3] -1/3 1/3 1 0 0 4 X2 [3] 2 4 1 0 0 3/2 1/2 -1/2 1 X3 1 2 1 1/3 4/3 -1/3 1/2 3/2 -1/2 0 X4 1 0 0 1/3 -2/3 -4/3 1/2 -1/2 -3/2 0 X5 0 1 0 0 1 0 0 1 0 R. H. S. 1 3 0 1/3 7/3 -4/3 1/2 5/2 -3/2 Ratio 1/3 3/2 1/2 M 最优解：X=（1/2，0，0，0，5/2）；最优值Z＝3/2

maxZ?2x1?x2?3x3?5x4?x1?5x2?3x3?7x4?30? (2) ?3x1?x2?x3?x4?10?2x?6x2?x3?4x4?20?1?xj?0,j?1,?,4?

【解】单纯形表： C(j) Basis X5 X6 X7 C(i) 0 0 0 2 X1 1 3 2 1 X2 5 -1 -6 -3 X3 3 [1] -1 5 X4 -7 1 [4] 0 X5 1 0 0 0 X6 0 1 0 0 X7 0 0 1 R. H. S. Ratio 30 10 20 M 10 5 C(j)-Z(j) X5 X6 X4 C(j)-Z(j) X5 X2 X4 C(j)-Z(j) 0 1 5 0 0 5 2 9/2 1 -3 5 0 0 1 0 0 0 1 0 0 0 0 0 1 0 65 M -11/2 5/4 5/2 1/2 -1/2 32 5 8 -43 [1/2] 5/4 -3/2 -1/4 17/2 -7/4 0 1 0 0 15 5/2 7/2 -23 0 1 0 0 0 0 7/4 -1/4 1/4 -5/4 5 5 120 10 20 10 M M 0 1 0 11 -1 2 -1/2 3 -1/2 -17 3 10 M 因为λ7＝3>0并且ai7<0(i=1,2,3)，故原问题具有无界解，即无最优解。

maxZ?3x1?2x2?1x83??x1?2x2?3x3?4 (3)??4x1?2x3?12??3x1?8x2?4x3?10?x,x,x?0?123

【解】 C(j) Basis X4 X5 X6 C(j)-Z(j) X4 X1 X6 C(j)-Z(j) X4 X1 X2 0 3 2 0 3 0 C(i) 0 0 0 3 X1 -1 [4] 3 3 0 1 0 0 0 1 0 2 X2 2 0 8 2 2 0 [8] 2 0 0 1 -0.125 X3 3 -2 4 -1/8 5/2 -1/2 11/2 11/8 9/8 -1/2 [11/16] 0 X4 1 0 0 0 1 0 0 0 1 0 0 0 0 X4 1 0 0 0 34112720 X5 0 1 0 0 1/4 1/4 -3/4 -3/4 7/16 1/4 -3/32 -9/16 0 X5 13/22 2/11 -3/22 -9/16 T0 X6 0 0 1 0 0 0 1 0 -1/4 0 1/8 -1/4 0 X6 -5/11 1/11 2/11 -1/4 374R. H. S. 4 12 10 0 7 3 1 9 27/4 3 1/8 Ratio M 3 10/3 3.5 M 1/8 6 M 0.181818 C(j)-Z(j) 0 0 0 X3进基、X2出基，得到另一个基本最优解。 37/4 R. H. S. 72/11 34/11 2/11 37/4 Basis X4 X1 X3 C(j) 3 X1 0 1 0 0 182742 X2 -18/11 8/11 16/11 0 -0.125 X3 0 0 1 0 (2) 0 3 -0.125 Ratio 6 M 0.1818 C(j)-Z(j) 原问题具有多重解。 基本最优解X(1)?(3,,0,,0)及X?(,0,1111,,0);Z?,最优解的通解可表

示为X?aX(1)?(1?a)XX?(3411(2)即

a,18a,211?211a,7211?7211a,0),(0?a?1)

T?111

maxZ?3x1?2x2?x3?5x1?4x2?6x3?25（4）?

8x?6x?3x?24?123?x?0,j?1,2,3?j【解】单纯形表：

C(j) Basis X4 X5 C(j)-Z(j) X4 0 C(i) 0 0 3 X1 5 [8] 3 0 2 X2 4 6 2 1/4 1 X3 6 3 1 33/8 0 X4 1 0 0 1 0 0 0 X5 0 1 0 -5/8 1/8 -3/8 R. H. S. 25 24 0 10 3 9 Ratio 5 3 X1 3 1 3/4 3/8 C(j)-Z(j) 0 -1/4 -1/8 最优解：X=（3，0，0，10，0）；最优值Z＝9

1.12 分别用大M法和两阶段法求解下列线性规划：

maxZ?10x1?5x2?x3?5x1?3x2?x3?10 (1) ?

??5x1?x2?10x3?15?x?0,j?1,2,3?j【解】大M法。数学模型为 maxZ?10x1?5x2?x3?Mx5?5x1?3x2?x3?x5?10???5x1?x2?10x3?x4?15?x?0,j?1,2,?,5?j

C(j) Basis X5 X4 C(j)-Z(j) * Big M X1 X4 C(j)-Z(j) * Big M 10 0 C(i) -M 0 10 5 -5 10 5 1 0 0 0 -5 3 1 -5 3 4 -11 0 1 X3 1 -10 1 1 -9 -1 0 0 X4 0 1 0 0 0 1 0 0 -M X5 1 0 0 0 X1 X2 R. H. S. Ratio 10 15 0 0 2 25 20 0 2 M 3/5 1/5 1/5 1 -2 -1 最优解X＝(2,0,0)；Z=20 两阶段法。

第一阶段：数学模型为 minw?x5?5x1?3x2?x3?x5?10 ???5x1?x2?10x3?x4?15?x?0,j?1,2,?,5?jC(j) Basis X5 X4 C(j)-Z(j) X1 X4 C(j)-Z(j) 第二阶段 C(j) Basis X1 X4 C(j)-Z(j) 最优解X=(2,0,0)；Z=20

minZ?5x1?6x2?7x3C(i) 10 0 0 0 C(i) 1 0 0 X1 [5] -5 -5 1 0 0 10 X1 1 0 0 0 X2 3 1 -3 4 0 -5 X2 4 0 X3 1 -10 -1 -9 0 1 X3 -9 0 X4 0 1 0 0 1 0 0 X4 0 1 0 1 X5 1 0 0 R. H. S. 10 15 2 25 R. H. S. 2 25 Ratio 2 M Ratio 2 M 3/5 1/5 1/5 1 1 3/5 1/5 -11 -1 ?x1?5x2?3x3?15?(2) ?5x1?6x2?10x3?20

?x?x2?x3?5?1?xj?0,j?1,2,3?【解】大M法。数学模型为

minZ?5x1?6x2?7x3?MA1?MA3?x1?5x2?3x3?S1?A1?15??5x1?6x2?10x3?S2?20??x1?x2?x3?A3?5?所有变量非负?

C(j) Basis A1 S2 A3 C(j)-Z(j) C(i) M 0 M 5 X1 1 5 1 5 -6 X2 [5] -6 1 -6 -7 X3 -3 10 1 -7 0 S1 -1 0 0 0 0 S2 0 1 0 0 M A1 1 0 0 0 M A3 0 0 1 0 R.H.S. Ratio 15 20 5 3 M 5 * Big M X2 S2 A3 C(j)-Z(j) * Big M X2 S2 X3 -6 0 -7 -6 0 M -2 1/5 31/5 4/5 31/5 -4/5 1/2 3 1/2 -6 1 0 0 0 0 1 0 0 0 2 -3/5 32/5 [8/5] -53/5 -8/5 0 0 1 0 0 1 -1/5 -6/5 1/5 -6/5 -1/5 -1/8 -2 1/8 1/8 0 0 0 1 0 0 0 0 1 0 0 0 0 1/5 6/5 -1/5 6/5 6/5 1/8 2 -1/8 -1/8 1 0 0 0 1 0 0 3/8 -4 5/8 53/8 1 30 5/4 3 38 2 M 95/16 5/4 15/4 C(j)-Z(j) 23/2 0 * Big M 0 两阶段法。 第一阶段：数学模型为 minw?A1?A3?x1?5x2?3x3?S1?A1?15??5x1?6x2?10x3?S2?20 ??x1?x2?x3?A3?5?所有变量非负?C(j) Basis A1 S2 A3 C(j)-Z(j) X2 S2 A3 C(j)-Z(j) X2 S2 X3 C(j)-Z(j) 第二阶段： C(j) Basis X2 S2 X3 C(j)-Z(j) 最优解：X?(0,C(i) -6 0 -7 0 0 0 0 0 1 C(i) 1 0 1 0 X1 1 5 1 -2 1/5 31/5 4/5 -4/5 1/2 3 1/2 0 5 X1 1/2 3 1/2 23/2 0 X2 5 -6 1 -6 1 0 0 0 1 0 0 0 -6 X2 1 0 0 0 0 X3 -3 10 1 2 -3/5 32/5 [8/5] -8/5 0 0 1 0 -7 X3 0 0 1 0 0 S1 -1 0 0 1 -1/5 -6/5 1/5 -1/5 -1/8 -2 1/8 0 0 S1 -1/8 -2 1/8 1/8 0 S2 0 1 0 0 0 1 0 0 0 1 0 0 1 A1 1 0 0 0 1/5 6/5 -1/5 6/5 1/8 2 -1/8 1 0 S2 0 1 0 0 1 A3 0 0 1 0 0 0 1 0 3/8 -4 5/8 1 R.H.S. Ratio 15 20 5 3 M 5 M 95/16 5/4 3 38 2 15/4 30 5/4 R.H.S. Ratio 15/4 3 30 5/4 M 5 155T125,),Z?? 444

maxZ?10x1?15x2?5x1?3x2?9?(3)??5x1?6x2?15??2x1?x2?5?x、x、x?023?1

【解】大M法。数学模型为

maxZ?10x1?15x2?Mx6?5x1?3x2?x3?9???5x1?6x2?x4?15?2x?x2?x5?x6?5?1?xj?0,j?1,2,?,6?

C(j) Basis C(i) X3 X4 X6 0 0 -M 10 X1 [5] -5 2 10 2 1 0 0 0 15 X2 3 6 1 15 1 3/5 9 -1/5 9 0 X3 1 0 0 0 0 0 X4 0 1 0 0 0 0 1 0 0 0 0 X5 0 0 -1 0 -1 0 0 -1 0 -1 -M X6 0 0 1 0 0 0 0 1 0 0 R. H. S. Ratio 9 15 5 0 0 9/5 24 7/5 18 0 1.8 M 2.5 C(j)-Z(j) * Big M X1 X4 X6 10 0 -M C(j)-Z(j) * Big M 0 -1/5 因为X6>0,原问题无可行解。 两阶段法

第一阶段：数学模型为

minZ?x61/5 1 -2/5 -2 -2/5 ?5x1?3x2?x3?9???5x1?6x2?x4?15 ?2x?x2?x5?x6?5?1?xj?0,j?1,2,?,6?C(j) Basis C(i) X3 X4 X6 X1 X4 0 0 1 0 0 0 X1 [5] -5 2 -2 1 0 0 X2 3 6 1 -1 3/5 9 0 X3 1 0 0 0 0 X4 0 1 0 0 0 1 0 X5 0 0 -1 1 0 0 1 X6 0 0 1 0 0 0 R. H. S. Ratio 9 15 5 5 9/5 24 1.8 M 2.5 14 C(j)-Z(j) 1/5 1 X6 1 0 -1/5 -2/5 0 0 -1 1 1 0 7/5 C(j)-Z(j) 0 1/5 2/5 因为X6>0,原问题无可行解。图解法如下：

maxZ?4x1?2x2?5x3?6x1?x2?4x3?10? (4) ?3x1?3x2?5x3?8?x?2x2?x3?20?1?xj?0,j?1,2,3?

【解】大M法。X7是人工变量，数学模型为

maxZ?4x1?2x2?5x3?Mx7?6x1?x2?4x3?x4?10? ?3x1?3x2?5x3?x5?8?x?2x2?2x3?x6?x7?20?1?xj?0,j?1,2,?,7?Cj CB 0 0 XB X4 X5 4 X1 2 X2 5 X3 0 X4 0 X5 0 X6 －M X7 R.H.S. Ratio 10 6 3 1 4 M -1 -3 [2] 2 2M 4 -5 1 5 M 1 －M X7 C(j)-Z(j) * Big M 1 －1 1 －1 10 8 20 0 0 2 X4 13/2 X5 X2 9/2 1/2 3 C(j)-Z(j) * Big M 5 0 2 X3 13/9 X5 86/9 X2 -2/9 -25/9 C(j)-Z(j) * Big M 1 1 [9/2] -7/2 1/2 4 1 1 2/9 7/9 -1/9 -8/9 1 1 -1/2 -3/2 -1/2 1 1/2 3/2 1/2 -1 -1 1/9 4/9 -1 20 38 10 -1/9 -4/9 40/9 70/9 -17/9 17/9 482/9 13/9 -13/9 无界解。 两阶段法。第一阶段： minZ?x7?6x1?x2?4x3?x4?10? ?3x1?3x2?5x3?x5?8?x?2x2?x3?x6?x7?20?1?xj?0,j?1,2,?,7?Cj CB 0 0 1 XB X4 X5 X7 X1 X2 X3 0 X4 0 X5 0 X6 1 X7 R.H.S. Ratio 10 6 3 1 －1 13/2 9/2 1/2 -1 -3 [2] 4 -5 1 C(j)-Z(j) 0 0 2 X4 X5 X2 1 －2 －1 C(j)-Z(j) 1 [9/2] -7/2 1/2 1 1 1 －1 1 -1/2 -3/2 -1/2 1 1/2 3/2 1/2 1 10 8 20 20 38 10 第二阶段： Cj CB 0 0 1 XB X4 X5 X2 4 X1 2 X2 5 X3 0 X4 0 X5 0 X6 R.H.S. Ratio 13/2 9/2 1/2 C(j)-Z(j) 0 0 2 X3 X5 X2 C(j)-Z(j) 7/2 13/9 86/9 -2/9 -3 1 1 [9/2] -7/2 1/2 1 9/2 1 2/9 7/9 -1/9 -1 1 1 -1/2 -3/2 -1/2 20 38 10 1/2 -1/9 40/9 -17/9 482/9 -4/9 70/9 1 原问题无界解。

?21.13 在第1.9题中，对于基B???41??,求所有变量的检验数?j(j?1,?,4),并判断B是不0?是最优基．

??0???1??1?4??, 1??2???1【解】B??4,B?1??C?CBBA??0?(5,2,0,0)?(5,0)??1???(5,2,0,0)?(5,?51?4??2??1??4?2??3?2100?? 1?595,0,)?(0,,0,?)2424??(0,92,0,?54), B不是最优基，可以证明B是可行基。

1.14已知线性规划

maxz?5x1?8x2?7x3?4x4?2x1?3x2?3x3?2x4?20??3x1?5x2?4x3?2x4?30?x?0,j?1,?,4?j

?2的最优基为B???23??，试用矩阵公式求（1）最优解；(2)单纯形乘子；5?(3)N1及N3；(4)?1和?3。 【解】

?5?4????1?2??3?4??,CB?(c4,c2)?(4,8,),则 1??2?T?1B?1(1)XB?(x4,x2)?Bb?(,5),最优解X?(0,5,0,),Z?50

225T5T(2)??CBB(3)

?1?(1,1)

?5?4?1N1?BP1????1??2?5?4?1N3?BP3????1?2??3??1?4??2??4???????1??3??1??2???2??3??3?4??3??4???????1??4??1???2??2??

?(4)

?1??4??1?c1?CBN1?5?(4,8)???5?5?0?1???2???3??4??3?c3?CBN3?7?(4,8)???7?7?0?1???2??

注：该题有多重解：

X(1)=(0，5，0，5/2)

X(2)=(0，10/3，10/3，0)

X(3)=(10，0，0，0)，x2是基变量，X(3)是退化基本可行解 Z＝50

1.15 已知某线性规划的单纯形表1－28, 求价值系数向量C及目标函数值Z．

表1－28 Cj CB 3 4 0 λj ic1 XB x4 x1 x6 x1 0 1 0 0 c2 x2 1 0 －1 －1 c3 x3 2 －1 4 －1 c4 x4 1 0 0 0 c5 x5 －3 2 －4 1 c6 x6 0 0 1 0 c7 x7 2 －1 2 －2 b 4 0 3/2 【解】由?j?cj??ciaij有cj??j??ciaij

ic2＝－1＋（3×1＋4×0＋0×（－1））＝2 c3＝－1＋（3×2＋4×（－1）＋0×4）＝1 c5＝1＋（3×（－3）＋4×2＋0×（－4））＝0 则λ＝(4,2,1,3,0,0,0,)，Z=CBXB=12

1.16 已知线性规划

maxZ?c1x1?c2x2?c3x3

?a11x1?a12x2?a13x3?b1??a21x1?a22x2?a23x3?b2 ?x,x,x?0?123的最优单纯形表如表1－29所示，求原线性规划矩阵C、A、及b，最优基B及B?1．

Cj CB c1 c2 λj XB x1 x2 c1 x1 1 0 0 c2 x2 0 1 0 表1－29 c3 x3 4 －3 －1 c4 x4 1/6 0 －2 c5 x5 1/15 1/5 －3 b 6 2 1??1?615??6?2??1【解】B???，c4＝c5＝0， ?,B??5?1??0?0?5???仿照第15题方法可求出c1＝12，c2＝11，c3＝14

由 A?B?1A 得 A?BA??由 b?B?1b 得 b?Bb???6?0?2??6??32?????? ?5??2?10???6?0?2530??32??6b?,，B??????15??10??0?6?0?2??1??5??04?????1??3?06?025??30? ?154?)?,则有 C?(12,11,1A?2??1?,B5??1?6???0??1?15?? 1?5??1.17 已知线性规划的单纯形表1－30．

表1－30

Cj CB －1 －1 λj XB x3 x4 －3 x1 －2 3 a x2 2 1 －1 x3 1 0 －1 x4 0 1 b b1 b2 λ2 λ3 λ4 λ1 当b1=（ ）,b2=（ ）,a=（ ）时，X＝(0,0,b1,b2)为唯一最优解. 当b1=（ ）,b2=（ ）,a=（ ）时，有多重解，此时λ＝（ ）

【解】(1)b1≥0,b2≥0,a<-3

(2)b1≥0,b2≥0,a=－3, λ＝(－2,0,0,0)

?a11x1?a12x2?a13x3?b1??a21x1?a22x2?a23x3?b2 ?x,x,x?0?123的最优单纯形表如表1－29所示，求原线性规划矩阵C、A、及b，最优基B及B?1．

Cj CB c1 c2 λj XB x1 x2 c1 x1 1 0 0 c2 x2 0 1 0 表1－29 c3 x3 4 －3 －1 c4 x4 1/6 0 －2 c5 x5 1/15 1/5 －3 b 6 2 1??1?615??6?2??1【解】B???，c4＝c5＝0， ?,B??5?1??0?0?5???仿照第15题方法可求出c1＝12，c2＝11，c3＝14

由 A?B?1A 得 A?BA??由 b?B?1b 得 b?Bb???6?0?2??6??32?????? ?5??2?10???6?0?2530??32??6b?,，B??????15??10??0?6?0?2??1??5??04?????1??3?06?025??30? ?154?)?,则有 C?(12,11,1A?2??1?,B5??1?6???0??1?15?? 1?5??1.17 已知线性规划的单纯形表1－30．

表1－30

Cj CB －1 －1 λj XB x3 x4 －3 x1 －2 3 a x2 2 1 －1 x3 1 0 －1 x4 0 1 b b1 b2 λ2 λ3 λ4 λ1 当b1=（ ）,b2=（ ）,a=（ ）时，X＝(0,0,b1,b2)为唯一最优解. 当b1=（ ）,b2=（ ）,a=（ ）时，有多重解，此时λ＝（ ）

【解】(1)b1≥0,b2≥0,a<-3

(2)b1≥0,b2≥0,a=－3, λ＝(－2,0,0,0)

本文来源：https://www.bwwdw.com/article/mqaa.html