1線性規(guī)劃的應用在人力，物力資源有限的條件下，如何安排生產，達到最大收益？如何用最少的人力，物力資源，完成給定的任務。許多管理上的問題可以用線性規(guī)劃來求解。2020/12/171ppt課件2線性規(guī)劃的問題某工廠生產兩種型號的電機（記為A和B），每臺A型電機需用原料2個單位，4個工時，每臺B型電機需用原料3個單位，2個工時，工廠共有原料100個單位，120個工時，A、B型電機的每臺利潤分別為600元和400元，問兩種電機各生產多少可使利潤最大？設A、B型電機各生產x1,x2臺，x1,x2稱為決策變量。利潤函數600x1+400x2目標函數2x1+3x2≤1004x1+2x2≤120約束條件2020/12/172ppt課件精品資料你怎么稱呼老師？如果老師最后沒有總結一節(jié)課的重點的難點，你是否會認為老師的教學方法需要改進？你所經歷的課堂，是講座式還是討論式？教師的教鞭“不怕太陽曬，也不怕那風雨狂，只怕先生罵我笨，沒有學問無顏見爹娘……”“太陽當空照，花兒對我笑，小鳥說早早早……”5線性規(guī)劃的數學問題上述問題可寫成如下的數學形式：它是求目標函數的最大值，決策變量滿足一定的條件（約束條件）。2020/12/175ppt課件6線性規(guī)劃的模型特點這是一個典型的利潤最大化的生產

計劃問題?！癕ax”是英文單詞“Maximize”的縮寫，含義為“最大化”；“s.t.”是“subjectto”的縮寫，表示

“滿足于……”。上述模型的含義是：在給定條件限制下，求使目標函數z達到最大的x1,x2

的取值。2020/12/176ppt課件7設有兩個磚廠A1，A2。產量分別為23萬和27萬，供應三個工地B1，B2，B3。其需要量分別為17萬，18萬和15萬。磚廠到各工地的每萬塊磚的運價如下表：線性規(guī)劃的應用模型B1B2B3A1506070A260110160如何調運，才可使總運費最小？2020/12/177ppt課件8于是得到如下的線性規(guī)劃模型：該問題可推廣到m個產地，n個銷地的運輸問題。2020/12/178ppt課件9線性規(guī)劃的應用模型某飼養(yǎng)場使用甲,乙,丙,丁四種飼料，每種飼料的的維生素A，B，C含量及單位價格和所需的維生素如下表，要求配制一個混合飼料，每單位混合飼料的維生素A、B、C的需要量為3，5，10.甲乙丙丁需要量ABC0.20.81.20.60.80.30.90.71.20.90.71.53510單價5667問如何配制多少可使成本最小而又能滿足需要？2020/12/179ppt課件10線性規(guī)劃的應用模型設x1,x2,x3,x4是甲乙丙丁四種飼料的用量，則要求維生素A的含量大于3，有

0.2x1+0.8x2+1.2x3+0.6x43要求維生素B的含量大于5，有

0.8x1+0.3x2+0.9x3+0.7x4

5要求維生素C的含量大于10，有

1.2x1+0.9x2+0.7x3+1.5x4

10目標是成本最小，有

Min5x1+6x2+6x3+7x4

2020/12/1710ppt課件11線性規(guī)劃的應用模型于是可得如下的線性規(guī)劃的模型：2020/12/1711ppt課件12線性規(guī)劃的一般形式2020/12/1712ppt課件13線性規(guī)劃的數學結構它是求一個函數最大值或最小值問題;這個函數稱為目標函數;這個目標函數是線性函數;這個目標函數可以認為定義在一個特定的區(qū)域上.這個區(qū)域是由一組線性不等式所確定.2020/12/1713ppt課件14線性規(guī)劃的標準形式2020/12/1714ppt課件15

可以看出，線性規(guī)劃的標準形式有如下四個特點：目標最大化、約束為等式、決策變量均非負、右端項非負。線性規(guī)劃的標準形式對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉化為標準形式:2020/12/1715ppt課件16

1.若目標函數求極?。簩⒕€性規(guī)劃化成標準形式設目標函數為

Minf=c1x1

+c2x2

+…+cnxn

則可以令z

＝-f

求極大化問題化成求下面的極小化問題.即

Maxz=-c1x1

-c2x2-…-cnxn

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

Minf

＝-Maxz2020/12/1716ppt課件17

2、約束條件不是等式的問題：

設約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進一個新的變量(稱為松弛變量)xn+i

，xn+i≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn+xn+i=bi將線性規(guī)劃化成標準形式2020/12/1717ppt課件18

當約束條件為

ai1x1+ai2x2+

…

+ainxn

≥bi

時，類似地引入變量xn+i(稱為剩余變量)xn+i≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn-xn+i=bi

將線性規(guī)劃化成標準形式2020/12/1718ppt課件19

例2.：將以下線性規(guī)劃問題轉化為標準形式

將線性規(guī)劃化成標準形式

解：第一個約束引入松弛變量x4,第二個約束引入剩余變量x5

