Dấu hiệu tối ưu

Ma trận cơ sở

Người ta gọi cơ sở của bài toán quy hoạch tuyến tính chính tắc (P) là mọi ma trận B không suy biến (có ma trận nghịch đảo) mxm trích ra từ m cột của ma trận ràng buộc A. Các cột còn lại được gọi là ma trận ngoài cơ sở, ký hiệu là N .

Phương án cơ sở - Phương án cơ sở khả thi

B là một cơ sở của bài toán (P).

Khi đó, bằng cách hoán vị các cột của A người ta có thể luôn luôn đặt A dưới dạng :

Phương án cơ sở

Người ta gọi một phương án cơ sở tương ứng với cơ sở B là một phương án đặc biệt, nhận được bằng cách cho :

x_N = 0

Khi đó x_B được xác định một cách duy nhất bằng cách giải hệ phương trình tuyến tính bằng phương pháp Cramer :

Bx_B = b ⇔ x_B = B^-1b

Phương án cơ sở khả thi

Một phương án cơ sở là phương án cơ sở khả thi nếu :

x_B = B^-1b ≥ 0

Cơ sở tương ứng với một phương án khả thi được gọi là cơ sở khả thi .

Ví dụ : xét bài toán quy hoạch tuyến tính dạng chính tắc :

Các cột x₅ x₆ x₃ tạo thành một ma trận cơ sở . Các biến tương ứng được gọi là các biến (trong) cơ sở .

Các cột x₁ x₂ x₄ tạo thành một ma trận ngoài cơ sở. Các biến tương ứng được gọi là các biến ngoài cơ sở.

Một phương án cơ sở khả thi của bài toán là :

Suy biến

Một phương án cơ sở khả thi được gọi là suy biến nếu x_B = B^-1b ≥ 0 có những thành phần bằng 0. Sự suy biến là một hiện tượng thường xảy ra trong một số bài toán như bài toán vận tải, dòng dữ liệu, đường đi ngắn nhất....... Đây là hiện tượng khá phức tạp (có nhiều cách giải quyết sẽ được xét sau). Vì vậy trong những phần tiếp theo ta giả sử rằng phương án cơ sở khả thi là không suy biến, tức là x_B = B^-1b > 0 ( dương thực sự ) .

Ðịnh lý 4 (dấu hiệu tối ưu)

Xét bài toán quy hoạch tuyến tính chính tắc

Người ta thường gọi :

c_N là chi phí ngoài cơ sở

c_B là chi phí cơ sở

c¯NT size 12{ {overline {c}} rSub { size 8{N} } rSup { size 8{T} } } {} là chi phí trượt giảm

cBTB−1N size 12{c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } N} {}là lượng gia giảm chi phí

Chứng minh (cho bài toán max)

Ðiều kiện đủ

Giả sử x* là một phương án cơ sở khả thi với ma trận cơ sở B và thoả

thì cần chứng minh x* là phương án tối ưu, nghĩa là chứng minh rằng với mọi phương án bất kỳ của bài toán ta luôn có :

z(x) ≤ z(x*)

Xét một phương án khả thi x bất kỳ , x thoả :

Tính giá trị hàm mục tiêu đối với phương án x ta được :

Vậy x* là phương án tối ưu.

Ðiều kiện cần

Giả sử là phương án tối ưu với ma trận cơ sở B, cần chứng minh rằng : c¯NT=cNT−cBTB−1N ≤ 0 size 12{ {overline {c}} rSub { size 8{N} } rSup { size 8{T} } =c rSub { size 8{N} } rSup { size 8{T} } - c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } "N " <= " 0"} {}.

( c¯N size 12{ {overline {c}} rSub { size 8{N} } } {} là vectơ có n-m thành phần)

Ta sẽ chứng minh điều này bằng phản chứng.

Giả sử rằng tồn tại một thành phần c_s của c¯N size 12{ {overline {c}} rSub { size 8{N} } } {} mà c_s > 0. Dựa vào c_s người ta xây dựng một vectơ x như sau :

Trong đó θ>0 và I_s là một vectơ có (n-m) thành phần bằng 0, trừ thành phần thứ s bằng 1 . Vậy

(*)

Do B^-1b ≥ 0 nên người ta có thể chọn θ>0 đủ nhỏ để x_B > 0

Vậy x được chọn như trên sẽ thoả :

x ≥ 0 (3)

Ta kiểm chứng x thỏa ràng buộc của bài toán bằng cách tính :

