基于拆量思想的兩輪逆向拍賣機(jī)制設(shè)計(jì)

王 娜, 汪定偉, 王洪峰, 王曉梅

(1. 沈陽(yáng)師范大學(xué) 計(jì)算機(jī)與數(shù)學(xué)基礎(chǔ)教學(xué)部, 沈陽(yáng) 110034;2. 東北大學(xué) 信息科學(xué)與工程學(xué)院, 沈陽(yáng) 110819)

0 引 言

制造行業(yè)企業(yè)原材料和服務(wù)的采購(gòu)成本占到了總成本的50%～80%[1-4]。而逆向拍賣,尤其是網(wǎng)上逆向拍賣能夠節(jié)約采購(gòu)成本,縮短采購(gòu)周期[5-8]?，F(xiàn)在許多大中型企業(yè)都利用網(wǎng)上逆向拍賣來采購(gòu)所需的原材料或服務(wù)[9-10]。

學(xué)者們對(duì)采購(gòu)問題進(jìn)行了大量的研究。Chen[11]討論了一個(gè)買方和多個(gè)潛在供應(yīng)商的采購(gòu)問題。Li和Scheller-Wolf[12]考慮不確定需求的一個(gè)買方通過在線采購(gòu)拍賣以降價(jià)方式從多個(gè)供應(yīng)商處采購(gòu),比較了唯價(jià)格的推拉式合同拍賣,確定了拍賣設(shè)計(jì)和合同設(shè)計(jì)在采購(gòu)拍賣中的相對(duì)重要性。劉樹人等[13]研究了價(jià)格相依隨機(jī)需求下零售商的逆向拍賣采購(gòu)與定價(jià)聯(lián)合決策問題。

大型企業(yè)集團(tuán)在集中采購(gòu)煤炭、石油和天然氣等物資時(shí),其總采購(gòu)量通常會(huì)遠(yuǎn)遠(yuǎn)超過單個(gè)供應(yīng)商的供應(yīng)能力,這就需要多個(gè)供應(yīng)商同時(shí)獲得供應(yīng)合同,將其稱之為可拆分單物品的采購(gòu)問題。

當(dāng)標(biāo)的物可拆分且單一種類,競(jìng)價(jià)人投標(biāo)時(shí)需要標(biāo)明單位價(jià)格和供應(yīng)量等信息,拍賣人在保證總采購(gòu)量滿足要求的情況下,按照總采購(gòu)成本最小或者采購(gòu)單價(jià)最低的原則確定勝出的競(jìng)價(jià)人。但在實(shí)踐中容易產(chǎn)生如下問題:

1) 供應(yīng)商自由投標(biāo)的供應(yīng)量之和可能會(huì)與預(yù)期采購(gòu)量不匹配,從而造成可行解數(shù)量過少,很難形成有效的競(jìng)爭(zhēng);

2) 投標(biāo)價(jià)格較低的供應(yīng)商可能無法與其他供應(yīng)商構(gòu)成可行解,造成采購(gòu)成本偏高。

上述2種情況都會(huì)影響拍賣人的采購(gòu)效果,帶來不必要的經(jīng)濟(jì)損失。受文獻(xiàn)[14-15]中多輪拍賣思想的啟發(fā),本文提出一種基于拆量思想的兩輪逆向拍賣機(jī)制,其基本思想是:根據(jù)競(jìng)價(jià)人的第一輪標(biāo)書中的投標(biāo)單價(jià)和供應(yīng)量,計(jì)算出競(jìng)價(jià)人在面對(duì)其他供應(yīng)量時(shí)的期望投標(biāo)單價(jià),按照收益最大化原則確定期望投標(biāo)策略,之后以拍賣商期望采購(gòu)成本最小化為目標(biāo)將總采購(gòu)量拆分成若干個(gè)分量;在第二輪投標(biāo)中,拍賣人僅允許競(jìng)價(jià)人對(duì)拆量包投標(biāo),根據(jù)實(shí)際投標(biāo)情況,按照采購(gòu)成本最小化原則確定最終勝標(biāo)的競(jìng)價(jià)人。

通過實(shí)例計(jì)算與分析,表明這種基于拆量思想的兩輪逆向拍賣機(jī)制對(duì)于這類可拆分單物品的集中采購(gòu)問題是有效的。

1 拆量?jī)?yōu)化問題

