1. Home
  2. Quy hoạch tuyến tính
  3. Quy hoạch tuyến tính
  4. Ứng dụng quy hoạch tuyến tính

0.3 Ứng dụng quy hoạch tuyến tính  (Page 3/9)

<< Chapter < Page
  Quy hoạch tuyến tính     Page 3 / 9
Chapter >> Page >

Như vậy ta đã xoay đúng một vòng, và nếu cứ lập luận như vậy thì ta sẽ xoay vòng mãi. Những bộ chiến lược nhận được trong khi xoay vòng là những nghiệm không ổ định.

Chiến lược hỗn hợp

Để có được lời giải của trò chơi không có nghiệm ổn định người ta đưa ra khái niệm chiến lược hỗn hợp. Mỗi người chơi không chọn một chiến lược thuần túy như trước đây mà chọn một phân bố xác suất sử dụng tất cả các chiến lược.

Xét trò chơi giữa A và B có ma trận điểm dương có dạng tổng quát :

1 2 ... n  B
A 
1 a 11 size 12{a rSub { size 8{"11"} } } {} a 12 size 12{a rSub { size 8{"12"} } } {} ... a 1n size 12{a rSub { size 8{1n} } } {}
2 a 21 size 12{a rSub { size 8{"21"} } } {} a 22 size 12{a rSub { size 8{"22"} } } {} ... a 2n size 12{a rSub { size 8{2n} } } {}
... ... ... ... ...
m a m1 size 12{a rSub { size 8{m1} } } {} a m2 size 12{a rSub { size 8{m2} } } {} ... a mn size 12{a rSub { size 8{ ital "mn"} } } {}

Giả sử rằng :

MaxiMin ( A ) = a i A j A = g A size 12{"MaxiMin " \( A \) =a rSub { size 8{i rSub { size 6{A} } j rSub { size 6{A} } } } =g rSub {A} } {}

M iniMax ( B ) = a i B j B = g B size 12{M"iniMax " \( B \) =a rSub { size 8{i rSub { size 6{B} } j rSub { size 6{B} } } } =g rSub {B} } {}

a i A j A ≠ a i B j B size 12{a rSub { size 8{i rSub { size 6{A} } j rSub { size 6{A} } } }<>a rSub {i rSub { size 6{B} } j rSub { size 6{B} } } } {}

Gọi :

. pi>0 (i=1 m ) là tần suất nước đi thứ i của A với

p1 + p2 + ... + pm = 1

. qj>0 (j=1 n ) là tần suất nước đi thứ j của B với

q1 + q2 + ... + qn = 1

q1 q2 ... qn
1 2 ... n  B
A 
p1 1 a 11 size 12{a rSub { size 8{"11"} } } {} a 12 size 12{a rSub { size 8{"12"} } } {} ... a 1n size 12{a rSub { size 8{1n} } } {}
p2 2 a 21 size 12{a rSub { size 8{"21"} } } {} a 22 size 12{a rSub { size 8{"22"} } } {} ... a 2n size 12{a rSub { size 8{2n} } } {}
... ... ... ... ... ...
pm m a m1 size 12{a rSub { size 8{m1} } } {} a m2 size 12{a rSub { size 8{m2} } } {} ... a mn size 12{a rSub { size 8{ ital "mn"} } } {}

Vấn đề đặt ra là :

-Tìm tần suất pi>0 của nước đi thứ i (i =1 m) của A sao cho đối với mỗi nước đi thứ j của B số điểm thắng trung bình của A không nhỏ thua gA :

p1a1j + p2a2j + ..... + pmamj(j = 1 n)

Cũng có nghĩa là tìm pi sao cho :

p1a1j + p2a2j + ..... + pmamj  g1  gA (j = 1 n)

g1  max

- Tìm tần suất qj>0 của nước đi thứ j (j =1 n) của B sao cho đối với mỗi nước đi thứ i của A số điểm thua trung bình của B không lớn hơn gB :

q1ai1 + q2ai2 + .... + qnain (i = 1 m)

Cũng có nghĩa là tìm các qj sao cho :

q1ai1 + q2ai2 + ..... + qnain  g2  gB (i = 1 m)

g2­  min

Khi đó hai bài toán quy hoạch tuyến tính thu được là :

