線性規(guī)劃的圖解法和標(biāo)準(zhǔn)化

線性規(guī)劃的圖解法和標(biāo)準(zhǔn)化第一頁(yè)，共二十三頁(yè)，編輯于2023年，星期三1例1.目標(biāo)函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標(biāo)值z(mì)=27500§1圖解法

對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問(wèn)題的有關(guān)概念，并求解。下面通過(guò)例1詳細(xì)講解其方法：第二頁(yè)，共二十三頁(yè)，編輯于2023年，星期三2幾何概念代數(shù)概念直線滿足一個(gè)等式約束的解半平面滿足一個(gè)不等式約束的解半平面的交集：凸多邊形滿足一組不等式約束的解目標(biāo)函數(shù)等值線：一組平行線目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解§1圖解法注：當(dāng)目標(biāo)函數(shù)求極大時(shí)，等值線向右移；當(dāng)目標(biāo)函數(shù)求極小時(shí)，等值線向左移。第三頁(yè)，共二十三頁(yè)，編輯于2023年，星期三3§1圖解法

(1)分別取決策變量X1和X2為橫軸和縱軸，建立直角坐標(biāo)系。在直角坐標(biāo)系中，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組取值，例1的每個(gè)約束條件都代表一個(gè)半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第四頁(yè)，共二十三頁(yè)，編輯于2023年，星期三4§1圖解法（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第五頁(yè)，共二十三頁(yè)，編輯于2023年，星期三5§1圖解法（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖3-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖3-1第六頁(yè)，共二十三頁(yè)，編輯于2023年，星期三6§1圖解法（4）目標(biāo)函數(shù)Z=50x1+100x2，當(dāng)Z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，Z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件，則其可行域的頂點(diǎn)也是有限的。x1x2z=20000=50x1+100x2圖3-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第七頁(yè)，共二十三頁(yè)，編輯于2023年，星期三7例2max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860x1x2§1圖解法第八頁(yè)，共二十三頁(yè)，編輯于2023年，星期三8進(jìn)一步討論例3

某公司由于生產(chǎn)需要，共需要A、B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購(gòu)進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)格為2萬(wàn)元，每噸B原料的價(jià)格為3萬(wàn)元，試問(wèn)在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買A、B兩種原料，使得購(gòu)進(jìn)成本最低？第九頁(yè)，共二十三頁(yè)，編輯于2023年，星期三9進(jìn)一步討論解：目標(biāo)函數(shù)：MinZ=2x1+3x2

約束條件：

s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

采用圖解法，如左圖：得Q點(diǎn)坐標(biāo)（250，100）為最優(yōu)解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q第十頁(yè)，共二十三頁(yè)，編輯于2023年，星期三10重要結(jié)論1：線性規(guī)劃的可行域是凸集可行域的頂點(diǎn)為有限個(gè)線性規(guī)劃的最優(yōu)解一定可以在某個(gè)頂點(diǎn)上實(shí)現(xiàn)凸集凸集不是凸集頂點(diǎn)§1圖解法第十一頁(yè)，共二十三頁(yè)，編輯于2023年，星期三11§1圖解法重要結(jié)論2：如果線性規(guī)劃有唯一最優(yōu)解（例1、2、3），則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)最優(yōu)解；無(wú)窮多個(gè)最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙axz=50x1+50x2，則線段BC上的所有點(diǎn)都代表最優(yōu)解；無(wú)界解。即可行域的范圍延伸到無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú)窮小。一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件；無(wú)可行解。若在例1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x2≥1200，則可行域?yàn)榭沼?，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解。第十二頁(yè)，共二十三頁(yè)，編輯于2023年，星期三12§2線性規(guī)劃的標(biāo)準(zhǔn)化一般形式目標(biāo)函數(shù)：Max（Min）Z=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：MaxZ=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn

≥0，bi≥0

注：只能使用一個(gè)腳碼（變量連續(xù)編號(hào)），不能使用多重腳碼第十三頁(yè)，共二十三頁(yè)，編輯于2023年，星期三13§2線性規(guī)劃的標(biāo)準(zhǔn)化可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)極大化；約束條件為等式；決策變量均非負(fù)；約束條件右端常數(shù)項(xiàng)非負(fù)。對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:第十四頁(yè)，共二十三頁(yè)，編輯于2023年，星期三14§2線性規(guī)劃的標(biāo)準(zhǔn)化1、變量不是大于等于0的問(wèn)題（1）若xj≤0,令xj’=-xj，則xj’≥0（2）若變量為無(wú)約束在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量xj沒(méi)有非負(fù)約束時(shí)，可以令：

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然xj的符號(hào)取決于xj’和xj”的大小。第十五頁(yè)，共二十三頁(yè)，編輯于2023年，星期三15§2線性規(guī)劃的標(biāo)準(zhǔn)化2、目標(biāo)函數(shù)為極小化的問(wèn)題：設(shè)目標(biāo)函數(shù)為：

MinZ=c1x1

+c2x2

+…+cnxn

(可以)令Z’

＝-Z

，則該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即：MaxZ’=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即：

MinZ

＝-MaxZ’3、右端常數(shù)項(xiàng)為負(fù)數(shù)的問(wèn)題：在標(biāo)準(zhǔn)形式中，要求約束條件右端常數(shù)項(xiàng)必須全部是非負(fù)的。當(dāng)某個(gè)右端常數(shù)項(xiàng)為負(fù)時(shí)，如bi<0，則把該約束條件兩端同時(shí)乘以(-1)，得到：-ai1x1-ai2x2-…-ainxn

=-bi第十六頁(yè)，共二十三頁(yè)，編輯于2023年，星期三16§2線性規(guī)劃的標(biāo)準(zhǔn)化4、約束條件不是等式的問(wèn)題：設(shè)約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進(jìn)一個(gè)新的變量s

，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)顯然，s

也具有非負(fù)約束，即：s≥0，這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=bi第十七頁(yè)，共二十三頁(yè)，編輯于2023年，星期三17§2線性規(guī)劃的標(biāo)準(zhǔn)化當(dāng)約束條件為

ai1x1+ai2x2+…+ainxn

≥bi

時(shí)，類似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

顯然，s

也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi第十八頁(yè)，共二十三頁(yè)，編輯于2023年，星期三18§2線性規(guī)劃的標(biāo)準(zhǔn)化

為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于”時(shí)稱為“松弛變量”；當(dāng)不等式為“大于等于”時(shí)稱為“剩余變量”。如果原問(wèn)題中有若干個(gè)非等式約束條件，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束條件引進(jìn)不同的松弛變量或剩余變量。

結(jié)論：當(dāng)約束條件為：“≤”：在約束條件的左端加入非負(fù)的松弛變量“≥”：在約束條件的左端減去非負(fù)的剩余變量注：****松弛變量和剩余變量在目標(biāo)函數(shù)中的系數(shù)為0****第十九頁(yè)，共二十三頁(yè)，編輯于2023年，星期三19例4：將下列線性規(guī)劃模型標(biāo)準(zhǔn)化：§2線性規(guī)劃的標(biāo)準(zhǔn)化第二十頁(yè)，共二十三頁(yè)，編輯于2023年，星期三20§2線性規(guī)劃的標(biāo)準(zhǔn)化第二十一頁(yè)，共二十三頁(yè)，編輯于2023年，星期三21§2線性規(guī)劃的標(biāo)準(zhǔn)化例5：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤6