运筹学 线性规划习题解析.ppt

管理运筹学 第一章线性规划 第一章线性规划 1 某化工厂生产某项化学产品 每单位标准重量为1000克 由A B C三种化学物混合而成 产品组成成分是每单位产品中A不超过300克 B不少于150克 C不少于200克 A B C每克成本分别为5元 6元 7元 问如何配置此化学产品 才能使成本最低 minS min 5x1 6x2 7x3 x1 x2 x3 1000 x1 300 x2 150 x3 200 x1 x2 x3 0 解 设配制此化学产品所需A B C三种化学物分别为x1 x2 x3克 成本为S元 则由题意可得本题的线性规划模型为 第一章线性规划 2 某产品重量为150千克 用A B两种原料制成 每单位A原料成本为2元 每单位B原料成本为8元 该产品至少需要含14单位B原料 最多含20单位A原料 每单位A B原料分别重5千克 10千克 为使成本最小 该产品中A B原料应各占多少 minS min 2x1 8x2 5x1 10 x2 150 x1 20 x2 14x1 x2 0 解 由题意可设该产品中A B原料分别为x1 x2千克 总成本为S 则本题线性规划模型为 第一章线性规划 3 设某工厂有甲 乙 丙 丁四台机床 生产A B C D E F六种产品 加工每一件产品所需要时间和每一件产品的单价如下表所示 表中没有填数的表示这台机床不参加生产这种产品 现假设在某一时间内 甲 乙 丙 丁四台机床的最大工作能力分别为850 700 600 900工时 问这一时段内 每种产品各应生产多少 才能使该厂总收入最大 maxS max 40 x1 28x2 32x3 72x4 64x5 80 x6 x1 x2 x3 3x4 3x5 3x6 8502x1 5x4 7002x2 5x4 6003x3 8x6 900 x1 x2 x6 0 解 由题意可设产品A B C D E F分别生产x1 x2 x3 x4 x5 x6单位 总收入为S元 则本题的线性规划模型为 第一章线性规划 4 一家玩具公司制造三种玩具 每一种要求不同的制造技术 高级的一种需要17个小时加工装配 8小时检测 每台利润30元 中级的需2小时加工装配 半小时检测 每台利润5元 低级的需半小时加工装配 10分钟检测 每台利润1元 现公司可供利用的加工装配时间为500小时 检测时间100小时 市场预测显示 对高级 中级 低级玩具的需求量分别不超过10台 30台 100台 试制定一个能够使总利润最大的生产计划 解 由题意设生产高级 中级 低级玩具各为x1 x2 x3台 总利润为S元 则由题意可得本题的线性规划模型为 由题意可得下表条件约束 maxS max 30 x1 5x2 x3 17x1 2x2 1 2x3 5008x1 1 2x2 1 6x3 100 x1 10 x2 30 x3 100 x1 x2 x3 0 第一章线性规划 5 现有300cm长的钢管500根 需截成70cm长和80cm长两种规格的成套材料 每套由70cm的3根 80cm的12根组成 问如何截管 可以使余料最少 套数最多 解 由题设条件可得到1根300cm长的钢管有以下几种分割方法 设x1 x2 x3 x4分别代表四种方法分割300cm的钢管的根数 S表示废料的总长度 x1 x2 x3 x4 500可以截得80cm钢管 3x1 2x2 x3 根 70cm钢管 2x2 3x3 4x4 根 共有废料 60 x1 10 x3 20 x4 cm则可得 3x1 2x2 x3 2x2 3x3 4x4 12 3化简的 3x1 6x2 11x3 16x4 0 minS min 60 x1 10 x2 20 x3 x1 x2 x3 x4 5003x1 6x2 11x3 16x4 0 x1 x2 x3 x4 0 第一章线性规划 6 某皮革厂生产甲 乙两种皮带 生产甲 乙皮带每条可获利分别为4元 3元 但生产一条甲皮带是生产一条乙皮带所需工时的2倍 如果全部生产乙皮带 该厂每天可生产1000条 但皮革供应只够日产800条 甲 乙两种皮带合计 甲 乙皮带所用皮扣 一条一扣 每天分别只能供应400个 700个 问如何安排生产 可使该厂获利最大 maxS max 4x1 3x2 2x1 x2 1000 x1 x2 800 x1 400 x2 700 x1 x2 0 解 由题设条件设生产甲 乙两种皮带分别为x1 x2根 交点 x1 200 x2 600 第一章线性规划 7 某厂用甲 乙两种原料生产A B两种产品 制造A B产品每吨所需要的各种原料 可得利润以及工厂现有的各种原料数如下表所示 1 在现有原料条件下 如何组织生产才能使利润最大maxS max 7x1 5x2 x1 2x2 284x1 x2 42x1 x2 0 解 设生产A B两种产品分别为x1 x2单位 1 在现有原料条件下 如何组织生产才能使利润最大 图解 x2 x1 14 28 42 10 5 4x1 x2 42 X1 2x2 28 k 7 5 4x1 x2 42X1 2x2 28 解得 x1 8 x2 10 K1 4 k2 1 2 2 如果原料甲增加到42吨 原最优解是否改变 图解 x2 x1 21 42 42 10 5 4x1 x2 42 X1 2x2 42 k 7 5 4x1 x2 42X1 2x2 42 解得 x1 6 x2 18 3 如果每吨B产品的利润增加到15万元 原最优解是否改变 图解 x2 x1 14 28 42 10 5 4x1 x2 42 X1 2x2 28 k 7 15 最优解是x1 2x2 28与x2轴的交点 0 14 4 每吨B产品的利润在什么范围内变化 原最优解才不会改变 图解 x2 x1 14 28 42 10 5 4x1 x2 42 X1 2x2 28 4 k 1 2 k1 4 k2 1 2 可得 4 k 1 2目标函数 7x1 bx2k 7 b7 4 b 14 复习 条件 满足前约束 满足后约束 无非零分量 或有非零分量但其非零分量对应的A的列向量线性无关 使目标函数最大 第一章线性规划 10 已知线性规划问题为 minS min x1 2x2 3x3 4x4 5x2 x3 3x4 5x1 4x2 x3 4x4 7xi i 1 2 3 4 判断下述各点 X1 8 2 7 4 T X2 1 0 2 1 T X3 2 0 5 0 T X4 0 0 1 2 T X5 3 1 0 0 T是不是该问题的可行解 基础解 基可行解 试从中找出最优的一个解 第一章线性规划 X1不是基础解 满足前约束但非零分量对应的列向量线性相关 不是可行解 不满足后约束 不是基可行解 X2不是基础解 非零分量对应的列变量线性相关 是可行解 满足前后约束 不是基可行解 X3是基础解 非零分量对应的列变量线性无关 可行解 因此也是基可行解 X4是基础解 不是可行解 因此也不是基可行解 X5是基础解 可行解 因此也是基可行解 将X3和X5带入目标函数可得 S3 S5 所以X3是最优解 第一章线性规划 11 已知X0 2 3 0 T是某线性规划问题的最优解 能否判断 1 X0一定是基础解 2 X0一定是可行解 3 X0一定是基可行解 4 X0一定是基最优解 错 对 错 错 第一章线性规划 12 已知X0 2 0 1 T是某已化成满秩标准形的 具有3个变量的线性规划问题的一组值 能否判定 1 X0一定不是基础解 2 X0一定不是可行解 3 X0一定不是基可行解 4 X0一定不是最优解 5 X0一定不是基最优解 错 对 对 对 对 第一章线性规划 13 已知线性规划问题maxS max x1 x2 x3