资源分配问题运筹学试验报告

实验报告 实验课程名称：资源分配问题 实验地点： ______________ 20162016 年 5 5 月至 20162016 年 6 6 月 专 班 业 ____________ 级 ___________ 学生姓名 __________________ 学号 指导老师 ______________ 实验报告 实验项目：B15201301B15201301 实验学时：4 4 学时 实验日期：20152015 年 5 5 月到 6 6 月 实验要求：梳理资源分配问题的产生时间、背景，清楚资源分配问题的原理及方法，运用这个方法 解决一个实 际问题。 实验内容：资源分配问题 1 1 资源分配问题的产生 1.11.1 资源分配问题的产生时间 由于资源分配问题的复杂性和明显的递阶结构特征，资源分配问题需要用两层模型 来描 述。Cassidy等人首次建立了一类两层次多部门资源分配问题的两层规划模型。该模 型是按照正向主从策略、并假定下级各部门之间是相互独立的、平等的。仲伟俊等人[1]在 此 基础上研究了下级之间具有合作关系的资源分配问题。杜纲等人 [1] (1997)建立了资源 分配问题的层次激励模型，张晋东等人[2](2002)基于主从结构的分析框架建立了资源分 配问 题的变权激励模型，提出了与之相应的变权激励策略。这些模型反映了资源分配本 身决策变 量的层次性和相互之间的联系。但对于本文所提到的系统复杂性的定量描述还 需要进行进一 步的研究，两层决策理论及有关算法就是描述这类问题重要而基本的工具。 基于以上背景， 本文选择了资源分配问题的两层决策模型进行研究，以期使资源分配问 题的研究更符合现 实，具有一般性。 1.21.2 资源分配问题的产生背景 资源作为工程实施和生产活动等企业管理的基本要素，是企业所能控制的并能用以 制定 和实施战略或方案、以提高效率和效果的因素，资源获得数量的多少和资源的利用 情况直接影 响着企业的经济目标，因此，每一个生产企业或工程实体都希望能够获得更 多的资源，以实现 他们的目标。然而，在实际工程建设和生产中，在一定的时间内，由于各方面的原因，所得到 的资源总是有一定限度的，若不加考虑地使用资源，直接的后 果是造成生产成本增加、工程费 用提高等，在资源极其短缺的情况下，还会造成工程各部门或生产各单位忙乱争夺资源的现 象，从而导致无法取得最佳经济目标，造成资源的 浪费。为了充分地利用现有资源，以获得最 优经济成果，于是就产生了如何分配以使工 程目标或生产目的达到最优的问题。 2.2.原理及方法 2.12.1 两层决策描述 一般的两层决策方法是一种具有递阶结构的系统优化方法。它包含一个上层问题和 多个 下层问题，上层问题和下层问题都有各自的目标函数和约束条件。上层问题的目标 函数和约束 条件不仅与上层决策变量有关，而且还依赖于下层问题的最优解，而下层问 题的最优解又受上 层决策变量的影响。一般上层决策者处于一个领导和协调下层各执行 部门的地位，而下层各决 策者处于执行地位。 在决策中， 上层决策者有权首先确定他的决策方案， 并将该信息传递给下层各执行 部门。 决策方案的满意与否是由上层决策者根据其自身的目标函数决定的。两层决策方法所描述决 策问题的决策过程是上层决策者首先宣布它的决策，这一决策将影响下层决策问题的约束集 和目标函数。然后下层各决策者在这种限制下选取使自己的目标函数最 优的决策，它也影响上 层决策问题的目标函数， 上层决策者再调整它的决策变量的取值， 该过程不断进行，直至上 层目标函数达到最优为止。国内外对两层决策方法的研究大多限于从理论的角度建立不同的 两层决策，模型的基础上研究各种算法，将两层决策方法 用于研究解决实际问题还很少见到。 由于两层决策模型的结构和其决策过程恰好体现了多种资源在多个项目间分配问题的递阶优 化结构， 因此都是用于解决一个决策点上的决策问题。 但在实际社会生活中，存在着组织内 包 含多个决策点的复杂决策系统。 这种复杂系统通常具有多级、 递阶结构。 如一个国家 内有中央、 省市及县区等不同的组织管理层次；一个企业内有公司级、厂级、车间级的组织决策层次。在 这种复杂系统中，由于涉及到具有主动行为的多个决策者的决策活动， 系统内部决策的分散化 使各决策部门的责任、权限和利益将有明确的区别。这样，每个 决策者都有自己希望达到的一 个或一组目标。同时，系统中的各个决策部门之间存在各种复杂的相互促进和相互制约的关 系。如果决策者处于系统中的不同的级， 那么处于较 高级的决策部门将具有更大的权利，他通 过一些调控手段来引导下级部门在实现其局部目标的同时，使上级的目标得到尽可能多的满 足。对这样的复杂决策系统， 目前主要针 对两层的，且上层只有一个决策者的情况研究分析它 的模型和决策方法。 2.32.3 资源分配问题的两层决策 任何一个现代化生产系统的决策过程都具有层次性，作为这个系统的上层管理者，总是 企图使整个系统取得最好的效果，而效果的产生是通过具体的资源分配等生产过程 实现的，这 就构成了资源的分配者和资源的使用者的统一体。由于不同的分配方式可能 产生不同的效果， 生产决策者要在上层给出的资源下使效果尽可能最佳。然后，上层管 理者再根据下层的反应在 可能的范围内作出最佳决策。于是，这种生产系统的决策过程 就形成了一个二层系统的决策问 题。这个二’层系统的下层是确定分配方式与生产效果 的对应关系，这个二层系统的上层则是 要根据资源分配方案的效果，在可能范围内，调 整资源分配方案使整个系统产生最好的效果。 这样，资源分配问题本身就明显地具有了 两层递阶结构，根据两层决策的决策机理，可把资源 分配问题抽象成两层决策模型 ： maxV(x, y(x)) x s.t g(x) 0 其中y(x)是使用资源的最佳效果函数。上述模型中，由于使用资源的最佳效果函数，有多 种形式，因此，有必要进一步明确上述模型的意义。本文对使用资源的最佳效果函数采用两种 目标，一是以资源有限最大经济价值为目标， 二是以最小工期为目标。由于 资源的分配者分配 资源的方案也有多种分配后产生的效果，因此，本文对分配方案的目 标采用相对于最大经济价 值来说资源总量最小。在工程应用领域，采用相对于最小工期 而言，整个工期的拖期最小为目 标。 43.43.应用实例 设上层总厂有 m 种可连续变化的资源要分配给下层 p 个项目，每个项目中有用个 活动 用到 m 种共享资源，且每个活动只用到一种共享资源。下层每个项目拥有各自的 自有资源。 为简化问题，在此不考虑每个项目中自有资源的分配，假定下层各项目中使 用自有资源的活动所需自有资源量均能满足，且活动持续时间不变，使用共享资源的活 动持续 时间由所分配到的资源量决定。 设使用共享资源的活动持续时间与资源分配量成反比关系如2 台机器干 6 天，4 台 机器就干 3 天。那么活动持续时间=活动工作量量源量。 上层以 p 个项目均在各自的预定工期内完成，消耗的共享资源总量最小为目标，下 层 p 个项目都以工期最短为目标。下层各项目的进度计划分别用网络计划表示。 为了便 于将下层 求最短工期问题用线性规划表示，在此用双代号网络图表示下层