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

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

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

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

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

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

某廠每日8小時(shí)的產(chǎn)量不低于1800件。為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員。一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15小時(shí)/件，正確率95%，計(jì)時(shí)工資3元/小時(shí)。檢驗(yàn)員每錯(cuò)檢一次，工廠要損失2元。為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？解設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：因檢驗(yàn)員錯(cuò)檢而造成的損失為：故目標(biāo)函數(shù)為：故目標(biāo)函數(shù)為：約束條件為：線性規(guī)劃模型：返回目標(biāo)函數(shù)：約束條件：①②③線性規(guī)劃數(shù)學(xué)模型的一般形式一般有兩種方法圖解法單純形法兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但需將一般形式變成標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的求解方法對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問(wèn)題的有關(guān)概念，并求解。下面通過(guò)例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）畫(huà)出線性規(guī)劃問(wèn)題的可行域，如圖所示。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取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱(chēng)之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。得到最優(yōu)解：x1=50，x2=250，最優(yōu)目標(biāo)值z(mì)=27500x1x2z=20000=50x1+100x2圖2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE1、解的概念⑴可行解：滿足約束條件②、③的解為可行解。所有解的集合為可行解的集或可行域。⑵最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。線性規(guī)劃問(wèn)題的解目標(biāo)函數(shù)：約束條件：①②③⑶基：B是矩陣A中m×n階非奇異子矩陣（∣B∣≠0），則B是一個(gè)基。則稱(chēng)Pj(j=12……m)為基向量?！郮j為基變量，否則為非基變量。目標(biāo)函數(shù)：約束條件：①②③

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

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

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

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

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