線性規(guī)劃第一

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

例6.1:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時(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è)備能力（機(jī)時(shí)數(shù)）的限制。對設(shè)備A，兩種產(chǎn)品生產(chǎn)所占用的機(jī)時(shí)數(shù)不能超過65，于是我們可以得到不等式：3x1

+2x2

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

+x2

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

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

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

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

Maxz=1500x1+2500x2

約束條件

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

x1,x2≥0

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

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

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

目標(biāo)函數(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標(biāo)準(zhǔn)形式目標(biāo)函數(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ī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最大化、約束為等式、決策變量均非負(fù)、右端項(xiàng)非負(fù)。對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:

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

Minf=c1x1

+c2x2

+…+cnxn

則可以令z

＝-f

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

Maxz=-c1x1

-c2x2-…-cnxn

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

Minf

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

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

ai1x1+ai2x2+…+ainxn

≤

bi

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

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

s=bi–(ai1x1

+ai2x2

+…+ainxn

)

顯然，s

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

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

當(dāng)約束條件為

ai1x1+ai2x2+…+ainxn

≥

bi

時(shí)，類似地令

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

顯然，s

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

ai1x1+ai2x2+…+ainxn-s=bi

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

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

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

例6.2：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔ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ī)劃的概念

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

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

≥0。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(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.變量無符號限制的問題：在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量xj沒有非負(fù)約束時(shí)，可以令

xj=xj’-xj”其中

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

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

=-bi

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

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

……=bi;

……<b,左加松馳變量

……+xi+1=bi;

……>b,左減剩余變量

……-xi+1=bi;

無約束變量x

x=x’-x”,x’>0,x”>0注：標(biāo)準(zhǔn)形在單純形法中用.

第18頁,共42頁，2024年2月25日，星期天19例6.3：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔ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解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z=-f=3x1–5x2–8x3+7x4

；其次考慮約束，有3個(gè)不等式約束，引進(jìn)松弛變量x5,x6,x7

≥0；由于x2無非負(fù)限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；由于第3個(gè)約束右端項(xiàng)系數(shù)為-58，于是把該式兩端乘以-1。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(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ī)劃的圖解法(解的幾何表示)對于只有兩個(gè)變量的線性規(guī)劃問題，可以二維直角坐標(biāo)平面上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。圖解法求解線性規(guī)劃問題的步驟如下：

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

為坐標(biāo)向量建立直角坐標(biāo)系。

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

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

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

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

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

max

f＝50X1

＋40X2

X1＋X2≤450

(1)

2X1＋X2≤800

(2)

X1＋3X2≤900

(3)

X1，X2≥0

(4)

以X1

，X2為坐標(biāo)，當(dāng)式(l)為等式，即X1

＋X2＝450時(shí)，在X1

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

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

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

＝0、X2=0，X1

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

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

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

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

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

＋40X2

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

=0、X2=0時(shí)；當(dāng)X1

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

第29頁,共42頁，2024年2月25日，星期天30第30頁,共42頁，2024年2月25日，星期天31由于直線I是等直線，而且斜率相等，它們又是一系列平行線，因此只要畫出其中任意的一條線，將它們平移到某個(gè)與凸集相交的極限位置，所得的交點(diǎn)就是既滿足約束條件(在凸集范圍內(nèi))，又使f值為最大的最優(yōu)解。如下圖中的點(diǎn)，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可行域目標(biāo)函數(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頁