第二章線性規(guī)劃

1第二章線性規(guī)劃

線性規(guī)劃內(nèi)容框架2第二章線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃LinearProgramming

LP規(guī)劃論中的靜態(tài)規(guī)劃在有限資源的條件下，合理分配和利用資源，以期取得最佳效益的優(yōu)化方法。求解方法：圖解法單純形解法

3第一部分

線性規(guī)劃的數(shù)學(xué)模型第二章線性規(guī)劃

第一節(jié)線性規(guī)劃一般模型第二節(jié)線性規(guī)劃的圖解法第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型第四節(jié)線性規(guī)劃解的概念第二部分

線性規(guī)劃的單純形法Homework4現(xiàn)有三個(gè)倉(cāng)庫(kù)（A,B,C）的產(chǎn)品運(yùn)往四個(gè)紡織廠。運(yùn)費(fèi)情況如下：

問應(yīng)當(dāng)怎樣調(diào)運(yùn)使運(yùn)費(fèi)最??？5一、線性規(guī)劃問題的三要素

決策變量決策問題待定的量值稱為決策變量。決策變量的取值要求非負(fù)。約束條件任何問題都是限定在一定的條件下求解，把各種限制條件表示為一組等式或不等式，稱之為約束條件。約束條件是決策方案可行的保障。LP的約束條件，都是決策變量的線性函數(shù)。目標(biāo)函數(shù)衡量決策方案優(yōu)劣的準(zhǔn)則，如時(shí)間最省、利潤(rùn)最大、成本最低。有的目標(biāo)要實(shí)現(xiàn)極大，有的則要求極小。目標(biāo)函數(shù)是決策變量的線性函數(shù)。第一節(jié)線性規(guī)劃一般模型6二、線性規(guī)劃的定義第一節(jié)線性規(guī)劃一般模型對(duì)于求取一組變量xj

(j=1,2,......,n)，使之既滿足線性約束條件，又使具有線性表達(dá)式的目標(biāo)函數(shù)取得極值（極大值或極小值）的一類最優(yōu)化問題稱為線性規(guī)劃問題，簡(jiǎn)稱線性規(guī)劃。7

某飲料公司在國(guó)內(nèi)有三個(gè)生產(chǎn)廠，分布在城市A1、A2、A3,其一級(jí)承銷商有4個(gè)，分布在城市B1、B2、B3、B4，已知各廠的產(chǎn)量、各承銷商的銷售量及從Ai到Bj的每噸飲料運(yùn)費(fèi)為Cij，為發(fā)揮集團(tuán)優(yōu)勢(shì)，公司要統(tǒng)一籌劃運(yùn)銷問題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3632575843297523銷量2314第一節(jié)線性規(guī)劃一般模型例1.運(yùn)輸問題二、線性規(guī)劃模型的構(gòu)建8(1)決策變量。

決策的是調(diào)運(yùn)量，因此決策變量為：從Ai到Bj的運(yùn)輸量為xij，(2)目標(biāo)函數(shù)。運(yùn)費(fèi)最小的目標(biāo)函數(shù)為minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)約束條件。產(chǎn)量之和等于銷量之和,故要滿足：x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3銷售平衡條件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4供應(yīng)平衡條件非負(fù)性約束xij≥0(i=1,2,3；j=1,2,3,4)

第一節(jié)線性規(guī)劃一般模型9minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

綜上所述，該問題的數(shù)學(xué)模型表示為

x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4xij≥0(i=1,2,3；j=1,2,3,4)

s.t.第一節(jié)線性規(guī)劃一般模型subjectto10某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：產(chǎn)品A產(chǎn)品B資源限量勞動(dòng)力設(shè)備原材料9434510360200300利潤(rùn)元/kg70120例2.生產(chǎn)計(jì)劃問題第一節(jié)線性規(guī)劃一般模型11問題：如何安排生產(chǎn)計(jì)劃，使得獲利最多？步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg；B產(chǎn)品x2kg2、確定目標(biāo)函數(shù)：maxZ=70X1+120X23、確定約束條件：勞動(dòng)力約束9X1+4X2≤360

設(shè)備約束4X1+5X2

≤200

原材料約束3X1+10X2

≤300

非負(fù)性約束X1≥0X2≥0第一節(jié)線性規(guī)劃一般模型補(bǔ)例.教材P1712用一組非負(fù)決策變量表示一個(gè)決策問題，存在一定的等式或不等式的線性約束條件，有一個(gè)希望達(dá)到的目標(biāo)，可表示成決策變量的線性函數(shù)?？赡苁亲畲蠡?，也可能是最小化。線性規(guī)劃一般模型的代數(shù)式為：四、線性規(guī)劃的一般模型

