1、第一章 線性規(guī)劃基本性質 線性規(guī)劃主要用于研究解決有限資源的最佳分配問題，即如何對有限的資源做出最佳方式的調配和最有利的使用，以便最充分的發(fā)揮資源的效能去獲取最佳經濟效益。為敘述簡便，以后我們把“線性規(guī)劃”用LP代替 。 第一節(jié) 線性規(guī)劃的一般模型1.1 線性規(guī)劃問題之例1、產品配比問題（LP問題范例) 某廠擬生產甲乙兩種適銷產品，每件利潤為3,5百元。甲乙產品的部件各自在A,B兩個車間分別生產，每件甲乙產品的部件分別需要A,B車間的生產能力1,2工時；兩種產品的部件最后都要在C車間裝配，裝配每件甲乙產品分別需要3,4工時,A,B,C三個車間每天可用于生產這兩這種產品的工時分別為8,12,36

2、.應如何安排生產才能獲利最多？ 解：這是一個典型的產品配比問題，現(xiàn)在建立這個問題的數(shù)學模型。設 , 分別為甲、乙產品的日產量，z為這兩種產品每天總的利潤。 可得數(shù)學模型簡記為: 其中max是英文maximize(最大化)的縮寫；s.t.是subject to(受約束于)的縮寫。 2、 配料問題 某化工廠根據(jù)一合同要為用戶生產一種用甲,乙兩種原料混合配制而成的特殊產品。甲乙兩種原料都含有A,B,C三種化學成分，其含量(%)是:甲為12,2,3乙為3,3,15.按合同規(guī)定，產品中三種化學成分的含量(%)不得低于4,2,5。甲乙原料成本為每千克3,2元。廠方希望總成本達到最小,則應如何配制該產品？解

3、： 設每千克該產品用x1千克甲原料和x2千克乙原料配制而成，每千克產品成本為z元，可構成該例的數(shù)學模型：1.2 線性規(guī)劃的一般模型（1可用一些變量表示這類問題的待定方案，這些變量的一組定值就代表一個具體方案。因此可將這些變量稱為決策變量，并要求它們?yōu)榉秦?。?存在一定的約束條件，這些約束條件度能用關于決策變量的線性不等式或等式來表示。（3有一個期望達到的目標，這些目標能以某種確定的數(shù)量指標刻畫出來，而這種數(shù)量指標可表示為關于決策變量數(shù)，按所考慮問題的不同，要求該函數(shù)值最大化或最小化。這類問題就是線性規(guī)劃問題。一般LP模型可表示如下：其中opt是英文optimize(最優(yōu)化)的縮寫。按問題要求不

4、同，可表示為max或min。(1-1)式稱為最優(yōu)化目標函數(shù)，其中 稱為目標函數(shù)，opt稱為其優(yōu)化，也可稱為目標要求；(1-2)式稱為函數(shù)約束；(1-3)式中的 稱為非負性約束； 稱為非正性約束；(1-2)、(1-3)式統(tǒng)稱為約束條件，簡稱約束。 稱為決策變量。 稱為LP模型的參數(shù)。第二節(jié) 線性規(guī)劃的圖解法2.1 圖解法的基本步驟1、可行域圖形的確定。范例的非負性約束代表以 為橫軸、以 為縱軸的直角坐標系的第一象限，首先就要畫出它的圖形。范例的三個函數(shù)約束是：函數(shù)約束圖形如下： 區(qū)域OABCD(包括其邊界)上的每一點，都是范例的LP模型的一個解，一般稱為可行解。因此區(qū)域OABCD是該LP模型的解

5、集合，一般稱為可行域，通常簡記為R。2、目標函數(shù)的等值線與最優(yōu)點的確定。 考慮范例的目標函數(shù) 它代表以z為參數(shù)的一族平行線。 由小到大適當?shù)慕oz賦值，如令 可得到一組平行線，而位于同一直線上的點具有相同的目標函數(shù)值(z值)，因而稱為等值線。2.2 幾點說明 (1) 若函數(shù)約束原型就是等式，則其代表的區(qū)域僅為一直線，而且問題的整個可行域R也必然在此直線上。 (2) 在畫目標函數(shù)等值線時只須畫兩條就能確定其方向，為此只須賦給z兩個適當?shù)闹怠?(3) 在找出最優(yōu)點后，關于其坐標值有兩種確定方法：在圖上觀測最優(yōu)點坐標值；通過解方程組得出最優(yōu)點坐標值。 2.3 幾種可能結果 1 唯一解。僅有唯一最優(yōu)解。

6、 2 多重解。最優(yōu)解不唯一。 3 無界解。最優(yōu)解無界的LP問題。 例題 試用圖解法求下述LP問題： 4 無可行解。不存在可行點的LP問題第三節(jié) 線性規(guī)劃的標準形式3.1 線性規(guī)劃問題的標準形式一般LP問題的標準形為：或簡記為 還可以記為矩陣形式或集合形式其中 為約束方程組(1-5)的系數(shù)陣。即A為滿秩陣。稱m為LP問題(M1)的階數(shù),n為其維數(shù)。 規(guī)定右端常失 ,即b中的一切分量 一般稱C為價值向量，其每個分量 稱為價值系數(shù)。3.2 非標準形LP問題的標準化1 目標函數(shù)。如LP問題的目標函數(shù)是： 可以將原目標函數(shù)化為2 函數(shù)約束。 (1) 的情形。 (2) 約束為 形式的情形。 (3) 約束為

