第1章-線性規(guī)劃初步與物流生產(chǎn)管理_第1頁
第1章-線性規(guī)劃初步與物流生產(chǎn)管理_第2頁
第1章-線性規(guī)劃初步與物流生產(chǎn)管理_第3頁
第1章-線性規(guī)劃初步與物流生產(chǎn)管理_第4頁
第1章-線性規(guī)劃初步與物流生產(chǎn)管理_第5頁
已閱讀5頁,還剩127頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

物流運(yùn)籌學(xué)教學(xué)課件第1章線性規(guī)劃初步與物流生產(chǎn)管理線性規(guī)劃的一般定義1線性規(guī)劃的圖解法2線性規(guī)劃的標(biāo)準(zhǔn)形式及矩陣表示3單純型法4生產(chǎn)能力的合理分配5裝卸作業(yè)調(diào)配6車載貨物的裝配71.1線性規(guī)劃的一般定義1.11.1.1建立數(shù)學(xué)模型【例1.1

某廠生產(chǎn)甲、乙兩種產(chǎn)品,均需經(jīng)過金工和裝配兩個車間加工,但每件利潤卻不相同,每件產(chǎn)品在兩個車間的加工時(shí)間如表。金工和裝配車間的總有效工時(shí)分別為400與500小時(shí)。甲、乙兩產(chǎn)品所能獲得的利潤分別為:100元/件、80元/件。問如何安排生產(chǎn),才能使所獲得的利潤最大?甲乙金

工42裝

配241.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型解:設(shè)

分別表示產(chǎn)品甲、乙的產(chǎn)量。根據(jù)題意,

必須滿足:線性不等式目標(biāo)函數(shù)1.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型這種含有決策變量、約束條件及目標(biāo)函數(shù)的數(shù)學(xué)式子,并指明了求目標(biāo)函數(shù)的最大值(或最小值),稱為數(shù)學(xué)模型。上述式子中的約束條件是決策變量的線性不等式組,目標(biāo)函數(shù)也是決策變量的線性函數(shù),像這樣約束條件和目標(biāo)函數(shù)都是用線性函數(shù)來描述的數(shù)學(xué)模型,我們稱之為線性規(guī)劃的數(shù)學(xué)模型,簡稱為線性規(guī)劃。1.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型【例1.2

】某學(xué)生食堂出售甲、乙兩種食品,甲每份售價(jià)1.50元,乙每份售價(jià)2.10元。經(jīng)檢測食品中含有三種學(xué)生所需的營養(yǎng)物A、B、C,其中食品甲每份含A、B、C分別為10,3,4毫克,食品乙每份含A、B、C分別為2,3,9毫克,而營養(yǎng)師認(rèn)為學(xué)生每餐至少需此三種營養(yǎng)物A、B、C分別為20,18,36毫克,問一學(xué)生進(jìn)餐應(yīng)對甲、乙食品各買幾份,既能保證足夠的營養(yǎng)要求,又花錢最少?

甲乙營養(yǎng)最低要求A10220B3318C4936單價(jià)(元/每份)1.502.10

1.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型解:設(shè)學(xué)生進(jìn)餐者購買食品甲、乙分別為

份,根據(jù)題意,此問題的線性規(guī)劃數(shù)學(xué)模型是:1.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型【例1.3

】某建筑工地,需要直徑相同、長度不同的成套鋼筋。每套由7根2米與2根7米的鋼筋組成。今有15米長的鋼筋150根,問應(yīng)怎樣下料,才能使廢料最少?1.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型把一根15米長的鋼筋割成分別為7米和2米的兩種規(guī)格,有三種比較經(jīng)濟(jì)的割法分割方法7米長2米長廢料長方法一0根7根1米方法二1根4根0米方法三2根0根1米1.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型設(shè)決策變量

分別表示采用上述三種方法割料的15米長鋼筋根數(shù),則有又考慮到每套由7根2米長和2根7米長的鋼筋組成。而7米長有(

)根,2米長有()根。于是,由配套要求得1.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型1.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型【例1.4

】設(shè)某種貨物有

A1、A2、A3三個產(chǎn)地,四個銷售地

B1、B2、B3、B4,從A1、A2、A3到地B1、B2、B3、B4

的單位運(yùn)價(jià)以及三個產(chǎn)地的供應(yīng)量和四個銷售地的需求量如表所示。問怎樣安排調(diào)運(yùn)方案,才能使總的運(yùn)費(fèi)最少?B1B2B3B4產(chǎn)量A1311267A219474A3421059銷量3548201.1線性規(guī)劃的一般定義1.1.1建立數(shù)學(xué)模型解:設(shè)由Aj到

Bj的運(yùn)量為xij,所需總運(yùn)費(fèi)為f,則其數(shù)學(xué)模型為求

滿足:1.1線性規(guī)劃的一般定義要確定決策變量(或),即確定優(yōu)化的內(nèi)容和對象。決策變量是不同方案賴以區(qū)分的根據(jù)。一般地,不同的決策變量表示著不同的方案。決策變量具有非負(fù)性。確定約束條件。約束條件是優(yōu)化過程受限制的條件,用含決策變量的一組線性等式或者線性不等式表示。確定目標(biāo)函數(shù)。目標(biāo)函數(shù)是決策變量的線性函數(shù),并明確求其最大(小)值。在線性約束條件下,要求確定決策變量的一組線性目標(biāo)函數(shù)達(dá)到最大值或最小值的問題,叫做線性規(guī)劃問題,常用LP表示。一般地,

