运筹学课设教材

1、运筹学基础课程设计题 目：院 系：专 业：姓名学号：指导老师：日 期 ： 年 月桂林电子科技大学课程设计报告用纸摘 要（单独一页）（300 字以上，小四 宋体 1.5 倍行距） 线性规划是运筹学的一个重要分支， 也是决策支持系统最优化数学规划方法 之一，它作为经营管理决策中的数学手段，在当代决策中的应用是非常广泛的。 因为实际决策问题大多是具有多个目标函数的问题， 所以在线性规划中多目标线 性规划方法的应用更为广泛。 本论文就是基于多目标线性规划方法， 构建了一个 处理经济管理中多目标决策问题的模型， 探讨了处理参数选择以及目标改进的方 法，并通过两个案例，具体说明了在特定战略约束条件下，应用

2、多目标线性规划 模型，实行企业具体决策的过程。决策者的参与对于多目标线性规划问题的求解是非常重要的， 尤其是表现在 决策者的偏好信息的表述上。那么， 面对实际决策问题的时候， 决策者和分析人 员应该选择哪一种多目标线性规划算法呢 ?是交互式的还是非交互式的呢 ?因为 不同的算法具有不同的特点， 所以不同的算法应该适合于不同的决策问题。 在众 多的多目标线性规划算法中， 单纯形法和目标规划的层次算法是求解应用是最广 泛的。本论文就是用单纯形法和层次算法求解的方法来研究问题的， 通过分析企 业在生产和销售过程的需求， 然后设置偏差变量，统一处理目标和约束。若采用 单纯形法，则第一步要列出初始单纯型

3、表， 第二步确定入基变量， 第三步确定出 基变量， 第四步用入基变量替换出基变量， 进行迭代运算； 若采用层次算法则对 优先因子 p1, p2,p3 ps各层进行逐层优化，从而得出结果。关键词：多目标线性规划，模型，参数选择 , 单纯刑法 , 层次算法桂林电子科技大学课程设计报告用纸Abstract (单独一页)小四 TIMES NEW ROMAN 1.5 倍行距)Goal Programming Application in ProductionManagement ResearchAbstract: Programming (LP) is not only an important bra

4、nch 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 involve

5、d 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 ancase,s

6、pecified enterprises' deceisdse dw ipthro acpplying 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 me

7、thods 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

8、 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桂林电子科技大学课程设计报告用纸目 录 （单独一页）黑体，一级标题四号 二级标题小四）摘要 错误！未定义书签。ABSTRACT. : 31 个人感言 错误！未定义书签。2 引

9、言：目标规划在生产管理中的应用 53.1 目标规划问题数学模型的相关概念 53.1.1 优先因子和权系数 . 53.1.2 目标值与偏差变量 . 63.1.3 绝对约束和目标约束 . 63.1.4 达成函数 . 64 目标规划的应用实例 错误！未定义书签。4.2 用单纯形法求解94.3 用 LINGO解法求解 85 结论 . 错误！未定义书签。桂林电子科技大学课程设计报告用纸2 目标规划在生产管理中的应用 在实际应用中，建立目标规划模型分以下四个步骤： 第一，确定要达到的目标；即企业根据实际情况，制定自己的目标或所要取 得的成果。第二，根据生产要素（生产资料、 人力等资源） 确定决策变量； 一

10、般做法是： 根据实际问题， 把决策系统中的可控因素作为决策变量， 通常用带有不同下标的 英文字母表示，例如用 1 x ， 2 x ，?，n x 表示年终计划中不同种产品的产量。 这些变量应为正值，因为在实际问题中变量所代表的均为实物，不能为负。第三，确定目标函数； 用数学形式表示出来的实际系统的期望目标称为目标 函数。目标规划的目标函数与线性规划的目标函数有所不同， 它一般由优先因子、 与目标的偏差和偏差权值所组成。第四，确定约束条件。 约束条件是指实现系统目标的限制因素， 从整体上看， 它可分为系统约束和目标约束，对于具体的问题它可以是生产力约束，原材料、 能源约束，库存水平约束等 7 。3

