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

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

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

0 引 言

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

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

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

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

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

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

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

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

1 拆量優(yōu)化問題

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

1.1 競價人投標(biāo)策略

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

1) 競價人都是風(fēng)險中性的;

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

3) 競價人僅知道自己的單位成本;

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

5) 競價人的投標(biāo)策略都是相同的;

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

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

8) 各個競價人之間無合謀行為;

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

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

1.1.1 自由投標(biāo)情形下的競價人投標(biāo)策略

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

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

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

(1)

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

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

(2)

于是,競價人的單位期望收益ui可以計算如下:

(3)

令

得

(4)

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

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

(5)

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

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

(6)

1.1.2 給定采購量情形下的競價人期望投標(biāo)策略

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

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

(7)

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

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

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

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

步驟PC:

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

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

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

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

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

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

最大收益原則:競價人i選擇ui(G)中最大收益進行報價。

(8)

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

1.2 拆量優(yōu)化模型

(9)

將拆量優(yōu)化問題描述如下:

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

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

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

(10)

(11)

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

(12)

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

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

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

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

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

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

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

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

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

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

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

3 實例計算與分析

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

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

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

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

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

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

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

……

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

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

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

G={16,19}

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

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

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

4 結(jié) 語

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