0-1整數(shù)規(guī)劃的算法及其應(yīng)用

1、五邑大學(xué)本科畢業(yè)論文摘 要0-1整數(shù)規(guī)劃在整數(shù)規(guī)劃中占有重要地位。許多實(shí)際問(wèn)題，例如指派問(wèn)題、選地問(wèn)題、送貨問(wèn)題都可歸結(jié)為0-1整數(shù)規(guī)劃問(wèn)題。正是由于0-1整數(shù)規(guī)劃具有深刻的背景和廣泛的應(yīng)用，所以研究0-1整數(shù)規(guī)劃的算法是十分必要且具有重要意義。本文主要研究0-1整數(shù)規(guī)劃的幾種算法及其應(yīng)用。首先介紹0-1整數(shù)規(guī)劃的相關(guān)概念、特點(diǎn)及其作用，通過(guò)實(shí)際問(wèn)題建立0-1整數(shù)規(guī)劃的數(shù)學(xué)模型。然后分別對(duì)窮舉法，隱枚舉法（過(guò)濾隱枚舉法、分枝定界法和分枝隱枚舉法），組合直接搜尋法等幾種算法進(jìn)行介紹，并以具體的計(jì)算實(shí)例對(duì)上述算法加以運(yùn)用，最后闡明了各種算法的優(yōu)缺點(diǎn)。關(guān)鍵詞 整數(shù)規(guī)劃；0-1整數(shù)規(guī)劃；枚舉法；組合直

2、接搜尋法Abstract0-1 integer linear programming plays an important role in integer programming. In many practical problems, such as assignment problem, site selection problem and deliver goods problem, they are all boiled down to 0-1 integer linear programming problem. And just because of the 0-1 integer

3、 linear programming has profound background and widely used, it is very necessary and important practical sense to study its algorithm. In this paper, we mainly study the algorithms for 0-1 integer linear programming and its applications. Firstly, we introduce the related concepts, features and func

4、tions, and set up the mathematical model based on the practical problems in the paper. Secondly, we study three algorithms about method of exhaustion, implicit enumeration method (which includes filter implicit enumeration, branch and bound method and branch-implied enumeration) and the method of co

5、mbination and direction-finding. And then, we apply the algorithms to work out the practical examples of calculation. At last, we compare and expound the advantages and disadvantages of every algorithm in this paper. Key words integer programming；0-1 integer linear programming；enumeration method；the

6、 method of combination and direction-finding目 錄摘 要ABSTRACT第1章 緒論11.1 研究背景及意義11.2 國(guó)內(nèi)外研究方法綜述11.3 本文主要研究?jī)?nèi)容2第2章 0-1整數(shù)規(guī)劃的數(shù)學(xué)模型32.1 0-1整數(shù)規(guī)劃的特點(diǎn)及作用32.2 0-1變量的定義52.3 0-1整數(shù)規(guī)劃的應(yīng)用舉例52.4 本章小結(jié)9第3章 窮舉法103.1 窮舉法的介紹103.2 窮舉法的計(jì)算實(shí)例103.3 對(duì)窮舉法的評(píng)價(jià)113.4 本章小結(jié)11第4章 隱枚舉法124.1 過(guò)濾隱枚舉法124.1.1 過(guò)濾隱枚舉法的介紹124.1.2 過(guò)濾隱枚舉法的計(jì)算實(shí)例124.1.3

7、對(duì)過(guò)濾隱枚舉法的評(píng)價(jià)144.2 分枝定界法144.2.1 分枝定界法的介紹144.2.2 分枝定界法的計(jì)算實(shí)例164.2.3 對(duì)分枝定界法的評(píng)價(jià)174.3 分枝隱枚舉法174.3.1 分枝隱枚舉法的介紹174.3.2 分枝隱枚舉法的計(jì)算實(shí)例18 4.3.3 對(duì)分枝隱枚舉法的評(píng)價(jià)194.4 本章小結(jié)20第5章 組合直接搜尋法215.1 組合直接搜尋法的介紹215.2 組合直接搜尋法的計(jì)算實(shí)例245.3 對(duì)組合直接搜尋法的評(píng)價(jià)255.4 本章小結(jié)25結(jié) 論26參考文獻(xiàn)27致 謝2829第1章 緒論1.1 研究背景及意義在線性規(guī)劃問(wèn)題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對(duì)于某些具體問(wèn)題，通常要求某些變

8、量的解必須是整數(shù)。例如，當(dāng)變量代表的是機(jī)器的臺(tái)數(shù)，工作的人數(shù)或裝貨的車數(shù)等。變量全部或部分取整數(shù)的線性規(guī)劃統(tǒng)稱為整數(shù)線性規(guī)劃（Integer Programming，簡(jiǎn)記為IP）。其中變量全部取整數(shù)的線性規(guī)劃稱為純整數(shù)線性規(guī)劃。只要求一部分變量取整數(shù)的稱為混合整數(shù)線性規(guī)劃。除所有決策變量要求取非負(fù)整數(shù)外，系數(shù)技術(shù)數(shù)據(jù)、價(jià)值數(shù)據(jù)、資源數(shù)據(jù)和約束條件右端的常數(shù)項(xiàng)也要求取整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量也必須是整數(shù)）的線性規(guī)劃稱為全整數(shù)規(guī)劃。在純整數(shù)規(guī)劃問(wèn)題中有一類重要的問(wèn)題，變量只能取0或1，稱為0-1整數(shù)規(guī)劃。0-1整數(shù)規(guī)劃具有廣泛的應(yīng)用背景。比如經(jīng)濟(jì)管理中的實(shí)際問(wèn)題的解必須滿足邏輯條件和順序