的模型為求1.2線性規(guī)劃的圖解法1.21.2.1線性規(guī)劃模型的解的基本概念求1.2.1線性規(guī)劃模型的解的基本概念可行解:我們把滿足約束條件(1-3)式和(1-4)式的一組變量,稱為

線性規(guī)劃的一組可行解;所有可行解的集合叫做可行解集,或稱可行域。最優(yōu)解:滿足目標(biāo)函數(shù)(1-5)的可行解圖稱為線性規(guī)劃的最優(yōu)解;最優(yōu)值:最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值。凸集:設(shè)R是n維空間的一個點(diǎn)集,如果R中任意兩點(diǎn)的連線仍在集R中,稱集R為凸集。用數(shù)學(xué)式子描述是:對于R中的任意兩點(diǎn)x1,

x2,對于參數(shù)

,若x1與x2連線上的點(diǎn)為+(1

仍在集R中,稱集R為凸集。頂點(diǎn):設(shè)R是凸集,

;若x不能用

兩點(diǎn)的連線組合表示為

則x為R的一個頂點(diǎn),或稱極點(diǎn)。即凸集的頂點(diǎn)是不處于凸集中任何兩個不同點(diǎn)的連線上的點(diǎn)。它與過去所說的幾何體的頂點(diǎn)的含義是一致的。1.2.2二元一次不等式的區(qū)域圖解法任何一個二元一次方程Ax1+Bx2+C=0,在平面直角坐標(biāo)系中都表示一條直線,此直線把平面分成兩個半平面:其中一個半平面包括直線l的點(diǎn)的坐標(biāo)總滿足二元一次不等式Ax1+Bx2+C≦0(或≧

0),此時(shí)另一半平面上的點(diǎn)(含直線l上的點(diǎn))就總滿足Ax1+Bx2+C≦0(或≧

0),兩半平面的邊界線就是直線Ax1+Bx2+C=0。如何確定半平面Ax1+Bx2+C≦0(或≧

0)呢?具體做法是:在直線Ax1+Bx2+C=0外任取一點(diǎn)(x1,x2),對于不經(jīng)過原點(diǎn)的直線,一般取原點(diǎn)(0,0),視其坐標(biāo)是否滿足不等式,若滿足不等式,則該點(diǎn)所在的一側(cè)的半平面就是不等式所表示的半平面區(qū)域;否則,另一半平面為不等式所表示的區(qū)域。1.2.2二元一次不等式的區(qū)域【例1.5

】求下列二元一次不等式所表示的區(qū)域:(1)

x2≧

0

(2)x1≧

0(3)4x1+2x2≦400(4)2x1+4x2≦5001.2.2二元一次不等式的區(qū)域解:(1)表示x1包括

軸和它上面的半平面,如圖所示1.2.2二元一次不等式的區(qū)域(2)表示x2包括

軸和它右半側(cè)的半平面,如圖所示1.2.2二元一次不等式的區(qū)域(3)先畫出直線:

4x1+2x2=400

再“試點(diǎn)”:把原點(diǎn)

代入原不等式,發(fā)現(xiàn)不等式成立,則原點(diǎn)所在一側(cè)即直線的左下方為不等式所表示的區(qū)域。1.2.2二元一次不等式的區(qū)域(4)作直線:2x1+4x2=500的圖像。把原點(diǎn)(0,0)代入不等式2x1+4x2≦500結(jié)果不等式成立。表明

2x1+4x2≦500的區(qū)域?yàn)橹本€與原點(diǎn)所在一側(cè),即直線的左下方半平面;另一半平面為2x1+4x2≧500所表示的區(qū)域1.2.3兩個變量的線性規(guī)劃問題的解法【例1.6

】生產(chǎn)安排問題:某工廠生產(chǎn)甲、乙兩種產(chǎn)品,所耗用的原料A、原料B數(shù)量,單件利潤值及庫存原料數(shù)如下表所示。試確定甲、乙兩種產(chǎn)品應(yīng)各生產(chǎn)多少件才能使該工廠利潤最大。

單件產(chǎn)品耗用原料數(shù)庫存原料總數(shù)(kg)甲乙A51060B4440單件利潤值(元/件)68

1.2.3兩個變量的線性規(guī)劃問題的解法先建立數(shù)學(xué)模型:設(shè)產(chǎn)品甲計(jì)劃生產(chǎn)x1件,產(chǎn)品乙計(jì)劃生產(chǎn)x2件,求x1、

x2的值(稱x1、x2為決策變量),使得f=2x1+4x2

(稱之為目標(biāo)函數(shù))達(dá)到最大值。約束條件為:1.2.3兩個變量的線性規(guī)劃問題的解法首先畫出可行解域

,再令目標(biāo)函數(shù)

f=2x1+4x2

=h(常數(shù))得到一條直線2x1+4x2=h

(稱為目標(biāo)函數(shù)的一條等值線)在此直線上的點(diǎn)的坐標(biāo)(

x1

,x2)都能使目標(biāo)函數(shù)的值等于h這條直線若穿過可行解域k,那么k中在這條等值線上的點(diǎn)的坐標(biāo)都滿足2x1+4x2=h

1.2.3兩個變量的線性規(guī)劃問題的解法畫出可行解域過O(0,0)點(diǎn)的等值線為:6x1+8x2=0過A(0,6)點(diǎn)的等值線為:6x1+8x2

=48等值線2x1+4x2

=h

向右平行移動時(shí),h

