茹少锋运筹学课后答案西北大学考研第二章到第十章

第二章

1．用图解法求解两个变量线性规划问题的最优解和最优值。

maxz?2x1?3x2?x1?2x2?6?st.?5x1?3x2?15?x,x?0?12

x2最优解：（12/7，15/7）最优值：69/7x1

2．用图解法求解以下线性规划问题，并指出哪个问题有惟一解、无穷多最优解、无界解或无可行解

minz?6x1?4x2?2x1?x2?1?st.?3x1?4x2?3?x,x?0?12

x2最优解：（1/5,3/5）最优值： 3.613/4 01/21x1

maxz?4x1?8x2?2x1?2x2?10?st.??x1?x2?8?x,x?012 ?

x2x1

无可行解

3．某公司从中心制造地点向分别位于城区北、东、南、西方向的分配点运送材料。该公司有26辆卡车，用于从制造地点向分配点运送材料。其中有9辆，每辆能装5吨的大型卡车，12辆每辆能装2吨的中型卡车和5辆每辆能装1吨的小型卡车。北、东、南、西四个点分别需要材料14吨、10吨、20吨、8吨。每辆卡车向各分配点送材料一次的费用如表2-7所示。建立运送材料总费用最小的线性规划模型。

表2-7 车辆运送一次的费用

大 中 小 北 80 50 20 东 63 60 15 南 92 55 38 西 75 42 22

解 设大、中、小型车分别用i表示，则i?1,2,3；东、南、西、北四个分点分别用j表

x示，则j?1,2,3,4；向j方向发出的i型车数量为ij。

minZ?80x11?63x12?92x13?75x14?50x21?60x22?55x23?42x24?20x31?15x32?38x33?22x34

?5x11?2x21?x31?14?5x?2x?x?102232?12?5x13?2x23?x33?20??5x14?2x24?x34?8st.??x11?x12?x13?x14?9?x21?x22?x23?x24?12??x31?x32?x33?x34?5?x?0,i,j?1,2,3,4?ij

4．某工厂生产A、B、C三种产品，现根据合同及生产状况制定5月份的生产计划。已知合同甲为：A产品1000件，每件价格为500元，违约金为100元/每件；合同乙：B产品500件，每件价格为400元，违约金为120元/每件；合同丙为：B产品600件，每件价格为420元，违约金为130元/每件；C产品600件，价格400元/每件，违约金为90元/每件。有关各产品生产过程所需工时以及原材料的情况如表2-8所示。试以利润为目标建立该工厂生产计划的线性规划模型。

表2-8 产品使用的原材料、加工工序、资源限制、成本

工序1 工序2 工序3 原料1 原料2 其他成本 产品A 2 3 2 3 4 10 产品B 1 1 3 2 3 10 产品C 2 1 2 4 2 10 资源限制 4600 4000 6000 10000 8000 工时或原材料成本 15 10 10 20 40 解 设工厂5月份为完成合同甲生产x1件A产品；为完成合同乙生产x2件B产品；为完成合同丙生产x3件 B产品，x4件C产品。

maxZ?500x1?(1000?x1)?400x2?(500?x2)?120?420x3?(600?x3)?130?400x4?(600?x4)?90?(2?15?3?10?2?10?3?20?4?40?10)x1?(15?10?3?10?20?2?3?40?10)?(x2?x3)?(2?15?10?2?20?4?20?2?40?10)x4?290x1?295x2?325x3?260x4?292000

?2x1?x2?x3?2x4?4600?3x?x?x?2x?4000234?1?2x1?3x2?3x3?2x4?6000??3x1?2(x2?x3)?4x4?10000?st.?4x1?3(x2?x3)?2x4?8000?0?x?1000,1??0?x2?500,?0?x?600,3???0?x4?600,

5．某公司从事某种商品的经营，现欲制定本年度10至12月的进货及销售计划。已知该种商品的初始库存量为2000件，公司仓库最多可存放10000件，公司拥有的经营资金80万元，据预测，10至12月的进货及销售价格如表2-9所示。若每个月仅在1号进货1次，且要求年底时商品存量达到3000件，在以上条件下，建立该问题的线性规划模型，使公司获得最大利润？（注：不考虑库存费用）

表2-9 进货和销售价格 月份 进货价格/（元/件） 10 90 11 95 12 98 销售价格/（元/件） 100 100 115 解

