.,1,運籌學OperationsResearch,陳志松Mob..,2,線性規劃及其基本理論,線性規劃概述線性規劃問題線性規劃數學模型一般模型標準模型線性規劃解的概念可行解、最優解基陣、基解、基可行解線性規劃的基本性質,.,3,線性規劃概述,線性規劃（LinearProgramming，簡記為LP）是運籌學中的一個最重要、應用最廣泛的分支。線性規劃及其通用解法-單純形法一般認為是美國學者丹捷格（G.Dantzig）在1947年研究美國空軍軍事規劃時提出的。蘇聯學者康托洛維奇在1939年解決工業生產組織與計劃問題時就提出類似線性規劃的模型及解法；康托洛維奇的工作當時沒有被重視，但直到1960年康托洛維奇再次發表最佳資源利用的經濟計算一書后，才受到重視。一些常見的帶有Spreadsheet的軟件，如：Excel、Lotus1-2-3等，均有內置的線性規劃求解功能。最優化問題求解軟件，如：Lindo、Lingo、Matlab等。,.,4,線性規劃問題提出,在生產管理和經營活動中經常會提出這樣一類問題：如何利用有限的人力、物力、財力等資源，取得最好的效果。例如：配載問題一交通工具，運輸幾種不同體積、重量的物資，如何裝配，所運的物資最多？下料問題用圓鋼制造長度不等的機軸，如何下料，所剩的余料最少？生產計劃問題企業生產A、B兩種電器產品，兩種產品的市場需求狀況可以確定，按當前的定價可確保所有產品均能銷售出去。企業可提供的兩種原材料和勞動時間的數量是有限的。產品A與產品B各應生產多少，可使企業總利潤最大?,.,5,線性規劃問題提出,上述這些問題有如下共同特點：問題解決要滿足一定條件，稱為約束條件；問題有多個滿足條件的解決方案；問題解決有明確的目標要求，對應不同方案有不同目標值，可表示成目標函數。,.,6,何謂線性規劃問題,最優化問題我們稱如下一般問題：“在一定約束條件下，求目標函數的最大或最小值”為最優化問題，用數學模型描述的最優化問題，稱為數學規劃問題。線性規劃問題在最優化問題中，如果約束條件與目標函數均是線性的，我們就稱之為線性規劃問題。,.,7,線性規劃問題的三個要素,決策變量決策問題待定的量值稱為決策變量。決策變量的取值有時要求非負。約束條件任何問題都是限定在一定的條件下求解，把各種限制條件表示為一組等式或不等式，稱之為約束條件。約束條件是決策方案可行的保障。LP的約束條件，都是決策變量的線性函數。目標函數衡量決策方案優劣的準則，如時間最省、利潤最大、成本最低。目標函數是決策變量的線性函數。有的目標要實現極大，有的則要求極小。,.,8,線性規劃數學模型,例生產計劃問題某廠生產甲乙兩種產品，各自的零部件分別在A、B車間生產，最后都需在C車間裝配，相關數據如表所示：問如何安排甲、乙兩產品的產量，使利潤為最大。,35,單位產品獲利,81236,123234,ABC,生產能力,工時單耗甲乙,產品車間,.,9,線性規劃數學模型,建立數學模型的步驟：Step1分析實際問題；Step2確定決策變量；Step3找出約束條件；Step4確定目標函數；Step5整理、寫出數學模型。,.,10,【例1.1】某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應量見下表：要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2)，求建造方案。,線性規劃問題舉例,.,11,【例1.2】最優生產計劃問題。某企業在計劃期內計劃生產甲、乙、丙三種產品。這些產品分別需要要在設備A、B上加工，需要消耗材料C、D，按工藝資料規定，單件產品在不同設備上加工及所需要的資源如表1.1所示。已知在計劃期內設備的加工能力各為200臺時，可供材料分別為360、300公斤；每生產一件甲、乙、丙三種產品，企業可獲得利潤分別為40、30、50元，假定市場需求無限制。企業決策者應如何安排生產計劃，使企業在計劃期內總的利潤收入最大？,線性規劃問題舉例,產品資源消耗表,.,12,【例1.3】某商場決定：營業員每周連續工作5天后連續休息2天，輪流休息。根據統計，商場每天需要的營業員如表1.2所示。,表1.2營業員需要量統計表,商場人力資源部應如何安排每天的上班人數，使商場總的營業員最少。,線性規劃問題舉例,.,13,【例1.4】合理用料問題。某汽車需要用甲、乙、丙三種規格的軸各一根，這些軸的規格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來做，圓鋼長度為4m。現在要制造1000輛汽車，最少要用多少圓鋼來生產這些軸？,線性規劃問題舉例,.,14,【解】這是一個條材下料問題，設切口寬度為零。設一根圓鋼切割成甲、乙、丙三種軸的根數分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y34表示，求這個不等式關于y1，y2，y3的非負整數解。象這樣的非負整數解共有10組，也就是有10種下料方式，如表1.3所示。,表13下料方案,.,15,設xj(j=1,2,10)為第j種下料方案所用圓鋼的根數。則用料最少數學模型為:,注意：（）求下料方案時應注意，余料不能超過最短毛坯的長度；（）最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案。（）如果方案較多，用計算機編程排方案，去掉余料較長的方案，進行初選。,.,16,【例1.5】配料問題。某鋼鐵公司生產一種合金，要求的成分規格是：錫不少于28%，鋅不多于15%，鉛恰好10%，鎳要界于35%55%之間，不允許有其他成分。鋼鐵公司擬從五種不同級別的礦石中進行冶煉，每種礦物的成分含量和價格如表1.4所示。礦石雜質在治煉過程中廢棄，現要求每噸合金成本最低的礦物數量。假設礦石在冶煉過程中，合金含量沒有發生變化。,表1.4礦石的金屬含量,線性規劃問題舉例,.,17,解:設xj（j=1,2，5）是第j種礦石數量，得到下列線性規劃模型,注意，礦石在實際冶煉時金屬含量會發生變化，建模時應將這種變化考慮進去，有可能是非線性關系。配料問題也稱配方問題、營養問題或混合問題，在許多行業生產中都能遇到。,.,18,【例1.6】投資問題。某投資公司在第一年有200萬元資金，每年都有如下的投資方案可供考慮采納：“假使第一年投入一筆資金，第二年又繼續投入此資金的50%，那么到第三年就可回收第一年投入資金的一倍金額”。投資公司決定最優的投資策略使第六年所掌握的資金最多。,線性規劃問題舉例,.,19,【例1.7】均衡配套生產問題。某產品由2件甲、3件乙零件組裝而成。兩種零件必須經過設備A、B上加工，每件甲零件在A、B上的加工時間分別為5分鐘和9分鐘，每件乙零件在A、B上的加工時間分別為4分鐘和10分鐘。現有2臺設備A和3臺設備B，每天可供加工時間為8小時。為了保持兩種設備均衡負荷生產，要求一種設備每天的加工總時間不超過另一種設備總時間1小時。怎樣安排設備的加工時間使每天產品的產量最大。,線性規劃問題舉例,.,20,線性規劃數學模型一般形式,假定線性規劃問題有n個決策變量，m個約束條件。一般地，線性規劃問題數學模型中可表示成如下形式：,.,21,線性規劃數學模型標準形式,線性規劃問題的數學模型有各種不同的形式，如目標函數有極大化和極小化；約束條件有“”、“”和“”三種情況；決策變量一般有非負性要求，有的則沒有。為了求解方便，特規定一種線性規劃的標準形式，非標準型可以轉化為標準型。標準形式為：目標函數極大化，約束條件為等式，右端常數項bi0，決策變量非負。,.,22,線性規劃數學模型標準形式,.,23,線性規劃數學模型標準形式,.,24,線性規劃數學模型標準形式,.,25,線性規劃數學模型標準形式,.,26,如何化線性規劃標準形式,.,27,如何化線性規劃標準形式,例1.8minz=x1+2x2-3x3x1+2x2-x352x1+3x2-x36-x1-x2+x3-2x10,x30,.,28,【例1.9】將下列線性規劃化為標準型,如何化線性規劃標準形式,.,29,如何化線性規劃標準形式,.,30,當某個變量xj0時,令x/j=xj。當某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束,將其化為兩個不等式,再加入松馳變量化為等式。,如何化線性規劃標準形式,.,31,線性規劃解的概念,可行解與可行域滿足約束條件（AX=b,X0）的X稱為線性規劃問題的可行解所有可行解的集合稱為可行域，記D=X|AX=b,X0。最優解使目標函數值達最大的可行解稱為線性規劃問題的最優解。若X*是最優解，則對任意的XD，恒有CX*CX。,.,32,線性規劃解的概念,基（基陣、基礎矩陣）,為mn維系數矩陣，秩為m。,稱系數矩陣A中m個線性獨立的列向量構成的矩陣B為線性規劃問題的一個基。矩陣B非奇異，|B|0，存在逆陣。,|B|0,B為非奇異子矩陣；,當m=n時，基矩陣唯一，當mn時，基矩陣就可能有多個，但數目不超過A中最多有,.,33,【例1.11】線性規劃,求所有基矩陣。,.,34,線性規劃基解的概念,基向量與非基向量系數矩陣A中構成基B的列向量稱為基向量。系數矩陣A中除基向量之外的列向量稱為基向量。A=(B,N)基變量與非基變量與基向量對應的變量稱為基變量。與非基向量對應的變量稱為非基變量。,.,35,在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量。基變量、非基變量是針對某一確定基而言的，不同的基對應的基變量和非基變量也不同。,線性規劃基解的概念,.,36,線性規劃基解的概念,基(礎)解基(礎)可行解滿足變量非負約束條件的基解，稱為線性規劃問題的基可行解。可行基與基可行解對應的基稱為可行基。,.,37,線性規劃解的關系,.,38,線性規劃的退化與非退化,一個基可行解，若其中所有基變量都取正值，則稱它是非退化的。一個基可行解，若其中有某一個基變量取零值，則稱它是退化的。一個線性規劃問題，若它的所有基可行解都是非退化的，則稱這個線性規劃問題是非退化的。,.,39,線性規劃基解求取,基解與基可行解是線性規劃的重要概念，求線性規劃的基解與基可行解是各類運籌學考試中的常考題。求線性規劃的基解與基可行解時，首先要先化標準形，然后根據概念求解。例選擇不同基，求如下LP的基解和基可行解：maxz=x1+4x2x1+x2+x3=4-x1+x2+x4=2x1，x2，x3，x40,.,40,凸集、凸組合、頂點（極點）,凸集凸組合,.,41,頂點(極點)設K是凸集，若X不能用K中兩個不同的點的凸組合表示為,則稱X是K的一個頂點或極點。,X是凸集K的極點即X不可能是K中某一線段的內點，只能是K中某一線段的端點。,O,凸集、凸組合、頂點（極點）,.,42,線性規劃的基本性質,定理1若線性規劃問題存在可行域，則其可行域一定是凸集。引理線性規劃問題的可行解X=(x1,x2,xn)T為基可行解的充要條件是X的正分量對應的系數列向量