Giải thuật đối ngẫu

Xét hai bài toán đối ngẫu :

Chúng ta sẽ xét xem giải thuật đơn hình cơ bản đã biết trong chương trước được áp dụng như thế nào đối với bài toán đối ngẫu.

Giả sử rằng B là một cơ sở của bài toán (P) thoả :

y=cBTB−1 size 12{y=c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } } {} và NTy≥cN size 12{N rSup { size 8{T} } y >= c rSub { size 8{N} } } {}

Nếu B cũng là một cơ sở khả thi của bài toán gốc, tức là, thì (theo định lý đối ngẫu) y, x lần lượt là phương án tối ưu của bài toán đối ngẫu và bài toán gốc. Nếu không thì xBxNrighx= size 12{x=alignl { stack { left [x rSub { size 8{B} } {} # right ] left [x rSub { size 8{N} } {} # righ]} } [ ] } {} không là phương án của bài toán gốc vì xB=b¯=B−1b size 12{x rSub { size 8{B} } = {overline {b}} =B rSup { size 8{ - 1} } b} {} không thể ≥ 0.

Để tiện việc trình bày ta xét (m=3 , n=5) :

và bài toán đối ngẫu

(D)

Người ta đưa (D) về dạng chính tắc bằng cách thêm các biến phụ y₄ y₅, y₆, y₇, y₈ ≥ 0. Chúng không ảnh hưởng đến hàm mục tiêu.

Các dữ liệu của (D) được trình bày trong bảng sau :

Giả sử rằng m cột đầu tiên của A là một cơ sở B của (P) thì hai bảng trên được trình bày rút gọn như sau :

Để đưa bài toán đối ngẫu về dạng chuẩn người ta nhân (bên trái) bảng (D) với bảng sau đây :

Khi đó người ta được bảng kết quả có dạng :

Bảng này cho ta một quy hoạch tuyến tính dạng chuẩn với ma trận đơn vị (cơ sở) tương ứng với các cột y₁ y₂ y₃ y₇ y₈ .

Áp dụng giải thuật đơn hình cơ bản vào kết quả này cho ta quy tắc đổi cơ sở như sau :

Tính : b¯=B−1b≥0 size 12{ {overline {b}} =B rSup { size 8{ - 1} } b >= 0} {}

a- Nếu b¯≥0 size 12{ {overline {b}} >= 0} {} thì giải thuật kết thúc, khi đó :

y=cBTB−1 size 12{y=c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } } {} là phương án tối ưu của bài toán đối ngẫu .

xBxNrighb¯0righx= size 12{x=alignl { stack { left [x rSub { size 8{B} } {} # right ] left [x rSub { size 8{N} } {} # righ]} } [ ] =alignl { stack { left [ {overline {b}} {} # right ] left [0 {} # righ]} } [ ] } {} là phương án tối ưu của bài toán gốc .

b- Nếu tồn tại r sao cho b¯r∈b¯,b¯r<0 size 12{ {overline {b}} rSub { size 8{r} } in {overline {b}} , {overline {b}} rSub { size 8{r} } <0} {} thì xảy ra một trong hai trường hợp sau :

- Nếu trong dòng r của N¯ size 12{ {overline {N}} } {} có thành phần < 0 thì người ta tính :

Như vậy : đối với bài toán đối ngẫu thì biến y_r đi vào cơ sở và biến y_s ra khỏi cơ sở, trong khi đó đối với bài toán gốc thì biến x_s đi vào cơ sở và biến x_r ra khỏi cơ sở.

- Nếu mọi thành phần trong dòng r của N¯ size 12{ {overline {N}} } {} đều > 0 thì phương án tối ưu của bài toán đối ngẫu là không giới nội, điều này (theo định lý đối ngẫu) dẫn đến bài toán gốc không có phương án.

Ta có thể chọn bài toán (D) hoặc (P) để giải tìm phương án tối ưu bằng phương pháp đơn hình, từ đó suy ra phương án tối ưu của bài toán còn lại theo kết quả trên. Trong ví dụ này ta chọn bài toán (D) để giải vì có chứa sẵn ma trận đơn vị.

Giải bài toán (D) bằng phương pháp đơn hình cải tiến ta được :

Giải thuật dừng vì thoả dấu hiệu tối ưu của bài toán min.

Phương án tối ưu của bài toán (D) là :