当前位置：文档之家 › 《运筹学》习题线性规划部分练习题及答案整理版

《运筹学》习题线性规划部分练习题及答案整理版

  • 格式：docx
  • 大小：56.95 KB
  • 文档页数：20

《运筹学》线性规划部分练习题 一、思考题 1.什么是线性规划模型，在模型中各系数的经济意义是什么？

2 .线性规划问题的一般形式有何特征？

3. 建立一个实际问题的数学模型一般要几步？

4. 两个变量的线性规划问题的图解法的一般步骤是什么？

5. 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？

6. 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。

7 •试述线性规划问题的可行解、基础解、基础可行解、 最优解、最优基础解的概念及它 们之间的相互关系。 8 •试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、 有无穷多个 最优解、无界解或无可行解。 9. 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？

10. 大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什 么？最大化问

题呢？ 11 •什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情 况下，继

续第二阶段？ 二、判断下列说法是否正确。 1 .线性规划问题的最优解一定在可行域的顶点达到。

2 .线性规划的可行解集是凸集。

3. 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。

4. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件， 可行域的

范围一般将扩大。 5 .线性规划问题的每一个基本解对应可行域的一个顶点。

6. 如果一个线性规划问题有可行解，那么它必有最优解。

7. 用单纯形法求解标准形式（求最小值）的线性规划问题时，与 j ' 0对应的变量都 可

以被选作换入变量。 8 .单纯形法计算中，如不按最小非负比值原则选出换出变量， 则在下一个解中至少有一

个基变量的值是负的。

9. 单纯形法计算中，选取最大正检验数 二k对应的变量

xk作为换入变量，可使目

标函数值得到最快的减少。 10 . 一旦一个人工变量在迭代中变为非基变量后， 该变量及相应列的数字可以从单纯形

表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1 .某公司计划在三年的计划期内，有四个建设项目可以投资：项目I从第一年到

第三年年初都可以投资。预计每年年初投资，年末可收回本利 120%，每年又可以重新 将所获本利纳入投资计划；项目n需要在第一年初投资，经过两年可收回本利 150% , 又可以重新将所获本利纳入投资计划， 但用于该项目的最大投资额不得超过 20万元；项 目川需要在第二年年初投资，经过两年可收回本利 160%，但用于该项目的最大投资额 不得超过15万元；项目"需要在第三年年初投资，年末可收回本利 140%，但用于该项 目的最大投资额不得超过 10万元。在这个计划期内，该公司第一年可供投资的资金有 30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？

2 .某饲养场饲养动物，设每头动物每天至少需要 700克蛋白质、30克矿物质、

100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单

价如下表2— 1所示：

表 2— 1 饲料 蛋白质（克） 矿物质（克） 维生素（毫克） 价格（元/公斤） 1 3 1 0 . 5 0 . 2 2 2 0. 5 1 . 0 0. 7 3 1 0. 2 0. 2 0. 4 4 6 2 2 0. 3 5 12 0. 5 0. 8 0. 8

要求确定既满足动物生长的营养要求，又使费用最省的选择饲料的方案。 设有某种原料的三个产地为 A1，A2，A3，把这种原料经过加工制成成品， 再运往销售地。 假设用4吨原料可制成1吨成品，产地 A1年产原料30万吨，同时需要成品7万吨；产 地A2年产原料26万吨，同时需要成品13万吨；产地A3年产原料24万吨，不需要成 品。又知A1与A2

间距离为150公里， A1与A3间距离为100公里，A2与A3间 距离为200公里。原料运费为 3千元/万吨公里，成品运费为 2.5千元/万吨公里；在 A1开设工厂加工费为 5.5千元/万吨，在A2

开设工厂加工费为 4千元/万吨，在A3 开设工厂加工费为 3千元/万吨；又因条件限制，在 A2设厂规模不能超过年产成品 5 万吨，A1与A3可以不限制（见表2―― 2），问应在何地设厂，生产多少成品，才使生 产费用（包括原料运费、成品运费和加工费）最少？

表2 — 2 距\产 地 产地 A1 A2 A3

产原料数

（万吨） 加工费

（千元/万吨）

A1 0 150 100 30 5 . 5

A2 150 0 200 26 4

A3 100 200 0 24 3

需成品数 （万吨） 7 13 0

4某旅馆每日至少需要下列数量的服务员. （见表2 — 3）每班服务员从开始上班到下班连续