11、 目标规划问题的数学模型3.1目标规划问题数学模型的相关概念3.1.1 优先因子和权系数虽然在决策者心中的目标有若干个， 但是这些目标的主次轻重是不 尽相同的，因此需要把这些目标的重要程度进行排序，把这些目标分出轻重 缓急，决定哪个目标是第一位的，必须首先满足；哪个是第二位的，在一个 目标满足的条件下尽量满足 .这就引入了优先因子 Pl 的概念 .按其重要程度 , 我们确定各个目标的优先因子 P1，P2，P3这里 Pk>>Pk 1,即Pk对应的目标 比 Pk 1 对应的目标有绝对的优先性。在决策时，只有较高的优先因子对应的 目标满足的前提下，才能考虑较低因子对应的目标。对于优先因子

12、相同的目桂林电子科技大学课程设计报告用纸标，如果他们的重要程度仍有一定的差别， 就用权系数 W 来表示他们的重要 程度。3.1.2 目标值与偏差变量对于每一个决策目标， 都预先给定一个期望值， 称为目标值。 目标 的决策值与目标值之间会存在一定偏差，这个偏差就用偏差变量 d 和 d 来 表示，其中 d 表示决策值超目标值的部分， d 表示决策值不足目标值的部 分。显然， d0，d 0，且 d * d =0。绝对约束和目标约束在约束条件中， 必须绝对满足的约束条件称为绝对约束。 对于某些 条件，我们提出其目标值，希望他们尽量满足这些目标值，但允许他们能够 偏离这个目标值，这样的约束称为目标约束，

13、比绝对约束柔性更强些。3.1.4 达成函数目标规划的目标函数称为达成函数， 有个目标约束的偏差变量及相 应的优先因子和权系数构成。因为目标规划追求的是个目标尽量达到其目标 值，也就是期望有关偏差变量尽量小，具体而言，通常有以下三种形式： minf （ d ） ：表示希望某个目标不超过其期望值；minf （ d ） 表示希望某个目标不少于其期望值； minf （ d +d ）表示希望某个目标刚好达到其期望值 4 。3.2 目标规划的一般模型及求解 目标规划法是线性规划的发展和推广，是综合考虑多目标评价值，在满 足限制条件下使其偏差最小化的一种方法，在模型上与线性规划的模型有很 大的差别：一般地，

14、线性规划的模型如下：maxZ a1x1 a2x2 a3x3anxnnaij xj （ , ）bj （i 1,2, ,m） 1-1j1( j 1,2, n)桂林电子科技大学课程设计报告用纸显然，从上述模型我们可看出，线性规划模型存在着下面的局限性： 第一，所求问题的解必须满足全部初始条件； 第二，只能处理单目标的优化问题； 第三，各个约束条件都处于同等重要的地位； 第四，寻求最优解，但很多实际问题中只要求出满意解就可以了。而一般的目标规划的模型如下：KLm i nzPk ( wkl dl wkl dl ) (a)k 1 l 1naij xj ( , )bj(i 1,2, ,m) (b)j1nc(

15、l) xj dl dlgl (l 1,2, L) (c)1-2j1xj 0 ( j 1,2, n)(d)dl ,dl0 (l 1,2, L) (e)其中， Pk为第 k级优先因子（ k 1,2, ,K ），且 P1 P2 P3d 超出目标的差值，正偏差变量；d 未达到目标的差值，负偏差变量；当实际值超出目标值时： d 0, d0；当实际值未达到目标值时： d 0, d 0；当实际值等于目标值时： d 0, d0，因此： d * d =0；wkl ,wkl 赋予第 l 个目标约束的正负偏差变量权系数；g ：第 l 个目标的预期值， l 1,2,., L；（b）为系统约束，（c）为目标约束对比而言

16、，模型 1-1 和 1-2 无论在目标函数、约束条件等方面都存在很 大的差异，显然，目标规划通过下面几个方面来解决上述线性规划模型中的桂林电子科技大学课程设计报告用纸局限性：1、设置偏差变量 d 和 d ，用来表明实际值同目标值之间的差异。2、统一处理系统约束和目标约束， 对资源使用上有严格限制的建立系统 约束，数学形式上为严格的等式或不等式（式（ b），对不严格限定的约束， 连同原线性规划模型的目标，通过目标约束表达 4 。3、增加了目标的优先级与权系数。 在模型中， 对属于同一层次优先级的 不同目标，按其重要程度可分别乘上不同的权系数，权系数越大，表示目标 越重要。目标规划求解的方法有图解

