Bài toán vận tải đa mục tiêu.

lêi më ®Çu

Cïng víi sù ph¸t triÓn m¹nh mÏ cña khoa häc kü thuËt, c¸c bµi to¸n tèi u xuÊt

hiÖn ngµy cµng nhiÒu vµ tÝnh phøc t¹p cña chóng ngµy cµng lín. Ph¹m vi vµ kh¶

n¨ng øng dông cña c¸c bµi to¸n tèi u còng ngµy cµng ®a d¹ng vµ phong phó.

Líp bµi to¸n tèi u quan träng ®îc nghiªn cøu ®Çu tiªn vµ ®îc øng dông nhiÒu

nhÊt lµ bµi to¸n quy ho¹ch tuyÕn tÝnh (linear programming). §ã lµ m« h×nh to¸n häc

cña mét líp réng lín c¸c bµi to¸n øng dông trong kinh tÕ vµ kü thuËt. Do ®ã cÊu tróc

cña líp bµi to¸n quy ho¹ch tuyÕn tÝnh cã nhiÒu tÝnh chÊt rÊt tèt vÒ mÆt to¸n häc, ngêi

ta ®· t×m ®îc c¸c thuËt gi¶i rÊt h÷u hiÖu cho bµi to¸n nµy. N¨m 1947 nhµ to¸n häc

Mü G.B. Dantzig ®· nghiªn cøu vµ ®Ò xuÊt ra thuËt to¸n ®¬n h×nh (simplex method)

®Ó gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh. ThuËt to¸n ®¬n h×nh ®îc ph¸t triÓn m¹nh mÏ

trong nh÷ng n¨m sau ®ã vµ ®îc xem lµ mét ph¬ng ph¸p kinh ®iÓn ®Ó gi¶i c¸c bµi

to¸n quy ho¹ch tuyÕn tÝnh. §©y lµ mét ph¬ng ph¸p ®îc sö dông cã thÓ nãi lµ réng r·i

nhÊt. Cã ba lý do chÝnh:

Mét lµ: RÊt nhiÒu vÊn ®Ò thùc tÕ, trong nhiÒu lÜnh vùc kh¸c nhau cã thÓ ®a vÒ

bµi to¸n quy ho¹ch tuyÕn tÝnh.

Hai lµ: Trong nhiÒu ph¬ng ph¸p gi¶i c¸c bµi to¸n phi tuyÕn, bµi to¸n tuyÕn tÝnh

xuÊt hiÖn nh lµ mét bµi to¸n phô cÇn ph¶i gi¶i trong nhiÒu bíc lÆp.

Ba lµ: Ph¬ng ph¸p ®¬n h×nh lµ ph¬ng ph¸p hiÖu qu¶ ®Ó gi¶i bµi to¸n quy ho¹ch

tuyÕn tÝnh.

Ngµy nay, b»ng thuËt to¸n ®¬n h×nh vµ c¸c d¹ng c¶i biªn cña chóng, ngêi ta cã

thÓ gi¶i rÊt nhanh c¸c bµi to¸n QHTT cì lín.

Líp c¸c bµi to¸n vËn t¶i lµ trêng hîp ®Æc biÖt cña quy ho¹ch tuyÕn tÝnh, bëi vËy

cã thÓ dïng c¸c ph¬ng ph¸p cña quy ho¹ch tuyÕn tÝnh ®Ó gi¶i. Tuy nhiªn, do tÝnh

chÊt ®Æc thï riªng cña nã, ngêi ta x©y dùng c¸c ph¬ng ph¸p gi¶i riªng.

Th«ng thêng khi nãi ®Õn bµi to¸n vËn t¶i ta thêng liªn hÖ ngay ®Õn bµi to¸n vËn

t¶i hai chØ sè, bëi ®©y lµ bµi to¸n vËn t¶i kinh ®iÓn cã nh÷ng ph¬ng ph¸p gi¶i hay.

Bªn c¹nh ®ã, ngêi ta cßn xÐt mét sè c¸c bµi to¸n vËn t¶i më réng nh bµi to¸n vËn t¶i

