（inregre linear progemming）
§1 整數規劃特點及應用
前面討論的lp的最優解可能是分數或小數。但是在經濟管理和工程實踐中，常常會出現要求變數值取整數的現象。如決策變數是機器台數、人數或車輛數等。
最初有些人認為：只要對非整數解「捨入取整」即可。但後來發現這是不行的。
因為捨入取整後的解不見得是可行解，即使是可行解，也不一定是最優整數解。因此，這裡另設一章，研究此問題，並稱這種求整數最優解的lp問題為整數線性規劃，簡記為「ilp」。
整數規劃分為許多態別：通常把所有變數都要求取整數的整數規劃，稱其為全（純）整數規劃；把部分變數要求取整數的整數規劃，稱為混合型ilp。把所有變數取值均為0或1的整數規劃稱為0-1規劃。
等等。求解整數規劃的一種簡單方法是：先不考慮整數條件，直接求解相應的線性規劃問題，當最優解為非整數且數值都較大時，把非整數最優解取整到最接近的整數可行解即可。但是，當最優解為非整數且數值都較小時，這種捨入化整的辦可能導致解的可行性被破壞。
例如，我們來研究下面整數規劃問題。
例4-1求解下面ilp問題： 相應的lp：
解：若先不考慮整數約束條件求解相應的lp問題，由**法得可行域如圖4-1。最優解x*=（3.25，2.5）。
所謂整數解，即要求變數取整數值。而由x*捨入化整得到的解，如（4，3）或（4，2）或（3，3）都不在可行域上，所以都不是可行解，而（3，2）雖是可行解，但它並不是最優整數解，因為該例有乙個可行解x=（4，1），其目標值z=14，大於可行解（3，2）的目標值13。
為了求得該整數規劃的最優整數解，我們將經過b點的目標函式等值線向可行域內平行移動，首次碰到的整數點即為所求。在本例中，最優整數解點就是（4，1）相應的z=14。本例說明，在一般情況下，企圖用捨入化整的辦法直接得到最優整數解是不可取的，必須專門研究其解法。
促使人們研究整數規劃還有其他原因，就是整數規劃模型，還能為處理某些特殊問題提供一種很好的方法，因為有些問題不利用整數規劃就很難處理。例如，投資工作中的許多決策問題，還有資源分配問題中，有多重約束條件的選擇問題，等等。都屬於這種情況。
下面我們就用例子來說明整數規劃模型的應用。
例4-2 試利用0-1變數將下列各題分別表示成一般線性約束條件。
（1） x1+x2 ≤ 2 或 2x1+3x2 ≥ 5
（2） 變數x只能取值0、3、5或7中的乙個
（3） 若x1≤2，則x2≥1，否則x2≤4
（4） 以下四個約束條件中至少滿足兩個：
x1+x2≤5，x1≤2，x3≥2，x3+x4≥6
解：（1）設
（2）（3）（4） 設則
下面看乙個實際問題。假定某化工廠有兩條生產線a1和a2均可用來生產三種化肥b1，b2，b3。用a1生產1噸b1，b2，b3分別需要5，7，6小時，用a2生產1噸b1，b2，b3分別需要4，5，3小時。
a1和a2分別有200，300小時可供利用。該廠決定只用兩條生產線中的一條生產，但用哪條生產線生產尚未決定。
若設該廠生產b1，b2，b3種化肥分別為x1，x2，x3噸。則依題意，必須滿足下面兩個約束條件之一：
5x+7x+6x≤200
4x+5x+3x≤300
這種情況就類似上面的例題，需要設乙個0-1變數處理。比如設
設上面兩個約束條件可表示為
5x+7x+6x≤200+my (m為任意大的正數)
4x+5x+3x≤300+m（1-y）
y=0或1
若y=0，則上面第乙個約束條件有效，而第二個約束條件是多餘的; 若y=1，則上面第二個約束條件有效，而第乙個約束條件是多餘的。這種結果還可以推廣到一般情況，假定在某一問題中有m個約束條件：
其中只有k個必須滿足，但事先並不知道是哪k個。
這是可設k個0-1變數
並將上面m個約束條件表示為下面的約束即可。
例4-3設某國際巧克力公司生產兩種產品，朱古力和朱爾斯，其相關資料如下：
可以利用的有限資源：機器工時700；直接人工工時5000。求產品如何組合才能使公司的效益達到最大。
解：設利潤為y，產品朱古力和朱爾斯的產量分別為x1 x2
max y=1.00x1+2.00x2
s.t 0.02x1 + 0.05x2<=700
0.20x1 + 0.25x2<=5000
x1 ,x2 >= 0, 且為整數
例4-4 有n個工廠擬在n個不同的廠址上建設。已知從i廠到j廠的物資運量為di j，又知從p廠址到q廠址單位物資的運費為cpq。試將這個問題歸結成乙個整數規劃模型，目標是使總運費為最少。
解：設則此問題的模型為：
例4-5某鑽井隊要從以下10個可供選擇的井位中確定5個鑽井探油，目標是使總的鑽探費用最小。若10個井位的代號為s1，s2，s3，s4，s5，s6，s7，s8，s9，s10，相應的鑽探費用為c1，c2，c3，c4，c5，c6，c7，c8，c9，c10，並且井位的選擇上要滿足下列條件：
（1） 或選擇s1和s7，或選擇鑽探s8；
（2） 選擇了s3或s4，就不能選擇s5，反過來也一樣；
（3） 在s2、s6、s9、s10中最多只能選擇兩個
試建立這個問題的數學模型。
解： 例4-6 某廠需生產2000件產品，該產品可利用a、b、c裝置中的任意一種（或兩種或三種）裝置加工。已知每種裝置的生產準備費用、生產該產品時的單位成本以及每種裝置限定的最大加工數量如下表所示，試建立使總費用最小的生產計畫問題數學模型。
解：用j=1，2，3表示a、b、c三種裝置，xj表示在裝置j上加工的產品數量，再設
則有§2 分枝定界法*
分枝定界法是求解混合整數規劃與純整數規劃的一種常用的有效方法，多數求解ilp的軟體也是用分枝定界法編寫的。
分枝定界法的思想是先不考慮整數約束條件，直接求解其相應的lp（又稱其為鬆弛問題）。若相應的lp的最優解不是整數解，則由其最優目標函式值可確定出原ilp目標函式的上（下）界，稱此為定界。然後增加約束條件把原ilp分成兩個子問題，稱其為分枝。
接下來求解子問題，由此，不斷縮小原ilp目標函式的上界，直至求出最優整數解或判斷出無解為止。
下面我們通過例子來說明分枝定界法的具體求解過程。
例4-6 用分枝定界法求解上節中例1-1問題。
解：1、先不考慮整數約束條件，用**法求得相應lp的最優解為：
x*=（3.25，2.5），z*=14.75
因為lp可行域上所有整數點是原ilp的全部可行解，所以原ilp的最優解應在這些整數點當中。
上面求出lp的最優解x*雖不是整數解，但由圖可知，z*是原ilp目標值的上界。這是因為ilp的全部可行解（即可行域上全部整數點）的目標函式值都不會超過z*。所以稱這一步為定界。
2、分枝
在ilp中，x1，x2要求取整數值。若x2取整數值，就要在x2≤2或x2≥3中取值，為此，我們將x2≤2和x2≥3分別加入原ilp中，將ilp分成兩個子問題。即
ilp1ilp2：
顯然這兩個子問題把lp的可行域劃分成部分，但是，這樣劃分，並未丟掉原ilp的可行解。我們稱這一劃分過程為分枝。
因為ilp1和ilp2的全部整數可行解仍包含ilp的全部可行解，所以我們可通過求解ilp1和ilp2的鬆弛問題lp1和lp2來尋找原ilp的最優整數解，於是由**法得：
lp1的x1*=（3.5，2），z1*=14.5
lp2的x2*=（2.5，3），z2*=13.5
3、修改原ilp目標函式值的上界
由lp1和lp2的最優目標函式值z1*和z2*知，當x2≤2時，原ilp的目標值不會超過14.5；當x2≥3時，原ilp目標函式值不會超過13.5。
從而可知，在可行域上，無論x2取何整數值，原ilp的目標值均不會超過14.5，於是我們應把前面確定的目標值上界由14.75修改為14.
5。因為求解兩個子問題仍未得到原ilp的最優整數解，為此將新上界對應的ilp1再分枝。考慮到x1*=（3.5，2）中x1=3.
5仍非整數，不合要求，再把x1≤3或x1≥4分別加入ilp1中，將ilp1分成兩個子問題如下：
ilp3ilp4：
顯然子問題ilp3和ilp4的整數可行解中包含了ilp1中的全部整數可行解，因此我們可通過求解ilp3和ilp4的鬆弛問題lp3和lp4來尋找原ilp1的最優整數解，於是由**法得：
lp3的x3*=（3，2），z3*=13
lp4的x4*=（4，1），z4*=14
此結果表明，在lp1的可行域上，無論x1取何整數值，ilp1的最優目標值都不會超過z4*=14，而ilp2的目標值z2*=13.5也不超過14，所以可斷定原ilp的目標值不會超過14，為此我們再把原ilp的目標值上界修改為14。
由於lp4的x4*=（4，1）是整數解，且其z4*=14是原ilp目標值的上界，已經達到了最大值，因此可確定x4*=（4，1）就是原ilp的最優整數解，分枝計算結束。整個求解過程可用乙個樹形圖來表示：
x1≤3
lp1lp3)
第四章動態規劃
1 引言 1.1 動態規劃的發展及研究內容 動態規劃 dynamic programming 是運籌學的乙個分支，是求解決策過程 decision process 最優化的數學方法。20世紀50年代初r.e.bellman等人在研究多階段決策過程 multistep decision process...
第四章目標規劃
目標規劃 good programming，簡記為gp 是 性規劃的基礎上，為適應經濟管理中多目標決策的需要而逐步發展起來的乙個運籌學分支，是實行目標管理這種現代化管理技術的乙個有效工具.目標規劃的有關概念和模型最早在1961年由美國學者查恩斯 a.charnes 和庫伯 在他們合著的 管理模型和線...
第四章線性規劃
在企業的經營管理中，常常遇到如何在現有條件下，獲得最大經濟效益的諸多方面的具體問題，如如何磁品產量和質量的要求下，合理配置裝置，合理儲存備件，合理制定生產計畫，以及合理運輸 下料，正確決策 等等一系列優化生產組織與計畫管理的問題。被廣泛用來解決這類優化問題的重要工具之一就是線性規劃。由於它具有廣泛適...