Bài giảng Tối ưu: Chương 1 - ThS. Trần Thị Thùy Nương

Chia sẻ: Bfvhgfff Bfvhgfff | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

169
lượt xem 23
download

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

Bài giảng Tối ưu: Chương 1 Lý thuyết trò chơi nhằm trình bày về các nội dung chính giới thiệu bài toán tổng quát, trò chơi 2 người tổng không, chiến lược thuần túy, chiến lược hỗn hợp, lý thuyết trò chơi dưới dạng quy hoạch tuyến tính.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Tối ưu: Chương 1 - ThS. Trần Thị Thùy Nương

Chương 1 LÝ THUYẾT TRÒ CHƠI 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 1
NỘI DUNG 1. Giới thiệu bài toán tổng quát 2. Trò chơi 2 người tổng không 3. Chiến lược thuần túy, chiến lược hỗn hợp 4. Lý thuyết trò chơi dưới dạng QHTT 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 2
GIỚI THIỆU BÀI TOÁN TỔNG QUÁT 1. Giới thiệu −Trò chơi thường có ít hai người chơi và dựa vào một quy luật đã được đưa ra trước khi bắt đầu trò chơi. Cuối trò chơi, mỗi người chơi sẽ nhận được một thu hoạch (payoff) nào đó, tùy theo thỏa thuận giữa những người chơi, ví dụ là tiền hay hình thức phạt nào đấy. −Trò chơi có thể mang tính ngẫu nhiên (ném xúc xắc, chia bài…); trò chơi dùng kỹ thuật, kỹ năng (cờ tướng, cờ ca rô…) 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 3
GIỚI THIỆU BÀI TOÁN TỔNG QUÁT −Trong trò chơi, người ta thường xét đến 3 yếu tố: chiến lược, quy luật của trò chơi và thu hoạch. −Lý thuyết trò chơi nghiên cứu các tình huống chiến lược trong đó các đối thủ (người chơi) lựa chọn các hành động khác nhau để cố gắng làm tối đa các kết quả nhận được. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 4
GIỚI THIỆU BÀI TOÁN TỔNG QUÁT − Lý thuyết trò chơi được ứng dụng trong nhiều lĩnh vực: • Kinh tế và kinh doanh: đấu giá, mặc cả… • Sinh học: phần lợi của trò chơi là sự thích nghi, ứng dụng vào việc giải thích sự tiến hóa (và bền vững) của tỉ lệ giới tính gần 1 : 1. • Khoa học máy tính và logic • Chính trị học • Triết học 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 5
TRÒ CHƠI 2 NGƯỜI TỔNG 0 - Giả sử pi là thu hoạch của người chơi Pi , i = 1,..., k trong đó có k người tham gia. k Khi đó, nếu ∑p i =1 i = 0 thì trò chơi này được gọi là trò chơi k người tổng 0. - Trường hợp k = 2, ta có trò chơi 2 người tổng 0. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 6
TRÒ CHƠI 2 NGƯỜI TỔNG 0 Dạng ma trận - Người chơi thứ nhất (P1) có m chiến lược, được biểu diễn là các hàng của ma trận. - Người chơi thứ hai (P2) có n chiến lược, được biểu diễn là các cột của ma trận. - Ta biểu diễn ma trận A = (aij) cấp m × n là thu hoạch của P1. Và của P2 là –A. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 7
TRÒ CHƠI 2 NGƯỜI TỔNG 0  a11 ⋯ a1 j ⋯ a1n     ⋮  A = (aij ) =  ai 1 ⋯ aij ain     ⋮  a amj  amn   m1 P1 chọn chiến lược i , P2 chọn chiến lược j và người này không biết sự lựa chọn của người kia. Khi đó, P1 sẽ nhận aij (P2 trả aij ). 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 8
TRÒ CHƠI 2 NGƯỜI TỔNG 0 • Nếu ma trận A = (aij ) thỏa mãn min max aij = max min aij = ars j i i j thì ma trận này được nói là có điểm yên ngựa tại (r,s). • Khi đó, r được gọi là chiến lược tối ưu của P1 , s được gọi là chiến lược tối ưu của P2. • ars được gọi là giá trị của trò chơi, kí hiệu là v. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 9
CHIẾN LƯỢC HỖN HỢP m • x = { x1,..., xm } với xi ≥ 0, i = 1,..., m, ∑ xi = 1 được gọi i =1 là chiến lược hỗn hợp. Với xi là xác suất mà người chơi chọn chiến lược thứ i. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 10
CHIẾN LƯỢC THUẦN TÚY Chiến lược hỗn hợp x = ξ i trong đó ξ i = 1, những thành phần còn lại bằng 0 được gọi là một chiến lược thuần túy. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 11
HÀM THU HOẠCH Gọi X = { x } tập chiến lược của P1, Y = { y } tập chiến lược của P2 . Khi đó, nếu P1 chọn chiến lược hỗn hợp x, P2 chọn chiến lược hỗn hợp y, thì hàm thu hoạch là: m n A( x, y ) = ∑∑ xi aij y j = xAT y i =1 j =1 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 12
ĐỊNH LÝ MINIMAX Đặt VI := max min A( x, y ) là giá trị thu được của P1, x∈ X y ∈Y VII := minmax A( x, y ) là giá trị thu được của P2. y ∈Y x∈ X Ta có: VI = max min xi aij ; VII = minmax y i aij x∈ X j y ∈Y i Định lý Minimax VI = VII . 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 13
TÍNH TRỘI • Trong ma trận A, ta nói hàng i trội hàng k nếu aij ≥ akj , ∀j    ∃j : aij > aik  • Trong ma trận A, ta nói cột j trội cột l nếu aij ≤ ail , ∀i   ∃i : aij < ail .  → Áp dụng tính trội để rút ngắn cỡ của ma trận A. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 14
CÁCH GIẢI TRÒ CHƠI 2 x 2 Xét ma trận thu hoạch (không có điểm yên ngựa) a b  A=  c d  Đặt r = a + d − b − c Giá trị của trò chơi: ad − bc v= r Các chiến lược tối ưu: d −c a−b d −b a−c  X = , ; Y =  r , r .  r r    10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 15
CÁCH GIẢI TRÒ CHƠI 2 x n Ma trận thu hoạch có 2 hàng, n cột. - Vẽ các đường thẳng z j := a1 j x1 + a2 j x2 ( x1 + x2 = 1) hay z j = a2 j + (a1 j − a2 j )x1 , 0 ≤ x1 ≤ 1. - Chọn min z j là đường (gấp khúc) nằm dưới cùng j trong hình vẽ. Sau đó, lấy max min z j tức là điểm x j 1 (đoạn) cao nhất trên đường (gấp khúc) này. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 16
CÁCH GIẢI TRÒ CHƠI 2 x n (tt) - Giao điểm cho ta nghiệm của bài toán. Cụ thể, xác định được x1 , v và x2 . - Để tìm chiến lược tối ưu cho Y = ( y1, y 2 ,..., y n ), ta xem điểm cao nhất nhận được là giao của 2 đường zj nào, chẳng hạn đó là đường j’ và j’’ , thì ta sẽ có ma trận cấp 2 x 2 là hai cột tương ứng j’ và j’’ của ma trận A. Giải trò chơi với ma trận này, ta sẽ nhận được y j ' , y .j '' - Vậy, ngoại trừ hai giá trị y j ' , y j '' vừa tính được, các thành phần còn lại của Y sẽ có giá trị là 0. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 17
TRÒ CHƠI m x 2 - Ma trận thu hoạch có m hàng, 2 cột. → Cách giải tương tự trò chơi 2 x n. - Đối với trò chơi m x n, ta sẽ dùng tính trội để đưa về các dạng trò chơi 2 x 2; 2 x n hay m x 2 để giải. 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 18
DẠNG QUY HOẠCH TUYẾN TÍNH Bài toán đối với P1 , m max min ∑ xi aij x∈ X 1≤ j ≤ n i =1  x1 + x2 + ... + xm = 1   xi ≥ 0, i = 1,..., m Vì hàm mục tiêu chưa phải hàm tuyến tính, nên ta thêm một biến mới p : p ≤ min xi aij 1≤ j ≤ n 10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 19
DẠNG QUY HOẠCH TUYẾN TÍNH Bài toán trở thành: Tìm p, xi sao cho max p  m  p ≤ ∑ xi ai 1  i =1 ⋮   m  p ≤ ∑ xi ain (1)  i =1  x1 + x2 + ... + xm = 1   xi ≥ 0, i = 1,..., m   10/6/2012 MaMH: C02012 Chương 1: Lý thuyết trò chơi 20