整數(shù)規(guī)劃問題應(yīng)用畢業(yè)論文

1、目 錄摘要iabstractii引言11 整數(shù)規(guī)劃問題11.1 概念11.2 分類11.3 整數(shù)規(guī)劃的一般形式22 整數(shù)規(guī)劃問題的計算方法22.1 分支定界法22.2 割平面法23 整數(shù)規(guī)劃問題的應(yīng)用33.1在經(jīng)濟(jì)管理問題中的應(yīng)用33.1.1 投資問題33.1.2 生產(chǎn)安排問題43.1.3 下料問題73.2 在指派問題中的應(yīng)用83.2.1 平衡指派問題93.2.2 不平衡指派問題103.2.3 非確定型指派問題123.3 在組合優(yōu)化方面的應(yīng)用143.3.1 一維背包問題143.3.2 選址問題153.4 在集合劃分問題中的應(yīng)用163.4.1 中心覆蓋問題173.4.2 旅行商問題(tsp)18

2、結(jié)論19致謝20參考文獻(xiàn)20整數(shù)規(guī)劃問題的應(yīng)用摘要：整數(shù)規(guī)劃(integer programming，ip)是帶整數(shù)變量的最優(yōu)化問題。即最大化或最小化全部或部分變量為整數(shù)的多元函數(shù)受約束于一組等式和不等式條件的最優(yōu)化問題。整數(shù)規(guī)劃的歷史可以追溯到20世紀(jì)50年代，主要是由于經(jīng)濟(jì)管理中的大量問題抽象為模型時，人們發(fā)現(xiàn)許多量具有不可分割性，因此當(dāng)它們被作為變量引入到規(guī)劃中時，常要求滿足取整條件。而今，許多經(jīng)濟(jì)、管理、通信和工程中的最優(yōu)化問題都可以用整數(shù)規(guī)劃來建模。本文主要闡述了整數(shù)規(guī)劃的理論基礎(chǔ)，給出了整數(shù)規(guī)劃的基本模型以及計算方法，在此基礎(chǔ)上對一些整數(shù)規(guī)劃問題及其解答方法進(jìn)行歸納總結(jié)，最后列舉了

3、若干整數(shù)規(guī)劃在現(xiàn)實中的應(yīng)用實例，將數(shù)學(xué)知識應(yīng)用到實際生活中來解決實際問題,從而使得該問題形象化、簡單化，同時進(jìn)一步完善和豐富整數(shù)規(guī)劃理論。關(guān)鍵詞： 整數(shù)規(guī)劃問題；實際應(yīng)用；0-1整數(shù)規(guī)劃；數(shù)學(xué)模型application of integer programming problemsabstract: integer programming is an optimization problem with integer variables, which maximize or minimize the multiple functions of full or partial variables

4、 for integer, subject to a set of equality and inequality constraint optimization problems.the history of integer programming can be traced back to the nineteen fifties, mainly due to a large number of problems in economic management be abstracted as a model, it is found that many are inseparable, t

5、herefore when they are taken as variables into the planning, often meet the requirements of integral conditions.now, many optimization problems with integer of economic, management, communication and engineering can be use to build model.this paper discusses the theoretical basis of integer programm

6、ing, on which summarize some integer programming problems and their answers. and how link up with other mathematical knowledge to solve practical problems. finally, this paper sums up several applications of integer programming in the reality. that makes the problem visualize and simplify, and furth

7、er improve and enrich integer programming theory.keywords: integer programming；practical application；0-1 integer linear programming；mathematical model引言 整數(shù)規(guī)劃(integer programming，ip)是規(guī)劃論中近30年才發(fā)展起來一個重要分支。整數(shù)規(guī)劃與組合最優(yōu)化從廣泛的意義上說，兩者的領(lǐng)域是一致的，都是在有限個可供選擇的方案中，尋找滿足一定標(biāo)準(zhǔn)的最好方案。有許多典型的問題反映整數(shù)規(guī)劃的廣泛背景。例如，背包（或裝載）問題、固定費用問題、

