第二章線性規(guī)劃及對偶理論目錄2.1一般線性規(guī)劃問題及其數(shù)學(xué)模型2.2圖解法2.3單純形法原理及計算步驟2.4對偶問題2.5線性規(guī)劃的應(yīng)用2.1一般線性規(guī)劃問題及其數(shù)學(xué)模型問題的提出：生產(chǎn)和經(jīng)營管理過程中如何提出合理安排，使用人力、物理等資源得到充分利用，獲得最大效益規(guī)劃問題主要有兩類：給定了人力、物力資源，研究如何合理地利用這些資源；研究如何統(tǒng)籌安排，盡量以最少的人力、物力資源來完成一定任務(wù)這些都屬于尋找整個問題的某個整體指標(biāo)的最優(yōu)化問題。例2-1生產(chǎn)計劃問題某公司計劃制造I，II兩種產(chǎn)品都要分別在A、B、C三種不同設(shè)備上加工，占用設(shè)備的時間、設(shè)備加工能力和產(chǎn)品售出利潤如右表所示，問該公司應(yīng)制造兩種產(chǎn)品各幾件，使獲取的利潤最大？ⅠⅡ加工能力限制

設(shè)備A128

設(shè)備B4016設(shè)備C0412利潤23分析求解解：設(shè)產(chǎn)品Ⅰ生產(chǎn)x1件，產(chǎn)品Ⅱ生產(chǎn)x2件。

z為利潤函數(shù)，

maxz:表示求z的最大值。則例1的數(shù)學(xué)模型可表示為：ⅠⅡ限制

設(shè)備A128

設(shè)備B4016設(shè)備C0412利潤23目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥0其中，x1，x2稱為決策變量z是公司能獲取的利潤目標(biāo)值，是變量x1，x2的函數(shù)，稱為目標(biāo)函數(shù)用于描述限制條件的數(shù)學(xué)表達(dá)式稱為約束條件。符號st.（subjectto的縮寫）為“約束于”由以上例子可以看出：為了求解上述問題，首先要把該問題用數(shù)學(xué)的語言來描述，這個過程叫做建立問題的數(shù)學(xué)模型。建立數(shù)學(xué)模型，可以按照以下三個步驟進(jìn)行：1、選取決策變量2、建立目標(biāo)函數(shù)3、確定約束方程這三者是組成規(guī)劃問題數(shù)學(xué)模型的三要素。2.1.1線性規(guī)劃數(shù)學(xué)模型的一般形式假定線性規(guī)劃問題中含n個變量，用xj表示，其系數(shù)為cj變量xj取值受m項資源的限制，用表示bj其資源擁有量用aij表示技術(shù)系數(shù)和工藝系數(shù)一般形式為：

max(min)(c1

x1+c2

x2+…+

cn

xn

)

a11

x1+a12

x2+…+a1nxn

(=,)b1

a21

x1+a22

x2+…+a2n

xn

(=,)b2

……

am1

x1+am2

x2+…+amn

xn

(=,)bm

x1，

x2，

…，xn

0

說明：

(1)決策變量：x1，x2，···，xn

。

一組決策變量表示為問題的一個方案；

(2)目標(biāo)函數(shù)：max(min)zz為決策變量的線性函數(shù);(3)約束條件一組線性不等式。cj為價值系數(shù),bi為資源，aij為技術(shù)系數(shù)(i=1,…,m;j=1,…,n).2.1.2線性規(guī)劃問題的標(biāo)準(zhǔn)型標(biāo)準(zhǔn)形特征如下：目標(biāo)函數(shù)值求最大約束條件全為線性等式?jīng)Q策變量全部不小于0限定系數(shù)全部為非負(fù)值幾種表示形式：代數(shù)式、和式、矩陣式和向量式（1）代數(shù)式目標(biāo)函數(shù)：max(c1

x1+c2

x2+…+

cn

xn

)

約束條件

a11

x1+a12

x2+…+a1nxn

=

b1

a21

x1+a22

x2+…+a2n

xn

=

b2

……

am1

x1+am2

x2+…+amn

xn

=

bm

x1，

x2，

…，xn

0

b1，

b2，

…，bn

0（2）和式

maxz=∑cjxj

∑aijxj=bi

i=1,2,…,m

xj

≥0

j=1,2,…,nj=1nnj=1（3）向量式

maxz=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,n

C=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=1（4）矩陣式

maxz=CX

AX=b，X

≥0，

b≥0

其中：

b=(b1,b2,…,bm)T

a11

a12….a1n

A=a21

a22…a2n………

am1

am2…amn標(biāo)準(zhǔn)形式的轉(zhuǎn)化1.無約束變量x的處理：

x=y-z,其中y,z02.負(fù)數(shù)變量x的處理：