17、法、序贯式算法、单纯形法等，一般的操作 是：建立模型后，先输入数据进行计算，看目标的满足程度如何，在所有预 定目标都能满足的情况下，所求的解即为最优解，如果目标不能全部满足， 调整目标，继续代入数据寻优，直到所有目标都能满足为止。4.1 目标规划的应用实例例 1 下面是某工厂生产管理的例子，其阐明了目标规划在生产管理中的具 体应用。光明机械厂利用原材料和现有设备可以生产甲、乙两种型号的推土机。 生产一辆甲型推土机需要消耗 2单位原材料，乙需要消耗 1单位原材料 .生产甲 乙两种型号推土机占用设备分别为 1 台时和 2 台时；原材料库存为 11 个单位。 根据订单合同有两种价格标准，甲乙两种机械

18、价格分别为 8、10 万元和 9、4 万 元 .试问怎样确定生产方案 ?现在工厂根据订单和工厂实际情况制定如下工作目标： 根据订单要求，甲型推土机不应低于乙型的数量 超过计划供应的原材料， 需用特别高的价格采购，会使成本大幅度提高，需 注意避免超标；为了保证产品的质量，设备工作的应不低于 10 台时；甲型和乙型数量应不低于 4 台；当甲型和乙型价格为 8、10 万元时，总价值不应多于 56万元； 当甲型和乙型价格为 9、4 万元时，总价值应不低于 36万元。 这些目标可以表示为如下不等式 :桂林电子科技大学课程设计报告用纸x1- x2 02x1 x2 114-1x1 2x2 10 x1 x2

19、4 8x1 10x2 56 9x1 4x2 36这是一个过目标决策问题，可以通过建立目标规划模型来解决此类问题。对于上例的六个目标， 经过讨论得出各个目标的主次轻重意见： 原材料的消耗不得突破限额，乙型推土机的数量必须优先考虑，其次质量须严格把关， 再次是产值指标，最后是甲乙两种推土机的数量原材料的使用是刚性目标， 必须满足。其他几个目标的有限因子分别是：P1P2，P3 ， P4， P5。2x1 x2 11P1x1-x2 0P2x1 2x2 10P38x1 10x2 562-2P49x1 4x2 36P5x1 x2 4目标 2x1 x2 11是必须满足的，是硬性约束；而另外几个目标，我们分别

20、给它设定目标值。 d ， d 分别表示不足和超过的部分。我们可以得到如下目标规划模型：min Z P1d1 P2d2 P3d3 P4d4 P5d52x1 x2 11桂林电子科技大学课程设计报告用纸x1 x2 d1 d1 0 x1 2x2 d2 d2 108x1 10x2 d3 d3 56 2-39x1 4x2 d4 d4 36x1 x2 d5 d5 4x1,x2 0,dk ,dk 0(k 1,2,3,4,5)有目标规划的数学模型的标准型可看出， 它实质上是线性规划模型， 因此可 用单纯形法求解。 因目标规划问题的达成函数都是求最小化， 所以当所有检验数 都满足最优性条件 (cj zj 0)时，

21、即可得出目标规划的解。值得注意的是，在 判别检验数 cj zj 时，应该把目标优先因子 P 理解为一个特殊的正常数，且他 们的关系是 P1 P2PL 。4.2用单纯形法解上例解 引入松弛变量 x3 ，化为如下标准式m i nZ P1d1 P2d2 P3d3 P4d4 P5d52x1 x2 x3 11x1 x2 d1 d1 02-4x1 2x2 d2 d2 108x1 10x2 d3 d3 569x1 4x2 d4 d4 36 x1 x2 d5 d5 4x1,x2,x3 0,dk ,dk 0(k 1,2,3,4,5)1. 以x3， d1 ，d2 ， d3 ，d4 ， d5 为基变量，建立初始单纯

22、形表，求出 检验数 cj zj 。将检验数中的优先因子 Pl 按从高到低的顺序分离出来， 表中另桂林电子科技大学课程设计报告用纸外列出各优先因子的系数。2.若检验数都为非负，则得到满意解，停止。若存在检验数小于0，则选择最小的检验数，对应的变量为换入变量。 与线性规划的单纯形法相同， 按最小非 负比值规则确定换出变量。3.当所有检验数都为非负，且不存在检验数为 0 的非基变量，因此得到唯一 满意解： x=2,x=4。此时， d1 ，d2 ，d3 都为 0，因此该满意解满足了前 3级 目标； d4 =20，所以该解没有满足第四级目标，而 d5 =0，可见该解满足了第 5 级目标。4.3 层次算法