8、有效探險隊問題（組合學(xué)的覆蓋問題）、送貨問題等。因此整數(shù)規(guī)劃的應(yīng)用范圍是極其廣泛的。它不僅在工業(yè)、工程設(shè)計和科學(xué)研究方面有許多應(yīng)用，而且在計算機(jī)設(shè)計、系統(tǒng)可靠性、編碼和經(jīng)濟(jì)分析等方面也有新的應(yīng)用。此外，整數(shù)規(guī)劃還可以描述和處理互斥決策問題。如運(yùn)作管理中的決策問題：工廠選址、超市選址、人員的工作指派、設(shè)備購置和配置、系統(tǒng)可靠性設(shè)計、機(jī)床加工任務(wù)的均衡分派、線路設(shè)計中的接點串聯(lián)設(shè)計等；物流管理中，物流中心的定點決策；以及金融和項目投資中的組合投資和項目選擇等等。其規(guī)劃模型中往往可以引入邏輯變量（即變量僅取 0 或 1 兩個值）來反映沖突因素和抉擇。另外，整數(shù)規(guī)劃還可以實現(xiàn)不相容狀態(tài)下，分散模型的模

9、式統(tǒng)一，加強(qiáng)系統(tǒng)研究的集成性。因此，整數(shù)規(guī)劃模型不同于前述的線性規(guī)劃范疇，而屬于一種新的類型。整數(shù)規(guī)劃在實踐中有比線性規(guī)劃更為廣泛的應(yīng)用空間，對整數(shù)規(guī)劃問題的探究是十分有必要的。1 整數(shù)規(guī)劃問題1.1 概念要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃(integer programming，簡記ip)。不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題(slack problem)。若松弛問題是一個線性規(guī)則，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃(integer linear programming，簡記ilp) 1.2 分類 整數(shù)規(guī)劃問題按決策變量取值可

10、分為下列幾種類型：1純整數(shù)規(guī)劃(pure integer programming)：指全部決策變量都必須取整數(shù)值的整數(shù)規(guī)劃。有時，也稱為全整數(shù)規(guī)劃。2混合整數(shù)規(guī)劃(mixed integer programming)：指決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)規(guī)劃。30-1型整數(shù)規(guī)劃(zeroone integer programming)：指決策變量只能取值0或1的整數(shù)規(guī)劃。1.3 整數(shù)規(guī)劃的一般形式 2 整數(shù)規(guī)劃問題的計算方法2.1 分支定界法分支定界法是在20世紀(jì)60年代初由land doing和dakin等人提出的適合于解純整數(shù)或混合整數(shù)規(guī)劃問題的方法。分支定界法的

11、主要思路是首先求解整數(shù)規(guī)劃的伴隨規(guī)劃，如果求得的最優(yōu)解不符合整數(shù)條件，則增加新約束縮小可行域；將原整數(shù)規(guī)劃問題分支分為兩個子規(guī)劃，再解子規(guī)劃的伴隨規(guī)劃，以此類推，最后得到原整數(shù)規(guī)劃的伴隨規(guī)劃。這就是所謂的“分支”。所謂“定界”，是在分支過程中，若某個后繼問題恰巧獲得整數(shù)規(guī)劃問題的一個可行解，那么，它的目標(biāo)函數(shù)值就是一個“界限”，可以作為衡量處理其它分支的一個依據(jù)。“分支”為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件，而“定界”則可以提高搜索的效率。分支定界法的計算步驟第一步：計算原問題目標(biāo)函數(shù)值的初始上界第二步：計算原問題目標(biāo)函數(shù)值的初始下界第三步：增加約束條件將原問題分支第四步：分別求解一對分支第五步：

12、修改上、下界第六步：比較上、下界大小，如有上界下界，停止計算，找到最優(yōu)解，否則轉(zhuǎn)32.2 割平面法割平面法由高莫瑞(gomory)于1958年提出。其基本思想是放寬變量的整數(shù)約束，首先求對應(yīng)的松弛問題最優(yōu)解，當(dāng)某個變量不滿足整數(shù)約束時，尋找一個約束方程并添加到松弛問題中，其作用是割掉非整數(shù)部分，縮小原松弛問題的可行域，最后逼近整數(shù)問題的最優(yōu)解。增加的新約束稱為割平面方程或切割方程(1)設(shè)是相應(yīng)線性規(guī)劃最優(yōu)解中為分?jǐn)?shù)值的一個基變量，則由單純形表的最終表得到 ()(2)將拆分成整數(shù)部分n和非負(fù)真分?jǐn)?shù)之和，即： ()表示不超過的最大整數(shù)。將()式代入(1)式 （）其中，就是割平面方程的最基本形式。割