9、要求等一些特殊的約束條件，此時(shí)，往往需要引進(jìn)邏輯變量（又稱0-1變量），以達(dá)到表示“是”（用1表示）與“非”（用0表示）。而0-1變量又是整數(shù)變量應(yīng)用中最活躍的部分，它可以數(shù)量化地描述諸如開(kāi)與關(guān)、取與棄、有與無(wú)等現(xiàn)象所反映的離散變量間的邏輯關(guān)系和順序關(guān)系。借助0-1變量還可以使很多含“非此即彼”的、相互排斥的決策變量和約束條件放在一個(gè)模型中統(tǒng)一研究，幫助回答管理中出現(xiàn)的“是”與“否”等二元決策問(wèn)題。此外，線路設(shè)計(jì)、工廠選址、生產(chǎn)計(jì)劃安排、旅行購(gòu)物、背包問(wèn)題、人員安排、代碼選取、可靠性等人們所關(guān)心的諸多問(wèn)題都可化為0-1整數(shù)規(guī)劃來(lái)求解。正是由于0-1整數(shù)規(guī)劃具有深刻的背景和廣泛的應(yīng)用，所以研究0

10、-1整數(shù)規(guī)劃的算法是十分必要而且具有重要意義。1.2 國(guó)內(nèi)外研究方法綜述 整數(shù)規(guī)劃是從1958年由R.E.戈莫里提出割平面法之后形成獨(dú)立分支的，30多年來(lái)發(fā)展出很多方法解決各種問(wèn)題。解整數(shù)規(guī)劃最典型的做法是逐步生成一個(gè)相關(guān)的問(wèn)題，稱它是原問(wèn)題的衍生問(wèn)題。對(duì)每個(gè)衍生問(wèn)題又伴隨一個(gè)比它更易于求解的松弛問(wèn)題（衍生問(wèn)題稱為松弛問(wèn)題的原問(wèn)題）。通過(guò)松弛問(wèn)題的解來(lái)確定它的原問(wèn)題的歸宿，即原問(wèn)題應(yīng)被舍棄，還是再生成一個(gè)或多個(gè)它本身的衍生問(wèn)題來(lái)替代它。隨即，再選擇一個(gè)尚未被舍棄的或替代的原問(wèn)題的衍生問(wèn)題，重復(fù)以上步驟直至不再剩有未解決的衍生問(wèn)題為止。0-1整數(shù)規(guī)劃在整數(shù)規(guī)劃中占有重要地位，一方面因?yàn)樵S多實(shí)際問(wèn)

11、題，例如指派問(wèn)題、選地問(wèn)題、送貨問(wèn)題都可歸結(jié)為此類規(guī)劃，另一方面任何有界變量的整數(shù)規(guī)劃都與0-1整數(shù)規(guī)劃等價(jià)，用0-1規(guī)劃方法還可以把多種非線性規(guī)劃問(wèn)題表示成整數(shù)規(guī)劃問(wèn)題，所以不少人致力于這個(gè)方向的研究。求解0-1整數(shù)規(guī)劃的常用方法是分枝定界法。對(duì)各種特殊問(wèn)題還有一些特殊方法，例如求解指派問(wèn)題用匈牙利方法就比較方便。隨著0-1整數(shù)規(guī)劃的廣泛應(yīng)用，為更有效地解決各領(lǐng)域?qū)嶋H問(wèn)題，國(guó)內(nèi)外學(xué)者提出不同的求解0-1整數(shù)規(guī)劃問(wèn)題的算法。如：在Kenney和Eberhart的二進(jìn)制粒子群算法（BPSO）的基礎(chǔ)上提出一種改進(jìn)的二進(jìn)制粒子群算法（IBPSO），在背包問(wèn)題上的計(jì)算結(jié)果表明，與遺傳算法相比，IBPS

12、O具有更快的收斂速度1-2；對(duì)于求解靶場(chǎng)效能優(yōu)化這類復(fù)雜的0-1整數(shù)規(guī)劃問(wèn)題，提出的混沌搜索算法能找到全局最優(yōu)解，并使得它優(yōu)于傳統(tǒng)的優(yōu)化算法3；基于三螺旋結(jié)構(gòu)的DNA鏈的獨(dú)特結(jié)構(gòu)，殷志祥首次將DNA計(jì)算應(yīng)用到0-1規(guī)劃問(wèn)題的求解中，提出了生物算法4；其他算法參看文獻(xiàn)5-8。目前，用于求解0-1整數(shù)規(guī)劃的幾種通用方法為窮舉法、隱枚舉法、組合直接搜尋法。1.3 本文主要研究?jī)?nèi)容0-1整數(shù)規(guī)劃在整數(shù)規(guī)劃中占有重要地位，許多實(shí)際問(wèn)題都可歸結(jié)為0-1整數(shù)規(guī)劃進(jìn)行研究。所以對(duì)其進(jìn)行算法研究具有重要意義。本文主要內(nèi)容如下：（1）介紹0-1整數(shù)規(guī)劃的研究背景及意義，以及目前國(guó)內(nèi)外關(guān)于0-1整數(shù)規(guī)劃的算法，介紹

13、本文的主要研究?jī)?nèi)容。（2）介紹0-1整數(shù)規(guī)劃的相關(guān)概念、特點(diǎn)及其作用。通過(guò)實(shí)例介紹0-1整數(shù)規(guī)劃在選址問(wèn)題、投資問(wèn)題、生產(chǎn)計(jì)劃問(wèn)題、生產(chǎn)決策問(wèn)題中的應(yīng)用，說(shuō)明了0-1整數(shù)規(guī)劃模型在實(shí)際問(wèn)題中應(yīng)用非常廣泛。（3）研究求解0-1整數(shù)規(guī)劃的窮舉法、隱枚舉法（過(guò)濾隱枚舉法、分枝定界法、分枝隱枚舉法）、組合直接搜尋法，對(duì)每種算法進(jìn)行了實(shí)證分析，最后對(duì)不同的算法進(jìn)行了評(píng)價(jià)。第2章 0-1整數(shù)規(guī)劃的數(shù)學(xué)模型2.1 0-1整數(shù)規(guī)劃的特點(diǎn)及作用在整數(shù)規(guī)劃中有一類特殊的情形，比如有些經(jīng)濟(jì)管理中的實(shí)際問(wèn)題的解必須滿足邏輯條件和順序要求等一些特殊的約束條件，此時(shí)，往往需要引進(jìn)邏輯變量（又稱0-1變量），以達(dá)到表示“是

