第二章 線性規(guī)劃解的概念、性質(zhì)及圖解法

圖解法線性規(guī)劃問題求解的幾種可能結果由圖解法得到的啟示

2.2線性規(guī)劃解的概念、性質(zhì)及圖解法繼續(xù)返回例1的數(shù)學模型

目標函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x29—8—7—6—5—4—3—2—1—0

| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2

8(0,4)(8,0)

目標函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

8

4x1

164x2

12x1、x2

04x1

164x2

12圖解法可行域步驟一：由全部約束條件作圖求出可行域；9—8—7—6—5—4—3—2—1—0

| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

目標函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

84x1

164x2

12可行域BCDEA圖解法B9—8—7—6—5—4—3—2—1—0

x2

目標函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

12BCDEA2x1+3x2=6圖解法步驟二：作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向；9—8—7—6—5—4—3—2—1—0

x2

目標函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

12BCDEA圖解法x1+2x2=84x1=16MaxZ=14最優(yōu)解(4,2)步驟三：平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。圖解法求解步驟由全部約束條件作圖求出可行域；作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向；平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。9—8—7—6—5—4—3—2—1—0

x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1BCDEA最優(yōu)解(4,2)改變約束條件或目標函數(shù)，解的結果如何？線性規(guī)劃問題求解的

幾種可能結果(a)唯一最優(yōu)解

9—8—7—6—5—4—3—2—1—0

x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1BCDEA線性規(guī)劃問題求解的

幾種可能結果x1+2x2

=8

目標函數(shù)MaxZ=x1+2x2約束條件x1+2x2

84x1

164x2

12x1、x2

0(b)無窮多最優(yōu)解(c)無界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

x2x1線性規(guī)劃問題求解的

幾種可能結果(d)無可行解

MaxZ=2x1+3x2

x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

0可行域為空集線性規(guī)劃問題求解的

幾種可能結果圖解法的幾點結論:

（由圖解法得到的啟示）可行域是有界或無界的凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。解題思路：找出凸集的頂點，計算其目標函數(shù)值，比較即得。練習：

用圖解法求解LP問題

MaxZ=15

x1+25

x2x1+3x2

60

x1+

x2

40

x1、x2

0maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

L1Z=250目標函數(shù)變形：x2=-3/5

x1+z/25x2x1最優(yōu)解：

x1=30x2=10最優(yōu)值：zmax=700B點是使z達到最大的唯一可行點(30,10)A（0,20）C（40,0）0B習題：用圖解法求下列線性規(guī)劃:習題2maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0習題3maxz=2x1+2x2s.t.x1+x2≥1x1

–

3x2≥–

3

x1≤3

x1，x2≥0習題4maxz=5x1+3x2s.t.x1+x2≤1x1+2x2≥4

x1，x2≥0Ox1x2Note:可行域為無界區(qū)域，目標函數(shù)值可無限增大，即解無界。稱為無最優(yōu)解。A(1,0)可行域為無界區(qū)域一定無最優(yōu)解嗎？maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0習題：用圖解法求下列線性規(guī)劃:

0x1x2A(1,0)minZ(多解)線段AD上的任一點都是最優(yōu)解minZ=2習題3maxz=2x1+2x2s.t.x1+x2≥1x1

–

3x2≥–

3

x1≤3

x1，x2≥0(30,10)B(3,0)C(3,2)D(0,1)若minZ換為maxZ則最優(yōu)解為?點

0x1x2A(1,0)(30,10)B(4,0)D(0,1)習題4maxz=5x1+3x2s.t.x1+x2≤1x1+2x2≥4

x1，x2≥0C(0,2)無可行解

根據(jù)以上例題，進一步分析討論可知線性規(guī) 劃的可行域和最優(yōu)解有以下幾種可能的情況

1.可行域為封閉的有界區(qū)域

(a)有唯一的最優(yōu)解；

(b)有無窮多個最優(yōu)解；

2.可行域為非封閉的無界區(qū)域

(c)有唯一的最優(yōu)解；

(d)有無窮多個最優(yōu)解；

(e)目標函數(shù)無界(即雖有可行解，但在可行域中，目標函數(shù)可以無限增大或無限減少)，因而沒有有限最優(yōu)解。

3.可行域為空集

(f)沒有可行解，原問題無最優(yōu)解

二、線性規(guī)劃解的有關概念可行解、最優(yōu)解基、基變量、非基變量基本解、基本可行解可行基、最優(yōu)基繼續(xù)返回Ax=b，x≥0；1.可行解與最優(yōu)解極點定義1設集合是n維歐氏空間中的一個點集，如果及實數(shù)