13、平面法解整數(shù)規(guī)劃問題的基本步驟第一步：用單純形法解松弛問題，得到最優(yōu)單純形表。第二步：求一個割平面方程，加到最優(yōu)單純形表中，用對偶單純形法繼續(xù)求解。第三步：若沒有得到整數(shù)最優(yōu)解，則繼續(xù)作割平面方程，轉(zhuǎn)第二步。3 整數(shù)規(guī)劃問題的應(yīng)用3.1在經(jīng)濟(jì)管理問題中的應(yīng)用3.1.1 投資問題設(shè)有個投資項目及年內(nèi)逐年投入資金矩陣，其中為第年的投資金額，以及投資矩陣，其中為第年項目所需投入資金。利潤矩陣，為項目的利潤。投資問題即在提供的資金的容許條件下，求利潤最高的投資決策。設(shè)則該問題的數(shù)學(xué)模型為：例1. 某公司在今后五年內(nèi)考慮給以下的項目投資。已知：項目a：從第一年到第四年每年年初可以投資，并于次年末回收本利

14、115%， 但第一年如果投資則最低金額為4萬元，第二、三、四年不限；項目b：第三年初可以投資，到第五年末能回收本利128，但規(guī)定最低投資金額為3萬元，最高金額為5萬元；項目 c：第二年初可以投資，到第五年末能回收本利140%，但規(guī)定其投資額或為2萬元或為4萬元或為6萬元或為8萬元。項目 d：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%，此項投資金額不限。 該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項目的每年投資額，使到第五年末擁有的資金本利總額為最大?解： 設(shè)分別表示第 年年初給項目a，b，c，d的投資額； 設(shè)是01變量 設(shè) 是非負(fù)整數(shù)變量，并規(guī)定：第2年投資c項目8萬元時，取值為4；

15、第 2年投資c項目6萬元時，取值3；第2年投資c項目4萬元時，取值2；第2年投資c項目2萬元時，取值1；第2年不投資c項目時，取值0；目標(biāo)函數(shù)及模型：3.1.2 生產(chǎn)安排問題（1） 靜態(tài)生產(chǎn)安排問題設(shè)有個生產(chǎn)行業(yè)，都需要某種資源。對于第個生產(chǎn)行業(yè)，如果用第種資源生產(chǎn)，可獲得的利潤為.若第種資源的單位價格為，現(xiàn)有資金。問應(yīng)購買第中資源多少單位，分配到個生產(chǎn)行業(yè)，使總利潤最大？此題的數(shù)學(xué)模型為：例2. 有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費用及售價、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費用見表3-1。要求制訂一個生產(chǎn)計劃，使總收益最大。表3-1 資源量、產(chǎn)品單件可變費用及售價、資源單耗

16、量及組織三種產(chǎn)品生產(chǎn)的固定費用資源單耗量產(chǎn)品資源量a248500b234300c123100單件可變費用456固定費用100150200單件售價81012解：設(shè)是第種產(chǎn)品的產(chǎn)量，再設(shè)則問題的整數(shù)規(guī)劃模型是（2） 動態(tài)生產(chǎn)安排問題設(shè)某公司對某種產(chǎn)品要制定一項個階段的生產(chǎn)（或購買）計劃。已知它的初始庫存量為零，每階段生產(chǎn)（或購買）該產(chǎn)品的數(shù)量有上限的限制；每階段社會對該產(chǎn)品的需求量是已知的，公司保證供應(yīng)；在階段末的終結(jié)庫存量為零。問該公司如何制定每個階段的生產(chǎn)（或購買）計劃，從而使總成本最小。設(shè)為第階段對產(chǎn)品的需求量，為第階段該產(chǎn)品的生產(chǎn)量（或采購量），為第階段結(jié)束時的產(chǎn)品庫存量，則有以表示第階段

