运筹学规划文章
线性规划模型的公式表示
识别潜在的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卡的热量。要使总成本最小，奶昔中应包含每种原料各多少单位？
由问题可知，有如下的决策变量：
令 E--奶昔中的奶油蛋糊含量；
C--奶昔中的冰激凌含量；
S--奶昔中的黄油糖浆含量。
我们的目标是使奶昔的总成本最小。由上表中列出的各个约束条件：胆固醇含量小于或等于175单位，脂肪含量小于或等于150单位，蛋白质含量大于或等于200单位，卡路里含量大于或等于100单位。该模型的代数表达式如下：
最小化 0.15E+0.25C+0.10S
约束 50E+150C+90S≤175 胆固醇
100C+50S≤150 脂肪
70E+10C≥200 蛋白质
30E+80C+200S≥100 卡路里
E，C，S≥0
根据所列公式，仅使用奶油蛋糊可以是该问题的一个解（即E=3.5，C=0，S=0）。但这样得到的东西称不上是奶昔，因此该问题还应加上一些附加条件以排除这种情况的发生。
2. 排班次问题
这个问题说明的是在服务需求发生变化的一段时间内，如何指派工作人员。我们的目标是安排最少的人数来满足这段时期内的需要。
例子：纽约的警察巡逻问题。由于有预算的约束，不可能雇佣新的警察，所以纽约的地方警察专员必须尽量利用现有的警力。在平时的一天里警察巡逻的需求如下：
根据指派，巡逻警官每两人坐一辆巡逻车，每班工作8小时。目前的情况是，巡警可以在午夜12点、早8点、下午4点3个时候报到上班。专员认为如果允许巡警在早4点、正午12点、下午8点也能报到上班，在人员的使用上能够由更好的效果。当然，这就需要一些警官在工作4小时后更换搭档。在每一个报到时点上，各应有多少警官开始他们8小时班的工作？人员的指派必须使所需的警官总数最小但却能满足最低的人员需要。目前的安排会造成人员过剩，原因是实行8小时一班，每天3个报到时刻（也即：x1=6，x3=14，x5=16）。
这个人员安排问题的决策变量可确定如下：
令xi=在时段i值勤的警官数 i=1,2,3,4,5,6
现在的问题是，在满足每4小时间隔期间对人员的最低需求量的条件下，使总的巡警数量最小。在列出该模型的代数表达式的时候还应该考虑到一个暗含的约束条件：当一名警官报到上班后，他或她就应持续地工作8小时。
最小化 x1+x2+x3+x4+x5+x6
约束 x1+x6≥ 6 时段1
x1+x2≥ 4 时段2
x2+x3≥ 14 时段3
x3+x4≥ 8 时段4
x4+x5≥ 12 时段5
x5+x6≥ 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之初雇佣的受训者数 t=1,2,3,4,5,6
At=阶段t之初可使用的出纳员数 t=1,2,3,4,5,6
其目标是使6个月的计划期内总的人事费用最小。这里需要两套约束条件。其一是6个月中每个月所要求的出纳工时数；另一个是，从第二个月起，在推算从某月到下一月可用出纳员数时，要考虑到新雇员数和离职数。下面的数学模型运用了一些速记代数符号。 最小化
约束 160A1-80T1 ≥1500 1月
160A2-80T2 ≥1800 2月
160A3-80T3 ≥1600 3月
160A4-80T4 ≥2000 4月
160A5-80T5 ≥1800 5月
160A6-80T6 ≥2200 6月
A1=12
0.9At-1+Tt-1-At=0 t=2,3,4,5,6
Tt ，At≥0且为整数 t=1,2,3,4,5,6
注意在使用这个模型时，只有1月份的雇佣人数可以直接得到。其他月份的雇佣人数可当作现在对未来的预计处理。在2月份开始之前，再次运用该模型时，应去掉1月份的需求并加上7月份的需求。运用这种方法，每一次雇员决策都是在满足6个月计划要求的基础
上作出的，这样可对员工的规模进行渐进的调整。决策变量必须限定为整数。但在本例子中，问题的构造并不却确保解一定是整数。这个问题表现的是一类特殊的线性规划模型，即整数规划。解整数规划需要一种特殊的计算机代码以确保结果是整数。
4. 运输问题
运输问题是一类特殊的LP模型，又称网络模型。这个问题的构造可以确保解是整数。问题的实质是把货物从起点运到终点，或从供应地运向需求地。每一个终点有一个特定的需求，而每一个起点有一个特定的供给。起点数与终点并不一定相等。为了解决问题的方便，可以虚设起点或终点以平衡需求和供给。从每一个起点到终点货物的单位运费是既定的，我们的目标是使总的运费最小。
例子：某个租车行重新分配它在各个地区的租车数目。在以下地区存在过剩：纽约过剩26辆、华盛顿过剩43辆、克里夫兰过剩31辆。而存在短缺的地区是：匹兹堡短缺32辆、布法罗短缺28辆、费城短缺26辆。各城市之间的距离为：
现在制定一个汽车在各地间重新分配的计划，并使花费的成本最小。运输费用是每英里1美元。
模型的目标是使总的运输成本最小。这里需要两套约束条件：其一是每个起点的供给量限制；其二是每个终点的需求量限制。由于供需平衡，所有的约束条件都是等式。 令 xij=从城市i运往城市j的汽车数
i=1,2,3; j=1,2,3,4
最小化 439x11+396x12+…+479x33+0x34
约束 x11+x12+x13+x14 =26
x21+x22+x23+x24 =43
x31+x33+x33+x34 =31
x11+x21+x31 =32
x12+x22+x32 =28
x13+x23+x33 =26
x14+x24+x34 =14
xij＞0，对所有的i、j。
注意约束条件的特殊结构是所有运输问题的共同特征。这种特殊结构以及约束等式中系数都是1的特点，可以确保解是整数解。
没有人真正用手算的方法来解线性规划模型，所以对计算机解的解释就变得重要起来。大部分计算机程序都运用了这样一个经验规则：如果右边项的增加能够改善目标函数（即最大化条件时增大目标函数，最小化条件时减小目标函数），则影子价格（代表一个单位的受限资源的转嫁价格）为正值且等于目标函数的变化值。但在某些例子中，增加右边项反而会削弱目标函数。例如在医院的例子中，如果蛋白质约束的右边项增加，目标函数将增大，这与我们所希望的最小化正好相反。一般用Excel Solver 7.0来解。
最后要注意的是，富余资源的影子价格为零。
----摘自《服务管理--运营、战略和信息技术》第二版 Fitzsimmons,J.A. 等