运筹学规划文章

线性规划模型的公式表示 识别潜在的Lp问题并把它结构化为计算机可解决的形式是一种艺术，这种能力是从经 验中获得的。采用以下的策略有助于用公式表示Lp模型 1. 画出一张含参数与约束的图表，并把问题中的各种关系表示出来。 2. 识别决策变量，并用象征性符号表示决策变量。 3. 用语言描述目标。 4. 把每个约束表达出来，明确右边项，并确定不等式的方向。 5. 用代数式写出模型。先写出目标函数；然后列出右边项，接下来确定不等号；最后在左 边填上每个约束的代数表达式。 6. 注明对决策变量的非负约束。 7. 用可行解来检验问题内在的一致性和完整性。 我们用以下的例子来说明这些指导性原则。 1. 饮食问题 这类问题说明的是如何选配一餐中的各类食物以满足特定的营养要求。各类食物的营养成 分是不同的。我们的目标是选定食物种类并确定其数量，使得成本最小。 例子某个医院的饮食学家正在调配一种特殊的奶昔。这种奶昔是用来作为一种特殊的“治 疗”手段的，帮助儿科患者手术后的康复。饮食学家需要确保，食物中胆固醇不超过175 单位，饱和性脂肪不超过150单位，蛋白质含量不少于200单位，卡路里含量应超过100 单位。饮食学家选择了 3种原料奶油蛋糊、冰激凌和黄油糖浆。一个单位的奶油蛋糊要 花费15美分，可提供50单位的胆固醇，0单位脂肪和30卡的热量，70单位的蛋白质。 一个单位的冰激凌要花费25美分，可提供150单位的胆固醇，100单位脂肪，10单位的 蛋白质和80卡的热量。一个单位的黄油糖浆要花费10美分，可提供90单位的胆固醇， 50单位的脂肪，0单位蛋白质和200卡的热量。要使总成本最小，奶昔中应包含每种原料 各多少单位 营养成分 奶油蛋糊 冰激凌 黄油糖浆 营养要求 胆固醇 50 150 90 W175 脂肪 0 100 50 W150 蛋白质 70 10 0 200 卡路里 30 80 200 100 单位成本（美分） 15 25 10 由问题可知，有如下的决策变量 令E--奶昔中的奶油蛋糊含量； C--奶昔中的冰激凌含量； S--奶昔中的黄油糖浆含量。 我们的目标是使奶昔的总成本最小。由上表中列出的各个约束条件胆固醇含量小于或等 于175单位，脂肪含量小于或等于150单位，蛋白质含量大于或等于200单位，卡路里含 量大于或等于100单位。该模型的代数表达式如下 最小化0.15E0.25C0.10S 约束50E150C90S175胆固醇 100C50S150 脂肪 70E10C200蛋白质 30E80C200S100 卡路里 E, C, S0 根据所列公式，仅使用奶油蛋糊可以是该问题的一个解（即E3.5, C0, S0）但这样 得到的东西称不上是奶昔，因此该问题还应加上一些附加条件以排除这种情况的发生。 2. 排班次问题 这个问题说明的是在服务需求发生变化的一段时间内，如何指派工作人员。我们的目标是 安排最少的人数来满足这段时期内的需要。 例子纽约的警察巡逻问题。由于有预算的约束，不可能雇佣新的警察，所以纽约的地方 警察专员必须尽量利用现有的警力。在平时的一天里警察巡逻的需求如下 时段 时间 巡逻警官数（最低限） 1 午夜12点〜凌晨4点 6 2 凌晨4点早8点 4 3 早8点正午12点 14 4 正午12点下午4点 8 5 下午4点晚8点 12 6 晚8点4夜12点 16 根据指派，巡逻警官每两人坐一辆巡逻车，每班工作8小时。目前的情况是，巡警可以在 午夜12点、早8点、下午4点3个时候报到上班。专员认为如果允许巡警在早4点、正 午12点、下午8点也能报到上班，在人员的使用上能够由更好的效果。当然，这就需要 一些警官在工作4小时后更换搭档。在每一个报到时点上，各应有多少警官开始他们8小 时班的工作人员的指派必须使所需的警官总数最小但却能满足最低的人员需要。目前的 安排会造成人员过剩，原因是实行8小时一班，每天3个报到时刻（也即xl6, x314, x516）。 这个人员安排问题的决策变量可确定如下 令xi在时段i值勤的警官数il,2,3,4,5,6 现在的问题是，在满足每4小时间隔期间对人员的最低需求量的条件下，使总的巡警数量 最小。在列出该模型的代数表达式的时候还应该考虑到一个暗含的约束条件当一名警官 报到上班后，他或她就应持续地工作8小时。 最小化 xlx2x3x4x5x6 约束 xlx6 6 时段1 xlx24时段 2 x2x3 14时段 3 x3x4 8时段 4 x4x5 12时段 5 x5x6 16时段 6 注意由于8小时一班, 每个决策变量只在两个约束条件中出现。例如，因为每个时段持续 4小时，在凌晨4点报到上班的警官（即x2）应上满时段2和时段3。因为我们求解的是 巡警的人数，所以决策变量必须限制为整数。本问题由于本身的构造，该LP模型的解是 整数解。但一般来说，LP的解是非负的实数（包括整数和分数）。 3. 员工计划问题 雇员的离职在服务行业中是普遍存在的。例如银行出纳员和飞机上的服务员就经常离职。 而且，新的雇员在为公众服务之前需要有一个培训期。由于顾客需求的变化，所需要的人 员配备水平也要随之变化，例如在夏季和节假日期间对乘飞机旅行的需求量会上升。员工 计划包括确定在什么时候需要招募多少人，以满足将来的人员配备需要并补上离职人员的 空缺。其目标是在一种动态的背景下来满足人员的配备需要，并使总的人事费用最小。 例子某个银行必须作出决定，在接下来的6个月里应雇佣和培训多少新的出纳员。出纳 的需要量以所需的出纳员工时数来衡量。各月的需要分别为1月份1500, 2月份1800, 3月份1600, 4月份2000, 5月份1800, 6月份2200。出纳员上岗之前，必须要经过1个 月的培训，因此，必须在时间需要的一个月前雇佣他们。并且，在一个月的培训期中，受 训者需要有80小时的模拟工作经历，这个过程是在正式出纳员的指导下进行的。因此， 每有一个受训者就要使一个正式出纳员的实际工作时间减少80小时。不管是否有需要， 每个熟练出纳员每月工作160小时。1月初，在该银行中有12个熟练的出纳员可供使用。 过去的经验表明，在每个月的月底都会有约10的熟练出纳员离职。正式的出纳员每月的 薪水是600美元，而受训者在一个月的受训期间可得到300美元。在接下来的6个月中， 每月需要雇佣多少出纳员 该模型决策变量是每个阶段雇佣的受训者数和各阶段初可使用的出纳员数。 令Tt阶段t之初雇佣的受训者数 tl,2,3,4,5,6 At阶段t之初可使用的出纳员数tl,2,3,4,5,6 其目标是使6个月的计划期内总的人事费用最小。这里需要两套约束条件。其一是6个月 中每个月所要求的出纳工时数；另一个是，从第二个月起，在推算从某月到下一月可用出 纳员数时，要考虑到新雇