max(min)Z=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤(≥,＝)b1a21x1+a22x2+…+a2nxn≤(≥,＝)b2……………am1x1+am2x2+…+amnxn≤(≥,＝)bmx1,x2,…,xn≥(≤)0第一節(jié)線性規(guī)劃一般模型13用圖示的方法來求解線性規(guī)劃問題。一個(gè)二維的線性規(guī)劃問題，可以在平面圖上求解，三維的線性規(guī)劃則要在立體圖上求解，而維數(shù)再高以后就不能圖示了。一、圖解法的基本步驟第二節(jié)LP問題的圖解法可行域的確定可行解最優(yōu)解141.可行域的確定例3的數(shù)學(xué)模型為

maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D五邊形OABCD內(nèi)(含邊界)的任意一點(diǎn)(x1，x2)都是滿足所有約束條件的一個(gè)解，稱之可行解。滿足所有約束條件的解的集合，稱之為可行域。即所有約束條件共同圍城的區(qū)域。第二節(jié)LP問題的圖解法152.最優(yōu)解的確定Z=30Z=42Z=15目標(biāo)函數(shù)Z=

3x1+5x2代表以Z為參數(shù)的一族平行線。x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D等值線：位于同一直線上的點(diǎn)的目標(biāo)函數(shù)值相同。最優(yōu)解：可行解中使目標(biāo)函數(shù)最優(yōu)(極大或極小)的解第二節(jié)LP問題的圖解法?16由線性不等式組成的可行域是凸集(凸集的定義是：集合內(nèi)部任意兩點(diǎn)連線上的點(diǎn)都屬于這個(gè)集合)?？尚杏蛴杏邢迋€(gè)頂點(diǎn)。設(shè)規(guī)劃問題有n個(gè)變量，m個(gè)約束，則頂點(diǎn)的個(gè)數(shù)不多于Cnm個(gè)。目標(biāo)函數(shù)最優(yōu)值（如果存在）一定在可行域的邊界達(dá)到，而不可能在其內(nèi)部。二、說明第二節(jié)LP問題的圖解法17例: 求解下列線性規(guī)劃問題

MaxZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20第二節(jié)LP問題的圖解法18X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20X2

0X1

019第二節(jié)LP問題的圖解法唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn)。多重最優(yōu)解：無窮多個(gè)最優(yōu)解。若在兩個(gè)相鄰頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線上的每一點(diǎn)都是最優(yōu)解。無界解：線性規(guī)劃問題的可行域無界，使目標(biāo)函數(shù)無限增大而無界。（缺乏必要的約束條件）。無可行解：若約束條件相互矛盾，則可行域?yàn)榭占６?、解的可能?0X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20唯一的最優(yōu)解X1

0X2

021X1X1=1X1=6X2=4X2X1+2X2=10ABCDE

MAXZ=2X1+4X2

S.T.X1+2X210X16X24X11X1,X202X1+4X2=Ω存在無窮多解MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20X1

0X2

022X1X1=1X1=6X2=4X2X1+2X2=0ADE4X1-3X2=0MAXZ=4X1-3X2

S.T.X1+2X20X16X24X11X1,X20可行域無界MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20X1

0X2

023X1X1=1X2X1+2X2=104X1-3X2=0MAXZ=4X1-3X2

S.T.X1+2X2

10X11X1,X20MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20可行域無界X1

0X2

024線性規(guī)劃問題的數(shù)學(xué)模型有各種不同的形式，如目標(biāo)函數(shù)有極大化和極小化；約束條件有“≤”、“≥”和“＝”三種情況；決策變量一般有非負(fù)性要求，有的則沒有。為了求解方便，特規(guī)定一種線性規(guī)劃的標(biāo)準(zhǔn)形式，非標(biāo)準(zhǔn)型可以轉(zhuǎn)化為標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)形式為：目標(biāo)函數(shù)極大化，約束條件為等式，右端常數(shù)項(xiàng)bi≥0，決策變量非負(fù)。一、標(biāo)準(zhǔn)型第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型25第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型26minZ=X1+3X2S.T.6X1+7X28-X1+3X2-6X1-X2=3X10不符合線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)“極小值”約束方程右端存在負(fù)數(shù)約束方程還不是等式約束