Trang: 1

ba chØ sè, bµi to¸n vËn t¶i kho¶ng, bµi to¸n vËn t¶i ®a môc tiªu vµ rÊt nhiÒu bµi to¸n

kh¸c, ®ã lµ c¸c biÕn thÓ cña bµi to¸n vËn t¶i kinh ®iÓn trªn.

Trong khu«n khæ kho¸ luËn nµy, em xem xÐt vµ nghiªn cøu mét sè bµi to¸n më

réng trong líp c¸c bµi to¸n vËn t¶i më réng ®ã. §ã lµ c¸c bµi to¸n: Bµi to¸n vËn t¶i

ba chØ sè (solid transport problem) kh«ng h¹n chÕ vµ cã h¹n chÕ kh¶ n¨ng th«ng

qua, Bµi to¸n vËn t¶i ba chØ sè kho¶ng (interval solid transport problem) vµ giíi

thiÖu mét sè Bµi to¸n vËn t¶i ®a môc tiªu.

Cuèi cïng, em xin bµy tá lßng biÕt ¬n s©u s¾c nhÊt ®èi víi thµy gi¸o híng dÉn

Th¹c sü Vò TiÕn ViÖt, ngêi ®· tËn t×nh chØ b¶o, gióp ®ì em trong qu¸ tr×nh hoµn

thµnh kho¸ luËn nµy. Em còng xin ch©n thµnh c¶m ¬n sù gióp ®ì nhiÖt t×nh cña c¸c

thÇy c« trong khoa To¸n - Tin, Häc viÖn An ninh Nh©n d©n.

Trang: 2

Ch¬ng I. Bµi to¸n quy ho¹ch tuyÕn tÝnh

Trong viÖc nghiªn cøu c¸c bµi to¸n tèi u nãi chung, gi¶i tÝch låi gi÷ mét vai trß

rÊt quan träng. Nã ®îc sö dông lµm c¬ së to¸n häc trong viÖc x©y dùng c¸c thuËt

to¸n.

Quy ho¹ch tuyÕn tÝnh lµ mét trong nh÷ng líp bµi to¸n tèi u ®îc nghiªn cøu

träng vÑn c¶ vÒ ph¬ng diÖn lý thuyÕt lÉn thùc hµnh, Bµi to¸n vËn t¶i lµ mét d¹ng ®Æc

biÖt cña QHTT. Do ®ã ch¬ng nµy nh»m giíi thiÖu mét sè kh¸i niÖm vµ kiÕn thøc c¬

b¶n vÒ gi¶i tÝch låi vµ QHTT.

1.1 Mét sè kh¸i niÖm vÒ gi¶i tÝch låi

1.1.1 Kh«ng gian Euclude

Mét vector n chiÒu trªn trêng sè thùc lµ mét bé ®îc s¾p thø tù gåm n sè thùc

x=(x1, x2, ..., xn). C¸c xi, i =1, ..., n gäi lµ c¸c thµnh phÇn hay to¹ ®é cña vector. VÝ

dô x=(4,5,10,20).

Hai vect¬ x vµ y gäi lµ b»ng nhau x=y, nÕu xi=yi, ∀i =1, ..., n.

XÐt hai phÐp to¸n trªn c¸c vector:

PhÐp céng: x+y=(x1+y1, x2+y2, ..., xn+yn)

PhÐp nh©n: αx=(αx1, αx2, ..., αxn), ∀α ∈ R

Khi ®ã tËp hîp tÊt c¶ c¸c vector n chiÒu trong ®ã x¸c ®Þnh phÐp céng c¸c vector,

nh©n mét sè thùc víi vector nh trªn t¹o thµnh kh«ng gian tuyÕn tÝnh n chiÒu trªn tr￾êng sè thùc R, ký hiÖu Rn

.

C¸c vector x(i) ∈R

n

, i =1, ..., m ®îc gäi lµ ®éc lËp tuyÕn tÝnh nÕu:

Trang: 3

x i

i m

i

m

i

i

0 0, 1,

( )

1

∑ = ⇔ = =

=

α α

