熊伟运筹学（第2版）1-3章参考答案

运筹学（第2版）习题答案1--3

习题一

1.1 讨论下列问题：

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

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

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

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

(5)在单纯形法中，为什么说当?k?0并且aik?0(i?1,2,,m)时线性规划具有无界解。 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.6x?1.2x?140023?1? ?150?x1?250??260?x2?310?120?x3?130???x1,x2,x3?01.3 建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格

及数量如表1－24所示：

表1－24 窗架所需材料规格及数量 每套窗架需要材料 需要量（套） 200 型号A 长度数量(根) （m） A1：1.7 2 A2：1.3 3 型号B 长度(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 0 0 2 0 0 1 0 0 0 300 450 400 A2:1.3m 0 1 1 2 0 0 1 0 1 3 0 2 3 4 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）用料最少数学模型为

0.4 0.8 minZ??xjj?114?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?60047910121314?23??xj?0,j?1,2,,14用单纯形法求解得到两个基本最优解

X(1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 X(2)=( 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 ?x?x?2x?x?3x?2x?x?400?3689111213?x?x?2x?x?x?3x?2x?3x?4x?60047910121314?23??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根 X(2)=( 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?x1?y1?x2?y2?x3?800??x1?y1?x2?y2?x3?y3?x4?800?x?y?x?y?x?y?x?y?x?800233445?112?x1?y1?x2?y2?x3?y3?x4?y4?x5?y5?x6?800（1）???x1?y1?200??x?y?x?y?2002?112??x1?y1?x2?y2?x3?y3?200???x1?y1?x2?y2?x3?y3?x4?y4?200??x1?y1?x2?y2?x3?y3?x4?y4?x5?y5?200???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年 第3年 数学模型为

项目一 x11 x21 x31 项目二 x12 项目三 x23 项目四 x34 maxZ?0.2x11?0.2x21?0.2x31?0.5x12?0.6x23?0.3x34?x11?x12?30000???1.2x11?x21?x23?30000??1.5x12?1.2x21?x31?x34?30000???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 ≤1 航空煤油 轻油、裂化油、重油、残油 一般煤油 轻油、裂化油、重油、残油按10:4:3: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)80x21?115x22?105x23?94,84??94

x11?x12?x13x21?x22?x23航空煤油蒸气压约束

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

x34?x35?x36＋x37一般煤油比例约束

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

即

x4410x454x463?,?,? x454x463x471半成品油供应量约束

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??4x21?31x22?21x23?0??0.5x35?0.4x36?0.95x37?0?4x?10x?045?44?3x45?4x46?0??x46?3x47?0??x11?x21?2000?x?x?1000?1222?x13?x23?1500??x34?x44?1200?x35?x45?1000??x36?x46?1000?x?x?800?3747??xij?0;i?1,2,3,4;j?1,2,,71.7 图解下列线性规划并指出解的形式：

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

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

1.8 将下列线性规划化为标准形式 maxZ?x1?4x2?x3?2x1?x2?3x3?20 (1)?

?5x1?7x2?4x3?3??10x1?3x2?6x3??5??x1?0,x2?0,x3无限制'''【解】（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?1233,x4,x5,x6?0minZ?9x1?3x2?5x3?|6x1?7x2?4x3|?20? (2) ?x1?5 ??x1?8x2??8??x1?0,x2?0,x3?0【解】（2）将绝对值化为两个不等式，则标准形式为

maxZ???9x1?3x2?5x3?6x1?7x2?4x3?x4?20??6x?7x?4x?x?201235? ?x?x?5?16??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?x?x?5 ?14??x1?x2?1??x1,x2,x3,x4?0??x1?1,有x1＝x1??1,x1??5?1?4 方法2：令x1??1)?3x2maxZ?2(x1??4?x1???1)?x2??1??(x1?x,x?0?12则标准型为

??3x2maxZ?2?2x1??x3?4?x1???x2?0??x1?x?,x,x?0?123

maxZ?min(3x1?4x2,x1?x2?x3)?x1?2x2?x3?30?(4) ?4x1?x2?2x3?15

??9x1?x2?6x3??5?x1无约束,x2、x3?0?【解】令y?3x1?4x2,y?x1?x2?x3,x1?x1??x1??，线性规划模型变为

maxZ?y??x1??)?4x2?y?3(x1?y?x??x???x?x1123????x1???2x2?x3?30 ?x1???x1??)?x2?2x3?15?4(x1?9(x1??x1??)?x2?6x3??5??,x1??,x2、x3?0??x1标准型为

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

1.9 设线性规划

maxZ?5x1?2x2?2x1?3x2?x3?50 ?4x?2x?x?60?124?x?0,j?1,?,4?j?21??20?取基B1?(P1，P3)??分别指出B1和B2对应的基变量和非基变量，?、B2＝?41?，40????求出基本解，并说明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 (1)???2x1?x2?2

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

单纯形法： C(j) C(i) 0 0 3 0 3 1 对应的顶点： Basis X3 X4 X2 X4 X2 X1 1 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) 可行域的顶点 、X(1)=（0，0，2，12） 、X(2)=（0，2，0，6，） （0，0） （0，2） 37,,0,0)、 423745最优解X?(,),Z?

424X(3)=（

37(,) 42minZ??3x1?5x2

?x1?2x2?6? (2) ?x1?4x2?10?

?x1?x2?4??x1?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） 、X(2)=（0，2.5，1，0，1.5，） X(3)=（2，2，0，0，0） X(4)=（2，2，0，0，0） 、可行域的顶点 （0，0） （0，2.5） (2，2) （2，2） 最优解：X=（2，2，0，0，0）；最优值Z＝－16 该题是退化基本可行解，5个基本可行解对应4个极点。

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

maxZ?3x1?4x2?x3?2x1?3x2?x3?1(1)??x1?2x2?2x3?3?x?0,j?1,2,3?j【解】单纯形表： 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??2x1?6x2?x3?4x4?20?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 1 0 0 0 11 -1 2 -1/2 3 -1/2 -17 3 7/4 -1/4 1/4 -5/4 5 5 120 10 20 10 M M 10 M 因为λ7＝3>0并且ai7<0(i=1,2,3)，故原问题具有无界解，即无最优解。

maxZ?3x1?2x2?18x3??x1?2x2?3x3?4? (3)?4x1?2x3?12??3x1?8x2?4x3?10??x1,x2,x3?0【解】 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 0 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 0 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 R. 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 Ratio 6 M 0.1818

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 2 X2 -18/11 8/11 16/11 0 -0.125 X3 0 0 1 0 0 3 -0.125 C(j)-Z(j) 原问题具有多重解。 基本最优解X(1)1273427237,最优解的通解可表?(3,,0,,0)及X(2)?(,0,,,0)T;Z?841111114示为X?aX(1)?(1?a)X(2)即

X?(

3411227272?a,a,?a,?a,0)T,(0?a?1) 1111811111111maxZ?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 X1 0 3 C(i) 0 0 3 X1 5 [8] 3 0 1 2 X2 4 6 2 1/4 1 X3 6 3 1 33/8 3/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 C(j)-Z(j) 0 -1/8 最优解：X=（3，0，0，10，0）；最优值Z＝9

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

3/4 -1/4 maxZ?10x1?5x2?x3 (1) ??5x1?3x2?x3?10??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?jC(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 ??5x?x?10x?x?15?1234?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

C(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 minZ?5x1?6x2?7x3?x1?5x2?3x3?15?(2) ?5x1?6x2?10x3?20

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

minZ?5x1?6x2?7x3?MA1?MA3?x1?5x2?3x3?S1?A1?15?5x?6x?10x?S?20?1232??x1?x2?x3?A3?5??所有变量非负C(j) 5 -6 Basis C(i) X1 X2 A1 M 1 [5] S2 0 5 -6 A3 M 1 1 C(j)-Z(j) 5 -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 38 2 3 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?5x?6x?10x?S?20 ?1232??x1?x2?x3?A3?5??所有变量非负C(j) 0 0 0 Basis C(i) X1 X2 X3 A1 1 1 -3 5 S2 0 5 -6 10 A3 1 1 1 1 C(j)-Z(j) -2 -6 2 X2 0 1/5 1 -3/5 S2 0 31/5 0 32/5 A3 1 4/5 0 [8/5] C(j)-Z(j) -4/5 0 -8/5 X2 0 1/2 1 0 S2 0 3 0 0 X3 0 1/2 0 1 C(j)-Z(j) 0 0 0 第二阶段： C(j) Basis X2 S2 X3 C(j)-Z(j) 最优解：X?(0,C(i) -6 0 -7 5 X1 1/2 3 1/2 -6 X2 1 0 0 -7 X3 0 0 1 0 0 S1 -1/8 -2 1/8 1/8 0 S2 0 1 0 0 R.H.S. Ratio 15/4 3 30 5/4 M 5 0 S1 -1 0 0 1 -1/5 -6/5 1/5 -1/5 -1/8 -2 1/8 0 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 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 30 5/4 15/4 23/2 0 155T125,),Z?? 444

?x1?2x2?8?y1M?x1?5?yM??x?5?(1?y)M?x1?2y1?4y2?6y3?8y4?4x1?x2?10?y2M1???【解】(1)?2x1?6x2?18?y3M (2)?x?10?yM(3)?y1?y2?y3?y4?1?2?y?y?y?1?y?0或1，j?1,2,3,4?x?8?(1?y)M1222?j?? ?y?0或1，j?1,2,3??y?0或1?j6．考虑下列数学模型

minZ?f(x1)?g(x2)

其中

?10?6x1,若x1?0?15?10x2,若x2?0 f(x1)??,g(x2)??若x1?0若x2?0?0,?0,满足约束条件 （1）x1≥8或x2≥6 （2）|x1－x2|=0，4或8

（3）x1+2x2≥20、2x1+x2≥20及x1+x2≥20 三个约束中至少一个满足 （4）x1≥0，x2≥0

将此问题归结为混合整数规划的数学模型。

minZ?10y1?6x1?15y2?10x2?x1?y1M;x2?y2M?x?8?yM3?1?x2?6?(1?y3)M??x1?x2?0y4?4y5?4y6?8y7?8y8【解】??y4?y5?y6?y7?y8?1??x1?2x2?20?y9M?2x1?x2?20?y10M??x1?x2?20?y11M?y?y?y?21011?911??x1?0,x2?0;yj?0或1，j?1,2,?，

7．用分枝定界法求解下列IP问题

条件（1）条件（2）条件（3）

条件（4）maxZ?x1?x2（1）?minZ?x1?2x2?3x1?2x2?7??x1?x2?10 （2）?

?10x1?2x2?50?2x1?4x2?5?x,x?0且为整数?x,x?0且为整数?12?12【解】(1)X=(1,2),或X＝（0,3）Z=3 (2) X=(5,0),Z=5

8．用割平面法求解下列IP问题

maxZ?2x1?3x2（1）?minZ?2x1?3x2?x1?2x2?9?x1?2x2?9 （2）?

?2x1?x2?10?2x1?x2?10?x,x?0且为整数?x,x?0且为整数?12?12【解】(1)X=(3,3),Z=15 (2)X=(5,2),Z=16

9．用隐枚举法求解下列BIP问题

??x1?x2?4x3?5x4?3?5x1?2x2?x3?6?（1）? （2）?3x1?x2?2x3?2x4?4

?4x1?2x2?x3?7??x1?3x2?2x3?4x4?7?x?0或1，j?1,2,3?j?xj?0或1，j?1,2,3,4?【解】(1)X=(1,1,1),Z=8 (2)X=(1,1,1,0),Z=4

10．用分枝定界－隐枚举法求解下列BIP问题

maxZ?4x1?3x2＋x3minZ?4x1?x2?x3?3x4maxZ?4x1?x2?x3?3x4??x1?x2?4x3?5x4?8?x1?5x2?x3?2x4?x5?8?3x?x?2x?2x?4（1）?1 （2）?234?2x1?2x2?3x3?2x4?x5?4?x?3x?2x?4x?7234?x?0或1，j?1,?,5?1?j?xj?0或1，j?1,2,3,4?【解】(1)X=(1,0,1,1),Z=8 (2)X=(1,1,0,0,0),Z=－2

minZ??3x1?x2?2x3?6x4?x5

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