OSYHY-1-2線性規(guī)劃解的概念及性質(zhì)

1-2線性規(guī)劃問題

解的概念和性質(zhì)

LP的標(biāo)準(zhǔn)型目標(biāo)函數(shù)約定是極大化Max;

約束條件均用等式表示;

決策變量限于取非負(fù)值;

右端常數(shù)均為非負(fù)值;LP問題的標(biāo)準(zhǔn)形其中:一、LP問題的各種解

可行解：滿足約束條件和非負(fù)條件的決策變量的一組取值。最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解?；窘猓涸O(shè)AX=b是含n個決策變量、

m個約束條件的LP的約束方程組，B是LP問題的一個基，若令不與B的列相應(yīng)的n-m個分量（非基變量）都等于零，所得的方程組的解稱為方程組AX=b關(guān)于基B的基本解，簡稱為LP的基本解。

4.基本可行解（對應(yīng)的基為可行基）：滿足非負(fù)條件的基本解。

5.基本最優(yōu)解（對應(yīng)的基為最優(yōu)基）：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的基本可行解。最優(yōu)解基本最優(yōu)解用畫圖、模型制作、三維動畫等方法清楚地顯示其可行解、基本解、基本可行解。進(jìn)一步具體計算出這些解來，說明它們之間的關(guān)系。課后討論1：研究約束集合二、線性規(guī)劃的圖解法

－－－解的幾何表示

1．什麼是圖解法？線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過程。求解的思路是：先將約束條件加以圖解，求得滿足約束條件的解的集合（即可行域），然后結(jié)合目標(biāo)函數(shù)的要求從可行域中找出最優(yōu)解。2.圖解法舉例

實(shí)施圖解法，以求出最優(yōu)生產(chǎn)計劃（最優(yōu)解）。

例1－1maxZ=2x1+3x2s.t.

由于線性規(guī)劃模型中只有兩個決策變量，因此只需建立平面直角坐標(biāo)系就可以進(jìn)行圖解了。

第一步：建立平面直角坐標(biāo)系。用x1軸表示產(chǎn)品A的產(chǎn)量，用x2軸表示產(chǎn)品B的產(chǎn)量。

第二步：對約束條件加以圖解。第三步：畫出目標(biāo)函數(shù)等值線，結(jié)合目標(biāo)函數(shù)的要求求出最優(yōu)解－－最優(yōu)生產(chǎn)方案。

0123456789x1

54321x2（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）將例1-1稍作改動形成案例1，仍使用圖解法來求解。

（案例1）某工廠生產(chǎn)A、B、C三種產(chǎn)品，每噸的利潤分別為2000元、3000元、1000元，生產(chǎn)單位產(chǎn)品所需的工時及原材料如表1－2所示。若供應(yīng)的原材料每天不超過3噸，所能利用的勞動力總工時是固定的，應(yīng)如何制定日生產(chǎn)計劃，使三種產(chǎn)品的總利潤最大？

設(shè)三種產(chǎn)品的產(chǎn)量分別是x1、x2、x3噸，由于有三個決策變量，用圖解法求解下面的線性規(guī)劃時，必須首先建立空間直角坐標(biāo)系。

B點(diǎn)對應(yīng)著該線性規(guī)劃的最優(yōu)解：

X*=(1,2,0)T

即x1=1（產(chǎn)品A的產(chǎn)量）

x2=2（產(chǎn)品B的產(chǎn)量）

x3=0（產(chǎn)品C的產(chǎn)量）此時可得產(chǎn)品最大總利潤為：

Zmax=8

由右圖可知，可行域?yàn)橥刮迕骟wOABCDE,粗虛線所圍平面為目標(biāo)函數(shù)等值面，平移目標(biāo)函數(shù)等值面得最優(yōu)點(diǎn)為B點(diǎn)。

例1-1和案例1所描述的都是有唯一最優(yōu)解且可行域是一個非空有界區(qū)域的情況。實(shí)際上，可行域不僅僅只有這一種可能，解的情況也是各種各樣的。

