熊伟运筹学课后习题答案1-4章

教材习题答案 ................................................................................................... 错误!未定义书签。

习题一 ...................................................................................................................................... 1 习题二 .................................................................................................................................... 27 习题三 .................................................................................................................................... 37 习题四 .................................................................................................................................... 39 习题五 ....................................................................................................... 错误!未定义书签。 习题六 ....................................................................................................... 错误!未定义书签。 习题七 ....................................................................................................... 错误!未定义书签。 习题八 ....................................................................................................... 错误!未定义书签。

部分有图形的答案附在各章PPT文档的后面，请留意。

习题一

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.6x1.2x1400231 150x1250260x2310120x3130x1,x2,x301.3 建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格及数量如表1－

23所示：

1 / 43

表1－23 窗架所需材料规格及数量 每套窗架需要材料 需要量（套） 200 型号A 长度数量(根) （m） A1：1.7 2 A2：1.3 3 型号B 长度(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 A2:1.3m 0 1 1 2 0 0 1 0 1 3 0 余料 0.6 0 0.3 0.7 0 0.3 0.7 0.6 1 0.1 0.9 第二步：建立线性规划数学模型 设xj（j=1,2,…，14）为第j种方案使用原材料的根数，则 （1）用料最少数学模型为

0 0 2 2 0 0 0 1 3 0 0 0 4 300 450 400 600 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 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)=( 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 A、B两种产品，都需要经过前后两道工序加工，每一个单位产品A需要前道工序1小时和后道工序2小时，每一个单位产品B需要前道工序2小时和后道工序3小时．可供利用的前道工序有11小时，后道工序有17小时．

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

出售单位产品A、B、C的利润分别为3、7、2元，每单位产品C的销毁费为1元．预测表明，产品C最多

2 / 43

只能售出13个单位．试建立总利润最大的生产计划数学模型．

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

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

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

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

表1－24 年份 10％项目所需资金（万元） 3 / 43

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

表（2）

年份 0 1 2 3 净现值 每种活动单位资源使用量（每个百分点投资的累计数） 项目1 40 100 190 200 45 项目2 80 160 240 310 70 项目3 90 140 160 220 50 累计可用资金(万元) 2500 4500 6500 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) x13x21x,x012

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

4 / 43

minZx13x2(2) 2x1x222x13x212x0,x021

【解】最优解X＝（3/4，7/2）；最优值Z=－45/4

5 / 43