NÕu: ∑=

=

m

i

i

i

x x

1

( )

α víi Ýt nhÊt mét αi ≠ 0 th× x gäi lµ tæ hîp tuyÕn tÝnh cña c¸c

x

(i), i =1, ..., m. H¬n n÷a nÕu αi > 0, i =1, ..., m vµ ∑=

=

m

i

i

1

α 1 th× x gäi lµ tæ hîp låi

cña c¸c x(i), i =1, ..., m.

Trong Rn

cã n vector ®éc lËp tuyÕn tÝnh lËp thµnh c¬ së cña nã.

Gi¶ sö e(1), e(2), ..., e(n) lµ mét c¬ së cña Rn

th× bÊt kú mét vector x ∈ Rn

®Òu lµ tæ

hîp tuyÕn tÝnh cña c¸c vector e(1), e(2), ..., e(n). Ta gäi tÝch v« híng cña hai vector

x=(x1, x2, ..., xn) vµ y=(y1, y2, ..., yn), ký hiÖu, <x,y>, lµ mét sè b»ng.

TÝch v« híng lµ mét d¹ng song tuyÕn tÝnh, ®èi xøng, kh«ng ©m, tøc lµ:

1. <x,y> = <y, x>. ∀x,y ∈ Rn

2. <x(1) + x(2), y >=< x(1), y >+< x(2), y>. ∀x

(1), x(2), y ∈ Rn

3. <λx,y> = λ<x,y>. ∀x,y ∈ Rn

4. <x,x> ≥ 0, ∀x∈ Rn

dÊu b»ng xÈy ra khi vµ chØ khi x= 0.

§é dµi cña vector x=(x1, x2, ..., xn) lµ mét sè x¸c ®Þnh bëi.

Kho¶ng c¸ch gi÷a hai vector x vµ y lµ mét sè x¸c ®Þnh bëi:

Kh«ng gian vector trong ®ã cã tÝch v« híng vµ kho¶ng c¸ch nh trªn gäi lµ

kh«ng gian Euclude.

1.1.2 TËp compact

D·y {x(k) }⊂R

n

k=1, 2, ... ®îc gäi lµ cã giíi h¹n x(0) khi k → ∞ vµ viÕt

lim x(k) = x(0), nÕu

Trang: 4

∑=

= < > =

n

i

i

x x x x

1

2

,

lim ( , ) 0

( ) (0)

=

→∞

x x

k

k

ρ

∑=

< >=

n

i

i i

x y x y

1

,

k → ∞

( ) ∑ ( )

=

= − = < − − > = −

n

i

i i x y x y x y x y x y

1

2

ρ , ,

H×nh cÇu t©m a b¸n kÝnh ρ lµ tËp S={x∈R

n

:x-a≤ ρ }. H×nh cÇu nµy t¹o nªn

ρ- l©n cËn cña ®iÓm a, hay gäi lµ l©n cËn cña a.

* NÕu tËp A⊂R

n

chøa cïng víi ®iÓm x mét l©n cËn cña nã th× x gäi lµ ®iÓm

trong cña A. NÕu trong l©n cËn bÊt kú cña x ∈ A cã c¸c ®iÓm cña A vµ c¸c ®iÓm

kh«ng thuéc A th× x gäi lµ ®iÓm biªn cña tËp hîp A.

* Mét tËp A⊂R

n

gäi lµ giíi néi nÕu nã ®îc chøa trong mét h×nh cÇu t©m O nµo

®ã, tøc lµ tån t¹i sè ρ ®ñ lín sao cho víi mäi x∈A,x≤ ρ. Mét d·y {x(k)} héi tô th×

bao giê còng giíi néi.

* Mét tËp hîp G⊂R

n

®îc gäi lµ më nÕu víi mäi x∈G ®Òu tån t¹i mét h×nh cÇu

t©m x n»m gän trong G. Mét tËp F⊂R

n

®îc gäi lµ ®ãng nÕu víi mäi d·y héi tô{x(k)}⊂

F ta ®Òu cã: x F

k

k

∈

→∞

( )

lim