存在自由變量X2第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型271.代數(shù)式二、標(biāo)準(zhǔn)型的表達(dá)方式（代數(shù)式、矩陣式）maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0maxZ=cjxjaijxj＝bi

(i=1,2,…,m)xj≥0(j=1,2,…,n)簡(jiǎn)記第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型282.矩陣式

第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型29目標(biāo)函數(shù)極小化問題

minZ=CX，只需將等式兩端乘以-1即變?yōu)闃O大化問題。因?yàn)閙inZ=-max(-Z)=CX，令Z′=-Z，則maxZ′=-CX右端常數(shù)項(xiàng)非正兩端同乘以-1約束條件為不等式當(dāng)約束方程為“≤”時(shí)，左端加入一個(gè)非負(fù)的松弛變量，就把不等式變成了等式；當(dāng)約束條件為“≥”時(shí)，不等式左端減去一個(gè)非負(fù)的剩余變量(也可稱松弛變量)即可。

決策變量xk沒有非負(fù)性要求令xk=xk′-xk〃，xk′≥0，xk〃≥0，用xk′-xk〃

取代模型中xk三、非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化

第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型30目標(biāo)函數(shù)標(biāo)準(zhǔn)化示意圖&目標(biāo)函數(shù)極小化/右端常數(shù)項(xiàng)非正

——兩邊同乘-1&約束條件是≤類型

——左邊加非負(fù)松弛變量

&約束條件是≥類型

——左邊減非負(fù)剩余變量

&變量符號(hào)不限

——引入新變量

轉(zhuǎn)化規(guī)則簡(jiǎn)要：第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型31例3minZ=

x1+2x2-3x3x1+2x2-x3≤52x1+3x2-x3≥6

-x1-x2+x3≥-2x1≥0,x3≤0S.t.第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型Step-1minZ=

x1+2x2+3x3′x1+2x2+x3′≤52x1+3x2+x3′≥6

-x1-x2-x3′≥-2x1≥0,x3′≥0

S.t.32Step-2minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)

+x3′≥6

-x1-(x2′-x2〃)

-x3′≥-2x1,

x2′,x2〃

,x3′≥0

Step-3minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃

)

+x3

′≤2x1,

x2′,x2〃,x3′≥0第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型S.t.S.t.33Step-4minZ=

x1+2(x2′-x2〃)

+3x3′

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4≥0Step-5minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=5

2x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4,x5≥0第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型S.t.S.t.34Step-6minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

-x3′+x6=2

x1,

x2′,x2〃,x3′,x4,x5,x6

≥0Step-7maxZ=-x1-2(x2′-x2〃)

-3x3′+0x4+0x5+0x6

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

-x3′+x6=2x1,

x2′,x2〃,x3′,x4,x5,x6≥0

第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型S.t.S.t.35例4maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0maxZ=

3x1+5x2+0x3+0x4+0x5

S.t.標(biāo)準(zhǔn)型作業(yè)：

1、教材后作業(yè)9（建立數(shù)學(xué)模型）2、教材后作業(yè)1（化標(biāo)準(zhǔn)型）3、教材后作業(yè)2的①（圖解法）37第四節(jié)LP問題的基本性質(zhì)一．LP解的基本概念可行解：滿足約束條件AX=b,X≥0的解。最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。基n元線性約束方程組，m個(gè)方程線性無關(guān)；即矩陣A的秩R(A)=m；根據(jù)線性代數(shù)定理可知，n＞m，則方程組有多個(gè)解，這也正是線性規(guī)劃尋求最優(yōu)解的余地所在。?秩的定義n元線性方程組Ax=b解的討論X1X1=1X1=6X2=4X2X1+2X2=10ABCDEMAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20X2

0X1

0可行域可行解39線性方程組的增廣矩陣?yán)?的標(biāo)準(zhǔn)型

maxZ=

3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0x1x2x3x4x5單位矩陣第四節(jié)LP問題的基本性質(zhì)40基（基矩陣）：系數(shù)矩陣A中任意m列所組成的m階非奇異子矩陣，稱為該線性規(guī)劃問題的一個(gè)基矩陣?；蚍Q為一個(gè)基，用B表示。稱基矩陣的列為基向量，用Pj表示(j=1,2,…,m)。的基矩陣B最多C53=10，如下：x3x4x5x1x4x5x2x4x5x3x1x5x3x2x5x3x4x1x3x4x2x1x2x5x