经济均衡问题及其应用 (二)：拍卖与投标问题
例3 假设一家拍卖行对委托的5类艺术品对外拍卖，采用在规定日期前投标人提 交投标书的方式进行，最后收到了来自4个投标人的投标书。每类项目的数量、投标人 对每个项目的投标价格如表3中所示。例如，有3件第4类艺术品；对每件第4类艺术品， 投标人1，2，3愿意出的最高价分别为6，1，3，2（货币单位，如万元）。此外，假设每个投标人对每类艺术品多只能购买1件，并且每个投标人购买的艺术品的总数不 能超过3件。那么，哪些艺术品能够卖出去？卖给谁？这个拍卖和投标问题中每类物品 的清算价应该是多少？https://img-blog.csdnimg.cn/20190419165033846.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70
（1）问题分析
这个具体问题在实际中可能可以通过对所有投标的报价进行排序来解决，例如可以 总是将艺术品优先卖给出价高的投标人。但这种方法不太好确定每类艺术品的清算价，所以我们这里还是借用前面两个例子中的方法，即假设有一个中间商希望大化自 己的利润，从而建立这个问题的线性规划模型。
（2）问题的一般提法和假设
先建立一般的模型，然后求解本例的具体问题，设有n类物品需要拍卖，第 j 类物品的数量为 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20s_%7Bj%7D（ j=1,2,...,n ）；有m 个投标者，投标者i（ i=1,2,...,m ）对第 j 类物品的投标价格为 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20b_%7Bij%7D （假设非负）。投标者i对每类物品多购买一件，且总件数不能超过 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20c_%7Bi%7D 。我们的目标之一是要确定第 j 类物品的清算价格 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20p_%7Bj%7D，它应当满足下列假设条件：
i）成交的第 j 类物品的数量不超过 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20s_%7Bj%7D（ j=1,2,...,n ）；
ii）对第 j 类物品的报价低于 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20p_%7Bj%7D 的投标人将不能获得第 j 类物品；
iii）如果成交的第 j 类物品的数量少于https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20s_%7Bj%7D （ j=1,2,...,n ）,可以认为 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20p_%7Bj%7D%3D0 （除非拍卖方另外指定一个低的保护价）；
iv）对第 j 类物品的报价高于 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20p_%7Bj%7D 的投标人有权获得第 j 类物品，但如果他有权获得的物品超过3件，那么我们假设他总是希望使自己的满意度大（满意度可以用他的 报价与市场清算价之差来衡量）。
（3）优化模型
用 0−1 变量 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20x_%7Bij%7D 表示是否分配一件第 j 类物品给投标者i，即 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20x_%7Bij%7D%3D1 表示分配，而 https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20x_%7Bij%7D%3D0表示不分配。目标函数仍然是虚拟的中间商的总利润（认为这些利润全部是拍卖行的利润也可以），即
https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20%5Csum_%7Bi%3D1%7D%5E%7Bm%7D%5Csum_%7Bj%3D1%7D%5E%7Bn%7Db_%7Bij%7Dx_%7Bij%7D （1）
除变量取值为0或1的约束外，问题的约束条件主要是两类：每类物品的数量限制 和每个投标人所能分到的物品的数量限制，即
https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20%5Csum_%7Bi%3D1%7D%5E%7Bm%7Dx_%7Bij%7D%20%5Cleqslant%20s_%7Bj%7D%5C%3A%20%2Cj%3D1%2C2%2C..%2Cn （2）
https://private.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Ctiny%20%5Csum_%7Bj%3D1%7D%5E%7Bn%7Dx_%7Bij%7D%5Cleqslant%20c_%7Bi%7D%5C%2C%20%2Ci%3D1%2C2%2C..%2Cm (3)
模型就是在约束（2）、（3）下最大化目标函数（1）。
（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):
@SUM(BIDDER(I): X(I,J)) < S(J) );
@FOR(BIDDER(I):
@SUM(AUCTION(J): X(I,J)) < C(I) );
@FOR(LINK: @BND(0,X,1));
END
（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，这是符合前面的假设 的。
可以指出的是：即使上面模型中不要求 为 0−1 变量（即只要求取0～1之间的实数），由于这个问题的特殊性，优解中 也会要么取0，要么取1，不可能取0～1之间的其它数，所以可以将LINGO模型中“@BIN(X)”改为“@BND(0,X,1)”，这个线 性规划的结果将与 0−1 整数线性规划得到的结果相同。
最后，大学生的选课问题与此是类似的，即把课程看成招标（拍卖）项目，而把学生愿意付出的选课费看成投标。据说国外有些大学的选课系统就是使用这个模型确定每 门课程的清算价格（选课费用）的，而且取得了成功。
————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89403559
页:
[1]