討論用圖解法求解線性規(guī)劃的各種可能的結(jié)果

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

該線性規(guī)劃的可行域?yàn)樯蠄D中四邊形OAED（即陰影區(qū)），虛線為目標(biāo)函數(shù)等值線，箭頭為目標(biāo)函數(shù)值遞增的方向。沿著箭頭的方向平移目標(biāo)函數(shù)等值線，發(fā)現(xiàn)平移的最終結(jié)果是目標(biāo)函數(shù)等值線將與可行域的一條邊界－－線段AE重合，這個結(jié)果表明，該線性規(guī)劃有無窮多個最優(yōu)解－－線段AE上的所有點(diǎn)都是最優(yōu)點(diǎn)，它們都使目標(biāo)函數(shù)取得相同的最大值Zmax=3。唯一最優(yōu)解

例1-3將例1-1中目標(biāo)要求改為極小化，目標(biāo)函數(shù)和約束條件均不變，則可行域與例1-1相同，目標(biāo)函數(shù)等值線也完全相同，只是在求最優(yōu)解時，應(yīng)沿著與箭頭相反的方向平移目標(biāo)函數(shù)等值線，求得的結(jié)果是有唯一最優(yōu)解x1=0,x2=0,對應(yīng)著圖1-6中的坐標(biāo)原點(diǎn)。無界解

本例中的可行域是一個無界區(qū)域，如圖中陰影區(qū)所示。虛線為目函數(shù)等值線，沿著箭頭所指的方向平移可以使目標(biāo)函數(shù)值無限制地增大，因此找不到最優(yōu)解。這種情況通常稱為無“有限最優(yōu)解”或“最優(yōu)解無界”。如果一個實(shí)際問題抽象成像例1－4這樣的線性規(guī)劃模型，比如是一個生產(chǎn)計劃問題，其經(jīng)濟(jì)含義就是某些資源是無限的，產(chǎn)品的產(chǎn)量可以無限大，解釋不合理。此時應(yīng)重新檢查和修改模型，否則就沒有實(shí)際意義。注意，對于無界可行域的情況，也可能有唯一最優(yōu)解或無窮多個最優(yōu)解。比如目標(biāo)要求為minZ=x1+2x2或maxZ=－2x1+x2，而約束條件不變的例子。x1x2

綜上，用圖解法求解線性規(guī)劃時，各種求解結(jié)果與各種類型的可行域之間的對應(yīng)關(guān)系可以用下圖加以描述：

課堂練習(xí)1-2：用圖解法求解下面的線性規(guī)劃依次完成：畫約束條件1；畫約束條件2；畫約束條件3；標(biāo)明可行域；目標(biāo)函數(shù)等值線；說明如何得到最優(yōu)解，算出相應(yīng)的目標(biāo)函數(shù)最優(yōu)值。

4、用圖解法求解線性規(guī)劃時需特別注意：

第一、線性規(guī)劃的可行域一定是凸多邊形或凸多面體，所以下圖中

所示陰影區(qū)不可能是某個線性規(guī)劃的可行域，而

所示陰影區(qū)則有可能。第二、目標(biāo)函數(shù)

Z=ax1+bx2的值遞增的方向與系數(shù)a、b有關(guān)

下圖表示目標(biāo)函數(shù)值遞增方向與其系數(shù)a、b的關(guān)系，其中箭頭所指為目標(biāo)函數(shù)值遞增的方向。圖解法小結(jié)

使用條件：僅有兩個至多不超過三個決策變量的線性規(guī)劃?；静襟E：第一步－－建立平面直角坐標(biāo)系；第二步－－根據(jù)約束條件和非負(fù)條件畫出可行域。第三步－－作出目標(biāo)函數(shù)等值線（至少兩條），結(jié)合目標(biāo)函數(shù)優(yōu)化要求，平移目標(biāo)函數(shù)等值線求出最優(yōu)解。圖解法的優(yōu)缺點(diǎn)：簡單、直觀但有局限性。