xi,i?10,11,12，为每月购进的货物，yi,i?10,11,12为每月销售的货物。

maxZ?100y10?100y11?115y12?90x10?95x11?98x12????????st.?????x12????90x10?95x11?98x12?80000 资金限制2000?x10?10000 库容限制x11?2000?x10?y10?10000 库容限制x12?x11?2000?x10?y10?y11?10000 库容限制y10?2000?x10 销量限制y11?x11?2000?x10?y10 销量限制y12?x12?x11?2000?x10?y10?y11 销量限制?x11?2000?x10?y10?y11?y12?3000 年底存量限制xi?0,i?10,11,12yi?0,i?10,11,12

6．某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量单价如表2-10所示。

表2-10 饲料所含的营养成分及价格

饲料 蛋白质/g 矿物质/g 维生素/g ?1kg价格/（元·） 1 3 1 0.5 0.2 2 3 4 5 2 1 6 18 0.5 0.2 2 0.5 1.0 0.2 2 0.8 0.7 0.4 0.3 0.8 求这个问题的规划模型，使既满足动物生长的需要，又使费用最小的选用饲料的方案。 解 设各送这5钟饲料x1，x2，x3，x4，x5kg。

minZ?0.2x1?0.7x2?0.4x3?0.3x4?0.8x5?3x1?2x2?x3?6x4?18x5?700?x?0.5x?0.2x?2x?0.5x?30?12345st.??0.5x1?x2?0.2x3?2x4?0.8x5?100??xi,i?1,2,3,4,5

7．某一企业家需要找人清理5间会议室、12张桌子和18个货架。今有两个临时工A和B可供该企业家雇佣。A一天可清理1间会议室、3张桌子与3个货架；而B一天可清理1间会议室、2张桌子与6个货架。A的工资每天25元，B每天22元。为了使成本最低，应雇佣A和B各多少天？（用线性规划图解法求解）

解：设雇佣A和B分别为x,y天

minZ?25x?22yx?y?5??3x?2y?12?st.?3x?6y?18???x;y?0且x,y为整数

x6 53 0 0 4 4 …

?23 0 0 1 0 203 cj?zj ?13 ?53 5 4 3 x2 x3 0 0 1 1 0 0 0 1 0 1541 841541 ?1041 4416?41 x1 2?41 ?1241 15418041 5041 4441 cj?zj 0 1 0 ?452455611???41 41 41 123

6．已知线性规划问题 maxz?c1x1?c2x2?c3x3

?a11x1?a12x2?a13x3?x4?b1?st.?a21x1?a22x2?a23x3?x5?b2?x?0,j?1,?5?j用单纯形法求解，得到最优单纯形表如表如表3-17所示：

表3-17 最终单纯形表

XB x3 x1 x2 x3 x4 1 12x5 b 320 1 0 1 0 0 12 ?12 2 -4 x2 -1 0 2 cj?zj -3 ⑴求a11,a12,a13,a21,a22,a23,b1,b2的值； ⑵求c1,c2,c3的值。

解：由题意可知：初始的基变量是x4， x5，将最终单纯形表的基变量通过迭代转换为x4，x5，还原成最初单纯形表，如下：

XB x1 x2 x3 x4 x5 b 92 52 1 1 4 2 1 0 0 1 8 5 x4 x5 cj?zj 92 3 6 0 0 ?9?2A???5??2从而得出：

114210?0???8??9??,3,6,0,01?????? b=?5? C=?2?

95所以,a11=2 a12=1 a13=4 a21=2 a22=1 a23=2 9 b1=8 b2=5， c1= 2 c2=3 c3=6

7．某公司生产1、2两种产品，市场对1、2两种产品的需求量为：产品1在1-4月每月需求10000件，5-9月每月30000件，10-12月每月100000件，产品2在3-9月每月需求15000件，其它月每月50000件，该公司生产这两种产品的成本为：产品1在1-5月内生产每件5元，6-12月内生产每件4.5元；产品2在1-5月内生产每件8元，6-12月内生产每件7元。该公司每月生产这两种产品的能力总合不超过120000件。产品1容积每件0.2立方米，产品2每件0.4立方米，该公司仓库容量为15000立方米，占用公司仓库每月每立方米库容需1元；如该公司仓库不足时，可从外边租借，租用外面仓库每月每立方米库容需1.5元。试问在满足市场需求的情况下，该厂应如何安排生产，使总的费用最小？