Mét tËp chøa mäi ®iÓm biªn cña nã lµ tËp ®ãng.

* TËp C ®îc gäi lµ tËp Compact nÕu tõ mäi d·y v« h¹n {x(k)} thuéc C ®Òu cã thÓ

trÝch ra mét d·y con {x(ki)} héi tô tíi phÇn tö thuéc C. TËp C lµ Compact khi vµ chØ

khi C ®ãng vµ giíi néi. TËp Compact M cña tËp ®ãng C còng ®ãng trong C. TËp con

®ãng M cña tËp Compact còng Compact.

Hµm f(x) liªn tôc trªn tËp Compact C th× sÏ ®¹t cùc trÞ trªn tËp Êy.

1.1.3 TËp låi

Cho hai ®iÓm a, b ∈R

n

. Ta gäi ®êng th¼ng qua a, b lµ tËp ®iÓm cã d¹ng

x∈R

n

: x = λa + (1-λ)b, λ ∈ R.

§o¹n th¼ng nèi hai ®iÓm a, b lµ tËp låi c¸c ®iÓm cã d¹ng

x∈R

n

:x = λx + (1-λ)y, 0 ≤ λ ≤ 1

* Mét tËp M⊂R

n

®îc gäi lµ mét ®a t¹p affine nÕu víi hai ®iÓm bÊt kú

x, y ∈M th× toµn bé ®êng th¼ng ®i qua hai ®iÓm ®ã còng thuéc M.

Tøc lµ λx + (1-λ)y ∈M : ∀x,y ∈M, ∀ λ∈R.

* Mét siªu ph¼ng trong kh«ng gian Rn

lµ tËp hîp tÊt c¶ c¸c ®iÓm

x=(x1, x2, ..., xn) ∈R

n

tháa m·n ph¬ng tr×nh tuyÕn tÝnh

Trang: 5

a1x1+ a2x2+ ... + anxn = α trong ®ã a1, a2, ..., an , α ∈R

* TËp hîp c¸c ®iÓm x=(x1, x2, ..., xn) ∈R

n

tho¶n m·n bÊt ph¬ng tr×nh tuyÕn tÝnh

a1x1+ a2x2+ ... + anxn ≤ α ®îc gäi lµ nöa kh«ng gian ®ãng.

* Nöa kh«ng gian ®îc cho bëi a1x1+ a2x2+ ... + anxn < α ®îc gäi lµ nöa kh«ng

gian më.

* TËp X⊂R

n ®îc gäi lµ tËp låi nÕu cïng víi viÖc chøa hai ®iÓm x, y nã chøa c¶

®o¹n th¼ng chøa hai ®iÓm Êy, tøc lµ chøa tÊt c¶ c¸c ®iÓm cã d¹ng:

λx + (1-λ)y, 0 ≤ λ ≤ 1

VÝ dô vÒ c¸c tËp låi: Kh«ng gian Euclide, c¸c nöa kh«ng gian, mÆt ph¼ng, nöa

mÆt ph¼ng, h×nh ch÷ nhËt, h×nh vu«ng, h×nh elip, h×nh hép, h×nh cÇu ...

* Mét tËp hîp lµ giao cña mét sè h÷u h¹n c¸c nöa kh«ng gian ®ãng ®îc gäi lµ

tËp låi ®a diÖn.

MÖnh ®Ò: Giao cña hai tËp låi lµ mét tËp låi.

HÖ qu¶ 1. Giao cña mét sè bÊt kú tËp hîp låi lµ tËp låi.

HÖ qu¶ 2. MiÒn chøa nghiÖm cña mét hÖ bÊt ph¬ng tr×nh tuyÕn tÝnh d¹ng.

lµ mét tËp låi (®a diÖn låi). Mét tËp låi ®a diÖn giíi néi gäi lµ mét ®a diÖn. Giao

cña tÊt c¶ c¸c tËp låi chøa tËp X gäi lµ bao låi cña nã, ký hiÖu [X]

1.1.4 Hµm låi

* Mét hµm sè f(x) x¸c ®Þnh trªn tËp låi C ⊂ Rn ®îc gäi lµ hµm låi trªn C, nÕu

