第二章線性規(guī)劃問題解的性質(zhì)演示文稿

第二章線性規(guī)劃問題解的性質(zhì)演示文稿當(dāng)前第1頁\共有34頁\編于星期五\9點(diǎn)優(yōu)選第二章線性規(guī)劃問題解的性質(zhì)ppt當(dāng)前第2頁\共有34頁\編于星期五\9點(diǎn)§2.1兩個(gè)變量的線性規(guī)劃問題的圖解法當(dāng)前第3頁\共有34頁\編于星期五\9點(diǎn)1.二元一次不等式表示平面區(qū)域§2.1兩個(gè)變量的線性規(guī)劃問題的圖解法問題1：x+y-1＞0以二元一次不等式x+y-1

＞0的xy11ol：x+y-1=0xy11ol：x+y-1=0x+y-1＜0以二元一次方程x+y-1=0的解為坐標(biāo)點(diǎn)的集合表示什么圖形？問題2：解為坐標(biāo)點(diǎn)的集合表示什么圖形？當(dāng)前第4頁\共有34頁\編于星期五\9點(diǎn)x+y=0A練習(xí)畫出不等式組表示的平面區(qū)域。解：①畫直線x-y+5=0，確定不等式x-y+5≥0表示的區(qū)域；②畫直線x+y=0，確定不等式x+y≥0表示的區(qū)域；③畫直線x=3，確定不等式x≤3表示的區(qū)域；④取公共區(qū)域部分。xyo24-2-424x-y+5=0x=3BC當(dāng)前第5頁\共有34頁\編于星期五\9點(diǎn)基本概念：(1)z=2x+y(3).象此問題一樣，求線性目標(biāo)函數(shù)在線性約束條件下的最值的問題統(tǒng)稱為線性規(guī)劃問題。(4).滿足約束條件的解(x，y)叫做可行解。(5).可行解組成的集合叫做可行域。（陰影部分）(6).使目標(biāo)函數(shù)取得最值的可行解叫做最優(yōu)解。目標(biāo)函數(shù)，也叫線性目標(biāo)函數(shù)。(2).線性約束條件。x-4y+3=03x+5y-25=0x=12x+y=t1xyo可行域A（5，2）B（1，1）當(dāng)前第6頁\共有34頁\編于星期五\9點(diǎn)例2.1

maxs=2x1+5x2x1Ox2再作：

x1≤4

x2≤3x1+2x2≤8

對于僅具有兩個(gè)變量的線性規(guī)劃問題，利用作圖的方法求最優(yōu)解，簡單、直觀。約束條件2.兩個(gè)變量的線性規(guī)劃問題的圖解法一般過程ABCD解(1).確定可行域先作:

x1≥0

x2≥0得可行域(見上圖)當(dāng)前第7頁\共有34頁\編于星期五\9點(diǎn)ABCDOx12x1+5x2=192x1+5x2=0x2由小到大給s

賦值，可得一

組平行線，而

位于同一直線

上的點(diǎn)具有相

同的目標(biāo)函數(shù)

值，因而稱為

等值線。(2).作目標(biāo)函數(shù)的等值線目標(biāo)函數(shù)s=2x1+5x2

它代表是以s為參數(shù)

的一族平行線當(dāng)前第8頁\共有34頁\編于星期五\9點(diǎn)相應(yīng)的目標(biāo)函數(shù)的最大值為

S=2×2+5×3=19.(3).確定最優(yōu)點(diǎn)先確定目標(biāo)函數(shù)值增大的方向，沿著這個(gè)方向平行移動(dòng)直線s=2x1+5x2，當(dāng)移動(dòng)到B點(diǎn)時(shí)，s值就在可行域上達(dá)到最大,從而確定B點(diǎn)就是最優(yōu)點(diǎn)，得最優(yōu)解為x1=2，x2=3。ABCDOx12x1+5x2=192x1+5x2=0x2當(dāng)前第9頁\共有34頁\編于星期五\9點(diǎn)ABCDOx1x1+2x2=8x2例2.2若將例2.1中的目標(biāo)函數(shù)改為S=x1+2x2BC邊上每一點(diǎn)的坐標(biāo)都是最優(yōu)解因此，最優(yōu)解有無窮多個(gè)。當(dāng)前第10頁\共有34頁\編于星期五\9點(diǎn)例2.3、若目標(biāo)函數(shù)為mins=2x1+2x2解⑴確定可行域約束條件為Ox2x1ABCD當(dāng)前第11頁\共有34頁\編于星期五\9點(diǎn)Ox2x12x1+2x2=102x1+2x2=22x1+2x2=6CBAD相應(yīng)的目標(biāo)函數(shù)最小值為s=2。因此，最優(yōu)解為x1=1,x2=0⑵作目標(biāo)函數(shù)的等值線⑶確定最優(yōu)點(diǎn)例2.3、若目標(biāo)函數(shù)為mins=2x1+2x2當(dāng)前第12頁\共有34頁\編于星期五\9點(diǎn)

例2.4、若將例2.3改為使目標(biāo)函數(shù)的值最大，即maxs=2x1+2x2從圖中可以看出，因?yàn)橥褂駻BCD無界，當(dāng)平行直線族的直線無限遠(yuǎn)離原點(diǎn)時(shí)，都可以與ABCD相交，所以目標(biāo)函數(shù)無上界，因此無最優(yōu)解。2x1+2x2=2Ox2x12x1+2x2=102x1+2x2=6CBAD當(dāng)前第13頁\共有34頁\編于星期五\9點(diǎn)例2.5、mins=2x1+2x2Ox1x2-x1+x2=1x1+x2=-2如圖，沒有可行解，故沒有最優(yōu)解。當(dāng)前第14頁\共有34頁\編于星期五\9點(diǎn)線性規(guī)劃問題解的四種情況：兩個(gè)重要結(jié)論：

★線性規(guī)劃問題的任意兩個(gè)可行解連線上的點(diǎn)都是可行解；

★線性規(guī)劃問題的最優(yōu)值如果存在，必然可在某個(gè)“頂點(diǎn)”達(dá)到。以后證明.當(dāng)前第15頁\共有34頁\編于星期五\9點(diǎn)§2.2線性規(guī)劃問題的標(biāo)準(zhǔn)形式(1)目標(biāo)函數(shù)，有的要求最大化，有的要求最小化；(2)約束條件也有多種形式LP問題有許多不同形式：這種多樣性不僅給研究帶來不便，而且使你難以尋找一種通用解法。人們發(fā)現(xiàn)：線性規(guī)劃問題的各種不同形式可以相互轉(zhuǎn)化。因此，只需給出一種形式的解法。當(dāng)前第16頁\共有34頁\編于星期五\9點(diǎn)矩陣表示min

s=cx其中c=(c1，c2，…，cn)mins=c1x1+c2x2+…+cnxn線性規(guī)劃問題的標(biāo)準(zhǔn)形式如下：價(jià)值向量資源向量約束矩陣待定決策向量當(dāng)前第17頁\共有34頁\編于星期五\9點(diǎn)mins=cx向量表示min

s=cxLP問題當(dāng)前第18頁\共有34頁\編于星期五\9點(diǎn)非標(biāo)準(zhǔn)形問題的標(biāo)準(zhǔn)化下面舉例說明如何將非標(biāo)準(zhǔn)形線性規(guī)劃問題化為標(biāo)準(zhǔn)形。（1）目標(biāo)函數(shù)若問題的目標(biāo)函數(shù)為最大化maxs=cx，（2）約束條件約束為≤形式的情形。如2x1-x2+3x3≤18變量x4稱為松弛變量。則加入一個(gè)非負(fù)變量x4≥0，改為：2x1-x2+3x3+x4=18則可化為求mins’=－cx，即可。當(dāng)前第19頁\共有34頁\編于星期五\9點(diǎn)約束為≥形式的情形。如c)若對某變量xj沒有非負(fù)限制，3x1+2x2-x4≥18則減去一個(gè)非負(fù)變量x5≥0，改為3x1+2x2-x4-x5=18變量x5稱為剩余變量。則引進(jìn)兩個(gè)非負(fù)變量xj’

≥0，xj’’

≥0，令xj=xj’

-xj’’

代入約束條件和目標(biāo)函數(shù)中，化為對全部變量都有非負(fù)限制。自由變量當(dāng)前第20頁\共有34頁\編于星期五\9點(diǎn)例2.6將下面的線性規(guī)劃問題化為標(biāo)準(zhǔn)形：