第一次作業(yè)——P69習(xí)題1：1-2；P701-3

三、基本可行解的幾何意義1、

討論課堂練習(xí)1-2（1）觀察圖解法求解圖，其中點(diǎn)I、H、G均在第一象限，它們是基本解，但不是基本可行解，這與基本可行解非負(fù)性有無矛盾？（2）如何求得基本解？第一步

模型標(biāo)準(zhǔn)化；第二步

按照基本解的定義①

找基（非退化3階方陣）——

多少個？不超過，為什麼？怎麼找？②

確定基變量和非基變量；③

令非基變量為0，解出基變量；④基變量和相應(yīng)非基變量搭配構(gòu)成基本解；求解結(jié)果：

H(6,4,-6,0,0)T,C(3,1,0,3,0)T,B(2,2,0,0,2)T,D(2,0,2,4,0)T,F(-2,0,6,0,4)T,I(4,0,0,6,-2)T,E(0,-2,6,6,0)T,A(0,1,3,0,3)T,G(0,4,0,-8,6)T,O(0,0,4,2,2)T2、結(jié)論：

(1)基本解對應(yīng)所有可行域邊界延長線、坐標(biāo)軸之間的交點(diǎn)；

(2)基本可行解對應(yīng)可行域的頂點(diǎn)。

1、基本概念：

凸集——設(shè)K是n維歐氏空間的一個點(diǎn)集，若任意兩點(diǎn)X（1）∈K，X（2）∈K的連線上的一切點(diǎn)：

αX（1）+（1-α）X（2）∈

K

（0<α<1），則稱K為凸集。

四、線性規(guī)劃解的性質(zhì)

凸組合——設(shè)X（1），X（2），…，X（k）是n維歐氏空間中的K個點(diǎn)，若存在k個數(shù)μ1，μ2，…，μk,滿足

0≤μi≤1,i=1,2,…,k；，則稱X=μ1X（1）+μ2X（2）+…+μkX(k)為X（1）,

，X（2），…，X（k）的凸組合。

頂點(diǎn)——設(shè)K是凸集，XK；若X不能用

X（1）

K，X（2）

K的線性組合表示，即

X≠αX（1）+（1-α）X（2）（0<α<1）則稱X為K的一個頂點(diǎn)（也稱為極點(diǎn)或角點(diǎn)）。

從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。上圖中的(a)(d)(e)是凸集，(b)(c)不是凸集。下圖中的(a)(b)是凸集，(c)不是凸集。2、線性規(guī)劃問題解的性質(zhì)定理：

定理1-1

線性規(guī)劃問題的可行解集（即可行域）是凸集。

證明思路：根據(jù)凸集定義，采用直接法證明；具體步驟：①從D中任取兩個不同的點(diǎn)，應(yīng)滿足可行解定義中相應(yīng)的條件；②證明X=αX(1)+(1-α)X(2)∈D(利用①，證明X滿足凸集定義中相應(yīng)的條件)

定理1-2

線性規(guī)劃幾何理論基本定理若，則X是D的一個頂點(diǎn)的充分必要條件是X為線性規(guī)劃的基本可行解。證明思路：定理1-2是X是D的一個頂點(diǎn)<=>X為LP的基本可行解;

引理是X為LP的基本可行解<=>X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān);從而將問題轉(zhuǎn)化為X是D的一個頂點(diǎn)<=>

X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)定理1-3

若可行域非空有界，則線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)值。證明思路：首先可行域非空有界就肯定有最優(yōu)解本定理要證明的是設(shè)在非頂點(diǎn)X處取得最優(yōu)值，則存在頂點(diǎn)X（1）和X（2）也取得相同的最優(yōu)值。定理1-4

若目標(biāo)函數(shù)在k個點(diǎn)處達(dá)到最優(yōu)值（k≥2）,則