minZ3x12x2x12x211x4x1012 (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x1,x20【解】最优解X＝（3/2，1/4）；最优值Z=7/4

6 / 43

minZx12x2x1x22(5) x13x26x1,x20【解】最优解X＝（3，0）；最优值Z=3

maxZx12x2x1x22(6) x13x26x1,x20【解】无界解。

7 / 43

minZ2x15x2x12x26 (7)x1x22x,x012【解】无可行解。

8 / 43

maxZ2.5x12x22x1x28(8) 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'''x1,x2,x3,x3,x4,x5,x60minZ9x13x25x3|6x17x24x3|20 (2) x15 x18x28x10,x20,x30【解】（2）将绝对值化为两个不等式，则标准形式为

9 / 43

maxZ9x13x25x36x17x24x3x4206x7x4xx201235 x1x65x8x821x1,x2,x3,x4,x5,x60maxZ2x13x2 (3)1x15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123maxZmin(3x14x2,x1x2x3)x12x2x330(4) 4x1x22x315 9x1x26x35x1无约束,x2、x30x1，线性规划模型变为 【解】令y3x14x2,yx1x2x3,x1x1maxZ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x110 / 43

标准型为

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【解】图解法

11 / 43

单纯形法：

C(j) C(i) 0 0 3 0 3 1 对应的顶点： 基可行解 X(1)=（0，0，2，12） 、X(2)=（0，2，0，6，） 、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,,0,0)、 423745最优解X(,),Z

424X(3)=（

37(,) 4212 / 43

minZ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 对应的顶点： 基可行解 13 / 43 可行域的顶点 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） 最优解：X=（2，2，0，0，0）；最优值Z＝－16

该题是退化基本可行解，5个基本可行解对应4个极点。

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

、（0，0） （0，2.5） (2，2) （2，2） 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(j)-Z(j) X5 X6 X4 0 0 5 C(i) 0 0 0

2 X1 1 3 2 2 9/2 1 X2 5 -1 -6 1 -3 X3 3 [1] -1 -3 5 X4 -7 1 [4] 5 0 0 X5 1 0 0 0 1 0 0 X6 0 1 0 0 0 1 0 X7 0 0 1 0 R. H. S. Ratio 30 10 20 M 10 5 M 65 -11/2 5/4 5/2 1/2 [1/2] 5/4 0 -3/2 -1/4 1 0 0 14 / 43 7/4 -1/4 1/4 5 5 10 M C(j)-Z(j) X5 X2 X4 C(j)-Z(j) 0 1 5 -1/2 17/2 -7/4 0 0 0 1 0 0 0 32 5 8 -43 0 1 0 0 15 5/2 7/2 -23 0 1 0 0 -5/4 11 -1 2 -1/2 3 -1/2 -17 3 120 10 20 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 -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 0 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 0 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 R. 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 Ratio 6 M 0.1818

C(j)-Z(j) 0 0 0 X3进基、X2出基，得到另一个基本最优解。 Basis X4 X1 X3 C(j) 3 X1 0 1 0 0 2 X2 -1.6 0.73 1.45 0 -0.125 X3 0 0 1 0 0 3 -0.125 R. H. S. 6.5455 3.0909 0.1818 9.25 C(j)-Z(j) 原问题具有多重解。 基本最优解X(1)(3,,0,18273427237,最优解的通解可表示为,0)及X(2)(,0,,,0)T;Z41111114XaX(1)(1a)X(2)即

X(

3411227272a,a,a,a,0)T,(0a1) 111181111111115 / 43

minZ2x1x24x3x4x12x2x33x48 (4) x2x32x410

2x17x25x310x420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 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 1 X4 -3 2 -10 1 -3 [5] -25 -11 0 1 0 0 0 1 0 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) C(j)-Z(j) C(j)-Z(j) C(j)-Z(j) 2/5 0 1/2 5/2 -1/2 1/2 1 -5 1/2 1/2 2/5 -1/5 0 9/5 1 0 -2 2 3/5 1/5 5 11/5 3/2 1/2 2 5/2 8 2 60 46/5 2/5 70 23 5 24 最优解：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【解】单纯形表： 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 0.25 0.75 1 X3 6 3 1 4.125 0.375 -0.125 0 X4 1 0 0 1 0 0 0 X5 0 1 0 -0.625 0.125 -0.375 R. H. S. 25 24 0 10 3 9 Ratio 5 3 C(j)-Z(j) 0 -0.25 最优解：X=（3，0，0，9，0）；最优值Z＝9

16 / 43

maxZ5x16x28x3 (6)x13x22x350x14x23x380x0,x0,x0231C(j) 5 C(i) 0 0 8 0 5 0 X1 1 1 5

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

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

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 最优解X＝(2,0,0)；Z=20 两阶段法。

第一阶段：数学模型为

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 17 / 43

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

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 -7 0 Basis C(i) X1 X2 X3 S1 A1 M 1 [5] -3 -1 S2 0 5 -6 10 0 A3 M 1 1 1 0 C(j)-Z(j) 5 -6 -7 0 * Big M -2 -6 2 1 X2 -6 1/5 1 -3/5 -1/5 S2 0 31/5 0 32/5 -6/5 A3 M 4/5 0 [8/5] 1/5 0 S2 0 1 0 0 0 0 1 0 M A1 1 0 0 0 0 1/5 6/5 -1/5 M A3 0 0 1 0 0 0 0 1 R.H.S. Ratio 15 20 5 3 38 2 M 95/16 5/4 3 M 5 18 / 43

C(j)-Z(j) * Big M X2 S2 X3 -6 0 -7 31/5 -4/5 1/2 3 1/2 0 0 1 0 0 0 -53/5 -8/5 0 0 1 0 0 -6/5 -1/5 -1/8 -2 1/8 1/8 0 0 0 0 1 0 0 0 6/5 6/5 1/8 2 -1/8 -1/8 1 0 0 3/8 -4 5/8 53/8 1 30 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 5 -3 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) -0.8 0 -1.6 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) 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 -0.2 -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 1.2 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 最优解：X=(0，3.75，1.25)；Z=－31.25 即 X(0,

155T125 ,),Z444maxZ10x115x25x13x29(3)5x16x2152x1x25x1、x2、x30

19 / 43

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

maxZ10x115x2Mx75x13x2x495x6xx151252x1x2x6x75xj0,j1,2,,715 0 0 0 X2 X4 X5 X6 3 1 0 0 6 0 1 0 1 0 0 -1 15 0 0 0 1 0 0 -1 3/5 0 0 1/5 9 1 1 0 -1/5 -2/5 0 -1 9 -2 0 0 -1/5 -2/5 0 -1

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

第一阶段：数学模型为

minZx75x13x2x495x6xx15 1252x1x2x6x75xj0,j1,2,,70 0 0 0 X2 X4 X5 X6 3 1 0 0 6 0 1 0 1 0 0 -1 -1 0 0 1 3/5 0 0 1/5 9 1 1 0 -1/5 -2/5 0 -1 1/5 2/5 0 1 C(j) Basis C(i) X4 X5 X7 X1 X5 X7 0 0 1 0 0 1 0 X1 [5] -5 2 -2 1 0 0 1 X7 0 0 1 0 0 0 1 0 R. H. S. Ratio 9 15 5 5 9/5 24 7/5 1.8 M 2.5 14 C(j)-Z(j) C(j)-Z(j) 0 因为X7>0,原问题无可行解。图解法如下： 20 / 43

maxZ2x13x2x3x4x1x22x3x492x2x3x45 (4)  2x1x23x3x41xx313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 X10 X11 -M -M -M 2 X1 1 2 1 2 4 3 X2 -1 2 -1 3 -2 -1 X3 2 1 1 X4 1 -1 -1 1 X5 -1 -1 -1 X6 1 X7 -1 -1 2/3 X8 -1 -1 -M X9 1 1 -M X10 1 -2/3

-M X11 1 R.H.S. 9 5 1 3 8.33 Ratio 4.5 5 0.3333 3 5 [3] 1 -1 6 C(j)-Z(j) * Big M X9 -M -1/3 -1/3 [1.67] 21 / 43

X6 X3 X11 -2/3 2.33 -1 -M 2/3 1/3 -1/3 1/3 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 -1 -3/5 -0.4 -1/5 1/5 0.4 1/5 -0.5 -1.5 0.5 -1 1 1 1 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 -0.5 [5.5] -1 -2.5 7 3/5 0.4 1/5 -1/5 -0.4 -1.2 0.5 1.5 -0.5 1 -1 -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 0.5 -5.5 1 2.5 -7 -1 4.67 1/3 2.67 -1/3 5 8 2 1 3 5.5 2.5 3 2.5 10 5.73 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 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 -4 -1/3 -2/3 2/3 1/3 -1/5 X2 -1 2 -1 2 -1/3 7/3 -1/3 1/3 -1/5 X3 2 1 X4 1 -1 -1 [5/3] -2/3 -1/3 1/3 -2 1 X5 -1 1 -1 1 -3/5 X6 1 1 X7 -1 1 2/3 1/3 -1/3 1/3 -1 2/5 X8 -1 1 -1 1 1 X9 1 1 3/5 1 X10 1 -2/3 -1/3 1/3 -1/3 2 -2/5 1 X11 1 1 R.H.S. 9 5 1 3 13 25/3 14/3 1/3 8/3 11 5 Ratio 9/2 5 1/3 3 5 M M 8 M [3] 1 -6 1 C(j)-Z(j) X9 X6 X3 X11 1 1 C(j)-Z(j) X4 22 / 43 X6 X3 X11 1 -4/5 3/5 2/5 -2/5 -3 1 1 2 X1 -3 1 1 -3/11 11/5 -2/5 [2/5] -2/5 1 3 X2 1 1 1 1 1 -1 X3 1 1 3/5 6/5 11/5 4/5 -42/5 1 1 X4 1 1 1 -2/5 -1/5 1/5 -1/5 -1/2 -3/2 1/2 X5 -1/2 -3/2 1/2 -1 1 1 X6 1 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/2 11/2 -1 -5/2 X8 -1/2 [11/2] -1 -5/2 7 2/5 1/5 -1/5 6/5 1/2 3/2 -1/2 1 -3/5 1/5 -1/5 6/5 -1/2 1/2 -1/2 1 1 1/2 -11/2 1 5/2 1 8 2 1 1 11/2 5/2 3 5/2 40/11 M 5/2 M 5/11 M M 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 -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 -6/11 -1 3 5/11 -4/11 42/11 1 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1.13 在第1.9题中，对于基B,求所有变量的检验数j(j1,,4),并判断B是不是最优基．

401041【解】B4,B,

112CCBB1A1042310(5,2,0,0)(5,0) 11420125595(5,2,0,0)(5,,0,)(0,,0,)2424(0,,0,), B不是最优基，可以证明B是可行基。

23 / 43

92541.14已知线性规划

maxz5x18x27x34x42x13x23x32x420 3x5x4x2x301234x0,j1,,4j23的最优基为B，试用矩阵公式求（1）最优解；(2)单纯形乘子；(3)N1及N3；(4)1和3。

25【解】

541B1234,C(c,c)(4,8,),则 B42125252(1)XB(x4,x2)TB1b(,5)T,最优解X(0,5,0,)T,Z50 (2)CBB(3)

1(1,1)

35142441N1BP11131222

35344341N3BP2115122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－25, 求价值系数向量C及目标函数值Z．

表1－25 Cj c1 c2 c3 c4 24 / 43

c5 c6 c7 b CB 3 4 0 λj 【解】由jcjXB x4 x1 x6 x1 0 1 0 0 x2 1 0 －1 －1 x3 2 －1 4 －1 iijx4 1 0 0 0 x5 －3 2 －4 1 x6 0 0 1 0 x7 2 －1 2 －2 4 0 3/2 caiiij有cjjcai

c2＝－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 11621615【解】B，c4＝c5＝0， ,B05105仿照第15题方法可求出c1＝12，c2＝11，c3＝14 由 ABA 得 ABA由 bB1b

1621046230 05013051562632得 bBb210

0511621615623032则有 C(12,11,14),A ,b10，B05,B10515051.17 已知线性规划的单纯形表1－27．

表1－27 Cj CB XB －3 x1 a x2 －1 x3 －1 x4 25 / 43

b －1 －1 λj x3 －2 x4 3 2 1 1 0 0 1 b1 b2 λ1 λ2 λ3 λ4 当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)

26 / 43

习题二

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24x9x30x25x12x15x15012345618x17x221x334x410x5180x1、x2、x3、x4、x5、x60（2）设yi为第i种单位营养的价格，则数学模型为

maxw80y1150y2180y313y124y218y30.525y9y7y0.4123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） 【解】x5x413y15y242x,x0y,y0121227 / 43

y1y22x12x210（2） 【解】2y13y21

x13x2x38y23x,x无约束，x0312y1无约束；y2010y17y24y3110x1x2x34x48y6y8y2123（3）7x16x22x35x410 【解】 y12y26y344x8x6xx62344y5yy31123x1,x20,x30,x4无约束y1无约束；y20,y30maxZ2x13x26x37x43x12x2x36x496x5xx6134（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5xx6341 【解】x12x2x32x42x15x110x10,x2,x3,x4无约束minZ2x1x23x3maxw10y18y2maxZx12x24x33x4minw8y110y26y3

minw9y16y22y3+5y410y53y16y2y3y4y522y2y312对偶问题为：  y5yy61236yy2y7123y1无约束；y20，y3,0，y40，x503．考虑线性规划

minZ12x120x2x14x24x5x2122x13x27x1,x20

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

(2)通过解对偶问题由最优表中观察出原问题的最优解；

－

(3)利用公式CBB1求原问题的最优解； (4)利用互补松弛条件求原问题的最优解． 【解】(1)原问题的对偶问题为

28 / 43

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(j)-Z(j) 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 2/5 0 -11/5 0 -16/5 -1/5 4/5 w=42.4 对偶问题的最优解Y＝(4/5,0,28/5)，由定理2.6，原问题的最优解为X=(16/5，1/5)，Z＝42.4

114455551（3）CB=(7,4),B, X(7,4)(16/5,1/5)

32325555(4)由y1、y3不等于零知原问题第一、三个约束是紧的，解等式

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

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

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

maxw3y12y22y1y21y2y2 122y13y22y20,y1无约束由约束条件①②知y1≤0，由约束条件③当y2≥0知y1≥1，对偶问题无可行解，因此原问题也无最优解(无

界解)。

5．已知线性规划

29 / 43

maxZ15x120x25x3x15x2x355x6xx6 1233x110x2x37x10,x20,x3无约束的最优解X(,0,1419T)，求对偶问题的最优解． 4【解】其对偶问题是：

minw5y16y27y3y15y23y3155y6y10y20 123y1y2y35y1,y2,y30由原问题的最优解知，原问题约束①等于零，x1、x2不等于零，则对偶问题的约束①、约束③为等式，y1＝

0；解方程

5y23y315 yy523得到对偶问题的最优解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 2x2xxx101235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 30 / 43

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 2x1x2x42x0,j1,2,3,4j XB X3 X4 Cj－Zj X1 X4 Cj－Zj X1 X2 Cj－Zj 3 4 3 0 CB 0 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 出基行系数全部非负，最小比值失效，原问题无可行解。

(3)minZ2x14x22x13x224x2x1012x13x215x1,x20

【解】将模型化为

minZ2x14x22x13x2x324x2xx10 124x13x2x515xj0,j1,2,3,4,5 cj XB X3 X4 CB 0 0 2 X1 2 -1 4 X2 3 -2 0 X3 1 0 0 X4 0 1 31 / 43

0 X5 0 0 b 24 -10 X5 Cj－Zj X3 X4 X2 Cj－Zj 0 0 0 4 -1 2 1 -1/3 1/3 2/3 [-3] 4 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 －2/3 －1/3 4/3 -15 9 0 5 最优解X=(0，5)；Z＝20

（4）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 2xxx3xx312346x0,j1,,6jCj XB X5 X6 Cj－Zj X2 X6 Cj－Zj X2 X3 Cj－Zj X1 X3 Cj－Zj X1 X2 Cj－Zj 2 3 2 5 3 5 3 0 CB 0 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 原问题有多重解：X(1)＝(7/5，0，1/5，)；最优解X(2)＝(8/5，1/5，0)；Z＝19/5 如果第一张表X6出基，则有 Cj XB X5 X6 Cj－Zj X5 0 CB 0 0 2 X1 -1 [-2] 2 0 3 X2 -2 1 3 [-5/2] 5 X3 -3 -1 5 -5/2 6 X4 -4 3 6 -11/2 32 / 43

0 X5 1 0 0 1 0 X6 b -2 -3 -1/2 0 1 0 -1/2 X1 Cj－Zj X2 X1 Cj－Zj

2 3 2 1 0 0 1 0 -1/2 2 1 0 0 1/2 4 1 1 2 -3/2 9 11/5 -7/5 23/5 0 0 -2/5 -1/5 4/5 -1/2 1 1/5 -2/5 3/5 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x2x3x500 1232x1x2x3600x10,x20,x30最优单纯形表：

C(j) X1 X3 X6 4 3 0 4 1 0 0 0 1 X2 1/5 3/5 0 -8/5 3 X3 0 1 0 0 0 X4 3/5 -1/5 -1 -9/5 0 X5 -1/5 2/5 0 -2/5 0 X6 0 0 1 0 XB CB X1 R.H.S. 20 160 400 Z=560 Ratio 最优解X=（20，0，160），Z=560。工厂应生产产品A20件，产品C160种，总利润为560元。 （2）则最优表可知，影子价格为y1C(j)-Z(j) 92,y2,y30,故增加利润1.8元。 55（3）因为y2=0.4，所以叫价应不少于1.6元。

（4）依据最优表计算得

83c12,c2,1c395 13c1[1,6],c2(,],c3[2,12]533 / 43

（5）依据最优表计算得

100b1400,400b2100,400b33 500b1[,600],b2[100,600],b3[200,).3（6）变化后的检验数为λ2=1,λ4=-2,λ5=0。故x2进基x1出基,得到最最优解X=(0,200,0)，即只生产产品B 200件,总利润为600元。 C(j) XB 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 4 2 0 2 3 0 2 0 0 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 CB R.H.S. 20 160 400 560 100 100 400 200 100 400 Ratio 100 800/3 M M 100 M C(j)-Z(j) C(j)-Z(j) C(j)-Z(j) 29222c7CBB1P7YP7,,02

5551则当单位产品D的利润超过4.4元时才有利于投产。

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

maxZ(32)x1(5)x2x14（1）x263x12x218x1,x20

【解】μ＝0时最优解X=(4,3,0)；最优表： C(j) 3 5 0 Basis X1 X2 X5 C(i) 3 5 0 X1 1 0 0 0 X2 0 1 0 0 X3 1 0 -3 -3 0 X4 0 0.5 -1 -2.5 0 X5 0 0 1 0 R. H. S. 4 3 0 27 C(j)-Z(j) 将参数引入到上表： 34 / 43

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

(μ＝5,Z=52)

(μ＝0,Z=27)

(μ＝-1.5,Z=19.5)

maxZ3x15x2x14（2）x26 3x12x2182x1,x200

【解】μ＝0时最优解X=(4,3,0)，Z＝27；最优表： C(j) 3 5 0 0 Basis X1 X2 C(i) 3 5 X1 1 0 X2 0 1 X3 1 0 X4 0 0.5 35 / 43

0 X5 0 0 R. H. S. 4 3 X5 C(j)-Z(j) 0 0 0 0 0 -3 -3 -1 -2.5 1 0 0 27 410

bbb6182bB1(bb)B1bB1b0014100.500303112410305替换最优表的右端常数，得到下表。 C(j) 3 5 Basis X1 X2 X5 C(i) 3 5 0 X1 1 0 0 X2 0 1 0 0 X3 1 0 [-3] 0 X4 0 0.5 -1

0 X5 0 0 1 R.H.S. 4＋μ 3 －5μ C(j)-Z(j) 0 0 -3 -2.5 0 ①μ<－4时问题不可行，－4≤μ<0时最优基不变。μ＝－4时Z＝15。 ②μ>0时X5出基X3进基得到下表： C(j) 3 5 0 0 0 Basis X1 X2 X3 C(i) 3 5 0 X1 1 0 0 X2 0 1 0 X3 0 0 1 0 X4 -1/3 1/2 1/3 -3/2 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 Range (Vector) (Vector) OBJ Value OBJ Value Slope Variable 1 0 0 27 27 3 X5 2 0 6 27 15 -2 X1 3 6 9 15 0 -5 X2 4 9 Infinity Infeasible 5 0 -4 27 15 3 X1 36 / 43

Entering Variable X3 X2 6 -4 目标值变化如下图所示。 -Infinity Infeasible

习题三

1．设xj1,投资j项目0，不投资j项目

maxZ30x140x220x315x430x55x14x25x37x48x530x7x9x5x6x25234518x12x26x32x49x530xj＝0或1,j1,,5最优解X＝(1,1,1,0,1)，Z=110万元。

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

maxZ400x1500x2450x3400x12900x11200x21000x3850x111000x12900044771212 x2,x3,x1,x2,x3,x4jjjjjjj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件货物，有

37 / 43

maxZ5x18x24x36x47x53x66x15x23x34x47x52x6203x17x24x35x46x52x656x4x50xx121xj0或1

4．设xij（i=1，2，…，5；j＝1，2，3，4）为第i人参赛j项目的状态，即

1xij0记第i人参赛j项目的成绩为Cij,，目标函数

第i人参赛j项目

第i人不参赛j项目54maxZCijxij

i1j1每个运动员最多只能参加3个项目并且每个项目只能参赛一次,约束条件：

xi1xi2xi3xi43i1,2,,5 每个项目至少要有人参赛一次，并且总的参赛人次数等于10，约束条件：

x1jx2jx3jx4jx5j1j1,2,3,4

xi1j154ij10

xij＝1或0，i=1，2，…，5；j＝1，2，3，4

x12x28y1Mx15yMx5(1y)Mx12y14y26y38y414x1x210y2M5. (1)2x16x218y3M(2)x210yM(3)y1y2y3y41yyy1x8(1y)My0或1，j1,2,3,41222j

y0或1，j1,2,3y0或1jminZ10y16x115y210x2x1y1M;x2y2Mx8yM31x26(1y3)Mx1x20y44y54y68y78y86．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．(1)X=(1,2),Z=3 (2) X=(5,0),Z=5 8．(1)X=(3,3),Z=15 (2)X=(5,2),Z=16 9．教材原题遗漏，请补上。

条件（1）条件（2）

条件（3）条件（4）38 / 43

x1x24x35x435x12x2x36（1） （2）3x1x22x32x44

4x12x2x37x0或1，j1,2,3x13x22x34x47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．(1)X=(1,0,1,1),Z=8 (2)X=(1,1,0,0,0),Z=－2

maxZ4x13x2＋x3minZ4x1x2x33x4习题四

4.1 工厂生产甲、乙两种产品，由Ａ、Ｂ二组人员来生产。Ａ组人员熟练工人比较多，工作效率高，成本也高；Ｂ组人员新手较多工作效率比较低，成本也较低。例如，A组只生产甲产品时每小时生产10件，成本是50元有关资料如表4.21所示。

表4.21 A组 B组 产品售价(元/件) 产品甲 效率(件/小时) 10 8 80 成本(元/件) 50 45 产品乙 效率(件/小时) 8 5 75 成本(元/件) 45 40 二组人员每天正常工作时间都是8小时，每周5天。一周内每组最多可以加班10小时，加班生产的产品每件增加成本5元。

工厂根据市场需求、利润及生产能力确定了下列目标顺序： P1：每周供应市场甲产品400件，乙产品300件 P2：每周利润指标不低于500元

P3：两组都尽可能少加班，如必须加班由Ａ组优先加班 建立此生产计划的数学模型。

4.1【解】 解法一：设x1, x2分别为A组一周内正常时间生产产品甲、乙的产量，x3, x4分别为A组一周内加班时间生产产品甲、乙的产量；x5, x6分别为B组一周内正常时间生产产品甲、乙的产量，x7, x8分别为B组一周内加班时间生产产品甲、乙的产量。 总利润为

80(x1x3x5x7)(50x155x345x550x7)75(x2x4x6x8)(45x250x440x645x8)30x130x225x325x435x535x630x730x8生产时间为

A组：0.1x10.125x20.1x30.125x4 B组：0.125x50.2x60.125x70.2x8 数学模型为：

39 / 43

－－minZp1(d1d2)p2d3p3(d4d5)p4(d62d7)x1x3x5x7d1－d1400－x2x4x6x8d2d230030x30x25x25x35x35x30x30xd－d5002345678331 0.1x10.125x2d4d4400.125x0.2xdd4056550.1x0.125xdd1034660.125x70.2x8d7d710x0,d,d0,i1,2,,7;j1,2,,8jii解法二：设x1, x2分别为A组一周内生产产品甲、乙的正常时间，x3, x4分别为A组一周内生产产品甲、乙

的加班时间；x5, x6分别为B组一周内生产产品甲、乙的正常时间，x7, x8分别为B组一周内生产产品甲、乙的加班时间。

数学模型请同学们建立。

4.2设xij为Ai到Bj的运量，数学模型为

minzPdP(ddd)PdPdP(dd)Pd112234354657768x13x23x33d1d1480B3保证供应xxxddB1需求的85％11213122274xxxdd204B需求的85％223233212x14x24x34d4d4323B3需求的85％x33d5d5200A3对B3 s..tx21d60A2对B12x112x212x31x12x22x32d7d70B2与B3的平衡34cijxijd80运费最小i1j1x0 (i1,2,3; j1,2,3,4);ijd,d0(i1,2,...,8);ii

4.3 双击下图，打开幻灯片。

40 / 43

习题4.3(1)minZp1d1p2(2d2d3)(1)504030x2－8x14x2d1d1160x12x2d2d230x12x2d3d340x,x,d,d0,i1,2,312ii满意解在线段AB上(2)d2d22010A(50/3,20/3)B(30,0)1020304050d3x1d

4.4 已知某实际问题的线性规划模型为

1d1d3(3) maxz100x150x2 10x116x220011x13x225x,x012假定重新确定这个问题的目标为： Ｐ1：ｚ的值应不低于1900 Ｐ2：资源１必须全部利用

将此问题转换为目标规划问题，列出数学模型。 【解】数学模型为

minZp1d1p2(d2d2)(资源1)(资源2)

100x150x2d1d1190010x116x2d2d2200 11x13x225x,d,d0,j1,2jjj4.5 已知目标规划问题

minzp1d1P2d2P3(5d33d4)P4d1

41 / 43

x12x2d1d1x2xdd1222x12x2d3d3xdd244x1,x2,di,di69420(i1,,4)

（1）分别用图解法和单纯形法求解；

(2)分析目标函数分别变为①、②两种情况时（②中分析w1、w2的比例变动）解的变化。 ① minzp1d1P2d2P3d1P4(5d33d4) ② minzp1d1P2d2P3(w1d3w2d4)P4d1 【解】（1）图解法（双击下图，打开幻灯片） 习题4.5(1)minzp1d1P2d2P3(5d33d4)P4d1(2)(1)43x2x12x2d1d1x12x2d2d2x12x2d3d3x2d4d4x1,x2,di,did469420(i1,,4)2d1(4)d4(3)d2(13/2,5/4)1d11d3d323456d29x1满意解：X＝(13/2,5/4) （1）单纯形法 Cj 0 0 3 P3 P1 d1 1 1 －P4 d1+ －1 1 1 －1 0 d2 1 1 －P2 d2+ －1 1 －1 5 P3 d3 1 1 －0 d3+ －1 5 0 d4+ CB P1 0 5 P3 3 P3 表（1） Cj－Zj P1 0 5 P3 0 基 d1 －－－－x1 1 1 1 －1 －5 [1] 1 1 x2 2 2 －2 [1] －2 7 1 d4 1 －b 6 9 4 2 2 5 8 2 d2 d3 d4 P1 P2 P3 P4 d1 －－－－1 3 2 2 －2 －1 －2 －2 2 1 d2 d3 x2 －－1 42 / 43

P1 表（2） Cj－Zj 0 P4 3 P3 －1 －5 1  7 1 －1 1 1 1 1 1  1/2 1 －1/4 1/4 3/4 1  1 －1/2 －1 1/4 －1/4 1 －3/4 1 1/2 1/4 －1/4 17/4 2 －7 0 1 －2 10 0 －1 3 13/2 3 3/4 5/4 P2 P3 P4 x1 d1+ d4 x2 P1 P2 P3 P4 －5 －1/2 －1/4 3/4 0 表（5） Cj－Zj

(b) minzp1d1P2d2P3(w1d3w2d4)P4d1

单纯形法，利用上表（5）的结果，引入参数w1、w2进行灵敏度分析，得到下表。 Cj 0 0 w2P3 P1 P4 0 P2 w1P3 0 CB 0 P4 w2P3 0 表（1） Cj－Zj 0 P4 w1P3 0 表（2） Cj－Zj 基 x1 d1+ d4 x2 P1 P2 P3 P4 x1 d1+ d3 x2 P1 P2 P3 P4 －－－0 d4+ 0 －1 x1 1 1 x2 1 1 d1 －1 1 1 －1 1 1 －d1+ 1 1 d2 1/2 1 －1/4 1/4 －d2+ －1/2 －1 1/4 －1/4 1 －w2/4 1 －1 －1 1 1 －w1 1 d3 1/2 [1/4] －1/4 w1- w2/4 1 －d3+ －1/2 －1/4 d4 0 1 －b 13/2 3 3/4 5/4 5 3 3 2 －2 4 1 w2－4w1 w2/4 1 1 1 －1 w2/4 w2 2 －4 －1 4w1 －1 w1 －1 w1 w11(w1,w20)时，满意解为：X＝（13/2，5/4） w24w1（2）由表（2）知，当w2－ 4w1 > 0，即 1(w1,w20)时，满意解为：X＝（5，2）

w24w1（3）当1(w1,w20)时，表(1)和表(2)都是满意解。

w24（1）由表（1）知，当w1－ w2/4 > 0，即

43 / 43