在企業的經營管理中，常常遇到如何在現有條件下，獲得最大經濟效益的諸多方面的具體問題，如如何磁品產量和質量的要求下，合理配置裝置，合理儲存備件，合理制定生產計畫，以及合理運輸、下料，正確決策……等等一系列優化生產組織與計畫管理的問題。被廣泛用來解決這類優化問題的重要工具之一就是線性規劃。由於它具有廣泛適應性，已成為當前應用極廣的現代管理方法。
第一節線性規劃的基本概念
一、例4.1：裝置配置問題
某車間生產a、b、c三種產品，需要配置有關裝置。各種資料列於表4.1中。
表4.1
要求在保證完成每天生產任務的前提下，合理確定甲、乙裝置的台數，使每天的運轉費最低。
顯然，這是乙個求滿足一定條件（每天的最低產量）下的最小值（運轉費最小）問題。解決這一問題的基本思路是：先假設所需配置的甲、乙裝置的台數分別是x1臺和x2臺，然後尋找滿足題意的x1、x2的範圍，並逐步縮小，最後找出條例題意的x1、x2的具體數值。
由於每台甲裝置每天能生產9件a產品，每台乙裝置每天能生產3件a產品，因此當甲乙裝置分別配置x1和x2台時，則每天能生產a產品為9x1+3x2。題目要求這一產量每天至少18件，當然可以多一於這一產量。也就是說，由於a產品每天產量的要求，必須使配置的甲、乙裝置的台數x1和x2滿足下述不等式：
9x1+3x2＞18 a產品產量的要求 (4,1)
同理可得:
3x1+3x2＞12 b產品產量的要求 (4,2)
6x1+18x2＞36 c產品產量的要求 (4,3)
同時滿足上述三個不等式的非負的x1和x2(因為裝置台數不能為負數)，一般來說有無窮多個組合，例如x1=2，x2=3；或x1=3，x2=2；……等等都同時滿足上述三個不等式。這三個不等式組稱為約束條件。於是題目要求：
在保證完成每天生產任務的前提下，合理確定甲乙裝置的台數x1，x2，使每天的運轉費最低。在這時就轉換成在同時滿足約束條件（4，1）、（4，2）、（4，3）個不等式的無窮多個非負的x1和x2的組合中，選定一組確定的值，使每天運轉費之和s為最低。即使s=800x1+640x2為最低。
通常寫成：
使得 mins(x1,x2)=800x1+640x24,4)
(4,4)式是目標值的計算公式，稱為目標函式。
把上述分析歸納到一起，並將其寫成簡鍊的數學表示式就是：
設x1、x2分別為甲乙裝置的配置台數，求x1，x2
滿足：約束條件
x1≥0，x2≥0 非負要求
使得mins(x1,x2)=800x1+640x2
上述數學表示式簡鍊地表達了題目的全部含義，稱為此問題的線性規劃模型。
二、線性規劃模型的特點
1.求解問題有明確的目標，而且目標值能表示成求未知變數（決策變數）x1，x2……xn的線性函式（目標函式）的極大值或極小值。如（4，4）式所示。
並要求這些未知變數xi的取值都是非負的。一般實際問題都能滿足這一要求。本例的裝置台數顯然不能是負值。
2.求解問題的目標同時受到多種限制條件的約束，且這些約束條件都能表示成線性等式或不等式，稱為約束函式，如（4，1）、（4，2）、（4，3）式所示。所謂性線是指無論目標函式或約束函式都是xi的一次函式，在平面直角座標系中它們是一根直線，所以稱為線性規劃。
3.通常同時滿足所有約束條件的非負未知變數x1，x2，……xn有無窮多組，每一組表示乙個方案。即可從同時滿足所有約束條件下的無窮多個方案中來選擇達到目標極小值的方案。
概括起來，線性規劃就是求**性約束下的線性目標函式的極值問題的數學模型。它由未知變數x1，x2，……xn及線性約束函式和線性目標函式三部分組成。
第二節實際問題線性規劃模型舉例
應用線性規劃解決實際問題的通常步驟是：
1.選擇決策變數x1，x2，……xn。選擇原則是要便於寫出約束和目標函式。
2.確定目標函式。
3.寫出約束條件。
4.求解。
本節再通過例項，介紹如何按上述步驟，對實際問題進行分析後，建立其線性規劃模型。
例4.2：裝置安裝問題材
某廠要安裝a1，a2，……a3三颱裝置，可以安裝在b1，b2……b3三個不同地方，各台裝置安裝在各個地方的安裝費（單位：百元）如表4.2所示。應如何安裝才能使總的安裝費最省？
1.確定決策變數：此問題是求何裝置（a1、a2、a3）安裝在何處（b1、b2、b3）能使總安裝費最省。
為了清楚地表達上述兩個「何」字的確切含義，我們用帶有兩個下標的決策變數xij（i，j，=1，2，3）就表示裝置ai安裝在bj處，共有9個（參見後（4，5）式所示）。
2.確定目標函式：設總安裝費為s，安裝裝置a1、a2、a3的費用分別為s1、s2、s3，則：
s1=18x11+12x12+14x13。同理可得s2，s3，及s=s1+s2+s3 （見後（4，7）式所示）
表 4.2
3.寫出約束條件：
（1）xij含義的約束：當我們按上述規定選擇決策變數時，會發現x21，x22，x23都是表示裝置a2安裝地點，它們分別表示a2安裝在b1，b2，b3處。這是不可能的，因為裝置a2只有一台，只可能安裝在其中的某一處，因此可寫出約束條件為：
x21=1 當裝置a2安裝在b1處時
x21=0 當裝置a2不安裝在b1處時
類似地可寫出通式為：
xij=1 裝置ai安裝在bj處時 i，j=1，2，3；
xij=0 裝置ai不安裝在bj處時 i，j=1，2，3；
（2）由於裝置ai（i=1，2，3）均只有一台或者說裝置a1只能安裝在b1，b2，b3的某一處，故可寫出約束條件為：x11+x12+x13=1
通式： xi1+xi2+xi3=1 i=1，2，3； 見後（4，5）式。
（3）由於每處bj（j=1，2，3）都只能安裝一台裝置，故可寫出約束條件為：
x11+x23+x31=1 在b1處只能安裝其中一台
通式：x1j+x2j+x3j=1 j=1，2，3；見後（4，6）式所示。
4.綜上所述，此問題的線性規劃模型為：
設xij表示裝置ai安裝在bj處。求xij （i，j=1，2，3）
滿足約束：
xij=1 裝置ai安裝在bj處時 i，j=1，2，3；
xij=0 裝置ai不安裝在bj處時 i，j=1，2，3；
x11+x12+x13=1 x21+x22+x23=1 x31+x32+x33=14，5）
x11+x21+x31=1 x12+x22+x32=1 x13+x23+x33=14，6）
使得 mins=s1+s2+s3
=18x11+12x12+14x13+13x21+14x22+10x23+10x31+19x32+15x334，7）
例4.3：裝置維修問題
某修理車間有a、b、c三種型別的裝置，負責全廠甲乙兩種裝置的修理任務，各類裝置每月可能利用的工時數及修理一台裝置所需a、b、c三種裝置的加工時數見表4.3所示。應如何安排修理任務，才能使每月修理的臺數最多？
表4.3
不難寫出此問題的線性規劃模型為:
設每月修理甲乙裝置的台數分別為x1和x2臺,求x1,x2
滿足約束:
21x1+14x2≤126
12x1+12x2≤96
15x1+30x21≤50
x≥10, x≥20 (修理台數不能為負值)
使得 maxs=x1+x2 （s為修理總台數)
上面的問題較為簡單,在實際工作中,要建立乙個實際問題的線性規劃模型不僅涉及到技術經濟問題,而且也涉及到方針、政策問題，還要深入實際調查研究，抓住事物的主要矛盾進行簡化、抽象，才能建立乙個比較實用的模型。
第三節線性規劃的求解
寫出實際問題的線性規劃模型後，最終要解出決策變數xi和目標函式的具體數值。對於例4.1，求解後可得x1=1，x2=3，s=2720元。
這就是說當配置甲裝置一台，乙裝置三颱時，既能保證完成每天的生產任務，又能使每天的運轉費最低(2720元)。其它任何滿足約束條件的x1+x2的組合，每天的運轉費肯定高於這一數值。
求解線性規劃的方法很多，通常多用單純形法。但當決策變數xi較多時手算求解就很困難，好在當前在電子計算機上已有求解線性規劃的標準程式，正確寫出實際問題的線性規劃模型後，只需將有關引數輸入電子計算機，呼叫相應的標準程式，就可求出具體的解來。但為了幫助我們形象地理解為什麼通過解線性規劃能找出最優解來，以及如何尋找最優解，下面用**法解乙個例項。
**法解題的基本思路是：首先確定滿足約束條件的解的範圍（簡稱可行解域），然後在此範圍內尋求目標函式的最優解。
現以例4.1為例說明**法的解題步驟：
該線性規劃問題為：
求 x1，x2
滿足約束： 9x1+3x2＞181
3x1+3x2＞12 （2
6x1+18x2＞36 （3
x1＞04
x2＞05
使得s（x1，x2）=800x1+640x2 取得小值。 （6）
其中x1，x2分別為甲乙裝置的配置台數。
根據**法解題思路，解題步驟如下：
1.作圖求可行解域
第一步：將各約束不等式換為等式：
9x1+3x2=18 （1＇）
3x1+3x2=12 （2＇）
6x1+19x2=36 （3＇）
x1=0 （4＇）
x2=0 （5＇）
由（1＇）式有: x2=-3x1+6
這是一直線方程(見圖4.1），斜率k=-3，在x2軸上的截點為a（0，6），在x1軸上的截點為b（2，0）。連線a，b兩點的直線即為滿足方程（1＇）的直線。
而約束條件（1）則是以ab直線為界的右上半平面，在ab直線上以箭頭方向表示。
同理作出滿足約束條件（2），（3），（4），（5）的區域，見圖4.1。
第二步：根據約束不等式取值範圍，確定可行解域。
由圖可知，aghf的右上半平面是同時滿足所有的約束條件的區域（包括邊界，下同），就是此問題的可行解域。於是我們所要找的解，一定是上述可行解域中的某一點。這樣，問題化為在可行解域內尋找最優解，尋找範圍大為縮小，而且找了它的邊界。
約束條件在這裡表現出明顯的幾何意義。
2.從可行解域求最優解
由於最優解不僅與可行解域（約束條件）有關，而且與目標函式有關，因此求最優解時必須把兩者綜合起來進行分析。
將目標函式改寫成：
x2=-（800/640）x1+s（x1，x2）/640=-1.25x1+s（x1，x2）/640
由上式可知，當s（x1，x2）取某一定值時，它是一條斜率k=-1.25的確定的直線。當使s（x1，x2）取一組不同的值時，便得到一組相互平行的直線，稱為目標等值線（見圖4.
1虛線所示）。顯然，目標等值線在可行解域內的線段上的任意一點，都滿足約束條件，而且有確定的目標值。那麼目標函式的最小值點在哪一條等值線的哪一點呢？
由圖上可知，當目標等值線沿其垂線向左下方平行移動時目標值減少。因此，我們可設想有一條平行於目標等值線的動直線，沿其垂線向左下方平移，當移動到頂點g時，對應的目標值就是目標函式在可行解域上的最小值。因為再往左下方移動，雖然目標值還能減少，但該動直線卻全部處於可行解域外，即該動直線上沒有一點能滿足約束要求。
因此，上述頂點g（x1，x2）=g（1，3），就是目標函式最小值的最優頂點。
由於頂點g是直線9x1+3x2=18和直線3x1+3x2=12交點，所以解方程組：
9x1+3x2=18
3x1+3x2=12
便得到頂點g的座標為x1=1，x2=3；
頂點g所對應的目標函式值為：
s（x1，x2）=800x1+640x2=2720元
這就是說，最優的裝置配置是甲裝置一台，乙裝置三颱。任何其它的滿足每天生產任務的裝置配置，每天的運轉費都肯定高於這一數值。這從圖4.1上可以清楚地看出來。
第四章約束非線性規劃
4.3 可行方向法 作者 黃希勇 2013.5.28 引入 對於非線性規劃問題，如果不存在約束，從任乙個初始點出發，沿的負梯度方向進行一維收索，便可求得目標函式的無約束極小值 而對有約束的極小化問題來說，除要使目標函式在每次迭代有所下降之外，還要注意解的可行性問題，為此，在求解約束非線性規劃迭代法的...
第四章對偶線性規劃問題
1.略2.用對偶單純形方法解1.1 解 把問題標準化 即 1 作對應於對偶可行基的單純形表 2 因表中基變數值有負數，而且 2對應的行都有負數，所以要進行換基迭代。3 換基迭代 求軸心項 以基變數中 2對應的行中所有負數去除檢驗數，其中最小的商1所對應的除數 1就是軸心項。進行換基迭代得新基 因為表...
第四章整數規劃
inregre linear progemming 1 整數規劃特點及應用 前面討論的lp的最優解可能是分數或小數。但是在經濟管理和工程實踐中，常常會出現要求變數值取整數的現象。如決策變數是機器台數 人數或車輛數等。最初有些人認為 只要對非整數解 捨入取整 即可。但後來發現這是不行的。因為捨入取整後...