線性規(guī)劃優(yōu)秀課件

第三章線性規(guī)劃數(shù)學(xué)建模與數(shù)學(xué)實驗教學(xué)目的教學(xué)內(nèi)容2掌握線性規(guī)劃模型建立的三個基本要素3理解單純型算法

1、了解線性規(guī)劃的基本內(nèi)容。2、線性規(guī)劃的基本算法。1、兩個引例。問題一：

任務(wù)分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件。假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？兩個引例問什么?——問怎樣分配車床的加工任務(wù)？設(shè)什么？設(shè)各車床的具體加工任務(wù)，得決策變量：設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?；具^程：決策變量——〉目標(biāo)函數(shù)——〉約束條件1、確定決策變量——問什么，則設(shè)什么。2、確定目標(biāo)函數(shù)——看目標(biāo)是什么？使加工費用最低！加工費用3、確定約束條件——各決策變量有何限制？3、確定約束條件——各決策變量有何限制？三種工件的數(shù)量分別為400、600和500，兩臺車床的可用臺時數(shù)分別為800和900非負(fù)性要求解

設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型：

解答三種工件的數(shù)量分別為400、600和500，兩臺車床的可用臺時數(shù)分別為800和900線性規(guī)劃的組成要素：決策變量用符號來表示可控制的因素目標(biāo)函數(shù)MaxF或MinF約束條件s.t.(subjectto)滿足于建模步驟1.理解要解決的問題，了解解題的目標(biāo)和條件；2.定義決策變量（x1，x2，…，xn），每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件問題二：

某廠每日8小時的產(chǎn)量不低于1800件。為了進(jìn)行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標(biāo)準(zhǔn)為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標(biāo)準(zhǔn)為：速度15小時/件，正確率95%，計時工資3元/小時。檢驗員每錯檢一次，工廠要損失2元。為使總檢驗費用最省，該工廠應(yīng)聘一級、二級檢驗員各幾名？解設(shè)需要一級和二級檢驗員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗員的工資為：因檢驗員錯檢而造成的損失為：故目標(biāo)函數(shù)為：故目標(biāo)函數(shù)為：約束條件為：線性規(guī)劃模型：返回目標(biāo)函數(shù)：約束條件：①②③線性規(guī)劃數(shù)學(xué)模型的一般形式一般有兩種方法圖解法單純形法兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量、但需將一般形式變成標(biāo)準(zhǔn)形式線性規(guī)劃問題的求解方法對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。下面通過例1詳細(xì)講解其方法。例1.目標(biāo)函數(shù)：

Maxz=50x1+100x2約束條件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)圖解法（1）畫出線性規(guī)劃問題的可行域，如圖所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖1

Maxz=50x1+100x2s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)（2）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動等值線，當(dāng)移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。得到最優(yōu)解：x1=50，x2=250，最優(yōu)目標(biāo)值z=27500x1x2z=20000=50x1+100x2圖2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE1、解的概念⑴可行解：滿足約束條件②、③的解為可行解。所有解的集合為可行解的集或可行域。⑵最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。線性規(guī)劃問題的解目標(biāo)函數(shù)：約束條件：①②③⑶基：B是矩陣A中m×n階非奇異子矩陣（∣B∣≠0），則B是一個基。則稱Pj(j=12……m)為基向量?！郮j為基變量，否則為非基變量。目標(biāo)函數(shù)：約束條件：①②③

⑷基本解：滿足條件②，但不滿足條件③的所有解，最多為個。

⑸基本可行解：滿足非負(fù)約束條件的基本解，簡稱基可行解。

⑹可行基：對應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解2、解的基本定理⑴線性規(guī)劃問題的可行域是凸集（凸多邊形）。凸集凸集不是凸集頂點⑵最優(yōu)解一定是在凸集的某一頂點實現(xiàn)（頂點數(shù)目不超過個）⑶先找一個基本可行解，與周圍頂點比較，如不是最大，繼續(xù)比較，直到找出最大為止。3、解的情況唯一解無窮解無界解無可行解有最優(yōu)解無最優(yōu)解（一）、基本思想將模型的一般形式變成標(biāo)準(zhǔn)形式，再根據(jù)標(biāo)準(zhǔn)型模型，從可行域中找一個基本可行解，并判斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個基本可行解，當(dāng)目標(biāo)函數(shù)達(dá)到最大時，得到最優(yōu)解。（二）、線性規(guī)劃模型的標(biāo)準(zhǔn)形式1、標(biāo)準(zhǔn)形式線性規(guī)劃的基本算法——單純形法2、特征：⑴.目標(biāo)函數(shù)為求極大值，也可以用求極小值；⑵.所有約束條件（非負(fù)條件除外）都是等式，右端常數(shù)項為非負(fù)；⑶.變量為非負(fù)。3、轉(zhuǎn)換方式：⑴.目標(biāo)函數(shù)的轉(zhuǎn)換如果是求極小值即，則可將目標(biāo)函數(shù)乘以（－1），可化為求極大值問題。也就是：令，可得到上式。即⑵.約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量⑶.變量的變換若存在取值無約束的變量，可令其中：例一、將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式為無約束（無非負(fù)限制）

解:用替換，且，將第3個約束方程兩邊乘以（－1）將極小值問題反號，變?yōu)榍髽O大值標(biāo)準(zhǔn)形式如下：引入變量例二、將線性規(guī)劃問題化為標(biāo)準(zhǔn)型為無約束解：（三）、單純形法例一、變成標(biāo)準(zhǔn)型約束方程的系數(shù)矩陣為基變量為非基變量I為單位矩陣且線性獨立令：則：∴基本可行解為（001281612）

此時，Z=0然后，找另一個基本可行解。即將非基變量換入基變量中，但保證其余的非負(fù)。如此循環(huán)下去，直到找到最優(yōu)解為止。注意：為盡快找到最優(yōu)解，在換入變量時有一定的要求。如將目標(biāo)系數(shù)大的先換入等。找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個目標(biāo)函數(shù)（找更大的基本可行解）最優(yōu)解是否循環(huán)直到找出為止，核心是：變量迭代結(jié)束其步驟總結(jié)如下：當(dāng)時，為換入變量確定換出變量為換出變量接下來有下式：用高斯法，將的系數(shù)列向量換為單位列向量，其步驟是：結(jié)果是：代入目標(biāo)函數(shù)：有正系數(shù)表明：還有潛力可挖，沒有達(dá)到最大值；此時：令