工作八小时，为满足每班所需要的最少服务员数，这个旅馆至少需要多少服务员。 表2 一 3 班次 时1 间 （日 夜服务） 最少服务员人数

1 上午 6点一 上午10点 80 2 上午 10点一 -下午2点 90 3 下午 2点一 下午6点 80 4 下午 6点一 夜间10点 70 5 夜间 10点— 夜间2点 40 6 夜间 2点一 上午6点 30 5. 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季

3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为 25元

/人日，秋冬季收入为 20元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲

养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资 800元，每只鸡投资3 元。养奶牛时每头需拨出 1.5公顷土地种饲料，并占用人工秋冬季为 100人日，春夏季 为50人日，年净收入900元/每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季 0.6人日，春夏季为0.3人日，年净收入2元/每只鸡。农场现有鸡舍允许最多养 1500 只鸡，牛栏允许最多养 200头。三种作物每年需要的人工及收入情况如表 2 — 4所示 表2 — 4

大豆 玉米 麦子 秋冬季需人日数 20 35 10

春夏季需人日数 50 75 40 年净收入（元/公顷） 3000 4100 4600 试决定该农场的经营方案，使年净收入为最大。 6. 市场对I、n两种产品的需求量为：产品I

在 1 — 4月份每月需1万件，5—9月份 每月需3万件，10 — 12月份每月需10万0件；产品H在3 — 9月份每月需1.5万件, 其它每月需5万件。某厂生产这两种产品的成本为： 产品I在1 — 5月份内生产时每件 5元，6 — 12月份内生产时每件 4.50元；产品H在在1 — 5月份内生产时每件 8元, 6 — 12月份内生产时每件 7元；该厂每月生产两种产品能力总和不超过 12万件。产品 I容积每件0.2立方米，产品n容积每件 0.4立方米。该厂仓库容积为1万5千立方米， 要求：（1）说明上述问题无可行解； （2）若该厂仓库不足时，可从外厂租借。若占用本 厂仓库每月每立方米需 1元，而租用外厂仓库时上述费用增加为 1.5元，试问在满足市 场需求情况下，该厂应如何安排生产，使总的生产加库存费用最少？（建立模型，不求 解） 7. 某工厂I、n、川三种产品在下

一年个季度的合同预定数如表 2 —5所示，该三种产品 第一季度初无库存，要求在在第四季度末每种产品的库存为 150件。已知该厂每季度生产工 时为15000小时，生产产品I、n、川每件需 3, 4, 3小时。因更换工艺装备，产品I在第 二季度无法生产。规定当产品不能按期交货时， 产品I、n每件每迟交一个季度赔偿 20元, 产品川赔偿15元，又生产出来的产品不在本季度交货的，每件每季度的库存费为 5元。问 应如何安排生产，使总的赔偿加库存费用最小。 表2 — 5

含 口 产 口仃

季 度

1 2 3 4 I 1500 1000 2000 1200

n 1500 1500 1200 1500 出 1500 2000 1500 2500 &某玩具厂生产I、n、川三种玩具，这三种玩具需在A、E、C三种机器上加工，每 60 个为一箱。每箱玩具在不同的机器上加工所需的时间（天）如表 2 — 6所示，本月可供使 用的机器的时间为：A为 15天，E为20天，C为2 4天。每箱玩具的价格为I: 1500元； n： 1700元；川:2400元。问怎样安排生产，使总的产值最大。 表2 一 6

加工天数 机 器 A B C 玩具I 2 6 1

玩具n 3 2 2

玩具川 5 2 一 9 •某线带厂生产A、E两种纱线和C、D两种纱带，纱带由纱线加工而成。这四种产品的 产值，可变成本（即材料、人工等随产品数量变化的直接费用） ，加工工时等由表2 — 7给 出，工厂有供纺纱的总工时 7200h，织带的总工时 1200h

（1） 列出线性规划模型，以便确定产品数量，使总的利润最大。

合集下载

线性规划题及答案

线性规划题及答案

线性规划题及答案线性规划是一种数学优化方法，用于在给定的约束条件下，寻找一个线性目标函数的最优解。

在实际应用中，线性规划可以用于解决各种决策问题，如生产计划、资源分配、投资组合等。

以下是一个线性规划问题的示例：问题描述：某工厂生产两种产品A和B，每天的生产时间为8小时。