的值增加,到通過頂點(diǎn)B(8,2)時(shí),得到最大值641.2.3兩個變量的線性規(guī)劃問題的解法【例1.7】

求x,y

,使其滿足約束條件,且使目標(biāo)函數(shù)

f(x,y)=3x+y達(dá)到最大。1.2.3兩個變量的線性規(guī)劃問題的解法解:畫出可行解域kk是凸四邊形OABC的內(nèi)部及其邊界線直線3x+y=h從左向右平行移動,h增大到與AB邊重合所得的h最大,即3x+y=10.5

此時(shí)得最優(yōu)解

實(shí)際上線段AB上任何一點(diǎn)的坐標(biāo)都是最優(yōu)解1.2.3兩個變量的線性規(guī)劃問題的解法【例1.8】

求x,y

,使其滿足約束條件,且使目標(biāo)函數(shù)

f(x,y)=-2x+y達(dá)到最大。雖然有可行解,但沒有最優(yōu)解1.2.3兩個變量的線性規(guī)劃問題的解法【例1.9】

求x,y

,使其滿足約束條件,且使目標(biāo)函數(shù)

f(x,y)=3x+y達(dá)到最大。可行解域K是空的,沒有可行解,也沒有最優(yōu)解1.2.3兩個變量的線性規(guī)劃問題的解法(1)有唯一最優(yōu)解,它必是可行解域

的一個頂點(diǎn)的坐標(biāo)。(2)有最優(yōu)解,但不唯一,最優(yōu)解必是可行解域的某條邊上任何一點(diǎn)的坐標(biāo)。(3)有可行解,但無最優(yōu)解。可行解中的點(diǎn)能夠使目標(biāo)函數(shù)值之絕對值無限增大(或無限減?。#?)無可行解,即可行解域k是空的。1.2.3兩個變量的線性規(guī)劃問題的解法【例1.10】某企業(yè)承包種植甲、乙兩種蔬菜,生產(chǎn)1t甲種蔬菜要消耗肥料9t,消耗電力4kW·h(澆水等用電力),勞動量3人·日;生產(chǎn)1t乙種蔬菜要消耗肥料4t,消耗電力5kW·h,勞動量10人·日。但基地能夠使用的肥料只有360t,電力200kW·h,勞動量300人·日,不能超過這個范圍。甲種蔬菜1t供應(yīng)7個單位,乙種蔬菜1t供應(yīng)12個單位。在上述肥料、電力、勞動量的限制下,希望能供應(yīng)單位越多越好,求生產(chǎn)甲、乙蔬菜各多少t為最好?

甲種蔬菜生產(chǎn)1t乙種蔬菜生產(chǎn)1t條件限制肥料(t)94360電力(kW·h)45200勞動量(人·日)310300供應(yīng)單位(個)712

1.2.3兩個變量的線性規(guī)劃問題的解法解:設(shè)生產(chǎn)甲種蔬菜x

t,乙種蔬菜yt.求x,y,使其滿足約束條件,且使目標(biāo)函數(shù)f(x,y)=7x+12y

達(dá)到最大值1.2.3兩個變量的線性規(guī)劃問題的解法k是凸五邊形OABCD的內(nèi)部及其邊界線直線7x+12y=h從下向上平行移動,h增大移動到點(diǎn)B時(shí)h最大,即7x+12y=428此時(shí)得最優(yōu)解

x=20,y=241.3線性規(guī)劃的標(biāo)準(zhǔn)形式及矩陣表示1.31.3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式

為了便于討論一般解法,常將線性規(guī)劃問題的約束條件歸結(jié)為變量非負(fù)且其它約束條件是線性方程,并且對目標(biāo)函數(shù)統(tǒng)一成求最大值,稱為線性規(guī)劃問題的標(biāo)準(zhǔn)形式,即1.3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式若目標(biāo)函數(shù)求

,可通過求其相反數(shù)的方法將最小值問題轉(zhuǎn)化為最大值問題

,非線性方程表示的約束條件可通過加一個非負(fù)變量或減一個非負(fù)變量

的方法轉(zhuǎn)化為標(biāo)準(zhǔn)形式,

xi稱為松弛變量1.3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式【例1.11】將線性規(guī)劃化為標(biāo)準(zhǔn)形式:解:引進(jìn)松弛變量

,于是所給問題化為標(biāo)準(zhǔn)形式:1.3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式【例1.12】將線性規(guī)劃化為標(biāo)準(zhǔn)形式.乘以-11.3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式【例1.13】將線性規(guī)劃化為標(biāo)準(zhǔn)形式.引進(jìn)兩個新的非負(fù)變量x5≧0

x6≧0將x1表示為x1=x5-x61.3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式(1)對目標(biāo)函數(shù),若求

minz,可令

便化為標(biāo)準(zhǔn)形式;(2)若約束條件中有“≦”關(guān)系,可加上非松弛變量化為“=”關(guān)系,若有“≧”關(guān)系,則減去非松弛變量化為“=”關(guān)系;(3)若有某個

bk<0,可在不等式(或等式)兩邊同乘以-1;(4)若有無正負(fù)約束決策變量

xk,可令

xk=

xk+1—xk+t+1

(xk+1

,xk+t+1

≧0).1.3.2線性規(guī)劃的矩陣表示標(biāo)準(zhǔn)形式的線性規(guī)劃問題可以用矩陣記號表示A為構(gòu)成約束條件的線性規(guī)劃方程組的系數(shù)矩陣X和b為構(gòu)成約束條件的線性規(guī)劃方程組變量矩陣與常數(shù)項(xiàng)矩陣C為目標(biāo)函數(shù)中變量系數(shù)構(gòu)成的1行

n列矩陣1.3.2線性規(guī)劃的矩陣表示設(shè)約束方程組AX=b中的系數(shù)矩陣A的秩r(A)=m

,B是矩陣A中任一階的非奇異矩陣,則稱B為該線性規(guī)劃問題的一個基.若設(shè)A=(B,N)

,其中B是一個基,且

B的列向量Pi(i=1,2,…,m)稱為基向量,N的列向量

Pi(i=m+1,m+2,…,n)稱為非基向量,對應(yīng)的變量稱為基變量和非基變量.非基變量取零值時(shí)所得的解稱為基本解,如果基本解又滿足非負(fù)條件,則稱為基本可行解,簡稱為基可行解,能使目標(biāo)函數(shù)達(dá)到最優(yōu)的基可行解,稱為最優(yōu)基可行解.1.3.2線性規(guī)劃的矩陣表示【例1.14

】寫出下列線性規(guī)劃問題的所有基陣:1.3.2線性規(guī)劃的矩陣表示解:

約束方程組的系數(shù)矩陣及各列向量分別為1.4單純型法1.41.4.1引例求線性規(guī)劃問題1.4.1引例解:在式(1)中

x3,x4,x5的系數(shù)列向量組成的一個基為:由約束條件得:1.4.1引例當(dāng)非基變量x1=

x2

=0時(shí)便得基本可行解X0

=(0,0,8,7,6)’目標(biāo)函數(shù)z=0,由于z=2x1+

3x2是非基變量的函數(shù)且x1,x2的系數(shù)為正,增加x1,x2可增加目標(biāo)函數(shù)的值,故X0不是最優(yōu)解一般選擇增加系數(shù)大的而非基變量的值以得到一個新的基本可行解,所以

x2增加后被選為新的基變量(稱為換入變量),當(dāng)

x1=0時(shí),由于非負(fù),約束條件(2)化為1.4.1引例把x1=

0,x2=4代人式(2)的第1個方程,得x3=0,所以

x3應(yīng)該被換出為非基變量(稱為換出變量).為了獲得以x2x4x5

為基變量的一個基本可行解,用主元素消去法對式(1)中的約束方程組的增廣矩陣施行初等行變把代入目標(biāo)函數(shù),變?yōu)椋?.4.1引例令x1=x3=0得基本可行解X0=(0,4,0,3,6)’,這時(shí)目標(biāo)函數(shù)z=12,其值增加了。