x=-y,其中y03.目標(biāo)函數(shù)極小化的處理：

MinCX=-Max(-CX)4.非等式約束條件的處理：加松弛變量或減剩余變量5.右端項為負(fù)：兩端同乘“-1”例2-2將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)型st.例2-2將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)型st.解：令z’=-z，則例2-2將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)型

（1）st.（2）（3）解：令z’=-z，令1式，左邊加上松弛變量2式，左邊減去剩余變量3式兩邊同時乘以（-1）2.1.3線性規(guī)劃的解集特征線性規(guī)劃解與基的概念

(1)可行解、可行域、最優(yōu)解和最優(yōu)值

(2)基、基列、基變量和非基變量

(3)基解、基可行解和可行基凸集的概念與解集的基本定理

(1)凸集的概念

(2)解集的基本定理(1)可行解、可行域、最優(yōu)解和最優(yōu)值可行解：滿足約束條件的一組決策變量的取值；可行域：可行解所構(gòu)成的集合；最優(yōu)解：使目標(biāo)函數(shù)達(dá)到極值的可行解；最優(yōu)值：與最優(yōu)解相對應(yīng)的目標(biāo)函數(shù)的取值。線性規(guī)劃基與解的概念(2)基、基列、基變量和非基變量

基：maxCX,AX=b,X0,b0

其中，Amn其秩為m，B是Amn中的一個mm階滿秩矩陣，則稱B是線性規(guī)劃問題的一個基

基列：基B

中所包含的m個列向量

基變量：基列所對應(yīng)的決策變量

非基變量：基變量以外的決策變量(3)基解、基可行解、可行基

基解：令所有的非基變量為零，所求得的一組解

基可行解：所有分量均為非負(fù)的基解

可行基：與基可行解所對應(yīng)的基凸集的概念與解集的基本定理1.凸集的概念：設(shè)K是n維歐氏空間的一點集，若任意兩點X(1)K，X(2)K的連線上的一切點

X(1)+(1-)X(2)K，(0<<1)

則稱K為凸集。2.解集的基本定理：

(1)若線性規(guī)劃問題存在可行域，則其可行域是凸集；

(2)線性規(guī)劃問題的基可行解對應(yīng)其可行域的頂點；

(3)若線性規(guī)劃問題存在最優(yōu)解，則其最優(yōu)解一定能在基可行解中找到。線性規(guī)劃的可行域是凸集線性規(guī)劃的最優(yōu)解在極點上凸集凸集不是凸集極點可行域的性質(zhì)2.2圖解法圖解法就是用幾何作圖的方法分析并求解出其最優(yōu)解的過程求解思路是：先將約束條件加以圖解，求得滿足約束條件的解的集合（即可行域），然后結(jié)合目標(biāo)函數(shù)的要求從可行域中找出最優(yōu)解2.2.1圖解法的局限性和意義局限性：只能求解具有兩個變量的線性規(guī)劃問題。學(xué)習(xí)目的：圖解法的應(yīng)用具有很大的局限性，因此學(xué)習(xí)圖解法除了要掌握一種線性規(guī)劃問題的求解方法，還要通過圖解法揭示線性規(guī)劃問題的內(nèi)在規(guī)律，為學(xué)習(xí)線性規(guī)劃問題的一般算法（單純形法）奠定基礎(chǔ)。2.2.2圖解法的基本步驟

1.畫出平面直角坐標(biāo)系；

2.將約束條件逐一反映進(jìn)平面直角坐標(biāo)系，用標(biāo)號和箭線表明約束條件的順序和不等號的方向；

3.找出可行域并反映出目標(biāo)函數(shù)直線的斜率；

4.平移目標(biāo)函數(shù)直線找出最優(yōu)解。

分析求解例2-1ⅠⅡ限制

設(shè)備A128

設(shè)備B4016設(shè)備C0412利潤23目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥0x1x2

4

3

2

1

012345678目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥0圖解法圖解法x1x2

4

3

2

1

012345678目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥0圖解法x1x2

4

3

2

1

012345678目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥0圖解法x1x2

4

3

2

1

012345678目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥0圖解法x1x2

4

3

2

1

012345678目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥0圖解法x1x2

4

3

2

1

012345678目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥0圖解法x1x2

4

3

2

1