17、生產(chǎn)產(chǎn)品時的成本費用，它包括生產(chǎn)準(zhǔn)備成本和產(chǎn)品成本（其中是單位產(chǎn)品成本）兩項費用。即：其中表示每階段最多能生產(chǎn)該產(chǎn)品的上限數(shù)。用表示第階段結(jié)束時庫存量為時所需的存儲費用，故第階段的成本費用為。因而，上述問題的數(shù)學(xué)模型為：例3某柴油機(jī)廠接到今年1至4季度柴油機(jī)生產(chǎn)訂單分別為：3000臺，4500臺，3500臺，5000臺。該廠每季度正常生產(chǎn)量為3000臺，若加班可多生產(chǎn)1500臺。正常生產(chǎn)成本為每臺5000元，加班生產(chǎn)還要追加成本每臺1500元。庫存成本為每臺每季度200元，問該柴油機(jī)廠該如何組織生產(chǎn)才能使生產(chǎn)成本最低？解： 設(shè)為第個季度正常生產(chǎn)的柴油機(jī)臺數(shù)，為第個季度加班生產(chǎn)的柴油機(jī)臺數(shù)，為第

18、個季度初的庫存量。第一季度初期及年底的庫存量均為零，若記為第個季度的需求量；分別為正常生產(chǎn)、加班生產(chǎn)、庫存（每季度）每臺柴油機(jī)的成本。則該問題的數(shù)學(xué)模型為：代入具體數(shù)據(jù)，3.1.3 下料問題制造某種產(chǎn)品，需要中軸件，其長度分別為。各類軸件都用長為的同一種圓鋼下料。設(shè)長度為的軸件需要量為，問最少要用多少根圓鋼？用非負(fù)的整數(shù)向量表示第種下料方式，其中表示下料長度為的軸件的數(shù)量，記所有下料方式的下標(biāo)集合為，則對，下料方式滿足：設(shè)采用第種下料方式的圓鋼數(shù)目為，則問題數(shù)學(xué)模型為例4 制造某種機(jī)床，需要a，b，c三種軸件，其規(guī)格與數(shù)量如表3-2所示。各類軸件都用5.5m長的同一種圓鋼下料。若計劃生產(chǎn)100

19、臺機(jī)床，最少要用多少根圓鋼？表3-2 軸件規(guī)格及數(shù)量軸類規(guī)格：長度（m）每臺機(jī)床所需軸件數(shù)a3.11b2.12c1.24依據(jù)問題，若直接以要用的圓鋼書作為決策變量，則建模變得很困難。所以避免直接由題意建模，先進(jìn)行分析，實際問題抽象成線性規(guī)劃的數(shù)學(xué)模型經(jīng)常要進(jìn)行轉(zhuǎn)化。首先考慮一根長5.5m的圓鋼截成a，b，c三種軸的毛坯有哪些具體下料方式。為次，只需找出全部省料截法，如下所示余料的各種截法，其中1.2m是各類軸件中最短者。一根圓鋼所截各類軸件數(shù)軸件需數(shù)量12345a(3.1)11000100b(2.1)10210200c(1.2)02124400余料0,300.110.7現(xiàn)在問題歸結(jié)為：常用上述

20、5種截法用多少根圓鋼，才能配成100套軸件，且使總下料根數(shù)最少？設(shè)按第種截法下料根。這樣就可以建立該問題的lp模型為3.2 在指派問題中的應(yīng)用 在實際中經(jīng)常會遇到這樣的問題，有項不同的任務(wù)，需要 個人分別完成其中的一項，但由于任務(wù)的性質(zhì)和各人的專長不同，因此各人去完成不同的任務(wù)的效率（或花費的時間或費用）也就不同。于是產(chǎn)生了一個問題，應(yīng)指派哪個人去完成哪項任務(wù)，使完成項任務(wù)的總效率最高（或所需時間最少），這類問題稱為指派問題或分派問題(assignment problem)。3.2.1 平衡指派問題在指派問題中，如果，擬每人做一件工作，且每件工作一個人做。這樣的指派問題稱為平衡指派問題。這類問

