線性規(guī)劃(LinearProgramming)線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題的求解方法線性規(guī)劃的圖解法線性規(guī)劃的單純形法單純形法的進(jìn)一步討論線性規(guī)劃模型的應(yīng)用一、線性規(guī)劃問題及其數(shù)學(xué)模型（一）、問題的提出

為了完成一項任務(wù)或達(dá)到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務(wù)或達(dá)到一定的目的，這個過程就是規(guī)劃。例一、有一正方形鐵皮，如何截取x使容積為最大？xa此為無約束極值問題

設(shè)備產(chǎn)品ABCD利潤（元）

Ⅰ

2

1

4

0

2

Ⅱ

2

2

0

4

3有效臺時12

81612

例二、已知資料如下表所示，問如何安排生產(chǎn)才能使利潤最大？或如何考慮利潤大，產(chǎn)品好銷。模型maxZ=2x1+3x2

x1≥0,x2≥0s.t.

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此為帶約束的極值問題（二）、數(shù)學(xué)模型1、問題中總有未知的變量，需要我們?nèi)ソ鉀Q。

要求：有目標(biāo)函數(shù)及約束條件，一般有非負(fù)條件存在，由此組成規(guī)劃數(shù)學(xué)模型。

如果在規(guī)劃問題的數(shù)學(xué)模型中，變量是連續(xù)的（數(shù)值取實數(shù)）其目標(biāo)函數(shù)是有關(guān)線性函數(shù)（一次方），約束條件是有關(guān)變量的線性等式或不等式，這樣，規(guī)劃問題的數(shù)學(xué)模型是線性的。反之，就是非線性的規(guī)劃問題（其中一個條件符合即可）。2、線性規(guī)劃數(shù)學(xué)模型的一般形式目標(biāo)函數(shù)：約束條件：①②③12也可以記為如下形式：目標(biāo)函數(shù)：約束條件：如將上例用表格表示如下：設(shè)變量

產(chǎn)品j設(shè)備i

有效臺時

利潤向量形式：矩陣形式：3、規(guī)劃類型規(guī)劃確定型隨機型靜態(tài)規(guī)劃動態(tài)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃非整數(shù)規(guī)劃整數(shù)規(guī)劃非整數(shù)規(guī)劃二、線性規(guī)劃問題的求解方法（一）、求解方法一般有兩種方法圖解法單純形法兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量、但需將一般形式變成標(biāo)準(zhǔn)形式（二）、線性規(guī)劃問題的解1、解的概念

⑴可行解：滿足約束條件②、③的解為可行解。所有解的集合為可行解的集或可行域。

⑵最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。

⑶基：B是矩陣A中m×n階非奇異子矩陣（∣B∣≠0），則B是一個基。則稱Pj

(j=12……m)為基向量?！郮j

為基變量，否則為非基變量。5

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

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

⑹可行基：對應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解2、解的基本定理⑴線性規(guī)劃問題的可行域是凸集（凸多邊形）。凸集凸集不是凸集極點⑵最優(yōu)解一定是在凸集的某一定點實現(xiàn)（頂點數(shù)目不超過個）⑶先找一個基本可行解，與周圍頂點比較，如不是最大，繼續(xù)比較，直到找出最大為止。3、解的情況唯一解無窮解無界解無可行解有最優(yōu)解無最優(yōu)解三、圖解法

建立直角坐標(biāo)，圖中陰影部分及邊界上的點均為其解，是由約束條件來反映的。例一、⑴⑵⑶⑷012345678123456⑴⑵⑶⑷作圖∴最優(yōu)解：x1=4x2=2有唯一最優(yōu)解，Z=14x2

x1(42)例二、例三、⑴⑵⑶無窮多最優(yōu)解⑴⑵無界解x1x1x2

x2

例三、⑴⑵x1x2

無可行解練習(xí)習(xí)題效產(chǎn)品機床率AB機床臺數(shù)

Ⅰ3040

40

Ⅱ5530

40

Ⅲ2337

20

2、

某車間用三種不同型號的機床Ⅰ、Ⅱ、Ⅲ，加工A、B兩種零件，機床臺數(shù)、生產(chǎn)效率如表所示。問如何合理安排機床的加工任務(wù)，才能使生產(chǎn)的零件總數(shù)最多？1、某工廠生產(chǎn)A1、A2

兩種產(chǎn)品，每件可獲利潤15、20元。每個產(chǎn)品都經(jīng)過三道工序，資料如表所示。工廠應(yīng)如何安排生產(chǎn)計劃使獲得的總利潤最多？試寫出此問題的數(shù)學(xué)模型。工產(chǎn)品工序時A1A2可用工時

Ⅰ

3

2

800

Ⅱ

2

3

800

Ⅲ

1

1

3503、用圖解法求解下面的線性規(guī)劃問題：四、單純形法（一）、基本思想將模型的一般形式變成標(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)形式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ù)大的先換入等。其步驟總結(jié)如下：找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個目標(biāo)函數(shù)（找更大的基本可行解）最優(yōu)解是否循環(huán)直到找出為止，核心是：變量迭代當(dāng)時，為換入變量確定換出變量為換出變量接下來有下式：用高斯法，將的系數(shù)列向量換為單位列向量，其步驟是：結(jié)果是：代入目標(biāo)函數(shù)：有正系數(shù)表明：還有潛力可挖，沒有達(dá)到最大值；有負(fù)系數(shù)表明：若要剩余資源發(fā)揮作用，就必須支付附加費用。當(dāng)時，即不再利用這些資源。此時：令得到另一個基本可行解