012345678目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥02.2.3圖解法的一般結(jié)論1.線性規(guī)劃問題的可行域是凸多邊形；2.如果線性規(guī)劃問題有最優(yōu)解，其最優(yōu)解一定可以在其可行域的頂點上得到，而不會在可行域的內(nèi)部；3.如果線性規(guī)劃問題在其可行域的兩個頂點上得到最優(yōu)解，那么兩頂點連線上的所有點均為最優(yōu)解點；4.線性規(guī)劃問題的解可能有四種情況：唯一最優(yōu)解；無窮多最優(yōu)解；無界解和無可行解。解題思路：先找凸集的任一頂點，計算比較2.3單純形法原理當(dāng)變量大于2時，可應(yīng)用求解單純形法的原理：先找出一個基可行解，判斷其是否為最優(yōu)解，如果為否，則轉(zhuǎn)換到相鄰的基可行解，并使目標(biāo)函數(shù)值不斷增大，一直到找到最優(yōu)解為止。即從可行域的一個頂點到另一個頂點迭代求最優(yōu)解2.3.1單純形法的基本思路1.找出一個初始的基可行解；2.判斷其最優(yōu)性；3.轉(zhuǎn)移至另一個較優(yōu)的基可行解；4.重復(fù)2、3兩步直至最優(yōu)。2.3.2最優(yōu)性檢驗與解的判別2.3.3單純形法的基本步驟1.數(shù)學(xué)模型標(biāo)準(zhǔn)化、正規(guī)化；2.建立初始單純形表；3.計算檢驗數(shù)并判斷最優(yōu)性，結(jié)束或繼續(xù)；4.確定入基變量和出基變量，5.迭代運算；6.重復(fù)3、4、5步，直至結(jié)束。繼續(xù)求解例2-1ⅠⅡ限制

設(shè)備A128

設(shè)備B4016設(shè)備C0412利潤23目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤8st.4x1≤164x2≤12x1，x2≥0

解：①標(biāo)準(zhǔn)化，建立單純形表

引入松弛變量x3，x4，x5為初始基變量

max

z=2x1+3x2+0x3+0x4+0x5x1

+

2x2

+

x3

=84x1

+

x4

=16

4x2

+

x5=12x1,x2,x3,x4,x5≥0cBxBbx1x2x3x4x5θcj23000cBxBbx1x2x3x4x5θ0x38121000x416400100x51204001σ令x1=0，x2=0此時的解：x(0)

=(0

0

8

16

12)Tz(0)=0②解的判別

∵σ1=2

σ2=3>0∴x(0)非最優(yōu)解③基變換

max{σ1,σ2}=3=σ2x2入基

min{8/2,--,12/4}=12/4x5出基出基變量和入基變量所在列的交叉處元素，為主元或樞軸元，用[]標(biāo)示。以主元[]所在行為軸，進(jìn)行初等行變換，將其變?yōu)?，使它所在列為單位列向量，得表213000cBxBbx1x2x3x4x5θ0x38121000x416400100x5120400123000cBxBbx1x2x3x4x5θ0x38121008/20x41640010--0x5120400112/423000此時的解：x(1)=(0

3

2

16

0)Tz(1)=9x(1)非最優(yōu)x1入基x3出基基變換

max{σ1,σ5}=2=σ1x1入基

min{2/1,16/4,--}=2/1x3出基以主元[a]所在行為軸，進(jìn)行初等行變換，將其變?yōu)?，使它所在列為單位列向量，得表3用單純形法求解例2-1此時的解：x(2)=(2

3

0

8

0)Tz(2)=11x(2)非最優(yōu)x5入基x4出基基變換

max{σ3,σ5}=1/4=σ5x5入基

min{--,8/4,12}=8/4x4出基以主元[a]所在行為軸，進(jìn)行初等行變換，將其變?yōu)?，使它所在列為單位列向量，得表4用單純形法求解例2-1此時的解：x(3)=(4

2

0

0

4)Tz(3)=11x(3)為最優(yōu)解即：最優(yōu)解：x*=(42004)T

最大值：z*=2×4+3×2=14若存在兩個以上相同的最小比值，就會出現(xiàn)退化解。理論上講，退化解可能使計算出現(xiàn)循環(huán)，從而得不到最優(yōu)解。然而，實際問題中很少出現(xiàn)這種情況。兩種特殊情況：2.3.4兩種改進(jìn)的單純形法1、大M法（M為很大的正數(shù)）法則：對于max問題，人工變量在目標(biāo)函數(shù)中的價值系數(shù)為-M；對于min問題，人工變量在目標(biāo)函數(shù)中的價值系數(shù)為M。2.兩階段法：由于大M不是一個確定的數(shù)，所以大M法適宜于手工計算，而不適合求解。為此，引入兩階段法。2.4對偶問題及對偶理論2.4.1對偶問題的提出：回顧例題2-1：現(xiàn)在I、II兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判，我們的價格底線是什么？ⅠⅡ加工限制

設(shè)備A128

設(shè)備B4016設(shè)備C0412利潤23設(shè)每個工時設(shè)備A收費y1元，B收費y2元，C收費y3元。出租收入不低于生產(chǎn)收入：

1y1+4y2≥22y1+4y3