21、題的提法如下：現(xiàn)有項工作分配個工人去完成，已知工人完成工作需要花費時間。要求每項工作只能由一個工人去完成，每個工人只能完成一項工作。應(yīng)如何分工，使總工時最少？為了建立平衡指派問題的數(shù)學(xué)模型，引入個0-1變量： 這樣，問題的數(shù)學(xué)模型可寫成 （）s.t. 其中，表示每件事必有且只有一個人去做，表示每個人必做且只做一件事。滿足約束條件、的可行解也可寫成表格或矩陣形式，稱為解矩陣。例5. 某游泳隊擬選用a、b、c、d四名運(yùn)動員組成一個4×100混合游泳接力隊，參加運(yùn)動會，他們的100m自由泳，蛙泳，蝶泳，仰泳的成績?nèi)绫?-3，如何安排游泳才能最大可能得取得好成績？ 表3-3 四名運(yùn)動員100

22、m自由泳，蛙泳，蝶泳，仰泳的成績表姿勢隊員自由泳蛙泳蝶泳仰泳a56746163b63696571c57776367d55766262解: 引入01變量，并令 可以表示為一個0-1整數(shù)規(guī)劃問題：3.2.2 不平衡指派問題如果，即人數(shù)和任務(wù)數(shù)不等的情況，該類問題稱為不平衡指派問題。下面給出不平衡指派問題的兩種情形及數(shù)學(xué)模型：情形1：當(dāng)人員數(shù)少于任務(wù)數(shù)時，出現(xiàn)部分人員將承擔(dān)多項任務(wù)；情形2：當(dāng)人員數(shù)多于任務(wù)數(shù)（時，出現(xiàn)部分人員將無任務(wù)承擔(dān)；針對情形1、2的指派問題，令：1. 當(dāng)時 （3.2.2-1）s.t.注：表示每個人員最少承擔(dān)一項任務(wù)；表示每項任務(wù)都有一個人員承擔(dān)，并只有一個人員承擔(dān)；特別地，當(dāng)

23、人員有任務(wù)承擔(dān)量約束時，對上式中的條件（）加強(qiáng)。若每個人員承擔(dān)的任務(wù)數(shù)有限制，設(shè)每個人員的任務(wù)承擔(dān)量分別為，則約束條件加強(qiáng)為：s.t.此時，問題的模型為對于該類問題的求解，若每每個人員的任務(wù)承擔(dān)量為無窮大，則項余下的任務(wù)肯定分別由完成這些任務(wù)時間最少的人來完成，才能使目標(biāo)函數(shù)最優(yōu)，通過添加個虛擬人員，且這些虛擬人員完成各項任務(wù)的時間設(shè)為完成此項任務(wù)的實質(zhì)人員中的最小時間，進(jìn)而轉(zhuǎn)化為標(biāo)準(zhǔn)的指派問題：s.t.2. 當(dāng)時：s.t.注：表示每項任務(wù)均有且只有一個人員承擔(dān)；表示可能有部分人員無任務(wù)承擔(dān)；3.2.3 非確定型指派問題在實際應(yīng)用中，平衡指派問題帶有很大的局限性。對于從事工作的人來說，由于工作

24、的難以程度及個人完成工作的效率不同，所以不同的人在規(guī)定時間內(nèi)完成工作的件數(shù)也不相同。例如在學(xué)校排課時，由于學(xué)習(xí)每門課的班數(shù)較多，所以每門課的任課教師可能多于一個，且每學(xué)科的任課教師的任課門數(shù)也不一定就是一門（包括重復(fù)上同一門課）。這類指派問題可以描述為：有項工作，可以安排個人去完成，第個人至少可以承擔(dān)項，最多可承擔(dān)項工作；而第項工作可以由個人來完成。第個人完成第項工作的效率為，給出指派方案，使完成項工作的總效率最高。以上指派問題，可以用下面的數(shù)學(xué)模型來描述：其中表示第個人完成第項工作的件數(shù)（第項工作需要個人完成，可以把第項工作看成分為件工作）。模型中，1式要求完成工作的成本、時間等為極小值（若

