運籌學(xué) 一般線性規(guī)劃問題的數(shù)學(xué)模型

運籌帷幄之中決勝千里之外線性規(guī)劃LinearProgramming第一章線性規(guī)劃及單純形法一般線性規(guī)劃問題的數(shù)學(xué)模型圖解法單純形法原理單純形法的計算步驟單純形法的進(jìn)一步討論應(yīng)用舉例第一節(jié)一般線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的標(biāo)準(zhǔn)型及其標(biāo)準(zhǔn)化線性規(guī)劃問題解的含義一、線性規(guī)劃的發(fā)展1939年，前蘇聯(lián)數(shù)學(xué)家康托洛維奇用線性模型研究提高組織和生產(chǎn)效率問題1947年，Dantzig提出求解線性規(guī)劃的單純形法1950-1956年，主要研究線性規(guī)劃的對偶理論1958年，發(fā)表整數(shù)規(guī)劃的割平面法1960年，Dantzig和Wolfe研究成功分解算法，奠定了大規(guī)模線性規(guī)劃問題理論和算法的基礎(chǔ)。1979年，Khachiyan，1984年，Karmarkaa研究成功線性規(guī)劃的多項式算法。另外，很多現(xiàn)代算法研究如進(jìn)化、神經(jīng)網(wǎng)絡(luò)等。解：一般方法是在鐵皮的四個角上剪去四個邊長各為x的正方形，折疊做成一個容器，則容積為V=(a-2x)2·x。要讓容積最大即確定x(0≤x≤a)的值，使V達(dá)到最大。

ax圖1-1二、問題的提出例1.1用一塊長為a的正方形鐵皮做一個容器，應(yīng)如何剪裁，使做成的容器的容積為最大（見圖1-1）例1.2Maxz=2x1+3x22x1+2x2≤12

x1+2x2≤84x1≤164x2≤12

x1，x2≥0例1.3

某工廠在計劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表。問題：工廠應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠獲利最多？Maxz=50x1+100x2

x1+x2≤3002x1+x2≤400x2≤250

x1

，x2≥0例1.4套裁下料問題

某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根，已知原料每根長7.4m。應(yīng)如何下料，可使所用原料最??？解：共可設(shè)計下列5種下料方案設(shè)x1,x2,x3,x4,x5

分別為上面5種方案下料的原料根數(shù)。建立數(shù)學(xué)模型如下目標(biāo)函數(shù)：Minz=0.1x2+0.2x3+0.3x4+0.8x5

約束條件：s.t.x1+2x2+x4=1002x3+2x4+x5=1003x1+x2+2x3+3x5=100

x1,x2,x3,x4,x5≥0總結(jié)提出問題類似的例子可以舉出很多。歸結(jié)起來有兩種情況：一是給定資源，如何充分利用二是給定計劃，研究如何統(tǒng)籌安排，用最少的人力物力去完成都是求極值的問題，有些問題可以用微積分解決，但例中除了要求變量非負(fù)外帶了很多附加條件，解決這類問題就是運籌學(xué)中規(guī)劃論研究的內(nèi)容?！艟€性規(guī)劃的三個要素決策變量：（x1，x2），一組值代表一個方案目標(biāo)函數(shù)：max或min約束條件：不等式或等式◆線性規(guī)劃：目標(biāo)函數(shù)、約束條件均為線性函數(shù)三、線性規(guī)劃的數(shù)學(xué)模型1.一般形式?jīng)Q策變量：X=(x1,x2,…..,xn)T目標(biāo)函數(shù)：max(minz)=c1x1+c2x2+…+cnxn約束條件：

a11x1+a12x2+……..+a1nxn≤(=≥)b1

a21x1+a22x2+……..+a2nxn≤(=≥)b2

…………am1x1+am2x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0

其中，“max(minz)”是“maximize(minimize)的縮寫，含義為“最大化(最小化)”2.一般形式的其它寫法①求和形式②向量形式目標(biāo)函數(shù)：

Max（Min）z=CX約束條件：s.t.X≥0其中C=(c1,c2,…,cn)③矩陣形式?jīng)Q策變量常數(shù)項系數(shù)矩陣價值系數(shù)四、線性規(guī)劃數(shù)學(xué)模型的建立1.建模條件(1)優(yōu)化條件：問題所要達(dá)到的目標(biāo)能用線型函數(shù)描述，且能夠用極值（max或min）來表示；(2)限定條件：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的線性等式或線性不等式表示；(3)選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。2.建模步驟(1)確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目問什么就設(shè)什么為決策變量。(2)找出所有限定條件：即決策變量受到的所有的約束；(3)寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確是max還是min。例1.5混合配料問題某糖果廠用原料1、2、3加工三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中原料1、2、3的含量、原料每月限用量、三種牌號糖果的加工費及售價，如下表所示。該廠每月如何生產(chǎn)才能獲利最大？解:用i=1，2，3代表原料1、2、3，j=1，2，3代表糖果甲、乙、丙。xij表示第j種產(chǎn)品中原料i的含量，則對于原料1：x11，x12

，x13

；對于原料2：x21，x22，x23

；對于原料3：x31

，x32

，x33

；對于甲：x11

，x21

，x31

；對于乙：x12，x22，x32

；對于丙：x13

，x23

，x33