14、”（用1表示）與“非”（用0表示）。我們稱決策變量均為0-1變量的整數(shù)規(guī)劃為0-1規(guī)劃。0-1變量是整數(shù)變量應(yīng)用中最活躍的部分，它可以數(shù)量化地描述諸如開(kāi)與關(guān)、取與棄、有與無(wú)等現(xiàn)象所反映的離散變量間的邏輯關(guān)系和順序關(guān)系；此外，借助0-1變量還可以使很多含“非此即彼”的、相互排斥的決策變量和約束條件放在一個(gè)模型中統(tǒng)一研究，幫助回答管理中出現(xiàn)的“是”與“否”等二元決策問(wèn)題。0-1整數(shù)規(guī)劃的模型對(duì)研究管理問(wèn)題有重要意義。很多管理問(wèn)題無(wú)法歸結(jié)為線性規(guī)劃的數(shù)學(xué)模型，但卻可以通過(guò)設(shè)置0-1變量建立起0-1整數(shù)規(guī)劃的數(shù)學(xué)模型。下面說(shuō)明0-1變量在建立數(shù)學(xué)模型中的作用。1.個(gè)約束條件中只有個(gè)起作用設(shè)個(gè)約束條件可

15、表為：定義又為任意大的正數(shù)，則表明（2.1）的個(gè)約束條件中有個(gè)的右端項(xiàng)為，不起約束作用，因而只有個(gè)約束條件真正起到約束作用。2.約束條件的右端項(xiàng)可能是個(gè)值中的某一個(gè)，即定義由此，上述約束條件（2.2）可表示為：3.兩組條件中滿足其中一組若；否則（即時(shí)），。定義又為任意大的正數(shù)，則問(wèn)題可表達(dá)為：4.用以表示含固定費(fèi)用的函數(shù)例如用代表產(chǎn)品的生產(chǎn)數(shù)量，其生產(chǎn)費(fèi)用函數(shù)通?？杀硎緸椋菏街惺峭a(chǎn)量無(wú)關(guān)的生產(chǎn)準(zhǔn)備費(fèi)用。問(wèn)題的目標(biāo)是使所有產(chǎn)品的總生產(chǎn)費(fèi)用為最小。即為表達(dá)（2.3）、（2.4）兩式，需設(shè)置一個(gè)0-1變量，當(dāng)；當(dāng)。為此引進(jìn)一個(gè)特殊的約束條件：在式（2.5）中顯然當(dāng)，若將（2.4）、（2.5）式表達(dá)

16、為：則由（2.6）看出當(dāng)為使極小化，應(yīng)有。2.2 0-1變量的定義在整數(shù)規(guī)劃中有一類特殊的情形，它的變量只能取0或l，這時(shí)的稱為0-l變量，或邏輯變量（Logical Variable），又叫二進(jìn)制變量（Binary Variable），這類問(wèn)題也就稱為0-1整數(shù)規(guī)劃。2.3 0-1整數(shù)規(guī)劃的應(yīng)用舉例例2.1. 某商家擬在、三個(gè)選址上投資建廠，表2-1給出了商家所要考慮的因素，為使獲利最大，該商家應(yīng)作如何的選擇？表2-1資源限制獲利（萬(wàn)元）3-25倉(cāng)庫(kù)容量（立方千米）1414交通方便指數(shù)12-12人流量指數(shù)1103物資運(yùn)輸費(fèi)用（千元）0416解：引入0-1變量，設(shè)則原問(wèn)題的數(shù)學(xué)模型為例2.2.

17、 今年某廠對(duì)、五個(gè)產(chǎn)品經(jīng)銷點(diǎn)的人力、設(shè)備進(jìn)行調(diào)整，為節(jié)約成本，有些點(diǎn)可能要裁員或減少設(shè)備數(shù)，具體數(shù)據(jù)如表2-2所示。為使總投資最少，問(wèn)廠方應(yīng)作出何種最優(yōu)調(diào)整決策？表2-2 資源經(jīng)銷點(diǎn)設(shè)備（套）人力（人）投資（萬(wàn)元）-3-58-3-321-242-47315資源限制-2-4解：引入0-1變量，設(shè)則原問(wèn)題的數(shù)學(xué)模型為例2.3. 在今后三年內(nèi)有四項(xiàng)工程考慮施工，每項(xiàng)工程的期望收入和年度費(fèi)用（萬(wàn)元）如表2-3所示，假定每一項(xiàng)已經(jīng)批準(zhǔn)的工程要在三年內(nèi)完成，其中第1年和第2年得可用基金最多為10萬(wàn)和3萬(wàn)，第3年至少花費(fèi)4萬(wàn)，為使總收入達(dá)到最大，問(wèn)如何選出最優(yōu)工程？表2-3工程費(fèi)用（萬(wàn)元）收入（萬(wàn)元）第1年

18、第2年第3年11236221-523411345-165解：引入0-1變量，設(shè)則原問(wèn)題的數(shù)學(xué)模型為例2.4. 一位旅行者出發(fā)前準(zhǔn)備在自己的背包中攜帶必需的物品，已知可供選擇的物品有種，第種物品的重量為公斤，其價(jià)值（或效益）為，如果旅行者的背包所帶物品的總重量不得超過(guò)公斤，問(wèn)旅行者應(yīng)如何選擇所帶物品，以使總價(jià)值（總效益）最大？在選擇裝入背包的物品時(shí)，對(duì)每種物品只有兩種選擇，即裝入背包或不裝入背包。不能將物品裝入背包多次，也不能只裝入部分的物品。因此，該問(wèn)題稱為背包問(wèn)題。解:先引入0-1變量， 設(shè) 則背包問(wèn)題的數(shù)學(xué)模型為在生產(chǎn)計(jì)劃決策中，常常碰到固定費(fèi)用問(wèn)題。一般來(lái)說(shuō)，總收益=銷售收入-（固定費(fèi)用

