陳修素， 陳 睿

( 1.重慶工商大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶400067; 2.重慶工商大學(xué) 信息化辦公室,重慶 400067)

基于固定費(fèi)用問(wèn)題的整數(shù)規(guī)劃模型注記*

陳修素1， 陳 睿2＊＊

( 1.重慶工商大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶400067; 2.重慶工商大學(xué) 信息化辦公室,重慶 400067)

分析了運(yùn)籌學(xué)經(jīng)典教材中整數(shù)規(guī)劃內(nèi)容里面關(guān)于引入0-1變量的實(shí)際問(wèn)題中的一個(gè)經(jīng)典的例子——關(guān)于固定費(fèi)用的問(wèn)題(Fixed cost Problem)，其建模過(guò)程中的一個(gè)有待商榷的問(wèn)題，給出了兩種情形的解決方案；并指出了其他部分運(yùn)籌學(xué)教材中的相關(guān)問(wèn)題及其解決思路。

固定費(fèi)用; 整數(shù)規(guī)劃; 0-1變量；數(shù)學(xué)模型

由李德和錢(qián)頌迪主編的清華大學(xué)出版社出版的運(yùn)籌學(xué)[1]自1982年出版以來(lái)，深受工科院校從事運(yùn)籌學(xué)教學(xué)的老師和學(xué)習(xí)運(yùn)籌學(xué)的學(xué)生們的歡迎和推崇，1990年修訂版[2]被國(guó)家教委管理工程類專業(yè)教材委員會(huì)推薦為經(jīng)濟(jì)管理類通用教材。經(jīng)過(guò)多年教學(xué)過(guò)程中的吸收、總結(jié)和修改。多次再版[1-4]和多次印刷，印數(shù)近百萬(wàn)冊(cè)，其出版對(duì)我國(guó)運(yùn)籌學(xué)教學(xué)、管理類專業(yè)人才的培養(yǎng)以及促進(jìn)運(yùn)籌學(xué)的研究都有著重要的意義。

在上述運(yùn)籌學(xué)教材的多個(gè)版本中都有整數(shù)規(guī)劃中的0-1型整數(shù)規(guī)劃作為一節(jié)的內(nèi)容，在其中首先介紹的是“引入0-1變量的實(shí)際問(wèn)題”，這里面第3個(gè)例子是“關(guān)于固定費(fèi)用的問(wèn)題(Fixed cost Problem)” ?，F(xiàn)回憶第一版的運(yùn)籌學(xué)[1]中的該例子的內(nèi)容如下：

在討論線性規(guī)劃時(shí)，有些問(wèn)題是要求使成本為最?。菚r(shí)總設(shè)固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出，但有些固定費(fèi)用(固定成本)的問(wèn)題不能用一般線性規(guī)劃來(lái)描述，但可改變?yōu)榛旌险麛?shù)規(guī)劃來(lái)解決，如例1所示。

例1[1]某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)方式投資高 (選購(gòu)自動(dòng)化程度高的設(shè)備)，由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動(dòng)成本就降低；反之，如選定的生產(chǎn)方式投資低，將來(lái)分配到每件產(chǎn)品的變動(dòng)成本可能增加，所以必須全面考慮。今設(shè)有3種方式可供選擇，令xj表示采用第j種方式時(shí)的產(chǎn)量；cj表示采用第j種方式時(shí)每件產(chǎn)品的變動(dòng)成本；kj表示采用第j種方式時(shí)的固定成本。

為了說(shuō)明成本的特點(diǎn)，暫不考慮其他約束條件。采用各種生產(chǎn)方式的總成本分別為

在構(gòu)成目標(biāo)函數(shù)時(shí)，為了統(tǒng)一在一個(gè)問(wèn)題中討論，現(xiàn)引入0-l變量yj，令

(1)

于是目標(biāo)函數(shù)：

minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)

式(1)這個(gè)規(guī)定可由下述3個(gè)線性約束條件表示：

(2)

式(2)中，M是個(gè)充分大的常數(shù)，式(2)說(shuō)明，當(dāng)xj>0時(shí)，yj必須為1；當(dāng)xj=0時(shí)，只有yj為0才有意義，所以式(2)可以完全代替式(1)。

注記1：在該運(yùn)籌學(xué)教材的多個(gè)不同的版本中，該例子的介紹除了部分文字和式子的編號(hào)略有改動(dòng)外，其余均無(wú)變動(dòng)。但在上述問(wèn)題中式(2)是不能完全代替式(1)的，因?yàn)橛墒?2)可知，當(dāng)xj=0時(shí)，yj可以為0，也可以為1。因此式(2)不能完全刻畫(huà)式(1)規(guī)定的要求。為此分情況給出上述問(wèn)題如下的兩種解決方案。

情形1：如果產(chǎn)品的計(jì)件單位是整數(shù)，即每種生產(chǎn)方式的產(chǎn)品的產(chǎn)量均是整數(shù)，此時(shí)的模型可以改進(jìn)如下：

即用

yj≤xj≤yjMj=1,2,3

(3)

代替式(1)，因?yàn)橛墒?3)的右端不等式可知，當(dāng)xj>0時(shí)，yj≠0，從而yj必須為1，且由于xj取值為整數(shù)，此時(shí)式(3)左端自然成立。當(dāng)xj=0時(shí)，滿足式(3)的yj只能為0，由此分析可見(jiàn)，式(3)完全替代了式(1)的要求。

