運籌學

OperationalResearch運籌帷幄，決勝千里

史記《張良傳》運籌學課件任課教師：楊艷梅緒論一、運籌學的起源與發展二、運籌學的特點及研究對象三、運籌學解決問題的方法步驟四、運籌學的發展趨勢一、運籌學的起源與發展起源于二次大戰的一門新興交叉學科與作戰問題相關如雷達的設置、運輸船隊的護航、反潛作戰中深水炸彈的深度、飛行員的編組、軍事物資的存儲等英國稱為OperationalResearch美國稱為OperationsResearch戰后在經濟、管理和機關學校及科研單位繼續研究1952年，Morse和Kimball出版《運籌學方法》1948年英國首先成立運籌學會1952年美國成立運籌學會1959年成立國際運籌學聯合會(IFORS)我國于1982年加入IFORS，并于1999年8月組織了第15屆大會二戰以前萌芽二戰期間產生五六十年代發展七八十年代成熟運籌學在我國的發展：歷史故事：齊王田忌賽馬現代發展：1950s中期，錢學森、華羅庚、許志國等將運籌學引入我國。引入數學方法解決實際問題

--定性與定量方法結合系統與整體性

--從全局考察問題應用性

--源于實踐、為了實踐、服務于實踐交叉學科

--涉及經濟、管理、數學、工程和系統等多學科開放性

--不斷產生新的問題和學科分支多分支

--問題的復雜和多樣性二、運籌學的特點及研究對象線性規劃劃數學規劃非線性規劃整數規劃動態規劃學科內容目標規劃組合優化最優計數問題網絡優化排序問題統籌圖隨機優化對策論排隊論庫存論決策分析可靠性分析運籌學的研究內容：三、運籌學解決問題的方法步驟明確問題建立模型設計算法整理數據求解模型評價結果明確問題建立模型設計算法整理數據求解模型評價結果簡化？滿意？YesNoNo第一章線性規劃與單純形法

線性規劃是運籌學的一個最重要的分支，理論上最完善，實際應用得最廣泛。自從1947年G.B.Dantzig發明了求解線性規劃的單純形方法后，線性規劃已被廣泛地應用于解決經濟管理和工業生產中遇到的實際問題。

§1.1線性規劃的基本概念一、線性規劃問題舉例例1.1生產計劃問題（Max,）某工廠生產P、Q兩種產品，主要消耗A、B、C三種原料，已知單位產品原料消耗數量等資源如表1-1所示，要求確定P、Q的產量，使產值最大.表1-1產品單位消耗原料PQ原料總量ABC1502248噸20噸12噸產品單價2萬元5萬元解：設P、Q的產量分別為因此問題歸結為下列模型：線性規劃模型：10例1.2配料問題（Min,≥）某公司打算利用甲、乙、丙三種原料配置一種新型保健飲料，已知每千克原料中兩種主要保健成分A、B的含量及原料單價如表1-2所示。表1-2原料含量成分甲乙丙AB2010400020原料單價223解：設每千克飲料中原料甲、乙、丙的投入量分別為x1、x2、x3千克，問題歸結為下列模型：產品質量標準規定每千克飲料中，營養成分A、B的含量不低于10個與8個單位。如何制定配方，既滿足質量標準又使成本最低？例1.3運輸問題數學模型

二、線性規劃的模型結構：

線性規劃問題的共同特點：（1）每個行動方案可用一組變量（x1，…，xn）的值表示，這些變量一般取非負值；（2）變量的變化要受某些限制，這些限制條件用一些線性等式或不等式表示；（3）有一個需要優化的目標，它也是變量的線性函數。具備以上三個特點的數學模型稱為線性規劃（LinearProgramming，簡記為LP）

目標函數：約束條件：①②③2、線性規劃數學模型的一般形式也可以記為如下形式：目標函數：約束條件：記向量和矩陣,,,,線性規劃問題矩陣形式線性規劃解的概念

對于只有兩個變量的線性規劃問題，可以在二維直角坐標平面上作圖表示線性規劃問題的有關概念，并求解。

