内容发布更新时间 : 2024/5/4 14:09:16星期一 下面是文章的全部内容请认真阅读。

华南理工大学网络教育学院 2013–2014学年度第一学期 《 运筹学 》作业

1. 某工厂用ABCD四种原料生产甲乙两种产品，生产甲和乙所需的各种原料的数量及在一个计划期内各种原料的现有数量见下表。又知每单位产品甲乙分别可获利400元和600元，设一个计划期内生产甲种产品x1个单位，乙种产品x2个单位，试写出以总利润为目标的线性规划模型，并化为标准型。

甲 乙 现有原料数量

产品 所需原料 A 4 4 28 B 4 2 20 C 1 0 32 D 2 4 24 maxZ?400x1?600x2?4x1?4x2?28?2x?2x?2012答案： ???x1?32?2x?4x?242?1??x1?0,x2?0maxZ?400x1?600x2?4x1?4x2?x3?28?2x1?2x2?x4?20?，? x?x?32?15?2x?4x?x?2426?1??x1,x2,x3,x4,x5,x6?02.某厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B

两种原材料的消耗，如下表所示：

设备 原材料A 原材料B I 1台时/件 4 kg/件 0 kg/件 II 2台时/件 0 kg/件 4 kg/件 总量 8台时 16kg 12kg 每生产一件产品I可获利1元，每生产一件产品II可获利3元，如何安排生产计划使获利最大？（有多种方法选择您熟悉的一种）（10分）

x24321O《 运筹学作业 》 第 1 页 （共 8 页）

x18246

maxZ?x1?3x2?x1?2x2?8?解 ?4x1?16??4x2?12??x1,x2?0，由图解法求出可行域各顶点的z值比较，得安排生产Ⅰ产品2件，、

Ⅱ产品3件，获利最大为11元。或加松弛变量用单纯形表计算。

maxZ?x1?2x2?x3?2x1?3x2?2x3?153、用单纯形法求解? ?1x?x?5x?20?1233???x1,x2,x3?0maxZ?x1?2x2?x3?2x1?3x2?2x3?x4?15解 先化为标准形式?，再列单纯形表计算如下 ?1?x1?x2?5x3?x5?20?3??x1,x2,x3,x4,x5?0cj CB 0 0 基XB 常数 15 20→ 1 2 1 0 0 x1 2 1/3 1 3 1/3 1/3↑ 1 0 x2 -3 1 2↑ 0 1 0 0 1 0 Tx3 2 5 1 17 5 -9 17/3 28/9 -98/9 x4 1 0 0 1 0 0 1/3 -1/9 -1/9 x5 0 1 0 3 1 -2 1 2/3 -7/3 x4 x5 200 ?，检Cj?Zj 10 0 x4 x5 75→ 20 7520-40 ?，检验数 31/30 0 x4 x5 25 35/3 最优了，检验数 -145/3 0 145?35?得到最优解为X??25, ,0,0,0?,maxZ?33??《 运筹学作业 》 第 2 页 （共 8 页）

maxZ?2x1?3x2?5x3?x4?4x1?x2?3x3?2x4?5?3x?2x?7x?44、写出线性规划问题的对偶问题 ?124s..t???2x1?3x3?4x3?x4?6??x1?0;x2,x3?0;x4无符号限制minw?5y1?4y2+6y3?4y1?3y2?2y3?2??y1?2y2?3y3?3解 对偶问题为 ?s..t??3y1?4y3??5?2y?7y?y?123?1??y1?0;y2?0;y3无符号限制maxZ?c1x1?c2x2?c3x3??a11??a13??a12??b1??1??0?5、已知线性规划问题???x1???x2???x3???x4???x5???

a??21??0??1??a22??b2??a23??x?0,j?1,2,3,4,5?j用单纯形法求解，得到最终单纯形表如下。试求出各待定常数的值。 0 0 cj CB 基XB 常数 3/2 2 c1 c2 x2 0 1 0 c3 x3 1 0 0 x1 1 1/2 -3 x4 1/2 -1 0 ?1x5 -1/2 2 -4 c3 c2 x3 x2 检验数Cj?Zj ?1/2?1/2??1/2?1/2??41??1?1,B?P,P??解 B??P3,P2????32?????? 2?2???1??1?21? B?1??b1?b2a11a12a21a22a11a12a13??3/2101? ????a23??21/210?a13??41??3/2101??89/214????????? a23??2121/21055/212???????1从而??b1?b2a21a22再由?N?CN?CBBN??c1,0,0???c3,c2???11/2?1/2?????3,0,?4?，从而 2??1/2?1《 运筹学作业 》 第 3 页 （共 8 页）

111c1?c3?c2??3,?c3?c2?0,c3?2c2??4，解得c2?4,c3?8,c1?7

222

maxZ?2x1?x2?5x3?6x4?2x1?x3?x4?86、已知线性规划问题?s..t?2x1?2x2?x3?2x4?12?x,x,x,x?0?1234y1?，其对偶问题的最优

对偶变量?y2?**解为y1?4,y2?1，试用对偶问题的性质，求原问题的最优解。

minw?8y1?12y2?2y1?2y2?2?2y?12**?解 原问题的对偶问题为，将y1?4,y2?1代入第一、二个约束成为严?s..t?y1?y2?5?y?2y?62?1??y1?0,y2?0****格等式，由互补松弛性质得x1?0,x2?0。又因y1?0,y2?0，由互补松弛性质，进而可

得??x3?x4?8T**，解之x3 ?x4?4。原问题的最优解为X*??0,0,4,4?，最优值为44。

?x3?2x4?12

7、已知世界6大城市：Pe，Pa，T，M，N，L。试在下表所示交通网络的数据中确定最小树。 Pe T Pa M N L Pe 13 51 77 68 50 T 13 60 70 67 59 Pa 51 60 57 36 2 M 77 70 57 20 55 N 68 67 36 20 34 T13596751776850552034260703657L 50 59 2 55 34 Pa解 将题设中的表用图表示

采用避圈法，寻找最小边的过程如下：

1?2?3?4?5?|

213203450[L,Pa][Pe,T][N,M][L,N][Pe,L]最后找到的[L,Pa],[Pe,T],[N,M],[L,N],[Pe,L]构成

PeMT13596751776070Pa36257最小支撑树如图所示

LNPe

《 运筹学作业M 》 第 4 页 （共 8 页）

6850552034LN

T132PaPe5020ML34N

W?T??2?13?50?34?20?119

8、某厂使用一台设备，在每年初，您作为厂长就要决定是购置新的，还是继续使用旧的。若置新的，就支付一定的购置费用；若继续使用旧的，则要支付一定的维修费。问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少，以五年为一个计划期，若已知该设备在各年初的价格预计为： 第1年 21 第2年 21 第3年 22 第4年 23 第5年 24 使用不同时间设备所需的维修费用为： 使用年数 维修费 0～1 5 1～2 6 2～3 9 3～4 14 4～5 21 显然不同的购置方案，有不同的结果，如何选择最佳方案？

554176v13226v2v3272633v43241422834v5295555v641v13226v2v3272633v4324142283476v52955v6

w12?21?5?26,w13?21?5?6?32,w13?21?5?6?9?41 w1621?5?6?9?14?55,w16?21?5?6?9?14?21?76

w23?21?5?26,w24?21?5?6?32,w25?21?5?6?9?41,w26?21?5?6?9?14?55w34?22?5?27,w35?22?5?6?33,w36?22?5?6?9?42 w45?23?5?28,w46?23?5?6?34,w56?24?5?29。

用Dijkstra 算法求：在点v1标?0,0?，在点v2标?v1,26?，再算min?32,,26?26??32在v3《 运筹学作业 》 第 5 页 （共 8 页）