第1章 線性規(guī)劃

運(yùn)籌學(xué)

OperationalResearch運(yùn)籌帷幄，決勝千里

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

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

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

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

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

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

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

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

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

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

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

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

對于只有兩個(gè)變量的線性規(guī)劃問題，可以在二維直角坐標(biāo)平面上作圖表示線性規(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ī)劃的標(biāo)準(zhǔn)形式和解的性質(zhì)一、LP的標(biāo)準(zhǔn)形式為了使線性規(guī)劃問題的解法標(biāo)準(zhǔn)，把一般形式LP化為標(biāo)準(zhǔn)形式變換一般LP為標(biāo)準(zhǔn)形式的方法：x1+x210

x1+x2+xs=10，xs0x1+x210

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

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

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

b基可行解基本解

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

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

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

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

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

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

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

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

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

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

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

換出變量確定法則

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

換基迭代運(yùn)算法則按照主元素進(jìn)行矩陣的初等行變換——把主元素變成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)于單純形法的補(bǔ)充說明1.無窮多最優(yōu)解與唯一最優(yōu)解的判別法則若對某可行解X1，（1）所有檢驗(yàn)數(shù)σj≤0，且有一個(gè)非基變量xk的檢驗(yàn)數(shù)等于0，則問題有無窮多最優(yōu)解；（2）所有非基變量的檢驗(yàn)數(shù)σj<0，則問題有唯一最優(yōu)解。例1.13討論線性規(guī)劃的最優(yōu)解的類型。解：2.無最優(yōu)解（無界解）的判定

若對基可行解X1，存在非基變量xk的檢驗(yàn)數(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)化為標(biāo)準(zhǔn)形式求maxz1；（2）直接計(jì)算最優(yōu)性檢驗(yàn)性條件改為:所有換入變量確定法則改為：則xk為換入變量。例1.14求LP問題的最優(yōu)解。第四節(jié)初始可行基的求法

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