CÁCH LẬP BÀI TOÁN ĐỐI NGẪU – Quy hoạch tuyến tính lớp hp: 211301201 gvhd: Nguyễn Ngọc Chương tp. Hcm 02/2016

1. CÁCH LẬP BÀI TOÁN ĐỐI NGẪU

1.1. Xét quy hoạch tuyến tính dạng chuẩn tắc:

f(x) = c1x1 + c2x2 + … + cnxn min

( P. ) [ Bài toán gốc ]
Trong đó aij, bi, cj là các thông số cho trước ; x = ( x1, x2, …, xn )  Rn l vecto biến cần tìm .
Ta gọi đối ngẫu của ( P. ) là QHTT, ký hiệu ( Q. ), có dạng :
g(y) = b1y1+b2y2+ … + bmym max

( Q. ) [ Bài toán đối ngẫu ]
Ở đây y = (y1, y2, … ,ym) Rm là vectơ biến cần tìm.

• 
  Nhận xét:
  

• 
  Các ràng buộc chính của (P)  các biến của (Q). Các biến của (P)  các ràng buộc chính của (Q).
  
• 
  Các hệ số vế phải ràng buộc chính của (P) trở thành các hệ số mục tiêu của (Q), còn các hệ số mục tiêu của (P) lại trở thành các hệ số vế phải ràng buộc chính của (Q).
  
• 
  Bài toán gốc tìm min thì bài toán đối ngẫu tìm max (và ngược lại).
  
• 
  Cả hai bài toán (P) và(Q) đều có dạng chuẩn.
  

• 
  Ví dụ: tìm bài toán đối ngẫu của bài toán QHTT dạng chuẩn.
  

f(x) = 20×1 + 15×2  min

Bài toán đối ngẫu là :

g(y) = 60y1 + 40y2 + 60y3  max

• 
  Dùng ký hiệu vectơ và ma trận, ta có thể viết:
  

Bài toán gốc: Bài toán đối ngẫu:

AT là ma trận chuyển vị của A, là tích vô hướng của hai vectơ a và b .

1.2. Định nghĩa đối ngẫu của bài toán qui hoạch tuyến tính dạng chính tắc:

Là bài toán :

• 
  Dưới dạng vectơ – ma trận, ta có thể viết:
  

Bài toán gốc: Bài toán đối ngẫu:

1.3 Tổng quát, xét bài toán QHTT có dạng

Trong đó I1  I2  I3 = { 1, …, m }, Ii  Ik = , i, k = 1, 2, 3 ( i  k ) ; J1  J2  J3 = { 1, …, n }, Ji  Jk = , j, k = 1, 2, 3 ( j  k ) .

Ta gọi đối ngẫu của bài toán trên là bài toán:

SƠ ĐỒ ĐỐI NGẪU TỔNG QUÁT
Bài toán gốc	Bài toán đối ngẫu
Các biến gốc: x1, x2,…, xn	Các biến đối ngẫu: y1, y2,…,ym
Hàm mục tiêu
f(x) = c1x1 + c2x2 +…+ cnxn  min	g(y) = b1y1+ b2y2 +…+ bmym  max
Các ràng buộc
ai1x1+ai2x2+…+ainxn	yi
xj	a1jy1+a2jy2+…+amjym

• 
  Nhận xét: Nếu lấy đối ngẫu của bài toán đối ngẫu thì ta sẽ nhận được bài toán gốc.
  

• 
  Ví dụ: tìm bài toán đối ngẫu của bài toán sau
  

Bài toán đối ngẫu là :

2. CÁC ĐỊNH LÝ ĐỐI NGẪU.

2.1. Cặp bài toán đối ngẫu dạng chuẩn:

(P) (Q)
Để tiện nghiên cứu và điều tra lý thuyế đối ngẫu, ta xét cặp bài toán đối ngẫu ( P. ) và ( Q. ) cho ở dạng chuẩn. Tuy nhiên các tác dụng nhận được cũng đúng cho một cặp bài toán đối ngẫu bất kể .

• 
  Định lý 1: (Đối ngẫu yếu).
  

Nếu x là 1 phương án bất kỳ của bài toán gốc (P) và y là 1 phương án bất kỳ của bài toán đối ngẫu (Q) thì:
f ( x ) = c1x1 + c2x2 + … + cnxn  g ( y ) = b1y1 + b2y2 + … + bmym

Hệ quả:

• 
  Giá trị mục tiêu của 1 phương án đối ngẫu bất kỳ là 1 cận dưới cho giá trị mục tiêu đối với mọi phương án của bài toán gốc.
  
• 
  Nếu hàm mục tiêu của bài toán gốc không bị chặn dưới trong miền ràng buộc của nó thì bài toán đối ngẫu không có bất kỳ mộ phương án nào.
  
• 
  Nếu hàm mục tiêu của bài toán đối ngẫu không bị chặn trên trong miền ràng buộc của nó thì bài toán gốc không có bất kỳ một phương án nào.
  
