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

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

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

0 引 言

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

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

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

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

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

2) 投標價格較低的供應商可能無法與其他供應商構成可行解,造成采購成本偏高。

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

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

1 拆量優化問題

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

1.1 競價人投標策略

首先給出競價人投標策略的基本假設:

1) 競價人都是風險中性的;

2) 競價人供貨的產品差異很小,近似認為產品是同質的;

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

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

5) 競價人的投標策略都是相同的;

6) 競價人的投標單價是其單位成本的嚴格單調遞增函數;

7) 競價人在自由投標情形下總是以最優供應量作為投標的供應量;

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

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

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

1.1.1 自由投標情形下的競價人投標策略

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

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

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

(1)

其中,a和e都是常數。

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

(2)

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

(3)

令

得

(4)

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

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

(5)

競價人i可以根據其單位成本計算使其單位收益最大的投標單價,進而根據自身的供應能力確定最優供應量qi。

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

(6)

1.1.2 給定采購量情形下的競價人期望投標策略

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

根據經濟學原理,當供應量為最優時,邊際成本為0;當供應量小于最優供應量時,邊際成本會隨著供應量的增加而減小;當供應量大于最優供應量時,邊際成本會隨著供應量的增加而增大。假設最優供應量為q,此時單位成本為c0,當供應量為g時,單位成本c可以計算如下:

(7)

其中,β1和β2為2個非負參數。

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

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

設拍賣人公布一個給定供應量g,根據上述討論,按以下步驟計算給定供應量下競價人i的期望投標策略。

步驟PC:

Step 1 以競價人i第一輪投標的供應量qi作為最優供應量,投標單價定義為pi(qi),投標單價與供應量之間具有函數關系;

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

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

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

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

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

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

(8)

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

1.2 拆量優化模型

(9)

將拆量優化問題描述如下:

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

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

以采購效益最優為目標函數,以拆量方案的每個供應量為決策變量,建立拆量優化問題的數學模型,具體如下:

(10)

(11)

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

(12)

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

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

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

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

Step 1 采購方在投標網站系統上發布采購信息,包括采購物品以及相應的最小供應量、最高采購價格和最低質量參數要求、供應商資質要求、采購流程具體要求等相關信息;

Step 2 采購方對所有表示投標意愿參加競價的供應商進行資質驗證,對合格的供應商發送加密的驗證碼,發起第一輪投標;

Step 3 驗證合格的供應商進入投標系統,上載密封的標書,標書中需要標明物品的供應量、單價以及質量參數信息;

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

Step 5 在投標系統中公布新的采購方案,發起第二輪投標,規定供應商只能對方案中至多一個分量進行投標;

Step 6 具有驗證碼的供應商對新的采購方案再次進行投標,上載密封標書;

Step 7 采購方根據第二輪投標結果,按照采購成本最小化指標確定勝出的供應商,并與供應商簽訂供貨項目協議。

3 實例計算與分析

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

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

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

在傳統單輪逆向拍賣下,為了達到總采購量,可以得到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;

……

注： 表中加粗的數字表示勝標者及其報價。

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

依據拆量優化模型,最優的拆量方案為

G={16,19}

分別由競價人3和競價人7的期望投標策略而獲得,對應的期望投標單價分別為10.7467和11。

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

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

4 結 語

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