線性規(guī)劃第一

關(guān)于線性規(guī)劃第一121.線性規(guī)劃的概念

例6.1:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示：

產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）15002500

第2頁,共42頁，2024年2月25日，星期天3

問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？解：設(shè)變量xi為第i種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i＝1，2）。根據(jù)題意，我們知道兩種產(chǎn)品的生產(chǎn)受到設(shè)備能力（機時數(shù)）的限制。對設(shè)備A，兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過65，于是我們可以得到不等式：3x1

+2x2

≤65；對設(shè)備B，兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過40，于是我們可以得到不等式：2x1

+x2

≤40；1.線性規(guī)劃的概念第3頁,共42頁，2024年2月25日，星期天4

對設(shè)備C，兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過75，于是我們可以得到不等式：3x2

≤75；另外，產(chǎn)品數(shù)不可能為負，即x1,x2≥0。同時，我們有一個追求目標，即獲取最大利潤。于是可寫出目標函數(shù)z為相應(yīng)的生產(chǎn)計劃可以獲得的總利潤：z=1500x1+2500x2

。綜合上述討論，在加工時間以及利潤與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下，把目標函數(shù)和約束條件放在一起，可以建立如下的線性規(guī)劃模型：1.線性規(guī)劃的概念第4頁,共42頁，2024年2月25日，星期天5目標函數(shù)

Maxz=1500x1+2500x2

約束條件

s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

1.線性規(guī)劃的概念第5頁,共42頁，2024年2月25日，星期天6

這是一個典型的利潤最大化的生產(chǎn)計劃問題。其中，“Max”是英文單詞“Maximize”的縮寫，含義為“最大化”；“s.t.”是“subjectto”的縮寫，表示“滿足于……”。因此，上述模型的含義是：在給定條件限制下，求使目標函數(shù)z達到最大的x1,x2

的取值。1.線性規(guī)劃的概念第6頁,共42頁，2024年2月25日，星期天7一般形式

目標函數(shù)：Max(Min)z=c1x1

+c2x2

+…+cnxn

約束條件：

a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2

...am1x1+am2x2

+…+amnxn≤(=,≥)bm

x1，x2，…，xn≥01.線性規(guī)劃的概念第7頁,共42頁，2024年2月25日，星期天8標準形式目標函數(shù)：Maxz=c1x1+c2x2+…+cnxn

約束條件：a11x1+a12x2+…+a1nxn

=

b1a21x1+a22x2+…+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn

≥01.線性規(guī)劃的概念第8頁,共42頁，2024年2月25日，星期天9

可以看出，線性規(guī)劃的標準形式有如下四個特點：目標最大化、約束為等式、決策變量均非負、右端項非負。對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標準形式:

1.線性規(guī)劃的概念第9頁,共42頁，2024年2月25日，星期天101.極小化目標函數(shù)的問題：設(shè)目標函數(shù)為

Minf=c1x1

+c2x2

+…+cnxn

則可以令z

＝-f

，該極小化問題與下面的極大化問題有相同的最優(yōu)解，即

Maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標函數(shù)值卻相差一個符號，即

Minf

＝-Maxz1.線性規(guī)劃的概念第10頁,共42頁，2024年2月25日，星期天11

2、約束條件不是等式的問題：設(shè)約束條件為

ai1x1+ai2x2+…+ainxn

≤

bi

可以引進一個新的變量s

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

s=bi–(ai1x1

+ai2x2

+…+ainxn

)

顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=bi第11頁,共42頁，2024年2月25日，星期天12

當約束條件為

ai1x1+ai2x2+…+ainxn

≥

bi

時，類似地令

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

顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi

1.線性規(guī)劃的概念第12頁,共42頁，2024年2月25日，星期天13

為了使約束由不等式成為等式而引進的變量s稱為“松弛變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標準形式時，必須對各個約束引進不同的松弛變量。

1.線性規(guī)劃的概念第13頁,共42頁，2024年2月25日，星期天14

例6.2：將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式

Minf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

1.線性規(guī)劃的概念

解：首先,將目標函數(shù)轉(zhuǎn)換成極大化：令z=-f=-3.6x1+5.2x2-1.8x3

第14頁,共42頁，2024年2月25日，星期天15其次考慮約束，有2個不等式約束，引進松弛變量x4，x5

≥0。于是，我們可以得到以下標準形式的線性規(guī)劃問題：Maxz=-3.6x1

+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9

x1+x2+x3=38

x1,x2,x3,x4,x5

≥01.線性規(guī)劃的概念第15頁,共42頁，2024年2月25日，星期天16

3.變量無符號限制的問題：在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。1.線性規(guī)劃的概念第16頁,共42頁，2024年2月25日，星期天17

4.右端項有負值的問題：在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數(shù)為負時，如bi<0，則把該等式約束兩端同時乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi

。1.線性規(guī)劃的概念第17頁,共42頁，2024年2月25日，星期天18標準型要求minz=Cx

maxz’=-Cx ……=-bi,兩邊乘(-1)

……=bi;

……<b,左加松馳變量

……+xi+1=bi;

……>b,左減剩余變量

……-xi+1=bi;

無約束變量x

x=x’-x”,x’>0,x”>0注：標準形在單純形法中用.

