运筹学部分习题

1 运筹学 运筹学部分习题 1 1 试建立下列问题的数学模型 1 设备配购问题 某农场要购买一批拖拉机以完成每年三季的工作量 春种 330 公顷 夏管 130 公顷 秋收 470 公顷 可供选择的拖拉机型号 单台投资额及工作能力如下表所示 单台工作能力 公顷 拖拉机型号单台投资 元 春种夏管秋收 东方红 5000301741 丰收 4500291443 跃进 4400321642 胜利 5200311844 问配购哪几种拖拉机各几台 才能完成上述每年工作量且使总投资最小 49800min 1 4 6 0 4321 zxxxx 2 食谱问题 某疗养院营养师要为某类病人拟订本周菜单 可供选择的蔬菜及其费用和所含营养成 分的数量 以及这类病人每周所需各种养分的最低数量如下表所示 每份蔬菜所含养分数量 毫克 养分 蔬菜铁磷维生素 A 单位 维生素 C烟酸 每份蔬菜 费用 元 青豆 0 451041580 31 5 胡萝卜 0 4528906530 351 5 花菜 1 05502550530 62 4 卷心菜 0 42575270 150 6 甜菜 0 5221550 251 8 土豆 0 57523580 81 0 每周养分 最低需求量 6 0325175002455 0 另外为了口味的需求 规定一周内所用的卷心菜不多于 2 份 其它蔬菜不多于 4 份 若病人每周需 14 份蔬菜 问选用每种蔬菜各多少份 9 19minz4 0 2 3 1 4 654321 xxxxxx 3 下料问题 某钢筋车间要用一批长度为 10 米的钢筋下料制作长度为三米的钢筋 90 根和长度为四 米的钢筋 60 根 问怎样下料最省 53min 0 45 8 321 zxxx 1 3 2 1 把下列 LP 问题化成标准形 1 2 无非负限制 321 321 321 321 321 0 0 1315719 15976 5 532min xxx xxx xxx xxx ts xxxz 无非负限制 4321 4321 321 321 4321 0 1 4 664 73 243min xxxx xxxx xxx xxx ts xxxxz 1 0 131515719 159976 5 5532max 543321 53321 3321 43321 3321 xxxxxx xxxxx xxxx xxxxx ts xxxxzz 2 0 3 2664 43 32243max 65443321 443321 63321 53321 443321 xxxxxxxx xxxxxx xxxxx xxxxx ts xxxxxxzz 2 分别用图解法和单纯形法求解下述 LP 问题 并指出单纯形法迭代中每一基本可行 解跟图解法可行域中哪一顶点相互对应 0 825 943 510max 1 21 21 21 21 xx xx xx ts xxz 0 5 2426 155 2max 2 21 21 21 2 21 xx xx xx x ts xxz 1 1212 1 1 5 max10517 5xxzxx 2 5 17max 5 1 1 21 zxx 3 农场有耕地 90 公顷 可种甲 乙 丙三种作物 甲 乙为粮食作物 丙为 经济作物 该场有流动资金 18000 元 配水 7500 百立方米 三作物每公顷对 流动资金占有额和用水量及每公顷获得纯利润如下 该农场如何安排生产可得 最大利润 作 物 消耗数量 项 目 甲 x1乙 x2丙 x3最大可用量 流动资金 元 公顷 用水量 百米 3 公顷 150 75 225 75 300 150 18000 7500 纯利润 元 公顷 375525600 最优解 X 4 30 60 0 0 0 750 即作物甲 乙分别种植 30 60 公顷 丙不种植 利润最大 单纯形法 3 1 4 1 13 123 123 23 123 max3 4 21 39 0 zxx xxx xxx s t xx x xx 1 请列举线性规划问题的标准形式的几点要求 并列出该线性规划问题的标准形式 此时不包含人工变量 2 请运用单纯形法的大 M 法求其最优解和目标函数值 1345 1234 1235 23 12345 max300 4 2 1 3 9 0 zxxxx xxxx xxxx s t xx x x x x x 2 运用单纯形法的大 M 法求解 134567 1234 12356 237 1234567 max300 4 2 1 3 9 0 zxxxxMxMx xxxx xxxxx s t xxx x x x x x x x 列单纯形表 计算最后一行检验数 所有非基的 去掉人工变量 得最优解0 j 目标函数值 5 3 0 0 0 2 2 X 3 2Z 2 试写出下述 LP 问题的对偶问题 0 40322 603 634max 1 321 321 321 321 xxx xxx xxx ts xxxz 0 0 63 32 423 4060min 21 21 21 21 21 yy yy yy yy ts yyw 0 12 1 23 201060min 2 321 321 321 321 321 xxx xxx xxx xxx ts xxxw 0 0 0 20 102 603 2max 321 321 321 321 321 yyy yyy yyy yyy ts yyyz 4 3 用对偶单纯形法求解下述线性规划问题 1 2 123 13 23 1 5 min41218 33 225 0 wxxx xx stxx x 1234 1234 1234 1 6 min23 22330 23220 0 wxxxx xxxx stxxxx x 1 转换化成标准形式 123 134 235 1 5 max41218 33 225 0 wxxx xxx stxxx x cj 4 12 18 0 0 CBXBx1 x2 x3 x4 x5 b 0 0 x4 x5 1 0 3 1 0 0 2 2 0 1 3 5 j 4 12 18 0 0 18 12 x3 x2 1 3 0 1 1 3 0 1 3 1 0 1 3 1 2 1 2 3 j 2 0 0 2 6W 36 X 0 2 3 1 0 0 36Z 2 转化为标准形式 1234 12345 12346 1 6 max23 22330 23220 0 wxxxx xxxxx s txxxxx x cj 1 2 3 1 0 0 CBXBx1 x2 x3 x4 x5 x6 b 0 0 x5 x6 1 2 2 3 1 0 2 1 3 2 0 1 30 20 j 1 2 3 1 0 0 1 0 x1 x6 1 2 2 3 1 0 0 3 1 4 2 1 30 40 j 0 0 1 1 1 0W 30 X 30 0 0 0 0 40 minz 30 5 3 某化肥厂生产两种化肥产品 A 和 B 需甲 乙两种原料 该厂库存原料和生 产两种产品的原料消耗及产品销售价如下 1 问如何安排生产计划使该厂总 产值最大 0 0 800 200 56000max XS由单纯形法得最优解 2 现在若原料紧缺 某公司向该厂购买原料 在该厂经济不受损失的情况下 问两种原料的最低售价是多少 56000 0 0 3 20 3 800 Zy这时最低总价值为 A x1 B x2 库存原料 甲 y1 乙 y2 0 1 0 2 2 1 180 吨 1200 吨 每吨售价40 元 60 元 4 某公司正在生产两种产品 产品某公司正在生产两种产品 产品 和产品和产品 每天的产量分别为每天的产量分别为 30 个和个和 120 个 利润分别为个 利润分别为 500 元元 个和个和 400 元元 个 公司负责人希望了解是否可以通过改变个 公司负责人希望了解是否可以通过改变 这两种产品的数量而提高公司利润这两种产品的数量而提高公司利润 公司各个车间的加工能力和制造单位产品所公司各个车间的加工能力和制造单位产品所 需的加工工时如下 需的加工工时如下 车间车间产品产品 产品产品 车间加工能力 每车间加工能力 每 天加工工时数 天加工工时数 120300 203540 322440 41 21 5300 单位利润单位利润500400 1 最优解及最优产品组合是什么 此时最大目标函数值即最大利润为多少 最优解及最优产品组合是什么 此时最大目标函数值即最大利润为多少 2 哪些车间的加工工时数已使用完 哪些车间的加工工时数还没用完 其哪些车间的加工工时数已使用完 哪些车间的加工工时数还没用完 其 松弛变量即没有用完的加工工时数为多少 松弛变量即没有用完的加工工时数为多少 3 四个车间的加工工时的对偶价格各为多少 请对此对偶价格的含义予以说 四个车间的加工工时的对偶价格各为多少 请对此对偶价格的含义予以说 明明 4 如果请你在这四个车间中选择一个车间进行加班生产 你会选择哪个车间 如果请你在这四个车间中选择一个车间进行加班生产 你会选择哪个车间 为什么 为什么 5 目标函数中 目标函数中 x1的系数的系数 c1 即每单位产品甲的利润值 在什么范围内变化 即每单位产品甲的利润值 在什么范围内变化 产 品 吨 耗 原 料 原 料 6 时 最优产品组合不变 时 最优产品组合不变 6 目标函数中 目标函数中 x2的系数的系数 c2 即每单位产品乙的利润值 从 即每单位产品乙的利润值 从 400 元提高为元提高为 490 元时 最优产品组合变化了没有 为什么 元时 最优产品组合变化了没有 为什么 7 请解释约束条件中的常数项的上限和下限 请解释约束条件中的常数项的上限和下限 8 第 第 1 车间的加工工时数从车间的加工工时数从 300 增加到增加到 400 时 总利润能增加多少 这时最时 总利润能增加多少 这时最 优产品的组合变化了没有 优产品的组合变化了没有 9 第 第 3 车间的加工工时数从车间的加工工时数从 440 增加到增加到 480 时 从计算机输出结果中我们能时 从计算机输出结果中我们能 否求得总利润增加的数量 为什么 否求得总利润增加的数量 为什么 10 当每单位产品甲的利润从 当每单位产品甲的利润从 500 元降至元降至 475 元 而每单位产品乙的利润从元 而每单位产品乙的利润从 400 元升至元升至 450 元时 其最优产品组合 即最优解 是否发生变化 请用百分元时 其最优产品组合 即最优解 是否发生变化 请用百分 之一百法则进行判断 之一百法则进行判断 11 当第 当第 1 车间的加工工时数从车间的加工工时数从 300 增加到增加到 350 而第 而第 3 车间的加工工时数车间的加工工时数 从从 440 降到降到 380 时 用百分之一百法则能否判断原来的对偶价格是否发生变化 时 用百分之一百法则能否判断原来的对偶价格是否发生变化 如不发生变化 请求出其最大利润 如不发生变化 请求出其最大利润 解 设解 设 x1为产品甲每天的产量 为产品甲每天的产量 x2为产品乙每天的产量 可以建立下面的线性为产品乙每天的产量 可以建立下面的线性 规划模型 规划模型 max z 500 x1 400 x2 约束条件 2 x1 300 3 x2 540 2 x1 2 x2 440 1 2 x1 1 5 x2 300 x1 x2 0 计算机求解结果如下 最优解如下 目标函数最优值为 103000 变量 最优解 相差值 x1 150 0 x2 70 0 约束 松弛 剩余变量 对偶价格 1 0 50 2 330 0 3 0 200 4 15 0 7 目标函数系数范围 变量 下限 当前值 上限 x1 400 500 无上限 x2 0 400 500 常数项数范围 约束 下限 当前值 上限 1 200 300 440 2 210 540 无上限 3 300 440 460 4 285 300 无上限 据此回答下面问题 据此回答下面问题 1 最优解及最优产品组合是什么 此时最大目标函数值即最大利润为多少 最优解及最优产品组合是什么 此时最大目标函数值即最大利润为多少 答 最优解及最优产品组合是 x1 150 x2 70 最大目标函数值即最大利润为 103000 2 哪些车间的加工工时数已使用完 哪些车间的加工工时数还没用完 其松弛 哪些车间的加工工时数已使用完 哪些车间的加工工时数还没用完 其松弛 变量即没有用完的加工工时数为多少 变量即没有用完的加工工时数为多少 答 1 3 车间的加工工时数已使用完 2 4 车间的加工工时数还没用完 其松 弛变量即对应车间没有用完的加工工时数分别为 330 和 15 3 四个车间的加工工时的对偶价格各为多少 请对此对偶价格的含义予以说明 四个车间的加工工时的对偶价格各为多少 请对此对偶价格的含义予以说明 答 1 2 3 4 车间的加工工时的对偶价格分别为 50 0 200 0 1 车间的 加工能力已用尽 设法再增加 1 个工时将使目标值 总利润 增加 50 元 3 车 间的加工能力也已用尽 设法再增加 1 个工时将使目标值 总利润 增加 200 元 2 4 车间的加工能力还有剩余 增加工时不能使目标值 总利润 有任何 增加 4 如果请你在这四个车间中选择一个车间进行加班生产 你会选择哪个车间 如果请你在这四个车间中选择一个车间进行加班生产 你会选择哪个车间 为什么 为什么 答 选择 3 车间进行加班生产 因为在该车间每增加一个工时创造的总利润增 量最大 为 200 元 5 目标函数中 目标函数中 x1的系数的系数 c1 即每单位产品甲的利润值 在什么范围内变化时 即每单位产品甲的利润值 在什么范围内变化时 最优产品组合不变 最优产品组合不变 答 决策变量 x1的价值系数在 400 内变化时 最优产品组合不变 6 目标函数中 目标函数中 x2的系数的系数 c2 即每单位产品乙的利润值 从 即每单位产品乙的利润值 从 400 元提高为元提高为 490 元时 最优产品组合变化了没有 为什么 元时 最优产品组合变化了没有 为什么 答 没有 因为其价值系数允许变化范围为 0 500 c2在此范围内变化 最 优产品组合不变 7 请解释约束条件中的常数项的上限和下限 请解释约束条件中的常数项的上限和下限 8 答 约束条件中的常数项称为资源系数 资源系数在上限和下限之间变化时 该约束条件的对偶价格不变 8 第 第 1 车间的加工工时数从车间的加工工时数从 300 增加到增加到 400 时 总利润能增加多少 这时最优时 总利润能增加多少 这时最优 产品的组合变化了没有 产品的组合变化了没有 答 第 1 车间的限额系数允许变化范围为 200 440 限额系数在此范围内变 化时 其对偶价格不变 均为 50 故第 1 车间的加工工时数从 300 增加到 400 时 总利润能增加 400 300 50 5000 这时最优产品的组合变化了 9 第 第 3 车间的加工工时数从车间的加工工时数从 440 增加到增加到 480 时 从计算机输出结果中我们能否时 从