8．某炼油厂使用三种原料油甲、乙、丙混合加工成A、B、C三类不同的汽油产品，有关数据如下表3-18所示。另外，由于市场原因，A的产量不得低于产品总量的40%。问该厂应如何安排生产才能使其总利润最大？

表3-18 三种原料的信息

产 品 规 原 料 甲 乙 丙 加工费（千元/吨） 售价（千元/吨） 格 ?60% ?15% 产 品 A B C 原料成本 （千元/吨） 原料限量 （吨） ?50% 1.800 1.350 0.900 2000 2500 1200 ?20% ?60% 0.450 3.060 0.360 2.565 0.270 2.025 解：设x1，x2，x3分别为A产品中甲、乙、丙的成分；x4，x5，x6分别为B产品中甲、乙、丙的成分；x7，x8，x9分别为C产品中甲、乙、丙的成分。由题意，有

max z=（3.060-0.450）*（x1+x2+x3）+（2.565-0.360）*（x4+x5+x6）+（2.025-0.270）*（x7+x8+x9）-1.800*（x1+x4+x7）-1.350*（x2+x5+x8）-0.900*（x3+x6+x9）

????x1?x4?x7?2000??x2?x5?x8?2500?x?x?x?120069?3x1??x?x?x?0.623?1?x3st.??0.2?x1?x2?x3?x4?0.15??x4?x5?x6?x6??0.6?x4?x5?x6?x9??0.5?x7?x8?x9??xj?0,j?1,2,...,9

用计算机求解为：

9．线性规划的目标函数是求其值的极大化，在标准的单纯形法求解过程中得到如下表(其中H1,H2是常数)

表3-19 求解中某一步的单纯形表

CB XB 2x1 5x2 8x3 0x4 0x5 0x6 0 5 0 b 20 x6 0 3 -1 0 x2 H1 -2 12 H2 8 x4 1 ?j -2 （1）在所有的空格上填上适当的数（可包含参数H1,H2）

（2）判断下面四种情况在什么时候成立，说明理由。1）此解为最优解，写出相应的基解和目标函数值；2）此解为最优解，且此线性规划有无穷多最优解；3）此规划有无界解；4）此解不是最优解，但可用单纯形法得到下一个基可行解。

解：（1）

CB XB 2x1 0 5 0 5x2 8x3 0x4 0x5 0x6 0 1 0 0 3 -1 -2 0 0 1 0 0 0 0 1 0 b 20 x6 0 x2 H1 -2 12H2 8 x4 1 ?j 2-5H1 - 522（2）1)当2-5H1<0 即 H1>5时，此线性规划模型有唯一解，基解为

(x1,x2,x3)??(0,H2,0)?最优值为5H2。

2 2）2-5H1=0，即 H1=5时，大于0，此线性规划模型有无穷多最优解。

3）2-5H1>0且 H1<0，即H1<0时， 此线性规划模型有无界解。

2 4）2-5H1>0且 H1>0且H2>0, 即00时，此解不是最优解。

10．表3-20是求某极大化线性规划问题计算得到的单纯形表。表中无人工变量，a1、a2、

a3、d、c1、c2为待定常数。试说明这些常数分别取何值时，以下结论成立。

表3-20 极大化线性规划问题计算得到的单纯形表

XB x3 x1 x2 x3 x4 x5 x6 b 4 -1 a1 -3 1 0 0 0 1 0 a2 -1 -4 0 0 1 d 2 3 x4 x6 a3 -5 cj?zj c1 c2 0 0 -3 0 ⑴表中解为惟一最优解； ⑵表中解为最优解，但存在无穷多最优解； ⑶该线性规划问题具有无界解；

⑷表中解非最优，为对解改进，换入变量为x1，换出变量为x6 解：（1）当d≥0，c1<0 且 c2<0, 此线性规划模型有唯一解。

（2）当d≥0，c1=0 或 c2=0，a1<0, 此线性规划模型有无穷个最优解。 （3）当d≥0，c2>0 且 a1<0, 此线性规划模型有无界解。

d （4）当d≥0，c1>0 且 a3>12，表中解非最优，为对解改进，换入变量为x1，换出变量为x6。

第四章

1．写出线性规划问题的对偶问题。

