谢金星lingo课件优化建模与LINGO第06章.ppt

优化建模与LINDO/LINGO软件 第 6 章 经济与金融中的优化问题,内容提要,1. 经济均衡问题及其应用 2. 投资组合问题 3. 市场营销问题,1. 经济均衡问题及其应用,单一生产商、单一消费者的情形 －例6.1: 市场清算价格,市场上有一个生产商（甲）和一个消费者（乙）对某种产品，他们在不同价格下的供应能力和需求能力为:,市场的清算价格应该是多少?,甲以1、2、3、4万元的单价售出的产品数量分别是A1 ，A２， A３， A４ （吨）,供需平衡： A1+A２+ A３+ A４= x1+x2+x3+x4,供应限制： A1 ，A２， A３， A４ ≤ 2,决策变量,目标函数,约束条件,建立线性规划模型(LP),,乙以9、4.5、3、2.25万元的单价购买的产品数量分别是x1，x2，x3，x4（吨）,非负限制： A1,A２, A３, A４, x1,x2,x3,x4 ≥ 0,消费限制： x1，x2，x3，x4 ≤ 2,9x1+4.5x2+3x3+2.5x4 -A1-2A２-3A３-4 A４,模型求解,用LINDO求解，最优解:A1=A2=x1=x2=2, A3=A4=x3=x4=0,思考:供需平衡约束的对偶价格含义,如果右端项增加一个很小的量，引起的经销商的损失就是这个小量的3倍。

