管理運籌線性規(guī)劃的圖解法

管理運籌線性規(guī)劃的圖解法第一頁，共三十一頁，2022年，8月28日1第二章線性規(guī)劃圖解法線性規(guī)劃數(shù)學模型

線性規(guī)劃圖解法

線性規(guī)劃數(shù)學模型標準型

第二頁，共三十一頁，2022年，8月28日2線性規(guī)劃（LinearProgramming,LP）線性規(guī)劃是研究線性約束條件下線性目標函數(shù)的極值問題的數(shù)學理論與方法。即對于統(tǒng)籌規(guī)劃問題，為如何合理地、有效地利用現(xiàn)有有限的人力、物力、財力資源來完成更多的任務，或者如何才能以最少的代價去實現(xiàn)目標，作出的最優(yōu)決策，提供科學的依據(jù)。

有關線性規(guī)劃問題的建模、求解和應用研究構成了運籌學中一個重要的、應用最為廣泛的分支。其典型問題有：運輸問題、生產計劃問題、下料問題、混合配料問題等。第三頁，共三十一頁，2022年，8月28日3

1939年蘇聯(lián)數(shù)學家康托羅維奇在《生產組織與計劃中的數(shù)學方法》一書中提出線性規(guī)劃問題﹐并未引起重視。

1947年美國數(shù)學家丹捷格﹐G.B.提出線性規(guī)劃的一般數(shù)學模型和求解線性規(guī)劃問題的通用方法──單純形法﹐為這門學科奠定了基礎。1947年美國數(shù)學家諾伊曼﹐J.von提出對偶理論﹐開創(chuàng)了線性規(guī)劃的許多新的研究領域﹐擴大了它的應用范圍和解題能力。線性規(guī)劃的發(fā)展第四頁，共三十一頁，2022年，8月28日4

1951年美國經濟學家T.C.庫普曼斯把線性規(guī)劃應用到經濟領域﹐為此與康托羅維奇一起獲1975年諾貝爾經濟學獎。50年代后對線性規(guī)劃進行大量的理論研究﹐并涌現(xiàn)出一大批新的算法。例如﹐1954年C.萊姆基提出對偶單純形法﹐1954年S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題﹐1956年A.塔克提出互補松弛定理﹐1960年丹捷格﹐G.B.和P.沃爾夫提出分解算法等。線性規(guī)劃的發(fā)展第五頁，共三十一頁，2022年，8月28日5線性規(guī)劃的研究成果還直接推動了其它數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃﹑隨機規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計算器的發(fā)展﹐出現(xiàn)了許多線性規(guī)劃軟件﹐如MPSX﹐OPHEIE﹐UMPIRE等﹐可以很方便地求解幾千個變量的線性規(guī)劃問題。線性規(guī)劃的發(fā)展大型電子計算器的出現(xiàn)對線性規(guī)劃的理論以及應用的發(fā)展起著決定性的作用，在經濟領域中廣泛地應用線性規(guī)劃方法﹐利用電子計算機目前已能解決變量多達數(shù)百萬之多的具有特殊結構的大型線性規(guī)劃問題。第六頁，共三十一頁，2022年，8月28日6第二章

線性規(guī)劃的圖解法§1問題的提出§2圖解法§3圖解法的靈敏度分析第七頁，共三十一頁，2022年，8月28日7第二章線性規(guī)劃的圖解法在管理中一些典型的線性規(guī)劃應用合理利用線材問題：如何在保證生產的條件下，下料最少配料問題：在原料供應量的限制下如何獲取最大利潤投資問題：從投資項目中選取方案，使投資回報最大產品生產計劃：合理利用人力、物力、財力等，使獲利最大勞動力安排：用最少的勞動力來滿足工作的需要運輸問題：如何制定調運方案，使總運費最小線性規(guī)劃的組成：目標函數(shù)MaxF或MinF約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素第八頁，共三十一頁，2022年，8月28日8§1問題的提出例1.某工廠在計劃期內要安排Ⅰ、Ⅱ兩種產品的生產，已知生產單位產品所需的設備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問題：工廠應分別生產多少單位Ⅰ、Ⅱ產品才能使工廠獲利最多？線性規(guī)劃模型：目標函數(shù)：Maxz=50x1+100x2

約束條件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0第九頁，共三十一頁，2022年，8月28日9§1問題的提出建模過程1.理解要解決的問題，了解解題的目標和條件；2.定義決策變量（x1，x2，…，xn

），每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標函數(shù)，確定最大化或最小化目標；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件一般形式目標函數(shù)：Max（Min）z=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0第十頁，共三十一頁，2022年，8月28日10例1.目標函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標值z=27500§2圖解法對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念，并求解。下面通過例1詳細講解其方法：第十一頁，共三十一頁，2022年，8月28日11§2圖解法

(1)分別取決策變量X1,X2

為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第十二頁，共三十一頁，2022年，8月28日12§2圖解法（2）對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第十三頁，共三十一頁，2022年，8月28日13§2圖解法（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1第十四頁，共三十一頁，2022年，8月28日14§2圖解法（4）目標函數(shù)z=50x1+100x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第十五頁，共三十一頁，2022年，8月28日15§2圖解法線性規(guī)劃的標準化內容之一：——引入松馳變量（含義是資源的剩余量）例1中引入s1，s2，s3模型化為目標函數(shù)：Maxz=50x1+100x2+0s1+0s2+0s3