25、是效率、產(chǎn)值、效益等時應(yīng)取極大值）；2式表示第項工作同時需要個人來完成；3式表示第個人至少可以同時完成件，最多可以同時完成件工作；4式表示完成項工作需要的總?cè)藬?shù)介于個人可以同時完成的最少工作量和最大工作量之間。由于每個人完成的工作量都是不確定的，所以我們稱上面的模型為不確定型指派問題為了求解上述問題，我們將問題進(jìn)行轉(zhuǎn)換，借助平衡指派問題，所有的數(shù)據(jù)和已知情況如表3-4所示：表3-4 人員及其可完成工作數(shù)據(jù)表工作人員至少從事工作件數(shù)最多從事工作件數(shù)需要人數(shù)m n2 n2則原問題的指派矩陣為：為了能用平衡指派問題的方法求解，我們可以將問題進(jìn)行轉(zhuǎn)換：因為項工作中，每項工作都必須由個人完成，所以我們將

26、其看成為有件工作，一共就有件工作；而個人每人至少做件，最多做件工作，即至少要做，最多要做件工作，所以我們假設(shè)最多有個人。因為，我們再假設(shè)有件虛擬工作，則所給問題就可以轉(zhuǎn)化為有件工作，每件工作必須且只須由一個人來做，有個人，每人必須且只須做一件工作的平衡指派問題。為了保證第個人至少完成件工作，所以當(dāng)把第個人要完成的件工作看成有個人時，前個人從事虛擬工作的效率，當(dāng)問題求最小值時取n（n為非常大的整數(shù)），當(dāng)問題求最大值是取0。此時，新的指派矩陣為：對于變化后的指派問題矩陣，利用解傳統(tǒng)指派問題的匈牙利法可求問題德法爾最優(yōu)解。3.3 在組合優(yōu)化方面的應(yīng)用在有限個可行解的集合中找出最優(yōu)解的一類優(yōu)化問題稱為

27、組合優(yōu)化問題。它是運(yùn)籌學(xué)的一個重要分支，所研究的問題涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、通訊網(wǎng)絡(luò)等諸多領(lǐng)域。3.3.1 一維背包問題設(shè)有一背包，其可攜帶物品重量的限度為。設(shè)有種不同的物品可供他選擇裝入背包中，已知第種物品的重量為，單位價值為（）。問此人應(yīng)如何選擇攜帶物品的方案，使總價值最大？設(shè)為第種物品的裝入件數(shù)，則問題的數(shù)學(xué)模型是例6. 一個登山隊員，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相器材、通信器材等。每種物品的重量合重要性系數(shù)如表3-5所示。設(shè)登山隊員可攜帶的最大重量為25kg,試選擇該隊員所應(yīng)攜帶的物品。表3-5 每種物品的重量合重要性系數(shù) 序號1234567

28、物品食品氧氣冰鎬繩索帳篷照相器材通信設(shè)備重量/kg55261224重要性系數(shù)201518148410解：引入01變量其數(shù)學(xué)模型為：上述問題就是一個標(biāo)準(zhǔn)的整數(shù)規(guī)劃問題.3.3.2 選址問題選址問題的基本提法如下：某機(jī)構(gòu)擬在個被服務(wù)點所在城市中建立 個服務(wù)中心，每個城市最多建立一個服務(wù)中心。若在第個城市建立服務(wù)中心，其服務(wù)能力為，單位時間的固定成本為，第 j 個被服務(wù)點的需求量為。從第個服務(wù)中心到第個被服務(wù)點的單位運(yùn)輸成本為。應(yīng)如何選擇服務(wù)中心位置和安排運(yùn)輸計劃，才能得到經(jīng)濟(jì)上花費最少的方案。 設(shè)在單位時間內(nèi)，從配貨中心運(yùn)往連鎖店的物資數(shù)量為， 為單位時間內(nèi)的總費用。引入變量則上述問題可歸結(jié)為如下

29、的數(shù)學(xué)模型：這是一個混合 規(guī)劃問題例7某企業(yè)在地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為 30 千箱，為了擴(kuò)大生產(chǎn)，打算在地中再選擇幾個地方建廠。已知在地建廠的固定成本分別為175千元、300千元、375千元、500千元，另外，產(chǎn)量及建成廠的產(chǎn)量，那時銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(每千箱運(yùn)費)如表3-6所示。 問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費用之和最小?表3-6 銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價銷地產(chǎn)地產(chǎn)量（千噸）84330523104342097530104240銷量（千噸）302020解： 設(shè)為從運(yùn)往的運(yùn)輸量(單位千箱)此時,該問題可以表示為一個整

