1 用图解法求解两个变量线性规划问题的最优解和最优值 0 1535 62 st 32max 21 21 21 21 xx xx xx xxz 1 x 2 x 最优解 12 7 15 7 最优值 69 7 2 用图解法求解以下线性规划问题 并指出哪个问题有惟一解 无穷多最优解 无界 解或无可行解 0 343 12 st 46min 21 21 21 21 xx xx xx xxz 最优解 1 5 3 5 最优值 3 6 11 2 0 3 4 1 1 x 2 x 0 8 1022 st 84max 21 21 21 21 xx xx xx xxz 1 x 2 x 无可行解 3 某公司从中心制造地点向分别位于城区北 东 南 西方向的分配点运送材料 该 公司有 26 辆卡车 用于从制造地点向分配点运送材料 其中有 9 辆 每辆能装 5 吨的大型 卡车 12 辆每辆能装 2 吨的中型卡车和 5 辆每辆能装 1 吨的小型卡车 北 东 南 西四 个点分别需要材料 14 吨 10 吨 20 吨 8 吨 每辆卡车向各分配点送材料一次的费用如表 2 7 所示 建立运送材料总费用最小的线性规划模型 表 2 7 车辆运送一次的费用 北 东 南 西 大 80 63 92 75 中 50 60 55 42 小 20 15 38 22 解 设大 中 小型车分别用i表示 则 3 2 1 i 东 南 西 北四个分点分别用 j 表 示 则 4 3 2 1 j 向 j 方向发出的i型车数量为 ij x 34333231 2423222114131211 22381520 4255605075926380min xxxx xxxxxxxxZ 4 3 2 1 0 5 12 9 825 2025 1025 1425 34333231 24232221 14131211 342414 332313 322212 312111 jix xxxx xxxx xxxx xxx xxx xxx xxx st 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 产品使用的原材料 加工工序 资源限制 成本 产品 A 产品 B 产品 C 资源限制 工时或原材料成本 工序 1 2 1 2 4600 15 工序 2 3 1 1 4000 10 工序 3 2 3 2 6000 10 原料 1 3 2 4 10000 20 原料 2 4 3 2 8000 40 其他成本 10 10 10 解 设工厂 5 月份为完成合同甲生产 1 x 件 A 产品 为完成合同乙生产 2 x 件 B 产品 为 完成合同丙生产 3 x 件 B 产品 4 x 件 C 产品 292000260325295290 10402 20420210152 104032201031015 10404203102103152 90 600 400130 600 420120 500 400 1000 500max 4321 4 32 144 332211 xxxx x xx xxx xxxxxxZ 6000 6000 5000 10000 80002 34 100004 23 60002332 400023 460022 4 3 2 1 4321 4321 4321 4321 4321 x x x x xxxx xxxx xxxx xxxx xxxx st 5 某公司从事某种商品的经营 现欲制定本年度 10 至 12 月的进货及销售计划 已知该种商品的初始库存量为 2000 件 公司仓库最多可存放 10000 件 公司拥有的经 营资金 80 万元 据预测 10 至 12 月的进货及销售价格如表 2 9 所示 若每个月仅在 1 号进货 1 次 且要求年底时商品存量达到 3000 件 在以上条件下 建立该问题的线性 规划模型 使公司获得最大利润 注 不考虑库存费用 表 2 9 进货和销售价格 月份 10 11 12 进货价格 元 件 90 95 98 销售价格 元 件 100 100 115 解 12 11 10 ix i 为每月购进的货物 12 11 10 iy i 为每月销售的货物 12 11 10 0 12 11 10 0 30002000 2000 2000 2000 100002000 100002000 100002000 80000989590 989590115100100max 121110101112 111010111212 10101111 1010 1110101112 101011 10 121110 121110121110 iy ix yyyxxx yyxxxy yxxy xy yyxxx yxx x xxx st xxxyyyZ i i 年底存量限制 销量限制 销量限制 销量限制 库容限制 库容限制 库容限制 资金限制 6 某饲养场饲养动物出售 设每头动物每天至少需 700g 蛋白质 30g 矿物质 100mg 维生素 现有五种饲料可供选用 各种饲料每公斤营养成分含量单价如表 2 10 所示 表 2 10 饲料所含的营养成分及价格 饲料 蛋白质 g 矿物质 g 维生素 g 价格 元 1 kg 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 18 0 5 0 8 0 8 求这个问题的规划模型 使既满足动物生长的需要 又使费用最小的选用饲料的方案 解 设各送这 5 钟饲料 1 x 2 x 3 x 4 x 5 x kg 5 4 3 2 1 1008 022 05 0 305 022 05 0 70018623 8 03 04 07 02 0min 54321 54321 54321 54321 ix xxxxx xxxxx xxxxx st xxxxxZ i 7 某一企业家需要找人清理 5 间会议室 12 张桌子和 18 个货架 今有两个临时工 A 和 B 可供该企业家雇佣 A 一天可清理 1 间会议室 3 张桌子与 3 个货架 而 B 一天可清 理 1 间会议室 2 张桌子与 6 个货架 A 的工资每天 25 元 B 每天 22 元 为了使成本最低 应雇佣 A 和 B 各多少天 用线性规划图解法求解 解 设雇佣 A 和 B 分别为 yx 天 为整数且yxyx yx yx yx st yxZ 0 1863 1223 5 2225min 0 4 56 3 5 6 x y A 3x 2y 12 x y 5 3x 6y 18 由图知 A 点为最优解 联立方程 5 1223 yx yx 解得 x 2 y 3 即 Zmin 25x 22 y 25 2 22 3 116 因此 雇佣 A 工人 2 天 B 工人 3 天 8 某外贸公司专门经营某种杂粮的批发业务 公司现有库容 5000 担的仓库 1 月 1 日 公司拥有库存 1000 担杂粮 并有资金 20000 元 估计第一季度杂粮价格如表 2 11 所示 表 2 11 第一季度杂粮价格表 进货价 元 出货价 元 1 月 2 85 3 10 2 月 3 05 3 25 3 月 2 90 2 95 如果买进的杂粮当月到货 但需到下月才能卖出 且规定 货到付款 公司希望本季度 末库存为 2000 担 建立该问题的线性规划模型使三个月总的获利最大 解 设一月份买入 1 x 担 卖出 1 x 担 二月份买入 2 x 担 卖出 2 x 担 三月份买入 3 x 担 卖出 3 x 担 3 2 1 0 3 2 1 0 20001000 25 310 385 22000090 2 50001000 10 385 22000005 3 50001000 2000085 2 90 295 205 325 385 210 3max 3 32 21 1 2 113 2 21 1 112 1 1 1 3 32 21 1 jxix xxxxxx xxxx xxxx xxx xx x st xxxxxxZ ji 1 求下列线性规划问题的所有基解 基可行解 最优解 0 642 2 st 33max 321 321 321 321 xxx xxx xxx xxxz 解 由题意知 A 111 124 1 2 3 ppp b 2 6 c 3 1 3 1 1 B 1 2 pp 1 B 0 1 B 是基 1 x 2 x 是基变量 3 x 是非基变量 令 3 x 0 得 1 x 2 2 x 4 即 1 2 3 x x x 2 4 0 为基解 但不是基本可行解 2 2 B 1 3 pp 2 B 0 2 B 是基 1 x 3 x 是基变量 2 x 是非基变量 令 2 x 0 得 1 x 2 3 3 x 3 4 即 1 2 3 x x x 3 4 3 2 0 为基解 同时为基本可行解 zmax 2 3 3 0 4 3 3 6 3 32 3 Bpp 3 B 0 3 B 是基 2 x 3 x 是基变量 1 x 是非基变量 令 1 x 0 得 2 x 1 3 x 1 即 1 2 3 x x x 1 1 0 为基解 同时为基本可行解 zmax 1 3 4 综上所述 基解为 1 2 3 x x x 0 4 2 1 2 3 x x x 3 4 3 2 0 1 2 3 x x x 1 1 0 其中第二个和第三个 为基本可行解 1 2 3 x x x 3 4 3 2 0 为最优解 2 分别用图解法和单纯形法求解下列线形规划问题 并指出单纯形法迭代的每一步相 当于图形上哪一个顶点 0 2 1 st 32max 21 1 21 21 xx x xx xxz 解 1 图解法 o 1 x 2 x A 2 1 x B 1 21 xx 有图解法知线性规划模型的可行域如阴影部分所示 令z 0 1 2 时 max z逐渐增大 可行域是无界的 所以 此模型是无界解 2 单纯形法 化为标准型为 1234 123 14 123 4 m a x2300 1 2 s t 0 zxxxx xxx xx xxxx A 1110 1001 2 1 b C 2 3 0 0 B c B x 2 1 x 3 2 x 0 3 x 0 4 x b 0 3 x 1 1 1 0 1 0 4 x 1 0 0 1 2 2 3 0 0 对应图中原点 以 1 为轴心项 换基迭代 得 B c B x 2 1 x 3 2 x 0 3 x 0 4 x b 2 1 x 1 1 1 0 1 0 4 x 0 1 1 1 1 0 5 2 0 2 此时对应图中 A 点 坐标是 1 0 以 1 为轴心项 换基迭代 得 B c B x 2 1 x 3 2 x 0 3 x 0 4 x b 2 1 x 1 0 0 1 2 3 2 x 0 1 1 1 1 0 0 3 5 7 此时对应图中 B 点 坐标是 2 3 因为 3 5 0 同时 3 x 对应的列小于等于 0 则 原模型有无界解 0 1823 122 4 st 52max 21 21 2 1 21 xx xx x x xxz 解 1 图解法 可行域如上图阴影部分所示 令 z 0 1 2 做等值线 得出在 c 点取最大值 c 点 坐标为 2 6 max z 34 2 单纯形法 化为标准型为 12345 13 24 125 m a x25000 4 21 2 s t 321 8 0 1 2 5 j zxxxxx xx xx xxx xj 10100 02010 32001 A 1 2345