是非基變量x1x3的函數(shù),

x1的系數(shù)為正,增加x1可增加目標(biāo)函數(shù)

z的值,故X1也不是最優(yōu)解.同理x1最多可增加到

代入第2個約束條件

,所以x1進(jìn)基,

x4出基,同樣進(jìn)行基變換得1.4.1引例是非基變量x3x4的函數(shù)且它們的系數(shù)均為負(fù)數(shù)最優(yōu)解單純型法:把線性規(guī)劃模型化為標(biāo)準(zhǔn)形式,從一個基本可行解開始,用換基迭代方法,轉(zhuǎn)換到另一個基本可行解,使目標(biāo)函數(shù)值逐步增加,當(dāng)目標(biāo)函數(shù)達(dá)到最大值時(shí),也就得到最優(yōu)解.1.4.2表格單純型法1.4.2表格單純型法(1)第一列的中間三行填寫基變量

x3x4x5;(2)

xi列填寫約束方程組中xi的系數(shù).b列填寫約束方程組右邊的常數(shù)項(xiàng);(3)

z行填寫目標(biāo)函數(shù)中xi的系數(shù),稱為檢驗(yàn)數(shù).當(dāng)檢驗(yàn)數(shù)全部小于等于0時(shí),目標(biāo)函數(shù)取得最優(yōu)值,最大正檢驗(yàn)數(shù)所在的列稱為主元素列,現(xiàn)在是x2列的3最大,它就是主元素列,

x2就成為進(jìn)基變量;(4)用主元素列中的正分量去除b列對應(yīng)的分量,取得最小比值對應(yīng)的行稱為主元素行,現(xiàn)在是在x3行.變量就成為出基變量;(5)給主元素行和主元素列的交點(diǎn)2加上中括號,它就稱為軸心項(xiàng);(6)下一步就是進(jìn)行換基迭代,利用矩陣的初等行變換,將軸心項(xiàng)化為“1”,主元素列的其它元素化為“0”.重復(fù)上述過程,直到檢驗(yàn)數(shù)全部非正.1.4.2表格單純型法1.4.2表格單純型法1.4.2表格單純型法【例1.15】解線性規(guī)劃問題1.4.2表格單純型法解:引進(jìn)新的目標(biāo)函數(shù)z’=-z,且引進(jìn)松弛變量

,把所給的線性規(guī)劃問題化為標(biāo)準(zhǔn)形式:1.4.2表格單純型法用單純型表作換基迭代1.4.2表格單純型法所有檢驗(yàn)數(shù)非正,去掉松弛變量,得最優(yōu)解1.4.2表格單純型法【例1.16】解線性規(guī)劃問題1.4.2表格單純型法解:這個線性規(guī)劃問題已經(jīng)是標(biāo)準(zhǔn)形式,可直接用單純型表作換基迭代:1.4.2表格單純型法還有一個證檢驗(yàn)數(shù)6,而對應(yīng)列元素全部為負(fù),無法進(jìn)行下一步的迭代將其變量