30、數(shù)規(guī)劃問題：（其中前4項為固定投資額，后面的項為運(yùn)輸費用）約束條件為：3.4 在集合劃分問題中的應(yīng)用集合劃分問題是m.r garey和d.s johnson在1979年提出的6個基本np完全問題之一。最簡單的集合劃分問題是將個正整數(shù)組成的集合a劃分成兩個子集，使兩個子集的元素之和盡可能的接近。更廣泛的情況是將這個正數(shù)劃分到個互不相交的子集中，使各個子集元素之和盡可能相等。集合劃分問題的另一種提法為：把個正數(shù)組成的集合劃分成個互不相交的子集中，使得這些子集各個元素之和中最大者盡可能小?？梢宰C明，兩者定義是等價的。引人0-1變量：它的數(shù)學(xué)模型可以表示為：其中，是集合a中的第個元素。集合劃分問題應(yīng)用

31、很廣泛，如處理調(diào)度問題，存儲分配問題等。3.4.1 中心覆蓋問題 設(shè)某地區(qū)劃分為若干個區(qū)域，需要建立若干個應(yīng)急服務(wù)中心（如消防站、急救中心等），每個中心的建立都需要一筆建站費用，設(shè)候選中心的位置已知，每個中心可以服務(wù)的區(qū)域預(yù)先知道，問如何選取中心使該應(yīng)急服務(wù)能覆蓋整個地區(qū)且使建站費用最小。記為該地區(qū)中的區(qū)域，是可選的中心，設(shè)為中心可以服務(wù)的區(qū)域集合，是中心的建站費用，定義0-1關(guān)聯(lián)矩陣，其中，如果，否則。設(shè)則問題可以表示為：例8. 該城市共有6個區(qū)域，每個區(qū)都可以建消防站，市政府希望設(shè)置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時，消防車要在15min內(nèi)趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間消防車

32、行駛時間見表3-7，請幫助該市制定一個布點最少的計劃。解 引入變量作決策變量，令表示在地區(qū)設(shè)消防站；表示在地區(qū)不設(shè)消防站。表3-7 消防車在各區(qū)間行駛時間表 單位 min地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6010162827201002432171016240122721283212015252717271501420102125140本問題的目標(biāo)是本問題的約束方程是要保證每個地區(qū)都有一個消防站在15分鐘行程內(nèi)。如地區(qū)1，有表#可知，在地區(qū)1及地區(qū)2內(nèi)設(shè)消防站都能達(dá)到要求，即因此本問題的數(shù)學(xué)模型為：3.4.2 旅行商問題(tsp)設(shè)有一個旅行售貨員需要去個城

33、市推銷他的產(chǎn)品，他必須而且只能訪問每個城市一次，并最后返回出發(fā)城市。設(shè)每個城市直接到達(dá)另一個城市的距離已知（如不能直接到達(dá)，則可設(shè)其距離為），他應(yīng)該如何選擇旅行路線使得總的旅行距離最短？設(shè)城市到城市的距離為。設(shè)約束條件：他離開城市一次：他離開城市一次：上面的約束條件使得每個城市正好經(jīng)過一次，但仍可能包括含圈但不聯(lián)通的路線，我們需要用下面的約束條件來去除這種情況發(fā)生：或從而旅行售貨員問題可以表示為結(jié)論本文在整數(shù)規(guī)劃的理論基礎(chǔ)上歸納總結(jié)出若干整數(shù)規(guī)劃問題并給出了相應(yīng)的解答方法，主要涉及一下幾個方面：（1）在經(jīng)濟(jì)管理問題中的應(yīng)用。探討了投資問題、生產(chǎn)安排問題和下料問題；（2）在指派問題中的應(yīng)用。探討了平衡指派問題、不平衡指派問題及非確定性指派問題；（3）在組合優(yōu)化方面的應(yīng)用。探討了一維背包問題和選址問題；