运筹学课后练习答案（熊伟第二版，前五章）

教材习题答案

第1章 线性规划

第2章 线性规划的对偶理论 第3章 整数规划 第4章 目标规划 第5章 运输与指派问题 第6章 网络模型 第7章 网络计划 第8章 动态规划 第9章 排队论 第10章 存储论 第11章 决策论 第12章 对策论

目录

教材习题答案................................................................................................................... 1

习题一 ...................................................................................................................... 1 习题二 .................................................................................................................... 29

习题三 .................................................................................................................... 40 习题四 .................................................................................................................... 42 习题五 .................................................................................................................... 47

由于篇幅的限制，本文档只有运筹学第一章---第五章的内容，后七章的内容请继续搜索“运筹学课后练习答案（熊伟第二版，后七章）”

习题一

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－22所示．

表1－22

产品 资源 材料(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－23所示：

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

3 4 600 0.4 0.8

14minZ??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 ?x?x?2x?x?3x?2x?x?400?3689111213?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 A、B两种产品，都需要经过前后两道工序加工，每一个单位产品A需要前道工序1小时和后道工序2小时，每一个单位产品B需要前道工序2小时和后道工序3小时．可供利用的前道工序有11小时，后道工序有17小时．

每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要任何费用，产品C一部分可出售赢利，其余的只能加以销毁．

出售单位产品A、B、C的利润分别为3、7、2元，每单位产品C的销毁费为1元．预测表明，产品C最多只能售出13个单位．试建立总利润最大的生产计划数学模型．

【解】设x1,x2分别为产品A、B的产量，x3为副产品C的销售量,x4为副产品C的销毁量，有x3+x4=2x2,Z为总利润，则数学模型为

maxZ=3x1+7x2+2x3?x4?x1?2x2?11?2x?3x2?17?1???2x2?x3?x4?0?x?13?3??xj?0,j?1,2,?,4

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 IV发展公司是商务房地产开发项目的投资商．公司有机会在三个建设项目中投资：高层办公楼、宾馆及购物中心，各项目不同年份所需资金和净现值见表1－24．三个项目的投资方案是：投资公司现在预付项目所需资金的百分比数，那么以后三年每年必须按此比例追加项目所需资金，也获得同样比例的净现值．例如，公司按10％投资项目1，现在必须支付400万，今后三年分别投入600万、900万和100万，获得净现值450万．

公司目前和预计今后三年可用于三个项目的投资金额是：现有2500万，一年后2000万，两年后2000万，三年后1500万．当年没有用完的资金可以转入下一年继续使用．

IV公司管理层希望设计一个组合投资方案，在每个项目中投资多少百分比，使其投资获得的净现值最大．

表1－24

年份 0 1 2 3 净现值 项目1 400 600 900 100 450 10％项目所需资金（万元） 项目2 项目3 800 800 800 700 700 900 500 200 600 500 【解】以1％为单位，计算累计投资比例和可用累计投资额，见表（2）。 表（2）

年份 0 1 2

每种活动单位资源使用量（每个百分点投资的累计数） 项目1 40 100 190 项目2 80 160 240 项目3 90 140 160 累计可用资金(万元) 2500 4500 6500

3 净现值 200 45 310 70 220 50 8000 设xj为j项目投资比例，则数学模型： maxZ?45x1?70x2?50x3?40x1?80x2?900x3?2500??100x1?160x2?140x3?4500 ??190x1?240x2?160x3?6500?200x?310x?220x?8000123???xj?0,j?1,2,3最优解X＝（0，16.5049，13.1067）；Z=1810.68万元

实际投资 年份 0 1 2 3 净现值 项目2比例：项目3比例：项目1比例：0 16.5049 13.1067 0 0 0 0 0 1320.392 2640.784 3961.176 5116.519 1155.343 1179.603 1834.938 2097.072 2883.474 655.335 累计投资(万元) 2499.995 4475.722 6058.248 7999.993

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

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

x?3x??1?12?x,x?02?1【解】最优解X＝（1/2，1/2）；最优值Z=－1/2

minZ??x1?3x2?2x1?x2??2(2) ?

2x?3x?12?12?x?0,x?02?1【解】最优解X＝（3/4，7/2）；最优值Z=－45/4

minZ??3x1?2x2?x1?2x2?11??x1?4x2?10 (3)???2x1?x2?7?x?3x?12?1??x1,x2?0

【解】最优解X＝（4，1）；最优值Z=－10

maxZ?x1?x2?3x1?8x2?12?(4) ?x1?x2?2

??2x1?3?x,x?0?12【解】最优解X＝（3/2，1/4）；最优值Z=7/4

minZ?x1?2x2?x1?x2?2?(5) ?x1?3??x2?6?x,x?0?12【解】最优解X＝（3，0）；最优值Z=3

maxZ?x1?2x2?x1?x2?2?(6) ?x1?3??x2?6?x,x?0?12

【解】无界解。

minZ?2x?5x?x1?2x2?6 (7)??x1?x2?2?x,x?0?12【解】无可行解。

maxZ?2.5x1?2x2?2x1?x2?8?(8) ?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?'''?10x?3x?6x?6x?x6?51233??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?x1

maxZ?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)?

?2x1?3x2?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 11.25 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 -0.125 2.5 -0.5 5.5 1.375 1.125 -0.5 [0.6875] 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 0.25 0.25 -0.75 -0.75 0.4375 0.25 -0.0938 -0.5625 0 X5 0.5909 0.1818 -0.1364 -0.5625 T0 X6 0 0 1 0 0 0 1 0 -0.25 0 0.125 -0.25 0 X6 -0.4545 0.0909 0.1818 -0.25 374R. H. S. 4 12 10 0 7 3 1 9 6.75 3 0.125 9.25 Ratio M 3 3.3333 3.5 M 0.125 6 M 0.181818 C(j)-Z(j) 0 0 0 X3进基、X2出基，得到另一个基本最优解。 Basis X4 X1 X3 C(j) 3 X1 0 1 0 0 182742 X2 -1.6 0.73 1.45 0 -0.125 X3 0 0 1 0 (2) 0 3 -0.125 R. H. S. 6.5455 3.0909 0.1818 9.25 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

minZ??2x1?x2?4x3?x4?x1?2x2?x3?3x4?8? (4) ??x2?x3?2x4?10

?2x?7x2?5x3?10x4?20?1?xj?0,j?1,?,4?【解】单纯形表： C(j) X5 X6 X7 X3 X6 X7 X3 X4 X7 X1 X4 X7 0 0 0 -4 0 0 -4 1 0 -2 1 0 -2 1 0 2 -2 1 -1 7 2 [2/5] -1/5 2 -1/5 1 0 0 -1 X2 2 -1 7 -1 2 -3 17 7 1/5 -3/5 2 -4 X3 [1] 1 -5 -4 1 0 0 0 1 0 0 0 5/2 1 X4 -3 2 -10 1 -3 [5] -25 -11 0 1 0 0 0 1 0 0 X5 1 0 0 0 1 -1 5 4 0 X6 0 1 0 0 0 1 0 0 0 X7 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 Basis C(i) X1 R. H. S. Ratio 8 10 20 8 10 M M 0.4 M 23 M 35 C(j)-Z(j) 8 2 60 C(j)-Z(j) 46/5 2/5 70 23 5 24 C(j)-Z(j) 2/5 1/2 -1/2 1 2/5 -1/5 0 9/5 1 0 -2 3/5 1/5 5 11/5 3/2 C(j)-Z(j) 0 1/2 0 2 最优解：X=（23，0，0，5，0，0，24）；最优值Z＝－41

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

8x?6x?3x?24?123?x?0,j?1,2,3?j【解】单纯形表： 1/2 -5 1/2 1/2 2 5/2 C(j) Basis X4 X5 C(j)-Z(j)

3 C(i) 0 0 X1 5 [8] 3 2 X2 4 6 2 1 X3 6 3 1 0 X4 1 0 0 0 X5 0 1 0 R. H. S. 25 24 0 Ratio 5 3

X4 0 0 0.25 4.125 0.375 -0.125 1 0 0 -0.625 0.125 -0.375 10 3 9 X1 3 1 0.75 C(j)-Z(j) 0 -0.25 最优解：X=（3，0，0，9，0）；最优值Z＝9

maxZ?5x1?6x2?8x3?x1?3x2?2x3?50 (6)??x1?4x2?3x3?80?x?0,x?0,x?023?1【解】单纯形表：

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

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

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

?5x?x?10x?15?123?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

10 C(i) -M 0 5 -5 10 5 10 0 1 0 -5 3 1 -5 3 4 1 X3 1 -10 1 1 -9 0 X4 0 1 0 0 0 1 -M X5 1 0 0 0 X1 X2 R. H. S. Ratio 10 15 0 0 2 25 2 M 3/5 1/5 1/5 1

C(j)-Z(j) * Big M 最优解X＝(2,0,0)；Z=20 两阶段法。

第一阶段：数学模型为 minw?x50 0 -11 0 -1 0 0 0 -2 -1 20 0 ?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

5 C(i) M 0 X1 1 5 -6 X2 [5] -6 -7 X3 -3 10 0 S1 -1 0 0 S2 0 1 M A1 1 0 M A3 0 0 R.H.S. Ratio 15 20 3 M

A3 M 1 5 -2 1/5 31/5 4/5 31/5 -4/5 1/2 3 1/2 1 -6 -6 1 0 0 0 0 1 0 0 0 1 -7 2 -3/5 32/5 [8/5] -53/5 -8/5 0 0 1 0 0 0 0 1 -1/5 -6/5 1/5 -6/5 -1/5 -1/8 -2 1/8 1/8 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1/5 6/5 -1/5 6/5 6/5 1/8 2 -1/8 -1/8 1 1 0 0 0 0 1 0 0 3/8 -4 5/8 53/8 1 5 3 38 2 5 C(j)-Z(j) * Big M X2 S2 A3 C(j)-Z(j) * Big M X2 S2 X3 -6 0 -7 -6 0 M M 95/16 5/4 15/4 30 5/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)

0 C(i) 1 0 1 0 0 1 0 0 0 X1 1 5 1 -2 1/5 31/5 4/5 -0.8 1/2 3 1/2 0 5 C(i) -6 0 -7 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] -1.6 0 0 1 0 -7 X3 0 0 1 0 0 S1 -1 0 0 1 -1/5 -6/5 1/5 -0.2 -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 1.2 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

最优解：X=(0，3.75，1.25)；Z=－31.25 即 X?(0,

maxZ?10x1?15x2?5x1?3x2?9?(3)??5x1?6x2?15??2x1?x2?5?x、x、x?023?1155T125 ,),Z??444

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

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

C(j) Basis C(i) X4 X5 X7 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 X4 1 0 0 0 0 0 X5 0 1 0 0 0 0 1 0 0 0 0 X6 0 0 -1 0 -1 0 0 -1 0 -1 -M X7 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 X5 X7 10 0 -M C(j)-Z(j) * Big M 0 -1/5 因为X7>0,原问题无可行解。 两阶段法

第一阶段：数学模型为

minZ?x71/5 1 -2/5 -2 -2/5 ?5x1?3x2?x4?9???5x1?6x2?x5?15 ?2x?x2?x6?x7?5?1?xj?0,j?1,2,?,7?C(j) Basis C(i) X4 X5 X7 X1

0 X1 [5] -5 2 -2 1 0 0 1 0 0 X2 3 6 1 -1 3/5 0 X4 1 0 0 0 0 X5 0 1 0 0 0 0 X6 0 0 -1 1 0 1 X7 0 0 1 0 0 R. H. S. Ratio 9 15 5 5 9/5 1.8 M 2.5 14 C(j)-Z(j) 1/5

X5 X7 0 1 0 0 9 -1/5 1 -2/5 1 0 0 0 -1 1 0 1 0 24 7/5 C(j)-Z(j) 0 1/5 2/5 因为X7>0,原问题无可行解。图解法如下：

maxZ?2x1?3x2?x3?x4?x1?x2?2x3?x4?9?2x2?x3?x4?5 (4) ? ???2x1?x2?3x3?x4??1?x?x?33?1??xj?0,j?1,?,4【解】大M法。数学模型为

maxZ?2x1?3x2?x3?x4?Mx9?Mx10?Mx11?x1?x2?2x3?x4?x5?x9?9?2x2?x3?x4?x6?5???2x1?x2?3x3?x4?x7?x10?1?x?x3?x8?x11?3?1??xj?0,j?1,2,?,11C(j) Basis C(i) X9 X6

-M 2 X1 1 3 X2 -1 2 -1 X3 2 1 1 X4 1 -1 X5 -1 X6 1 X7 X8 -M X9 1

-M X10 -M X11 R.H.S. 9 5 Ratio 4.5 5

X10 X11 -M -M 2 1 2 4 -1/3 -1 3 -2 -1/3 [3] 1 -1 6 -1 1 -1 -1 -1 -3/5 -0.4 -1/5 1/5 0.4 1/5 -0.5 -1.5 0.5 -1 1 1 1 -1 -1 2/3 1/3 -1/3 1/3 -1/3 1 0.4 3/5 -1/5 1/5 -3/5 1/5 0.5 -0.5 0.5 -2 -1 -1 -1 -1 -1 -1 -0.5 [5.5] -1 -2.5 7 1 3/5 0.4 1/5 -1/5 -0.4 -1.2 0.5 1.5 -0.5 1 -1 1 -2/3 -1/3 1/3 -1/3 1/3 -2 -0.4 -3/5 1/5 -1/5 3/5 -1.2 -0.5 0.5 -0.5 2 -1 1 1 1 0.5 -5.5 1 2.5 -7 -1 1 3 8.33 4.67 1/3 2.67 -1/3 5 8 2 1 3 5.5 2.5 3 2.5 10 5.73 0.3333 3 5 M M 8 M 3.6364 M 2.5 M 0.4545 M M M M 7.6 M M M M M C(j)-Z(j) * Big M X9 X6 X3 X11 -M [1.67] 1 1 1 1.00 3/5 1.2 2.2 0.8 -8.4 -2/3 -1/3 1/3 2/3 2 1 1 -2/3 2.33 -1 -M 2/3 1/3 -1/3 1/3 C(j)-Z(j) * Big M X4 X6 X3 X11 1 2.67 2.67 -1/5 -1/5 2.2 -0.4 0.4 [2.8] 0.4 1 -0.8 -1 -M 3/5 0.4 2.8 0.4 -3 1 1 -0.27 C(j)-Z(j) * Big M X4 X6 X3 X2 1 -1 3 C(j)-Z(j) * Big M X4 X8 X3 X2 1 1.00 -0.64 0.09 0.45 1 0.64 -0.45 -0.55 -1 3 [0.45] -0.27 0.18 -0.09 1.00 0.27 0.09 -1.00 0.45 -0.27 0.18 -0.09 -0.18 0.45 0.27 0.91 -1.27 -1.36 -0.8 -3/5 -3/5 -0.4 3.2 1/5 0.4 0.4 3/5 -2.8 0.4 -1/5 -1/5 1/5 -3/5 1 0.27 0.09 0.18 -0.27 -0.91 1.36 -1 0.8 3/5 3/5 0.4 -3.2 -1 -1 -0.4 1/5 1/5 -1/5 3/5 -1 -1 -1 -1 3.45 3.64 13.18 7.8 4.6 7.6 6.4 42.2 -0.36 1.00 3.82 1 1 C(j)-Z(j) * Big M X4 X8 X1 X2 1 2 3 C(j)-Z(j) * Big M 无界解。 两阶段法。第一阶段： C(j) Basis C(i) X9 X6 X10 X11 1 1 1 X1 1 2 1 X2 -1 2 -1 X3 2 1 X4 1 -1 -1 X5 -1 X6 1 X7 -1 X8 -1 1 X9 1 1 X10 1 1 X11 1 R.H.S. 9 5 1 3 Ratio 9/2 5 1/3 3 [3] 1

C(j)-Z(j) X9 X6 X3 X11 1 1 -4 -1/3 -2/3 2/3 1/3 -1/5 -4/5 3/5 2/5 -2/5 -3 1 1 2 X1 -3 1 1 -3/11 -6/11 5/11 -4/11 42/11 1 2 -1/3 7/3 -1/3 1/3 -1/5 11/5 -2/5 [2/5] -2/5 1 3 X2 1 1 1 -6 1 1 1 -1 X3 1 1 3/5 6/5 11/5 4/5 -42/5 [5/3] -2/3 -1/3 1/3 -2 1 1 1 X4 1 1 1 1 -1 1 -3/5 -2/5 -1/5 1/5 -1/5 -1/2 -3/2 1/2 X5 -1/2 -3/2 1/2 -1 1 1 1 X6 1 1 2/3 1/3 -1/3 1/3 -1 2/5 3/5 -1/5 1/5 -1/5 1/2 -1/2 1/2 X7 1/2 -1/2 1/2 -2 1 -1 1 -1 1 -1/2 11/2 -1 -5/2 X8 -1/2 [11/2] -1 -5/2 7 1 3/5 2/5 1/5 -1/5 6/5 1/2 3/2 -1/2 1 -2/3 -1/3 1/3 -1/3 2 -2/5 -3/5 1/5 -1/5 6/5 -1/2 1/2 -1/2 1 1 1 1/2 -11/2 1 5/2 1 13 25/3 14/3 1/3 8/3 11 5 8 2 1 1 11/2 5/2 3 5/2 5 M M 8 M 40/11 M 5/2 M 5/11 M M C(j)-Z(j) X4 X6 X3 X11 1 C(j)-Z(j) X4 X6 X3 X2 C(j)-Z(j) 第二阶段： C(j) Basis C(i) X4 X6 X3 X2 1 -1 3 R.H.S. Ratio 11/2 5/2 3 5/2 10 M 5/11 M M M M C(j)-Z(j) X4 X8 X3 X2 1 -1 3 -7/11 1/11 5/11 -3/11 2/11 -1/11 -3/11 2/11 -1/11 -2/11 5/11 3/11 1 -4/5 -3/5 -3/5 -2/5 16/5 -14/11 -15/11 1/5 2/5 2/5 3/5 -14/5 2/5 -1/5 -1/5 1/5 -3/5 63/11 1 5/11 38/11 38/5 40/11 13.18 1 39/5 23/5 38/5 32/5 42.2 M M M M M C(j)-Z(j) X4 X8 X1 X2 1 2 3 C(j)-Z(j) 原问题无界解。

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

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

1.14已知线性规划

maxz?5x1?8x2?7x3?4x4?2x?1?3x2?3x3?2x4?20?3x1?5x2?4x

3?2x4?30??xj?0,j?1,?,4的最优基为B??23???25?，试用矩阵公式求（1）最优解；?(3)N1及N3；(4)?1和?3。 【解】

?5?3?B?1???44?1?,Cc??B?(4,c2)?(4,8,),则 ??1?22??(1)XT?15T5TB?(x4,x2)?Bb?(2,5),最优解X?(0,5,0,2),Z?50

(2)??C?1BB?(1,1)

(3)

?5?3??1?N?1?1?BP44??2??4?1????11????3???1??????22????2???53

???3?N?1P?3?B44??3??4?2????11????5??????1???22????2??(4)

(2)单纯形乘子；

?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－25, 求价值系数向量C及目标函数值Z．

表1－25 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－26所示，求原线性规划矩阵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－26 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

?6得 b?Bb???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－27．

表1－27 Cj CB －1 －1 λj XB x4 －3 x1 3 x3 －2 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)

习题二

1．某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位，C不少于180单位．此人准备每天从六种食物中摄取这三种营养成分．已知六种食物每百克的营养成分含量及食物价格如表2-22所示．（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A，B，C三种营养成分．试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂商能获得最大利益，建立数学模型．

含量 食物 营养成分 A B C 食物单价（元/100g） 一 13 24 18 0.5 二 25 9 7 0.4 表2-22

三 14 30 21 0.8 四 40 25 34 0.9 五 8 12 10 0.3 六 11 15 0 0.2 需要量 ≥80 ≥150 ≥180 【解】（1）设xj为每天第j种食物的用量，数学模型为 minZ?0.5x1?0.4x2?0.8x3?0.9x4?0.3x5?0.2x6?13x1?25x2?14x3?40x4?8x5?11x6?80??24x1?9x2?30x3?25x4?12x5?15x6?150??18x1?7x2?21x3?34x4?10x5?180?x、x、x、x、x、x?023456?1

（2）设yi为第i种单位营养的价格，则数学模型为

maxw?80y1?150y2?180y3?13y1?24y2?18y3?0.5?25y1?9y2?7y3?0.4??14y1?30y2?21y3?0.8??40y1?25y2?34y3?0.9?8y?12y?10y?0.323?1?11y1?15y2??0.5??y1,y2,y3?0

2．写出下列线性规划的对偶问题 max??2x1?4x2minw??y1?4y2??x1?3x2??1??y1?y2??2（1）? 【解】??x1?5x2?4?3y1?5y2?4?x,x?0?y,y?0?12?12

?y1?y2?2?x1?2x2?10?（2）? 【解】?2y1?3y2??1

???x1?3x2?x3?8?y2?3?x,x无约束，x?03?12?y无约束；y?0?12maxZ?x1?2x2?4x3?3x4?10x1?x2?x3?4x4?8?（3）?7x1?6x2?2x3?5x4?10??4x1?8x2?6x3?x4?6?x1,x2?0,x3?0,x4无约束?minw?8y1?10y2?6y3?10y1?7y2?4y3?1?y1?6y2?8y3?2 【解】? ???y1?2y2?6y3?4??4y?5y?y??3123???y1无约束；y2?0,y3?0minZ?2x1?x2?3x3maxw?10y1?8y2maxZ??2x1?3x2?6x3?7x4?3x1?2x2?x3?6x4?9?6x1?5x3?x4?6?（4）???x1?2x2?x3?2x4??2?5?x?101???x1?0,x2,x3,x4无约束maxZ??2x1?3x2?6x3?7x4?3x1?2x2?x3?6x4?9?6x?5x3?x4?6?1 【解】???x1?2x2?x3?2x4??2??x1?5?x?101???x1?0,x2,x3,x4无约束5

minw?9y1?6y2?2y+5y?10y34y??2?3y1?6y2?y3?y?45??2y1?2y2?3?对偶问题为： ? y?5y?y?6?123??6y?y?2y??7123???y1无约束；y2?0，y3,?0，y4?0，x5?03．考虑线性规划

minZ?12x1?20x2?x1?4x2?4??x1?5x2?2??2x1?3x2?7?x,x?0?12

(1)说明原问题与对偶问题都有最优解；

(2)通过解对偶问题由最优表中观察出原问题的最优解； (3)利用公式CBB－1求原问题的最优解； (4)利用互补松弛条件求原问题的最优解． 【解】(1)原问题的对偶问题为

maxw?4y1?2y2?7y3?y1?y2?2y3?12??4y1?5y2?3y3?20?y?0,j?1,2,3?j

容易看出原问题和对偶问题都有可行解，如X＝(2，1)、Y＝(1，0，1)，由定理2.4知都有最优解。

(2)对偶问题最优单纯形表为 C(j) Basis y3 y1 C(i) 7 4 4 y1 0 1 2 y2 -1/5 7/5 7 y3 1 0 0 y4 4/5 -3/5 0 y5 -1/5 R. H. S. 28/5 C(j)-Z(j) w=42.4 对偶问题的最优解Y＝(4/5,0,28/5)，由定理2.6，原问题的最优解为X=(16/5，1/5)，Z＝42.4

?4?5????3??5?1??4?55??, X?(7,4)?2???3?5???5?1?5???(16/5,1/5) 2?5??2/5 0 -11/5 0 -16/5 -1/5 4/5 （3）CB=(7,4),B?1(4)由y1、y3不等于零知原问题第一、三个约束是紧的，解等式

?x1?4x2?4 ?2x?3x?7?12得到原问题的最优解为X=(16/5，1/5)。

4．证明下列线性规划问题无最优解

minZ?x1?2x2?2x3?2x1?x2?2x3?3 ?x?2x?3x?2?123?x,x?0,x无约束3?12证明：首先看到该问题存在可行解，例如x=(2,1,1)，而上述问题的对偶问题为

maxw?3y1?2y2?2y1?y2?1? ?y1?2y2??2???2y1?3y2??2?y?0,y无约束?21由约束条件①②知y1≤0，由约束条件③当y2≥0知y1≥1，对偶问题无可行解，因此原问题也无最优解(无界解)。

5．已知线性规划

maxZ?15x1?20x2?5x3?x1?5x2?x3?5??5x1?6x2?x3?6??3x1?10x2?x3?7?x?0,x?0,x无约束23?1

的最优解X?(,0,41194)，求对偶问题的最优解．

T【解】其对偶问题是：

minw?5y1?6y2?7y3?y1?5y2?3y3?15??5y1?6y2?10y3?20 ??y1?y2?y3?5?y,y,y?0?123由原问题的最优解知，原问题约束①等于零，x1、x2不等于零，则对偶问题的约束①、约束③为等式，y1＝0；解方程

?5y2?3y3?15 ??y2?y3?5得到对偶问题的最优解Y=(5/2,5/2,0)；w＝55/2＝27.5 6．用对偶单纯形法求解下列线性规划

（1）minZ?3x1?4x2?5x3?x1?2x2?3x3?8??2x1?2x2?x3?10?x,x,x?0?123

【解】将模型化为

minZ?3x1?4x2?5x3??x1?2x2?3x3?x4??8 ???2x1?2x2?x3?x5??10?x?0,j?1,2,3,4,5?j对偶单纯形表：

cj CB 0 0 XB X4 X5 C(j)-Z(j) 0 3 X4 X1 C(j)-Z(j)

3 X1 －1 [－2] 3 0 1 0 4 X2 －2 －2 4 [－1] 1 1 5 X3 －3 －1 5 －5/2 1/2 7/2 0 X4 1 0 0 1 0 0 0 X5 0 1 0 －1/2 －1/2 3/2 b －8 －10 0 －3 5 0

5 3 X2 X1 C(j)-Z(j) 0 1 0 1 0 0 5/2 －2 1 －1 1 1 1/2 －1 1 3 2 b列全为非负，最优解为x＝(2，3，0)；Z＝18

（2）minZ?3x1?4x2?x1?x2?4??2x1?x2?2?x?0,x?02?1

【解】将模型化为

minZ?3x1?4x2??x1?x2?x3??4 ?2x?x?x?2?124?x?0,j?1,2,3,4?j XB X3 CB 0 3 X1 [-1] 2 3 1 0 0 1 0 0 4 X2 -1 1 4 1 [-1] 1 0 1 0 0 X3 1 0 0 -1 2 3 1 -2 5 0 X4 0 1 0 0 1 0 1 -1 1 b -4 2 4 -6 -2 6 X4 0 Cj－Zj X1 3 X4 0 Cj－Zj X1 3 X2 4 Cj－Zj (3)出基行系数全部非负，最小比值失效，原问题无可行解。

minZ?2x1?4x2?2x1?3x2?24??x1?2x2?10??x1?3x2?15?x,x?0?12

【解】将模型化为 minZ?2x1?4x2?2x1?3x2?x3?24???x1?2x2?x4??10 ??x?3x2?x5??15?1?xj?0,j?1,2,3,4,5? cj XB

2 CB X1 4 X2 0 X3 0 X4 0 X5 b

X3 X4 0 0 2 -1 -1 2 1 -1/3 1/3 2/3 3 -2 [-3] 4 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 －2/3 －1/3 4/3 24 -10 -15 9 0 5 X5 0 Cj－Zj X3 X4 X2 Cj－Zj

（4）0 0 4 最优解X=(0，5)；Z＝20

minZ?2x1?3x2?5x3?6x4?x1?2x2?3x3?x4?2???2x1?x2?x3?3x4??3?x?0,j?1,?,4?j

【解】将模型化为

minZ?2x1?3x2?5x3?6x4??x1?2x2?3x3?x4?x5??2 ???2x1?x2?x3?3x4?x6??3?x?0,j?1,?,6?jCj XB X5 CB 0 2 X1 -1 -2 2 1/2 -5/2 1/2 [-1] 1 0 1 0 0 1 0 0 3 X2 [-2] 1 3 1 0 0 1 0 0 -1 [1] 0 0 1 0 5 X3 -3 -1 5 3/2 [-5/2] 1/2 0 1 0 0 1 0 1 1 0 6 X4 -4 3 6 2 1 0 13/5 -2/5 1/5 -13/5 11/5 1/5 -2/5 11/5 1/5 0 X5 1 0 0 -1/2 1/2 3/2 -1/5 -1/5 8/5 1/5 -2/5 8/5 -1/5 -2/5 8/5 0 X6 b -2 -3 1 -4 -7/5 8/5 7/5 1/5 8/5 1/5 0 1 0 0 1 0 3/5 -2/5 1/5 -3/5 1/5 1/5 -2/5 1/5 1/5 X6 0 Cj－Zj X2 3 X6 0 Cj－Zj X2 3 X3 5 Cj－Zj X1 2 X3 5 Cj－Zj X1 2 X2 3 Cj－Zj 原问题有多重解：X(1)＝(7/5，0，1/5，)；最优解X(2)＝(8/5，1/5，0)；Z＝19/5 如果第一张表X6出基，则有

Cj XB X5

2 CB 0 X1 -1 3 X2 -2 5 X3 -3 6 X4 -4 0 X5 1 0 X6 b -2 0

X6 0 Cj－Zj X5 0 X1 2 Cj－Zj X2 X1 Cj－Zj

3 2 [-2] 2 0 1 0 0 1 0 1 3 [-5/2] -1/2 2 1 0 0 -1 5 -5/2 1/2 4 1 1 2 3 6 -11/2 -3/2 9 11/5 -7/5 23/5 0 0 1 0 0 -2/5 -1/5 4/5 1 0 -1/2 -1/2 1 1/5 -2/5 3/5 -3 -1/2 3/2 1/5 8/5 7．某工厂利用原材料甲、乙、丙生产产品A、B、C，有关资料见表2-23．

表2-23 材 产品 产材料消耗料 品消原材料 耗材料甲 乙 丙 每件产品利润 A 2 1 2 4 B 1 2 2 1 C 1 3 1 3 每月可供原材料（Kg） 200 500 600 （1）怎样安排生产，使利润最大．

（2）若增加1kg原材料甲，总利润增加多少．

（3）设原材料乙的市场价格为1.2元/Kg，若要转卖原材料乙，工厂应至少叫价多少，为什么？

（4）单位产品利润分别在什么范围内变化时，原生产计划不变．

（5）原材料分别单独在什么范围内波动时，仍只生产A和C两种产品．

（6）由于市场的变化，产品B、C的单件利润变为3元和2元，这时应如何调整生产计划． （7）工厂计划生产新产品D，每件产品D消耗原材料甲、乙、丙分别为2kg，2kg及1kg，每件产品D应获利多少时才有利于投产．

【解】（1）设 x1、x2、x3分别为产品A、B、C的月生产量，数学模型为

maxZ?4x1?x2?3x3?2x1?1x2?x3?200??x1?2x2?3x3?500 ??2x1?x2?x3?600?x?0,x?0,x?023?1最优单纯形表：

C(j) 4 1 X2 1/5 3/5 0 3 X3 0 1 0 0 X4 3/5 -1/5 -1 0 X5 -1/5 2/5 0 0 X6 0 0 1 XB CB X1 X1 4 1 X3 X6 3 0 0 0 R.H.S. 20 160 400 Ratio C(j)-Z(j) 0 -8/5 0 -9/5 -2/5 0 Z=560 最优解X=（20，0，160），Z=560。工厂应生产产品A20件，产品C160种，总利润为560元。

（2）则最优表可知，影子价格为y1?

95,y2?25,y3?0,故增加利润1.8元。

（3）因为y2=0.4，所以叫价应不少于1.6元。 （4）依据最优表计算得

?3??c1?2,?c2?c1?[1,6],c2?(??,855,?1??c3?913

],c3?[2,12]（5）依据最优表计算得

?1003??b1?400,?400??b2?100,?400??b3,600],b2?[100,600],b3?[200,??).

b1?[5003（6）变化后的检验数为λ2=1,λ4=-2,λ5=0。故x2进基x1出基,得到最最优解X=(0,200,0)，即只生产产品B 200件,总利润为600元。 C(j) XB CB X1 X3 X6 X2 X3 X6 X2 X4 X6

?1(7)设产品D的产量为x7, 单件产品利润为c7，只有当?7?c7?CBBP7?0时才有利于投

4 X1 1 0 0 0 5 -3 0 -5 2 -3 0 -2 3 X2 [1/5] 3/5 0 1 1 0 0 0 1 0 0 0 2 X3 0 1 0 0 0 1 0 0 1 1 0 -1 0 X4 3/5 -1/5 -1 -2 3 -2 -1 -5 1 -2 -1 -3 0 X5 -1/5 2/5 0 0 -1 [1] 0 1 0 1 0 0 0 X6 0 0 1 0 0 0 1 0 0 0 1 0 R.H.S. 20 160 400 560 100 100 400 200 100 400 Ratio 100 800/3 M M 100 M 4 2 0 2 3 0 2 0 0 C(j)-Z(j) C(j)-Z(j) C(j)-Z(j) 产。

?2??92???22?1c7?CBBP7?YP7??,,0?2? ??5?55???1??则当单位产品D的利润超过4.4元时才有利于投产。

8．对下列线性规划作参数分析

maxZ?(3?2?)x1?(5??)x2?x1?4?（1）?x2?6??3x1?2x2?18?x,x?0?12

【解】μ＝0时最优解X=(4,3,0)；最优表： C(j) 3 5 0 Basis X1 X2 X5 C(i) 3 5 0 X1 1 0 0 0 3＋2μ X1 1 0 0 X2 0 1 0 0 5－μ X2 0 1 0 X3 1 0 -3 -3 0 X3 1 0 0 X4 0 0.5 -1 -2.5 0 X5 0 0 1 0 0 X4 0 0.5 R. H. S. 4 3 0 27 0 X5 0 0 1 R.H.S. 4 3 0 C(j)-Z(j) 将参数引入到上表： C(j) Basis X1 X2 X5 C(i) 3＋2μ 5－μ 0 C(j)-Z(j) 0 0 0 27 当－3－2μ≤0及-2.5＋0.5μ≤0时最优基不变，有－1.5≤μ≤5。当μ<－1.5时X3进基X1出基；μ>5时X4进基X2出基，用单纯形法计算。参数变化与目标值变化的关系如下表所示。 -3 -1 －3－2μ -2.5＋0.5μ Range 1 2 3 From (Vector) 0 5 0 To 5 M -1.5 From 27 52 27 19.5 To 52 M 19.5 M Slope 5 8 5 -3 Leaving Entering Variable Variable X2 X1 X4 X3 (Vector) OBJ Value OBJ Value 4 -1.5 -M 目标值变化如下图所示。

(μ＝5,Z=52)

(μ＝0,Z=27)

(μ＝-1.5,Z=19.5)

0

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

??3x1?2x2?18?2??x,x?0?12【解】μ＝0时最优解X=(4,3,0)，Z＝27；最优表： C(j) 3 5 0 0 Basis X1 X2 X5 C(j)-Z(j) C(i) 3 5 0 X1 1 0 0 0 X2 0 1 0 0 X3 1 0 -3 -3 X4 0 0.5 -1 -2.5 0 X5 0 0 1 0 R. H. S. 4 3 0 27 ?4??1?????b?b??b???6?0?

??????18?????2??b?B(b??b???)?Bb??Bb????4??1????3?0?????0?????300.5?10??1????00????1?????2???1?1?1

?4??1??????3?0???????0?????5??

替换最优表的右端常数，得到下表。 C(j) Basis X1 X2 C(i) 3 5 3 X1 1 0 5 X2 0 1 0 X3 1 0 0 X4 0 0.5 0 X5 0 0 R.H.S. 4＋μ 3 －5μ X5 0 0 0 [-3] -1 1 C(j)-Z(j) 0 0 -3 -2.5 0 ①μ<－4时问题不可行，－4≤μ<0时最优基不变。μ＝－4时Z＝15。 ②μ>0时X5出基X3进基得到下表： C(j) Basis X1 X2 X3 C(i) 3 5 0 3 X1 1 0 0 5 X2 0 1 0 0 X3 0 0 1 0 0 X4 -1/3 1/2 1/3 -3/2 0 X5 1/3 0 -1/3 -1 R.H.S. 4-2/3μ 3 5μ/3 C(j)-Z(j) 0 0 0≤μ≤6时为最优解。μ＝6时Z＝15。 ③μ>6时X1出基X4进基得到下表： C(j) 3 5 Basis X4 X2 X3 C(i) 0 5 0 X1 -3 3/2 1 X2 0 1 0 0 X3 0 0 1 0 X4 1 0 0 0 X5 -1 1/2 0 R.H.S. -12+2μ 9-μ 4+μ C(j)-Z(j) μ＝9时最优解X=(0，0，13，6，0)，Z=0；μ>9时无可行解。 综合分析如下表所示。 From To From To Leaving Entering Range (Vector) (Vector) OBJ Value OBJ Value Slope Variable Variable 1 0 0 27 27 3 X5 X3 2 0 6 27 15 -2 X1 X2 3 6 9 15 0 -5 X2 4 9 Infinity Infeasible 5 0 -4 27 15 3 X1 6 -4 -Infinity Infeasible 目标值变化如下图所示。

习题三

1．设xj???1,投资j项目?0，不投资j项目

maxZ?30x1?40x2?20x3?15x4?30x5?5x1?4x2?5x3?7x4?8x5?30??x1?7x2?9x3?5x4?6x5?25?8x?2x2?6x3?2x4?9x5?30?1?x＝0或1,j?1,?,5?j

最优解X＝(1,1,1,0,1)，Z=110万元。

2．设xj为投资第j个点的状态，xj=1或0，j=1,2,…,12

maxZ?400x1?500x2?450x3???400x12?900x?1200x?1000x???850x?1000x?90001231112?44771212 ?x?2,x?3,x?1,x?2,x?3,x?4??j?j?j?j?j?jj?1j?1j?5j?5j?8j?8??x?1或0，j?1,?,12?j最优解：x1＝x5=x12=0，其余xj=1,总收益Z=3870万元，实际完成投资额8920万元。 3．设xj为装载第j件货物的状态，xj=1表示装载第j件货物，xj=0表示不装载第j件货物，有

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