x3

x1即目標(biāo)函數(shù)z用非基變量x2x4

表示為令非基變量x2無限增大,x4

=0,此時(shí)基變量仍滿足非負(fù)的約束條件,但目標(biāo)函數(shù)z卻無限增大,即無最大值,所以這個線性規(guī)劃問題有可行解而沒有最優(yōu)解.1.5生產(chǎn)能力的合理分配1.51.5.1一般性的問題設(shè)有n臺機(jī)床,在這些機(jī)床上制造由m個不同的零件組成的產(chǎn)品。假設(shè)在第i臺機(jī)床上加工第k種零件,一天能生產(chǎn)Qik個零件,這些是已知的注意:如果在第i臺機(jī)床上不能加工第k種零件,則認(rèn)為Qik=0問怎樣來分配零件的加工,可以使制造出來的零件組成的產(chǎn)品最多?1.5.1一般性的問題設(shè)tik表示在第i臺機(jī)床上生產(chǎn)第k種零件的時(shí)間(用占一個工作日的份額表示)第i臺機(jī)床上生產(chǎn)所有零件的時(shí)間總計(jì)為1個工作日是Qiktik在第i臺機(jī)床上生產(chǎn)第k種零件的數(shù)量1.5.1一般性的問題tik應(yīng)使最大。1.5.2效率比法【例1.17】設(shè)有兩種零件,在單位時(shí)間內(nèi)工人甲生產(chǎn)50個第I種零件,60個第II種零件;工人乙生產(chǎn)30個第I種零件,90個第II種零件;工人丙生產(chǎn)20個第I種零件,80個第II種零件。每種零件各一個就能配成套,問如何分配任務(wù),可在單位時(shí)間內(nèi)生產(chǎn)出最多的套數(shù)。1.5.2效率比法解:將甲、乙、丙三個工人在單位時(shí)間內(nèi)生產(chǎn)各種零件的個數(shù)(生產(chǎn)效率)列表如下:

甲乙丙I503020II6090801.5.2效率比法(1)工人甲單獨(dú)成套生產(chǎn)。設(shè)工人甲單獨(dú)生產(chǎn)零件I所占的時(shí)間份額為x,那么1—x則是工人甲單獨(dú)生產(chǎn)零件II所占的時(shí)間份額,則有工人甲在單位時(shí)間內(nèi)可生產(chǎn)1.5.2效率比法(2)工人乙單獨(dú)成套生產(chǎn)。設(shè)工人乙單獨(dú)生產(chǎn)零件I所占的時(shí)間份額為y,那么1—y為他生產(chǎn)零件II占用的時(shí)間份額,于是有:工人乙在單位時(shí)間內(nèi)可生產(chǎn)1.5.2效率比法(3)工人丙單獨(dú)成套生產(chǎn)。設(shè)工人丙單獨(dú)生產(chǎn)零件I所占的時(shí)間份額為z,那么1—z為他生產(chǎn)零件II占用的時(shí)間份額,因此有:工人丙在單位時(shí)間內(nèi)可生產(chǎn)1.5.2效率比法

甲乙丙I272216II272216方案一:三個工人分別單獨(dú)成套生產(chǎn),共可生產(chǎn)65套/單位時(shí)間。但是這種分配任務(wù)的方法未必能得到最多的套數(shù)。1.5.2效率比法依經(jīng)驗(yàn),可以采用誰加工哪種零件最快誰就加工哪種零件的方法:讓工人甲加工零件I50個,工人丙加工零件I20個,工人乙加工I與II兩種零件。設(shè)t與1—t為乙分別加工I與II兩種零件占用的時(shí)間份額,則有

甲乙丙I50520II

75

1.5.2效率比法方案二:共生產(chǎn)了75套,比前面的分配方法多出10套1.5.2效率比法效率比法:先求出甲、乙、丙三位工人生產(chǎn)這兩種零件的效率比,見下表:1.5.2效率比法甲生產(chǎn)零件I的效率最高,丙生產(chǎn)零件II的效率最高。因此,讓工人甲生產(chǎn)零件I,工人丙生產(chǎn)零件II1.5.2效率比法讓工人乙生產(chǎn)零件I和II以便調(diào)配成套。設(shè)乙生產(chǎn)零件Ix個,零件IIy個。那么乙生產(chǎn)這x個零件I要占用時(shí)間份額

,而生產(chǎn)y個零件II占用的時(shí)間份額為

,從而有解得:

x=30y=01.5.2效率比法方案三:共可生產(chǎn)80套,比第二個分配方案又多出5套。

甲乙丙I5030

II

801.5.2效率比法【例1.18】

某物流企業(yè)有四個生產(chǎn)組,A組有11人,每人每天生產(chǎn)甲產(chǎn)品1.1噸或生產(chǎn)乙產(chǎn)品2噸;B組有5人,每人每天生產(chǎn)甲產(chǎn)品1.5噸或生產(chǎn)乙產(chǎn)品3噸;C組有16人,每人每天生產(chǎn)甲產(chǎn)品1.1噸或生產(chǎn)乙產(chǎn)品1.5噸;D組有8人,每人每天生產(chǎn)甲產(chǎn)品0.8噸或生產(chǎn)乙產(chǎn)品1噸;求在生產(chǎn)甲產(chǎn)品26噸的情況下,生產(chǎn)乙產(chǎn)品越多越好的人員分配方案。1.5.2效率比法解:先列出各組人員的生產(chǎn)效率表

