建立线性规划模型.ppt

《建立线性规划模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、拍卖与投标问题-例6.3:艺术品拍卖问题招标项目类型12345招标项目的数量12334投标价格投标人192863投标人267915投标人378634投标人454321假设每个投标人对每类艺术品最多只能购买1件每个投标人购买的艺术品的总数不能超过3件问哪些艺术品能够卖出去？卖给谁？每类物品的清算价应该是多少？假设有一个中间商希望最大化自己的例润问题分析与假设设有N类物品需要拍卖，第j类物品的数量为Sj（j=1,2，…,N）；有M个投标者，投标者i（i=1，2，…,M）对第j类物品的投标价格为bij（假设非负）。投标者i对每类物品最多购买一件，且总件数不能超过ci。实际中可以通过对所

2、有投标的报价进行排序来解决目标：确定第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表示分配，而xi

3、j=0表示不分配。目标函数虚拟的中间商的总利润最大,即约束条件(1)每类物品的数量限制(2)每个投标人所能分到的物品的数量限制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);

4、ENDDATAMAX=@SUM(LINK:B*X);!目标函数;@FOR(AUCTION(J):!拍卖数量限制[AUC_LIM]@SUM(BIDDER(I):X(I,J))

5、类艺术品的数量限制的，对应的影子价格就是其清算价格：即5类艺术品的清算价格分别是5、5、3、0、0。第4、5类艺术品有剩余，所以清算价格为0推广:大学生的选课问题交通流均衡问题－例6.4:公路网汽车分布居民区工作区BCDA每天上班时间有6千辆小汽车要从居民区A前往工作区D道路ABACBCBDCD行驶时间（分钟）流量≤220521252202<流量≤330531353303<流量≤440541454405条道路上每辆汽车的平均行驶时间和汽车流量之间的关系见下表这些汽车将如何在每条道路上分布？问题分析交通流的规律:每辆汽车都将选择使自己从A到D运行时间最少的路线必然的结果:无论走哪条

6、路线从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)表示流量

7、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,