約束條件：s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=

250x1,x2,s1,s2,s3≥0

對于最優(yōu)解

x1=50x2=250，s1=0s2=50s3=0

說明：生產50單位Ⅰ產品和250單位Ⅱ產品將消耗完所有可能的設備臺時數(shù)及原料B，但對原料A則還剩余50千克。第十六頁，共三十一頁，2022年，8月28日16§2圖解法重要結論：如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應一個最優(yōu)解；無窮多個最優(yōu)解。若將例1中的目標函數(shù)變?yōu)閙axz=50x1+50x2，則線段BC上的所有點都代表了最優(yōu)解；無界解。即可行域的范圍延伸到無窮遠，目標函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。若在例1的數(shù)學模型中再增加一個約束條件4x1+3x2≥1200，則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解了。第十七頁，共三十一頁，2022年，8月28日17進一步討論例2

某公司由于生產需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購進125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時間也是不同的，加工每噸A原料需要2個小時，加工每噸B原料需要1小時，而公司總共有600個加工小時。又知道每噸A原料的價格為2萬元，每噸B原料的價格為3萬元，試問在滿足生產需要的前提下，在公司加工能力的范圍內，如何購買A，B兩種原料，使得購進成本最低？第十八頁，共三十一頁，2022年，8月28日18進一步討論解：目標函數(shù)：Minf=2x1+3x2

約束條件：s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

采用圖解法。如下圖：得Q點坐標（250，100）為最優(yōu)解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q第十九頁，共三十一頁，2022年，8月28日19§3圖解法的靈敏度分析線性規(guī)劃的標準化一般形式目標函數(shù)：Max（Min）z=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0標準形式目標函數(shù)：Maxz=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥0第二十頁，共三十一頁，2022年，8月28日20§3圖解法的靈敏度分析

可以看出，線性規(guī)劃的標準形式有如下四個特點：目標最大化；約束為等式；決策變量均非負；右端項非負。對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉化為標準形式:第二十一頁，共三十一頁，2022年，8月28日21§3圖解法的靈敏度分析1.極小化目標函數(shù)的問題：設目標函數(shù)為

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z

＝-f

，則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即Maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標函數(shù)值卻相差一個符號，即

Minf

＝-Maxz第二十二頁，共三十一頁，2022年，8月28日22§3圖解法的靈敏度分析2、約束條件不是等式的問題：設約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進一個新的變量s

，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=bi第二十三頁，共三十一頁，2022年，8月28日23§3圖解法的靈敏度分析當約束條件為

ai1x1+ai2x2+…+ainxn

≥bi

時，類似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi第二十四頁，共三十一頁，2022年，8月28日24§3圖解法的靈敏度分析為了使約束由不等式成為等式而引進的變量s,當不等式為“小于等于”時稱為“松弛變量”；當不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉化為標準形式時，必須對各個約束引進不同的松弛變量。

3.右端項有負值的問題：

在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數(shù)為負時，如bi<0，則把該等式約束兩端同時乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi。第二十五頁，共三十一頁，2022年，8月28日25§3圖解法的靈敏度分析例：將以下線性規(guī)劃問題轉化為標準形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤62x1+x3≥8

x1+x2+x3=-9

x1,x2,x3

≥0

解：首先,將目標函數(shù)轉換成極大化：令z=-f=-2x1+3x2-4x3

其次考慮約束，有2個不等式約束，引進松弛變量x4，x5

≥0。第三個約束條件的右端值為負，在等式兩邊同時乘-1。第二十六頁，共三十一頁，2022年，8月28日26§3圖解法的靈敏度分析通過以上變換，可以得到以下標準形式的線性規(guī)劃問題：

Maxz=-2x1

+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0***變量無符號限制的問題***：

在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。第二十七頁，共三十一頁，2022年，8月28日27§3圖解法的靈敏度分析

靈敏度分析：建立數(shù)學模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci,aij,bj

變化時，對最優(yōu)解產生的影響。3.1目標函數(shù)中的系數(shù)ci

的靈敏度分析考慮例1的情況，ci的變化只影響目標函數(shù)等值線的斜率，目標函數(shù)z=50x1+100x2

在z=x2(x2=z斜率為0

)

到z=x1+x2(x2=-x1+z斜率為-1

)之間時，原最優(yōu)解x1=50，x2=100仍是最優(yōu)解。一般情況：

z=c1x1+c2x2

寫成斜截式x2=-(c1/c2)x1+z/c2

目標函數(shù)等值線的斜率為-(c1/c2)，當-1-(c1/c2)0（*）時，原最優(yōu)解仍是最優(yōu)解。第二十八頁，共三十一頁，2022年，8月28日28§3圖解法的靈敏度分析假設產品Ⅱ的利潤100元不變，即c2=100，代到式（*）并整理得

0c1

100假設產品Ⅰ的利潤50元不變，即c1=50，代到式（*）并整理得

50c2

+假若產品Ⅰ、Ⅱ的利潤均改變，則可直接用式（*）來判斷。假設產品Ⅰ、Ⅱ的利潤分別為60元