；目標(biāo)函數(shù)：利潤最大，利潤=收入-原料成本-加工費約束條件：原料用量限制，含量限制maxz=(3.4-0.5)(x11+x21+x31)+(2.85-0.4)(x11+x22+x32)+(2.25-0.3)(x13+x23+x33)-2(x11+x12+x13)-1.5(x21+x22+x23)-1(x31+x32+x33)x11+x12+x13≤2000(供應(yīng)量限制）

x21+x22+x23≤2500

x31+x32+x33≤1200x11≥0.6(x11+x21+x31)(含量限制）

x31≤0.2(x11+x21+x31)

x12≥0.3(x12+x22+x32)x32≤0.5(x11+x22+x32)x33≤0.6(x13+x23+x33)

xij≥0,i=1,2,3;j=1,2,3五、線性規(guī)劃的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：maxz=c1x1+c2x2+…+cnxn約束條件：

a11x1+a12x2+……..+a1nxn=b1

a21x1+a22x2+……..+a2nxn=b2

………………am1x1+am2x2+……..+amnxn=bmx1,x2,……xn≥0,b1,b2,……bm≥0◆非標(biāo)準(zhǔn)形式如何化為標(biāo)準(zhǔn)形式目標(biāo)函數(shù)極小化Minz=c1x1+c2x2+…+cnxn令z′=-z，則

Maxz′=（-c1x1）

+（-c2x2）

+…+（-cnxn）兩個問題最優(yōu)解相同，最優(yōu)值相差一個符號，即

Minz=-Maxz′約束條件為不等式ai1x1+ai2x2+…+ainxn≤bi引進(jìn)一個新的變量s，

s=bi–(ai1x1+ai2x2+…+ainxn)顯然，s≥0這時新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=biS——松弛變量，在實際問題中表示未被充分利用的資源數(shù)，未被轉(zhuǎn)化為價值和利潤，在目標(biāo)函數(shù)中系數(shù)為零.ai1x1+ai2x2+…+ainxn≥bi引進(jìn)一個新的變量t，

t=(ai1x1+ai2x2+…+ainxn)–bi顯然，t≥0這時新的約束條件成為

ai1x1+ai2x2+…+ainxn-t=bit——剩余變量，在實際問題中表示超用資源數(shù)，未被轉(zhuǎn)化為價值和利潤，在目標(biāo)函數(shù)中系數(shù)為零如約束條件為

2x1+2x2≤12可令x3=12-2x1-2x2則新的約束條件為

2x1+2x2+

x3=12x3為松弛變量，x3≥0如約束條件為

2x1+2x2≥

12可令x4=2x1+2x2-12則新的約束條件為

2x1+2x2-

x4=12x4為剩余變量，x4≥0右端項有負(fù)值如bi<0則把該等式約束兩端同時乘以-1，得到：

-ai1x1-ai2x2-…-ainxn=-bi

變量取負(fù)值如xi≤0，令xi'=-xi

，則xi'≥0變量無約束如x無約束，令x＝x′-x′′,其中x′≥

0，x′′≥0例1.6

將以下線性規(guī)劃問題化為標(biāo)準(zhǔn)形式

minZ=x1+2x2+3x3s.t.-2x1+x2+x3≤9-3x1+x2+2x3

≥43x1-2x2-3x3=-6x1≤0

,x2≥0

，x3取值無約束。解：首先令z′=-z，x3=x′3-x′′3，其中x′3≥

0,x′′3≥0，

x′1=－x1，其中x′1≥

0，考慮約束，引進(jìn)松弛變量x4≥0

、剩余變量x5≥0再次等式約束其右端項為負(fù)數(shù)，所以兩邊同乘以-1，得到-3x′1

+2x2+3x′3-3x′′3

=6問題轉(zhuǎn)化為：

maxZ′=x′1

-2x2-3x′3+3x′′3

+0x4+0x5s.t.2x′1

+x2+x′3-x′′3

+x4=93x′1

+x2+2x′3-2x′′3

-x5=43x′1

+2x2+3x′3-3x′′3

=6x′1,x2,x′3,x′′3,x4,x5≥0

練習(xí)1.6（a）解：首先令z′=-z，x2=x′2-x′′2，其中x′2≥

0,x′′2≥0，

x′3=－x3，其中x′3≥

0，考慮約束，引進(jìn)松弛變量x4≥0

、剩余變量x5≥0問題轉(zhuǎn)化為：

六、線性規(guī)劃問題的解對于線性規(guī)劃問題maxCTX（1.1a）

(LP)s.t.AX≤b（1.1b）

X≥0（1.1c）其中,C,XRn,bRm,Amn矩陣有以下幾個概念（單純形法中詳細(xì)介紹）：1.可行解(feasiblesolution)

滿足(1.1b)(1.1c)X=(x1,x2,…..,xn)T稱為線性規(guī)劃問題(LP)的可行解。全部可行解的集合稱為可行域。2.最優(yōu)解(optimalsolution)

使目標(biāo)函數(shù)(1.1a)達(dá)到最大值的可行解成為最優(yōu)解。3.基設(shè)n>m,A的秩為m。B是矩陣A中的一個mm階的滿秩矩陣，稱B是線性規(guī)劃問題的一個基。不失一般性，設(shè)

=(P1,···,Pm),B中的每一個列向量Pj(j=1,···m)稱為基向量，與基向量Pj對應(yīng)的變量xj稱為基變量。線性規(guī)劃除基變量以外的其他變量稱為非基變量。4.基解在約束方程組(1.1b)中，令所有非基變量xm+1=xm+2=··