拆量?jī)?yōu)化問題的目標(biāo)是將總采購(gòu)量拆分成若干個(gè)采購(gòu)方案,即確定每個(gè)方案中的采購(gòu)量,以獲得最優(yōu)的采購(gòu)效益。為了對(duì)總采購(gòu)量進(jìn)行有效拆分,首先對(duì)競(jìng)價(jià)人的投標(biāo)策略進(jìn)行分析。

1.1 競(jìng)價(jià)人投標(biāo)策略

首先給出競(jìng)價(jià)人投標(biāo)策略的基本假設(shè):

1) 競(jìng)價(jià)人都是風(fēng)險(xiǎn)中性的;

2) 競(jìng)價(jià)人供貨的產(chǎn)品差異很小,近似認(rèn)為產(chǎn)品是同質(zhì)的;

3) 競(jìng)價(jià)人僅知道自己的單位成本;

4) 競(jìng)價(jià)人假設(shè)其他競(jìng)價(jià)人的單位成本是在行業(yè)水平的最低成本和最高成本之間均勻分布的獨(dú)立隨機(jī)變量;

5) 競(jìng)價(jià)人的投標(biāo)策略都是相同的;

6) 競(jìng)價(jià)人的投標(biāo)單價(jià)是其單位成本的嚴(yán)格單調(diào)遞增函數(shù);

7) 競(jìng)價(jià)人在自由投標(biāo)情形下總是以最優(yōu)供應(yīng)量作為投標(biāo)的供應(yīng)量;

8) 各個(gè)競(jìng)價(jià)人之間無合謀行為;

9) 不止一個(gè)最低報(bào)價(jià)是小概率事件,可以認(rèn)為不可能發(fā)生。

在上述假設(shè)前提下,分2種不同情形對(duì)競(jìng)價(jià)人投標(biāo)策略進(jìn)行分析。

1.1.1 自由投標(biāo)情形下的競(jìng)價(jià)人投標(biāo)策略

在自由投標(biāo)情況下,競(jìng)價(jià)人不知道拍賣人的具體供應(yīng)量信息,完全根據(jù)自己的供應(yīng)能力進(jìn)行投標(biāo),也即是競(jìng)價(jià)人在第一輪的投標(biāo)過程。

令競(jìng)價(jià)人i∈N(i=1,2,…,n)的單位成本為ci,投標(biāo)單價(jià)為pi。這里假設(shè)競(jìng)價(jià)人i的投標(biāo)單價(jià)pi是單位成本ci的線性遞增函數(shù),表達(dá)如下:

pi=a+e·ci(e>0)

(1)

其中,a和e都是常數(shù)。

于是,在自由投標(biāo)情況下,競(jìng)價(jià)人i報(bào)價(jià)低于其他競(jìng)價(jià)人報(bào)價(jià)的概率為:

(2)

于是,競(jìng)價(jià)人的單位期望收益ui可以計(jì)算如下:

(3)

令

得

(4)

又由式(1)pi=a+e·ci,可得

于是,在自由投標(biāo)情形下競(jìng)價(jià)人i的投標(biāo)策略為:

(5)

競(jìng)價(jià)人i可以根據(jù)其單位成本計(jì)算使其單位收益最大的投標(biāo)單價(jià),進(jìn)而根據(jù)自身的供應(yīng)能力確定最優(yōu)供應(yīng)量qi。

另一方面,一旦拍賣人了解到某一競(jìng)價(jià)人的投標(biāo)單價(jià),也能夠獲得該競(jìng)價(jià)人在供應(yīng)量為qi時(shí)的單位成本ci,即

(6)

1.1.2 給定采購(gòu)量情形下的競(jìng)價(jià)人期望投標(biāo)策略

在非自由投標(biāo)情形下,也就是當(dāng)拍賣人公布一個(gè)采購(gòu)量為g的采購(gòu)方案或者拆量包時(shí),競(jìng)價(jià)人報(bào)價(jià)時(shí)將不得不面對(duì)g不等于其最優(yōu)供應(yīng)量的情況,此時(shí)競(jìng)價(jià)人的單位成本將會(huì)發(fā)生變化。

根據(jù)經(jīng)濟(jì)學(xué)原理,當(dāng)供應(yīng)量為最優(yōu)時(shí),邊際成本為0;當(dāng)供應(yīng)量小于最優(yōu)供應(yīng)量時(shí),邊際成本會(huì)隨著供應(yīng)量的增加而減小;當(dāng)供應(yīng)量大于最優(yōu)供應(yīng)量時(shí),邊際成本會(huì)隨著供應(yīng)量的增加而增大。假設(shè)最優(yōu)供應(yīng)量為q,此時(shí)單位成本為c0,當(dāng)供應(yīng)量為g時(shí),單位成本c可以計(jì)算如下:

