Các mô hình mạng 9

Chia sẻ: Thi Sms | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

52
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'các mô hình mạng 9', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các mô hình mạng 9

Chú ý: Có th ch ng minh ñư c r ng n u hàm th a d ng u(.) là hàm l i (l i ng t) thì π ≤ 0 (< 0) v i m i cu c x s . Còn n u hàm th a d ng u(.) là hàm lõm (lõm ng t) thì π ≥ 0 (> 0) v i m i cu c x s . Quay l i ví d ñang xét, do hàm u(.) v i ñ th u1 ñã xây d ng là l i ng t nên ta luôn có π = E(x/p) – u−1(E(u/p)) < 0. ði u này cũng có nghĩa là u(E(x/p)) < E(u/p), t c là ñ th a d ng c a kì v ng l i nhu n là nh hơn kì v ng th a d ng do cu c x s mang l i. Trong trư ng h p hàm th a d ng có ñ th u3 (trên hình V.4) thì π > 0 và do ñó u(E(x/p)) > E(u/p), t c là ñ th a d ng c a kì v ng l i nhu n là l n hơn kì v ng th a d ng do cu c x s mang l i. T các phân tích trên, ta th y n u ngư i ra quy t ñ nh có hàm th a d ng u(.) l i thì ngư i ñó có tính “hư ng m o hi m” (Risk Prone), còn n u trái l i, u(.) lõm thì có tính “tránh m o hi m” (Risk Averse). V i u(.) tuy n tính, ngư i ra quy t ñ nh có tính h p lí (Risk Neutral). ði u này ñư c th hi n khá tr c quan trên hình V.4 n u ta quy l i thang b c gi i thư ng: thay vì các cu c x s “b o hi m” ñã nói t i trong ví d , chúng ta xét các cu c x s th t s v i gi i thư ng (ñư c quy l i g c t a ñ ) thu c vào kho ng 0 USD t i 150000 USD. V i ñ th u1 ta th y, các gi i thư ng khá cao ngư i ra quy t ñ nh có tính “hư ng m o hi m” v n ch có ñ th a d ng (m c ñ th a mãn) th p, ch ng h n gi i thư ng 149500 USD ch mang l i ñ th a d ng là 0,7 và ñ th a mãn tăng r t nhanh khi m c gi i thư ng tăng sát 150000 USD. ð th u3 cũng có th ñư c phân tích tương t ñ th y tính “tránh m o hi m” c a ngư i ra quy t ñ nh. Ví d 2: M t nhà ñ u tư có 10000 USD có th ñ u tư vào th trư ng ch ng khoán. Anh ta có th l a ch n hai công ti X và Y ñ ñ u tư (gi s r ng hai công ti X và Y là hoàn toàn ñ c l p v i nhau). Theo tính toán sơ b và d ñoán c a chuyên gia thì nhà ñ u tư có th nh n ñư c g p ñôi s ti n ñ u tư v i xác su t 0,6 và có th m t ñi m t n a s ti n ñ u tư v i xác su t 0,4 khi ñ u tư vào m t trong hai công ti trên. Anh ta xem xét các l a ch n sau: - ð u tư toàn b s ti n vào m t trong hai công ti (phương án A). - ð u tư 5000 USD vào công ti X (phương án B). - ð u tư 5000 USD vào công ti X và 5000 USD vào công ti Y (phương án C). - Không ñ u tư vào hai công ti trên (phương án D). Ngoài ra, gi s ñã bi t hàm tho d ng c a ngư i ñ u tư t i m t s m c l i nhu n: u(−5000) = 0; u(−2500) = 0,2; u(0) = 0,4; u(2500) = 0,7; u(5000) = 0,9; u(10000) = 1. Hãy xác ñ nh phương án ñ u tư d a trên tiêu chu n kì v ng tho d ng t i ña. Tính kì v ng tho d ng cho phương án A: E(u/pA) = 0,6×u(10000) + 0,4×u(−5000) = 0,6. Tương t , E(u/pB) = 0,6×u(5000) + 0,4×u(−2500) = 0,6×0,9 + 0,4×0,2 = 0,62 Nh m tính kì v ng tho d ng cho phương án C, chúng ta s d ng hàm sinh (0,6a1 + 0,4 b1)(0,6a2 + 0,4 b2) = 0,36 a1a2 + 0,24a1b2 + 0,24b1a2 + 0,16b1b2 ñ xác ñ nh ñư c các xác su t: xác su t ñ u tư vào c hai công ti cùng lãi là 0,36; xác su t ñ u tư vào công ti X lãi và công ti Y l là 0,24; xác su t ñ u tư vào công ti X l và công ti Y lãi là 0,24; xác su t ñ u tư vào c hai công ti cùng l là 0,16. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........180
V y E(u/pC) = 0,36×u(10000) + 0,24×u(2500) + 0,24×u(2500) + 0,16×u(−5000) = 0,36×1 + 0,24×0,7 + 0,24×0,7 + 0,16×0 = 0,696. D th y E(u/pD) = 0,4. Do ñó, d a trên tiêu chu n kì v ng th a d ng t i ña, ta ch n phương án C ñ ñ u tư. Chú ý: Ra quy t ñ nh d a trên tiêu chu n kì v ng tho d ng t i ña là m t phương pháp ra quy t ñ nh trong môi trư ng r i ro. Cái khó nh t trong phương pháp này là thi t l p ñư c hàm tho d ng. Ví d 3: M t nhà ñ u tư nghiên c u v c phi u c a m t công ti và ñánh giá r ng các c phi u s tăng giá trong th i gian t i. Hi n t i m t c phi u ñư c bán ra v i giá 50 USD. Thông qua ngư i môi gi i, nhà ñ u tư ñư c gi i thi u ñ mua m t h p ñ ng như sau: mua 4 USD/quy n mua m t c phi u v i giá 48 USD/c phi u trong vòng hai tháng n a. Nhà ñ u tư cũng ñư c ñ ngh m t h p ñ ng khác: mua 8 USD/quy n mua m t c phi u v i giá 48 USD/c phi u trong vòng b n tháng n a. Nhà ñ u tư thu th p ñư c thông tin v phân ph i xác su t c a giá c phi u và t ng h p trong b ng VI.9. B ng VI.9. B ng phân ph i xác su t giá c phi u Xác su t c a giá c phi u Giá c phi u Sau hai tháng Sau b n tháng 42 0,05 0,00 48 0,10 0,05 52 0,15 0,10 56 0,20 0,15 60 0,50 0.30 64 0,00 0,40 Nhà ñ u tư mu n xem xét vi c mua quy n mua m t s c phi u trong th i h n các h p ñ ng trên. N u giá c phi u trên th trư ng ch ng khoán là cao hơn 48 USD nhà ñ u tư s mua v i giá 48 USD/c phi u (ñã mua quy n mua) và bán ngay chúng theo giá th trư ng. Còn n u giá c phi u không vư t quá 48 USD/c phi u trong th i h n h p ñ ng thì toàn b s ti n mua quy n mua các c phi u s b th t thu. Nhà ñ u tư mu n l a ch n m t trong ba phương án sau: Phương án A: Mua quy n mua 100 c phi u trong h p ñ ng th nh t. Phương án B: Mua quy n mua 100 c phi u trong h p ñ ng th hai. Phương án C: Không mua gì c . Nhà ñ u tư là ngư i tương ñ i b o th , có tính cách “tránh m o hi m” v i hàm th a d ng ñư c xác ñ nh t i m t s m c l i nhu n như trong b ng VI.10. B ng VI.10. Giá tr hàm th a d ng L i nhu n ð tho d ng 1200 1 800 0,8 400 0,7
0 0,6 -400 0,1 -800 0 Xét phương án A, ta có E(u/pA) = 0,05×u(−400) + 0,1×u(−400) + 0,15×u(0) + 0,20×u(400) + 0,50×u(800) + 0×u(1200) = 0,645. Xét phương án B, ta có E(u/pB) = 0×u(−800) + 0,05×u(−800) + 0,1×u(−400) + 0,15×u(0) + 0,30×u(400) + 0,40×u(800) = 0,63. V i phương án C, E(u/pC) = 0,6.V y nhà ñ u tư quy t ñ nh ch n phương án A. Chú ý: Vi c d báo phân ph i xác su t c a giá các c phi u cũng là m t v n ñ khá ph c t p, n u các xác su t này chưa bi t thì có th coi là chúng b ng nhau theo nguyên lí lí l không ñ y ñ . Ngoài ra, v i s li u c a ví d trên cũng có th xem xét ñ l a ch n nhi u phương án ñ u tư khác. 5. LÍ THUY T TRÒ CHƠI VÀ NG D NG 5.1. M t s khái ni m cơ b n c a lí thuy t trò chơi m c 1, các tiêu chu n ra quy t ñ nh ñã giúp ngư i ra quy t ñ nh ñưa ra các l a ch n h p lí khi ñ i di n v i ñ i th là môi trư ng b t ñ nh, không có trí tu . Trong lí thuy t trò chơi, ta s h c cách ñưa quy t ñ nh khi ph i ñ i di n v i m t hay nhi u ñ i th có trí thông minh. Trong các trò chơi, ñư c hi u theo nghĩa r ng, các ñ i th c nh tranh nhau ñ u coi là có trí thông minh như nhau, ñ u mong mu n l a ch n cho mình t m t s h u h n ho c vô h n các phương án hành ñ ng m t phương án hành ñ ng h p lí nh m ñ t ñư c thành tích t t nh t hay l i nhu n t t nh t. Tuy nhiên, lí thuy t trò chơi, trư c h t là m t lĩnh v c toán h c, không có m c tiêu nghiên c u v vi c làm th nào ñ th ng ñư c ñ i th , mà t p trung nghiên c u kh o sát các mâu thu n ñ i kháng khách quan c a trò chơi, nh m gi i quy t ñư c v n ñ phát sinh ñ ng trên quy n l i c a t t c các bên tham gia. Các ví d ñi n hình v lí thuy t trò chơi là v các chi n lư c phát tri n s n ph m, d ch v , th trư ng trong n n kinh t hàng hóa c nh tranh khu v c và toàn c u, các chi n lư c quân s ... Sau ñây là m t s khái ni m cơ b n hay các thu t ng then ch t c a lí thuy t trò chơi: − ð i th g i là ngư i chơi. − M t phương án hành ñ ng c a m t ngư i chơi ñư c g i là m t chi n lư c. − Khi các ñ i th ñã l a ch n các chi n lư c hành ñ ng thì trò chơi cho ta m t k t c c thư ng ñ nh lư ng b ng các s ñư c g i là m t pay-off. Nh ng t h p chi n lư c khác nhau t phía các ngư i chơi có th d n t i các k t c c hay các pay-off khác nhau c a trò chơi. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........182
− M t t rò chơi v i hai ngư i chơi tham gia, mà trong ñó l i nhu n mà ngư i này thu ñ ư c chính b n g th t thu c a n gư i kia, ñ ư c g i l à t rò chơi hai ng ư i - t n g không. Ví d 1: Hai ngư i chơi A và B tham gia vào trò chơi, m i ngư i có quy n c h n m t t rong hai m t c a ñ ng xu: ch n m t có s S (chi n l ư c 1) ho c m t không có s N (chi n l ư c 2). Khi ñó có th x y ra các k t c c sau: (S, S) - t c là ngư i th nh t và ngư i th hai ñ u ch n m t có s , (S, N) - ngư i th nh t ch n m t có s và ngư i th hai ch n m t không có s , (N, S) và (N, N). Các k t c c này ñư c ñ nh lư ng b i các pay-off: N u k t c c là (S, S) ho c (N, N) thì A ñư c coi là th ng 1 ñi m và B b m t 1 ñi m. Còn n u k t c c là (S, N) ho c (N, S) thì A m t 1 ñi m và B ñ ư c 1 ñi m. ðây là trò chơi hai ngư i - t ng không, v i các d ki n ñư c t ng h p b i ma tr n c 2×2 như sau: Ngư i chơi B SN S  +1 −1 =  a ij  , Ngư i chơi A N  −1 +1   2×2   v i các pay-off mang d u + bi u th A th ng (do B thua), còn các pay-off mang d u - bi u th anh thua (do B th ng). − Ma tr n sau ñây ñư c g i là ma tr n trò chơi c a trò chơi hai ngư i - t ng không, khi ngư i chơi th nh t có th l a ch n hành ñ ng theo m t trong m chi n lư c t i m i th i ñi m, còn ngư i chơi th hai có th l a ch n hành ñ ng theo m t trong n chi n lư c t i m i th i ñi m:  a11 a12 ... a1n  a ... a 2n  a 22 G =  21  = a  ... ...   ij  m×n  ... ...   a m1 a m2 ... a mn  trong ñó aij là pay-off khi ngư i th nh t chơi chi n lư c i còn ngư i th hai chơi chi n lư c j c a mình. aij có d u + n u ngư i th nh t th ng và có d u - n u ngư i th nh t thua. Không làm gi m tính t ng quát, ta gi s trong ma tr n trò chơi G không có hai hàng hay hai c t gi ng h t nhau. − N u akj ≥ asj, ∀j = 1, 2,..., n, k ≠ s và có ít nh t m t ch s j* sao cho a kj* > a sj* thì ta nói hàng k là tr i hơn hàng s. Lúc ñó có th b hàng s ra kh i ma tr n trò chơi G, vì ngư i th nh t s không bao gi chơi chi n lư c s. Còn n u aik ≥ ais, ∀i = 1, 2,...,
n, k ≠ s và có ít nh t m t ch s i* sao cho a i*k > a i*s thì ta nói c t k là tr i hơn c t s. Lúc ñó có th b c t k ra kh i ma tr n trò chơi G, vì ngư i th hai s không bao gi chơi chi n lư c k. Ví d 2: Xét trò chơi hai ngư i - t ng không cho b i ma tr n trò chơi sau Ngư i chơi B 8 2 9 5 9 6 8 18  5 7 Ngư i chơi A  . 3 2 6 8 10    3 −4 −3 10  7 Lúc ñó, có th g ch b hàng 3 ra kh i ma tr n trò chơi, sau ñó c t 4 ra kh i ma tr n trò chơi ñ rút g n ma tr n trên. 5.2. Trò chơi hai ngư i - t ng không v i chi n lư c thu n nh t Ví d 3: Xét trò chơi hai ngư i - t ng không cho b i ma tr n trò chơi sau Ngư i chơi B 8 2 9 5  Ngư i chơi A 6 5 7 18    7 3 −4 10    Gi i thích: Trong ma tr n trò chơi trên a11 = 8, t c là n u A chơi chi n lư c 1 c a mình và B chơi chi n lư c 1 c a mình thì A th ng 8 còn B thua 8 (ñơn v ). Các pay-off khác ñư c gi i thích tương t . ñây, m = 3 và n = 4. Ta th y n u A chơi chi n lư c 1 c a mình thì B s chơi chi n lư c 2 ñ gi m thi u 4 t i ña l i nhu n c a A và th t thu c a B v i pay - off tương ng là Min {a1j} = 2. N u A j=1 4 chơi chi n lư c 2 thì v i lí do tương t B chơi chi n lư c 2 ñ có pay - off là Min {a2j} j=1 4 = 5. còn n u A chơi chi n lư c 3 thì B chơi chi n lư c 3 d n t i pay - off là Min {a3j} = j=1 -4. Do ñó ñ l i nhu n là l n nh t có th , A ph i th c hi n quy t c Maximin như sau: 3 3 4 Ch n chi n lư c k ng v i akl = Max { Min {aij}} = Max {2, 5, -4} = 5 = a22. j=1 i =1 i =1 Như v y A l a ch n chi n lư c 2. Chi n lư c này ñư c g i là chi n lư c Maximin. V phía ngư i chơi B, b ng l p lu n tương t , ñ th t thu là ít nh t có th , ph i th c hi n quy t c Minimax như sau: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........184
3 4 4 Ch n chi n lư c s ng v i aqs = Min { Max {aij}} = Min {8, 5, 9, 10} = 5 = a22. j=1 i =1 j=1 Do ñó, B l a ch n chi n lư c 2. Chi n lư c này ñư c g i là chi n lư c Minimax. ð nh lí 1: V i m i ma tr n trò chơi G = a ij  c a trò chơi hai ngư i - t ng   m×n không, b t ñ ng th c sau ñây luôn ñúng: m m n n Min { Max {aij}} ≥ Max { Min {aij}} (*) j=1 i =1 i =1 j=1 m m n n H qu 1: N u v = Min { Max {aij}} = Max { Min {aij}} = aks (**) thì ngư i chơi j=1 i =1 i =1 j=1 th nh t s quy t ñ nh chơi chi n lư c k, còn ngư i chơi th hai s quy t ñ nh chơi chi n lư c s. N u ñi u ki n (**) ñư c th a mãn thì trò chơi ñư c g i là trò chơi v i chi n lư c thu n nh t (Pure Strategy), v ñư c g i là giá tr c a trò chơi (Game Value), còn aks ñư c g i là ñi m yên ng a (Saddle Point). Có th ch ra các ví d khi ma tr n trò chơi có nhi u hơn m t ñi m yên ng a. 5.3. Trò chơi hai ngư i - t ng không v i chi n lư c h n h p Ví d 4: Xét trò chơi hai ngư i - t ng không cho b i ma tr n trò chơi sau ñây (v i m = n = 3). Ngư i chơi B  6 2 0   Ngư i chơi A  0 6 2   −1 0 6    m n dàng tính ñư c ngay: v = Min { Max {aij}} = 6, còn v = Chúng ta d i =1 j=1 m n Max { Min {aij}} = 0. Do v > v , nên trong ví d này ñi m yên ng a không t n t i và i =1 j=1 trò chơi không ph i là trò chơi v i chi n lư c thu n nh t. Gi s r ng trò chơi trong ví d này ñư c l p l i nhi u l n. Lúc ñó, n u A luôn ch chơi chi n lư c Maximin thì anh ta ch luôn thu ñư c l i nhu n là 0. Còn n u B luôn ch chơi chi n lư c Minimax thì anh ta s luôn b th t thu là 6. Như v y, ñ tăng l i nhu n trung bình trong m t l n chơi lên trên 0, A có th nghĩ t i m t chi n lư c h n h p: th c hi n m t trong b n chi n lư c c a mình m t cách xen k v i các t n su t (xác xu t th c nghi m) nh t ñ nh, lúc chi n lư c này lúc chi n lư c khác. V ph n B, ñ gi m th t thu trung bình trong m t l n chơi xu ng dư i 6, m t chi n lư c h n h p cũng c n ñư c xem xét.
ð nh nghĩa 1: Xét trò chơi hai ngư i - t ng không. T i m i th i ñi m, ngư i th nh t có th hành ñ ng theo m t trong m chi n lư c a1, a2, ..., am, còn ngư i th hai có th hành ñ ng theo m t trong n chi n lư c b1, b2, ..., bn. M t chi n lư c h n h p c a ngư i th nh t là: chơi chi n lư c a1 v i xác su t x1, chi n lư c a2 v i xác su t x2, ..., m chi n lư c am v i xác su t xm, v i ∑ x i = 1, ∀i, x i ≥ 0 . Còn m t chi n lư c h n h p i =1 c a ngư i th hai là: chơi chi n lư c b1 v i xác su t y1, chi n lư c b2 v i xác su t y2,..., n chi n lư c bn v i xác su t yn v i ∑ y j = 1, ∀j, y j ≥ 0 . j=1 Quay l i ví d nêu trên, ñ xác ñ nh ñư c chi n lư c h n h p t t nh t c a mình, ngư i chơi A c n tìm ñư c phân ph i xác su t x = (x1, x2, ..., xm) ñ c c ñ i hóa kì v ng pay − off th p nh t trong các c t, t c là c n gi i bài toán sau:   m m m Min  ∑ a i1x i , ∑ a i2 x i ,..., ∑ a in x i ,   (***) Max  i =1  x =(x1 ,...,x m )  i =1 i =1 ðây là tiêu chu n Maximin kì v ng l i nhu n c a t ng c t. ði u này có nghĩa là: N u m t phân ph i xác su t x = (x1, x2, ..., xm) ñã ñư c ch n thì ngư i chơi B luôn ch n chơi chi n lư c ng v i c t có kì v ng pay − off th p nh t ñ gi m thi u th t thu c a mình. Do ñó, ngư i chơi A b t bu c ph i ch n phân ph i xác su t x theo tiêu chu n Maximin. Còn ñ xác ñ nh ñư c chi n lư c h n h p t t nh t c a mình, ngư i chơi B c n tìm ñư c phân ph i xác su t y = (y1, y2, ..., yn) ñ c c ti u hóa kì v ng pay − off cao nh t trong các hàng, t c là c n gi i bài toán sau:      n n n Min Max  ∑ a1j y j , ∑ a 2 j y j ,..., ∑ a mj y j ,   (****) y =(y1 ,...,yn )    j=1   j=1 j=1 ðây là tiêu chu n Minimax kì v ng th t thu c a t ng hàng. ði u này có nghĩa là: N u m t phân ph i xác su t y = (y1, y2,..., yn) ñã ñư c ch n thì ngư i chơi A luôn ch n chơi chi n lư c ng v i c t có kì v ng pay - off cao nh t ñ tăng l i nhu n c a mình. Do ñó, ngư i chơi B b t bu c ph i ch n phân ph i xác su t y theo tiêu chu n Maximin. Chú ý: N u ch xét các trư ng h p véc tơ phân ph i xác su t x = (x1, x2, ..., xm) có ñúng m t t a ñ b ng 1, còn các t a ñ b ng 0 thì (***) chính là quy t c Maximin trong m c 5.2. Còn n u ch xét các trư ng h p véc tơ phân ph i xác su t y = (y1, y2,..., yn) có ñúng m t t a ñ b ng 1, còn các t a ñ b ng 0 thì (****) chính là quy t c Minimax trong m c 5.2. ð nh lí 2: V i m i phân ph i xác su t x = (x1, x2,..., xm) và m i phân ph i xác su t y = (y1, y2,..., yn) ta luôn có: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........186
       m m m n n n Min Max  ∑ a1j y j , ∑ a 2 j y j ,..., ∑ a mj y j ,   ≥ Max Min  ∑ a i1x i , ∑ a i2 x i ,..., ∑ a in x i ,   .  i =1  x =(x1 ,...,x m )  y =(y1 ,...,y n )    j=1   i =1 i =1 j=1 j=1 Ngoài ra, d u b ng trong b t ñ ng th c trên x y ra n u x* = (x1 , x ∗ ,..., x ∗ ) và ∗ 2 m y* = (y1 , y∗ ,..., y∗ ) là các phân ph i xác su t t i ưu c a hai bài toán (***) và (****). ∗ 2 n H qu 2: N u x* = (x1 , x ∗ ,..., x ∗ ) và y* = (y1 , y∗ ,..., y∗ ) là các phân ph i xác su t ∗ ∗ 2 m 2 n t i ưu c a hai bài toán (***) và (****) thì:      n n n v* = Min Max  ∑ a1j y j , ∑ a 2 j y j ,..., ∑ a mj y j ,   y =(y1 ,...,y n )    j=1   j=1 j=1 mn   m m m ∑ ∑ a ijx∗ y∗ . = Max  Min  ∑ a i1x i , ∑ a i2 x i ,..., ∑ a in x i ,   = ij  i=1  x =(x1 ,...,x m )  i=1 j=1 i =1 i =1 Giá tr v* trên ñây ñư c g i là giá tr c a trò chơi hai ngư i - t ng không v i chi n lư c h n h p (Mixed Strategies). ð xác ñ nh chi n lư c h n h p t i ưu x* = (x1 , x ∗ ,..., x∗ ) , chúng ta c n l n lư t ∗ 2 m xét các bài toán sau:   m m m Min  ∑ a i1x i , ∑ a i2 x i ,..., ∑ a in x i ,   Bài toán 1a: Max  i=1  x =(x1 ,...,x m )  i =1 i=1 m ∑ x i = 1, ∀i, x i ≥ 0 . vi i =1 ðưa bài toán 1a v bài toán sau: m m Bài toán 1b: Max z = v, v i các ràng bu c ∑ a ij x i ≥ v ,∀ j; ∑ x i = 1, ∀i, x i ≥ 0 . i =1 i =1 Không làm gi m tính t ng quát, gi s v > 0 (n u trái l i, có th c ng vào t t c các ph n t c a ma tr n trò chơi m t s dương thích h p). Th c hi n phép ñ i bi n Xi = m m xi/v, ∀ i = 1, 2, ..., m, v i chú ý r ng do ∑ x i = 1 nên 1/v = u = ∑ X i . V y cu i cùng i =1 i =1 chúng ta có bài toán sau: m m Bài toán 1c: Min u = ∑ X i , v i các ràng bu c ∑ a ijXi ≥ 1 , ∀ j; ∀i, X i ≥ 0 . i =1 i =1 Bài toán 1c là BTQHTT có th gi i ñư c v i ph n m m thích h p s n có. ð xác ñ nh chi n lư c h n h p t i ưu y* = (y1 , y∗ ,..., y∗ ) chúng ta c n xem xét l n ∗ 2 n lư t các bài toán sau:
  n n n Bài toán 2a: Max  ∑ a1j y j , ∑ a 2 j y j ,..., ∑ a mj y j ,   Min  j=1  y =(y1 ,...,y n )  j=1 j=1 n ∑ y j = 1, ∀j, y j ≥ 0 . vi j=1 ðưa bài toán 2a v bài toán sau: n n Bài toán 2b: Min z = w, v i các ràng bu c ∑ a ij y j ≤ w ,∀ i; ∑ y j = 1, ∀j, y j ≥ 0 . j=1 j=1 Không làm gi m tính t ng quát, gi s w > 0 (n u trái l i, có th c ng vào t t c các ph n t c a ma tr n trò chơi m t s dương thích h p). Th c hi n phép ñ i bi n Yj = n n yj/w, ∀ j = 1, 2,..., n, v i chú ý r ng do ∑ y j = 1 nên 1/w = u’ = ∑ Yj . V y cu i cùng j=1 j=1 chúng a có bài toán sau: n n Bài toán 2c: Max u’ = ∑ Yj , v i các ràng bu c ∑ a ijYj ≤ 1 , ∀ i; ∀j, Yj ≥ 0 . j=1 j=1 Bài toán 2c cũng là BTQHTT nên có th gi i ñư c v i ph n m m thích h p s n có. Ta th y bài toán 2c và bài toán 1c t o thành c p bài toán ñ i ng u, nên theo các ñ nh lí ñ i ng u ta s có Max u’ ≤ Min u, d u b ng x y ra t i các c p phương án t i ưu tương ng. D a trên nh n xét này có th ch ng minh ñư c ñ nh lí ñã nêu trên ñây. Quay l i ví d ñã xét, v i trò chơi hai ngư i - t ng không cho b i ma tr n trò chơi sau Ngư i chơi B  6 2 0 Ngư i chơi A  0 6 2     −1 0 6    Trư c h t, ñ cho v > 0 cũng như w > 0 chúng ta c ng t t c các pay − off v i 2, ñ ñư c ma tr n trò chơi sau ñây: 8 4 2  2 8 4   1 2 8    ð gi i trò chơi, c n thi t l p các bài toán tương ng (v i các bài toán 1c và 2c): Bài toán 1: Min u = X1 + X2 + X3, v i các ràng bu c Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........188