清算价格: 3万元,供需平衡约束目前的右端项为0，影子价格为-3结果解释,模型扩展,假设甲的供应能力随价格的变化情况分为K段，即价格位于区间[pk , pk+1)时，供应量最多为ck (k=1,2,…,K; 0 p1 p2 …pK+1 =∞; 0 =c0 c1 c2 …cK)，我们把这个函数关系称为供应函数（这里它是一个阶梯函数）,假设乙的消费能力随价格的变化情况分为L段，即价格位于区间(qk+1,qk]时，消费量最多为dk,(k=1,2,…,L; q1 …qLqL+1 =0; 0=d0 d1 d2 …dL) ，我们把这个函数关系称为需求函数（这里它也是一个阶梯函数）,建立线性规划模型(LP),设甲以pk的价格售出的产品数量为Ak (k=1,2,…,K)，乙以qk的价格购入的产品数量为Xk ( (k=1,2,…,L）记c0 = d0 =0,,两个生产商、两个消费者的情形 －例6.2: 市场清算价格,市场上有两个生产商（甲和丙）和两个消费者（乙和丁）他们在不同价格下的供应能力和需求能力为:,甲销售到丁的运输成本是1.5（万元）/吨,丙销售到乙的运输成本是2（万元）/吨,甲、乙之间，丙、丁之间没有运输成本,市场的清算价格应该是多少？,甲和丙分别生产多少？,乙和丁分别购买多少？,目标,关键是考虑这些运输成本,认为甲乙是一个市场（地区或国家），而丙丁是另一个市场（地区或国家）。

关税成本的存在，两个市场的清算价可能是不同 的 问题分析,甲以1、2、3、4万元的单价售出的产品数量分别是A1 ，A２， A３， A４ （吨）,决策变量,目标函数,,乙以9、4.5、3、2.25万元的单价购买的产品数量分别是x1，x2，x3，x4（吨）,9x1+4.5x2+3x3+2.5x4+15y1+8y2+5y3+3y4 -2BX-1.5AY- A1-2A２-3A３-4 A４-2B1-4B２-6B３-8B４,丙以2、4、6、8万元的单价售出的产品数量分别是B 1 ，B ２， B ３， B ４ （吨）,丁以15、8、5、3万元的单价购买的产品数量分别是y1，y2，y3，y4（吨）,虚拟经销商的总利润最大,建立线性规划模型(LP),供需平衡：AX+AY= A1+A２+ A３+ A４ BX+BY = B1+B２+ B３+ B４ AX+BX=x1+x2+x3+x4 AY+BY=y1+y2+y3+y4,约束条件,,供应限制,消费限制,非负限制,决策变量之间关系,结果解释,最优解为A1=A2=A3=x1=x2=2, B1=1，B2=3，y1=1，y2=3，y3=3，AX=BY=4，A4=B3=B4=x3=x4=y4=BY=0. AY=2，也即甲将向丁销售2吨产品，丙不会向乙销售,如何才能确定清算价格呢？,针对甲的供需平衡条件，目前的右端项为0，影子价格为-3.5，意思就是说如果右端项增加一个很小的量，引起的经销商的损失就是这个小量的3.5倍。

可见，此时甲的销售单价就是3万元，这就是甲面对的清算价格！,生产商丙面对的清算价格为5则乙面对的清算价格就是是3.5，丁面对的清算价格就是5，因为甲乙位于同一个市场，而丙丁也位于同一个市场这两个市场的清算价之差正好等于从甲、乙到丙、丁的运输成本（1.5）拍卖与投标问题- 例6.3: 艺术品拍卖问题,假设每个投标人对每类艺术品最多只能购买1件,每个投标人购买的艺术品的总数不能超过3件,问哪些艺术品能够卖出去？卖给谁？每类物品的清算价应该是多少？,假设有一个中间商希望最大化自己的例润,问题分析与假设,设有N类物品需要拍卖，第j类物品的数量为Sj（j=1, 2，…,N）；有M个投标者，投标者i（i=1，2，…,M）对第j类物品的投标价格为bij（假设非负）投标者i对每类物品最多购买一件，且总件数不能超过ci实际中可以通过对所有投标的报价进行排序来解决,目标：确定第j类物品的清算价格pj，它应当满足下列假设条件： 成交的第j类物品的数量不超过Sj（j=1，2，…,N）； 对第j类物品的报价低于pj的投标人将不能获得第j类物品； 如果成交的第 j 类物品的数量少于Sj（j=1， 2，…,N），可以认为pj=0 （除非拍卖方另外指定一个最低的保护价）； 对第j类物品的报价高于pj的投标人有权获得第j类物品，但如果他有权获得的物品超过3件，那么假设他总是希望使自己的满意度最大（满意度可以用他的报价与市场清算价之差来衡量）。

线性规划模型(LP),用0-1变量xij表示是否分配一件第j类物品给投标者i，即xij=1表示分配，而xij=0表示不分配目标函数,虚拟的中间商的总利润最大 ,即,,约束条件,(1)每类物品的数量限制,,(2)每个投标人所能分到的物品的数量限制,,MODEL: TITLE 拍卖与投标; SETS: ! S,C,B,X的含义就是上面建模时给出的定义; AUCTION: S; BIDDER : C; LINK(BIDDER,AUCTION): B, X; ENDSETS DATA: ! 通过文本文件输入数据; AUCTION=@FILE(AUCTION.TXT); BIDDER =@FILE(AUCTION.TXT); S=@FILE(AUCTION.TXT); C=@FILE(AUCTION.TXT); B=@FILE(AUCTION.TXT); 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: @BIN(X)); ! 0-1变量限制; END,LINGO模型为,最优解为：投标人1得到艺术品1、3、4，投标人2、3都得到艺术品2、3、5，投标人4得到艺术品4、5. 结果，第4、5类艺术品各剩下1件没有成交。

如何才能确定清算价格呢？,约束“AUC_LIM”是针对每类艺术品的数量限制的，对应的影子价格就是其清算价格：即5类艺术品的清算价格分别是5、5、3、0、0第4、5类艺术品有剩余，所以清算价格为0,推广:大学生的选课问题,交通流均衡问题－例6.4: 公路网汽车分布,居民区,工作区,B,C,D,A,,,,,,每天上班时间有6千辆小汽车要从居民区A前往工作区D,5条道路上每辆汽车的平均行驶时间和汽车流量之间的关系见下表,这些汽车将如何在每条道路上分布？,问题分析,交通流的规律:每辆汽车都将选择使自己从A到D运行时间最少的路线,必然的结果:无论走哪条路线从A到D，最终花费的时间应该是一样的，因为花费时间较长的那条线路上的部分汽车总会改变自己的路线，以缩短自己的行驶时间,汽车在每条道路上的分布将达到均衡状态,决策变量,共有20个决策变量Y(j)和X(i,j)，(i=2， 3，4；j=AB，AC，BC，BD，CD）,如Y（AB）表示道路AB上的总的流量，进一步分解成三部分： 道路AB上的流量不超过2时的流量，用X（2，AB）表示； AB上的流量超过2但不超过3时，超过2的流量部分用X（3，AB）表示； AB上的流量超过3但不超过4时，超过3的流量部分用X（4，AB）表示。

线性规划模型(LP),目标函数,约束条件,总的堵塞时间最小,用T(i，j)表示流量X(i，j)对应的堵塞时间,,并不是总 堵塞时间,T(i，j)关于i是单调增加的，即不断增加的车流只会使以前的堵塞加剧而不可能使以前的堵塞减缓故关于决策变量X(i，j)而言，与希望优化的目标的单调性一致,每条道路上的总流量Y等于该道路上的分流量X的和 道路交汇处A、B、C、D(称为节点)的流量守恒（即流入量等于流出量） 决策变量的上限限制，如 X(2，AB)≤2，X(3，AB)≤1，X（4，AB）≤1等,LINGO模型如下：,MODEL: TITLE 交通流均衡; SETS: ROAD/AB,AC,BC,BD,CD/:Y; CAR/2,3,4/; LINK(CAR,ROAD): T, X; ENDSETS DATA: ! 行驶时间; T=20,52,12,52,20 30,53,13,53,30 40,54,14,54,40; ENDDATA [OBJ] MIN=@SUM(LINK: T*X); ! 目标函数;,! 四个节点的流量守恒条件; [NODE_A] Y(@INDEX(AB))+Y(@INDEX(AC)) = 6; [NODE_B] Y(@INDEX(AB))=Y(@INDEX(BC))+Y(@INDEX(BD)); [NODE_C] Y(@INDEX(AC))+Y(@INDEX(BC))=Y(@INDEX(CD)); [NODE_D] Y(@INDEX(BD))+Y(@INDEX(CD))=6; ! 每条道路上的总流量Y等于该道路上的分流量X的和; @FOR( ROAD(I): [ROAD_LIM] @SUM(CAR(J): X(J,I)) = Y(I) ); ! 每条道路的分流量X的上下界设定; @FOR(LINK(I,J)|I#EQ#1: @BND(0,X(I,J),2) ); @FOR(LINK(I,J)|I#GT#1: @BND(0,X(I,J),1) ); END,均衡时道路AB、AC、BC、BD、CD的流量分别是4、2、2、2、4（千辆车）。

注意这时得到的目标函数452并不是真正的总运行和堵塞时间,真正运行时间是：每辆车通过AB、AC、BC、BD、CD道路分别需要40、52、12、52、40分钟，也就是三条路线ABD、ACD、ABCD上都需要92分钟，所以这也说明交通流确实达到了均衡于是，均衡时真正的总运行时间应该是6*92=552（千辆车*分钟）,结果解释,模型讨论,均衡解并不一定是最优的流量分配方案，故上面的解并不是最优解假设有一个权威的机构来统筹安排，如何最优分配这些交通流，使所有汽车的总运行时间最小？,计算新增的流量X(i,j)，(i=2, 3,4；j=AB,AC,BC,BD,CD）造成的实际堵塞时间以道路AB为例：,当流量为2（千辆）时，每辆车的通过时间为20分钟，所以总通过时间是40（千辆车*分钟） 当流量增加一个单位（1千辆）达到3（千辆）时，每辆车的通过时间为30分钟，所以总通过时间是90（千辆车*分钟） 当流量再增加一个单位达到4（千辆）时，每辆车的通过时间为40分钟，所以总通过时间是160（千辆车*分钟）,这样可以得到单位流量的增加导致总行。