A組11人B組5人C組16人D組8人生產(chǎn)甲產(chǎn)品1.11.51.10.8生產(chǎn)乙產(chǎn)品231.511.5.2效率比法先要完成種26噸甲產(chǎn)品的任務(wù),再分配生產(chǎn)乙產(chǎn)品的任務(wù)。可按下表分配任務(wù)

A組11人B組5人C組16人D組8人生產(chǎn)甲產(chǎn)品1156生產(chǎn)乙產(chǎn)品108甲產(chǎn)品:乙產(chǎn)品:1.5.2效率比法效率比法:先求各組人員的效率比:

A組B組C組D組1.821.361.25D組人員的效率比最低,B組人員的效率比最高。8位D組人員生產(chǎn)甲產(chǎn)品:16位C組人員也生產(chǎn)甲產(chǎn)品:共24噸,還差2噸再分配2位B組人員去生產(chǎn)甲產(chǎn)品:剩下的人員全生產(chǎn)乙產(chǎn)品1.5.2效率比法

A組B組C組D組生產(chǎn)甲產(chǎn)品2

168生產(chǎn)乙產(chǎn)品95

1.6裝卸作業(yè)調(diào)配1.61.6.1裝卸任務(wù)分配問題【例1.19】某運(yùn)輸倉庫有4項(xiàng)裝卸任務(wù)必須在二天內(nèi)完成,該倉庫有3個裝卸隊(duì),均可以單獨(dú)完成其中任一項(xiàng)任務(wù).如表所示,列出了各裝卸隊(duì)單獨(dú)完成各項(xiàng)任務(wù)所需要的時(shí)間,每小時(shí)的裝卸成本及可用的小時(shí)數(shù),各項(xiàng)任務(wù)均可以分開由兩個或三個隊(duì)完成(這也是與一般指派問題的區(qū)別).試問怎樣分配這些任務(wù)才能使裝卸成本達(dá)到最低.

裝卸隊(duì)每任務(wù)所需時(shí)間

單位成本

可用時(shí)間12341232020207375773630285963601901801558080801.6.1裝卸任務(wù)分配問題解:設(shè)Xsr表示第r項(xiàng)任務(wù)由第s隊(duì)所做的小時(shí)數(shù),其完成任務(wù)的最小成本的線型規(guī)劃問題可表達(dá)為:S.t:1.6.1裝卸任務(wù)分配問題用單純型法求解,得出:按照Xij的定義,第1隊(duì)承擔(dān)第2項(xiàng)任務(wù)14.7小時(shí)(占該項(xiàng)任務(wù)的14.7/73=20%),又承擔(dān)第4任務(wù)7.8小時(shí)(占該項(xiàng)任務(wù)的7.8/59=13.3%);第2隊(duì)承擔(dān)第1項(xiàng)任務(wù)20小時(shí)(占100%),又承擔(dān)第2任務(wù)60小時(shí)(占80%);第3隊(duì)承擔(dān)第3項(xiàng)任務(wù)28小時(shí)(占100%),又承擔(dān)第4任務(wù)52小時(shí)(占該任務(wù)的86.7%).也就是說,第4項(xiàng)任務(wù)由第1、第3隊(duì)承擔(dān);第2項(xiàng)任務(wù)由第2隊(duì)承擔(dān);第3項(xiàng)任務(wù)由第3隊(duì)承擔(dān);第1項(xiàng)任務(wù)由第2隊(duì)承擔(dān).1.6.2裝卸工人的調(diào)配問題在汽車運(yùn)輸中,為了減少空駛里程,提高汽車的里程利用率,往往要組織巡回運(yùn)輸。這樣,一輛汽車從車場開出之后,中途就會經(jīng)過若干個裝卸點(diǎn),每個裝卸點(diǎn)因貨物不同,需要的裝卸工人的人數(shù)也不相同,于是就產(chǎn)生了怎樣調(diào)配裝卸工人,才能充分發(fā)揮他們的效率的問題。1.6.2裝卸工人的調(diào)配問題方法1:調(diào)配裝卸工人的簡易方法——編號計(jì)算法當(dāng)車輛比裝卸點(diǎn)多時(shí),裝卸工人固定在裝卸點(diǎn)處/車輛比裝卸點(diǎn)少時(shí),采用編號法。其步驟是:按裝卸點(diǎn)所需要的裝卸工人數(shù)目,由多到少把相應(yīng)的裝卸點(diǎn)編上號碼,按次序排列起來。若有n輛車,就從排列好的需要裝卸工人數(shù)最多的裝卸點(diǎn)一端開始數(shù)n個裝卸點(diǎn)的號碼,看數(shù)到的第n個裝卸點(diǎn)需要多少裝卸工人,就派多少裝卸工人在車上。在需要更多裝卸工人的裝卸點(diǎn)派出相應(yīng)數(shù)目的裝卸工人固定到裝卸點(diǎn)上,跟車裝卸工人數(shù)與固定在裝卸點(diǎn)上的裝卸工人數(shù)之和應(yīng)該等于該點(diǎn)所需要的裝卸工人數(shù)。1.6.2裝卸工人的調(diào)配問題【例1.20】

