第1章 線性規(guī)劃

運籌學(xué)

OperationalResearch運籌帷幄，決勝千里

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

--定性與定量方法結(jié)合系統(tǒng)與整體性

--從全局考察問題應(yīng)用性

--源于實踐、為了實踐、服務(wù)于實踐交叉學(xué)科

--涉及經(jīng)濟、管理、數(shù)學(xué)、工程和系統(tǒng)等多學(xué)科開放性

--不斷產(chǎn)生新的問題和學(xué)科分支多分支

--問題的復(fù)雜和多樣性二、運籌學(xué)的特點及研究對象線性規(guī)劃劃數(shù)學(xué)規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動態(tài)規(guī)劃學(xué)科內(nèi)容目標規(guī)劃組合優(yōu)化最優(yōu)計數(shù)問題網(wǎng)絡(luò)優(yōu)化排序問題統(tǒng)籌圖隨機優(yōu)化對策論排隊論庫存論決策分析可靠性分析運籌學(xué)的研究內(nèi)容：三、運籌學(xué)解決問題的方法步驟明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果簡化？滿意？YesNoNo第一章線性規(guī)劃與單純形法

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

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

二、線性規(guī)劃的模型結(jié)構(gòu)：

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

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

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

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

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

問題的最優(yōu)解為例1.6⑴⑵無界解x1x2

x1x2

x2

⑴⑵x1x2

無可行解例1.7練習(xí)1第二節(jié)線性規(guī)劃的標準形式和解的性質(zhì)一、LP的標準形式為了使線性規(guī)劃問題的解法標準，把一般形式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：將下列線性規(guī)劃問題化為標準形式例1.9：將下列線性規(guī)劃問題化為標準形式二、LP的基可行解的概念

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

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

b基可行解基本解

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

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

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

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

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

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

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

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

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

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

最優(yōu)性判定法則若對基可行解X1，所有檢驗數(shù)σj≤0則X1為最優(yōu)解。法則3

換出變量確定法則

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

換基迭代運算法則按照主元素進行矩陣的初等行變換——把主元素變成1，主元列的其他元素變成0（即主元列變?yōu)閱挝幌蛄浚┯脝渭冃畏ㄇ笙铝蠰P問題的最優(yōu)解最優(yōu)解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問題的最優(yōu)解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練習(xí)0-130-20σj

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

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

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，轉(zhuǎn)化為標準形式求maxz1；（2）直接計算最優(yōu)性檢驗性條件改為:所有換入變量確定法則改為：則xk為換入變量。例1.14求LP問題的最優(yōu)解。第四節(jié)初始可行基的求法

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