圖解法簡單、直觀，便于初學者了解線性規劃基本原理和幾何意義。三、圖解法例1.4用圖解法求解下列線性規劃⑴⑵⑶⑷012345678123456⑴⑵⑶⑷作圖∴最優解：x1=4x2=2有唯一最優解，Z=14x2

x1(42)⑴⑵⑶⑷例1.5⑴⑵⑶無窮多最優解x1x2

問題的最優解為例1.6⑴⑵無界解x1x2

x1x2

x2

⑴⑵x1x2

無可行解例1.7練習1第二節線性規劃的標準形式和解的性質一、LP的標準形式為了使線性規劃問題的解法標準，把一般形式LP化為標準形式變換一般LP為標準形式的方法：x1+x210

x1+x2+xs=10，xs0x1+x210

x1+x2-xs=10，xs0（4）若某個xj的符號約束為xj≤0；那么令xj′=－xj，則xj′≥0；若某個xj無符號限制，則可令xj=xj′－xj″，其中xj′≥0，xj″≥0。例1.8：將下列線性規劃問題化為標準形式例1.9：將下列線性規劃問題化為標準形式二、LP的基可行解的概念

標準形式的線性規劃的矩陣表示：注：標準型有n+m個變量，m個約束條件在標準型中，技術系數矩陣有n+m列最多有個基基本解令非基變量XN=0，求得基變量

XB的值稱為基本解即XB=B-1

b基可行解基本解

XB的非零分量都0時，稱為基可行解。注：可行解：滿足約束條件和非負條件的解X稱為可行解。34線性規劃標準型問題解的關系約束方程的解空間基本解可行解非可行解基可行解35例考慮問題：可行解、基本解和基本可行解舉例§1.3單純形法單純形方法的解題思路單純形要點和單純形表單純形法的補充說明方便、有效、通用一、單純形方法的解題思路單純形方法的基本思想

將模型的一般形式變成標準形式，再根據標準型模型，從可行域中找一個基本可行解，并判斷是否是最優。如果是，獲得最優解；如果不是，轉換到另一個基本可行解，當目標函數達到最大時，得到最優解。三個問題：(1)如何找到一個初始的基本可行解;(2)如何判別當前的基本可行解是否已達到了最優解;(3)若當前解不是最優解，如何去尋找一個改善的基可行解。例1.11求解線性規劃：

解：第一步：引入非負的松弛變量將原問題轉化為標準型模型：

第三步：寫出初始基本可行解和相應的目標函數值令非基變量為零，得到：X1=(0,0,8,20，12)T，z(1)=0最優性檢驗: 該解是最優解嗎？從目標函數來看，x1

或者x2成為基變量，變成正值，則Z值會上升。約束方程組是典式，x3,x4,x5為基變量第二步：尋求初始可行基，確定基變量第二次換基迭代：選x2入基約束方程：新基變量x2,x3,x4的解出形式為：X2

=(0,3,2,14，0)T確定換出變量最優性檢驗兩個關鍵的基本表達式：①用非基變量表示基變量的表達式②用非基變量表示目標函數的表達式第四步：分析兩個基本表達式，看看目標函數是否可以改善？

x1引入基可改善Z的值第三次換基迭代：選x1入基

解出形式為：得到新的基可行解X3

=(2,3,0,4，0)T目標函數用非基變量表示X3是最優解，Z的最優值是19萬元第五步：上述過程何時停止？——分析用非基變量表示目標函數的表達式，如果讓負檢驗數所對應的變量進基，目標函數值將下降！當用非基變量表示目標函數的表達式中，非基變量的系數（檢驗數）全部非正時，當前的基本可行解就是最優解!

為什么？找出一個初始可行解是否最優轉移到另一個目標函數（找更大的基本可行解）最優解是否循環直到找出為止，核心是：變量迭代在可行域的頂點——基可行解中尋優結束單純形法是一種迭代算法，其步驟總結如下：二、單純形要點和單純形表1.檢驗數的意義和計算公式①用非基變量表示基變量的表達式②用非基變量表示目標函數的表達式2.單純形表3.單純形法的基本法則法則2換入變量確定法則設則xk為換入變量。法則1

