- Bài toỏn tối ưu tổng quỏt...3. - Phõn loại bài toỏn...3. - Bài toỏn ...17. - Bài toỏn đối ngẫu ...41. - Bài toỏn tối ưu tổng quỏt. - Mỗi một vectơ được gọi là một phương ỏn của bài toỏn (hay lời giải chấp nhận được).. - Phõn loại bài toỏn. - Bài toỏn cỏi tỳi. - Bài toỏn vận tải. - Khi đú bài toỏn (I) sẽ cú phương ỏn cực biờn tối ưu. - Ta sẽ chứng minh rằng sẽ là phương ỏn tối ưu của bài toỏn (I).. - x D , hay là phương ỏn tối ưu của bài toỏn (I). - Xột bài toỏn QHTT dạng chớnh tắc (I). - Bài toỏn. - Vớ dụ: Giải bài toỏn QHTT sau. - Xột bài toỏn QHTT dạng chớnh tắc:. - Nếu bài toỏn (I) cú phương ỏn thỡ cú phương ỏn cực biờn.. - Vớ dụ 1: Giải bài toỏn QHTT sau. - Vớ dụ 2: Giải bài toỏn QHTT sau. - Ta xột bài toỏn:. - Bài toỏn (2) cú phương ỏn cực biờn xuất phỏt là với cơ sở là. - Trường hợp bài toỏn khụng suy biến. - Trường hợp bài toỏn suy biến. - Khi đú ta xột bài toỏn phụ như sau:. - Định lý: Bài toỏn ban đầu (I) cú phương ỏn cực biờn là khi và chỉ khi bài toỏn (P) cú phương ỏn tối ưu là với. - “Điều kiện cần”: giả thiết bài toỏn (I) cú phương ỏn cực biờn là . - Như vậy để giải bài toỏn QHTT (I) thỡ ta làm theo cỏc bước sau đõy: Pha 1, giải bài toỏn phụ để tỡm phương ỏn cực biờn xuất phỏt cho bài toỏn (I). - Giả sử khi giải bài toỏn (P) ta thu được phương ỏn tối ưu là . - 0 thỡ kết luận bài toỏn ban đầu (I) khụng cú phương ỏn.. - Khi đú ta kết luận chớnh là phương ỏn cực biờn xuất phỏt của bài toỏn (I).. - Ta đi giải bài toỏn phụ. - Bài toỏn phụ cú một cơ sở là và phương ỏn cực biờn tương ứng là. - Vậy ta thu được là phương ỏn tối ưu của bài toỏn phụ và cỏc biến giả . - Do đú là phương ỏn cực biờn xuất phỏt của bài toỏn ban đầu với cơ sở. - Vớ dụ 2: Giải bài toỏn sau. - Ta xột bài toỏn phụ:. - Vậy là phương ỏn tối ưu của bài toỏn. - Nhưng nờn ta kết luận bài toỏn. - Khi đú ta xột bài toỏn (M) sau:. - Đối với bài toỏn (M) ta thấy , với , là một phương ỏn cực biờn. - a) Nếu bài toỏn (I) cú phương ỏn thỡ mọi phương ỏn cực biờn tối ưu của bài toỏn (M) phải cú. - b) Bài toỏn (I) cú phương ỏn tối ưu khi và chỉ khi bài toỏn (M) cú phương ỏn tối ưu là. - Như vậy việc giải bài toỏn (I) cú thể đưa về việc giải bài toỏn (M). - Khi đú ta kết luận bài toỏn (I) khụng cú phương ỏn.. - Ta sẽ đi giải bài toỏn (2) sau:. - Bài toỏn (2) cú một cơ sở là và phương ỏn cực biờn tương ứng là. - Vậy bài toỏn (2) cú phương ỏn tối ưu là . - Nhưng do nờn bài toỏn (1) cú phương ỏn tối ưu là. - Bài toỏn đối ngẫu. - Khi đú bài toỏn. - Khi đú bài toỏn đối ngẫu cú dạng:. - Bài toỏn gốc (P) Bài toỏn đối ngẫu (Q) min. - Vớ dụ: Cho bài toỏn gốc. - 1 khi đú bài toỏn đối ngẫu là:. - bất kỳ của bài toỏn đối ngẫu (Q). - Định lý 2: Nếu là phương ỏn của bài toỏn (P), là phương ỏn của bài toỏn (Q) thoả món. - Khi đú là phương ỏn tối ưu của bài toỏn (P) và là phương ỏn tối ưu của bài toỏn (Q).. - Do đú là phương ỏn tối ưu của bài toỏn (P). - Vậy là phương ỏn tối ưu của bài toỏn (Q). - a) Nếu bài toỏn (P) cú phương ỏn tối ưu thỡ bài toỏn (Q) cũng cú phương ỏn tối ưu là và ngược lại. - của bài toỏn gốc (P) khụng bị chặn dưới thỡ bài toỏn đối ngẫu (Q) khụng cú phương ỏn.. - c) Nếu hàm mục tiờu của bài toỏn đối ngẫu (Q) khụng bị chặn trờn thỡ bài toỏn gốc (P) khụng cú phương ỏn.. - d) Nếu là phương ỏn tối ưu của bài toỏn gốc (P) với cơ sở tương ứng là J thỡ là phương ỏn tối ưu của bài toỏn đối ngẫu (Q), trong đú. - Giả thiết x * ∈ℜ n là phương ỏn của bài toỏn gốc (P), y * ∈ℜ m là phương ỏn. - của bài toỏn đối ngẫu (Q). - Xột bài toỏn đối ngẫu của bài toỏn (P):. - Vớ dụ: Xột bài toỏn QHTT sau. - Khi đú ta cú bài toỏn đối ngẫu là:. - Ta cú là phương ỏn cực biờn xuất phỏt của bài toỏn (1) với cơ sở là . - nhưng y này khụng là phương ỏn chấp nhận được của bài toỏn đối ngẫu (2). - Nếu thỡ ta kết luận bài toỏn gốc khụng cú phương ỏn. - Vớ dụ 1: giải bài toỏn. - Vớ dụ 2: Xột bài toỏn QHTT. - Với bài toỏn mở rộng thỡ J J. - ắ Trường hợp 1: Bài toỏn mở rộng khụng cú phương ỏn. - ắ Trường hợp 2: Bài toỏn mở rộng cú phương ỏn tối ưu. - Khi đú ta kết luận bài toỏn xuất phỏt cú phương ỏn tối ưu là. - ắ Trường hợp 3: Bài toỏn mở rộng cú phương ỏn tối ưu. - Vớ dụ: Giải bài toỏn sau. - 0,1,2,3 } là một cơ sở của bài toỏn mở rộng. - Bài toỏn người du lịch. - Giải bài toỏn QHTT: thu được phương ỏn tối ưu là (nếu khụng thu được thỡ ta kết luận bài toỏn (1)-(4) khụng cú lời giải, hoặc khụng cú lời giải hữu hạn).. - Mọi phương ỏn chấp nhận được của bài toỏn (1)-(4) đều phải thoả món (tức là nú khụng cắt đi bất kỳ phương ỏn chấp nhận được nào của bài toỏn xuất phỏt).. - Giải bài toỏn QHTT (1)-(3) được nghiệm tối ưu là (nếu khụng thu được thỡ ta kết luận bài toỏn (1)-(4) khụng cú lời giải).. - vào bài toỏn (1)-(3).. - a) Vớ dụ 1: Giải bài toỏn sau. - Xột bài toỏn QHTT nguyờn (1)-(4). - ε được gọi là phương ỏn ε - tối ưu của bài toỏn (trong đú là giỏ trị nào đú cho trước).. - a) Bước chuẩn bị : Giải bài toỏn QHTT tương ứng với thu được phương ỏn tối ưu. - Ngược lại thỡ bài toỏn khụng cú phương ỏn chấp nhận được.. - f x x D ∈ k 1 } và P k 2 là bài toỏn: min. - (i) Phỏt hiện bài toỏn khụng cú phương ỏn chấp nhận được.. - Bài toỏn là đó xột xong. - Giải bài toỏn QHTT tương ứng với bài toỏn P o ta thu được phương ỏn tối ưu là x 0 = (3/2. - Tớnh cận dưới cho P 2 : Giải bài toỏn QHTT tương ứng ta thu được phương ỏn tối ưu là x 2 = (2. - Tớnh cận dưới cho P 3 : Giải bài toỏn QHTT tương ứng ta thu được phương ỏn tối ưu là x 3 = (9/4. - Kết luận: Bài toỏn cú phương ỏn tối ưu là x. - b) Vớ dụ 2: Giải bài toỏn sau. - Giải bài toỏn QHTT tương ứng với P o ta thu được phương ỏn tối ưu là và. - Tớnh cận dưới cho P 1 : Giải bài toỏn QHTT tương ứng ta thu được phương ỏn tối ưu là x 1 = (2
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt