Bài giảng Phương pháp trợ giúp ra quyết định - Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM

Chương 6: Ra quyết định đa mục tiêu

Khoa KTXD - Bộ môn KTTNN

Chương 6: Ra quyết định đa mục tiêu

NỘI DUNG MÔN HỌC

Chương 1: Giới thiệu.

Chương 2 : Cơ sở lý thuyết ra quyết định.

Chương 3 : Quy hoạch tuyến tính.

Chương 4 : Bài toán vận tải.

Chương 5 : Quản lý kho.

Chương 6 : Ra quyết định đa mục tiêu.

Chương 7 : Phương pháp AHP.

Chương 8 : Qui hoạch động.

Giảng viên: PGS. TS. NGUYỄN THỐNG

E-mail: [email protected] or [email protected]r

Web: http://www4.hcmut.edu.vn/~nguyenthong/

Chương 9 : Mô phỏng Monte Carlo.

1

8/29/2016

2

PGS. TS. Nguyễn Thống

Té l. (08) 38 691 592- 098 99 66 719

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

GIꢀI THIꢁU VꢂN Đꢃ

Tꢄm lꢅi giꢆi tꢇi ưu cꢈa bꢉi toꢊn cꢋ MꢌT

HꢍM MꢎC TIÊU DUY NHꢂT

 BꢍI TOÁN ĐƠN MꢎC TIÊU (ra quyꢏt

đꢐnh cho bꢉi toꢊn đơn mꢑc tiêu).

Trong trưꢅng hꢒp nꢉy, vꢓi phương

phꢊp giꢆi thích hꢒp  MꢔI NGƯꢕI

đꢖu ꢗm ra CꢘNG MꢌT LꢕI GIꢙI (tꢇi

ưu).

Ví dꢑ  Quy hoaïch tuyeán tính hoaëc

Quy hoaïch phi tuyeán, Quy hoạch

động  Quy hoaïch ñôn muïc tieâu.

8/29/2016

3

8/29/2016

4

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

GIꢀI THIꢁU VꢂN Đꢃ

Ví dꢑ: Tꢄm quy mô “hꢒp lꢞ” (lꢅi giꢆi) cho

mꢟt khu công nghiꢠp phꢑc vꢑ nhiꢖu mꢑc

tiêu đꢡng thꢅi:

Trong trưꢅng hꢒp khꢊc, ꢗm lꢅi giꢆi bꢉi

toꢊn vꢓi Cꢚ ĐꢛNG THꢕI NHIꢃU HꢍM

MꢎC TIÊU phꢆi “THꢜA MꢝN”  BꢍI

TOÁN ĐA MꢎC TIÊU.

 Phꢊt triꢢn khu vꢣc (giao thông)

 Doanh thu (cho thuê đꢤt) mang vꢖ

 Dân sinh (giꢆi tꢥa di dꢅi).

 ……..

8/29/2016

5

8/29/2016

PGS. Dr. Nguyễn Thống

6

PGS. Dr. Nguyễn Thống

1

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Vꢓi bꢉi toꢊn ĐA MꢎC TIÊU 

HꢍM MꢎC TIÊU

 Hꢉm mꢑc tiêu bao gꢡm nhiꢖu

hàm đơn mꢑc tiêu.

Thông thưꢅng KHÔNG THꢦ TÌM RA LꢕI

GIꢙI TꢧI ƯU CHO MꢔI MꢎC TIÊU.

Không cꢋ lꢅi giꢆi tꢇi ưu tuyꢠt đꢇi.

 Chꢨ tꢄm đưꢒc lꢅi giꢆi thoꢆ mãn “tương

đꢇi” cꢊc hꢉm mꢑc tiêu đơn.

8/29/2016

PGS. Dr. Nguyễn Thống

7

8/29/2016

PGS. Dr. Nguyễn Thống

8

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Heä phöông trình toaùn hoïc cuûa quy hoaïch ña

muïc tieâu

MÔ HÌNH TOÁN

BꢀI TOÁN

Max f (X )

1





i

Maxf₂(Y )

i



HMT Min f (Z )



3

i



ĐA MꢁC TIÊU

.



Raøng buoäc:

g_i(X_i) = b_i





Min f_n(T )

i

------------------

h_i(Y_i) = c_i

f_ichæ caùc haøm ñôn muïc tieâu.

i ,

8/29/2016

9

8/29/2016

10

_PGSX_{. Dr. N}Y_gu,_yễZ_n,_ThT_ống bieán quyeát ñònh

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

CÁC BƯỚC GIꢀI QUYꢁT BꢂI TOÁN

ĐA MỤC TIÊU

CAÙC PHÖÔNG PHAÙP P/TÍCH ÑA MUÏC TIEÂU

• Moâ hình cöïc.

1. Xaùc ñònh caùc bieán quyeát ñònh.

2. Thieát laäp caùc haøm ñôn muïc tieâu.

3. Thieát laäp caùc raøng buoäc cho töøng haøm ñôn

muïc tieâu (neáu coù).

• Moâ hình tính vaø cho ñieåm.

• Moâ hình theo hieäu quaû vaø chi phí.

• Moâ hình vôùi lôïi ích chung.

• Moâ hình thoûa hieäp.

• Moâ hình AHP (Analysys Hierachy Processus)

(Saép xeáp theo thöù töï töø ñôn giaûn ñeán phöùc taïp).

4. Xaùc laäp caùc phöông aùn xem xeùt (lôøi giaûi).

5. Duøng phöông phaùp phaân tích ña muïc tieâu

thích hôïp ñeå löïa choïn phöông aùn.

8/29/2016

PGS. Dr. Nguyễn Thống

11

8/29/2016

PGS. Dr. Nguyễn Thống

12

2

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH CỰC

Theo ñoà thò neâu treân ta coù 3 phöông aùn ñeå so

saùnh vaø ñöa ra löïa choïn.

LÔØI GIAÛI BÒ TROÄI

Ñoù laø lôøi giaûi maø caùc tieâu chí cuûa noù ñeàu

“keùm” lôøi giaûi so saùnh khaùc.

Ñaây laø moâ hình söû duïng trong giai ñoaïn ñaàu

tieân ñeå coù yù töôûng choïn phöông aùn.

NHANH

RẼ

Vôùi ví duï treân ta coù lôøi giaûi 3 bò troäi bôûi lôøi giaûi

2  lôøi giaûi 3 (bò troäi) seõ bò loaïi “tröïc tieáp”.

NHIỀU

---: LỜI GIꢀI 1

---: LỜI GIꢀI 2

Baøi toaùn coøn laïi chæ coøn so saùnh giöõa 1 & 2.

8/29/2016

14

8/29/2016

PGS. Dr. Nguyễn Thống

13

TỐT

….:LỜI GIꢀI 3

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MOÂ HÌNH TÍNH & CHO ĐIỂM

Caùc lôøi giaûi seõ ñöôïc ñaùnh giaù theo thang ñieåm

MOÂ HÌNH THEO HIỆU ÍCH & CHI PHÍ

Phöông phaùp ñöôïc minh hoïa bôûi ñoà thò sau:

cho töøng yeáu toá so saùnh.

HIỆU ÍCH, R

Nhanh

Nhieàu

2

Toát

2

Reõ

R_MIN

Ñieåm

A

3

x

2

x

1

3

x

1

x

3

x

1

x

3

2

x

1

x

Toång

lời giải có thể

CHI PHÍ, I

R_A

10

6

Lôøi giaûi A(I_A,R_A)

B

x

C

x

8

I_A

I_MAX

 Lôøi giaûi A ñöôïc kieán nghò.

8/29/2016

PGS. Dr. Nguyễn Thống

15

8/29/2016

PGS. Dr. Nguyễn Thống

16

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH LỢI ÍCH CHUNG

Phương pháp được tiến hành trên bản đánh giá (cho điểm theo

thang giống hoặc khác nhau) cho các lời giải với các tiêu chí

xem xét khác nhau. Bảng tổng hợp có dạng như sau:

Theo phöông phaùp naøy, lôøi giaûi seõ

ñöôïc xaùc ñònh töø caùc yeáu toá sau:

• Hieäu suaát R phaûi lôùn hôn giaù trò

R_minyeâu caàu.

Trọng số Lời giải

A¹

A²

.

A^m

Tieâu chí

α¹

α²

α^.

F¹

Z^1,1

Z^2,1

.

Z^2,2

.

F²

.

• Chi phí I khoâng vuôït quaù khaû

.

naêng I_max

.

αⁿ

Fⁿ

.

Z^n,m

S^m¹⁸

8/29/2016

Sum

S¹

S²

8/29/2016

PGS. Dr. Nguyễn Thống

17

PGS. Dr. Nguyễn Thống

3

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

• n : số tiêu chí xét

• m : số lời giải khảo sát (số phương án so sánh)

• Z_i,j: giá trị đánh giá của lời giải j theo tiêu chí i.

NHꢩN XꢪT

Giꢊ trꢐ theo hꢉng (tꢫng tiêu chí)

phꢆi cꢋ giꢊ trꢐ Min & Max KHÁC

NHAU, nꢏu KHÔNG  tiêu chí đꢋ

KHÔNG Cꢚ NGHꢬA đꢢ phân biꢠt

phương ꢊn so sꢊnh  tiêu chí bꢐ

LOꢭI tꢫ đꢮu.

• α_itrọng số ñaùnh giaù möùc ñoä quan troïng tương

đối của caùc tieâu chí F_i

Chú ý

• Các giá trị Z_ijtrong cùng một hàng phải có cùng

đơn vị.

• Các giá trị Z_ijtrong cùng một cột có thể khác

đơn vị.

8/29/2016

PGS. Dr. Nguyễn Thống

19

8/29/2016

PGS. Dr. Nguyễn Thống

20

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

NHꢩN XꢪT BꢍI TOÁN

CÓ 3 LOꢭI BꢍI TOÁN

 Bài toán Max

 Bài toán Min

Vꢖ nguyên tắc đꢟ lꢓn cꢈa các đại

lưꢒng đꢊnh giá các tiêu chí là KHÁC

NHAU (thang đo).

 Bꢉi toꢊn hꢯn hꢒp (Max+Min)

 Vꢖ nguyên tắc đơn vꢐ đꢊnh giá cꢈa

các tiêu chí là KHÁC NHAU.

8/29/2016

PGS. Dr. Nguyễn Thống

22

8/29/2016

PGS. Dr. Nguyễn Thống

21

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

ÔN THꢧNG KÊ

 PHꢙI LOꢭI Bꢜ ĐƠN VỊ ĐO CꢰA

Sꢧ LIꢁU (TꢱNG HꢍNG) & LOꢭI

Bꢜ ꢙNH HƯꢲNG Đꢌ LꢀN THANG

PP1: Sử dꢑng phép biꢏn đổi gọi là TRUNG TÂM HOÁ & CHUẨN

HOÁ đꢢ loại ꢆnh hưꢳng đơn vꢐ & thang đo (Standadized):

T  T

with t_i 0;_t1

i

t_i

i

ĐO

_T

i

t_i biꢏn chuẩn hoá & trung tâm hoá (không cꢋ đơn vꢐ)

T_i biꢏn nghiên cứu

 giá trꢐ TB cꢈa biꢏn T

 đꢟ lꢠch chuẩn



T

8/29/2016

PGS. Dr. Nguyễn Thống

24

8/29/2016

PGS. Dr. Nguyễn Thống

23

4

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

ÔN THꢧNG KÊ

PP2: Biꢏn đổi T_i t_itheo phép biꢏn đổi

(Normalized): :

PP3: Biꢏn đổi T_i t_itheo phép biꢏn đổi

(Adjusted normalized):

T T_min

T_maxT_min

i

T  T_min

T_max T_min

i

t_i

 t_i

0,1

 

t_i 2*

1  t_i



1,1



 t_iKHÔNG ĐƠN VỊ

8/29/2016

25

8/29/2016

26

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

TRỪỜNG HỢP BꢂI TOÁN MAX

a. Biến đổi Z_ijtrong mỗi hàng i thành các số b_ij

không thứ nguyên và khꢃ thang đo:

BꢍI TOÁN MAX

Z_ij Z_{ij(min i)}

b_ij

Z_{ij(max i)} Z_{ij(min i)}

GIÁ TRỊ MIN HꢀNG i

GIÁ TRỊ MAX HꢀNG i

8/29/2016

PGS. Dr. Nguyễn Thống

28

8/29/2016

PGS. Dr. Nguyễn Thống

27

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

b. Mꢯi tiêu chí F_isẽ gắn vꢓi hꢠ sꢇ

α_itùy theo mức đꢟ quan trọng

(chꢈ quan).

CHÚ Ý

Sau khi biꢏn đổi biꢏn  b_ij

thay đổi trong khoꢆng [0 

1]

8/29/2016

PGS. Dr. Nguyễn Thống

30

8/29/2016

PGS. Dr. Nguyễn Thống

29

5

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH LỢI ÍCH CHUNG

Cꢋ thꢢ gꢊn giꢊ trꢐ α_ithay đổi xung

quanh giꢊ trꢐ 1:

Trọng số

Lời giải

A¹

A²

.

A^m

Tieâu chí

α¹

α²

α^.

F¹

F²

b^1,1

b^2,1

.

b^2,2

.

 α_i> 1 yꢏu tꢇ “quan trọng”,

 α_i< 1 yꢏu tꢇ “ít quan trọng”,

 α_i=1 yꢏu tꢇ “trung hꢴa”.

Cꢋ thꢢ gꢊn dạng

.

αⁿ

Fⁿ

.

b^n,m

S^m



1



i

Sum

S¹

S²

i

S₁=SUM PRODUCT

8/29/2016

PGS. Dr. Nguyễn Thống

31

8/29/2016

PGS. Dr. Nguyễn Thống

32

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

TRỪỜNG HỢP BꢂI TOÁN MIN

c. Tính (Sum)_jcho các phương án j:

a. Biến đổi Z_ijtrong mỗi hàng i thành các số b_ij

không thứ nguyên và loại bỏ ảnh hưởng

thang đo:

n

(Sum)   b



j

i ij

i1

Z_{ij(max i)} Z_ij

b_ij

 Lời giải chọn sẽ là : (Sum)_j Max

i caùc tieâu chí

Z_{ij(max i)} Z_{ij(min i)}

j  caùc phöông aùn so saùnh ñeå choïn löïa

b. Mỗi tiêu chí sẽ gắn với hệ số α tùy theo mức

8/29/2016

33

8/29/2016

34

độ quan trọng (chủ quan).

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Bài tập: Một Chủ đầu tư muốn thực hiện một dự án với

4 hàm mục tiêu F_ikhác nhau. Có 4 nhà thầu A_jđược

xem xét. Kết quả đánh giá tổng hợp trong bảng sau.

Xác định nhà thầu chọn theo phương pháp đánh giá

lợi ích chung (bài toán max).

c. Tính (Sum)_jcho các phương án j:

n

(Sum)   b



j

i ij

i1

Vôùi:

• F₁: Naêng löïc quaûn lyù (cao nhaát ñöôïc ñaùnh giaù 5).

• F₂: Voán löu ñoäng (tyû VNÑ).

 Lời giải chọn sẽ là : (Sum)_j Max

i caùc tieâu chí

• F₃: Döï aùn töông töï ñaõ thöïc hieän 3 naêm gaàn nhaát.

• F₄: Coâng nhaân laønh ngheà treân 10 naêm.

j  caùc phöông aùn so saùnh ñeå choïn löïa

8/29/2016

PGS. Dr. Nguyễn Thống

36

8/29/2016

35

PGS. Dr. Nguyễn Thống

6

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Höôùng daãn: Kieán nghò A4

Keát quaû ñaùnh giaù ñöôïc toång hôïp nhö sau:

Nhaø thaàu



A1

A2

A3

A4



A1

5

100

2

A2

3

80

6

A3

1

120 140

8

40

A4

2

Tieân chí

1.20

1.00

0.90

1.00

Sum

1.00

0.33

0.00

0.67

2.20

0.50

0.00

0.67

0.00

1.20

0.00

0.67

1.00

0.33

1.90

0.25

1.00

0.00

1.00

2.30

F1

1.2

1.0

0.9

1.0

F2

F3

2

60

F4

50

30

Kieán nghò nhaø thaàu theo moâ hình lôïi ích chung ?

8/29/2016

37

8/29/2016

38

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Keát quaû ñaùnh giaù toång hôïp nhö sau:

Nhaø thaàu

Bài tập: Một Chủ đầu tư muốn thực hiện một dự

án. Có 4 nhà thầu A_jđược xem xét. Có 3 tiêu

chí F_iđể so sánh chọn nhà thầu. Kết quả đánh

giá tổng hợp trong bảng sau. Xác định nhà thầu

chọn theo phương pháp đánh giá lợi ích chung



A1

A2

A3

A4

4

Tieâu chí

1.1

10

8

1

F1

(bài toán min).

F1: toång t/gian thực hiện döï aùn bò treå trong 5 naêm

1.0 0.45

0.9

0.5

12

0.45

10

0.6

4

F2

gaàn nhaát (thaùng).

F2: tyû leä voán vay treân voán töï coù.

5

F3

F3: nôï Coâng ty phaûi traõ trong 2 naêm ñeán (tyû).

8/29/2016