最優性判定法則若對基可行解X1，所有檢驗數σj≤0則X1為最優解。法則3

換出變量確定法則

最小比所在行的原基變量xl為換出變量注：這個法則的目的是，保證下一個基本解的可行性，違背這一法則，下一個基本解一定包含負分量，即不是可行解法則4

換基迭代運算法則按照主元素進行矩陣的初等行變換——把主元素變成1，主元列的其他元素變成0（即主元列變為單位向量）用單純形法求下列LP問題的最優解最優解X*=（2，3，0，4，0）T，z*=2×2+5×3=19。cj

2

5

0

0

0

CB

XB

b

x1

x2

x3

x4

x5

θ比

0

0

0

x3

x4

x5

8

20

12

1

5

0

2

2

[4]

1

0

0

0

1

0

0

0

1

8/2

20/2

12/4

σj

2

5

0

0

0

0

0

5

x3

x4

x2

2

14

3

[1]

5

0

0

0

1

1

0

0

0

1

0

-1/2

-1/2

1/4

2/1

14/5

—

σj

2

0

0

0

-5/4

2

0

5

x1

x4

x2

2

4

3

1

0

0

0

0

1

1

-5

0

0

1

0

-1/2

2

1/4

σj

0

0

-2

0

-1/4

例題1.12求下列LP問題的最優解cj230000cBxBb

x1x2x3x4x5x60000x3x4x5x61281612221000120100400010040001σj

23000012/28/2－12/4000x3x4x516

400010

σj

3x23010001/42620100-1/210010-1/220000-3/46/2216/4－cj230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/4σj

20000-3/46/2216/4－0203x3x1x5x22283001-201/210010-1/2000-412010001/44－412σj

000-201/4cj230000cBxBbx1x2x3x4x5x60203x6x1x5x2

4402

002-401101-10000-441001-1/2100σj

00-1/2-100000-201/4σj

4－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cjcj230000cBxBbx1x2x3x4x5x60203x3x1x6x2

0442001-1-1/4010001/40

000-21/210101/2-1/80σj

000-3/2-1/80000-201/4σj

4－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj練習0-130-20σj

10x1x4x6000x1x2x3x4x5x6bxBcB0-130-20cj1270-430810-2410013-1020初始表三、關于單純形法的補充說明1.無窮多最優解與唯一最優解的判別法則若對某可行解X1，（1）所有檢驗數σj≤0，且有一個非基變量xk的檢驗數等于0，則問題有無窮多最優解；（2）所有非基變量的檢驗數σj<0，則問題有唯一最優解。例1.13討論線性規劃的最優解的類型。解：2.無最優解（無界解）的判定

若對基可行解X1，存在非基變量xk的檢驗數σk>0，但aik≤0，i=1，2，…，m。即xk的系數列向量無正分量，則問題無最優解。用單純形表求下列線性規劃：

max

z=4x1+x2

s.t.

x1+x2

2

x1

4x2

4

x1

2x2

8

x1,x2

0

c41000 cBxBbx1x2x3x4x50x32-11100 --0x441-401040x581-20018

σj

41000

c41000cBxBbx1x2x3x4x50x360-3110 --4x141-4010--0x54020-112

σj

0170-40

c41000 cBxBbx1x2x3x4x50x312001-1/23/2 4x112100-121x22010-1/21/2

σj

0009/2-17/2284610-224x1

x2x1-2x2

8-x1+x2

2z=4x1+x2-4-2x1-4x2

43.求minz的情況兩種處理方式：（1）令z1=-z，轉化為標準形式求maxz1；（2）直接計算最優性檢驗性條件改為:所有換入變量確定法則改為：則xk為換入變量。例1.14求LP問題的最優解。第四節初始可行基的求法

——人工變量法大M法二階段法一、大M法基本思想引入人工變量，人為的地構造一組初始基變量；在目標函數中賦予人工變量很大的罰系數M；用線性規劃的優化機制迫使人工變量出基，