7、 形式的情形。3 決策變量 例題 將右側LP問題化成 標準形：第四節(jié) 線性規(guī)劃的解及其性質4.1 線性規(guī)劃的解的概念1 可行解。 滿足LP問題所有的約束條件的向量X稱為可行解，所有可行解構成的集合稱為可行域，記為R。2 最優(yōu)解。 滿足目標要求的可行解稱為最優(yōu)解，記為 ；它所對應的目標函數(shù)值稱為最優(yōu)值，記為 。有時把 統(tǒng)稱為最優(yōu)解，簡稱為解。3 基本解。就范例的 標準形進行研討：4 基本可行解。 滿足非負性約束(1-6)的基本解，稱為標準形LP問題(M)的基本可行解。若它是退化的,則稱為退化基本可行解。 把基本可行解對應的基稱為可行基,把最優(yōu)基本解對應的基稱為最優(yōu)基。 表 標準形LP問題解的概念

8、與關系 4.2 凸性的幾個基本概念 1 凸集。設 ,對任意兩點 ，如對滿足 的一切實數(shù) ，都有則稱S為凸集。 該定義的幾何意義是：n維空間 的一個子集S中的任意兩點連線上的一切點都在S中,則S為凸集。而線性組合 就代表兩點X與Y連線上的任一點 。 2 極點。設凸集 。如果X不能用S中的兩點Y和Z表示為則稱X為S的一個極點。 3 凸組合。設 ，實數(shù) 且 ,則稱 為點 的一個凸組合。4.3 線性規(guī)劃的解的性質 性質1 線性規(guī)劃問題（M）的可行域是凸集。 性質2 LP問題（M）的一個基本可行解與可行域R的一個極點互相對應。 性質3 線性規(guī)劃的基本定理 對于任何一個給定的標準形LP問題（M）來說： （

9、1）如（M）有可行解，則必有基本可行解； （2）如（M）有最優(yōu)解，則必有最優(yōu)可行解。 性質4 如LP問題的可行域 ，則R至少有一個極點。 性質5 LP問題可行域R的極點數(shù)目必為有限多個。第五節(jié) 線性規(guī)劃的應用模型 一般來說，一個經濟管理問題滿足以下條件時才能適用線性規(guī)劃模型： （1）實際問題所要求達到的目標能用數(shù)值指標的線性函數(shù)表示； （2）存在多種實現(xiàn)目標的可行方案； （3）要實現(xiàn)的目標受到一定條件的制約，而這些條件均能用線性方程（等式或不等式）描述。 對于經過概括，抽象而簡化了的實際問題，一般可按照1決策變量；2約束條件；3目標函數(shù)的次序，逐步建立其LP模型。5.1 生產計劃問題 一般生產

10、計劃問題可描述如下： 某企業(yè)擬用m種資源(用i=1,2, ,m表示)生產n種產品(用j=1,2, ,n表示)，已知第i種資源的數(shù)量為 ，其單價為 ，每生產一個單位第j種產品所提供的產值為 ，所消耗的第i種資源的數(shù)量為 。第j種產品的合同與指令行計劃的產量指標為 ，最高需求量為 。該企業(yè)應如何擬定生產計劃？解： 可得該問題的LP模型：顯然 ，故上述模型不必列出非負性約束 了。5.2 食譜問題 一般描述如下： 有n種食品，每種食品中含有m種營養(yǎng)成分。食品用j=1,2, ,n表示，養(yǎng)分用i=1,2, ,m表示。已知第j種食品單價為Cj，每天最大供量為dj；而每單位第j種食品中所含第i種養(yǎng)分的數(shù)量為a

11、ij；假定某種生物每天對第i種養(yǎng)分的需求量至少為bi，而每天進食數(shù)量限定在h1,h2范圍內。試求該生物的食譜，使總成本為最小? 則該LP問題的模型為:5.3 產品配套問題 一般產品配套問題可描述如下： 某廠用m種機床 加工制造n種零件 并用來組裝一種機器。組裝一臺機需要 個Bj零件(j=1,2, ,n)，機床Ai每個工作日可加工Bj零件aij個(i=1,2, ,m),應如何分配機床負荷才能使生產的機器最多? 設xij為機床Ai每天加工零件Bj的時間（單位:工作日），z為每個工作日按比例 加工出來的n種零件的套數(shù)。則該問題模型為:5.4 下料問題 一般下料問題可描述如下： 要用某原料(條材或板材

12、)下m種零件 的毛坯。根據(jù)既節(jié)省原材料又易于現(xiàn)場操作的原則，在一件原材料上已設計出m種不同的下料方式。其中第j種方式可下得Ai零件aij個(i=1,2, ,m；j=1,2, ,n) 。若Ai零件的需要量為bi (i=1,2, ,m )，則應如何下料，才能既滿足需要又使所用的原材料最少？ 設用第j種下料方式套裁原材料xj(j=1,2, ,n)件，所用原材料總數(shù)為z件。則該問題的LP模型為:5.5 配料問題 一般配料問題可描述如下： 要用n種原料 配制成具有m種成分 的某產品，規(guī)定每一單位產品中所含Bi成分的數(shù)量不低于bi(i=1,2, ,m)。原料Aj的單價為Cj，現(xiàn)有數(shù)量為dj，而每一單位Ai原料所含Bi成分的數(shù)量為aij。若要求配成的產品總量不低于e，則應如何配料，才能既能滿足需要又使總成本最低？ 設為配制該產品取用原料Aj的數(shù)量為xj，原料總成本為z，則問題的模型為 其中第一類約束條件是由 導出的。例題精選 1. 一家工廠制造三種產品，需要三種資源技術服務、勞動力和行政管理。下表列出了三種單位產品對每種資源的需要量。今有100小時的技術服務，600小時的勞動力和300小時