39

8/29/2016

40

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Höôùng daãn: Kieán nghò A3

BꢍI TOÁN HꢵN HỢP



A1

A2

A3

A4

Đꢋ lꢉ bꢉi toꢊn mꢉ cꢊc hꢉm

đơn mꢑc tiêu (tiêu chí) cꢋ

hꢉm Min & Max ĐꢛNG THꢕI

hiꢠn hꢶu.

1.10

1.00

0.90

Sum

0.00

1.00

0.88

1.79

0.22

0.67

0.00

0.91

1.00

0.25

2.33

0.67

0.00

1.00

1.63

8/29/2016

41

8/29/2016

42

PGS. Dr. Nguyễn Thống

7

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Bài tập: Mꢟt Chꢈ đꢮu tư muꢇn chọn mꢟt trong 4

nhà thꢮu A_jdꢣa vꢉo 4 tiêu chí F_i, đꢢ thꢣc hiꢠn

mꢟt dꢣ án. Kꢏt quꢆ đꢊnh giá tổng hꢒp trong

bꢆng sau. Xác đꢐnh nhà thꢮu chọn theo phương

pháp đꢊnh giá lꢒi ích chung.

• F₁: Vꢇn lưu đꢟng (tr. $)

• F₂: Sꢇ công trꢄnh tương tꢣ thꢣc hiꢠn trong 5

năm gꢮn nhꢤt (đơn vꢐ).

PHƯƠNG PHÁP GIꢙI

Dꢷng phꢸp biꢏn đổi thích hꢒp

cho tꢫng HꢍM MꢎC TIÊU.

 Tính SUM như thưꢅng.

 Phương ꢊn kiꢏn nghꢐ có SUM

 Max

• F₃: Sꢇ kꢹ sư lꢉnh nghꢖ trên 15 năm (ngưꢅi).

• F₄: Tꢺ lꢠ vꢇn vay (nꢒ ngân hꢉng) trên tổng tꢉi

sꢆn (%).

8/29/2016

PGS. Dr. Nguyễn Thống

44

8/29/2016

PGS. Dr. Nguyễn Thống

43

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Keát quaû ñaùnh giaù ñöôïc toång hôïp nhö sau:

MÔ HÌNH THꢜA HIꢁP

 Mô hꢄnh thꢥa hiꢠp đơn

giꢆn (Bꢉi toꢊn Max, Min)

 Mô hꢄnh thꢥa hiꢠp phức

tạp (tổng quꢊt).

Nhaø thaàu



A1

6

4

A2

15

6

A3

10

3

A4

8

Tieân chí

1.1

1.0

0.9

1.2

F1

F2

20

25

32

35

40

15

35

F3

F4

Kieán nghò Nhaø thaàu (A_i) theo moâ hình lôïi ích chung ?

8/29/2016

PGS. Dr. Nguyễn Thống

45

8/29/2016

PGS. Dr. Nguyễn Thống

46

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH THỎA HIỆP

MÔ HÌNH THꢜA HIꢁP

ĐƠN GIꢙN

• Moâ hình thoaû hieäp “ñôn giaûn” : Tröôøng

hôïp baøi toaùn coù 2 muïc tieâu vaø caùc haøm

muïc tieâu coù cuøng daïng (max hoaëc min).

BꢍI TOÁN MAX

• Moâ hình thoaû hieäp “phöùc taïp” : Tröôøng

hôïp baøi toaùn coù nhieàu hôn 2 muïc tieâu vaø

caùc haøm muïc tieâu coù daïng max hoaëc min

baát kyø.

8/29/2016

PGS. Dr. Nguyễn Thống

47

8/29/2016

PGS. Dr. Nguyễn Thống

48

8

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Z₂

Mieàn lôøi giaûi

MOÂ HÌNH THOAÛ HIEÄP ÑÔN GIAÛN