某物流企業(yè)的車場每天有4輛貨車經(jīng)過6個裝卸點(diǎn)A1,A2,A3,A4,A5,A6,組織巡回運(yùn)輸。在A1點(diǎn)裝貨,需要8個裝卸工人;在A1點(diǎn)卸貨,需要5個裝卸工人;在A5點(diǎn)裝貨,需要3個裝卸工人;在A5點(diǎn)卸貨,需要4個裝卸工人。試制定合理調(diào)配裝卸工人的方案。1.6.2裝卸工人的調(diào)配問題解:此例中,車輛數(shù)為4,裝卸點(diǎn)為6個,是車比裝卸點(diǎn)少的情況,因此不要把裝卸工人全固定到裝卸點(diǎn)上。按照編號計(jì)算法,把所有裝卸點(diǎn)按需要裝卸工人的數(shù)目由多到少排列起來:A3(8人),A1(6人),A4(5人),A2(4人),A6(4人),A5(3人),再根據(jù)車輛數(shù)4,從多的一端開始數(shù)到排好的第四個點(diǎn)(這里是A2)。又A2需要4個裝卸工人,就派4個裝卸工跟車;A3需要8人,就派4個裝卸工固定在A3;A1需要6人,就派2人固定在A1;A4需要5人,則派1人固定在A4;A2,A6,A5就不需派人了。這樣,總共用了4×4+4+2+1=23個裝卸工人。1.6.2裝卸工人的調(diào)配問題車比點(diǎn)多,人往點(diǎn)上擱;

車比點(diǎn)少,編號方法好;按點(diǎn)需要人多少,由大到小編編號,車數(shù)是幾數(shù)到幾,幾個人數(shù)跟車跑。1.6.2裝卸工人的調(diào)配問題方法2:調(diào)配裝卸工人的一般方法——推導(dǎo)求解方法假定有m個裝卸點(diǎn),各點(diǎn)所需要裝卸工人人數(shù)分別為b1,

b2……bm,汽車數(shù)目為n,由于所需要人數(shù)與各點(diǎn)的順序無關(guān),所以我們規(guī)定設(shè)X表示跟車人數(shù),存在某一個整數(shù)k,使循環(huán)運(yùn)輸所需要安裝工人人數(shù)為:為了求f(X)的極小值,我們對X求導(dǎo),并令其為零,即1.6.2裝卸工人的調(diào)配問題由此可見,當(dāng)k=n時(shí),f(X)達(dá)到極值,因此可按如下辦法確定跟車人數(shù):1.如果n>m,則取X=0,即無人跟車,所有裝卸工人均固定在各個裝卸點(diǎn)上.2.如果n≦m,則X取bn與bn+1之間的整數(shù).裝卸作業(yè)所需的裝卸工人人數(shù)為:1.6.2裝卸工人的調(diào)配問題【例1.21】某車場每天有4輛汽車經(jīng)過A1,A2,A3,A4,A5,A6六個點(diǎn)組織循環(huán)運(yùn)輸,在A1裝貨需要6個工人;在A2裝貨需要9個工人;在A3裝貨需要8個工人;在A4卸貨需要6個工人;在A5卸貨需要兩個工人;在A6卸貨需要4個工人。試制定合理調(diào)配裝卸工人的方案。1.6.2裝卸工人的調(diào)配問題解:因?yàn)閙=6,n=4,各裝卸點(diǎn)所需人數(shù)按遞降順序排列成9,8,6,6,4,2。所以跟車人數(shù)為6與4之間的整數(shù),即X=6或X=5或X=4均可.故所需裝卸工人的總?cè)藬?shù)為:如果取X=5,則各點(diǎn)固定人數(shù)分別為:1.6.3裝卸服務(wù)順序問題【例1.22】5個貨主需要在甲、乙兩臺設(shè)備上安排裝卸(例如先在甲卸貨,再到乙裝貨),所需時(shí)間如表1-23所示。T(甲)表示貨主在甲臺設(shè)備上的作業(yè)時(shí)間,T(乙)表示貨主在乙臺設(shè)備上的作業(yè)時(shí)間。貨主ABCDET(甲)0*8*103*7T(乙)1195*34*安排順序一三四二五1.6.3裝卸服務(wù)順序問題第一步,比較表中的各個數(shù)值,找出其中的最小值,本例的最小值為0,這個最小值如果在T(甲)行,則該貨主(本例為A貨主)最先裝卸。如果,在T(乙)行,則該貨主安排在最后裝卸。第二步,把已經(jīng)安排裝卸順序的貨主消去,轉(zhuǎn)第三步。第三步,在剩余的貨主中,繼續(xù)安排裝卸順序,在表中各數(shù)值中,尋找最小值。如果該最小值在T(甲)行,則該貨主安排在前面,如果最小值在T(乙)行,則該貨主安排在后面。重復(fù)第二步和第三步,直至全部安排完為止。注意,如果同一貨主在兩臺設(shè)備上所需裝卸時(shí)間均為最小值時(shí),應(yīng)首先選擇T(甲)行的最小值。如果幾個貨主同臺設(shè)備裝卸時(shí)間均為最小值時(shí),應(yīng)比較在另一臺設(shè)備上的對應(yīng)裝卸時(shí)間。必須把對應(yīng)裝卸時(shí)間較少的貨主排在前面。對應(yīng)裝卸時(shí)間較多的貨主排在后面。按上述步驟對本例排序的結(jié)果是:A貨主第一;D貨主第二;B貨主第三;C貨主第四;E貨主第五。1.6.3裝卸服務(wù)順序問題貨主作業(yè)時(shí)間等待時(shí)間完成時(shí)間ABCDE11-0=1123-3=2028-11=1714-0=1432-21=110+0=03+0=38+3=110+0=010+11=211123281432合計(jì)73351081.6.3裝卸服務(wù)順序問題1.7車載貨物的裝配1.71.7.1

