运筹学基础课程设计.doc

运筹学基础运筹学基础运筹学基础 课程设计课程设计课程设计 题 目 院 系 专 业 姓名学号 指导老师 日 期 年 月 日 桂林电子科技大学课程设计报告用纸 摘 要 单独一页 300 字以上 小四 宋体 1 5 倍行距 线性规划是运筹学的一个重要分支 也是决策支持系统最优化数学规划方 法之一 它作为经营管理决策中的数学手段 在当代决策中的应用是非常广泛 的 因为实际决策问题大多是具有多个目标函数的问题 所以在线性规划中多 目标线性规划方法的应用更为广泛 本论文就是基于多目标线性规划方法 构 建了一个处理经济管理中多目标决策问题的模型 探讨了处理参数选择以及目 标改进的方法 并通过两个案例 具体说明了在特定战略约束条件下 应用多 目标线性规划模型 实行企业具体决策的过程 决策者的参与对于多目标线性规划问题的求解是非常重要的 尤其是表现 在决策者的偏好信息的表述上 那么 面对实际决策问题的时候 决策者和分 析人员应该选择哪一种多目标线性规划算法呢 是交互式的还是非交互式的呢 因为不同的算法具有不同的特点 所以不同的算法应该适合于不同的决策问题 在众多的多目标线性规划算法中 单纯形法和目标规划的层次算法是求解应用 是最广泛的 本论文就是用单纯形法和层次算法求解的方法来研究问题的 通 过分析企业在生产和销售过程的需求 然后设置偏差变量 统一处理目标和约 束 若采用单纯形法 则第一步要列出初始单纯型表 第二步确定入基变量 第三步确定出基变量 第四步用入基变量替换出基变量 进行迭代运算 若采 用层次算法则对优先因子 各层进行逐层优化 从而得出结果 123 p pp s p 关键词关键词 多目标线性规划 模型 参数选择 单纯刑法 层次算法 桂林电子科技大学课程设计报告用纸 Abstract 单独一页 单独一页 小四 TIMES NEW ROMAN 1 5 倍行距 Goal Programming Application in Production Management Research Abstract Abstract Programming LP is not only an important branch of operational research but also one of the optimization mathematical programming methods in DSS As a mathematical measure LP is applied to management decision making widely The application of Multiple Objective Linear Programming MOLP is wider because there are much more problems involved multiple objective functions This thesis base on the multiple ob jective linear programming amodelwas established in this paper for deal ing with the problems of multiple objective decisions making and the method of parameter selection and objective improcement was discussed At last by an case specified enterprises decided process with applying the multiple objective linear programming decisions making model DM s participation is important to solving the MOLP problems especially some preference information given from the DM The DM and analyst have to select one from many MOLP methods when they solve some MOLP problems So which kind of methods should be chosen and how to select one from so many methods Because different methods have different characteristics different methods should apply to different practical problems Among the many multi objective linear programming algorithm the simplex method is the most widely used applications This paper is to use simplex method approach to research questions Key words multiple objective linear programming model parameter 桂林电子科技大学课程设计报告用纸 selection 目 录 单独一页 黑体 一级标题四号 黑体 一级标题四号 二级标题小四 二级标题小四 摘要 I ABSTRACT II 1 个人感言 1 2 引言 目标规划在生产管理中的应用 5 3 1 目标规划问题数学模型的相关概念 5 3 1 1 优先因子和权系数 5 3 1 2 目标值与偏差变量 5 3 1 3 绝对约束和目标约束 5 3 1 4 达成函数 6 4 目标规划的应用实例 9 4 2 用单纯形法求解 9 4 3 用LINGO解法求解 9 5 结论 17 桂林电子科技大学课程设计报告用纸 2 目标规划在生产管理中的应用 在实际应用中 建立目标规划模型分以下四个步骤 第一 确定要达到的目标 即企业根据实际情况 制定自己的目标或所要 取得的成果 第二 根据生产要素 生产资料 人力等资源 确定决策变量 一般做法 是 根据实际问题 把决策系统中的可控因素作为决策变量 通常用带有不同 下标的英文字母表示 例如用 1 x 2 x n x 表示年终计划中不同种产品 的产量 这些变量应为正值 因为在实际问题中变量所代表的均为实物 不能 为负 第三 确定目标函数 用数学形式表示出来的实际系统的期望目标称为目 标函数 目标规划的目标函数与线性规划的目标函数有所不同 它一般由优先 因子 与目标的偏差和偏差权值所组成 第四 确定约束条件 约束条件是指实现系统目标的限制因素 从整体上 看 它可分为系统约束和目标约束 对于具体的问题它可以是生产力约束 原 材料 能源约束 库存水平约束等 7 3 目标规划问题的数学模型 3 1 目标规划问题数学模型的相关概念 3 1 1 优先因子和权系数 虽然在决策者心中的目标有若干个 但是这些目标的主次轻重是 不尽相同的 因此需要把这些目标的重要程度进行排序 把这些目标分出轻 重缓急 决定哪个目标是第一位的 必须首先满足 哪个是第二位的 在一 个目标满足的条件下尽量满足 这就引入了优先因子的概念 按其重要程 l P 度 我们确定各个目标的优先因子 这里 即对应的目 1 P 2 P 3 P k P 1k P k P 标比对应的目标有绝对的优先性 在决策时 只有较高的优先因子对应 1k P 桂林电子科技大学课程设计报告用纸 的目标满足的前提下 才能考虑较低因子对应的目标 对于优先因子相同的 目标 如果他们的重要程度仍有一定的差别 就用权系数 W 来表示他们的 重要程度 3 1 2 目标值与偏差变量 对于每一个决策目标 都预先给定一个期望值 称为目标值 目 标的决策值与目标值之间会存在一定偏差 这个偏差就用偏差变量和 d 来表示 其中表示决策值超目标值的部分 表示决策值不足目标值 d d d 的部分 显然 0 0 且 0 d d d d 3 1 3 绝对约束和目标约束 在约束条件中 必须绝对满足的约束条件称为绝对约束 对于某 些条件 我们提出其目标值 希望他们尽量满足这些目标值 但允许他们能 够偏离这个目标值 这样的约束称为目标约束 比绝对约束柔性更强些 3 1 4 达成函数 目标规划的目标函数称为达成函数 有个目标约束的偏差变量及 相应的优先因子和权系数构成 因为目标规划追求的是个目标尽量达到其目 标值 也就是期望有关偏差变量尽量小 具体而言 通常有以下三种形式 min f 表示希望某个目标不超过其期望值 d min f 表示希望某个目标不少于其期望值 d min f 表示希望某个目标刚好达到其期望值 4 d d 3 2 目标规划的一般模型及求解 目标规划法是线性规划的发展和推广 是综合考虑多目标评价值 在满 足限制条件下使其偏差最小化的一种方法 在模型上与线性规划的模型有很 大的差别 一般地 线性规划的模型如下 nnx axaxaxaZ 332211 max 1 1 j n j jij bxa 1 2 1 mi 桂林电子科技大学课程设计报告用纸 0 j x 2 1 nj 显然 从上述模型我们可看出 线性规划模型存在着下面的局限性 第一 所求问题的解必须满足全部初始条件 第二 只能处理单目标的优化问题 第三 各个约束条件都处于同等重要的地位 第四 寻求最优解 但很多实际问题中只要求出满意解就可以了 而一般的目标规划的模型如下 a min 11 lkll L l kl K k k dwdwPz b j n j jij bxa 1 2 1 mi c 1 2 lllj n j l gddxc 1 2 1 Ll d 0 j x 2 1 nj e 0 ll dd 2 1 Ll 其中 为第级优先因子 且 k PkKk 2 1 321 PPP 超出目标的差值 正偏差变量 d 未达到目标的差值 负偏差变量 d 当实际值超出目标值时 0 0 d d 当实际值未达到目标值时 0 0 d d 当实际值等于目标值时 0 0 因此 0 d d d d klkl ww 赋予第 l 个目标约束的正负偏差变量权系数 g 第 l 个目标的预期值 1 2 L l b 为系统约束 c 为目标约束 对比而言 模型 1 1 和 1 2 无论在目标函数 约束条件等方面都存在很 桂林电子科技大学课程设计报告用纸 大的差异 显然 目标规划通过下面几个方面来解决上述线性规划模型中的 局限性 1 设置偏差变量和 用来表明实际值同目标值之间的差异 d d 2 统一处理系统约束和目标约束 对资源使用上有严格限制的建立系 统约束 数学形式上为严格的等式或不等式 式 b 对不严格限定的约 束 连同原线性规划模型的目标 通过目标约束表达 4 3 增加了目标的优先级与权系数 在模型中 对属于同一层次优先级 的不同目标 按其重要程度可分别乘上不同的权系数 权系数越大 表示目 标越重要 目标规划求解的方法有图解法 序贯式算法 单纯形法等 一般的操作 是 建立模型后 先输入数据进行计算 看目标的满足程度如何 在所有预 定目标都能满足的情况下 所求的解即为最优解 如果目标不能全部满足 调整目标 继续代入数据寻优 直到所有目标都能满足为止 4 1 目标规划的应用实例目标规划的应用实例 例 1 下面是某工厂生产管理的例子 其阐明了目标规划在生产管理中的具 体应用 光明机械厂利用原材料和现有设备可以生产甲 乙两种型号的推土机 生产一辆甲型推土机需要消耗 2 单位原材料 乙需要消耗 1 单位原材料 生产甲 乙两种型号推土机占用设备分别为 1 台时和 2 台时 原材料库存为 11 个单位 根据订单合同有两种价格标准 甲乙两种机械价格分别为 8 10 万元和 9 4 万 元 试问怎样确定生产方案 现在工厂根据订单和工厂实际情况制定如下工作目标 根据订单要求 甲型推土机不应低于乙型的数量 超过计划供应的原材料 需用特别高的价格采购 会使成本大幅度提高 需注意避免超标 为了保证产品的质量 设备工作的应不低于 10 台时 甲型和乙型数量应不低于 4 台 当甲型和乙型价格为 8 10 万元时 总价值不应多于 56 万元 当甲型和乙型价格为 9 4 万元时 总价值应不低于 36 万元 桂林电子科技大学课程设计报告用纸 这些目标可以表示为如下不等式 1 x 2 x 0 112 21 xx 102 21 xx 4 1 4 21 xx 56108 21 xx 3649 21 xx 这是一个过目标决策问题 可以通过建立目标规划模型来解决此类问题 对于上例的六个目标 经过讨论得出各个目标的主次轻重意见 原材料的 消耗不得突破限额 乙型推土机的数量必须优先考虑 其次质量须严格把关 再次是产值指标 最后是甲乙两种推土机的数量 原材料的使用是刚性目标 必须满足 其他几个目标的有限因子分别是 1 P 2 P 3 P 4 P 5 P 112 21 xx 1 P 1 x 2 x 0 2 P 102 21 xx 3 P 56108 21 xx 2 2 4 P 3649 21 xx 5 P 4 21 xx 目标 112 21 xx 是必须满足的 是硬性约束 而另外几个目标 我们分别 给它设定目标值 d d 分别表示不足和超过的部分 我们可以得到如下目标规划模型 5544332211 mindPdPdPdPdPZ 桂林电子科技大学课程设计报告用纸 112 21 xx 0 1121 ddxx 102 2221 ddxx 56108 3321 ddxx 2 3 3649 4421 ddxx 4 5521 ddxx 5 4 3 2 1 0 0 21 kddxx kk 有目标规划的数学模型的标准型可看出 它实质上是线性规划模型 因此 可用单纯形法求解 因目标规划问题的达成函数都是求最小化 所以当所有检 验数都满足最优性条件 0 jj zc 时 即可得出目标规划的解 值得注意的 是 在判别检验数 jj zc 时 应该把目标优先因子 P 理解为一个特殊的正常数 且他们的关系是 L PPP 21 4 2 用单纯形法解上例 解 引入松弛变量 3 x 化为如下标准式 5544332211 mindPdPdPdPdPZ 112 321 xxx 0 1121 ddxx 102 2221 ddxx 2 4 56108 3321 ddxx 3649 4421 ddxx 4 5521 ddxx 5 4 3 2 1 0 0 321 kddxxx kk 1 以 3 x 1 d 2 d 3 d 4 d 5 d 为基变量 建立初始单纯形表 求出 桂林电子科技大学课程设计报告用纸 检验数 jj zc 将检验数中的优先因子 l P 按从高到低的顺序分离出来 表中 另外列出各优先因子的系数 2 若检验数都为非负 则得到满意解 停止 若存在检验数小于 0 则选择 最小的检验数 对应的变量为换入变量 与线性规划的单纯形法相同 按最小 非负比值规则确定换出变量 3 当所有检验数都为非负 且不存在检验数为 0 的非基变量 因此得到唯 一满意解 x 2 x 4 此时 1 d 2 d 3 d 都为 0 因此该满意解满足了前 3 级目标 4 d 2 0 所以该解没有满足第四级目标 而 5 d 0 可见该解满足 了第 5 级目标 4 3 层次算法解决目标规划问题层次算法解决目标规划问题 其算法的步骤如下 第一步 先对目标函数中的层次进行优化 建立起第一层次的线性规划模 1 p 型 的目标函数为 再包括约束条件各式 1 LP 1 LP 11111 1 min L ll l zw dw d 第二步 接着对层进行优化根据下一层次优化时应在前面各层次优化基 2 p 础上进行的要求 若第一曾粗目标函数最优值为 则构建的层次的线性规 1 z 2 p 划模型 其目标函数为 其约束条件包括第一层 2 LP 22222 1 min L ll l zw dw d 次的约束条件 还要加上 11111ll w dw dz 第三步 以此类推得到层次进行优化时建立的线性规划模型 2 s ps s LP 1 min L sslssls l zw dw d b j n j jij bxa 1 2 1 mi c lllj n j l gddxc 1 2 1 Ll 桂林电子科技大学课程设计报告用纸 d 0 j x 2 1 nj e 0 ll dd 2 1 Ll 本题中用层次算法建立得到模型为 5544332211 mindPdPdPdPdPZ 112 21 xx 0 1121 ddxx 2 4102 2221 ddxx 56108 3321 ddxx 3649 4421 ddxx 4 5521 ddxx 5 4 3 2 1 0 0 21 kddxx kk 1 用lingo程序解 建立第一级目标规划 model min d12 2 x1 x2 11 x1 x2 d11 d12 0 x1 2 x2 d21 d22 10 8 x1 10 x2 d31 d32 56 9 x1 4 x2 d41 d42 36 x1 x2 d51 d52 4 end 运行结果为 Global optimal solution found Objective value 0 000000 Infeasibilities 0 000000 Total solver iterations 0 Variable Value Reduced Cost D12 0 000000 1 000000 X1 0 000000 0 000000 桂林电子科技大学课程设计报告用纸 X2 11 00000 0 000000 D11 11 00000 0 000000 D21 0 000000 0 000000 D22 12 00000 0 000000 D31 0 000000 0 000000 D32 54 00000 0 000000 D41 0 000000 0 000000 D42 8 000000 0 000000 D51 0 000000 0 000000 D52 7 000000 0 000000 Row Slack or Surplus Dual Price 1 0 000000 1 000000 2 0 000000 0 000000 3 0 000000 0 000000 4 0 000000 0 000000 5 0 000000 0 000000 6 0 000000 0 000000 7 0 000000 0 000000 第二步 求第二级目标的最优解 建立如下 Lingo 模型 model min d21 2 x1 x2 11 x1 x2 d11 d12 0 x1 2 x2 d21 d22 10 8 x1 10 x2 d31 d32 56 9 x1 4 x2 d41 d42 36 x1 x2 d51 d52 4 d12 0 end 运行结果为 Global optimal solution found Objective value 0 000000 Infeasibilities 0 000000 Total solver iterations 0 Variable Value Reduced Cost D21 0 000000 1 000000 X1 3 666667 0 000000 X2 3 666667 0 000000 D11 0 000000 0 000000 D12 0 000000 0 000000 D22 1 000000 0 000000 桂林电子科技大学课程设计报告用纸 D31 0 000000 0 000000 D32 10 00000 0 000000 D41 0 000000 0 000000 D42 11 66667 0 000000 D51 0 000000 0 000000 D52 3 333333 0 000000 Row Slack or Surplus Dual Price 1 0 000000 1 000000 2 0 000000 0 000000 3 0 000000 0 000000 4 0 000000 0 000000 5 0 000000 0 000000 6 0 000000 0 000000 7 0 000000 0 000000 8 0 000000 0 000000 第三步 求第三级目标的最优解 建立如下 Lingo 模型 model min d32 2 x1 x2 11 x1 x2 d11 d12 0 x1 2 x2 d21 d22 10 8 x1 10 x2 d31 d32 56 9 x1 4 x2 d41 d42 36 x1 x2 d51 d52 4 d12 0 d21 0 end 运行的结果为 Global optimal solution found Objective value 10 00000 Infeasibilities 0 000000 Total solver iterations 0 Variable Value Reduced Cost D32 10 00000 0 000000 X1 3 666667 0 000000 X2 3 666667 0 000000 D11 0 000000 4 000000 桂林电子科技大学课程设计报告用纸 D12 0 000000 0 000000 D21 0 000000 0 000000 D22 1 000000 0 000000 D31 0 000000 1 000000 D41 0 000000 0 000000 D42 11 66667 0 000000 D51 0 000000 0 000000 D52 3 333333 0 000000 Row Slack or Surplus Dual Price 1 10 00000 1 000000 2 0 000000 6 000000 3 0 000000 4 000000 4 0 000000 0 000000 5 0 000000 1 000000 6 0 000000 0 000000 7 0 000000 0 000000 8 0 000000 4 000000 9 0 000000 0 000000 第四步 求第四级目标的最优解 建立如下 Lingo 模型 model min d41 2 x1 x2 11 x1 x2 d11 d12 0 x1 2 x2 d21 d22 10 8 x1 10 x2 d31 d32 56 9 x1 4 x2 d41 d42 36 x1 x2 d51 d52 4 d12 0 d21 0 d32 10 end 运行结果为 Global optimal solution found Objective value 0 000000 Infeasibilities 0 000000 Total solver iterations 0 Variable Value Reduced Cost D41 0 000000 1 000000 X1 3 666667 0 000000 X2 3 666667 0 000000 桂林电子科技大学课程设计报告用纸 D11 0 000000 0 000000 D12 0 000000 0 000000 D21 0 000000 0 000000 D22 1 000000 0 000000 D31 0 000000 0 000000 D32 10 00000 0 000000 D42 11 66667 0 000000 D51 0 000000 0 000000 D52 3 333333 0 000000 Row Slack or Surplus Dual Price 1 0 000000 1 000000 2 0 000000 0 000000 3 0 000000 0 000000 4 0 000000 0 000000 5 0 000000 0 000000 6 0 000000 0 000000 7 0 000000 0 000000 8 0 000000 0 000000 9 0 000000 0 000000 10 0 000000 0 000000 第五步 求第五级目标的最优解 建立如下 Lingo 模型 model min d51 2 x1 x2 11 x1 x2 d11 d12 0 x1 2 x2 d21 d22 10 8 x1 10 x2 d31 d32 56 9 x1 4 x2 d41 d42 36 x1 x2 d51 d52 4 d12 0 d21 0 d32 10 d41 0 end 运行的结果为 Global optimal solution found Objective value 0 000000 Infeasibilities 0 000000 Total solver iterations 0 桂林电