(7)

其中,β1和β2為2個(gè)非負(fù)參數(shù)。

參數(shù)β1用來刻畫當(dāng)供應(yīng)量小于最優(yōu)供應(yīng)量時(shí)邊際成本的變化程度。β1的值越大,則表示實(shí)際供應(yīng)量g越低于最優(yōu)供應(yīng)量q時(shí),邊際成本變化越緩慢。當(dāng)β1的值足夠大時(shí),邊際成本幾乎為0。對(duì)于某一競(jìng)價(jià)人來說,當(dāng)拍賣人公布的采購(gòu)方案或者拆量包小于其第一輪投標(biāo)的供應(yīng)量時(shí),由于單位成本增加比較小,其博弈投標(biāo)報(bào)價(jià)的變化也不會(huì)大。反之,β1的值減小,則表示隨著實(shí)際供應(yīng)量的減少,其邊際成本提高越快,從而導(dǎo)致其博弈投標(biāo)報(bào)價(jià)上升越快。一般來說,β1可取1.17。

參數(shù)β2用來刻畫供應(yīng)量大于最優(yōu)供應(yīng)量時(shí)邊際成本的變化程度。β2的值越大,則表示實(shí)際供應(yīng)量g越高于最優(yōu)供應(yīng)量q時(shí),邊際成本變化越緩慢。當(dāng)β2的值足夠大時(shí),邊際成本幾乎為0。對(duì)于某一競(jìng)價(jià)人來說,當(dāng)拍賣人公布的采購(gòu)方案或者拆量包大于其第一輪投標(biāo)的供應(yīng)量時(shí),由于單位成本增加比較小,其博弈投標(biāo)報(bào)價(jià)的變化也不會(huì)大。反之,β2的值減小,則表示隨著實(shí)際供應(yīng)量的增加,其單位成本增加較大,從而導(dǎo)致其博弈投標(biāo)報(bào)價(jià)上升較大。一般來說,β2可取1.0。

設(shè)拍賣人公布一個(gè)給定供應(yīng)量g,根據(jù)上述討論,按以下步驟計(jì)算給定供應(yīng)量下競(jìng)價(jià)人i的期望投標(biāo)策略。

步驟PC:

Step 1 以競(jìng)價(jià)人i第一輪投標(biāo)的供應(yīng)量qi作為最優(yōu)供應(yīng)量,投標(biāo)單價(jià)定義為pi(qi),投標(biāo)單價(jià)與供應(yīng)量之間具有函數(shù)關(guān)系;

Step 2 利用公式(6)計(jì)算出競(jìng)價(jià)人i在自由投標(biāo)階段供應(yīng)量為qi時(shí)的單位成本ci(qi);

Step 3 利用公式(7)計(jì)算出競(jìng)價(jià)人i在給定供應(yīng)量為g時(shí)的單位成本ci(g);

Step 4 利用公式(5)計(jì)算出競(jìng)價(jià)人i對(duì)這一采購(gòu)方案的投標(biāo)單價(jià)pi(g),考慮到競(jìng)價(jià)人的能力和意愿,規(guī)定競(jìng)價(jià)人i對(duì)供應(yīng)量g:|g-q|≤[10%Q]投標(biāo),其中Q為總采購(gòu)量;

Step 5 計(jì)算競(jìng)價(jià)人i的收益:ui(g)=[pi(g)-ci(g)]·g。

如果拍賣人公布m個(gè)給定供應(yīng)量的采購(gòu)方案G={g1,g2,…,gm},規(guī)定競(jìng)價(jià)人i只能對(duì)至多一個(gè)捆綁gk,k=1,2,…,m進(jìn)行投標(biāo),此時(shí)按照以下原則確定競(jìng)價(jià)人i對(duì)G的投標(biāo)策略:

最大收益原則:競(jìng)價(jià)人i選擇ui(G)中最大收益進(jìn)行報(bào)價(jià)。

(8)

需要說明的是,這樣的結(jié)論是拍賣人根據(jù)競(jìng)價(jià)人第一輪投標(biāo)結(jié)果進(jìn)行推導(dǎo)而得,并不是競(jìng)價(jià)人的真實(shí)投標(biāo)行為,故本文將其稱之為競(jìng)價(jià)人的期望投標(biāo)策略。