S (lôøi giaûi lyù töôûng

khoâng khaû thi

Mꢟt Bꢉ nꢟi trꢒ đi chꢒ vꢓi sꢇ ꢻꢖn đã cꢋ.

Dꢣ kiꢏn mua thꢐt Z₁(cho Chꢡng) & mua

cꢊ Z₂(cho Con). Sꢇ lưꢒng mua cho bꢳi

đꢡ thꢐ. Xꢊc đꢐnh Z₁& Z₂“hꢒp lꢞ” bꢼng

phương phꢊp thꢥa hiꢠp.

Z_2,max

Z_2,op

“khoâng töôûng”

M

L_SM Min

M_op

Mieàn lôøi giaûi

taàm thöôøng

0

Z₁

Z_1,max

Z_1,op

MOÂ HÌNH THOAÛ HIEÄP ÑÔN GIAÛN

8/29/2016

PGS. Dr. Nguyễn Thống

49

8/29/2016

PGS. Dr. Nguyễn Thống

50

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MOÂ HÌNH THOAÛ HIEÄP ÑÔN GIAÛN



²^0.5

2

L  Z^max Z^j Z^max Z₂^j

 min

Ñieåm S coù toïa ñoä Z_1,maxvaø Z_2,maxlaø lôøi

giaûi “lyù töôûng” nhöng KHOÂNG

THÖÏC TEÁ.

 Lôøi giaûi “toái öu” seõ laø lôøi giaûi naèm

treân ñöôøng cong (Z_1,max Z_2,max) vaø

GAÀN vôùi S nhaát.



₁







1

2









(Z₁^j, Z₂^j)

với

cong.

tọa độ điểm trên đường

 Cực trị hàm trên sẽ cho cặp giá trị

(Z₁,Z₂) chính là lời giải của bài toán.

8/29/2016

PGS. Dr. Nguyễn Thống

51

8/29/2016

PGS. Dr. Nguyễn Thống

52

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Baøi taäp: Tìm lôøi giaûi baèng phöông phaùp thoaû hieäp:

Ví dụ 1: Xác định lời giải tối ưu cho ví

dụ sau:

X₂

X₁²X²₂

A

X₂

10



1

X_2max=10

15²10²

M(X₁,X₂)

X_1max=15

X₁

0

15

0

X₁

(Xem lôøi giaûi trong Solver_ thoahiep.xls Vi du 2)

(Xem Solver_Thoa Hiep Vi du 1)

8/29/2016

PGS. Dr. Nguyễn Thống

53

8/29/2016

PGS. Dr. Nguyễn Thống

54

9

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

DUØNG SOLVER TRONG EXCEL ÑEÅ GIAÛI

KEÁT QUAÛ

8/29/2016

55

57

59

8/29/2016

56

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MOÂ HÌNH THOAÛ HIEÄP ÑÔN GIAÛN

MÔ HÌNH THꢜA HIꢁP

ĐƠN GIꢙN

Moät Chuû ñaàu tö phaûi ñöa ra löïa choïn

Coâng ty thöïc hieän döï aùn. Coù 2 tieâu

chí ñöôïc ñeà ra laø soá tyû leä tieàn nôï

ngaân haøng cuûa Coâng ty treân voán töï

coù vaø thôøi gian töông ñoái maø caùc

Coâng ty ñaõ treå haïn caùc döï aùn cuûa 3

naêm gaàn nhaát.

BꢍI TOÁN Min

8/29/2016

PGS. Dr. Nguyễn Thống

8/29/2016

PGS. Dr. Nguyễn Thống

58

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Tìm lời giải tối ưu cho ví dụ sau:

Nôï (Z₂, %û)

Chương 6: Ra quyết định đa mục tiêu

LÔØI GIAÛI

Phöông aùn “toát nhaát” seõ laø phöông aùn coù

Z₁=0 vaø Z₂=0. Tuy nhieân trong thöïc teá

khoâng coù phöông aùn naøy. Do ñoù phöông

aùn toát nhaát seõ laø phöông aùn “gaàn” vôùi

100

M(Z₁,Z₂)

O(0,0) nhaát:

0,5

L 



(Z₁^min Z₁^j)² (Z₂^min Z₂^j)²



120

O

Thôøi gian treå

0,5





(0  Z₁^j)² (0  Z₂^j)²



 min

(Z₁, %)

O laø lôøi giaûi toái öu “khoâng töôûng”

8/29/2016

PGS. Dr. Nguyễn Thống

60

8/29/2016

PGS. Dr. Nguyễn Thống

10

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH THỎA HIỆP “TỔNG QUÁT”

MÔ HÌNH THꢜA HIꢁP

PHꢽC TꢭP (TꢾNG QUÁT)

• Bài toán nêu trên thực chất là ta cố gắng tìm

giá trị lớn nhất (bài toán max) và nhỏ nhất

(bài toán min) có thể cho 2 hàm mục tiêu.

Trong thực tế chúng ta có thể gặp các trường

hợp tổng quát hơn.

• Số lượng hàm mục tiêu >= 2.

• Mỗi hàm mục tiêu có thể là cực đại hoặc cực

tiểu (bài toán trên cả 2 hàm mực tiêu là cực

đại).

8/29/2016

PGS. Dr. Nguyễn Thống

61

8/29/2016

62

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Diện tích

tưới

N^lm

(MW)

Lợi nhuận Số dân Diện tích

Ví dụ: Một dự án hồ chứa thủy lợi bao gồm

các mục tiêu sau:

(10⁶$)

di dời

lòng hồ

(ha)

(ng)

(ha)

P/A

Tưới Phát

• Cực đại lợi nhuận tưới và phát điện;

• Cực tiểu số người tái định cư;

điện

1

2

3

20000

10000

25000

200

500

300

2.5

1.5

2.5

15

65

25

3000

5000

4500

410000

480000

390000

• Cực đại diện tích tưới;

• Cực tiểu vùng rừng lòng hồ bị phá bỏ.

Giả sꢃ ta có 3 phương án xem xét như sau:

8/29/2016

PGS. Dr. Nguyễn Thống

64

8/29/2016

PGS. Dr. Nguyễn Thống

63

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

• Hệ số gia trọng cho 4 mục tiêu trên là (0.3,0.3,0.2,0.2).

• Lời giải tốt nhất được xác định theo tiêu chí sau:

• Từ số liệu trên, ta có giá trị của 4 hàm mục tiêu Z cho

3 phương án xem xét A như sau:





^p^1/p

Số HMT

Z^*_i Z_i^j

Z_i^max Z_i^min

n













Phương án A^j

A¹

A²

A³

α

Min(L_j) 

_i

__

 

^i1

Mục tiêu Zⁱ





Z^*_i

Max Z¹(10⁶$)

17.5

66.5

27.5

0.3

•

 giá trị max trong hàng thứ i nếu hàm mục tiêu cục bộ

là max.

Min Z²(người)

3000

5000

4500 0.3

*

Z_i

 giá trị min trong hàng thứ i nếu hàm mục tiêu cục bộ là

min.

Max Z³(ha) tưới

20000 10000 25000 0.2

• Quy öôùc soá lieäu theo tieâu chí ñöôïc trình baøy theo haøng.

• p=2  tính khoaûng caùch trong khoâng gian Euclide.

Min Z⁴(ha) rừng 410000 480000 390000 0.2

8/29/2016

PGS. Dr. Nguyễn Thống

65

8/29/2016

66

PGS. Dr. Nguyễn Thống

11

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Bài giải (j=1  P/án 1,…):

Từ đó:

^p^{1/ p}

p



66.517.5

3000 3000

5000 3000

25000  20000

25000 10000

39000  41000

48000 39000

















• Với p=1: L₁= 0.411, L₂= 0.700, L₃=

0.464

L_j1



0.3*



0.3*



0.2*



0.2*















































^p^{1/ p}

p

0.2

2

p











L_j1



0.3



 0.2*

L₁ min  Phương án A₁là tốt nhất





















3

9











• Với p=2 (không gian Euclide): L₁=

0.310, L₂= 0.412, L₃= 0.328



^p^1/p



p

L_j2 0.3  2 0.2















^p^{1/ p}

L₁ min  Phương án A₁vẫn là tốt

nhất  kieán nghò A₁

p

39

49

3

4











L_j3



0.3

 0.3*























8/29/2016

PGS. Dr. Nguyễn Thống

67

8/29/2016

68

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Diện tích N^lm(M Lợi nhuận Số dân Diện tích

Bài tập: Một dự án hồ chứa thủy lợi bao

gồm các mục tiêu sau:

tưới

W)

(10⁶$)

di dời lòng hồ

(ha)

P/A

1

Tưới Điện

• Cực đại lợi nhuận tưới và phát điện;

• Cực tiểu số người tái định cư;

• Cực đại diện tích tưới;

15000

100

3

20

2000

380000

2

3

20000

15000

400

200

2

3

60

25

4000

4500

480000

390000

• Cực tiểu vùng rừng lòng hồ bị phá bỏ.

(caùc giaù trò _i=1)

Duøng phöông phaùp thoûa hieäp

ñeå xaùc ñònh p/a kieán nghò với p=2

8/29/2016

70

8/29/2016

PGS. Dr. Nguyễn Thống

69

PGS. Dr. Nguyễn Thống

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

TꢾNG HỢP KẾT QUꢙ ĐÁNH GIÁ

Baøi taäp: Duøng phöông phaùp thoûa hieäp (p=2) ñeå

löïa choïn nhaø thaàu thöïc hieän dö aùn, Nhaø ñaàu

tö ñöa ra 5 tieâu chí xem xeùt.

Nhꢂ thꢃu

Tiêu chꢄ

A1

A2

A3

(1)

(2)

(3)

(4)

(5)

200

8

250

6

500

5

(1) Voán löu ñoäng (tyû VNÑ).

(2) Ñaõ xaây döïng döï aùn quy moâ töông töï (./10).

(3) Kinh nghieäm ñoäi nguõ nhaân vieân (./10).

(4) Soá döï aùn ñang thöïc hieän ñoàng thôøi (ñv).

(5) Thôøi gian thi coâng döï aùn (thaùng).

Laáy _i=1

9

5

7

3

5

10

26

25

23

8/29/2016

PGS. Dr. Nguyễn Thống

72

8/29/2016

71

PGS. Dr. Nguyễn Thống

Coù 3 hoà sô ñöôïc xem xeùt vaø cho keát quaû sau:

12

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Baøi taäp: Xeùt 3 döï aùn quy hoaïch giao thoâng vôùi caùc

hieäu quaû mang laïi cho töøng tieâu chí nhö baûng sau.

Caùc haøm muïc tieâu ñaët ra laø:

Soá lieäu tính toaùn cho caùc phöông aùn nhö sau.

Troïng soá α_ilaàn löôït cho caùc muïc tieâu theo thöù

töï treân laø [1.2; 1; 1; 0.8].

1. Toång möùc ñaàu tö nhoû nhaát (tyû VNÑ).

Phöông aùn

1

2

3

2. Khaû naêng phuïc vuï giao thoâng lôùn nhaát (tr. ngöôøi).

3. Cöïc tieåu vuøng dieän tích ñeàn buø (ha).

4. Cöïc ñaïi daân cö vuøng phuïc vuï trong baùn kính 200

km, tính töø trung taâm quy hoaïch (tr. ngöôøi).

Muïc tieâu

1. Toång möùc

2000

1.2

2500

1.6

2800

2.4

2. Khaû naêng phuïc vuï

3. Giaûi toaû

100

2

130

2.5

180

Xaùc ñònh phöông aùn kieán nghò theo phöông phaùp

4. Phuïc vuï daân cö

8/29/2016

PGS. Dr. Nguyễn Thống

4

thoûa hieäp (p=2).

8/29/2016

PGS. Dr. Nguyễn Thống

74

73

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

Soá lieäu tính toaùn cho caùc phöông aùn nhö sau.

Troïng soá α_ilaàn löôït cho caùc muïc tieâu theo thöù

töï treân laø [1.2; 1; 0.9; 0.8].

Baøi taäp: Xeùt 3 döï aùn quy hoaïch khu coâng

nghieäp. Caùc haøm muïc tieâu ñaët ra laø:

1. Soá daân di dôøi nhoû nhaát (nghìn ngöôøi).

Phöông aùn

1

2

3

2. Maïng löôùi giao thoâng lieân keát caùc Tp. laø lôùn

Muïc tieâu

Soá daân di dôøi

nhaát (traêm km).

2.1

2.5

3.2

3. Khoaûng caùch ñeán caùc caûng bieån & caûng haøng

khoâng laø beù nhaát (traêm km).

Maïng löôùi g/thoâng l/keát

Khoaûng caùch ñeán ga, caûng

Dieän tích ñaát khai thaùc

7

4

8

6

10

6

4. Dieän tích coù khaû naêng xaây döïng laø lôùn nhaát

(traêm ha).

600 800 1200

Xem 3 phöông aùn sau. Xaùc ñònh phöông aùn

kieán nghò theo phöông phaùp thoûa hieäp (p=2).

8/29/2016

PGS. Dr. Nguyễn Thống

8/29/2016

PGS. Dr. Nguyễn Thống

75

76

MÔ HÌNH & PHƯƠNG PHÁP TRỢ GIÚP RA QUYẾT ĐỊNH

Chương 6: Ra quyết định đa mục tiêu

HẾT CHƯƠNG

8/29/2016

77

PGS. Dr. Nguyễn Thống

13

Bài giảng Phương pháp trợ giúp ra quyết định - Chương 6: Ra quyết định đa mục tiêu - Nguyễn Thống