19、+可變費(fèi)用）。建模時(shí)，碰到的困難主要是事先不能確切知道某種產(chǎn)品是否生產(chǎn)，因而不能確定相應(yīng)的固定費(fèi)用是否發(fā)生。如果借助于0-1變量便可解決這個(gè)問(wèn)題。例2.5. 有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用及售價(jià)、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用見(jiàn)表2-4。要求制訂一個(gè)生產(chǎn)計(jì)劃，使總收益最大。資源單耗量產(chǎn)品資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單間售價(jià)81012表2-4解：設(shè)是第種產(chǎn)品的產(chǎn)量，再設(shè) 則問(wèn)題的整數(shù)規(guī)劃模型是其中為的某個(gè)上界。如果生產(chǎn)第種產(chǎn)品，則其產(chǎn)量。此時(shí)，由約束條件，知。因此，相應(yīng)的固定費(fèi)用在目標(biāo)函數(shù)中將被考慮。

20、如果不生產(chǎn)第種產(chǎn)品，則其產(chǎn)量。此時(shí)，約束條件可知，可以是0也可以是1。但不利于目標(biāo)函數(shù)的最大化，因而在問(wèn)題的最優(yōu)解中必然是，從而相應(yīng)的固定費(fèi)用在目標(biāo)函數(shù)中將不被考慮9。2.4 本章小結(jié)本章主要介紹了0-1整數(shù)規(guī)劃的相關(guān)概念、特點(diǎn)及其作用。通過(guò)實(shí)例介紹0-1整數(shù)規(guī)劃在選址問(wèn)題、投資問(wèn)題、生產(chǎn)計(jì)劃問(wèn)題、生產(chǎn)決策問(wèn)題中的應(yīng)用。說(shuō)明了0-1整數(shù)規(guī)劃模型在實(shí)際問(wèn)題中的應(yīng)用非常廣泛。第3章 窮舉法3.1 窮舉法的介紹對(duì)于0-1整數(shù)規(guī)劃問(wèn)題，由于每個(gè)變量只取0或1，因此求解時(shí)最容易想到的方法，就是窮舉法，即將所有的0,1組合找出，然后檢查每一種組合是否滿足約束條件，再比較目標(biāo)函數(shù)值以求得最優(yōu)解。3.2 窮舉

21、法的計(jì)算實(shí)例例3.1. 利用窮舉法求解例2.1。解: 列出變量取值為0或1的組合，共個(gè)，分別代入約束條件判斷是否滿足。具體求解過(guò)程如表3-1所示。表3-1 約束條件滿足條件值（1） （2） （3） （4）是 否×（0,0,0） 0 0 0 00（0,0,1） -1 1 0 15（0,1,0） 2 4 1 4-2（1,0,0） 1 1 1 03（0,1,1） 1 5×（1,0,1） 0 2 1 18（1,1,0） 3×（1,1,1） 2 6×從而得最優(yōu)解為，最優(yōu)值為。3.3 對(duì)窮舉法的評(píng)價(jià)當(dāng)變量的個(gè)數(shù)比較少、約束條件比較簡(jiǎn)單時(shí)，使用窮舉法求解0-1整數(shù)規(guī)劃

22、問(wèn)題比較簡(jiǎn)單明了。但是當(dāng)變量的個(gè)數(shù)比較多、約束條件比較復(fù)雜時(shí)，使用窮舉法求解時(shí)要求必須檢查每一種組合，而全部組合的個(gè)數(shù)是隨著變量的個(gè)數(shù)以冪的形式增加的，即個(gè)變量則有種組合。例如，當(dāng)決策變量數(shù)為15，約束條件數(shù)也為15時(shí)，使用窮舉法需要進(jìn)行次運(yùn)算，這幾乎是不可能的。所以在實(shí)際問(wèn)題中，當(dāng)決策變量數(shù)和約束條件數(shù)較大時(shí)，由于運(yùn)算量太大以致窮舉法根本不適用。3.4 本章小結(jié)本章研究了求解0-1整數(shù)規(guī)劃的窮舉法， 并對(duì)算法進(jìn)行了實(shí)證分析。算法顯示：當(dāng)變量的個(gè)數(shù)比較少、約束條件比較簡(jiǎn)單時(shí)，使用窮舉法求解0-1整數(shù)規(guī)劃問(wèn)題比較簡(jiǎn)單明了。但是當(dāng)變量的個(gè)數(shù)比較多、約束條件比較復(fù)雜時(shí)，由于運(yùn)算量太大將導(dǎo)致窮舉法根本

23、不適用。第4章 隱枚舉法鑒于變量較多時(shí)窮舉法的運(yùn)算量太大，不是一種有效的算法，因此提出隱枚舉法，即只要檢查全部變量組合中的一部分組合就可求出最優(yōu)解。目前，求解0-1整數(shù)規(guī)劃問(wèn)題通常采用隱枚舉法，該方法大體又分為兩種類型：一種為過(guò)濾隱枚舉法，一種為分枝定界法。4.1 過(guò)濾隱枚舉法4.1.1 過(guò)濾隱枚舉法的介紹過(guò)濾隱枚舉法10是在窮舉法的基礎(chǔ)上進(jìn)行了改進(jìn)，對(duì)于最大值問(wèn)題求解的基本步驟如下：（1）尋找一個(gè)初始可行解，得到對(duì)應(yīng)目標(biāo)值的下界（最小值問(wèn)題則為上界）；（2）按窮舉法列出個(gè)變量取值的組合，當(dāng)組合解對(duì)應(yīng)的目標(biāo)值小于時(shí)則認(rèn)為不可行，當(dāng)大于等于時(shí)，再檢驗(yàn)是否滿足約束條件，得到0-1整數(shù)規(guī)劃問(wèn)題的可行