maxs=x1+2x2-3x3

解引進(jìn)非負(fù)變量x4，x5，x6，則原問題的標(biāo)準(zhǔn)形為：松弛變量剩余變量當(dāng)前第21頁\共有34頁\編于星期五\9點(diǎn)1.可行解、基礎(chǔ)可行解、最優(yōu)解、基礎(chǔ)最優(yōu)解設(shè)線性規(guī)劃問題mins=cx§2.3線性規(guī)劃問題解的性質(zhì)（一）幾個(gè)概念我們把滿足約束條件的稱為LP問題的可行解。若x(0)=0，或x

(0)的非零分量所對應(yīng)的系數(shù)列向量組線性無關(guān)時(shí)，稱可行解x

(0)為基礎(chǔ)可行解。使目標(biāo)函數(shù)取最小值的基礎(chǔ)可行解，稱為基礎(chǔ)最優(yōu)解。使目標(biāo)函數(shù)取最小值的可行解，稱為最優(yōu)解。當(dāng)前第22頁\共有34頁\編于星期五\9點(diǎn)例如：若對于x

(1)，x

(2)∈S，x=α

x

(1)+(1-α)x

(2)∈S（0≤α≤1），則稱S為凸集。連接n維點(diǎn)集合S中任意兩點(diǎn)x

(1)，x

(2)的線段仍在S內(nèi)，則稱S為凸集。即2.凸集點(diǎn)集中任意兩點(diǎn)的連線段整個(gè)均是該點(diǎn)集的點(diǎn)，稱該點(diǎn)集為凸集。x

(1)x

(2)x

(1)x

(2)x

(1)x

(2)x

(1)x

(2)x

(1)x

(2)當(dāng)前第23頁\共有34頁\編于星期五\9點(diǎn)3.極點(diǎn)(頂點(diǎn))若凸集S中的點(diǎn)x，不能成為S中的內(nèi)點(diǎn)，則稱x為S的極點(diǎn)（頂點(diǎn)）。即，

若對于x

(1)

x

(2)∈S,不存在α(0<α<1),使

x=αx

(1)+(1-α)x

(2)

則稱x為S的極點(diǎn)（頂點(diǎn)）。當(dāng)前第24頁\共有34頁\編于星期五\9點(diǎn)（二）線性規(guī)劃問題解的性質(zhì)定理1線性規(guī)劃問題的可行解集（可行域）為凸集。設(shè)LP問題:mins=cx證對于x

(1)

x

(2)∈S,α[0,1]S是其可行域，考查x=αx

(1)+(1-α)x

(2)∈S當(dāng)前第25頁\共有34頁\編于星期五\9點(diǎn)定理2

x是基礎(chǔ)可行解x是可行域S中的極點(diǎn).（二）線性規(guī)劃問題解的性質(zhì)設(shè)LP問題:mins=cx證S是其可行域，“”即若x是可行域S中的極點(diǎn)，則x是基礎(chǔ)可行解.反證法當(dāng)前第26頁\共有34頁\編于星期五\9點(diǎn)定理2

x是基礎(chǔ)可行解x是可行域S中的極點(diǎn).反證法由此取當(dāng)前第27頁\共有34頁\編于星期五\9點(diǎn)定理2

x是基礎(chǔ)可行解x是可行域S中的極點(diǎn).反證法由此取構(gòu)造充分性得證！當(dāng)前第28頁\共有34頁\編于星期五\9點(diǎn)定理2

x是基礎(chǔ)可行解x是可行域S中的極點(diǎn).反證法由此取當(dāng)前第29頁\共有34頁\編于星期五\9點(diǎn)定理2

x是基礎(chǔ)可行解x是可行域S中的極點(diǎn).“”即若x是基礎(chǔ)可行解，則x是可行域S中的極點(diǎn).設(shè)LP問題:mins=cx證S是其可行域，反證法若x不是可行域S中的極點(diǎn).x

(1)

x

(2)∈S,α(0,1),使得x=αx

(1)+(1-α)x

(2)當(dāng)前第30頁\共有34頁\編于星期五\9點(diǎn)定理2

x是基礎(chǔ)可行解x是可行域S中的極點(diǎn).“”即若x是基礎(chǔ)可行解，則x是可行域S中的極點(diǎn).設(shè)LP問題:mins=cx