Từ (3) và (4) cho thấy x là một phương án khả thi của bài toán

Bây giờ ta chỉ ra mâu thuẩn bằng so sánh giá trị hàm mục tiêu tại x và x* . Ta có :

Vậy x* không phải là phương án tối ưu nên mâu thuẩn với giả thiết .

Chú ý

Qua việc chứng minh định lý dấu hiệu tối ưu ta thấy rằng từ một phương án cơ sở khả thi chưa tối ưu có thể tìm được các phương án khả thi càng lúc càng tốt hơn nhờ lặp lại nhiều lần công thức (*). Vấn đề được đặt là đại lượng θ được chọn như thế nào để nhanh chóng nhận được phương án tối ưu.

Bổ đề

Xét bài toán quy hoạch tuyến tính chính tắc

với B là một cơ sở khả thi nào đó và x⁰ là phương án cơ sở tương ứng, tức là

và z(x0)=cBTB−1b size 12{z ( x rSup { size 8{0} } ) =c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } b} {}

Xét.

Nếu tồn tại một biến ngoài cơ sở x_s sao cho c¯s size 12{ {overline {c}} rSub { size 8{s} } } {}>0 với c¯s size 12{ {overline {c}} rSub { size 8{s} } } {}là thành phần thứ s của c¯N size 12{ {overline {c}} rSub { size 8{N} } } {} thì :

a- Hoặc là người ta có thể làm tăng một cách vô hạn giá trị của x_s mà không đi ra khỏi tập hợp các phương án khả thi, và trong trường hợp này phương án tối ưu của bài toán không giới nội.

b- Hoặc là người ta có thể xác định một cơ sở khả thi khác là B size 12{ {B} cSup { size 8{ and } } } {} có phương án cơ sở khả thi x size 12{ {x} cSup { size 8{ and } } } {} tương ứng với nó là tốt hơn , tức là :

z(x⁰) < z( x size 12{ {x} cSup { size 8{ and } } } {})

Chứng minh

Trong quá trình chứng minh định lý dấu hiệu tối ưu ta có phương án mới được xác định như sau :

Hai trường hợp có thể xảy ra như sau :

a- Trường hợp N¯s≤0 size 12{ {overline {N}} rSub { size 8{s} } <= 0} {}

Trong trường hợp này x_s có thể nhận một giá trị θ lớn tuỳ mà vẫn đảm bảo x_B ≥ 0, nghĩa là x luôn luôn thoả ≥ 0 . Khi đó như đã biết giá trị hàm mục tiêu tương ứng là

với c¯sθ size 12{ {overline {c}} rSub { size 8{s} } θ} {} có thể lớn vô hạn thì giá trị của hàm mục tiêu là không giới nội.

b- Trường hợp tồn tại i=1→m sao cho N¯is>0 size 12{ {overline {N}} rSub { size 8{ ital "is"} } >0} {}

( N¯is>0 size 12{ {overline {N}} rSub { size 8{ ital "is"} } >0} {} là thành phần thứ i của N¯s size 12{ {overline {N}} rSub { size 8{s} } } {})

Trong trường hợp này giá trị của θ>0 mà x_s có thể nhận không thể tăng vô hạn vì phải đảm bảo x_B>0. Giá trị lớn nhất θ size 12{ {θ} cSup { size 8{ and } } } {} của θ mà x_s có thể nhận được xác định như sau :

Ghi chú :

Trong trường hợp bài toán không suy biến, nếu θ size 12{ {θ} cSup { size 8{ and } } } {} được xác định một cách duy nhất thì phương án mới x size 12{ {x} cSup { size 8{ and } } } {} có đúng m thành phần khác 0. Thật vậy :

- Biến x_s đang bằng 0 trong phương án x⁰ trở thành dương thật sự vì xs=θˆ size 12{x rSub { size 8{s} } = { hat {θ}}} {}

- Biến x_r đang dương thật sự bây giờ nhận giá trị :

Vậy phương án mới x size 12{ {x} cSup { size 8{ and } } } {} là một phương án cơ sở. Nó tương ứng với cơ sở ở B size 12{ {B} cSup { size 8{ and } } } {} được suy ra từ B bằng cách thay thế cột r bằng cột s.

Người ta nói rằng hai cơ sở B và B size 12{ {B} cSup { size 8{ and } } } {} là kề nhau, chung tương ứng với những điểm cực biên kề nhau trong tập hợp lồi S các phương án khả thi của bài toán.