1.2 拆量?jī)?yōu)化模型

(9)

將拆量?jī)?yōu)化問題描述如下:

拍賣人根據(jù)n個(gè)競(jìng)價(jià)人第一輪投標(biāo)結(jié)果,將總采購(gòu)量Q拆分為m個(gè)采購(gòu)方案G={g1,g2,…,gm},其中g(shù)min≤gi≤gmax(i=1,2,…,m),gmin和gmax分別表示最小供應(yīng)量和最大供應(yīng)量,以獲得最優(yōu)的期望采購(gòu)效益,即實(shí)現(xiàn)期望采購(gòu)成本最小化。

需要說明的是,拆量方案的數(shù)目m將由拍賣人預(yù)先設(shè)定。拍賣人可以根據(jù)企業(yè)的具體情況,來確定m的值,以達(dá)到防止壟斷的目的。

以采購(gòu)效益最優(yōu)為目標(biāo)函數(shù),以拆量方案的每個(gè)供應(yīng)量為決策變量,建立拆量?jī)?yōu)化問題的數(shù)學(xué)模型,具體如下:

(10)

(11)

gmin≤gi≤gmax,i=1,2,…,m

(12)

目標(biāo)函數(shù)(10)表示最小化拍賣人的期望采購(gòu)成本,約束條件(11)表示所有拆量方案的供應(yīng)量之和等于拍賣人的采購(gòu)總量,約束條件(12)表示決策變量gi(i=1,2,…,m)的取值范圍。

上述拆量?jī)?yōu)化模型中,決策變量是一組gi(i=1,2,…,m),約束條件均為線性的,且目標(biāo)函數(shù)需要通過求解組合優(yōu)化問題才能夠計(jì)算出來。因此,上述模型是由線性規(guī)劃與組合優(yōu)化組成的混合優(yōu)化問題,這種優(yōu)化問題顯然無法通過一般的數(shù)學(xué)規(guī)劃方法求解。但遺傳算法等可以方便的進(jìn)行求解,限于篇幅,這里不對(duì)模型(10)—(12)的求解方法展開討論。

2 基于拆量思想的兩輪逆向拍賣機(jī)制設(shè)計(jì)

根據(jù)前面的討論,提出基于拆量思想的兩輪逆向拍賣機(jī)制,具體實(shí)施步驟如下:

Step 1 采購(gòu)方在投標(biāo)網(wǎng)站系統(tǒng)上發(fā)布采購(gòu)信息,包括采購(gòu)物品以及相應(yīng)的最小供應(yīng)量、最高采購(gòu)價(jià)格和最低質(zhì)量參數(shù)要求、供應(yīng)商資質(zhì)要求、采購(gòu)流程具體要求等相關(guān)信息;

Step 2 采購(gòu)方對(duì)所有表示投標(biāo)意愿參加競(jìng)價(jià)的供應(yīng)商進(jìn)行資質(zhì)驗(yàn)證,對(duì)合格的供應(yīng)商發(fā)送加密的驗(yàn)證碼,發(fā)起第一輪投標(biāo);

Step 3 驗(yàn)證合格的供應(yīng)商進(jìn)入投標(biāo)系統(tǒng),上載密封的標(biāo)書,標(biāo)書中需要標(biāo)明物品的供應(yīng)量、單價(jià)以及質(zhì)量參數(shù)信息;

Step 4 采購(gòu)方根據(jù)第一輪投標(biāo)結(jié)果,按照步驟PC和最大收益原則計(jì)算出競(jìng)價(jià)人的期望投標(biāo)策略,并按照模型(10)～(12)求解出最優(yōu)拆量方案;

Step 5 在投標(biāo)系統(tǒng)中公布新的采購(gòu)方案,發(fā)起第二輪投標(biāo),規(guī)定供應(yīng)商只能對(duì)方案中至多一個(gè)分量進(jìn)行投標(biāo);

Step 6 具有驗(yàn)證碼的供應(yīng)商對(duì)新的采購(gòu)方案再次進(jìn)行投標(biāo),上載密封標(biāo)書;

Step 7 采購(gòu)方根據(jù)第二輪投標(biāo)結(jié)果,按照采購(gòu)成本最小化指標(biāo)確定勝出的供應(yīng)商,并與供應(yīng)商簽訂供貨項(xiàng)目協(xié)議。