víi mäi x, y ∈C vµ 0 ≤ λ ≤ 1 ta cã f(λx + (1-λ)y) ≤ λf(x) + (1-λ)f(y).

* Hµm f(x) ®îc gäi lµ hµm låi chÆt nÕu víi mäi x, y ∈C vµ 0 ≤ λ ≤ 1 ta cã. f(λx

+ (1-λ)y) < λf(x) + (1-λ)f(y).

* Hµm f(x) ®îc gäi lµ hµm lâm (lâm chÆt) nÕu - f(x) lµ hµm låi (låi chÆt)

Trang: 6

.

...

. . . . . . . . . . . . . . . . . . . .

...

...

1 1 2 2

21 1 22 2 2 2

11 1 12 2 1 1















+ + + ≤

+ + + ≤

+ + + ≤

n n nn n n

n n

n n

a x a x a x b

a x a x a x b

a x a x a x b

* Hµm f(x) x¸c ®Þnh trªn C ®¹t cùc tiÓu tuyÖt ®èi t¹i x* ∈C nÕu

f(x*

) ≤ f(x):∀ x∈C

* Hµm f(x) ®¹t cùc tiÓu ®Þa ph¬ng t¹i x* ∈ C nÕu tån t¹i l©n cËn më U cña x*

sao cho f(x*) ≤ f(x):∀ x∈C ∩U

MÖnh ®Ò 1: BÊt kú ®iÓm cùc tiÓu ®Þa ph¬ng nµo cña hµm låi trªn tËp låi còng lµ

®iÓm cùc tiÓu tuyÖt ®èi.

HÖ qu¶: BÊt kú ®iÓm cùc ®¹i ®Þa ph¬ng nµo cña hµm lâm còng lµ cùc ®¹i tuyÖt

®èi.

MÖnh ®Ò 2: Cùc ®¹i cña mét hµm låi (nÕu cã) trªn mét tËp låi cã ®iÓm cùc biªn

bao giê còng ®¹t t¹i mét ®iÓm cùc biªn.

1.2 Bµi to¸n Quy ho¹ch tuyÕn tÝnh

QHTT b¾t nguån tõ nh÷ng nghiªn cøu cña nhµ to¸n häc Nga næi tiÕng, ViÖn sü

L.V. Kantorovich trong mét lo¹t c¸c c«ng tr×nh vÒ bµi to¸n kÕ ho¹ch ho¸ s¶n xuÊt,

c«ng bè n¨m 1938. N¨m 1947 nhµ to¸n häc Mü G.B. Dantzig ®· nghiªn cøu vµ ®Ò

xuÊt ph¬ng ph¸p ®¬n h×nh (Simplex method) ®Ó gi¶i bµi to¸n QHTT. N¨m 1952 ph-

¬ng ph¸p ®¬n h×nh ®· ®îc ch¹y trªn m¸y tÝnh ®iÖn tö cña Mü.

1.2.1 Bµi to¸n quy ho¹ch tuyÕn tÝnh

 Bµi to¸n tæng qu¸t.

§Ó nhÊt qu¸n lËp luËn ta xÐt bµi to¸n t×m cùc ®¹i, sau ®ã ta xÐt c¸ch chuyÓn bµi

to¸n t×m cùc tiÓu sang t×m cùc ®¹i. Bµi to¸n tæng qu¸t cña QHTT cã d¹ng:

Ký hiÖu: A=(aij)mxn lµ ma trËn víi c¸c phÇn tö aij

(1.1) gäi lµ hµm môc tiªu, (1.2) lµ c¸c r»ng buéc.

NÕu gÆp bµi to¸n Min, tøc lµ

Trang: 7

( )

x D

f x c x j

n

j

j

∈

=∑ →

=

min

1

max (1.1)

1

∑ →

=

j

n

j

j c x

( ) ( )

0, 1,..., (1.3)

, , , 1,..., 1.2

1

x j n

a x b i m

j

i

n

j

ij j

≥ =

∑ ≤ = ≥ =

=