24、解；（3）依據(jù)的值確定最優(yōu)解。這里的下界可以動(dòng)態(tài)移動(dòng)，當(dāng)某個(gè)大于時(shí)則將作為新的下界。4.1.2 過(guò)濾隱枚舉法的計(jì)算實(shí)例例4.1. 利用過(guò)濾隱枚舉法求解例2.1。解：求解思路及改進(jìn)措施如下：（1）先試探性求一個(gè)可行解，易看出滿足約束條件，故可作為一個(gè)初始可行解，得到對(duì)應(yīng)目標(biāo)值；（2）因?yàn)槭乔笞畲笾祮?wèn)題，故求最優(yōu)解時(shí)，凡是目標(biāo)值的解不必檢驗(yàn)是否滿足約束條件即可刪除，因?yàn)樗隙ú皇亲顑?yōu)解，于是應(yīng)增加一個(gè)約束條件（目標(biāo)值下界）：，稱該條件為過(guò)濾條件(Filtering Contraint)。原問(wèn)題變?yōu)楦鶕?jù)窮舉法，3個(gè)變量共有8種可能的組合，將這8種組合依次檢驗(yàn)它是否滿足條件，對(duì)某個(gè)組合，若它不滿足，即

25、不滿足過(guò)濾條件，則的可行性條件不必再檢驗(yàn)；若它滿足且對(duì)應(yīng)的目標(biāo)值均嚴(yán)格大于3，則進(jìn)行下一步；（3） 改進(jìn)過(guò)濾條件；（4） 由于對(duì)每個(gè)組合首先計(jì)算目標(biāo)值以驗(yàn)證過(guò)濾條件，故應(yīng)優(yōu)先計(jì)算目標(biāo)值大的組合，這樣可提前抬高過(guò)濾門檻，以減少計(jì)算量。按上述思路與方法，例2.1求解過(guò)程如表4-1所示。表4-1 目標(biāo)值約束條件過(guò)濾條件 （0,0,0）0×（0,0,1）5 （0,1,0）-2×（1,0,0）3 （0,1,1）3×（1,0,1）8 （1,1,0）1×（1,1,1）6×從而得最優(yōu)解為，最優(yōu)值為。選擇不同的初始可行解，計(jì)算量會(huì)不一樣。一般地，當(dāng)目標(biāo)函數(shù)求最大

26、值時(shí)，首先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于1；當(dāng)目標(biāo)函數(shù)求最小值時(shí)，先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于0。4.1.3 對(duì)過(guò)濾隱枚舉法的評(píng)價(jià)對(duì)過(guò)濾隱枚舉法來(lái)說(shuō)其數(shù)學(xué)模型無(wú)須轉(zhuǎn)化為標(biāo)準(zhǔn)型，減少了人工處理的工作量，但它需要檢驗(yàn)的方案較多，而且在集體操作中存在兩個(gè)明顯的不確定因素：（1）該方法要求先求出一個(gè)可行解，但并沒(méi)有給出求第一個(gè)可行解的方法。當(dāng)約束條件較多，不可能一眼看出哪一個(gè)變量組合是可行解時(shí)，須通過(guò)試探的方法來(lái)解決。這種做法比較盲目，有時(shí)得試探好幾個(gè)變量組合后才能找到第一個(gè)可行解。（2）雖不管通過(guò)多少次試算總可找到一個(gè)可行解，并據(jù)以建立過(guò)濾條件，但所建立的過(guò)濾條件，有效性如何又是難以確定的。如通

27、過(guò)試算所找到的可行解的值是全部可行解中值較小或最小的，那么，所建立的過(guò)濾條件必然是很弱的，甚至起不到過(guò)濾作用。由于以上兩個(gè)不確定性因素的存在，直接影響到本解法對(duì)減少工作量的有效性，這是過(guò)濾隱枚舉法存在的主要缺陷11。4.2 分枝定界法4.2.1 分枝定界法的介紹解題思路12與解整數(shù)規(guī)劃的分枝定界法相似，利用變量只能取0或1兩個(gè)值的特性，進(jìn)行分枝。首先令全部變量取0值，檢驗(yàn)解是否可行。若可行，已得最優(yōu)解；若不可行，則令一個(gè)變量取值為0或1（此變量稱為固定變量），將問(wèn)題分成兩個(gè)子域，其余未被指定取值的變量稱為自由變量。由于這些自由變量在目標(biāo)函數(shù)中的系數(shù)都是正數(shù)，因此令自由變量為0與固定變量組成的子

28、域的解使目標(biāo)函數(shù)值最小。經(jīng)過(guò)幾次檢驗(yàn)，或者停止分枝，或者將第二個(gè)自由變量轉(zhuǎn)為固定變量，令其值為0或1，將此子域再分成兩個(gè)子域。如此繼續(xù)進(jìn)行，直至沒(méi)有自由變量或全部子域停止分枝為止，就求出最優(yōu)解。具體計(jì)算步驟如下：（1）令全部都是自由變量且取值為0，檢驗(yàn)解是否可行。若可行，已得最優(yōu)解；若不可行，進(jìn)行（2）；（2）將某一變量轉(zhuǎn)為固定變量，令其取值為1或0，使問(wèn)題分成兩個(gè)子域。令一個(gè)子域中的自由變量都取0值，加上固定變量取值，組成此子域的解；（3）計(jì)算此解的目標(biāo)函數(shù)值，與已求出的可行解的最小目標(biāo)函數(shù)值比較。如前者大，則不必檢驗(yàn)其是否可行而停止分枝，若子域都檢驗(yàn)過(guò)，轉(zhuǎn)（7），否則轉(zhuǎn)（6）。因繼續(xù)分枝即

29、使得到可行解，其目標(biāo)函數(shù)值也較大，不會(huì)是最優(yōu)解；如前者小，進(jìn)行（4）。對(duì)第一次算出的目標(biāo)函數(shù)值，不必進(jìn)行比較，直接轉(zhuǎn)（4）；（4）檢驗(yàn)解是否可行。如可行，已得一個(gè)可行解，計(jì)算并記下它的值，并停止分枝。若子域都檢驗(yàn)過(guò)，轉(zhuǎn)（7），否則轉(zhuǎn)（6）。因繼續(xù)分枝，即使得到可行解，目標(biāo)函數(shù)值也比記下的值大，不會(huì)是最優(yōu)解；如不可行，進(jìn)行（5）；（5）將子域固定變量的值代入第一個(gè)不等式約束條件方程，并令不等式左端的自由變量當(dāng)系數(shù)為負(fù)時(shí)取值為1，系數(shù)為正時(shí)取值為0，這就是左端所能取的最小值。若此最小值大于右端值，則稱此子域?yàn)椴豢尚凶佑?，不再往下分枝。若子域都檢驗(yàn)過(guò)，轉(zhuǎn)（7），否則轉(zhuǎn)（6）；若此最小值小于右端值，則