• 
  Nếu x* là 1 phương án của bài toán gốc, y* là 1 phương án của bài toán đối ngẫu và f(x*) = g(y*) thì x* là phương án tối ưu của bài toán gốc và y* là phương án tối ưu của bài toán đối ngẫu.
  

• 
  Định lý 2: (Đối ngẫu mạnh).
  

Nếu một quy hoạch có phương án tối ưu thì quy hoạch đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của chúng là bằng nhau.

• 
  Định lý 3: (Định lý tồn tại).
  

Đối với mỗi cặp quy hoạch đối ngẫu nhau thì có thể xảy ra một trong ba khả năng loại trừ nhau sau đây.

• 
  Cả hai bài toán đều không có phương án.
  
• 
  Cả hai bài toán đều có phương án. Khi đó, cả hai bài toán đều có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu là bằng nhau.
  
• 
  Một bài toán có phương án và bài toán kia không có phương án. Khi đó, bài toán có phương án sẽ không có phương án tối ưu và hàm mục tiêu của nó không giới nội trong miền ràng buộc.
  

• 
  Định lý 4: (Định lý về độ lệch bù).
  

Một cặp phương án x, y của hai bài toán (P), (Q) là những phương án tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức:

• 
  
  
• 
  (2)
  

Nhận xét:

: độ lệch ở ràng buộc I của (P).

: độ lệch ở ràng buộc j của(Q).

Ghi chú:
Các hệ thức ( 1 ), ( 2 ) nói rằng : với mỗi ràng buộc gốc hay đối ngẫu thì tích của độ lệch ở ràng buộc này và biến đối ngẫu ( hay biến gốc ) tương ứng với ràng buộc đó phải bằng không .
Nói cách khác, nếu một ràng buộc có độ lệch dương thì biến ( gốc hay đối ngẫu ) tương ứng với ràng buộc đó phải bằng không ; ngược lại, nếu một biến gốc hay đối ngẫu có giá trị dương thì giải pháp của bài toán thỏa mãn nhu cầu ràng buộc tương ứng với dấu bằng .
Như vậy, hệ thức ( 1 ) có nghĩa là :

>bi yi = 0

Và yi > 0 =bi

Hệ thức (2) cũng có nghĩa tương tự:

< cj xj = 0

Và xj > 0 = cj

• 
  Định lý 5 (Định lý mạnh về độ lệch bù).
  

Nếu cặp bài toán đối ngẫu (P) và (Q) có phương án thì tồn tại một cặp phương án tối ưu x*, y* nghiệm đúng
y * + ( Ax * – b ) > 0
Và x* + ( c – ATy*) >0

2.2. Tìm phương án tối ưu của bài toán đối ngẫu

Nếu biết giải pháp tối ưu của bài toán gốc, vận dụng triết lý đối ngẫu ta hoàn toàn có thể suy ra giải pháp tối ưu của bài tối đối ngẫu tương ứng mà không cần giải nó ,

Ví dụ: Bài toán qui hoạch tuyến tính

Có phương án tối ưu x* = (0, 1, 0, 2, 3) với fmin = 6. Hãy tìm phương án tối ưu của bài toán đối ngẫu tương ứng.

Giải
Bài toán đối ngẫu của bài toán gốc là :

Gọi y * là giải pháp tối ưu của bài toán đối ngẫu
Do x*2, x*3, x*5 >0, nên theo định lý độ lệch bù, y* là nghiệm đúng hệ phương trình:

Giải hệ phương trình ta có:
Vậy y * ( – 5, 1, 1 ) là giải pháp tối ưu của g ( y ) với
gmax = – 5 + ( 3 * 1 ) + ( 8 * 1 ) = 6 = fmin

Ví dụ: dùng phương pháp đơn hình giải quy hoạch gốc (P) sau đây, từ đó suy ra lời giải của bài toán đối ngẫu tương ứng với nó.

Xuất phát từ giải pháp cực biên khởi đầu x0 = ( 2, 12, 9, 0, 0, 0 ), cơ sở tương ứng { A1, A2, A3 ). Quá trình giải được ghi lại trong bảng đơn hình dưới đây .

Để tìm lời giải (phương án tối ưu) của bài toán đối ngẫu ta áp dụng qui tắc sau:

Qui tắc

Nếu cơ sở ban đầu của (P) là cơ sở chính tắc (các vecto đơn vị), giả sử là {Aj, jJ}.

Để tìm giải thuật của bài toán đối ngẫu, ta chọn ra từ bảng đơn hình sau cuối của ( P. ) các  j ( j  J ) rồi cộng với thông số cj tương ứng .
Vì thế, giải thuật của bài toán đối ngẫu y * = ( y * 1, y * 2, y * 3 ) được xác lập như sau :

Vậy y* =(, -1, ) và gmax = -17 = fmin

2. 
   BÀI TẬP