产品A每件需要2小时的加工时间，产品B每件需要3小时的加工时间。

每天的加工时间总共有16个小时。

产品A的利润为100元/件，产品B的利润为150元/件。

工厂的目标是最大化每天的总利润。

解决步骤：1. 定义变量：设产品A的生产数量为x，产品B的生产数量为y。

2. 建立目标函数：目标函数是每天的总利润，即：Z = 100x + 150y。

3. 建立约束条件：a) 加工时间约束：2x + 3y ≤ 16，表示每天的加工时间不能超过16小时。

b) 非负约束：x ≥ 0，y ≥ 0，表示产品的生产数量不能为负数。

4. 求解最优解：将目标函数和约束条件带入线性规划模型，使用线性规划算法求解最优解。

最优解及分析：经过计算，得到最优解为x = 4，y = 4，此时总利润最大为100 * 4 + 150 * 4 = 1000元。

通过最优解的分析可知，工厂每天应生产4件产品A和4件产品B，才能达到每天最大利润1000元。

同时，由于加工时间约束，每天的加工时间不能超过16小时，这也是生产数量的限制条件。

此外，也可以通过灵敏度分析来了解生产数量的变化对最优解的影响。

例如，如果产品A的利润提高到120元/件，而产品B的利润保持不变，那么最优解会发生变化。

在这种情况下，最优解为x = 6，y = 2，总利润为120 * 6 + 150 * 2 = 960元。

这表明，产品A的利润提高会促使工厂增加产品A的生产数量，减少产品B 的生产数量，以获得更高的总利润。

总结：线性规划是一种重要的数学优化方法，可以用于解决各种实际问题。

通过建立目标函数和约束条件，可以将实际问题转化为数学模型，并通过线性规划算法求解最优解。

线性规划题及答案

线性规划题及答案

线性规划题及答案一、问题描述假设某公司生产两种产品：产品A和产品B。

每天生产的产品A需要花费3小时的人工时间和2小时的机器时间，每天生产的产品B需要花费2小时的人工时间和4小时的机器时间。

公司每天有8小时的人工时间和10小时的机器时间可供使用。

产品A的利润为200元/件，产品B的利润为300元/件。

公司希望通过合理安排生产计划，使得每天的总利润最大化。

二、数学建模1. 定义变量：设产品A的生产量为x，产品B的生产量为y。

2. 建立目标函数：总利润最大化，即Maximize Z = 200x + 300y。

3. 建立约束条件：3x + 2y ≤ 8（人工时间约束）2x + 4y ≤ 10（机器时间约束）x ≥ 0，y ≥ 0（非负约束）三、线性规划模型Maximize Z = 200x + 300ysubject to3x + 2y ≤ 82x + 4y ≤ 10x ≥ 0, y ≥ 0四、求解线性规划问题通过线性规划求解器进行计算，得到最优解。

1. 求解目标函数最大值：Z = 200x + 300y最大值为Z = 200 * 2 + 300 * 1 = 700。

2. 求解最优生产量：当x = 2，y = 1时，总利润最大，即每天生产2件产品A和1件产品B，总利润为700元。

五、结论根据线性规划模型的计算结果，为了使得公司每天的总利润最大化，应该安排每天生产2件产品A和1件产品B。

这样可以获得每天700元的总利润。

六、灵敏度分析在线性规划问题中，灵敏度分析可以帮助我们了解模型的稳定性和可行性。

下面对人工时间和机器时间的变化进行灵敏度分析。

1. 人工时间的变化：当每天的人工时间增加1小时，即约束条件变为3x + 2y ≤ 9时，重新求解线性规划问题。

结果显示，最大总利润仍然为700元，最优生产量为每天生产2件产品A和1件产品B。

2. 机器时间的变化：当每天的机器时间增加1小时，即约束条件变为2x + 4y ≤ 11时，重新求解线性规划问题。

运筹学习题

运筹学习题

习题一1.1 用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。