30、依次檢驗(yàn)下一個(gè)不等式約束方程，直至所有的不等式約束方程都通過(guò)。若子域都檢驗(yàn)過(guò)，轉(zhuǎn)（7），否則轉(zhuǎn)（6）；（6）定出尚未檢驗(yàn)過(guò)的另一個(gè)子域的解，進(jìn)行（3）至（5），若所有子域都停止分枝，計(jì)算停止，目標(biāo)函數(shù)值最小的可行解就是最優(yōu)解；否則，轉(zhuǎn)（7）；（7）檢查有無(wú)自由變量。若有，轉(zhuǎn)（2）；若沒(méi)有，計(jì)算停止。目標(biāo)函數(shù)值最小的可行解就是最優(yōu)解。由于（3）、（4）、（5）中都有停止分枝的情況，對(duì)這些子域自由變量取值為0或1的一切可能組合都被隱含地考慮過(guò)了，不必再一一列舉。所以，這種方法與窮舉法比較，計(jì)算量可大大減少。注意，要應(yīng)用這種算法，0-1規(guī)劃模型必須是下述標(biāo)準(zhǔn)型：其中，可以是正數(shù)、負(fù)數(shù)或0，所有約束條

31、件方程必須是“”型式。如果0-1規(guī)劃模型不是標(biāo)準(zhǔn)型式，則可作下述變換，使其成為標(biāo)準(zhǔn)型式：（1）如目標(biāo)函數(shù)是求最大，可將目標(biāo)函數(shù)乘-1并求最??；（2）如約束條件方程是“”型式，可將不等式兩端乘-1，變換為“”型式；（3）如約束條件方程是“=” 型式，則將它變換為一個(gè)“”型式和一個(gè)“”型式的約束條件方程，并對(duì)后一方程兩端乘-1，使其成為“”型式；（4）如果有一個(gè)變量的目標(biāo)函數(shù)系數(shù)，則可用替換。例如：，令，則。4.2.2 分枝定界法的計(jì)算實(shí)例例4.2. 利用分枝定界法求解例2.2。 解：這個(gè)問(wèn)題的枚舉樹(shù)如圖4-1所示。圖4-1下面對(duì)樹(shù)中的幾個(gè)子域加以說(shuō)明：1、 經(jīng)過(guò)（1）、（2）、（3）后進(jìn)行（4）

32、，子域1的解（1,0,0,0,0）可行，記下，不再分枝。轉(zhuǎn)（6），對(duì)子域2進(jìn)行檢驗(yàn)計(jì)算，進(jìn)行（4），此解（0,0,0,0,0）不可行。但（5）能通過(guò)兩個(gè)不等式約束方程，轉(zhuǎn)（7），尚有自由變量，對(duì)子域2分枝成子域3及4。2、 子域3的解（0,1,0,0,0），不可行，但能通過(guò)兩個(gè)不等式約束方程，轉(zhuǎn)（6），對(duì)子域4進(jìn)行檢驗(yàn)計(jì)算。3、子域4的解（0,0,0,0,0）與初始解相同，不可行。進(jìn)行（5），將，代入第一個(gè)約束方程，并令，求出左端的可能最小值為0，大于右端值-2，可知子域4是不可行子域，不再分枝。轉(zhuǎn)（7），對(duì)子域3進(jìn)行分枝得子域5及6。4、子域5的解為（0,1,1,0,0），此解可行，記下值，

33、不再分枝，轉(zhuǎn)（6）。5、子域6的解為（0,1,0,0,0），與子域3的解相同，直接進(jìn)行（5），能通過(guò)兩個(gè)不等式約束方程，進(jìn)行（7），對(duì)子域6進(jìn)行分枝得子域7及8。6、子域7的解（0,1,0,1,0），不再分枝。子域8是不可行子域，所有子域都停止分枝，計(jì)算停止。7、此問(wèn)題的最優(yōu)解是子域5的解（0,1,1,0,0），。4.2.3 對(duì)分枝定界法的評(píng)價(jià)對(duì)分枝定界法來(lái)說(shuō)，所需檢驗(yàn)的方案較少，這是其優(yōu)點(diǎn)。但在檢驗(yàn)之前必須通過(guò)人工處理將數(shù)學(xué)模型標(biāo)準(zhǔn)化，當(dāng)問(wèn)題復(fù)雜時(shí)，人工處理的工作量很大，且易出錯(cuò)，這是其缺點(diǎn)之一。在具體操作過(guò)程中還存在如下問(wèn)題，即此解法有效性的關(guān)鍵在于檢驗(yàn)前必須排出一個(gè)能體現(xiàn)各解點(diǎn)值大小順序

34、的對(duì)各變量取值0或1的各種組合的檢驗(yàn)順序，當(dāng)變量個(gè)數(shù)較多的時(shí)候，這是相當(dāng)困難的。4.3 分枝隱枚舉法根據(jù)過(guò)濾隱枚舉法和分枝定界法各自的特點(diǎn)，將這兩種算法結(jié)合起來(lái)，就形成了分枝隱枚舉法。4.3.1 分枝隱枚舉法的介紹分枝隱枚舉法9的計(jì)算步驟如下：（1）將0-1規(guī)劃問(wèn)題的目標(biāo)函數(shù)的系數(shù)化為非負(fù)，如，令，則當(dāng)變量做了代換后，約束條件中的變量也相應(yīng)作代換；（2）變量重新排序。變量依據(jù)目標(biāo)函數(shù)系數(shù)值按升排序，如，令，則；（3）求主枝。目標(biāo)函數(shù)是形式時(shí)令所有變量等于1，得到目標(biāo)值的上界；目標(biāo)函數(shù)是形式時(shí)令所有變量等于0，得到目標(biāo)值的下界；如果主枝的解滿足所有約束條件則得到最優(yōu)解，否則轉(zhuǎn)下一步；（4）分枝與