情形2：如果產(chǎn)品的計(jì)件單位不是整數(shù)，即每種生產(chǎn)方式的產(chǎn)品的產(chǎn)量是非負(fù)實(shí)數(shù)，此時(shí)的模型可以改進(jìn)如下：

其中yj=sgn(xj)表示符號(hào)函數(shù)。

徐永仁在其編寫(xiě)的《經(jīng)濟(jì)管理運(yùn)籌學(xué)》[5]的4.2節(jié)“0-1規(guī)劃問(wèn)題與隱枚舉法”中的第一部分“0-1規(guī)劃問(wèn)題”的第4個(gè)例子(詳見(jiàn)參考文獻(xiàn)[5]中的第92頁(yè))介紹了通過(guò)引入0-1變量y及其中的約束條件式(4)—式(7)來(lái)表示帶有分段性質(zhì)的如下目標(biāo)函數(shù)：

把分段形式的目標(biāo)函數(shù)表示如下帶約束條件的線性函數(shù)：

F(x)=ky+cx

(4)

(5)

(6)

(7)

其中M為一個(gè)充分大的數(shù)。

因此，利用式(4)—式(7)是不能表示出例4的分段性質(zhì)的目標(biāo)函數(shù)的，可以利用前面介紹的方法，分如下兩種情形作處理。

當(dāng)x取值非負(fù)整數(shù)時(shí)，其分段形式的目標(biāo)函數(shù)可表示成如下帶約束條件的線性函數(shù)：

F(x)=ky+cx

(8)

(12)

(13)

當(dāng)x取值非負(fù)實(shí)數(shù)時(shí)，其分段形式的目標(biāo)函數(shù)可表示為帶約束條件的如下線性函數(shù)：

F(x)=ky+cx

(11)

(12)

(13)

西南交通大學(xué)的省級(jí)精品課程運(yùn)籌學(xué)中的”運(yùn)籌學(xué)A課件”里的整數(shù)規(guī)劃中的第四節(jié) 0-1 規(guī)劃里面的模型實(shí)例中的第3例 “固定費(fèi)用問(wèn)題”涉及利用3種資源生產(chǎn)3種產(chǎn)品，由于不同產(chǎn)品的生產(chǎn)組織方式不同，生產(chǎn)相應(yīng)產(chǎn)品的固定費(fèi)用互不相同，問(wèn)題是要制定一個(gè)使總的凈收益最大的生產(chǎn)計(jì)劃，利用3個(gè)0-1變量yj(j=1,2,3),建立了含有3種資源約束的、以總的凈收益最大的整數(shù)規(guī)劃模型：

maxz=4x1+5x2+6x3-100y1-150y2-200y3

注記3：上述模型中的后面四行約束與第一個(gè)案例一樣，可以由xj>0導(dǎo)出yj=1，但不能由xj=0導(dǎo)出yj=0，因此上述建模未能解決原問(wèn)題。如果利用前面情形(1)的解決方法可得該問(wèn)題如下的線性規(guī)劃整數(shù)模型：

maxz=4x1+5x2+6x3-100y1-150y2-200y3

[1] 《運(yùn)籌學(xué)》試用教材編寫(xiě)組.運(yùn)籌學(xué)[M].12th edt.北京：清華大學(xué)出版社,1982

Trial Teaching Material Drawing Board of Operations Research. Operations Research[M]. Beijing: Tsinghua University Press,1982

[2] 《運(yùn)籌學(xué)》教材編寫(xiě)組：運(yùn)籌學(xué)(修訂版)[M].2版,北京：清華大學(xué)出版社,1990

Teaching Material Drawing Board of Operations Research. Operational Research (Revised Edition)[M].2nd edt, Beijing: Tsinghua University Press, January 1990

[3] 《運(yùn)籌學(xué)》教材編寫(xiě)組.運(yùn)籌學(xué)[M].3版. 北京：清華大學(xué)出版社,2005

Teaching Material Drawing Board of Operations Research, Operational Research[M]. 3rd edt. Beijing: Tsinghua University Press,2005

[4] 《運(yùn)籌學(xué)》教材編寫(xiě)組. 運(yùn)籌學(xué)(本科班)[M]. 4版. 北京：清華大學(xué)出版社,2005

Teaching Material Drawing Board of Operations Research. Operational Research (Undergraduate Class)[M]. 4th edt, Beijing: Tsinghua University Press, 2005

[5] 徐永仁. 經(jīng)濟(jì)管理運(yùn)籌學(xué)[M]. 哈爾濱：哈爾濱工業(yè)大學(xué)出版社,1996

XU Y R. Operations Research in Economic Management[M]. Harbin: Harbin Industrial University Press, 1996

Notes about Integer Programming Model for Fixed Cost Problems

CHENXiu-su1,CHENRui2

(1. School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067, China; 2. Information Office, Chongqing Technology and Business University, Chongqing 400067, China)

This paper analyzes the introduction of a classic example in practical problem of 0-1 variables in the integer programming content in the classic textbook of operational research, proposes that fixed cost problem is worth being discussed in the process of modeling, gives the solutions for two kinds of situation and points out the related problems and their solutions in other textbooks of operational research.

fixed cost; integer programming; 0-1 variables; mathematical model

O317

A

2017-05-17；

2017-06-25.

國(guó)家自然科學(xué)基金(11401058) ; 重慶市教委項(xiàng)目(YIG123112，103146，KJ090732)．

陳修素( 1964-) ，男，四川大竹縣人，教授，碩士，從事運(yùn)籌與管理研究.

**

陳睿( 1989-) ，男，重慶市人，碩士，從事信息化與建模研究.

責(zé)任編輯：代小紅