（0，3，6，2，16，0）如此循環(huán)進(jìn)行，直到找到最優(yōu)為止。本例最優(yōu)解為：（4，2，0，0，0，4）（四）、單純形表例題：判定標(biāo)準(zhǔn)：若求

或cj230000cBxBbx1x2x3x4x5x60000x3x4x5x61281612221000120100400010040001-Z0

23000012/28/2－12/4cj230000cBxBbx1x2x3x4x5x6000x3x4x516

400010

-Z3x23010001/42620100-1/2100100-1/2cj

230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/4-Z-9

20000-3/46/2216/4－cj230000cBxBbx1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44－412-Z-13000-201/4據(jù)攝動原理將下標(biāo)大的換出cj230000cBxBbx1x2x3x4x5x60203x3x1x6

x2

0442000-1-1/401100

1/40

000-21/2

10411/2

-1/80-Z-14000-3/2-1/80cj230000cBxBbx1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44－412-Z-13000-201/4據(jù)攝動原理將下標(biāo)大的換出五、單純形法的進(jìn)一步討論（一）、模型情況

變量：xj≥0xj≤0xj無約束結(jié)1、組成約束條件：≥=≤b

目標(biāo)函數(shù)：maxmin果2、變量xj≤0令xj′=-xj，xj′≥0

xj≥0不處理

xj

無約束令xj=xj′－

xj″,xj′≥0,xj″≥0唯一最優(yōu)無窮最優(yōu)無界解無可行解3、約束條件：加入松弛變量加入人工變量先減去再加上例：4、目標(biāo)函數(shù)：max,min

設(shè)規(guī)劃模型約束條件為，需加入人工變量，而得到一個m×m的單位矩陣，即基變量組合。因人工變量為虛擬變量，且存在于初始基本可行解中，需要將它們從基變量中替換出來。若基變量中不含有非零的人工變量，表示原問題優(yōu)解。若當(dāng)，而還有人工變量（非零）時，則表示原問題無可行解。加入人工變量后，目的是找到一個單位向量，叫人工基。其目標(biāo)價值系數(shù)要確定，但不能影響目標(biāo)函數(shù)的取值。一般可采用兩種方法處理：大M法和兩階段法。

⑴.大M法：即假定人工變量在目標(biāo)函數(shù)中的系數(shù)為M（任意大正數(shù)），如果是求極大值，需加-M；如果是求極小值，需加M。如基變量中還存在M，就不能實現(xiàn)極值。cj-31100MMcBxBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011-Z-3-6M1-M1-3M0M00cBxBbx1x2x3x4x5x6x70x4103-20100-1－Mx610100-11-211x31-2010001－-Z-11-M00M03M-1cj-31100MMcBxBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2－1x31-2010001－-Z-2-10001M-1M+1cBxBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3-Z20001/31/3M-1/3M-2/3∴最優(yōu)解為（4190000），Z=－2

⑵.兩階段法：用計算機處理數(shù)據(jù)時，只能用很大的數(shù)代替M,可能造成計算機上的錯誤，故多采用兩階段法。

第一階段：在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型：對上述模型求解（單純形法），若W=0,說明問題存在基本可行解，可以進(jìn)行第二個階段；否則，原問題無可行解，停止運算。第二階段：在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計算的初始表（用單純形法計算）。例：第一階段cj0000011cBxBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011-Z46-1-301000x4103-20100-1－1x610100-11-210x31-2010001－-Z10-1001030x4123001-22-50x210100-11-20x31-2010000-Z00000011cj-31100cBxBbx1x2x3x4x50x4123001-241x210100-1－1x31-20100－-Z-2-10001-3x141001/3-2/31x210100-11x390012/3-4/3-Z00001/31/3第二階段∴最優(yōu)解為（41900），目標(biāo)函數(shù)Z=-26、無可行解的判斷：運算到檢驗數(shù)全負(fù)為止，仍含有仍工變量，無可行解。

8、退化：即計算出的θ（用于確定換出變量）存在有兩個以上相同的最小比值，會造成下一次迭代中由一個或幾個基變量等于零，這就是退化（會產(chǎn)生退化解）。雖任意換出變量，目標(biāo)函數(shù)值不變，但此時不同的基卻表示為同一頂點，其特例是永遠(yuǎn)達(dá)不到最優(yōu)解。需作如下處理：

⑴.選中下標(biāo)最小的非基變量為換出變量；

⑵.當(dāng)θ中出現(xiàn)兩個以上最小值時，選下標(biāo)最大的基變量為換出變量。（二）、線性規(guī)劃小結(jié)建立模型個數(shù)取值右端項等式或不等式極大或極小新加變量系數(shù)兩個三個以上xj≥0xj無約束xj

≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解圖解法、單純形法單純形法不處理令xj

=

x′-x″

x′≥0x″≥0令

xj

=-xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xa加入xs不處理令z′=-ZminZ=－maxz′0-M根據(jù)上表列出初始單純形表AA六、線性規(guī)劃模型的應(yīng)用一般而言，一個經(jīng)濟(jì)、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。

⑴.要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)；

⑵.存在著多種方案；

⑶.要求達(dá)到的目標(biāo)是