35、定界。從第一個(gè)變量開(kāi)始依次取1或0，求極大值時(shí)其后面的變量等于1，求極小值時(shí)其后面的變量等于0，用分枝定界法搜索可行解和最優(yōu)解。分枝隱枚舉法是從非可行解中進(jìn)行分枝搜索可行解，第（1）步到第（3）步用了過(guò)濾隱枚舉法的思路，第（4）步用了分枝定界法的思路。停止分枝和需要繼續(xù)分枝的原則如下：（1）當(dāng)某一子問(wèn)題是可行解時(shí)則停止分枝并保留；（2）不是可行解但目標(biāo)值劣于現(xiàn)有保留分枝的目標(biāo)值時(shí)停止分枝并剪枝；（3）后續(xù)分枝變量無(wú)論取1或0都不能得到可行解時(shí)停止分枝并剪枝；（4）當(dāng)某一子問(wèn)題不可行但目標(biāo)值優(yōu)于現(xiàn)有保留分枝的所有目標(biāo)值，則要繼續(xù)分枝。從以上原則可以看出，子問(wèn)題可行時(shí)停止分枝，子問(wèn)題不可行時(shí)則有可

36、能繼續(xù)分枝。但需要注意的是保留和剪枝的含義，盡管它們的子問(wèn)題都是停止分枝，但保留的子問(wèn)題是可行的，最優(yōu)解就在其中，而剪枝的子問(wèn)題是不可行的。4.3.2 分枝隱枚舉法的計(jì)算實(shí)例例4.3. 利用分枝隱枚舉法求解例2.3。 解 ：（1）目標(biāo)函數(shù)系數(shù)全部非負(fù)，直接對(duì)變量重新排序（2）求主枝。令得到主枝1，檢查約束條件知（3）式不滿足，則進(jìn)行分枝。（3）令同時(shí)令及得到分枝2和分枝3，和是可行解，分枝停止并保留，如圖4-2所示。令同時(shí)令得到分枝4，是可行解，分枝停止并保留。令，取0和1,得到分枝5和分枝6，分枝5不可行并且小于和，分枝停止并剪枝。注意到分枝6，時(shí)只有（就是主枝），不可行并且小于和，分枝停止

37、并剪枝，分枝過(guò)程結(jié)束。整個(gè)計(jì)算過(guò)程可用圖4-2和表4-2表示。圖4-2表4-2分枝（1）（2）（3）目標(biāo)值可行性1（1,1,1,1）×16不可行2（0,0,1,1）11可行3（0,1,1,1）14可行4（1,0,1,1）13可行5（1,1,0,1）×11不可行6（1,1,1,0）×10不可行搜索到3個(gè)可行解，3個(gè)目標(biāo)值中最大，因此是最優(yōu)解，即原問(wèn)題的最優(yōu)解為，最優(yōu)值，計(jì)算結(jié)束。4.3.3 對(duì)分枝隱枚舉法的評(píng)價(jià) 分枝隱枚舉法是將過(guò)濾隱枚舉法和分枝定界法這兩種算法結(jié)合起來(lái)，克服了分枝定界法所需的在檢驗(yàn)之前必須通過(guò)人工處理將數(shù)學(xué)模型標(biāo)準(zhǔn)化，同時(shí)也避免了隱枚舉法需要檢驗(yàn)很

38、多方案的弊端，對(duì)于變量個(gè)數(shù)和約束條件個(gè)數(shù)比較少時(shí)，運(yùn)算起來(lái)比較方便、實(shí)用。但是，當(dāng)變量個(gè)數(shù)和約束條件個(gè)數(shù)比較多時(shí)，需要分的“枝”就很多，因此運(yùn)算量就會(huì)成倍增大。4.4 本章小結(jié)本章主要研究求解0-1整數(shù)規(guī)劃的隱枚舉法，包括過(guò)濾隱枚舉法、分枝定界法、分枝隱枚舉法，對(duì)每種算法進(jìn)行了實(shí)證分析，并針對(duì)每種算法的特點(diǎn)作出了評(píng)價(jià)。第5章 組合直接搜尋法5.1 組合直接搜尋法的介紹考慮下面的0-1規(guī)劃問(wèn)題：這里，是整數(shù)集，和是相應(yīng)維數(shù)的非負(fù)整數(shù)向量。不妨設(shè)，否則，可以按價(jià)值系數(shù)從小到大的順序?qū)ψ兞恐匦戮幪?hào)。由約束條件（2），構(gòu)造一張初始表作為0-1規(guī)劃計(jì)算求解的平臺(tái)。如表5-1所示表5-1 X f -b 其

39、中，。然后，把分量取0或1的所有整數(shù)向量按分量中所含1的個(gè)數(shù)進(jìn)行分類，令是個(gè)分量取1，個(gè)分量取0的向量集合，顯然有，且。于是，從開(kāi)始，依次在的每個(gè)子集中搜尋（IP）的相對(duì)局部最優(yōu)點(diǎn)。根據(jù)對(duì)0-1規(guī)劃（IP）所作的假設(shè)，中的唯一向量不是可行解；當(dāng)，可以通過(guò)表5-1直接計(jì)算判斷中的（IP）相對(duì)局部最優(yōu)點(diǎn)。首先，設(shè)，對(duì)滿足所在行，從左至右依次計(jì)算直到某一列，使為止；最后，根據(jù)假設(shè)，可以判斷是中的（IP）相對(duì)局部最優(yōu)點(diǎn)，此時(shí)，相應(yīng)的局部最優(yōu)值為。一般地，中的點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)取值范圍可通過(guò)下述估計(jì)定理來(lái)描述。定理113 中所有點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)取值滿足不等式：根據(jù)對(duì)（IP）的約定：，以及中點(diǎn)的特征，不等式