第18頁,共42頁，2024年2月25日，星期天19例6.3：將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥01.線性規(guī)劃的概念第19頁,共42頁，2024年2月25日，星期天20解：首先，將目標函數(shù)轉(zhuǎn)換成極大化：令z=-f=3x1–5x2–8x3+7x4

；其次考慮約束，有3個不等式約束，引進松弛變量x5,x6,x7

≥0；由于x2無非負限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；由于第3個約束右端項系數(shù)為-58，于是把該式兩端乘以-1。于是，我們可以得到以下標準形式的線性規(guī)劃問題：

1.線性規(guī)劃的概念第20頁,共42頁，2024年2月25日，星期天21Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

1.線性規(guī)劃的概念第21頁,共42頁，2024年2月25日，星期天222.線性規(guī)劃的圖解法

線性規(guī)劃的圖解法(解的幾何表示)對于只有兩個變量的線性規(guī)劃問題，可以二維直角坐標平面上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。圖解法求解線性規(guī)劃問題的步驟如下：

(1)分別取決策變量x1,x2

為坐標向量建立直角坐標系。

第22頁,共42頁，2024年2月25日，星期天232.線性規(guī)劃的圖解法

（2）對每個約束（包括非負約束）條件，先取其等式在坐標系中作出直線，通過判斷確定不等式所決定的半平面。各約束半平面交出來的區(qū)域(存在或不存在），若存在，其中的點表示的解稱為此線性規(guī)劃的可行解。這些符合約束限制的點集合，稱為可行集或可行域。然后進行（3）。否則該線性規(guī)劃問題無可行解。

第23頁,共42頁，2024年2月25日，星期天24

2.線性規(guī)劃的圖解法

（3）任意給定目標函數(shù)一個值作一條目標函數(shù)的等值線，并確定該等值線平移后值增加的方向，平移此目標函數(shù)的等值線，使其達到既與可行域有交點又不可能使值再增加的位置(有時交于無窮遠處，此時稱無有限最優(yōu)解）。若有交點時，此目標函數(shù)等值線與可行域的交點即最優(yōu)解（一個或多個），此目標函數(shù)的值即最優(yōu)值。第24頁,共42頁，2024年2月25日，星期天25設(shè)有一線性規(guī)劃問題表達式(包括目標函數(shù)、約束條件)如下

max

f＝50X1

＋40X2

X1＋X2≤450

(1)

2X1＋X2≤800

(2)

X1＋3X2≤900

(3)

X1，X2≥0

(4)

以X1

，X2為坐標，當式(l)為等式，即X1

＋X2＝450時，在X1

，X2坐標系，它是一條直線，但式(l)不是等式，而是X1

＋X2≤450，即在式(1)表示的約束條件中給定的不僅是在直線上的所有點，而是在直線X1

＋X2=450左下部一個廣大的區(qū)域(包括直線在內(nèi)的陰影線部分)，見圖，例如X1

＝0、X2=0，X1

＝-5、X2=0,X1=3、X2=-3等等,都是滿足式(1)的點。

第25頁,共42頁，2024年2月25日，星期天26第26頁,共42頁，2024年2月25日，星期天27同理，也可以在X1

，X2坐標系中畫出式(2)、(3)、(4)所決定的4條直線，連同式(1)，共5條直線，如圖所示。

由圖所示的5條直線所圍成的一個凸多邊形，就是約束條件給定的區(qū)域，其中所有的點都滿足約束條件的要求。實際上，它表示一個由凸多邊形內(nèi)無數(shù)多個點所組成的集合，稱為凸集。那么，怎樣從無窮多中求出使目標函數(shù)值最大的點呢？

第27頁,共42頁，2024年2月25日，星期天28第28頁,共42頁，2024年2月25日，星期天29由于目標函數(shù)f＝50X1

＋40X2

，在f為一定值時也是一條直線，其斜率為-40/50。當f為不同值時，在X1，X2坐標系中實際上是一系列的平行線，則盡管在每一條直線上X1，X2取不同的值，f總是某一定值。例如圖中的直線I，當X1

=0、X2=0時；當X1

=4、X2＝-5時f=0；因此稱直線I為f的某一等直線（此處為零）。

第29頁,共42頁，2024年2月25日，星期天30第30頁,共42頁，2024年2月25日，星期天31由于直線I是等直線，而且斜率相等，它們又是一系列平行線，因此只要畫出其中任意的一條線，將它們平移到某個與凸集相交的極限位置，所得的交點就是既滿足約束條件(在凸集范圍內(nèi))，又使f值為最大的最優(yōu)解。如下圖中的點，X1=350，X2=100，f=21500。

第31頁,共42頁，2024年2月25日，星期天32第32頁,共42頁，2024年2月25日，星期天33線性規(guī)劃的圖解max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目標函數(shù)等值線最優(yōu)解64-860x1x2第33頁,共42頁，2024年2月25日，星期天34⑴⑵⑶∴線性規(guī)劃有無窮多最優(yōu)解x1x2

例線性規(guī)劃的圖解法第34頁,共42頁，2024年2月25日，星期天35⑴⑵x1x2

線性規(guī)劃的圖解法例∴線性規(guī)劃有無界解第35頁