建立线性规划模型.ppt

《建立线性规划模型.ppt》由会员分享，可在线阅读，更多相关《建立线性规划模型.ppt（39页珍藏版）》请在三一办公上搜索。

1、拍卖与投标问题-例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、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)每个投标人所能分到的物品的数量限制,

3、MODEL:TITLE 拍卖与投标;SETS:!S,C,B,X的含义就是上面建模时给出的定义;AUCTION:S;BIDDER:C;LINK(BIDDER,AUCTION):B,X;ENDSETSDATA:!通过文本文件输入数据;AUCTION=FILE(AUCTION.TXT);BIDDER=FILE(AUCTION.TXT);S=FILE(AUCTION.TXT);C=FILE(AUCTION.TXT);B=FILE(AUCTION.TXT);ENDDATAMAX=SUM(LINK:B*X);!目标函数;FOR(AUCTION(J):!拍卖数量限制 AUC_LIM SUM(BIDDER(I

4、):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

5、.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上的总的流量，

6、进一步分解成三部分：道路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(称为节点)的流量守恒（即流

7、入量等于流出量）决策变量的上限限制，如 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;ENDSETSDATA:!行驶时间;T=20,52,12,52,20 30,53,13,53,30 40,54,14,54,40;ENDDATAOBJ MIN=SUM(LINK:T*X);!目标函数;,!四个节点的流量守恒条件;NODE_A Y(INDEX(AB)+Y(INDEX(AC)=6;NODE_B Y(INDEX(AB)

8、=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（

9、千辆车）。注意这时得到的目标函数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）造成的实际堵塞时间。以道路A

10、B为例：,当流量为2（千辆）时，每辆车的通过时间为20分钟，所以总通过时间是40（千辆车*分钟）当流量增加一个单位（1千辆）达到3（千辆）时，每辆车的通过时间为30分钟，所以总通过时间是90（千辆车*分钟）当流量再增加一个单位达到4（千辆）时，每辆车的通过时间为40分钟，所以总通过时间是160（千辆车*分钟）,这样可以得到单位流量的增加导致总行驶时间的增量和汽车流量之间的关系，如下表,用总行驶时间的增量数据代替前面模型中的每辆车的行驶时间数据T(i，j)，重新求解LINGO模型,最优的车流分配方式是：道路AB、AC、BD、CD的流量都是3千辆车，道路BC上无流量；总运行时间为498（千辆车*分

11、钟），优于均衡时的结果552。此时，每辆车的运行时间=498/6=83（分钟），少于均衡时的92（分钟）,2.投资组合问题,期望年收益率至少达到15%，应当如何投资？,基本的投资组合模型-例6.5:股票投资问题,问题分析,收益不确定,收益的期望值,风险 收益的方差,一种股票收益的均值衡量这种股票的平均收益状况,一种股票收益的方差衡量这种股票收益的波动幅度,两种股票收益的协方差表示他们之间的相关程度,方差越大，风险越大；方差越小，风险越小。,数学期望：ER1=0.0890833,ER2=0.213667,ER3=0.234583协方差矩阵：COV=,假设股票A、B、C每年的收益率分别为R1，R2

12、和R3,模型建立,年收益率（的数学期望）不低于15%,资金 全部用于投资这三种股票,决策变量,x1投资股票A,x2投资股票B,x3投资股票C,约束条件,x1,x2,x3 0，x1+x2+x3=1,x1ER1+x2ER2+x3ER3 0.15,目标函数,年投资收益率的方差极小,二次规划模型(QP),A占53%，B占36%，C占11%,现有一种无风险的投资方式(如购买国库券)。假设国库券的年收益率为5%，如何考虑例6.5中的问题？,存在无风险资产时的投资组合模型-例6.6:,问题分析,无风险的投资方式的收益固定,方差为0,特例,假设国库券的投资方式记为D,投资A占8%，B占42%，C占14%，D占

13、34%,期望收益:15%10%,投资A大约占4%，B占21%，C占7%，D（国库券）占67%,结果分析,风险资产之间的投资比例与期望收益和风险偏好无关,风险资产本身相互之间的比例不变,变化的只是投资于风险资产与无风险资产之间的比例,分离定理,Tobin教授,1981,诺贝尔经济学奖,继续考虑例6.5（期望收益率仍定为15%）。假设握有的股票比例为：股票A占50%，B占35%，C占15%。如按交易额的1%收取交易费，,考虑交易成本的的投资组合模型-例6.7:,问题:是否需要对手上的股票进行买卖（换手）？,模型建立,决策变量,x1投资股票A,x2投资股票B,x3投资股票C,假设购买股票A、B、C的

14、比例为y1、y2和 y3,假设卖出股票A、B、C的比例为z1、z2和 z3,投资A大约占52.647%，B占35%，C占12.299%，,约束条件,x1,x2,x3 0，y1,y2,y3 0,z1,z2,z3 0。,注:yi与zi（i=1，2，3）中最多只能有一个严格取正数,x1+x2+x3+0.01(y1+y2+y3+z1+z2+z3)=1,注:持有的总资金守恒,ci为当前握有的各支股票的份额,xi=ci+yi-zi（i=1，2，3）,三者之和略小于100%,为什么?,能否通过一定方式避免协方差的计算，对模型进行简化呢？,利用股票指数简化投资组合模型-例6.8:,线性回归,利用股票指数,假设

15、每只股票的收益与股票指数成线性关系,M表示股票指数,均值为m0=E(M)，方差为s02=D(M),股票i，其价值Ri=ui+biM+ei,ei是一个随机误差项,均值为E(ei)=0，方差为si2=D(ei),假设随机误差项ei是与其他股票j（ji）和股票指数M都是独立的,E(eiej)=E(eiM)=0,如何根据所给数据经过回归计算得到ui 和 bi?,记12年的数据为 M(k)，Ri(k)，（k=1，2，,12）,优化问题,结果,M的均值m0=1.191458，方差为s02=0.02873661,标准差为s0=0.1695188,A:u1=0.5639761，b1=0.4407264，s12

16、=0.005748320，s1=0.07581767,B:u2=-0.2635059，b2=1.239802，s22=0.01564263，s2=0.1250705,C:u3=-0.5809590，b3=1.523798，s32=0.03025165，s3=0.1739300,年收益率(数学期望)不低于15%,决策变量,x1投资股票A,x2投资股票B,x3投资股票C,约束条件,x1,x2,x3 0，x1+x2+x3=1,目标函数,年投资收益率的方差极小,优化模型,对应的收益:,二次规划模型(QP),与前结果A占53%，B占36%，C占11%比较,略有差异,A占53%，B占38%，C占9%,结果

17、,其他目标下的投资组合模型-例6.9:保守股票投资,市场上只有两只股票A、B可供某个投资者购买,市场只能出现两种可能的情况（1和2）,现要使两种情况下最小的收益最大化（即不管未来发生哪种情况，都能至少获得这个收益），如何建立模型和求解？,优化模型与求解,决策变量,约束条件,目标函数,X1年初投资股票A,X2年初投资股票B,x1,x2 0，x1+x2=1,最小收益最大的“保守”目标实际上就是希望：Max min(1.0 x1+1.2x2,1.5x1+0.7x2),引入一个辅助变量y，这个模型就可以线性化。相应的LINDO模型为：,MAX ySubject tox1+x2=1x1+1.2 x2-y

18、 01.5 x1+0.7 x2-y 0,求解得到：应该投资A、B股票各50%，至少可以增值10%,求解得到：应该投资A股票54.5455%，B 股票45.4545%，至少可以增值13.6364%.,现在，假设有一条重要信息：如果情形1发生，股票B的增值将达到30%而不是表中给出的20%。那么，一般人的想法应该是增加对股票B的持有份额。果真如此吗？这个投资人如果将上面模型中的1.2改为1.3计算,也就是说，应该减少对股票B的持有份额，增加对股票A的持有份额！这真是叫人大吃一惊！这相当于说：有人告诉你有某只股票涨幅要增加了，你赶紧说：那我马上把这只股票再卖点吧。之所以出现如此奇怪的现象，就是由于这

19、个例子中的目标的特殊性引起的,3.市场营销问题,现有新产品A和已有的同类产品B、C、D，市场调查如下表,例6.10：新产品的市场预测问题,新产品A未来的市场份额大概是多少？,问题分析,模型建立,离散动态随机过程,A未来的市场份额,产品编号记为 i（i=1，2，,N）,转移概率矩阵的元素记为Tij,稳定状态下每种产品的概率,优化模型(无目标函数),稳定状态下产品i的市场份额记为pi,pi非负,A的市场份额是47.5%,效用函数-例6.11:小汽车属性的效用函数,考虑某牌号小汽车的两种属性：价格和安全气囊。价格分为12.9、9.9、7.9万元；安全气囊的配置为两个、一个、没有。顾客对该产品的不同配

20、置的偏好程度（效用）如下表所示：,价格和安全气囊的效用函数如何？,模型建立,记价格选项分别为H(高)、M(中)、L(低)，对应的效用为pj（j=H，M，L）；安全气囊选项分别为0、1、2，对应的效用为qi（i=0，1，2）,目的:求出pj 和qi,假设价格和安全气囊的效用是线性可加的，即当价格选项为j、安全气囊选项为i时，效用 c（i，j）=pj+qi,如何比较不同的估计的好坏呢？,用最小二乘法确定pj和qi。也就是说，此时的目标为：,其中，c0(i，j)是表中的数据(安全气囊选项为i、价格选项为j时具体产品的效用),因为做效用分析的主要目的是将来用于把不同配置的具体产品的优劣次序排出来，所以

21、另一种方法是希望c(i，j)和c0(i，j)保持同样的顺序：即对任意的(i，j)和(k，l),当c0(i，j)+1 c0(k，l)时，也尽量有c(i，j)+1 c(k，l)(这里“+1”表示c(i，j)严格小于 c(k，l)，且至少相差1)。,考虑目标,求和只对满足c0(i，j)+1 c0(k，l)的(i，j)和(k，l)求和,此时模型的最优值（误差和）为0，所以说明在这个效用函数下，虽然得到的产品权重（效用）与问题中给出的数据并完全相同，但产品的相对偏好顺序是完全一致的。,航班AH、HB、HC可搭乘旅客的最大数量分别为120、100、110人,机票的销售策略 例6.12：机票分配问题,每条航

22、线上分别分配多少头等舱和经济舱的机票？,问题,目标,使销售收入最大化,5个起终点航线AH、AB、AC、HB、HC，依次编号为i（i=1，2，,5）,模型建立,相应的头等舱需求记为ai，价格记为pi,相应的经济舱需求记为bi，价格记为qi,三个航班AH、HB、HC的顾客容量分别是c1=120，c2=100，c3=110,决策变量,xi（起终点航线i上销售的头等舱机票数）yi（销售的经济舱机票数）,约束,x1+x2+x3+y1+y2+y3 c1 x2+x4+y2+y4 c2 x3+x5+y3+y5 c3,容量限制,需求限制,0 xi ai0 yi bi,线性规划模型(LP),头等舱：33、10、12、44、16经济舱：0、0、65、46、17总销售收入：39344（元）,