兩種貨物的裝配問題【例1.23】設(shè)某物流企業(yè)有甲貨物每件a1

噸,體積為a2m3;乙貨物每件b1噸,體積為b2m3。每輛車的載重量為k噸,有效容積為vm3。求怎樣配裝這兩種貨物,既能使車輛載滿,又能充分利用車輛的有效容積。1.7.1

兩種貨物的裝配問題解:可設(shè)每輛車裝甲貨x件,裝乙貨y件。由題意知:(1)方程組有正數(shù)的解x0>0,

y0>0且x0和y0又都是整數(shù)時(shí),配裝方案是裝甲貨x0件,裝乙貨y0件。而x0,y0有一個不是整數(shù)時(shí),則應(yīng)在圖(1)所示的四邊形中選一個離點(diǎn)(x0,y0)最近的坐標(biāo)為正整數(shù)的點(diǎn)(

x1,y1),這時(shí)近似最佳配裝方案為裝甲貨x1件,裝乙貨y1件。1.7.1

兩種貨物的裝配問題直線l1:a1x+b1y=k和與l2:

a2x+b2y=v

的交點(diǎn)不在第一象限,這時(shí)交點(diǎn)坐標(biāo)x和y必有一個是負(fù)數(shù),不合要求。此時(shí)應(yīng)該在圖(2)(3)中畫陰影的三角形上找一個離斜邊最近的在斜邊上的坐標(biāo)是正整數(shù)的點(diǎn)(

x2,y2

近似最佳裝配方案為:裝甲貨

x2件,裝乙貨y2件。1.7.1

兩種貨物的裝配問題【例1.24】某物流企業(yè)有甲、乙兩種貨物,甲貨每件重10kg,體積為0.02m3;乙貨每件重2kg,體積為0.005m3。汽車的載重量為4t,有效容積為5.4m3。求最優(yōu)配裝方案。1.7.1

兩種貨物的裝配問題解:設(shè)裝甲貨x件,裝乙貨y件,則有y<0,不符合要求1.7.1

兩種貨物的裝配問題直線4x+y=1080上任何一個坐標(biāo)為非負(fù)整數(shù)的點(diǎn),其坐標(biāo)(x

,y)(0≦x≦270)都是較好的配裝方案。這樣的點(diǎn)也應(yīng)盡量靠近直線5x+y=2000

上述問題,我們既考慮載重量又考慮有效容積,若再考慮使裝載的貨物總價(jià)值最大,則問題就變成了二元背包問題,解起來就復(fù)雜多了。在這里我們不討論這樣的問題。1.7.2裝箱問題裝箱問題:有體積分別為v1,v2,…,vn的n種物品u1,u2,…,un,將其裝到容量為L的箱子里,要求使裝盡這n種物品的箱子數(shù)目達(dá)到最小。1.7.2裝箱問題對n種物品u1,u2,…,un,先按體積從大到小排序。不妨設(shè):

u1≥u2≥…≥un設(shè)箱子的次序?yàn)锽1,B2,…,Bn對于某一個物品ui,它總是被裝到第一個能裝下ui的箱子里。也就是說,對未裝滿的箱子,既不封住,也不搬走,對于物品ui,對所有未裝滿的箱子Bj,從j=1開始順序檢查,只要有Bj能裝下ui,且標(biāo)號小于j的箱子均裝不進(jìn)ui,則把ui裝進(jìn)Bj1.7.2裝箱問題1.7.3運(yùn)用動態(tài)規(guī)劃解裝貨問題設(shè)貨車的載重量上限為G,用于運(yùn)送n種不同的貨物(物品),物品的重量分別為W1,W2,…,Wn每一種物品對應(yīng)于一個價(jià)值系數(shù),分別用P1,P2,…,Pn表示.它表示價(jià)值、運(yùn)費(fèi)或重量等.設(shè)Xk表示第k種物品的裝入數(shù)量,裝貨問題可以表述為:s.t1.7.3運(yùn)用動態(tài)規(guī)劃解裝貨問題可以把裝入一件物品作為一個階段,把裝貨問題化為動態(tài)規(guī)劃問題.動態(tài)規(guī)劃問題求解過程是從最后一個階段開始由后向前推進(jìn).由于裝入物品的先后次序不影響最優(yōu)解,所以我們的求解過程可從第一階段開始,由前向后逐步進(jìn)行.第一步:裝入第1種物品X1件,其最大價(jià)值為第二步:裝入第2種物品X2件,其最大價(jià)值為1.7.3運(yùn)用動態(tài)規(guī)劃解裝貨問題第三步:裝入第3種物品X3件,其最大價(jià)值為第n步:裝入第n種物品Xn件,其最大價(jià)值為1.7.3運(yùn)用動態(tài)規(guī)劃解裝貨問題【例1.25】載重量為8噸的載重汽車,運(yùn)輸4種機(jī)電產(chǎn)品,其重量分別為3,3,4,5噸,試問如何配裝才能充分利用貨車的運(yùn)載能力?物品號重量(噸)價(jià)值系數(shù)1234334533451.7.3運(yùn)用動態(tài)規(guī)劃解裝貨問題在第四階段計(jì)算表中,價(jià)值(本例為載重量)最大值

f4(W)=8,對應(yīng)兩組數(shù)據(jù).其中,一組中X4=0,

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論