maxz?5x1?6x2?3x3maxz?10x1?3x2?5x3?2x1?5x2?x3?15?st.?4x1?3x3?7?x,x,x?0123??x1?2x2?2x3?5??x?5x?x?3?123st.??4x1?7x2?3x3?8??x1无约束，x2?0,x3?0

minz???cijxiji?1j?1mn

解：（1） （2）

?nminz?3x1?2x2?4x3?2x5??xij?ai (i?1,2,?,m)?1?jm?3x1?5x2?x4?2x5?6??st.??xij?bj (j?1,2,?,n)x2?4x3?x5?8??i?1st.??xij?0 (j?1,2,?n;i?1,2,?,m)?2x1?3x2?7x3?x4?5x5?0??x1,x2?0,x4?0??

min??15y1?7y2?2y1?4y2?10?5y?3?1st.??y1?3y2?5??y1,y2?0（3）

min??5y1?3y2?8y3?y1?y2?4y3?5?2y?5y?7y?6?123st.??2y1?y2?3y3?3?y1无约束,y2?0,y3?0?

（2）如果2分厂的产量从400箱提高到了600箱，那么应如何安排运输方案，使得总运费最小？

（3）如果销地甲的需求从400箱提高到550箱，那么该如何安排运输方案 ，使得总运费最小？

解：（1）这个问题是产销平衡运输问题。 由伏格尔法得初始调运方案为： 销地 甲 乙 产地 1分厂 2分厂 3分厂 销量/箱 400 400 250 250 350 350 丙 50 0 150 200 丁 产量/箱 300 400 500 1200 由位势法判别： 建立方程组

vi+uj=cij（cij为基变量对应运价） vi =0

解得：v2=-6，v 3=-3，u1=16，u 2= 17，u 3=23，u 4=25

由非基变量xij检验数σij=vi+uj-cij，得出σij≤0，∴该方案即为最优。

即：应安排1分厂给乙供货250箱，给丁供货50箱，2分厂给甲供货400箱，3分厂给丙供货350箱，给丁供货150箱，此时总运费最少。 （2）这个问题是产大于销的运输问题。

为了求得产销平衡，在产销平衡表中增加一个虚拟的销地戊，其销量为200箱。 则产销平衡表和单位运价表如下： 销地 产地 1分厂 2分厂 3分厂 销量/箱 甲 21 10 23 400 乙 17 15 21 250 丙 23 30 20 350 丁 25 19 22 200 戊 0 0 0 200 产量/箱 300 600 500 1400

由伏格尔法得初始调运方案为： 销地 甲 乙 产地 1分厂 2分厂 3分厂 400 250 丙 50（-50） ④ 丁 200 戊 （+50） ① 0 ② 产量/箱 300 600 500 ③ 300（+50） 销量/箱 400 250 350 200 200（-50） 200 1400 由位势法判别： 建立方程组 vi+uj=cij vi =0

由非基变量xij检验数σij=vi+uj-cij，得出σ15＞0，∴该方案不是最优方案。 故调整方案，由闭合回路法得出新的调运方案： 销地 甲 乙 丙 丁 产地 1分厂 2分厂 3分厂 销量/箱 400 400 250 250 350 350 200 200 戊 50 0 150 200 产量/箱 300 600 500 1400 由位势法判别： 建立方程组 vi+uj=cij vi =0

由非基变量xij检验数σij=vi+uj-cij，得出σij≤0，∴该方案即为最优。

即：应安排1分厂给乙供货250箱，2分厂给甲供货400箱，给丁供货200箱，3分厂给丙供货350箱，此时总运费最少。

（3）这个问题是销大于产的运输问题。

为了求得产销平衡，在产销平衡表中增加一个虚拟的产地4分厂，其产量为150箱。 则产销平衡表和单位运价表如下： 销地 甲 乙 丙 丁 产量/箱 产地 1分厂 2分厂 3分厂 4分厂 销量/箱 21 10 23 0 550 17 15 21 0 250 23 30 20 0 350 25 19 22 0 200 300 400 500 150 1350 由伏格尔法得初始调运方案为： 销地 甲 产地 1分厂 2分厂 3分厂 50 400 100（-100） 乙 250 丙 200（+100） 丁 200 产量/箱 300 400 500 ② 4分厂 销量/箱 ① （+100） 550 250 ③ ④ 150（-100） 350 200 150 1350 由位势法判别： 建立方程组 vi+uj=cij vi =0