2020/12/1719ppt課件20于是，我們可以得到以下標準形式的線性規(guī)劃問題：將線性規(guī)劃化成標準形式2020/12/1720ppt課件21

3.變量無符號限制的問題：在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。將線性規(guī)劃化成標準形式2020/12/1721ppt課件22

4.右端項有負值的問題：在標準形式中，要求右端項必須每一個分量非負。當某一個右端項為負時，如bi<0，則把該約束兩端同時乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi

。將線性規(guī)劃化成標準形式2020/12/1722ppt課件23例2.3：將以下線性規(guī)劃問題轉化為標準形式

將線性規(guī)劃化成標準形式第一個約束加松弛變量x5,第二約束加剩余變量x6,第三個約束兩端乘-1，再加剩余變量x7.2020/12/1723ppt課件24解：首先，目標函數是極小化,將它化成求最大。其次考慮3個不等式約束：將線性規(guī)劃化成標準形式第一個約束加松弛變量x5,2x1-3x2+5x3+6x4+x5=28第二約束加剩余變量x6,4x1+2x2+3x3-9x4–x6=39第三個約束兩端乘-1，再加剩余變量x7-6x2-2x3-3x4-x7=582020/12/1724ppt課件25由于x2無非負限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；于是，我們可以得到以下標準形式的線性規(guī)劃問題：2020/12/1725ppt課件26線性規(guī)劃的圖解法對兩個決策變量的線性規(guī)劃，可以利用幾何的方法來研究；觀察線性規(guī)劃的約束區(qū)域；觀察線性規(guī)劃的目標函數；觀察線性規(guī)劃的最優(yōu)解；2020/12/1726ppt課件27

線性規(guī)劃的圖解法對于兩個決策變量的線性規(guī)劃可用作圖方法來求解。圖解法求解線性規(guī)劃問題的步驟如下：

分別取決策變量x1,x2

為坐標向量建立直角坐標系。畫出線性規(guī)劃的約束區(qū)域；畫出目標函數等值線；平行移動目標函數等值線，找到最優(yōu)解。2020/12/1727ppt課件28

線性規(guī)劃的圖解法例1:某工廠擁有A、B、C三種類型的設備，生產甲、乙兩種產品。每件產品在生產中需要占用的設備機時數，每件產品可以獲得的利潤以及三種設備可利用的時數如下表所示：

產品甲產品乙設備能力（h）設備A3265設備B2140設備C0375利潤（元/件）15002500

2020/12/1728ppt課件29

線性規(guī)劃的圖解法

問題：工廠應如何安排生產可獲得最大的總利潤？用圖解法求解。解：設變量xi為第i種（甲、乙）產品的生產件數（i＝1，2）。根據前面分析，可以建立如下的線性規(guī)劃模型：

Max

z=1500x1

+2500x2

s.t.3x1+2x2

≤65(A)2x1+x2

≤40(B)3x2

≤75(C)

x1,x2

≥0(D,E)2020/12/1729ppt課件30線性規(guī)劃的圖解法以決策變量x1

，x2為坐標軸建立平面直角坐標系?？紤]約束條件3x1+2x2

≤653x1+2x2

=65是一個直線方程畫出這條直線。約束3x1+2x2

≤65是半個平面同理約束條件2x1+x2

≤40也是半個平面。2020/12/1730ppt課件31線性規(guī)劃的圖解法整個約束區(qū)域是由直線3x1+2x2

=65；2x1+x2

=40；3x2

=75；x1=0；x2

=0所圍

約束區(qū)域在約束區(qū)域中尋找一點使目標函數最大。2020/12/1731ppt課件32線性規(guī)劃的圖解法作出目標函數的等值線：1500x1+2500x2=30000將目標函數等值線沿增大方向平行移動。最優(yōu)解是3x1+2x2

=65和3x2

=75

兩直線的交點。2020/12/1732ppt課件33線性規(guī)劃的圖解法

圖解法求解線性規(guī)劃2020/12/1733ppt課件34線性規(guī)劃的圖解法

任意給定目標函數一個值作一條目標函數的等值線，并確定該等值線平移后值增加的方向，平移此目標函數的等值線，使其達到既與可行域有交點又不可能使值再增加的位置，得到交點(5,25)T，此目標函數的值為70000。于是，我們得到這個線性規(guī)劃的最優(yōu)解x1=5、x2=25，最優(yōu)值z=70000。即最優(yōu)方案為生產甲產品5件、乙產品25件，可獲得最大利潤為70000元。2020/12/1734ppt課件35作圖法求解如下線性規(guī)劃2020/12/1735ppt課件36最優(yōu)解點坐標:(1,5)2020/12/1736ppt課件37目標函數等值線2x1+3x2與約束條件4x1+6x2=9平行。2020/12/1737ppt課件38令x1→∞,則S→∞目標函數在可行域內無界!目標函數等值線沿右下方向將減小!2020/12/1738ppt課件39約束條件矛盾，線性規(guī)劃無解!－x1+2x2=22x1-x2=32020/12/1739ppt課件40

根據以上例題，進一步分析討論可知線性規(guī)劃的可行域和最