max g 1 min 1 g 1 p 1 + p 2 + . . . + p m = 1 p 1 a 1j + p 2 a 2j + . . . + p m a mj ≥ g 1 ( j = 1 → n ) p i > 0 ( i = 1 → n ) { { { size 12{alignl { stack { left lbrace "max"" "g rSub { size 8{1} } " " left ("min " { {1} over {g rSub { size 8{1} } } } right ) {} #right none left lbrace p rSub { size 8{1} } +p rSub { size 8{2} } + "." "." "." +p rSub { size 8{m} } =1 {} # right none left lbrace p rSub { size 8{1} } a rSub { size 8{1j} } +p rSub { size 8{2} } a rSub { size 8{2j} } + "." "." "." +p rSub { size 8{m} } a rSub { size 8{ ital "mj"} }>= g rSub { size 8{1} } " " \( j=1 rightarrow n \) {} # right none left lbrace p rSub { size 8{i} }>0" " \( i=1 rightarrow n \) {} # right no } } lbrace } {}

min g 2 max 1 g 2 q 1 + q 2 + . . . + q n = 1 q 1 a i1 + q 2 a i2 + . . . + q n a in ≤ g 2 ( i = 1 → m ) q j > 0 ( j = 1 → m ) { { { size 12{alignl { stack { left lbrace "min"" "g rSub { size 8{2} } " " left ("max " { {1} over {g rSub { size 8{2} } } } right ) {} #right none left lbrace q rSub { size 8{1} } +q rSub { size 8{2} } + "." "." "." +q rSub { size 8{n} } =1 {} # right none left lbrace q rSub { size 8{1} } a rSub { size 8{i1} } +q rSub { size 8{2} } a rSub { size 8{i2} } + "." "." "." +q rSub { size 8{n} } a rSub { size 8{ ital "in"} }<= g rSub { size 8{2} } " " \( i=1 rightarrow m \) {} # right none left lbrace q rSub { size 8{j} }>0" " \( j=1 rightarrow m \) {} # right no } } lbrace } {}

Chia các ràng buộc của bài toán thứ nhất cho g1>0 và đặt :

x i = p i g 1 ( i = 1 → m ) size 12{x rSub { size 8{i} } = { {p rSub { size 8{i} } } over {g rSub { size 8{1} } } } " " \( i=1 rightarrow m \) } {}

Chia các ràng buộc của bài toán thứ hai cho g2>0 và đặt :

y j = q j g 2 ( j = 1 → n ) size 12{y rSub { size 8{j} } = { {q rSub { size 8{j} } } over {g rSub { size 8{2} } } } " " \( j=1 rightarrow n \) } {}

Khi đó hai bài toán quy hoạch tuyến tính trên trở thành :

(D) min 1 g 1 = x 1 + x 2 + . . . + x m a 1j x 1 + a 2j x 2 + . . . + a mj x m ≥ 1 ( j = 1 → n ) x i > 0 ( i = 1 → m ) { { size 12{alignl { stack { left lbrace "min"" " { {1} over {g rSub { size 8{1} } } } =x rSub { size 8{1} } +x rSub { size 8{2} } + "." "." "." +x rSub { size 8{m} } {} #right none left lbrace a rSub { size 8{1j} } x rSub { size 8{1} } +a rSub { size 8{2j} } x rSub { size 8{2} } + "." "." "." +a rSub { size 8{ ital "mj"} } x rSub { size 8{m} }>= 1" " \( j=1 rightarrow n \) {} # right none left lbrace x rSub { size 8{i} }>0" " \( i=1 rightarrow m \) {} # right no } } lbrace } {}

(P) max 1 g 2 = y 1 + y 2 + . . . + y 3 a i1 y 1 + a i2 y 2 + . . . + a in y n ≤ 1 ( i = 1 → m ) y j > 0 ( j = 1 → m ) { { size 12{alignl { stack { left lbrace "max"" " { {1} over {g rSub { size 8{2} } } } =y rSub { size 8{1} } +y rSub { size 8{2} } + "." "." "." +y rSub { size 8{3} } {} #right none left lbrace a rSub { size 8{i1} } y rSub { size 8{1} } +a rSub { size 8{i2} } y rSub { size 8{2} } + "." "." "." +a rSub { size 8{ ital "in"} } y rSub { size 8{n} }<= "1 " \( i=1 rightarrow m \) {} # right none left lbrace y rSub { size 8{j} }>0" " \( j=1 rightarrow m \) {} # right no } } lbrace } {}

Ðây là hai bài toán đối ngẫu . Chọn một trong hai để giải

Ví dụ :

Xét trò chơi giữa A và B có bảng điểm như sau :

1 2 3  B
A 
1 -1 2 1
2 1 -2 2
3 3 4 -3

Theo chiến thuật của A và của B ta có :

MaxiMin(A) = a11

MiniMax(B) = a23

Tăng đồng loạt các ô của bảng điểm lên 4 ta được :

1 2 3  B
A 
1 3 6 5
2 5 2 6
3 7 8 1

Gọi

pi  0 là tần suất nước đi thứ i của A (i=1 3)

p1 + p2 + p3 = 1

qj  0 là tần suất nước đi thứ j của B (j=1 3)

q1 + q2 + q3 =1

Thực hiện tương tự như trên ta được hai bài toán đối ngẫu như sau :

q1 q2 q3  B
A 
p1 3 6 5
p2 5 2 6
p3 7 8 1

(D) min w = 1 g 1 = x 1 + x 2 + x 3 3x 1 + 5x 2 + 7x 3 ≥ 1 6x 1 + 2x 2 + 8x 3 ≥ 1 5x 1 + 6x 2 + x 3 ≥ 1 x 1 > 0 , x 2 > 0 , x 3 > 0 { { { { size 12{alignl { stack { left lbrace "min"" w"= { {1} over {g rSub { size 8{1} } } } =x rSub { size 8{1} } +x rSub { size 8{2} } +x rSub { size 8{3} } {} #right none left lbrace 3x rSub { size 8{1} } +5x rSub { size 8{2} } +7x rSub { size 8{3} }>= 1 {} # right none left lbrace 6x rSub { size 8{1} } +2x rSub { size 8{2} } +8x rSub { size 8{3} }>= 1 {} # right none left lbrace 5x rSub { size 8{1} } +6x rSub { size 8{2} } +x rSub { size 8{3} }>= 1 {} # right none left lbrace " x" rSub { size 8{1} }>0" "," x" rSub { size 8{2} }>0" "," x" rSub { size 8{3} }>0 {} # right no } } lbrace } {} (P) max z = 1 g 2 = y 1 + y 2 + y 3 3y 1 + 6y 2 + 5y 3 ≤ 1 5y 1 + 2y 2 + 6y 3 ≤ 1 7y 1 + 8y 2 + y 3 ≤ 1 y 1 > 0 , y 2 > 0 , y 3 > 0 { { { { size 12{alignl { stack { left lbrace "max"z= { {1} over {g rSub { size 8{2} } } } =y rSub { size 8{1} } +y rSub { size 8{2} } +y rSub { size 8{3} } {} #right none left lbrace 3y rSub { size 8{1} } +6y rSub { size 8{2} } +5y rSub { size 8{3} }<= 1" " {} # right none left lbrace 5y rSub { size 8{1} } +2y rSub { size 8{2} } +6y rSub { size 8{3} }<= 1" " {} # right none left lbrace 7y rSub { size 8{1} } +8y rSub { size 8{2} } +y rSub { size 8{3} }<= 1" " {} # right none left lbrace y rSub { size 8{1} }>0" "," y" rSub { size 8{2} }>0" "," y" rSub { size 8{3} }>0 {} # right no } } lbrace } {}

Ta chọn bài toán (P) để giải.

Ðưa bài toán (P) về dạng chuẩn :

(P) max z = 1 g 2 = y 1 + y 2 + y 3 + 0 . y 4 + 0 . y 5 + 0 . y 6 3y 1 + 6y 2 + 5y 3 + y 4 = 1 5y 1 + 2y 2 + 6y 3 + y 5 = 1 7y 1 + 8y 2 + y 3 + y 6 = 1 y 1 > 0 , y 2 > 0 , y 3 > 0, y 4 > 0 , y 5 > 0 , y 6 > 0 { { { { size 12{alignl { stack { left lbrace "max z"= { {1} over {g rSub { size 8{2} } } } =y rSub { size 8{1} } +y rSub { size 8{2} } +y rSub { size 8{3} } +0 "." y rSub { size 8{4} } +0 "." y rSub { size 8{5} } +0 "." y rSub { size 8{6} } {} #right none left lbrace "3y" rSub { size 8{1} } +"6y" rSub { size 8{2} } +"5y" rSub { size 8{3} } +y rSub { size 8{4} } ="1 " {} # right none left lbrace "5y" rSub { size 8{1} } +"2y" rSub { size 8{2} } +"6y" rSub { size 8{3} } +y rSub { size 8{5} } ="1 " {} #right none left lbrace "7y" rSub { size 8{1} } +"8y" rSub { size 8{2} } +y rSub { size 8{3} } +y rSub { size 8{6} } ="1 " {} # right none left lbrace y rSub { size 8{1} }>"0 , y" rSub { size 8{2} }>"0 , y" rSub { size 8{3} }>"0, y" rSub { size 8{4} }>"0 , y" rSub { size 8{5} }>"0 , y" rSub { size 8{6} }>0 {} # right no } } lbrace } {}

Dùng giải thuật đơn hình cải tiến :

c B 0 size 12{c rSub { size 8{B rSub { size 6{0} } } } } {} i B 0 size 12{i rSub { size 8{B rSub { size 6{0} } } } } {} y 1 size 12{y rSub { size 8{1} } } {} y 2 size 12{y rSub { size 8{2} } } {} y 3 size 12{y rSub { size 8{3} } } {} y 4 size 12{y rSub { size 8{4} } } {} y 5 size 12{y rSub { size 8{5} } } {} y 6 size 12{y rSub { size 8{6} } } {} b ¯ 0 size 12{ {overline {b}} rSub { size 8{0} } } {}
0 4 3 6 5 1 0 0 1
0 5 5 2 6 0 1 0 1
0 6 7 8 1 0 0 1 1
c T size 12{c rSup { size 8{T} } } {} 1 1 1 0 0 0 z 0 size 12{z rSub { size 8{0} } } {}
c ¯ 0 T size 12{ {overline {c}} rSub { size 8{0} } rSup { size 8{T} } } {} 1 1 1 0 0 0 0
c B 1 size 12{c rSub { size 8{B rSub { size 6{1} } } } } {} i B 1 size 12{i rSub { size 8{B rSub { size 6{1} } } } } {} y 1 size 12{y rSub { size 8{1} } } {} y 2 size 12{y rSub { size 8{2} } } {} y 3 size 12{y rSub { size 8{3} } } {} y 4 size 12{y rSub { size 8{4} } } {} y 5 size 12{y rSub { size 8{5} } } {} y 6 size 12{y rSub { size 8{6} } } {} b ¯ 1 size 12{ {overline {b}} rSub { size 8{1} } } {}
0 4 0 18 7 size 12{ { {"18"} over {7} } } {} 32 7 size 12{ { {"32"} over {7} } } {} 1 0 − 3 7 size 12{ - { {3} over {7} } } {} 4 7 size 12{ { {4} over {7} } } {}
0 5 0 − 26 7 size 12{ - { {"26"} over {7} } } {} 37 7 size 12{ { {"37"} over {7} } } {} 0 1 − 5 7 size 12{ - { {5} over {7} } } {} 2 7 size 12{ { {2} over {7} } } {}
1 1 1 8 7 size 12{ { {8} over {7} } } {} 1 7 size 12{ { {1} over {7} } } {} 0 0 1 7 size 12{ { {1} over {7} } } {} 1 7 size 12{ { {1} over {7} } } {}
c T size 12{c rSup { size 8{T} } } {} 1 1 1 0 0 0 z 1 size 12{z rSub { size 8{1} } } {}
c ¯ 1 T size 12{ {overline {c}} rSub { size 8{1} } rSup { size 8{T} } } {} 0 − 1 7 size 12{ - { {1} over {7} } } {} 6 7 size 12{ { {6} over {7} } } {} 0 0 − 1 7 size 12{ - { {1} over {7} } } {} 1 7 size 12{ { {1} over {7} } } {}
<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Quy hoạch tuyến tính. OpenStax CNX. Aug 08, 2009 Download for free at http://cnx.org/content/col10903/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Quy hoạch tuyến tính' conversation and receive update notifications?

Ask