8X1 + 2X 2 + X3 ≥ 1 4X + 8X + 2X ≥ 1 1 2 3  2X1 + 4X 2 + 8X 3 ≥ 1 X1 , X 2 , X3 ≥ 0  Bài toán 2: Max u’= Y1 + Y2 + Y3, v i các ràng bu c  8Y1 + 4Y2 + 2Y3 ≤ 1  2Y + 8Y + 4Y ≤ 1 1 2 3   Y1 + 2Y2 + 8Y3 ≤ 1  Y1 , Y2 , Y3 ≥ 0  K t qu gi i các bài toán này b ng ph n m m Lingo như sau: Objective value u: 0.2295918 Variable Value Reduced Cost X1 0.1020408 0.0000000E+00 X2 0.5612245E–01 0.0000000E+00 X3 0.7142857E–01 0.0000000E+00 Objective value u’: 0.2295918 Variable Value Reduced Cost Y1 0.7142857E–01 0.0000000E+00 Y2 0.5612245E–01 0.0000000E+00 Y3 0.1020408 0.0000000E+00 V y giá tr c a trò chơi trên là v* = 1/ u Min − 2 =1/ u ′ Max − 2 = 2.355556252 = 106/45. Chi n lư c h n h p c a ngư i chơi th nh t ñư c tìm theo công th c: 3 x ∗ = X* / ∑ X∗ v i i =1, 2, 3. T ñó có: x1 = 0.44444441 = 20/45, x ∗ = 0.24444447 = ∗ 2 i i i i =1 x∗ = 11/45, 0.31111113 = 14/45. Chi n lư c h n h p c a ngư i chơi th hai ñư c tìm 3 3 theo công th c: y∗ = Yj∗ / ∑ Yj∗ v i i =1, 2, 3. T ñó có: y1 = 0.31111113 = 14/45, y∗ = ∗ j 2 j=1 y∗ = 0.24444447 = 11/45, 0.44444441 = 20/45. 3 5.4. L i gi i b ng ñ th cho các trò chơi c 2×N ho c M×2 Ví d 5: Xét trò chơi hai ngư i - t ng không v i ma tr n trò chơi c 2×4 sau
 2 2 3 −1 4 3 2 6    Do c t 1 là tr i hơn c t 2 nên ma tr n trên ñư c rút g n v d ng  2 3 −1 3 2 6    Kí hi u véc tơ phân ph i xác su t ng v i chi n lư c h n h p c a ngư i chơi A là x = (x1, x2) = (x1, 1 − x1), chúng ta có các kì v ng pay − off c a ngư i chơi A khi ngư i chơi B chơi các chi n lư c (thu n nh t) khác nhau như sau: − N u B chơi chi n lư c 1 (b1) thì kì v ng pay − off c a A là E(X/b1) = 2x1 + 3(1−x1) = −x1 + 3. − N u B chơi chi n lư c 2 (b2) thì kì v ng pay − off c a A là E(X/b2) = x1 + 2. − N u B chơi chi n lư c 3 (b3) thì kì v ng pay − off c a A là E(X/b3) = −7x1 + 6. V ñ th c a các kì v ng pay − off trên (hình VI.5) ta th y ñư ng vi n ñ m nét phía dư i cho bi t Min {E(X/b1), E(X/b2), E(X/b3)} tùy theo x1 ñã ch n. Như v y ph i ∗ ch n x1 ng v i Max {Min {E(X/b1), E(X/b2), E(X/b3)}. V y x1 = 0,5 như ñã ch ra trên ñ th . Do ñó x ∗ = 1 − x1 = 0,5 và giá tr c a trò chơi trên là 5/2. ∗ 2 E 6 §iÓm Maximin E(X/b3) E(X/b2) 3 E(X/b1) • 5/2 2 x 1 0 0.5 Hình VI.5. ð th các kì v ng pay − off E(X/bi) Ð xác ñ nh chi n lư c h n h p (y1, y2, y3) cho ngư i chơi B, ta nh n th y các ba ñư ng kì v ng pay − off ñ u ñi qua ñi m cao nh t (1/2, 5/2) c a ñư ng vi n ñ m nét. Ði u này có nghĩa là B có th xây d ng chi n lư c h n h p d a trên c b1, b2 l n b3. Có ng kì v ng pay − off b t kì v i các h s góc trái d u ñ u th ch ng minh ñư c, hai ñư cho m t chi n lư c h n h p t i ưu c a B. Như v y, ch c n xét hai trư ng h p sau: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........190