第二十六章经济与金融中的优化问题 本章主要介绍用 LINGO软件求解经济、金融和市场营销方面的几个优化问题的案 例 §1经济均衡问题及其应用 在市场经济活动中,当市场上某种产品的价格越高时,生产商越是愿意扩大生产 能力(供应能力),提供更多的产品满足市场需求;但市场价格太高时,消费者的消费 欲望(需求能力)会下降。反之,当市场上某种商品的价格越低时,消费者的消费欲望 (需求能力)会上升,但生产商的供应能力会下降。如果生产商的供应能力和消费者的 需求能力长期不匹配,就会导致经济不稳定。在完全市场竞争的环境中,我们总是认为 经济活动应当达到均衡( equilibrium),即生产和消费(供应能力和需求能力)达到平 衡,不再发生变化,这时该商品的价格就是市场的清算价格。 下面考虑两个简单的单一市场及双边市场的具体实例,并介绍经济均衡思想在拍 卖与投标问题、交通流分配问题中的应用案例。 1.1单一生产商、单一消费者的情形 例1假设市场上只有一个生产商(记为甲)和一个消费者(记为乙)。对某种商 品,他们在不同价格下的供应能力和需求能力如表1所示。举例来说,表中数据的含义 是:当单价低于2万元但大于或等于1万元时,甲愿意生产2t产品,乙愿意购买8t产 品;当单价等于或低于9万元但大于45万元时,乙愿意购买2t产品,甲愿意生产8t 产品;依次类推。那么的市场价格应该是多少? 表1不同价格下的供应能力和需求能力 生产商(甲) 消费者(乙) 单价(万元) 供应能力(t)单价(万元) 需求能力(t) (1)问题分析 仔细观察一下表1就可以看出来,这个具体问题的解是一目了然的:清算价格显 然应该是3万元,因为此时供需平衡(都是6t)。为了能够处理一般情况,下面通过 建立优化模型来解决这个问题 这个问题给人的第一印象似乎没有明确的目标函数,不太像是一个优化问题。不 过,我们可以换一个角度来想问题:假设市场上还有一个虚拟的经销商,他是甲乙进行 交易的中介。那么,为了使自己获得的利润最大,他将总是以可能的最低价格从甲购买 产品,再以可能的最高价格卖给乙,直到进一步的交易无利可图为止。例如,最开始的
-348- 第二十六章 经济与金融中的优化问题 本章主要介绍用 LINGO 软件求解经济、金融和市场营销方面的几个优化问题的案 例。 §1 经济均衡问题及其应用 在市场经济活动中，当市场上某种产品的价格越高时，生产商越是愿意扩大生产 能力（供应能力），提供更多的产品满足市场需求；但市场价格太高时，消费者的消费 欲望（需求能力）会下降。反之，当市场上某种商品的价格越低时，消费者的消费欲望 （需求能力）会上升，但生产商的供应能力会下降。如果生产商的供应能力和消费者的 需求能力长期不匹配，就会导致经济不稳定。在完全市场竞争的环境中，我们总是认为 经济活动应当达到均衡（equilibrium），即生产和消费（供应能力和需求能力）达到平 衡，不再发生变化，这时该商品的价格就是市场的清算价格。 下面考虑两个简单的单一市场及双边市场的具体实例，并介绍经济均衡思想在拍 卖与投标问题、交通流分配问题中的应用案例。 1.1 单一生产商、单一消费者的情形 例 1 假设市场上只有一个生产商（记为甲）和一个消费者（记为乙）。对某种商 品，他们在不同价格下的供应能力和需求能力如表 1 所示。举例来说，表中数据的含义 是：当单价低于 2 万元但大于或等于 1 万元时，甲愿意生产 2t 产品，乙愿意购买 8t 产 品；当单价等于或低于 9 万元但大于 4.5 万元时，乙愿意购买 2t 产品，甲愿意生产 8t 产品；依次类推。那么的市场价格应该是多少？ 表 1 不同价格下的供应能力和需求能力 生产商（甲） 消费者（乙） 单价（万元/t） 供应能力（t） 单价（万元/t） 需求能力（t） 1 2 2 4 3 6 4 8 9 2 4.5 4 3 6 2.25 8 （1）问题分析 仔细观察一下表 1 就可以看出来，这个具体问题的解是一目了然的：清算价格显 然应该是 3 万元/t，因为此时供需平衡（都是 6t）。为了能够处理一般情况，下面通过 建立优化模型来解决这个问题。 这个问题给人的第一印象似乎没有明确的目标函数，不太像是一个优化问题。不 过，我们可以换一个角度来想问题：假设市场上还有一个虚拟的经销商，他是甲乙进行 交易的中介。那么，为了使自己获得的利润最大，他将总是以可能的最低价格从甲购买 产品，再以可能的最高价格卖给乙，直到进一步的交易无利可图为止。例如，最开始的
2t产品他将会以1万元的单价从甲购买,以9万元的单价卖给乙;接下来的2t产品他 会以2万元的单价从甲购买,再以4.5万元的单价卖给乙:再接下来的2t产品他只能以 3万元的单价从甲购买,再以3万元的单价卖给乙(其实这次交易他己经只是保本,但 我们仍然假设这笔交易会发生,例如他为了使自己的营业额尽量大);最后,如果他继 续购买甲的产品卖给乙,他一定会亏本,所以他肯定不会交易。因此,市场清算价格就 是3万元。根据这个想法,我们就可以建立这个问题的线性规划模型。 (2)模型建立 决策变量:设甲以1万元,2万元,3万元,4万元的单价售出的产品数量(单位 t)分别是x1,x2,x3,x4,乙以9万元,45万元,3万元,225万元的单价购买的产品 数量(单位:t)分别是y1,y2,y3,y4 目标函数:就是虚拟经销商的总利润,即 9y1+4.5y2+3y3+2.5y4-x1-2x2-3x3-4x4 约束条件: 供需平衡∑x=∑y 供应限制x1≤2,i=1,2,3,4 消费限制y≤2,i=1,234 (4) 非负限制x2y≥0,i=1,2,34 (5) (3)模型求解 式(1)~(5)是一个线性规划模型,可以用 LINGO求解,对应的 LINGO程序 如下: model gx/1..4/:c1,c2,x,y endsets data c2=9,4.5,3,2.5; enddata max=@sum(gx: c2*y-cl*x)i @sum(gx: x)=@sum(gx: y)i @for (gx: @bnd(0, x, 2)i @bnd(o, y, 2))i
-349- 2t 产品他将会以 1 万元的单价从甲购买，以 9 万元的单价卖给乙；接下来的 2t 产品他 会以 2 万元的单价从甲购买，再以 4.5 万元的单价卖给乙；再接下来的 2t 产品他只能以 3 万元的单价从甲购买，再以 3 万元的单价卖给乙（其实这次交易他已经只是保本，但 我们仍然假设这笔交易会发生，例如他为了使自己的营业额尽量大）；最后，如果他继 续购买甲的产品卖给乙，他一定会亏本，所以他肯定不会交易。因此，市场清算价格就 是 3 万元。根据这个想法，我们就可以建立这个问题的线性规划模型。 （2）模型建立 决策变量：设甲以 1 万元，2 万元，3 万元，4 万元的单价售出的产品数量（单位： t）分别是 1 2 3 4 x , x , x , x ，乙以 9 万元，4.5 万元，3 万元，2.25 万元的单价购买的产品 数量（单位：t）分别是 1 2 3 4 y , y , y , y 。 目标函数：就是虚拟经销商的总利润，即 1 2 3 5 4 1 2 2 3 3 4 4 9y + 4.5y + 3y + 2. y − x − x − x − x （1） 约束条件： 供需平衡 ∑ ∑ = = = 4 1 4 1 i i i i x y （2） 供应限制 xi ≤ 2，i =1,2,3,4 （3） 消费限制 yi ≤ 2 ，i = 1,2,3,4 （4） 非负限制 xi , yi ≥ 0 ，i = 1,2,3,4 （5） （3）模型求解 式（1）～（5）是一个线性规划模型，可以用 LINGO 求解，对应的 LINGO 程序 如下： model: sets: gx/1..4/:c1,c2,x,y; endsets data: c1=1 2 3 4; c2=9,4.5,3,2.5; enddata max=@sum(gx:c2*y-c1*x); @sum(gx:x)=@sum(gx:y); @for(gx:@bnd(0,x,2);@bnd(0,y,2));
求解这个模型,得到如下解答 Global optimal solution found at iteration Objective value 21.00000 Variable Value Reduced cost C1(2) 2.000000 C1(4 4.000000 0.000000 C2(2) 4.500000 0.0000 0.000000 0.000000 Y(1) 2.000000 6.000000 Y(3) 0.000000 0.000000 0.000000 R。ws1 ack or Surp1us Dual price 21.00000 0.000000 3.000000 (4)结果解释 可以看出,最优解为x1=x2=y=y2=2,x3=x4=y3=y4=0。但你肯定觉 得这还是没有解决问题,甚至认为这个模型错了,因为这个解法没有包括3万元单价的 2t交易量。虽然容易验证x=x2=x3=y=y2=y3=0,x4=y4=0也是最优解, 但在一般情况下是难以保证一定求出这个解的。 那么如何才能确定清算价格呢?请仔细思考一下供需平衡约束(2)的对偶价格 ( dual prices)的含义。对偶价格又称影子价格,表示的是对应约束的右端项的价值。 供需平衡约束目前的右端项为0,影子价格为一3,意思就是说如果右端项增加一个很 小的量(即甲的供应量增加一个很小的量),引起的经销商的损失就是这个小量的3倍。 可见,此时的销售单价就是3万元,这就是清算价格 (5)模型扩展 般地,可以假设甲的供应能力随价格的变化情况分为K段,即价格位于区间
-350- end 求解这个模型，得到如下解答： Global optimal solution found at iteration: 5 Objective value: 21.00000 Variable Value Reduced Cost C1( 1) 1.000000 0.000000 C1( 2) 2.000000 0.000000 C1( 3) 3.000000 0.000000 C1( 4) 4.000000 0.000000 C2( 1) 9.000000 0.000000 C2( 2) 4.500000 0.000000 C2( 3) 3.000000 0.000000 C2( 4) 2.500000 0.000000 X( 1) 2.000000 -2.000000 X( 2) 2.000000 -1.000000 X( 3) 0.000000 0.000000 X( 4) 0.000000 1.000000 Y( 1) 2.000000 -6.000000 Y( 2) 2.000000 -1.500000 Y( 3) 0.000000 0.000000 Y( 4) 0.000000 0.5000000 Row Slack or Surplus Dual Price 1 21.00000 1.000000 2 0.000000 -3.000000 （4）结果解释 可以看出，最优解为 2 x1 = x2 = y1 = y2 = ， x3 = x4 = y3 = y4 = 0。但你肯定觉 得这还是没有解决问题，甚至认为这个模型错了，因为这个解法没有包括 3 万元单价的 2t 交易量。虽然容易验证 x1 = x2 = x3 = y1 = y2 = y3 = 0， 0 x4 = y4 = 也是最优解， 但在一般情况下是难以保证一定求出这个解的。 那么如何才能确定清算价格呢？请仔细思考一下供需平衡约束（2）的对偶价格 （dual prices）的含义。对偶价格又称影子价格，表示的是对应约束的右端项的价值。 供需平衡约束目前的右端项为 0，影子价格为－3，意思就是说如果右端项增加一个很 小的量（即甲的供应量增加一个很小的量），引起的经销商的损失就是这个小量的 3 倍。 可见，此时的销售单价就是 3 万元，这就是清算价格。 （5）模型扩展 一般地，可以假设甲的供应能力随价格的变化情况分为 K 段，即价格位于区间
[Pk,Pk)时,供应量最多为ck(k=1,2,…K;0…>q1>q1+=0:0=d<d<…d), 我们把这个函数关系称为需求函数(这里它也是一个阶梯函数)。 设甲以Pk的价格售出的产品数量为x(k=12,…,K,乙以q,的价格购入的产 品数量为y,(j=12…,L)。记co=d=0,则可以建立如下所示的线性规划模型: max ∑qy-∑ PkIk (6) -y=0 0≤xk≤Ck-Ck1,k=1,2,…,K (8) 0≤y1≤d1-d1,j=12,…,L 12两个生产商、两个消费者的情形 例2假设市场上除了例1中的甲和乙外,还有另一个生产商(记为丙)和另一个 消费者(记为丁),他们在不同价格下的供应能力和需求能力如表2所示。此外,从甲 销售到丁的每吨产品的运输成本是1.5万元,从丙销售到乙的每吨产品的运输成本是2 万元,而甲、乙之间没有运输成本,丙、丁之间没有运输成本。这时,市场的清算价格 应该是多少?甲和丙分别生产多少?乙和丁分别购买多少? 表2不同价格下的供应能力和消费能力 生产商(丙) 生产商(丁) 单价(万元) 供应能力(t)单价(万元/t) 供应能力(t) 15 8 (1)问题分析
-351- [ , ) pk pk+1 时，供应量最多为 k c （ k =1,2,L,K ； 0 L> qL > qL+1 = ；0 = d0 < d1 <LdL ）， 我们把这个函数关系称为需求函数（这里它也是一个阶梯函数）。 设甲以 pk 的价格售出的产品数量为 k x （ k = 1,2,L,K ），乙以 qj 的价格购入的产 品数量为 j y （ j =1,2,L, L ）。记c0 = d0 = 0 ，则可以建立如下所示的线性规划模型： ∑ ∑ = = − K k k k L j j j q y p x 1 1 max （6） s.t. 0 1 1 ∑ −∑ = = = L j j K k k x y （7） 0 ≤ k ≤ k − k−1 x c c ，k =1,2,L,K （8） 0 ≤ j ≤ d j − d j−1 y ， j =1,2,L, L （9） 1.2 两个生产商、两个消费者的情形 例 2 假设市场上除了例 1 中的甲和乙外，还有另一个生产商（记为丙）和另一个 消费者（记为丁），他们在不同价格下的供应能力和需求能力如表 2 所示。此外，从甲 销售到丁的每吨产品的运输成本是 1.5 万元，从丙销售到乙的每吨产品的运输成本是 2 万元，而甲、乙之间没有运输成本，丙、丁之间没有运输成本。这时，市场的清算价格 应该是多少？甲和丙分别生产多少？乙和丁分别购买多少？ 表 2 不同价格下的供应能力和消费能力 生产商（丙） 生产商（丁） 单价（万元/t） 供应能力（t） 单价（万元/t） 供应能力（t） 2 1 4 4 6 8 8 12 15 1 8 3 5 6 3 10 （1）问题分析
首先,我们看看为什么要考虑从甲销售到丁的产品的运输成本和从丙销售到乙的 产品的运输成本。如果不考虑这些运输成本,我们就可以认为甲乙丙丁处于同一个市场 上,因此可以将两个生产商(甲和丙)的供应函数合并成一个供应函数,合并后就可以 认为市场上仍然只有一个供应商。类似地,乙和丁的需求函数也可以合并成一个需求函 数,合并后就可以认为市场上仍然只有一个消费者。这样,就回到了例1的情形。 也就是说,考虑运输成本在经济学上的含义,应当是认为甲乙是一个市场(地区 或国家),而丙丁是另一个市场(地区或国家)。运输成本也可能还包括关税等成本,由 于这个成本的存在,两个市场的清算价可能是不同的。 仍然按照例1的思路,可以建立这个问题的线性规划模型。 (2)模型的建立和求解 设甲以1,2,3,4(万元)的单价售出的产品数量(单位:t)分别是A,A2,A3,A4, 乙以9,4.5,3,225(万元)的单价购买的产品数量(单位:t)分别是X1X2,X3,X4 丙以2,4,6,8(万元)的单价售出的产品数量(单位:t)分别是B,B2,B3,B4,丁 以15,8,5,3(万元)的单价购买的产品数量(单位:t分别是Y1Y2,H3,F。此外, 假设AX和AY分别是甲向乙和丁的供货量,BX和BY分别是丙向乙和丁的供货量。 这些决策变量之间的关系参见示意图1。 A1,A2A3,A4 B1B2,B3,B4 乙的的量 H1,2,3,4 图1决策变量之间的关系 目标函数仍然是虚拟经销商的总利润,约東条件仍然是四类(供需平衡、供应限制 需求限制和非负限制),不过这时应注意供需平衡约束应该是包括图1所示的决策变量 之间的关系: AX+ Ar=A+ A2+ A3+ A (10) BX+BY=B,+B,+B,+B4 (11) AX+BX=X+X+x+X (12) 352-
-352- 首先，我们看看为什么要考虑从甲销售到丁的产品的运输成本和从丙销售到乙的 产品的运输成本。如果不考虑这些运输成本，我们就可以认为甲乙丙丁处于同一个市场 上，因此可以将两个生产商（甲和丙）的供应函数合并成一个供应函数，合并后就可以 认为市场上仍然只有一个供应商。类似地，乙和丁的需求函数也可以合并成一个需求函 数，合并后就可以认为市场上仍然只有一个消费者。这样，就回到了例 1 的情形。 也就是说，考虑运输成本在经济学上的含义，应当是认为甲乙是一个市场（地区 或国家），而丙丁是另一个市场（地区或国家）。运输成本也可能还包括关税等成本，由 于这个成本的存在，两个市场的清算价可能是不同的。 仍然按照例 1 的思路，可以建立这个问题的线性规划模型。 （2）模型的建立和求解 设甲以 1，2，3，4（万元）的单价售出的产品数量（单位：t）分别是 1 2 3 4 A , A , A , A ， 乙以 9，4.5，3，2.25（万元）的单价购买的产品数量（单位：t）分别是 1 2 3 4 X , X , X , X ； 丙以 2，4，6，8（万元）的单价售出的产品数量（单位：t）分别是 1 2 3 4 B , B , B , B ，丁 以 15，8，5，3（万元）的单价购买的产品数量（单位：t）分别是 1 2 3 4 Y ,Y ,Y ,Y 。此外， 假设 AX 和 AY 分别是甲向乙和丁的供货量， BX 和 BY 分别是丙向乙和丁的供货量。 这些决策变量之间的关系参见示意图 1。 图 1 决策变量之间的关系 目标函数仍然是虚拟经销商的总利润，约束条件仍然是四类（供需平衡、供应限制、 需求限制和非负限制），不过这时应注意供需平衡约束应该是包括图 1 所示的决策变量 之间的关系： AX + AY = A1 + A2 + A3 + A4 （10） BX + BY = B1 + B2 + B3 + B4 （11） AX + BX = X1 + X2 + X3 + X4 （12）
Ar+Br=Y+Y2+Y+Y4 (13) 此外的其它约束实际上只是一个简单的变量上界约束 下面直接给出 LINGO程序: model sets num1/1..4/:c1,c2,c3,c4,d1,d2,A,B,X,Y num2/1, 2/: AXY,BXY endsets data c1=94.532.25; c2=15853; d1=1344 d2=1234 max=@sum(num1: cl*x+c2*y-C3*A-C4*B)-2*BXY(1)-1. 5*AXY(2) @sum(numl: A)-@sum(num2: AXY)=0 @sum(numl: B)-@sum(num2: BXY)=0 AXY(1)+BXY(1)-@sum(num1: X)=0 AXY(2)+BXY(2)-@sum (numl: Y @for(numl: @bnd (0, A, 2)i @bnd(0, x, 2)i@bnd(0, B, d1); @bnd(o,Y, d2)) 求解这个模型,得到如下解答: Global optimal solution found at iteration: 44.00000 Variable Reduced cost 9.000000 8.000000 0.000000 C3(1 1.000000 2.000000 0.000000 C3(3) 3.000000 0.00000
-353- AY + BY = Y1 + Y2 + Y3 + Y4 （13） 此外的其它约束实际上只是一个简单的变量上界约束。 下面直接给出 LINGO 程序： model: sets: num1/1..4/:c1,c2,c3,c4,d1,d2,A,B,X,Y; num2/1,2/:AXY,BXY; endsets data: c1=9 4.5 3 2.25; c2=15 8 5 3; c3=1 2 3 4; c4=2 4 6 8; d1=1 3 4 4; d2=1 2 3 4; enddata max=@sum(num1:c1*x+c2*y-c3*A-c4*B)-2*BXY(1)-1.5*AXY(2); @sum(num1:A)-@sum(num2:AXY)=0; @sum(num1:B)-@sum(num2:BXY)=0; AXY(1)+BXY(1)-@sum(num1:X)=0; AXY(2)+BXY(2)-@sum(num1:Y)=0; @for(num1:@bnd(0,A,2);@bnd(0,X,2);@bnd(0,B,d1);@bnd(0,Y,d2)); end 求解这个模型，得到如下解答： Global optimal solution found at iteration: 0 Objective value: 44.00000 Variable Value Reduced Cost C1( 1) 9.000000 0.000000 C1( 2) 4.500000 0.000000 C1( 3) 3.000000 0.000000 C1( 4) 2.250000 0.000000 C2( 1) 15.00000 0.000000 C2( 2) 8.000000 0.000000 C2( 3) 5.000000 0.000000 C2( 4) 3.000000 0.000000 C3( 1) 1.000000 0.000000 C3( 2) 2.000000 0.000000 C3( 3) 3.000000 0.000000
C3(4) 4.000000 C4(1 2.000000 0.0000 C4(2) 4.000000 C4(3) 0.000000 D1(4 4.000000 0.000000 1.000000 0.000000 2.000000 0.0000 D2(3) 3.000000 A(3) 2.000000 0.000000 B(1) 1.000000 2.500000 B(3) 0.000000 1.500000 0.000000 3.500 2.000000 0.000000 Y(1) 000000 10.50000 3.5000 Y(3) 3.000000 0.5000000 0.000000 1.50000 0.000000 0.000000 BXY( 1) 0.000000 BXY( 2) 4.000000 R。wS1 ack or Surplus Dual price 44.00000 1.000000 0.000000 4.500000 0.000000 3.000000 0.000000 4.500000 354
-354- C3( 4) 4.000000 0.000000 C4( 1) 2.000000 0.000000 C4( 2) 4.000000 0.000000 C4( 3) 6.000000 0.000000 C4( 4) 8.000000 0.000000 D1( 1) 1.000000 0.000000 D1( 2) 3.000000 0.000000 D1( 3) 4.000000 0.000000 D1( 4) 4.000000 0.000000 D2( 1) 1.000000 0.000000 D2( 2) 2.000000 0.000000 D2( 3) 3.000000 0.000000 D2( 4) 4.000000 0.000000 A( 1) 2.000000 -2.000000 A( 2) 2.000000 -1.000000 A( 3) 2.000000 0.000000 A( 4) 0.000000 1.000000 B( 1) 1.000000 -2.500000 B( 2) 3.000000 -0.5000000 B( 3) 0.000000 1.500000 B( 4) 0.000000 3.500000 X( 1) 2.000000 -6.000000 X( 2) 2.000000 -1.500000 X( 3) 0.000000 0.000000 X( 4) 0.000000 0.7500000 Y( 1) 1.000000 -10.50000 Y( 2) 2.000000 -3.500000 Y( 3) 3.000000 -0.5000000 Y( 4) 0.000000 1.500000 AXY( 1) 4.000000 0.000000 AXY( 2) 2.000000 0.000000 BXY( 1) 0.000000 3.500000 BXY( 2) 4.000000 0.000000 Row Slack or Surplus Dual Price 1 44.00000 1.000000 2 0.000000 -3.000000 3 0.000000 -4.500000 4 0.000000 -3.000000 5 0.000000 -4.500000
(3)结果解释 可以看到,最优解为A1=A2=A3=X1=X2=2,B1=1,B2=3,H1=1 Y2=3,Y3=3,AX=BY=4,AY=2,A4=B3=B4=X3=X4=4=BX=0。 也就是说,甲将向丁销售2t产品,丙不会向乙销售。 那么如何才能确定清算价格呢?与例1类似,约束(2)是针对生产商甲的供需平 衡条件,目前的右端项为0,影子价格为一3,意思就是说如果右端项增加一个很少的 量(即甲的供应量增加一个很少的量),引起的经销商的损失就是这个小量的3.5倍。 可见,此时甲的销售单价就是3万元,这就是甲面对的清算价格。 完全类似地,可以知道生产商丙面对的清算价格为4.5。自然地,乙面对的清算价 格也是3,丁面对的清算价格也是4.5,因为甲乙位于同一个市场,而丙丁也位于同一 个市场。这两个市场的清算价之差正好等于从甲、乙到丙、丁的运输成本(1.5),这 是非常合理的 (4)模型扩展 可以和1.1一样,将上面的具体模型一般化,即考虑供应函数和需求函数的分段数 不是固定为4,而是任意有限正整数的情形 很自然地,上面的方法很容易推广到不仅仅是2个市场,而是任意有限个市场的情 形。理论上看这当然没有什么难度,只是这时变量会更多,数学表达式变得更复杂一些。 1.3拍卖与投标问题 例3假设一家拍卖行对委托的5类艺术品对外拍卖,采用在规定日期前投标人提 交投标书的方式进行,最后收到了来自4个投标人的投标书。每类项目的数量、投标人 对每个项目的投标价格如表3中所示。例如,有3件第4类艺术品;对每件第4类艺术品 投标人1,2,3愿意出的最高价分别为6,1,3,2(货币单位,如万元)。此外,假 设每个投标人对每类艺术品最多只能购买1件,并且每个投标人购买的艺术品的总数不 能超过3件。那么,哪些艺术品能够卖出去?卖给谁?这个拍卖和投标问题中每类物品 的清算价应该是多少? 表3拍卖与投标信息 招标项目类型 招标项目的数量 投标人1 1196 投标人2 投标价格 222784 338963 436132 54354 投标人3 7 (1)问题分析 这个具体问题在实际中可能可以通过对所有投标的报价进行排序来解决,例如可以 总是将艺术品优先卖给出价最高的投标人。但这种方法不太好确定每类艺术品的清算 -355
-355- （3）结果解释 可以看到，最优解为 A1 = A2 = A3 = X1 = X2 = 2， 1 B1 = ， 3 B2 = ， 1 Y1 = ， 3 Y2 = ，Y3 = 3，AX = BY = 4 ，AY = 2 ，A4 = B3 = B4 = X3 = X4 = Y4 = BX = 0 。 也就是说，甲将向丁销售2t产品，丙不会向乙销售。 那么如何才能确定清算价格呢？与例1类似，约束（2）是针对生产商甲的供需平 衡条件，目前的右端项为0，影子价格为－3，意思就是说如果右端项增加一个很少的 量（即甲的供应量增加一个很少的量），引起的经销商的损失就是这个小量的3.5倍。 可见，此时甲的销售单价就是3万元，这就是甲面对的清算价格。 完全类似地，可以知道生产商丙面对的清算价格为4.5。自然地，乙面对的清算价 格也是3，丁面对的清算价格也是4.5，因为甲乙位于同一个市场，而丙丁也位于同一 个市场。这两个市场的清算价之差正好等于从甲、乙到丙、丁的运输成本（1.5），这 是非常合理的。 （4）模型扩展 可以和1.1一样，将上面的具体模型一般化，即考虑供应函数和需求函数的分段数 不是固定为4，而是任意有限正整数的情形。 很自然地，上面的方法很容易推广到不仅仅是2个市场，而是任意有限个市场的情 形。理论上看这当然没有什么难度，只是这时变量会更多，数学表达式变得更复杂一些。 1.3 拍卖与投标问题 例3 假设一家拍卖行对委托的5类艺术品对外拍卖，采用在规定日期前投标人提 交投标书的方式进行，最后收到了来自4个投标人的投标书。每类项目的数量、投标人 对每个项目的投标价格如表3中所示。例如，有3件第4类艺术品；对每件第4类艺术品， 投标人1，2，3愿意出的最高价分别为6，1，3，2（货币单位，如万元）。此外，假 设每个投标人对每类艺术品最多只能购买1件，并且每个投标人购买的艺术品的总数不 能超过3件。那么，哪些艺术品能够卖出去？卖给谁？这个拍卖和投标问题中每类物品 的清算价应该是多少？ 表3 拍卖与投标信息 招标项目类型 1 2 3 4 5 招标项目的数量 1 2 3 3 4 投标人1 9 2 8 6 3 投标人2 6 7 9 1 5 投标人3 7 8 6 3 4 投标价格 投标人4 5 4 3 2 1 （1）问题分析 这个具体问题在实际中可能可以通过对所有投标的报价进行排序来解决，例如可以 总是将艺术品优先卖给出价最高的投标人。但这种方法不太好确定每类艺术品的清算
价,所以我们这里还是借用前面两个例子中的方法,即假设有一个中间商希望最大化自 己的利润,从而建立这个问题的线性规划模型。 (2)问题的一般提法和假设 先建立一般的模型,然后求解本例的具体问题,设有n类物品需要拍卖,第j类物 品的数量为s1(j=1,2,…,n):有m个投标者,投标者i(i=1,2,…m)对第j类 物品的投标价格为b(假设非负)。投标者订对每类物品最多购买一件,且总件数不能 超过;。我们的目标之一是要确定第j类物品的清算价格P,,它应当满足下列假设条 件 i)成交的第j类物品的数量不超过s,(j=1,2,…,n) ii)对第j类物品的报价低于P,的投标人将不能获得第j类物品; i1i)如果成交的第j类物品的数量少于S(j=12,…n)可以认为P,=0(除 非拍卖方另外指定一个最低的保护价) iv)对第j类物品的报价高于p,的投标人有权获得第j类物品,但如果他有权获 得的物品超过3件,那么我们假设他总是希望使自己的满意度最大(满意度可以用他的 报价与市场清算价之差来衡量)。 (3)优化模型 用0-1变量xn表示是否分配一件第j类物品给投标者i,即x=1表示分配,而 x=0表示不分配。目标函数仍然是虚拟的中间商的总利润(认为这些利润全部是拍 卖行的利润也可以),即 b 除变量取值为0或1的约束外,问题的约束条件主要是两类:每类物品的数量限制 和每个投标人所能分到的物品的数量限制,即 ∑x≤S,j=12,…,n xn≤C,i=1,2 (16) 356
-356- 价，所以我们这里还是借用前面两个例子中的方法，即假设有一个中间商希望最大化自 己的利润，从而建立这个问题的线性规划模型。 （2）问题的一般提法和假设 先建立一般的模型，然后求解本例的具体问题，设有 n 类物品需要拍卖，第 j 类物 品的数量为 j s （ j =1,2,L,n ）；有 m 个投标者，投标者i （i = 1,2,Lm ）对第 j 类 物品的投标价格为bij（假设非负）。投标者i 对每类物品最多购买一件，且总件数不能 超过 i c 。我们的目标之一是要确定第 j 类物品的清算价格 pj ，它应当满足下列假设条 件： i）成交的第 j 类物品的数量不超过 j s （ j =1,2,L,n ）； ii）对第 j 类物品的报价低于 pj 的投标人将不能获得第 j 类物品； iii）如果成交的第 j 类物品的数量少于 j s （ j =1,2,L,n ）可以认为 pj = 0（除 非拍卖方另外指定一个最低的保护价）； iv）对第 j 类物品的报价高于 pj 的投标人有权获得第 j 类物品，但如果他有权获 得的物品超过3件，那么我们假设他总是希望使自己的满意度最大（满意度可以用他的 报价与市场清算价之差来衡量）。 （3）优化模型 用0 −1变量 ij x 表示是否分配一件第 j 类物品给投标者i ，即 xij = 1表示分配，而 xij = 0表示不分配。目标函数仍然是虚拟的中间商的总利润（认为这些利润全部是拍 卖行的利润也可以），即 ∑∑= = m i n j ij ij b x 1 1 （14） 除变量取值为0或1的约束外，问题的约束条件主要是两类：每类物品的数量限制 和每个投标人所能分到的物品的数量限制，即 j m i ij ∑x ≤ s =1 ，j =1,2,L, n （15） i n j ij ∑x ≤ c =1 ，i = 1,2,L,m (16)
模型就是在约束(15)、(16)下最大化目标函数(14)。 (4)模型求解 编写的 LINGO程序如下 MODEL TITLE拍卖与投标 SETS IoN/1..5/:S; L工NK( BIDDER, AUCTION ENDSETS DATA C=3333; 7 6 ENDDATA MAX=@SUM (LINK: B*X) @FOR (AUCTION(J) [AUC LIM GSUM(BIDDER(I): X(I,J))<S(J)) FOR( BIDDER(工) [B工DLIM]@SUM( AUCTION(J):X(工,J))<C(工)); @FOR (LINK: CBND(0, X,1) END 需要指出的是,上面程序中DATA语句的数据表是直接从网ORD文档中复制(ctr1 +C)后粘贴(ctx1+V)过来的,所以显示格式继续保持了WoRD文档的风格 (5)求解结果解释 可以看到,最优解为:投标人1得到艺术品1,3,4,投标人2,3都得到艺术品2, 3,5,投标人4得到艺术品4,5。结果,第4,5类艺术品各剩下1件没有成交。 那么如何才能确定清算价格呢?与例1和例2类似,约束“ AUC LIM”是针对每类 艺术品的数量限制的,对应的影子价格就是其清算价格:即5类艺术品的清算价格分别 是5,5,3,0,0。第4,5类艺术品有剩余,所以清算价格为0,这是符合前面的假设 可以指出的是:即使上面模型中不要求x为0-1变量(即只要求取0~1之间的实
-357- 模型就是在约束（15）、（16）下最大化目标函数（14）。 （4）模型求解 编写的LINGO程序如下： MODEL: TITLE 拍卖与投标; SETS: AUCTION/1..5/: S; BIDDER/1..4/ : C; LINK(BIDDER,AUCTION): B, X; ENDSETS DATA: S=1 2 3 3 4; C=3 3 3 3; B= 9 2 8 6 3 6 7 9 1 5 7 8 6 3 4 5 4 3 2 1 ; ENDDATA MAX=@SUM(LINK: B*X); @FOR(AUCTION(J): [AUC_LIM] @SUM(BIDDER(I): X(I,J)) < S(J) ); @FOR(BIDDER(I): [BID_LIM] @SUM(AUCTION(J): X(I,J)) < C(I) ); @FOR(LINK: @BND(0,X,1)); END 需要指出的是，上面程序中DATA语句的数据表是直接从WORD文档中复制（Ctrl +C）后粘贴（Ctrl+V）过来的，所以显示格式继续保持了WORD文档的风格。 （5）求解结果解释 可以看到，最优解为：投标人1得到艺术品1，3，4，投标人2，3都得到艺术品2， 3，5，投标人4得到艺术品4，5。结果，第4，5类艺术品各剩下1件没有成交。 那么如何才能确定清算价格呢？与例1和例2类似，约束“AUC_LIM”是针对每类 艺术品的数量限制的，对应的影子价格就是其清算价格：即5类艺术品的清算价格分别 是5，5，3，0，0。第4，5类艺术品有剩余，所以清算价格为0，这是符合前面的假设 的。 可以指出的是：即使上面模型中不要求 ij x 为0 −1变量（即只要求取0～1之间的实