40、（4）成立是顯而易見(jiàn)的。于是，根據(jù)上述定理，當(dāng)?shù)南鄬?duì)局部最優(yōu)值時(shí)，則對(duì)的局部尋優(yōu)計(jì)算過(guò)程終止，比較前面獲得的各個(gè)子集的局部最優(yōu)值，其中最小的值就是（IP）的最優(yōu)值，即，與相應(yīng)的解為（IP）的最優(yōu)解；如果，則對(duì)繼續(xù)進(jìn)行局部尋優(yōu)計(jì)算。此時(shí)，把中每一個(gè)向量取1的分量組合在一起，用一個(gè)字母表示。比如分量組合在一起，表示為，當(dāng)且僅當(dāng)；它在計(jì)算判斷表5-2中對(duì)應(yīng)的目標(biāo)函數(shù)系數(shù)，約束條件（2）的系數(shù)表5-2 的局部尋優(yōu)計(jì)算判斷表 -b 其中，向量是維行向量，即，矩陣是矩陣。的分量按從小到大的順序排列。然后，可以在表5-2中尋找的相對(duì)局部最優(yōu)解。類似于表5-1，即在中的尋優(yōu)過(guò)程，如果中存在（IP）的可行解，則

41、一定可以找到某個(gè)，滿足此時(shí)是中的（IP）相對(duì)局部最優(yōu)點(diǎn)，按照前述組合約定，不妨設(shè)代表中個(gè)變量的組合，則（IP）在中的相對(duì)局部最優(yōu)解為相對(duì)局部最優(yōu)值為。上述尋優(yōu)過(guò)程直到，如果（IP）存在可行解，則通過(guò)本算法，最終會(huì)獲得（IP）的最優(yōu)解；否則，（IP）無(wú)可行解。根據(jù)上述算法原理，可以得到相應(yīng)的算法步驟13如下：步驟1，取，將價(jià)值系數(shù)從小到大排序后得到，按照表5-1的形式列出初始計(jì)算表。計(jì)算直到某一列，使，由此在中求得最優(yōu)解（6）和最優(yōu)值。步驟2，置，如果時(shí)，則對(duì)的局部尋優(yōu)計(jì)算過(guò)程終止，比較前面獲得的各個(gè)子集的局部最優(yōu)值，其中最小的值就是（IP）的最優(yōu)值，即，與相應(yīng)的解為（IP）的最優(yōu)解；否則，轉(zhuǎn)下

42、一步。步驟3，對(duì)向量集合中的向量，根據(jù)分量取1的變量組合成一個(gè)新的變量，得到相應(yīng)的局部尋優(yōu)計(jì)算表5-2，計(jì)算得到中的相對(duì)局部最優(yōu)解和最優(yōu)值。步驟4，如果，則算法終止。此時(shí)，或者求得了全局最優(yōu)解和相應(yīng)的目標(biāo)最優(yōu)值，或者判斷（IP）無(wú)可行解；否則，轉(zhuǎn)步驟2。5.2 組合直接搜尋法的計(jì)算實(shí)例例5.2. 利用組合直接搜尋法求解下列優(yōu)化問(wèn)題： 解 ：按表5-1構(gòu)造初始表5-3如下。表5-311467-43-2624-2-51116顯然中的唯一向量不是（IP）的可行解；則由上表，只有變量所在的列滿足判別式：，故（IP）在中的相對(duì)局部最優(yōu)解及最優(yōu)目標(biāo)值為：。然后，對(duì)中的向量，有目標(biāo)取值的估計(jì)：，于是，需對(duì)實(shí)

43、施局部尋優(yōu)；按本算法組合中各向量的變量，并進(jìn)行相應(yīng)的計(jì)算如表5-4所示。表5-4 局部尋優(yōu)計(jì)算表255-4194-2-4-42據(jù)表5-4，滿足（5）的，此時(shí)，（IP）在中的相對(duì)局部最優(yōu)解及最優(yōu)目標(biāo)值為：。最后，對(duì)中的向量，有目標(biāo)取值的估計(jì)：；由，本算法的尋優(yōu)過(guò)程終止。比較和的目標(biāo)最優(yōu)值，可得（IP）的最優(yōu)解及最優(yōu)目標(biāo)值為。5.3 對(duì)組合直接搜尋法的評(píng)價(jià)與隱枚舉法相比，組合直接搜尋法簡(jiǎn)單適用，計(jì)算過(guò)程非常簡(jiǎn)捷。整個(gè)計(jì)算判斷過(guò)程可以在同一張表臺(tái)上進(jìn)行，非常方便、直觀。當(dāng)（IP）的全局最優(yōu)目標(biāo)值與中的局部最優(yōu)目標(biāo)值之差較小且也是一個(gè)小正整數(shù)時(shí)，算法的效率是很高的。5.4 本章小結(jié)本章主要研究求解0-1整數(shù)規(guī)劃的組合直接搜尋法，對(duì)該算法進(jìn)行了實(shí)證分析。與隱枚舉法相比，組合直接搜尋法簡(jiǎn)單適用，計(jì)算過(guò)程非常簡(jiǎn)捷，整個(gè)計(jì)算判斷過(guò)程可以在同一張表臺(tái)上進(jìn)行，非常方便、直觀。結(jié) 論0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃中一類特殊的情形，它的變量只能取0或1。對(duì)于很多管理問(wèn)題無(wú)法歸結(jié)為線性規(guī)劃的數(shù)學(xué)模型，可以借助0-1變量，將很多含“非此即彼”的、相互排斥的決策變量和約束條件放在一個(gè)模型中統(tǒng)一研究，從而建立起相應(yīng)的0-1整數(shù)規(guī)劃模型。求解0-1整數(shù)規(guī)劃問(wèn)題，一般選用隱枚舉法，包括過(guò)濾隱枚舉法、分枝定界法和分枝隱枚舉法，但特別