3 實(shí)例計(jì)算與分析

通過大量數(shù)值實(shí)例,證明了以上基于拆量思想的兩輪逆向拍賣機(jī)制的有效性。為描述方便,這里僅介紹一個(gè)小規(guī)模的例子。

表1 競(jìng)價(jià)人第一輪的投標(biāo)情況Tab.1 The bided data of first turn bidding

假設(shè)拍賣人對(duì)一種物品進(jìn)行招標(biāo),期望的總采購(gòu)量Q為35,采購(gòu)上限為37,每個(gè)競(jìng)價(jià)人的供應(yīng)上限和下限分別為25和10;有10個(gè)符合資質(zhì)要求的競(jìng)價(jià)人參與投標(biāo),競(jìng)價(jià)人標(biāo)書中投標(biāo)單價(jià)和供應(yīng)量如表1。

在傳統(tǒng)單輪逆向拍賣下,為了達(dá)到總采購(gòu)量,可以得到9個(gè)可行解,如:

可行解1:{2,7},采購(gòu)量為:18+19=37>35,采購(gòu)成本為:201.6+209=410.6;

可行解2:{3,9},采購(gòu)量為:15+21=36>35,采購(gòu)成本為:153+205.8=358.8;

可行解3:{5,6},采購(gòu)量為:16+20=36>35,采購(gòu)成本為:168+216=384;

……

注： 表中加粗的數(shù)字表示勝標(biāo)者及其報(bào)價(jià)。

通過枚舉法,最終求得可行解2為最優(yōu)解,即競(jìng)價(jià)人3和競(jìng)價(jià)人9勝出,最后拍賣人的采購(gòu)成本為358.8,采購(gòu)量為36,比總采購(gòu)量多出1個(gè)單位。另外,從投標(biāo)結(jié)果來看,競(jìng)價(jià)人1的投標(biāo)單價(jià)最低,但由于它無法與其他標(biāo)書構(gòu)成可行解,拍賣人不得不放棄。

依據(jù)拆量?jī)?yōu)化模型,最優(yōu)的拆量方案為

G={16,19}

分別由競(jìng)價(jià)人3和競(jìng)價(jià)人7的期望投標(biāo)策略而獲得,對(duì)應(yīng)的期望投標(biāo)單價(jià)分別為10.7467和11。

拍賣人第二輪按這2個(gè)分量重新招標(biāo),采購(gòu)單價(jià)不高于12。第二輪投標(biāo)情況見表2。

從表2可以看出,競(jìng)價(jià)人分別根據(jù)2個(gè)確定采購(gòu)量16和19修改了自己的投標(biāo)方案,組成的可行解數(shù)量由原來的9個(gè)上升為現(xiàn)在的24個(gè)。按照拍賣人采購(gòu)成本最小化原則,很容易得到最優(yōu)解,即勝標(biāo)人為競(jìng)價(jià)人1和9,最優(yōu)采購(gòu)成本為344.9。這個(gè)價(jià)格比單輪逆向拍賣下的最優(yōu)值358.8節(jié)省了3.8%。這個(gè)拆量的結(jié)果讓原來出價(jià)較低的競(jìng)價(jià)人1也得到勝出的機(jī)會(huì),顯然取得了比較好的拍賣效益。

4 結(jié) 語

政府和大型企業(yè)集團(tuán)在集中采購(gòu)煤炭、石油等物資時(shí)通常采用將采購(gòu)量拆分的逆向拍賣方式,但是一方面供應(yīng)商自由投標(biāo)的供應(yīng)量之和可能會(huì)與預(yù)期采購(gòu)量不匹配,從而造成可行解數(shù)量過少;另一方面投標(biāo)價(jià)格較低的供應(yīng)商由于無法與其他供應(yīng)商構(gòu)成可行解,也使得拍賣人不得不放棄。本文提出了一種基于拆量思想的兩輪逆向拍賣機(jī)制。首先根據(jù)競(jìng)價(jià)人第一輪自由投標(biāo)的結(jié)果按照收益最大化原則確定其投標(biāo)策略,并以拍賣人期望采購(gòu)成本最小化為目標(biāo)確定拆量方案,再按拆量方案進(jìn)行第二輪投標(biāo)。這種拍賣機(jī)制使得可行解數(shù)量大大增加,從而激化競(jìng)爭(zhēng),取得更好的拍賣效果。