第10章利用LING0开发高级模型 在这一章里,我们将在不同的领域里建立一些高级模型。其目的有两个:一个是通过对这些高级模型 的研究,帮助用户提高建模的技巧:另一个是通过 LINGO在生产管理、后勤保障、金融、排队和销售等 很多领域的实例来说明 LINGO应用的广泛性。 10.1生产管理模型 在这一节里,我们将开发生产管理领域里的四个模型。下面分别进行详细介绍: 10.1.1 MODELI: BLEND(原材料混合模型) 1.背景 在混合问题中,通常是将两种或多种原材料混合在一起制成一种或多种产品,这种产品要满足一种或 多种质量要求。混合问题适用于很多领域,包括决定动物饲料的最佳配比、最低成本的矿石组合以及制造 出一种最低成本的特殊合金或决定最有效的广告媒体交易等等。 2.问题 假设有一家燃料处理工厂,生产两种产品 Regular和 Premium,并希望能获得最大的收益。这两种产品都 是由丁烷( butane)、催化重整油( catalytic reformats)和石脑油( naphtha)混合而成。它们必须在锌烷( octane) 蒸汽压( vapor pressure)和挥发性( volatility)方面满足一定的要求。每一种原材料都是有限的。而且己 知原材料的单位成本和产品的最小需要量和最大需要量 3.模型 模型10.1.1.1:原材料混合模型 BLEND ??? 4.集合 在这个模型里,我们定义了三个基本集合,即 RAWMAT(原材料)、 FINGOOD(产品)和 QUALMES 质量要素)。 从这三个基本集合可创建三个派生集合。第一个派生集合RXQ是一个密集,它是由原材料集合和质 量要素集合相乘而得,用这个派生集合来定义一个属性以表示每一种原材料的质量指标。第二个派生集合 QXF是由质量集合和产品集合相乘而得,用这个集合可以计算出产品里的质量指标。第三个派生集合RXF 是由原材料集合和产品集合相乘而得,用这个集合可以计算出每一种产品里原材料的含量 5.变量 在这个模型里,主要变量是每一种产品里各种原材料的数量(USED)。为了计算上的需要,我们还增 加了两个其他的变量。第一个变量是 BATCH,它被用于表示每一种产品的批量大小。第二个变量是 QSLACK,它被用于表示每一种产品里的各个质量要素离上限值的松弛量。 6.目标函数 这个模型的目标函数是求总收益达到最大。这可以用下面的表达式计算: [OBJECTIVEJMAX @SUM ( FINGOOD: PRICe*BATCH) @SUM (RAWMAT (R): COST (R)* @SUM(FINGOOD(F): USED(R, F))); 总收益当然是总收入减去总费用。总收入等于每一种产品的单位售价乘上它的批量再求和。可用下面 的 LINGO语句表达 UM (FINGOOD: PRICE %BATCH 总费用等于每一种原材料的单位价格乘上所用的总数再求和。它可以用下面的表达式计算: @SUM(RAWMAT (R: COST(R)( aSUM (FINGOOD(F): USED(R, F) 7.约束 在这个模型里有四种类型的约東,仅仅有两种要计算。第一种要计算的约束是每一种产品的批量。可 以用下面的表达式计算: BATCOMPJBATCH(F)=@SUM (RAWMAT (R): USED(R, F));
第 10 章 利用 LING0 开发高级模型 在这一章里，我们将在不同的领域里建立一些高级模型。其目的有两个：一个是通过对这些高级模型 的研究，帮助用户提高建模的技巧；另一个是通过 LINGO 在生产管理、后勤保障、金融、排队和销售等 很多领域的实例来说明 LINGO 应用的广泛性。 10.1 生产管理模型 在这一节里，我们将开发生产管理领域里的四个模型。下面分别进行详细介绍： 10.1.1 MODELl：BLEND（原材料混合模型） 1. 背景 在混合问题中，通常是将两种或多种原材料混合在一起制成一种或多种产品，这种产品要满足一种或 多种质量要求。混合问题适用于很多领域，包括决定动物饲料的最佳配比、最低成本的矿石组合以及制造 出一种最低成本的特殊合金或决定最有效的广告媒体交易等等。 2. 问题 假设有一家燃料处理工厂，生产两种产品 Regular 和 Premium，并希望能获得最大的收益。这两种产品都 是由丁烷（butane）、催化重整油（catalytic reformats）和石脑油（naphtha）混合而成。它们必须在锌烷（octane）、 蒸汽压（vapor pressure）和挥发性（volatility）方面满足一定的要求。每一种原材料都是有限的。而且己 知原材料的单位成本和产品的最小需要量和最大需要量。 3. 模型 模型 10.1.1.1：原材料混合模型 BLEND ？？？ 4. 集合 在这个模型里，我们定义了三个基本集合，即 RAWMAT（原材料）、FINGOOD（产品）和 QUALMES （质量要素）。 从这三个基本集合可创建三个派生集合。第一个派生集合 RXQ 是一个密集，它是由原材料集合和质 量要素集合相乘而得，用这个派生集合来定义一个属性以表示每一种原材料的质量指标。第二个派生集合 QXF 是由质量集合和产品集合相乘而得，用这个集合可以计算出产品里的质量指标。第三个派生集合 RXF 是由原材料集合和产品集合相乘而得，用这个集合可以计算出每一种产品里原材料的含量。 5. 变量 在这个模型里，主要变量是每一种产品里各种原材料的数量（USED）。为了计算上的需要，我们还增 加了两个其他的变量。第一个变量是 BATCH，它被用于表示每一种产品的批量大小。第二个变量是 QSLACK，它被用于表示每一种产品里的各个质量要素离上限值的松弛量。 6. 目标函数 这个模型的目标函数是求总收益达到最大。这可以用下面的表达式计算： [OBJECTIVE]MAX= @SUM（FINGOOD：PRICE*BATCH） @SUM（RAWMAT（R）：COST（R）* @SUM（FINGOOD（F）：USED（R，F）））； 总收益当然是总收入减去总费用。总收入等于每一种产品的单位售价乘上它的批量再求和。可用下面 的 LINGO 语句表达： @SUM（FINGOOD：PRICE％BATCH） 总费用等于每一种原材料的单位价格乘上所用的总数再求和。它可以用下面的表达式计算： @SUM（RAWMAT（R）：COST（R）{ @SUM（FINGOOD（F）：USED（R，F）） 7. 约束 在这个模型里有四种类型的约束，仅仅有两种要计算。第一种要计算的约束是每一种产品的批量。可 以用下面的表达式计算： [BATCOMP]BATCH（F）=@SUM（RAWMAT（R）：USED（R，F））；
具体说就是:产品F的批量是所有用于产品里的原材料的总和 第二种要计算的约束是计算每一种产品里的质量指标离质量上限的缺损值。每一种质量指标测定如 下 [QRESUPJ@SUM(RAWMAT (R) QLEVEL(R,Q)*USED(R, F))+QSLACK(Q, F)=QUP(Q, F)*BATCH (F); 具体地说,实际质量指标加上离上限的缺损值等于质量上限指标, 第三种约束是产品的批量必须在限制的范围内。我们用@BND函数建立这一约束如下 @BND(MINREQ, BATCH, MAXSELL): 注意:虽然我们可以直接输入批量大小限制的约束,但是使用aBND函数限制变量的界限效率更高。 最后一种约束是产品的质量指标必须符合要求。我们使用下面的约束: [QRESDNJQSLACK (Q, F)
具体说就是：产品 F 的批量是所有用于产品里的原材料的总和。 第二种要计算的约束是计算每一种产品里的质量指标离质量上限的缺损值。每一种质量指标测定如 下： [QRESUP]@SUM（RAWMAT（R）： QLEVEL（R，Q）* USED（R，F））+QSLACK（Q，F）=QUP（Q，F）*BATCH（F）； 具体地说，实际质量指标加上离上限的缺损值等于质量上限指标。 第三种约束是产品的批量必须在限制的范围内。我们用@BND 函数建立这一约束如下： @BND（MINREQ，BATCH，MAXSELL）； 注意：虽然我们可以直接输入批量大小限制的约束，但是使用@BND 函数限制变量的界限效率更高。 最后一种约束是产品的质量指标必须符合要求。我们使用下面的约束： [QRESDN]QSLACK（Q，F）<=（QUP（Q，F）-QLOW（Q，F））$BATCH（F）； 具体地说，质量指标的松弛量必须小于等于质量指标的最大量与最小量的差值。否则质量指标一定低 于最小限量。松弛量非负的事实确保质量指标不会超过最大限量。 8. 解答 求解模型可得如下结果： BATCH（REGULAR） 4000.000 BATCH（PREMIUM） 4095.238 total profit $44,905 下面列出了产品中各种原材料的实际含量： Raw Material（原材料） Regular Premium Butane 534 466 Catalytic Reformats 1,516 2.484 Naphtha 1,950 l,146 10.1.2 MODEL2：MRP（物资需求计划模型） 1. 背景 物资需求计划技术简称 MRP，是用于制作复杂产品的生产进度表。假设已知产品的需求进度表、产品 及各种部件订货至交货的时间，于是 MRP 可利用它们提出符合需求进度表的详细及时的生产进度表。 MRP 的目的是找到一个符合需求的详细及时的生产进度表。MRP 没有试图去寻找总成本最少的生产 进度表。在很多情况下，借助于 MRP 去寻找成本最少的生产进度表是一个很复杂的最优化问题，而且很 难实现。 2. 问题 假设你是一个人力车的制造商，有一个未来产品的需求计划。为了满足生产的需求，你需要知道什么 时候需要哪些部件、子部件以及它们的数量。假设你的最终产品有： （1）单轮脚踏车（有一个座位和一个轮子）——Unicycle （2）自行车（有一个座位、两个轮子和一根链条）——Bicycles （3）双座自行车（两个座位、两个轮子和两根链条）——Tandem 每一种产品都是由一些部件组装而成。每一个部件又都是由其他的一些子部件组装而成。为了简单和 不失一般性，我们把所有的产品、部件和子部件都看成零件。下面是主要的部件和子部件： （1）座位——Seats （2）轮子（有 1 根轮轴和 36 根轮辐）——Wheels （3）链条（有 84 个链环）——Chins （4）轮轴——Hubs （5）轮辐——Spokes （6）链环——Links 生产每一批零件所用的时间称为定货至交货的时间。当你开始生产一个零件的时候，相应的部件必须 及时到位。销售部门对未来两个月（8 周）的需求作了预测：第八周需要 10 辆单轮脚踏车，第九周需要
20辆自行车和20辆双座自行车 3.模型 模型10.1.2-1:物资需求计划模型MRP ?? 你一定还记得代字号“~”是LNGO的记录结束符号。当遇到一个代字号时,LNGO就停止从数据 文件读取数据而开始读取模型文件里的下一个语句。 5.集合 在这个模型里我们定义了两个基本集合:一个是零件(PARI),另一个是时间周期(TME) 用上面两个基本集合又产生了两个派生集合:一个是USES,它是一个密集,由PART与自身相乘而 得,我们用这个集合来建造一个包含零件使用数据的表格或称输入输出矩阵,这个表格告诉我们生产一个 零件需要多少配件。另一个派生集合是PXT,它是由零件集合与时间周期集合相乘而得,我们需要这个集 合是由于我们关心每一时期每一种零件的需要量及每一时期开始生产的每一种零件的数量。 6.变量 在这个模型里惟一未知的是总需求属性(TD)。这里TD(p,t)是t时期产品p的总需求。总需求由 两个因素决定:一个是外部消费者的需求(ED):一个是内部生产方面的需求。我们借助于合并零件的定 货至交货的时间来计算TD。这样,当TD在某一时期为非零时,则生产必须在那一时期开始。 7.公式 这个模型的关键公式是: !对每一零件P和时间周期T,总需求=外部需求+未来一个订货至交货时间父集合的需求 复制过来??? 对每一个时期里的每一种零件而言,必须开始生产的数量在其订货交货时间后要满足: (1)外部的需求 (2)内部生产的需求 表示内部需求的子表达式为:ED(PT+LT(P)) 下面的表达式求出了在一个订货交货时间以外,内部生产需要的所有其余零件数量 aSUM(USES(P2, P): TD(P2, T+LT(P))*NEEDS(P2, P)): 注意:我们在外面@FOR循环函数里还使用了一个逻辑判别式(用黑体显示) @FOR (PXT (ET) I T+LT (P)#LE#NP: 如果没有这个条件判别式,这个计算将扩展到TME集合里的最后时期之外。 8.解答 求解这个模型,我们将会得到下面的变量TD的非零值解答: Variable TD (U, 7) 10.00000 TD(B, 7) 20.00000 TD(T8) 20.00000 TD(S, 6) 30.00000 TD(S。7) 40.00000 ID(W:4)50.00000 TD(W5) 40.00000 TD(C, 6) 20.00000 TD(C7 40.00000 TD(H3) 50.00000 TD(H 4) 40.00000 TD(P2) 1800.000 TD(E3) 1440.000 TD(L, 4) 1680.000
20 辆自行车和 20 辆双座自行车。 3. 模型 模型 10.1.2—1：物资需求计划模型 MRP ？？？ 你一定还记得代字号“~”是 LINGO 的记录结束符号。当遇到一个代字号时，LINGO 就停止从数据 文件读取数据而开始读取模型文件里的下一个语句。 5. 集合 在这个模型里我们定义了两个基本集合：一个是零件（PART），另一个是时间周期（TIME）。 用上面两个基本集合又产生了两个派生集合：一个是 USES，它是一个密集，由 PART 与自身相乘而 得，我们用这个集合来建造一个包含零件使用数据的表格或称输入输出矩阵，这个表格告诉我们生产一个 零件需要多少配件。另一个派生集合是 PXT，它是由零件集合与时间周期集合相乘而得，我们需要这个集 合是由于我们关心每一时期每一种零件的需要量及每一时期开始生产的每一种零件的数量。 6. 变量 在这个模型里惟一未知的是总需求属性（TD）。这里 TD（p，t）是 t 时期产品 p 的总需求。总需求由 两个因素决定：一个是外部消费者的需求（ED）；一个是内部生产方面的需求。我们借助于合并零件的定 货至交货的时间来计算 TD。这样，当 TD 在某一时期为非零时，则生产必须在那一时期开始。 7. 公式 这个模型的关键公式是： !对每一零件 P 和时间周期 T，总需求=外部需求+未来一个订货至交货时间父集合的需求； 复制过来？？？ 对每一个时期里的每一种零件而言，必须开始生产的数量在其订货交货时间后要满足： （1）外部的需求 （2）内部生产的需求 表示内部需求的子表达式为：ED（P, T+LT（P）） 下面的表达式求出了在一个订货交货时间以外，内部生产需要的所有其余零件数量。 @SUM（USES（P2，P）：TD（P2，T+LT（P））*NEEDS（P2，P））； 注意：我们在外面@FOR 循环函数里还使用了一个逻辑判别式（用黑体显示）： @FOR（PXT（E T）I T+LT（P）#LE#NP： 如果没有这个条件判别式，这个计算将扩展到 TIME 集合里的最后时期之外。 8. 解答 求解这个模型，我们将会得到下面的变量 TD 的非零值解答： Variable Value TD（U，7） 10.00000 TD（B，7） 20.00000 TD（T.8） 20.00000 TD（S，6） 30.00000 TD（S。7） 40.00000 TD（W：4） 50.00000 TD（W,5） 40.00000 TD（C，6） 20.00000 TD（C.7） 40.00000 TD（H.3） 50.00000 TD（H.4） 40.00000 TD（P,2） 1800.000 TD（E 3） 1440.000 TD（L，4） 1680.000
T1)(L,5)3360.000 将上面的解答制成表格就会得到如表10.1所示的生产进度表。 表10.1MRP生产进度 时间(周) 3 4 6 8 零件(个) Unicycle Bicycles Tandem Seats Hubs 40 Spokes 1.8001.440 1.6803.360 见程序 !对于每一个存在优先关系的作业对来说,前者对应的工作站I必须小于后者对应的工作站J @FOR (PRED(I, J): @SUM (STATION (K): K(X (, K).KX(I, K))>=0) 对于每一个工作站来说,指派作业完成的总时间必须小于最大循环时间 @FOR (STATION (K) @SUM(TXS (I, K):T(D)X(I, K))
T1）（L, 5） 3360.000 将上面的解答制成表格就会得到如表 10.1 所示的生产进度表。 表 10.1 MRP 生产进度 时间（周） 零件（个） 2 3 4 5 6 7 8 Unicvcle lO Bicvcles 20 Tandem 20 Seats 30 40 Wheels 50 40 Chains 20 40 Hubs 50 40 Spokes 1.800 1.440 Links 1.680 3.360 见程序 !对于每一个存在优先关系的作业对来说，前者对应的工作站 I 必须小于后者对应的工作站 J： @FOR（PRED（I，J）：@SUM（STATION（K）：K{X（J，K）·K}X（I，K））>=0）； !对于每一个工作站来说，指派作业完成的总时间必须小于最大循环时间； @FOR（STATION（K）： @SUM（TXS（I，K）：T（I）}X（I，K））<=CYCTIME）； !目标函数是使最大循环时间达到最小； MIN=CYCTIME； !指定 X（I，J）为 0／1 变量； @FOR（TXS：@BIN（X））； END 4. 集合 我们定义两个基本集合——TASK（作业）和 STATION（工作站）。我们用这两个基本集合产生两个派 生集合。第一个派生集合是 PRET，它是一个疏集，是由集合 TASK 与自身相乘而得。集合的元素是作业 之间的优先关系，例如，这个集合的第一个元素是（A，B），它表示作业 A 优先于作业 B。 第二个派生集合是 TXS，它是由作业集合与工作站集合相乘而得到的密集，我们用这个集合来确定哪 一个作业指派给哪一个工作站。 5. 变量 这个模型的决策变量是属性 X。属性 X 是定义在集合 TXS 上。X（t，s）是一个 0／1 变量。如果作 业 t 指派给工作站 s，则其值为 l；否则其值为 0。属性 X 可用下式限定为 0／1 变量： @FOR（TXS：@BIN（X））； 为了表示整个装配线的循环时间，我们引进了标量变量 CYCTIME，它是通过每个工作站的最大循环 时间来计算的。 6. 目标函数 这个模型的目标函数很简单，它就是使得装配线总体循环时间达到最小值。可用下式给出： MIN=CYCTIME； 7. 约束 这个模型的约束有三种：
(1)每一个作业必须指派到一个工作站; (2)作业的优先关系必须得到满足; (3)装配线循环时间 CYCTIME变量的计算 下面的表达式求出每一个作业的指派标量的总和并令其值为1。这样就限定一个作业只被指派到一 工作站 @FOR(TASK (I):@SUM(STATION(K):X(, K))=1) 我们使用下面的表达式执行作业的优先关系: @FOR(PRED(I, J) @SUM (STATION (): K*X(J, K)-K*X(I, K))>=0) 假设作业Ⅰ是在作业J之前。如果作业I被错误地指派给了一个工作站,而这个工作站是在作业J指 派给的工作站之后。那么,所有K*X(I,K)的总和将超所有K*X(J,K)的总和,约束不会得到满足 这样,上面的约束有效地保证了优先关系 我们用下面的约束计算循环时间 @FOR (STATION (K) @SUM(TXS (I, K):T(I)*X(I, K))
（1）每一个作业必须指派到一个工作站； （2）作业的优先关系必须得到满足； （3）装配线循环时间 CYCTIME 变量的计算。 下面的表达式求出每一个作业的指派标量的总和并令其值为 1。这样就限定一个作业只被指派到一个 工作站。 @FOR（TASK（I）：@SUM（STATION（K）：X（I，K））=1）； 我们使用下面的表达式执行作业的优先关系： @FOR（PRED（I，J）： @SUM（STATION（K）：K*X（J，K）-K* X（I，K））>=0）； 假设作业 I 是在作业 J 之前。如果作业 I 被错误地指派给了一个工作站，而这个工作站是在作业 J 指 派给的工作站之后。那么，所有 K*X（I，K）的总和将超所有 K*X（J，K）的总和，约束不会得到满足。 这样，上面的约束有效地保证了优先关系。 我们用下面的约束计算循环时间： @FOR（STATION（K）： @SUM（TXS（I，K）：T（I）*X（I，K））<=CYCTIME）； 在这个约束里，@SUM（TXS（I，K）：T（I）}*X（I，K））为工作站 K 算出循环时间。我们用@FOR 语句使变量 CYCTIME 大于或等于所有工作站的循环时间。如果我们再加上目标函数使 CYCTIME 达到最 小，CYCTIME 将被“压缩”到各个工作站循环时间的最大值。 借助于“压缩”CYCTIME 到恰当的值，我们避免了使用@MAX 函数。假如我们一定要使用@MAX 函数的话，为了把握分段线性函数@MAX，LINGO 将不得不求助于非线性求解器。在建模实践中，我们 应尽量避免使用非线性模型，这很重要。 8. 解答 求解模型，我们将会得到下面指派变量 X 的非零值解答： Variable Value X（A，2） 1.000000 X（B，3） 1.000000 X（C，4） 1.000000 X（D，1） 1.000000 X（E，3） 1.000000 X（F，4） 1.000000 X（G，4） 1.000000 X（H，3） 1.000000 X（I，3） 1.000000 X（J，4） 1.000000 X（K，4） 1.000000 概述这个解答，我们有： Workstation Assigned Tasks Cycle Time 1 D 50 2 A 45 3 B，E，H，I 50 4 C，F，G，J，K 50 整个装配线的循环时间是 50 分钟，它是所有工作站的最大循环时间。我们得到了一个较为平衡的装 配线（只有 2 号工作站有 5 分钟的松弛时间）。 10.1.4 MODEL4：ORDER（工件排序模型） 1. 背景 在工件排序问题中，每个工件将被指派到不同的机床上进行加工作业，目标函数是求出所有工件的加
工方案,使在最短的时间内完成全部加工作业。对于每一个工件来说,它要在不同的机床上进行加工作业, 而且加工作业还要按一定的顺序进行:对每一个机床来说,它要加工不同的工件,而且必须按照一定的顺 序进行。虽然我们无论如何都可以求出工件的加工方案,但是,如果安排不当就必然会出现瓶颈现象 机床等待加工的时间较长。这样就会使得完成全部工件加工的总时间较长。由于工件加工作业之间具有优 先关系,有些作业必须等到其他作业完成后才可进行,这使得工件排序问题变得更加复杂。指派到机床上 的加工作业必须服从优先关系。 2.问题 假设用4台机床加2123个工件。各个工件的机床加工顺序,以及工件i在机床j上的加工时间(i=1, 2,3:j=1,2,3,4)如表10.3所示(单位:小时)。 10.3工件加工顺序及时间表 机床1→ 机床2→ 机床3 工件1 工件2 2 462 934 248 工件3 我们要找出一种工件加工作业方案使得完成全部工件加工的总时间达到最小。 3.模型 模型10.1.4—1:工件排序模型 ORDER 4.集合 我们定义三个基本集合一— GONGJ(工件)、 JICHUANG(机床)和 SHUIAN(时间)。我们用这三个 基本集合产生两个派生集合。一个是LNKS,它是一个密集,是由集合 GONGJ与 JICHUANG相乘而得 利用 LINKS我们产生两个属性,属性A存储工件在每个机床上加工所用时间:属性Y是控制变量。另 个派生集合是 GONGSHI,它也是一个密集,是由集合 GONGJ和SHAN相乘而得。利用 GONGSH我 们产生一个属性x,它表示工件在各个机床上加工的开始时间和结束时间。 5.变量 模型里的决策变量是属性X。X(i,1)、X(i,3)、X(i,5)、X(i,7)表示工件i在4个机床上的 加工开始时间,X(i,2)、X(i,4)、X(i,6)、X(i,8)表示工件i在4个机床上的加工结束时间(i=1, 2,3);当j是奇数时,Ⅹ(1,j、X(2,j)、Ⅹ(3,j)表示机床(j+1)/2加工3个工件的开始时间; 当j是偶数时,Ⅹ(1,j)、X(2,j)、X(3,j)表示机床j/2加工3个工件的结束时间(j=1,2,…8) 所有的(i,j)就构成了工件的加工时间表。属性Y是控制变量,只取0/1两个值,用来控制机床加工 工件的顺序 6.数据 在此模型中,输入的数据是存放在文件工件排序xls里的‘加工时间’域上。具体内容见表104中的 数据部分。 将数据放在模型之外可以使得模型的调试变得很容易。如果加工时间有变化,只要改动表104中的数 据,模型不需做任何改动就可获得相应的解答 输入数据是用下面的公式完成: A=@OLE(\ingo\工件排序xls’,’加工时间’); 7.目标函数 这个模型的目标很简单,它就是求出加工完全部工件的总时间的最小值。可用下式给出 @for(GONGJ (i): W>=x(i, m+3)ta (i, m)): 这里,m表示最后一个机床。 8.约束 在这个模型里,我们有下面两类约束 (1)每个工件加工次序的约束 对于每个工件来说,加工次序必须得到满足。即工件i(i=1,2,3)在某个机床上的开始加工时间加
工方案，使在最短的时间内完成全部加工作业。对于每一个工件来说，它要在不同的机床上进行加工作业， 而且加工作业还要按一定的顺序进行；对每一个机床来说，它要加工不同的工件，而且必须按照一定的顺 序进行。虽然我们无论如何都可以求出工件的加工方案，但是，如果安排不当就必然会出现瓶颈现象—— 机床等待加工的时间较长。这样就会使得完成全部工件加工的总时间较长。由于工件加工作业之间具有优 先关系，有些作业必须等到其他作业完成后才可进行，这使得工件排序问题变得更加复杂。指派到机床上 的加工作业必须服从优先关系。 2. 问题 假设用 4 台机床加 212 3 个工件。各个工件的机床加工顺序，以及工件 i 在机床 j 上的加工时间（i=1， 2，3；j=1，2，3，4）如表 10.3 所示（单位：小时）。 10.3 工件加工顺序及时间表 机床l→ 机床2→ 机床3→ 机床4 工件1 3 4 9 2 工件2 2 6 3 4 工件3 1 2 4 8 我们要找出一种工件加工作业方案使得完成全部工件加工的总时间达到最小。 3. 模型 模型 10.1.4—1：工件排序模型 ORDER 4. 集合 我们定义三个基本集合——GONGJ（工件）、JICHUANG（机床）和 SHUIAN（时间）。我们用这三个 基本集合产生两个派生集合。一个是 LINKS，它是一个密集，是由集合 GONGJ 与 JICHUANG 相乘而得。 利用 LINKS 我们产生两个属性，属性 A 存储工件在每个机床上加工所用时间；属性 Y 是控制变量。另一 个派生集合是 GONGSHI，它也是一个密集，是由集合 GONGJ 和 SHIJIAN 相乘而得。利用 GONGSHI 我 们产生一个属性 x，它表示工件在各个机床上加工的开始时间和结束时间。 5. 变量 模型里的决策变量是属性 X。X（i，1）、X（i，3）、X（i，5）、X（i，7）表示工件 i 在 4 个机床上的 加工开始时间，X（i，2）、X（i，4）、X（i，6）、X（i，8）表示工件 i 在 4 个机床上的加工结束时间（i=1， 2，3）；当 j 是奇数时，X（1，j）、X（2，j）、X（3，j）表示机床（j+1）／2 加工 3 个工件的开始时间； 当 j 是偶数时，X（1，j）、X（2，j）、X（3，j）表示机床.j／2 加工 3 个工件的结束时间（j=1，2，…8）。 所有的 X（i，j）就构成了工件的加工时间表。属性 Y 是控制变量，只取 0／1 两个值，用来控制机床加工 工件的顺序。 6. 数据 在此模型中，输入的数据是存放在文件工件排序.xls 里的‘加工时间’域上。具体内容见表 10.4 中的 数据部分。 将数据放在模型之外可以使得模型的调试变得很容易。如果加工时间有变化，只要改动表 10.4 中的数 据，模型不需做任何改动就可获得相应的解答。 输入数据是用下面的公式完成： A=@OLE（’＼lingo＼工件排序.xls’，’加工时间’）； 7. 目标函数 这个模型的目标很简单，它就是求出加工完全部工件的总时间的最小值。可用下式给出： min=W； @for（GONGJ（i）：W>=x（i，m+3）+a（i，m））； 这里，m 表示最后一个机床。 8. 约束 在这个模型里，我们有下面两类约束： （1）每个工件加工次序的约束 对于每个工件来说，加工次序必须得到满足。即工件 i（i=l，2，3）在某个机床上的开始加工时间加
上加工所用时间,必须小于等于在下一个机床上的开始加工时间。可以用下式表达: 复制过来 efor( LINKS(i’j)1j规t#m:x(i,纠一1)+a(蝎)
上加工所用时间，必须小于等于在下一个机床上的开始加工时间。可以用下式表达： 复制过来 @for（LINKS（i'j）lj 规 t#m：x（i，纠一 1）+a（蝎）<--x（i，2 凇 j+1））； （2）每个机床加工次序的约束 对于每个机床来说，某一时刻只能加工一个工件。例如，我们只考虑工件 1 和工件 2 在机床 1 上的加 工情况，则必须满足：X（1，1）+a（1，1）≤X（2，1）或 X（2，1）+a（2，1）≤X（1，1）。我们可以 用下式表达机床加工次序的约束： 复制过来？？ @for（GONGJ（k）Ik#1 饼 s： @for（UNKS（i’j）li 册防 s—k+1： x（i，2 巧一 1）+a（i，j）<=x（i+k，2q 一 1）+1000 木 y（i+k 一 1'j）））； @for（GONGJ（k）Ik#1 饼 s= @for（LINKS（i'j）Ii#1 饼 s_k+1： t x（i+k，2 木 j 一 1）+a（i+k'j）<=x（i，2 巧一 1）+1000$（1 一 y（i+k 一 1'j））））； !限制 y（i’j）为 O 一 1 变量； @for（GONGJ（i）：@for（JICHUANG（j）：@bin（y（i'j））））； 9. 解答 模型求解后，我们将解答送回到文件工件排序.xls 里的‘起止时间’域上。可用下式完成： @OLE（’\1ingo＼工件排序.xls’，’起止时间’）=x 输出的具体结果如表 10.4 所示的数据部分。 表 10.4 工件加工时间表 机床 1 机床 2 机床 3 机床 4 开始时间 结束时间 开始时间 结束时间 开始时间 结束时间 开始时间 结束时间 工件l 3 6 9 13 13 22 22 24 工件2 l 3 3 9 9 12 15 19 工件3 O l 1 3 3 7 7 15 10.2 后勤保障模型 在这一节里，我们将开发两个后勤保障方面的模型。一个涉及工厂定位，一个涉及网络的最短线路。 lO.2.1 MODEL5：cAPLOC（工广定位模型） 1. 背景 工厂定位模型是我们在第 1 章中介绍的有关运输问题的推广。工厂定位问题具有较大的决策范围，工 厂位置是变量。厂商很可能会遇到这样一类问题：在满足顾客对产品要求的前提下使总运输成本达到最少。 2. 问题 某公司计划增加一些产品加工点（工厂），有三个位置可供选择。现有四个客户需要该公司的产品且 需要量已知。在每一个位置建立工厂都有与其关联的月运作费用，从工厂到客户的运输成本也不相同。此 外，工厂的运输能力也是有限的，不得突破它的生产能力。 现在需要决定哪些工厂要开工？开工的工厂给每一个客户运送多少产品使得总运输成本和工厂月运作费 用之和最少。 3. 模型 模型 10.2.1—1：工厂定位模型 CAPLOC 4. 集合 在这个模型里，我们建立了两个基本集合：一个是 PLANTS（工厂）集合；一个是 CUSTOMERS（客
户)集合。用这两个集合,我们建立了一个密集ARCS,它是由工厂集合与客户集合相乘而得。我们用个 集合来表达工厂与客户之间的运输线路 5.变量 在这个模型里,我们有两类决策变量。定义在集合ARCS上的属性VOL代表了工厂到客户每一个线 路上的运输量:定义在集合 PLANTS上的属性OPEN是用于表示哪些工厂将开工。具体地说,如果工厂 将开工,则OPEN(p)的值为L,否则为0。属性OPEN的元素将用下式定义为二元0/1变量 @FOR(PLANTS:@BIN(OPEN)); 6.目标函数 这个模型的目标函数是使得总成本(运输总成本加上运作成本的总和)达到最少。这可以用下面的表 达式计算: ITTL COSTIMIN=@SUM(ARCS: COST"VOL)+ @SUM (PLANTS: FCOST*OPEN) 目标函数里运输总成本是 aSUM(ARCS:COST*ⅤOL);而运作成本总和是aSUM( PLANTS FCOST*OPEN)。 7.约束 这个模型有两种类型的约束:第一种是每个客户必须得到足够的产品以满足需求:第二种是每个工厂 的运输量不能超过它的生产量 我们使用下面的表达式保证所有客户都可以获得足够的产品 @FOR(CUSTOMERS (J): [DEMAND] @SUM(PLANTS (I): VOL (I, J))>=DEM (J)): 对每一个客户,我们计算出了接收运输量的总和,并且让它大于或等于客户的需求量。为了限制工厂 的运输量不超过它的生产能力,我们使用下面的语句: @FOR(PLANTS (I): [SUPPLY] @SUM(CUSTOMERS (J): VOL(I,J))
户）集合。用这两个集合，我们建立了一个密集 ARCS，它是由工厂集合与客户集合相乘而得。我们用个 集合来表达工厂与客户之间的运输线路。 5. 变量 在这个模型里，我们有两类决策变量。定义在集合 ARCS 上的属性 VOL 代表了工厂到客户每一个线 路上的运输量；定义在集合 PLANTS 上的属性 OPEN 是用于表示哪些工厂将开工。具体地说，如果工厂 p 将开工，则 OPEN（p）的值为 l，否则为 0。属性 OPEN 的元素将用下式定义为二元 0／1 变量： @FOR（PLANTS：@BIN（OPEN））； 6. 目标函数 这个模型的目标函数是使得总成本（运输总成本加上运作成本的总和）达到最少。这可以用下面的表 达式计算： [TTL_COSTlMIN=@SUM(ARCS: COST*VOL)+ @SUM（PLANTS：FCOST*OPEN）； 目标函数里运输总成本是@SUM(ARCS: COST*VOL) ；而运作成本总和是@SUM（PLANTS： FCOST*OPEN）。 7. 约束 这个模型有两种类型的约束：第一种是每个客户必须得到足够的产品以满足需求；第二种是每个工厂 的运输量不能超过它的生产量。 我们使用下面的表达式保证所有客户都可以获得足够的产品： @FOR（CUSTOMERS（J）：[DEMAND] @SUM（PLANTS（I）：VOL（I，J））>=DEM（J））； 对每一个客户，我们计算出了接收运输量的总和，并且让它大于或等于客户的需求量。为了限制工厂 的运输量不超过它的生产能力，我们使用下面的语句： @FOR（PLANTS（I）：[SUPPLY] @SUM（CUSTOMERS（J）：VOL（I，J））<= CAP（I）{OPEN（I） ）； 对于每一个客户，我们计算出了运输量的总和，并且让它小于或等于工厂的生产能力乘上表示工厂开 工与否的指示器 OPEN。 注意：为了使工厂可以运出产+品，在这些约束里的二元变量 OPEN 必须取 1 的值。 8. 解答 求解模型，我们将得到下面的工厂定位模型的解答： Optimal solution found at step： 38 Objective value： 327.0000 Branch count： 3 Variable Value OPEN（P1） 1.000000 OPEN（P3） 1.000000 VOL（P1，C1） 15.00000 VOL（P1，C2） 17.00000 VOL（Pl，C4） 3.0000 VOL（P3，C3） 22.00000 VOL（P3，C4） 9.000000 我们让工厂 1 和工厂 3。从工厂 1 开工，我们分别运出 15，17 和 3 个单位给客户 l，2 和 4；从工厂 3， 我们运出 22 个单位给客户 3，运出 9 个单位给客户 4。 复制过来
4.集合 我们只建立一个基本集合 CITIES,它代表了网络里的城市。我们用这个基本集合派生出一个集合 ROADS,它代表了城市之间的连接。我们直接给出 ROADS中的元素。所以, ROADS是一个疏集 变量 定义在 CITIES集合上的属性F是用来存储每一个城市到终点城市的最短距离。定义在 ROADS集合 上的属性D表示两个城市之间的直达距离 6.公式 我们使用下面的语句计算各城市到城市10的最短距离 复制过来 FOR( CITIES(i)Ii∥L滞@SIZE( CITIES) F (i)=@MIN(ROADS (i, j:D(i, j)+F ()) 7.解答 求解模型,我们就会得到下面的结果: Variable value F(1) F(2) 1900000 F(3)1400000 F(4)20.00000 F(5)8000000 F(6) 7.000000 F(7) 12.00000 5.000000 F(9)2.000000 F(10)0.000000 从城市1到城市10的最短距离F(1)为19。好奇的读者可发现相应的最短线路为: (城市)1-3-5-8-10。 10.3财政金融模型 在这一节里,我们将开发一些与财政金融有关的模型 10.3. I MODEL7: GENPRT( Markowitz投资选择模型) 1.背景 1952年3月在美国的《金融》杂志上, Harry M. Markowi-发表了一篇题为“投资选择”的文章。在这 篇文章里,他论证了如何通过选择那些相关程度不大的投资来减少资产投资的风险。与此同时,为了在风 险和利润之间建立一个有利关系,他还拟定了一个基本原则:这就是众所周知的投资多样化。换句话说 就是不要将所有的“鸡蛋”放在一个“篮子”里 理解 Markowitz投资模型的关键是统计量:投资方差。从数学上看,投资方差是: 这里,Ⅺi是用于第i项投资的投资额,如果i不等于j,则??j是第i项与第j项的协方差;如果i等 于j,则0;是第i项投资的方差 方差是表示利润波动的平均值。方差越大,投资风险就越大。协方差是表示一种股票的利润波动与另 种股票利润波动的相关性。协方差较大,则表明一种股票利润的增加很可能会带动另一种股票利润的增 加。协方差接近0,则意味着两种股票的利润变化彼此独立。一个负的协方差意味着一种股票利润的增加 可能会导致另一种股票利润的减少 Markov~模型是寻求最小投资方差的投资方案,同时使得所有期望利润总和达到一定水平 2问题
4. 集合 我们只建立一个基本集合 CITIES，它代表了网络里的城市。我们用这个基本集合派生出一个集合 ROADS，它代表了城市之间的连接。我们直接给出 ROADS 中的元素。所以，ROADS 是一个疏集。 5. 变量 定义在 CITIES 集合上的属性 F 是用来存储每一个城市到终点城市的最短距离。定义在 ROADS 集合 上的属性 D 表示两个城市之间的直达距离。 6. 公式 我们使用下面的语句计算各城市到城市 10 的最短距离： 复制过来 @FOR（CITIES（i）I i∥L]滞@SIZE（CITIES）： F（i）=@MIN（ROADS（i，j）：D（i，j）+F（j）） ）； 7. 解答 求解模型，我们就会得到下面的结果： Variable Value F（1） 19.00000 F（2） 19.00000 F（3） 14.00000 F（4） 20.00000 F（5） 8.000000 F（6） 7.000000 F（7） 12.00000 F（8） 5.000000 F（9） 2.000000 F（10） 0.000000 从城市 1 到城市 10 的最短距离 F（1）为 19。好奇的读者可发现相应的最短线路为： （城市）1—3—5—8—10。 10.3 财政金融模型 在这一节里，我们将开发一些与财政金融有关的模型。 10.3.1 MODEL7：GENPRT（Markowitz 投资选择模型） 1. 背景 1952 年 3 月在美国的《金融》杂志上，Harry M.Markowi~发表了一篇题为“投资选择”的文章。在这 篇文章里，他论证了如何通过选择那些相关程度不大的投资来减少资产投资的风险。与此同时，为了在风 险和利润之间建立一个有利关系，他还拟定了一个基本原则：这就是众所周知的投资多样化。换句话说， 就是不要将所有的“鸡蛋”放在一个“篮子”里。 理解 Markowittz 投资模型的关键是统计量：投资方差。从数学上看，投资方差是： ??? 这里，Xi 是用于第 i 项投资的投资额，如果 i 不等于 j，则??? ij 是第 i 项与第 j 项的协方差；如果 i 等 于 j，则 0；；是第 i 项投资的方差。 方差是表示利润波动的平均值。方差越大，投资风险就越大。协方差是表示一种股票的利润波动与另 一种股票利润波动的相关性。协方差较大，则表明一种股票利润的增加很可能会带动另一种股票利润的增 加。协方差接近 0，则意味着两种股票的利润变化彼此独立。一个负的协方差意味着一种股票利润的增加 可能会导致另一种股票利润的减少。 Markowi~模型是寻求最小投资方差的投资方案，同时使得所有期望利润总和达到一定水平。 2.问题
假设你正在考虑向三种股票进行投资。通过历史资料,你计算出了一个期望利润、利润方差和各种股 票之间利润的协方差。你希望通过向三种而不是一种股票投资来降低风险。你计划让利润增加12%。那么, 为了达到这一目标并且使投资风险最小,你应该如何分配你的资金向三种股票投资?作为一种安全上的考 虑,你规定任何一项单独的投资不得超过投资总额的75% 3.模型 模型103.1-l: Markowitz投资选择模型 GENPRT 4.集合 我们定义了一个基本集合 ASSETS,它表示模型里的三种股票。利用这个集合的自乘,我们派生了 个密集 COVMAT,用来定义协方差矩阵 5.属性 在这个模型里,我们定义了4个属性。前3个属性RATE、UB和v用于存储数据。RAE存储每一种 投资的期望利润,UB存储投资中用于某一项投资的上限值,而ⅴ存储协方差矩阵。 注意:协方差矩阵是对称的。在大型的投资模型里,这个矩阵只给出一半就行了,而在这个模型里, 为了简单起见我们给出了整个矩阵。 最后一个属性x构成了这个模型的决策变量。具体地说,x(i)是表示用于第i项投资的投资比例。 6.目标函数 这个模型的目标函数是使得投资风险达到最小。正如上面提到的,我们用投资方差来表示投资风险 从而得到下面的目标函数: [VARJMIN=@SUM(COVMAT(I, J): V(I,){X(D)%X(J) 7.约束 我们有三种形式的约束: (1)我们必须将资金全部用于投资 (2)我们不可能在某一项上投资过多 (3)期望利润必须达到或超过目标利润率,我们的目标利润率为12% 使用下面的表达式可将所有的资金用于投资: FULLJQSUM(ASSE-X)=1: 具体地说,所有各项投资的比例之和必须等于1。如果没有这个约束,LNGO将试图寻求方差更低的 投资方案。你可以将这个约束去掉,运行模型试试结果。 我们用下面的表达式保证对某项目的投资不至于太多 @FOR(ASSET:(@BND(O, X, UB)): 用@BND函数限制变量的界限是最有效的方法。 我们用下面的表达式迫使投资的期望利润大于或等于目标利润: RETJ@SUM(ASSET: RATE X)>=GROWTH 式左边是期望利润率,它是各项投资利润率与投资比率相乘相加的结果。 8.解答 求解模型,我们将得到下面的 Markov忆Z投资选择模型解答: Optim-solution found at step: Jective value 0.4173749 Variable X(1) 0.1548631 X(2) 0.2502361 X(3) 0.5949008 Row Slack Or Surplus VAR 0.4173749 FULL 0.0000000
假设你正在考虑向三种股票进行投资。通过历史资料，你计算出了一个期望利润、利润方差和各种股 票之间利润的协方差。你希望通过向三种而不是一种股票投资来降低风险。你计划让利润增加 12％。那么， 为了达到这一目标并且使投资风险最小，你应该如何分配你的资金向三种股票投资？作为一种安全上的考 虑，你规定任何一项单独的投资不得超过投资总额的 75％。 3. 模型 模型 10_3.1-l：Markowitz 投资选择模型 GENPRT 4. 集合 我们定义了一个基本集合 ASSETS，它表示模型里的三种股票。利用这个集合的自乘，我们派生了一 个密集 COVMAT，用来定义协方差矩阵。 5. 属性 在这个模型里，我们定义了 4 个属性。前 3 个属性 RATE、UB 和 v 用于存储数据。RATE 存储每一种 投资的期望利润，UB 存储投资中用于某一项投资的上限值，而 v 存储协方差矩阵。 注意：协方差矩阵是对称的。在大型的投资模型里，这个矩阵只给出一半就行了，而在这个模型里， 为了简单起见我们给出了整个矩阵。 最后一个属性 x 构成了这个模型的决策变量。具体地说，x(i)是表示用于第 i 项投资的投资比例。 6. 目标函数 这个模型的目标函数是使得投资风险达到最小。正如上面提到的，我们用投资方差来表示投资风险。 从而得到下面的目标函数： [VAR]MIN=@SUM(COVMAT(I，J)： V(I，J){X(I)％X(J))； 7. 约束 我们有三种形式的约束： (1)我们必须将资金全部用于投资； (2)我们不可能在某一项上投资过多； (3)期望利润必须达到或超过目标利润率，我们的目标利润率为 12％。 使用下面的表达式可将所有的资金用于投资： [FULL]@SUM(ASSE~X)=l； 具体地说，所有各项投资的比例之和必须等于 1。如果没有这个约束，LINGO 将试图寻求方差更低的 投资方案。你可以将这个约束去掉，运行模型试试结果。 我们用下面的表达式保证对某项目的投资不至于太多： @FOR(ASSET：@BND(O，X，UB))； 用@BND 函数限制变量的界限是最有效的方法。 我们用下面的表达式迫使投资的期望利润大于或等于目标利润： [RET]@SUM(ASSET：RATE}X)>=GROWTH； 式左边是期望利润率，它是各项投资利润率与投资比率相乘相加的结果。 8. 解答 求解模型，我们将得到下面的 MarkowitZ 投资选择模型解答： Optim~solution found at step： 7 Objective value： 0.4173749 Variable Value X(1) 0.1548631 X(2) 0.2502361 X(3) 0.5949008 Row Slack Or Surplus VAR 0.4173749 FULL 0.0000000