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

陳修素， 陳 睿

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

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

陳修素1， 陳 睿2＊＊

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

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

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

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

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

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

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

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

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

(1)

于是目標函數(shù)：

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

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

(2)

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

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

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

即用

yj≤xj≤yjMj=1,2,3

(3)

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

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

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

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

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

F(x)=ky+cx

(4)

(5)

(6)

(7)

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

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

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

F(x)=ky+cx

(8)

(12)

(13)

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

F(x)=ky+cx

(11)

(12)

(13)

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

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

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

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

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

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

[2] 《運籌學(xué)》教材編寫組：運籌學(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] 《運籌學(xué)》教材編寫組.運籌學(xué)[M].3版. 北京：清華大學(xué)出版社,2005

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

[4] 《運籌學(xué)》教材編寫組. 運籌學(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)濟管理運籌學(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.

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

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

**

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

責任編輯：代小紅