則稱

S是一個凸集。幾何意義：如果集合中任意兩點連線上的一切點都在該集合中，則稱該集合為凸集。

凸集定義2

設則稱為點的一個凸組合。定義3設凸集兩點表示為則稱x為S

的一個極點（或頂點）。

定理LP問題的可行解集ＬＰ的可行域以及最優(yōu)解有以下性質(zhì):1.若線性規(guī)劃的可行域非空，則可行域必定為一凸集．2.若線性規(guī)劃的可行域非空，則至多有有限個極點.3.若線性規(guī)劃有最優(yōu)解,則至少有一個極點是最優(yōu)解.可行域內(nèi)無限個可行解可行域的有限個極點搜索1.圖解法求解步驟由全部約束條件作圖求出可行域；作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向；平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。小結：1.可行域為封閉的有界區(qū)域

(a)有唯一的最優(yōu)解；

(b)有無窮多個最優(yōu)解；

2.可行域為非封閉的無界區(qū)域

(c)有唯一的最優(yōu)解；

(d)有無窮多個最優(yōu)解；

(e)目標函數(shù)無界(即雖有可行解，但在可行域中，目標函數(shù)可以無限增大或無限減少)，因而沒有有限最優(yōu)解。

3.可行域為空集

(f)沒有可行解，原問題無最優(yōu)解

2.線性規(guī)劃的可行域和最優(yōu)解Ax=b，x≥0；3.可行解與最優(yōu)解1.若線性規(guī)劃的可行域非空，則可行域必定為一凸集．2.若線性規(guī)劃的可行域非空，則至多有有限個極點.3.若線性規(guī)劃有最優(yōu)解,則至少有一個極點是最優(yōu)解.可行域內(nèi)無限個可行解可行域的有限個極點搜索4.線性規(guī)劃的可行域和最優(yōu)解的性質(zhì)2.線性規(guī)劃的基、基本解與基本可行解

在一般情況下，由于圖解法無法解決三個變量以上的線性規(guī)劃問題，對于n個變量的線性規(guī)劃問題，我們必須用解方程的辦法來求得可行域的極點。再來進一步考察前例。

2.線性規(guī)劃的基、基本解與基本可行解

例2.8把例2.1的線性規(guī)劃模型標準化，引入松馳變量 x3

，x4

，x5≥0，得到

Maxz=1500x1

+2500x2

s.t.3x1+2x2+x3=65(A)

2x1+x2+x4=40(B)

3x2+x5=75(C)

x1

,x2

,x3,x4

,x5

≥0

用（D）（E）（F）（G）（H）分別表示x1

=0、x2

=0、x3=0、x4

=0、x5

=0。

這里一共有8個約束條件，其中3個等式約束（一般情況下，等式約束的個數(shù)少于決策變量的個數(shù)），5個變量非負約束（與決策變量個數(shù)相同）。每5個方程若線性無關可解得一個點，我們可以看到前例圖解法得到的區(qū)域中每兩條直線的交點與此例的各個方程有如下關系：見下圖。

由上圖可以看出：直線A、B的交點對應于約束條件(A)、（B）、（C）、（F）、（G）的解，即：x(1)=(15,10,0,0,45)T

直線A、C的交點對應于約束條件(A)、（B）、（C）、（F）、（H）的解，即：x(2)=(5,25,0,5,0)T

直線A、D的交點對應于約束條件(A)、（B）、（C）、（D）、（F）的解，即：x(3)=(0,32.5,0,7.5,-22.5)TMaxz=1500x1+2500x2

s.t.3x1+2x2+x3=65(A)

2x1+x2+x4=40(B)

3x2+x5=75(C)

x1,x2,x3,x4,x5≥0用（D）（E）（F）（G）（H）分別表示x1=0、x2=0、x3=0、x4=0、x5=0。X(1)X(2)X(3)DE

直線A、E的交點對應于約束條件(A)、（B）、（C）、（E）、（F）的解，即：x(4)=(65/3,0,0,-10/3,75)T

直線B、C的交點對應于約束條件(A)、（B）、（C）、（G）、（H）的解，即：x(5)=(7.5,25,-7.5,0,0)T

直線B、D的交點對應于約束條件(A)、（B）、（C）、（D）、（G）的解，即：x(6)=(0,40,-15,0,-45)TEDX(5)X(6)

直線B、E的交點對應于約束條件(A)、（B）、（C）、（E）、（G）的解，即：x(7)=(20,0,5,0,75)T

直線C、D的交點對應于約束條件(A)、（B）、（C）、（D）、（H）的解，即：x(8)=(0,25,15,15,0)T

直線C、E無交點（C、E相互平行）直線D、E的交點對應于約束條件(A)、（B）、（C）、（D）、（E）的解，即：x(9)=(0,0,65,40,75)TEX(8)X(9)

如果某一交點的坐標(x1

,x2,x3,x4,x5

)T全為非負，則該交點就對應于線性規(guī)劃可行域的一個極點（如A、B，A、C，B、E，C、D和D、E的交點，共5個）如果某一交點的坐標中至少有一個分量為負值（如A、D，A、E，B、C和B、D的交點），則該交點不是可行域的極點。E定義線性規(guī)劃的約束條件：

Ax=b，x≥0；A是m×n矩陣，m≤n并且r(A)=m。

（1）線性規(guī)劃的基基

(basis)：B是A中的一個非奇異（可逆）的m×m子矩陣，即|B|≠0

，則稱B是線性規(guī)劃的一個基(或基矩陣)。當m=n時，基矩陣惟一，當m<n時，基矩陣就可能有多個，但數(shù)目不超過。行滿秩的矩陣基向量：基B中的列

pj(j=1,2,…,m);基變量：與基向量對應的決策變量

xj(j=1,2,…,m)；非基變量：與非基向量對應的決策變量

xj(j=m+1,…,n)非基向量：A中除基向量外，其余的列pj(j=m+1,…,n);（1）線性規(guī)劃的基任取A中的m個線性無關列向量構成矩陣B，則B是A的一個基；【解】約束方程的系數(shù)矩陣為2×4矩陣

容易看出r(A)=2，2階可逆子矩陣最多有幾個？C42=6基向量：

p1和p2基變量：x1和x2，基向量：

p3和p4基變量：x3

和x4基變量、非基變量是針對某一確定基而言的，不同的基對應的基變量和非基變量也不同。非基向量：

p3和p4非基向量：

p1和p2非基變量：x1和x2非基變量：x3和x4若B是線性規(guī)劃的一個基，設是A的前m列，則A可以表示為A=[B,N]，x也可相應地分成

xBx=xN其中:xB為m維列向量，它的各分量稱為基變量，與基B的列向量對應；

xN為n-m維列向量，它的各分量稱為非基變量，與非基矩陣N的列向量對應。（2）基本解、基本可行解和可行基

基矩陣這時約束等式Ax=b可表示為

xB

（B,N）=b

xN

或

BxB

+NxN

=b

如果對非基變量xN取確定的值，則xB有唯一的值與之對應

xB=B-1b-B-1NxN

特別，當取xN=0，這時有xB=B-1b。

求解

基變量令非基變量T可求出：基本解：稱由約束求出的X解為基本解。矩陣描述為，對于線性規(guī)劃的解

xB

B-1b

x==

xN0

稱為線性規(guī)劃與基B對應的基本解。若其中B-1b≥

0，則稱以上的基本解為一基本可行解（即非負的基本解），相應的基B稱為可行基。

系數(shù)陣A中可找出多個基B返回非負的基本解就是基本可行解每個基B都對應于一個基本解注意：線性規(guī)劃的基本解、基本可行解和可行基只與線性規(guī)劃問題標準形式的約束條件有關。與目標函數(shù)無關。

線性規(guī)劃解的關系圖非可行解可行解

基本可行解

基本解

結論：線性規(guī)劃的基本可行解就是可行域的極點。最優(yōu)解？求相應于B1和B6的基本解，是否基本可行解？相應于基B6的基本解為X=(0,0,1,3)，是基本可行解.相應于基B1的基本解為X=(7/5,-1/5,0,0)，不是基本可行解.

線性規(guī)劃的基本定理

“線性規(guī)劃的基本可行解就是可行域的極點”．－－線性規(guī)劃的基本定理

這一基本定理把可行域的極點這一幾何概念與基本可行解這一代數(shù)概念聯(lián)系起來，因而可以通過求基本可行解的線性代數(shù)的方法來得到可行域的一切極點，從而有可能進一步獲得最優(yōu)極點。這里指出了一種求解線性規(guī)劃問題的可能途徑，就是先確定線性規(guī)劃問題的基，如果是可行基，則計算相應的基本可行解以及相應解的目標函數(shù)值。由于基的個數(shù)是有限的,因此必定可以從有限個基本可行解中找到最優(yōu)解。1、線性規(guī)劃的基基

(basis)：B是A中的一個非奇異（可逆）的m×m子矩陣，即|B|≠0

，則稱B是線性規(guī)劃的一個基(或基矩陣)