由非基变量xij检验数σij=vi+uj-cij，得出σ41＞0，∴该方案不是最优方案。 故调整方案，由闭合回路法得出新的调运方案： 销地 甲 乙 丙 丁 产地 1分厂 2分厂 3分厂 4分厂 销量/箱 50 400 100 550 250 250 300（+50） ③ ② 50（-50） 350 200（-50） ④ ① （+50） 200 产量/箱 300 400 500 150 1350 由位势法判别： 建立方程组 vi+uj=cij vi =0

由非基变量xij检验数σij=vi+uj-cij，得出σ44＞0，∴该方案不是最优方案。 故调整方案，由闭合回路法得出新的调运方案： 销地 甲 乙 丙 丁 产地 1分厂 2分厂 3分厂 4分厂 销量/箱 50 400 100 550 250 250 350 150 50 产量/箱 300 400 500 150 1350 由位势法判别： 建立方程组 vi+uj=cij vi =0

由非基变量xij检验数σij=vi+uj-cij，得出σij≤0，∴该方案即为最优。

即：应安排1分厂给甲供货50箱，给乙供货250箱，2分厂给甲供货400箱，3分厂给丙供货350箱，给丁供货150箱，此时总运费最少。

2． 用表上作业法求下表7-36所列运输问题

表7-36 各个运输点之间的运量与收量

发 收 点 点 B1 B2 B3 B4 发量 A1 A2 A3 收量 8 3 5 5 7 4 6 5 1 6 10 3 4 2 6 7 9 9 2 解：这个问题是产销平衡运输问题。 由伏格尔法得初始调运方案为： B1 B2 发点 收点 A1 A2 A3 收量/件 5（-2） ② ① （+2） 5 3（+2） ③ ④ 2（-2） 5 B3 3 3 B4 6 1 7 发量/件 9 9 2 20 由位势法判别： 建立方程组

vi+uj=cij（cij为基变量对应运费） vi =0

由非基变量xij检验数σij=vi+uj-cij，得出σ31=0，其余检验数均小于0。 ∴该方案是最优方案，且不是唯一最优的，该问题存在另一最优解。 故进行方案调整，调整后得另一最优解为： B1 B2 B3 B4 发点 发量/件 收点 A1 A2 A3 收量/件 3 2 5 5 5 3 3 6 1 7 9 9 2 20 即要想使运费最少，应作如下安排： B1 →A2（5），B2→ A2（3）、A3（2），B3→ A1（3），B4 →A1（6）、A2（1） 或者，B1→ A2（3）、A3（2），B2→A2（5），B3→ A1（3），B4 →A1（6）、A2（1）

3．某种产品今后四周的需求量分别是300、700、900、600件，必须得到满足。已知每

件产品的成本在起初两周是10元，以后两周是15元。工厂每周能生产这种产品700件，且在第二、三周能加班生产，加班后，每周可增产200件，但成本每件增加5元。产品如不能在本周交货，则每件每周存储费为3元，问如何安排生产时总费用最少。（要求建立运输问题模型但不求解）

xxx解：设ij为第i周运往第j周的产品数量，i=1,2,3,4,j=1,2,3,4,5j,6j分别表示第2、3周加

班生产运往第j周的产品数量

minZ?10x11?13x12?16x13?19x14?10x22?13x23?16x24?15x33?18x34?15x44?15x32?18x53?21x54?15x63?18x64?x11?300??x12?x22?x52?700?x13?x23?x33?x53?x63?900??x14?x24?x34?x54?x64?600?x?x?x?x?70011121314??st.?x22?x23?16x24?700?x?x?70034?33?x44?700?x?x?x?2005354?52?x63?x64?200??x?0,i?1,2,3,4,5,6,j?5,6,7,8 ?ij

4．求解下列模型

minz?3x11?2x12?4x13?2x21?4x22?5x23 ?8x31?2x32?x33?5x41?5x42?2x43?x11?x12?x13?100?x?x?x?50?212223st.??x31?x32?x33?60??x41?x42?x43?40x11?x21?x31?x41?85x12?x22?x32?x42?90x13?x23?x33?x43?75xij?0,i?1,2,3,4;j?1,2,3

解：设Ai为第i（i=1，2，3，4）行，Bj为第j（j=1，2，3）列，则

由已知得该线性规划模型的约束条件和系数表为： Bj B1 B2 B3 ∑Ai Ai A1 A2 A3 3 2 8 2 4 2 4 5 1 100 50 60

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