《2线性规划的图解法》由会员分享,可在线阅读,更多相关《2线性规划的图解法(58页珍藏版)》请在金锄头文库上搜索。
1、1 物流运筹学物流运筹学 运筹学模型 方法在物流管理中的应用 重庆工商大学李海南重庆工商大学李海南 2 线性规划是运筹学的一个重要分支 它是现线性规划是运筹学的一个重要分支 它是现线性规划是运筹学的一个重要分支 它是现线性规划是运筹学的一个重要分支 它是现 代科学管理的重要手段之一 是帮助管理者作出代科学管理的重要手段之一 是帮助管理者作出代科学管理的重要手段之一 是帮助管理者作出代科学管理的重要手段之一 是帮助管理者作出 最优决策的一个有效的方法 最优决策的一个有效的方法 最优决策的一个有效的方法 最优决策的一个有效的方法 先看下面一个问题先看下面一个问题先看下面一个问题先看下面一个问题 第
2、二章 线性规划的图解法第二章 线性规划的图解法 3 例例例例1 1 某工厂在计划期内要安排 某工厂在计划期内要安排 某工厂在计划期内要安排 某工厂在计划期内要安排 两种产品的两种产品的两种产品的两种产品的 生产 已知生产单位产品所需的设备台时及生产 已知生产单位产品所需的设备台时及生产 已知生产单位产品所需的设备台时及生产 已知生产单位产品所需的设备台时及A A B B两两两两 种原材料的消耗 以及资源的限制 如下表所示 种原材料的消耗 以及资源的限制 如下表所示 种原材料的消耗 以及资源的限制 如下表所示 种原材料的消耗 以及资源的限制 如下表所示 资源限制资源限制资源限制资源限制 设备设备
3、设备设备 1 1 1 1 300300台时台时台时台时 原料原料原料原料A A 2 2 1 1 400400千克千克千克千克 原料原料原料原料B B 0 0 1 1 250250千克千克千克千克 4 问题问题问题问题2 2 如果该工厂每生产一单位产品如果该工厂每生产一单位产品如果该工厂每生产一单位产品如果该工厂每生产一单位产品I I可获利可获利可获利可获利5050元 每生产一单位元 每生产一单位元 每生产一单位元 每生产一单位 产品产品产品产品 可获利可获利可获利可获利100 100 元 元 元 元 问工厂应分别生产多少个产品问工厂应分别生产多少个产品问工厂应分别生产多少个产品问工厂应分别生产
4、多少个产品 和产品和产品和产品和产品 才能使工厂获利最才能使工厂获利最才能使工厂获利最才能使工厂获利最 多多多多 问题问题问题问题1 1 利用上述资源可以生产出多少件上述产品 利用上述资源可以生产出多少件上述产品 利用上述资源可以生产出多少件上述产品 利用上述资源可以生产出多少件上述产品 5 如何建立模型 如何建立模型 6 问题分析问题分析 对于问题对于问题1 利用上述资源可以各生产出多少件上利用上述资源可以各生产出多少件上利用上述资源可以各生产出多少件上利用上述资源可以各生产出多少件上 述产品 述产品 述产品 述产品 资源限制资源限制资源限制资源限制 设备设备设备设备 1 1 1 1 300
5、300台时台时台时台时 原料原料原料原料A A 2 2 1 1 400400千克千克千克千克 原料原料原料原料B B 0 0 1 1 250250千克千克千克千克 这是中学就可以解决的问题 工厂目前要决策的问题是 在上述资源限制下生产多少 个 产品和 产品 把这个要决策的问题用变量 这是中学就可以解决的问题 工厂目前要决策的问题是 在上述资源限制下生产多少 个 产品和 产品 把这个要决策的问题用变量x1 x2 来表示 则称来表示 则称x1和和x2为为决策变量 即决策变量 即决策变量x1 生产生产 I产品的数量 决策变量产品的数量 决策变量x2 生产 产品的数量 生产 产品的数量 7 台时数的限
6、制可以表示为 台时数的限制可以表示为 X1 X2 300 两种原材料的限量可分别表示为 两种原材料的限量可分别表示为 2X1 X2 400 X2 250 考虑现实可行性 显然还应该有考虑现实可行性 显然还应该有 x1 0 x2 0 因为 产品因为 产品 产品的 产量是不能取负值的 产品的 产量是不能取负值的 8 问题分析问题分析 对于问题对于问题2 如果该工厂每生产一单位产品如果该工厂每生产一单位产品如果该工厂每生产一单位产品如果该工厂每生产一单位产品I I可获可获可获可获 利利利利5050元 每生产一单位产品元 每生产一单位产品元 每生产一单位产品元 每生产一单位产品 可获利可获利可获利可获
7、利100 100 元 问元 问元 问元 问 工厂应分别生产多少个产品工厂应分别生产多少个产品工厂应分别生产多少个产品工厂应分别生产多少个产品 和产品和产品和产品和产品 才能使工厂才能使工厂才能使工厂才能使工厂 获利最多获利最多获利最多获利最多 问题问题2与问题与问题1之间有什么关系 之间有什么关系 用用x1和和x2的线性函数形式来表示工厂所要求的最大 利润的目标 的线性函数形式来表示工厂所要求的最大 利润的目标 max Z 50 x1 100 x2 称为 称为目标函 数 目标函 数 其中其中max为最大化的符号为最大化的符号 最小化为最小化为min 50和和100 分别为单位产品 的利润 分别
8、为单位产品 的利润 再考虑前述资源约束 即再考虑前述资源约束 即约束条件约束条件 就得到了问 题 就得到了问 题2的数学模型的数学模型 9 目标函数 目标函数 max Z 50 x1 100 x2 满足约束条件 满足约束条件 x1 x2 300 2 x1 x2 400 x2 250 x1 0 x2 0 由于上述数学模型的由于上述数学模型的目标函数为变量的线性函 数 约束条件也为变量的线性等式或不等式 目标函数为变量的线性函 数 约束条件也为变量的线性等式或不等式 故此模 型称之为线性规划 如果目标函数是变量的非线性函 数 或约束条件中含有变量非线性的等式或不等式的 数学模型则称之为非线性规划
9、故此模 型称之为线性规划 如果目标函数是变量的非线性函 数 或约束条件中含有变量非线性的等式或不等式的 数学模型则称之为非线性规划 把满足所有约束条件的解称为该线性规划的可行 解 问题 把满足所有约束条件的解称为该线性规划的可行 解 问题1的解 把使得目标函数值最大的解 把使得目标函数值最大 即利润最 大 即利润最 大 的可行解称为该线性规划的最优解 此目标函数 值称为最优目标函数值 简称最优值 的可行解称为该线性规划的最优解 此目标函数 值称为最优目标函数值 简称最优值 10 管理上有很多问题可建立线性规划模型来解决 如管理上有很多问题可建立线性规划模型来解决 如 合理利用线材问题合理利用线
10、材问题 现有一批长度一定的钢管 由于 现有一批长度一定的钢管 由于 生产的需要 要求截出不同规格的钢管若干 试问应生产的需要 要求截出不同规格的钢管若干 试问应 如何下料 既满足了生产的需要 又使得使用的原材如何下料 既满足了生产的需要 又使得使用的原材 料钢管的数量最少 料钢管的数量最少 配料问题配料问题 用若干种不同价格不同成分含量的原料 用若干种不同价格不同成分含量的原料 用不同的配比混合调配出一些不同价格不同规格的产用不同的配比混合调配出一些不同价格不同规格的产 品 在原料供应量的限制和保证产品成分的含量的前品 在原料供应量的限制和保证产品成分的含量的前 提下 如何获取最大的利润 提下
11、 如何获取最大的利润 常见的线性规划问题常见的线性规划问题 11 3 3 投资问题投资问题 从许多不同的投资项目中选出一个投资方 从许多不同的投资项目中选出一个投资方 案 使得投资的回报为最大 案 使得投资的回报为最大 4 4 产品生产计划产品生产计划 合理充分地利用厂里现有的人力 物 合理充分地利用厂里现有的人力 物 力 财力 作出最优的产品生产计划 使得工厂获利最力 财力 作出最优的产品生产计划 使得工厂获利最 大 大 5 5 劳动力安排劳动力安排 某单位由于工作需要 在不同时间段需要 某单位由于工作需要 在不同时间段需要 不同数量的劳动力 在每个劳动力工作日连续工作八小不同数量的劳动力
12、在每个劳动力工作日连续工作八小 时的规则下 如何安排劳动力 才能用最少的劳动力来时的规则下 如何安排劳动力 才能用最少的劳动力来 满足工作的需要 满足工作的需要 6 6 运输问题运输问题 一个公司有若干个生产单位与销售单位 根 一个公司有若干个生产单位与销售单位 根 据各生产单位的产量及销售单位的销量 如何制定调运据各生产单位的产量及销售单位的销量 如何制定调运 方案 将产品运到各销售单位而总的运费最小 方案 将产品运到各销售单位而总的运费最小 12 线性规划建模要弄清楚以下几个问题 线性规划建模要弄清楚以下几个问题 1 哪些问题可采用线性规划模型解决 哪些问题可采用线性规划模型解决 2 怎么
13、知道所建立的模型是线性规划呢 怎么知道所建立的模型是线性规划呢 3 线性规划问题建模要注意哪些问题 线性规划问题建模要注意哪些问题 4 变量说明要注意的问题变量说明要注意的问题 讨论与小结讨论与小结 13 可采用线性规划模型解决的问题的特征可采用线性规划模型解决的问题的特征 首先 首先 首先 首先 模型是线性的 模型是线性的 模型是线性的 模型是线性的 其次 其次 其次 其次 都要求达到某些数量上的最大化或最小都要求达到某些数量上的最大化或最小都要求达到某些数量上的最大化或最小都要求达到某些数量上的最大化或最小 化的目标 化的目标 化的目标 化的目标 如问题如问题如问题如问题1 1 是要求使用
14、原料钢管最少 是要求使用原料钢管最少 是要求使用原料钢管最少 是要求使用原料钢管最少 问题问题问题问题2 2是要求利润最大 问题是要求利润最大 问题是要求利润最大 问题是要求利润最大 问题3 3是要求投资回报最大是要求投资回报最大是要求投资回报最大是要求投资回报最大 等等 在所有线性规划的问题中某些数量上的最大等等 在所有线性规划的问题中某些数量上的最大等等 在所有线性规划的问题中某些数量上的最大等等 在所有线性规划的问题中某些数量上的最大 化或最小化就是线性规划问题的目标 化或最小化就是线性规划问题的目标 化或最小化就是线性规划问题的目标 化或最小化就是线性规划问题的目标 最后 所有线性规划
15、问题都是在一定的最后 所有线性规划问题都是在一定的最后 所有线性规划问题都是在一定的最后 所有线性规划问题都是在一定的约束条约束条约束条约束条 件件件件下来追求其目标的 例如问题下来追求其目标的 例如问题下来追求其目标的 例如问题下来追求其目标的 例如问题1 1 是在满足生产 是在满足生产 是在满足生产 是在满足生产 需要的一定数量 不同规格的钢管的约束下来追求需要的一定数量 不同规格的钢管的约束下来追求需要的一定数量 不同规格的钢管的约束下来追求需要的一定数量 不同规格的钢管的约束下来追求 原材料钢管的最小使用量 而在问题原材料钢管的最小使用量 而在问题原材料钢管的最小使用量 而在问题原材料
16、钢管的最小使用量 而在问题2 2中是在原料中是在原料中是在原料中是在原料 供应量的限制和保证产品成分的含量约束下来追求供应量的限制和保证产品成分的含量约束下来追求供应量的限制和保证产品成分的含量约束下来追求供应量的限制和保证产品成分的含量约束下来追求 最大利润的 最大利润的 最大利润的 最大利润的 14 解决以下两类问题 资源一定产出最大 产出 如产量 销售量 利润等 任务一定投入最小 投入 如资金 人员 时间 原材料等 第二章 线性规划的图解法 15 线性规划的数学模型的一般形式为线性规划的数学模型的一般形式为 目标函数 max min Z c1x1 c2x2 cnxn 约束条件 a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm x1 x2 xn 0 16 1 要正确理解所要解决的问题 要搞清在什么条件下 追求 什么样的目标 要正确理解所要解决的问题 要搞清在什么条件下 追求 什么样的目标 2 定义决策变量 每一个问题都用一组决策变量 定义决策变量 每一个问题都用一组决策变量 X1 X2 Xn 表示任何一个方