(1) min z ＝6x1＋4x2(2) max z ＝4x1＋8x2st. 2x1＋x2≥1 st. 2x1＋2x2≤103x1＋4x2≥1.5 －x1＋x2≥8x1, x2≥0 x1, x2≥0(3) max z ＝x1＋x2(4) max z ＝3x1－2x2st. 8x1＋6x2≥24 st. x1＋x2≤14x1＋6x2≥－12 2x1＋2x2≥42x2≥4 x1, x2≥0x1, x2≥0(5) max z ＝3x1＋9x2(6) max z ＝3x1＋4x2st. x1＋3x2≤22 st. －x1＋2x2≤8－x1＋x2≤4 x1＋2x2≤12x2≤6 2x1＋x2≤162x1－5x2≤0 x1, x2≥0x1, x2≥01.2. 在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标函数，比较找出最优解。

(1) max z ＝3x1＋5x2(2) min z ＝4x1＋12x2＋18x3st. x1＋x3＝4 st. x1＋3x3－x4＝32x2＋x4＝12 2x2＋2x3－x5＝53x1＋2x2＋x5＝18 x j≥0 （j＝1, (5)x j≥0 （j＝1, (5)1.3. 分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。

(1) max z ＝10x1＋5x2st. 3x1＋4x2≤95x1＋2x2≤8x1, x2≥0(2) max z ＝100x1＋200x2st. x1＋x2≤500x1≤2002x1＋6x2≤1200x1, x2≥01.4. 分别用大M法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类：(1) max z ＝4x1＋5x2＋x3(2) max z ＝2x1＋x2＋x3st. 3x1＋2x2＋x3≥18 st. 4x1＋2x2＋2x3≥42x1＋x2≤4 2x1＋4x2≤20x1＋x2－x3＝5 4x1＋8x2＋2x3≤16x j≥0 （j＝1,2,3）x j≥0 （j＝1,2,3）(3) max z ＝ x 1＋ x 2 (4) max z ＝x 1＋2x 2＋3x 3－x 4 st. 8x 1＋6x 2≥24 st. x 1＋2x 2＋3x 3＝154x 1＋6x 2≥－12 2x 1＋ x 2＋5x 3＝202x 2≥4 x 1＋2x 2＋ x 3＋ x 4＝10x 1, x 2≥0 x j ≥0 （j ＝1, (4)(5) max z ＝4x 1＋6x 2 (6) max z ＝5x 1＋3x 2＋6x 3 st. 2x 1＋4x 2 ≤180 st. x 1＋2x 2＋ x 3≤183x 1＋2x 2 ≤150 2x 1＋ x 2＋3x 3≤16 x 1＋ x 2＝57 x 1＋ x 2＋ x 3＝10x 2≥22 x 1, x 2≥0，x 3无约束 x 1, x 2≥01.5 线性规划问题max z ＝CX ，AX ＝b ，X ≥0，如X*是该问题的最优解，又λ＞0为某一常数，分别讨论下列情况时最优解的变化：（1） 目标函数变为max z ＝λCX ；（2） 目标函数变为max z ＝（C ＋λ）X ；（3） 目标函数变为max z ＝C X ，约束条件变为AX ＝λb 。

(完整版)《运筹学》习题集

(完整版)《运筹学》习题集

第一章线性规划1．1将下述线性规划问题化成标准形式1)min z＝－3x1＋4x2－2x3＋5 x4－x2＋2x3－x4＝－24xst. x1＋x2－x3＋2 x4 ≤14－2x1＋3x2＋x3－x4 ≥2x1，x2，x3≥0，x4无约束2)min z ＝2x1－2x2＋3x3＋x2＋x3＝4－xst. －2x1＋x2－x3≤6x1≤0 ，x2≥0，x3无约束1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

1)min z＝2x1＋3x24x1＋6x2≥6st2x1＋2x2≥4x1，x2≥02)max z＝3x1＋2x22x1＋x2≤2st3x1＋4x2≥12x1，x2≥03)max z＝3x1＋5x26x1＋10x2≤120st5≤x1≤103≤x2≤84)max z＝5x1＋6x22x1－x2≥2st－2x1＋3x2≤2x1，x2≥01．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解（1）min z＝5x1－2x2＋3x3＋2x4x1＋2x2＋3x3＋4x4＝7st2x1＋2x2＋x3 ＋2x4＝3x1，x2，x3，x4≥01．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。

1) maxz ＝10x 1＋5x 23x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥02) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥01．5 分别用大M 法与两阶段法求解下列LP 问题。

1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥02) max z ＝4x 1＋5x 2＋ x 3. 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4x 1＋ x 2－ x 3＝53) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥01231231231231234)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩1．61.7某班有男生30人，女生20人，周日去植树。