23、解决目标规划问题其算法的步骤如下 :第一步 :先对目标函数中的 p1层次进行优化 ,建立起第一层次的线性规划模L型 LP1 , LP1 的目标函数为 min z1(w1l d1 w1l d1 ) ,再包括约束条件各式。l1第二步：接着对 p2 层进行优化根据下一层次优化时应在前面各层次优化基 础上进行的要求，若第一曾粗目标函数最优值为 z1* ，则构建的 p2层次的线性规 L划模型 LP2 ，其目标函数为 min z2(w2ld2 w2ld2 ) ，其约束条件包括第一层次l1的约束条件，还要加上 w1ld1 w1ld1 z1*第三步：以此类推得到 ps s 2 层次进行优化时建立的线性规划模型

24、 LPsLmin zs(wslds wslds )l1naij xj ( , )bj(i 1,2, ,m) (b)j1nc(l) xj dl dlgl (l 1,2, L) (c)j1xj 0 ( j 1,2, n)(d)桂林电子科技大学课程设计报告用纸dl ,dl 0 (l 1,2, L)(e)本题中用层次算法建立得到模型为：minZ P1d1 P2d2 P3d3 P4d4 P5d52x1 x2 11x1 x2 d1 d1 02-4x1 2x2 d2 d2 108x1 10x2 d3 d3 569x1 4x2 d4 d4 36 x1 x2 d5 d5 4x1,x2 0,dk ,dk 0(k

25、1,2,3,4,5)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.000000Infeasibilities:0.000000Total solver iterations: 0VariableValueReduced Cos

26、tD120.0000001.000000X10.0000000.000000X211.000000.000000D1111.000000.000000桂林电子科技大学课程设计报告用纸D210.0000000.000000D2212.000000.000000D310.0000000.000000D3254.000000.000000D410.0000000.000000D428.0000000.000000D510.0000000.000000D527.0000000.000000RowSlack or SurplusDual Price10.000000-1.00000020.0000000

27、.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.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

28、value:0.000000Infeasibilities:0.000000Total solver iterations: 0VariableValueReduced CostD210.0000001.000000X13.6666670.000000X23.6666670.000000D110.0000000.000000D120.0000000.000000D221.0000000.000000D310.0000000.000000D3210.000000.000000桂林电子科技大学课程设计报告用纸D410.0000000.000000D4211.666670.000000D510.00

29、00000.000000D523.3333330.000000RowSlack or SurplusDual Price10.000000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.000000建立如下 Lingo 模型第三步：求第三级目标的最优解，model : min =d32;2*x1+x2=11; x1-x2+d11-d12=0; x1+2*x2+d21-d22=10; 8*x1+10*x

30、2+d31-d32=56; 9*x1+4*x2+d41-d42=36; x1+x2+d51-d52=4;d12=0;d21=0;end运行的结果为 :Global optimal solution found.10.000000.0000000Objective value:Infeasibilities:Total solver iterations:VariableValueReduced CostD3210.000000.000000X13.6666670.000000X23.6666670.000000D110.0000004.000000D120.0000000.000000D210

31、.0000000.000000桂林电子科技大学课程设计报告用纸D221.0000000.000000D310.0000001.000000D410.0000000.000000D4211.666670.000000D510.0000000.000000D523.3333330.000000RowSlack or SurplusDual Pri110.00000-1.00000020.000000-6.00000030.0000004.00000040.0000000.00000050.0000001.00000060.0000000.00000070.0000000.00000080.0000

32、004.00000090.0000000.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.0.0000000.000000Objective value:Infeasibilities:Total solver i

33、terations:VariableValueReduced CostD410.0000001.000000X13.6666670.000000X23.6666670.000000D110.0000000.000000D120.0000000.000000桂林电子科技大学课程设计报告用纸D210.0000000.000000D221.0000000.000000D310.0000000.000000D3210.000000.000000D4211.666670.000000D510.0000000.000000D523.3333330.000000RowSlack or SurplusDual

34、 Price10.000000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.00000090.0000000.000000100.0000000.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.0.0000000.0000000Objective value: Inf