intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng: Tài liệu tối ưu hóa

Chia sẻ: Tuhuy Tuhuy | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
1.342
lượt xem 468
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chúng ta thấy rằng, một cách hiển nhiên nhất để giải bài toán đặt ra là: Tính giá trị của hàm ()fx trên tất cả các phương án của miền ràng buộc sau đó so sánh các giá trị của hàm mục tiêu thu được để tìm ra phương án tối ưu. Tuy nhiên cách làm này là rất khó hoặc đúng hơn là không thể làm được trong trường hợp tổng quát (chẳng hạn tập là không đếm được). Vì vậy chúng ta phải phân tách nhỏ ra bằng cách thêm một số điều kiện nào đó để được......

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng: Tài liệu tối ưu hóa

  1. ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN -----o0o----- Bài giảng môn TỐI ƯU HÓA THÂN QUANG KHOÁT Thái nguyên - 2007
  2. Thân Quang Khoát MỤC LỤC Chương 1. MỞ ĐẦU......................................................................................................3 §1. ĐỐI TƯỢNG NGHIÊN CỨU ...............................................................................3 1.1. Bài toán tối ưu tổng quát...................................................................................3 1.2. Phân loại bài toán ..............................................................................................3 1.3. Một số mô hình thực tế .....................................................................................4 §2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ..........................................................6 2.1. Dạng tổng quát ..................................................................................................6 2.2. Dạng chuẩn tắc..................................................................................................7 2.3. Dạng chính tắc...................................................................................................7 §3. MỘT SỐ KIẾN THỨC BỔ TRỢ ..........................................................................9 3.1. Tập hợp lồi và điểm cực biên............................................................................9 3.2. Đa diện lồi (polytope) .....................................................................................10 §4. CẤU TRÚC MIỀN RÀNG BUỘC CỦA BÀI TOÁN ........................................11 QUY HOẠCH TUYẾN TÍNH ............................................................................11 4.1. Phương án cực biên và phương án cực biên tối ưu.........................................11 4.2. Điều kiện cần và đủ để một phương án là cực biên ........................................13 4.3. Cơ sở của một phương án cực biên.................................................................15 Chương 2. THUẬT TOÁN ĐƠN HÌNH....................................................................17 §1. MỞ ĐẦU .............................................................................................................17 1.1. Bài toán ...........................................................................................................17 1.2. Phương pháp Hình Học...................................................................................17 §2. THUẬT TOÁN ĐƠN HÌNH ...............................................................................19 2.1. Tư tưởng của thuật toán đơn hình ...................................................................19 2.2. Công thức số gia hàm mục tiêu - dấu hiệu tối ưu ...........................................20 2.3. Tìm phương án cực biên tốt hơn - Công thức đổi cơ sở .................................21 2.4. Thuật toán đơn hình (Simplex method) ..........................................................23 2.5. Bảng đơn hình .................................................................................................24 §3. TÍNH HỮU HẠN CỦA THUẬT TOÁN ĐƠN HÌNH .......................................28 3.1. Trường hợp bài toán không suy biến ..............................................................28 3.2. Trường hợp bài toán suy biến .........................................................................28 §4. PHƯƠNG PHÁP HAI PHA ................................................................................31 4.1. Vấn đề .............................................................................................................31 4.2. Phương pháp hai pha giải bài toán QHTT ......................................................32 Bộ môn Khoa Học Cơ Bản 1
  3. Bài Giảng môn Tối Ưu Hoá 4.3. Một số ví dụ ....................................................................................................34 §5. PHƯƠNG PHÁP ĐÁNH THUẾ.........................................................................36 §6. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU ...................................41 6.1. Bài toán đối ngẫu ............................................................................................41 6.2. Các định lý đối ngẫu .......................................................................................42 6.3. Một số ứng dụng của lý thuyết đối ngẫu ........................................................44 6.4. Thuật toán đơn hình đối ngẫu .........................................................................46 Chương 3. TỐI ƯU HOÁ RỜI RẠC .........................................................................56 §1. BÀI TOÁN TỐI ƯU HOÁ RỜI RẠC.................................................................56 1.1. Mở đầu ............................................................................................................56 1.2. Một số bài toán tối ưu hoá rời rạc tiêu biểu....................................................56 §2. PHƯƠNG PHÁP CẮT GOMORY GIẢI BÀI TOÁN QHTT NGUYÊN ..........58 2.1. Tư tưởng chung của phương pháp cắt ............................................................58 2.2. Phương pháp cắt Gomory cho bài toán QHTT nguyên hoàn toàn .................59 2.3. Phương pháp cắt Gomory cho bài toán QHTT nguyên bộ phận ....................64 §3. PHƯƠNG PHÁP NHÁNH CẬN ........................................................................65 3.1. Sơ đồ tổng quát ...............................................................................................65 3.2. Thuật toán nhánh cận Land-Doig giải bài toán QHTT nguyên ......................66 3.3. Một số ví dụ ....................................................................................................68 §4. BÀI TOÁN CÁI TÚI...........................................................................................72 4.1. Đưa bài toán QHTT Nguyên về bài toán cái túi .............................................72 4.2. Phương pháp Quy hoạch động giải bài toán cái túi ........................................74 Tài liệu tham khảo.......................................................................................................77 Khoa Công nghệ thông tin - ĐHTN 2
  4. Thân Quang Khoát Chương 1. MỞ ĐẦU §1. ĐỐI TƯỢNG NGHIÊN CỨU 1.1. Bài toán tối ưu tổng quát Bài toán tối ưu tổng quát có dạng như sau: f (x ) → min (max) ⎧gi(x ) ≥bi , i = 1,m1 ⎪ ⎪ ⎪ ⎪g (x ) ≤b , j = m +1,m ⎪ j ⎪ j 1 2 ⎨ ⎪gk (x ) = bk , k = m2 +1,m ⎪ ⎪ ⎪ ⎪x ∈ X ⊂ℜn ⎪ ⎪ ⎩ Trong đó f (x ) được gọi là hàm mục tiêu; gi(x ), i = 1,m được gọi là các hàm ràng buộc. Mỗi một đẳng thức hay bất đẳng thức được gọi là một ràng buộc. Gọi ⎧ ⎪ g (x ) ≥bi,i = 1,m1; g j (x ) ≤bj, j = m1 +1,m2⎫ ⎪ D =⎨⎪x ∈ℜn i ⎪ ⎬ ⎪ ⎪ gk (x ) = bk,k = m2 +1,m; x ∈ X ⎪ ⎪ ⎪ ⎩ ⎪ ⎭ D được gọi là miền ràng buộc (hay miền chấp nhận được). Mỗi một vectơ x = (x 1, x 2, ..., x n ) ∈ D đượ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). Định nghĩa: Phương án x * ∈ D được gọi là phương án tối ưu của bài toán nếu thoả mãn điều kiện sau f (x *) ≤ f (x ) , ∀x ∈ D (®èi víi bµi to¸n t×m Min) f (x *) ≥ f (x ) , ∀x ∈ D (®èi víi bµi to¸n t×m Max) khi đó giá trị f (x *) được gọi là giá trị tối ưu. 1.2. Phân loại bài toán Chúng ta thấy rằng, một cách hiển nhiên nhất để giải bài toán đặt ra là: Tính giá trị của hàm f (x ) trên tất cả các phương án của miền ràng buộc sau đó so sánh các giá trị của hàm mục tiêu thu được để tìm ra phương án tối ưu. Tuy Bộ môn Khoa Học Cơ Bản 3
  5. Bài Giảng môn Tối Ưu Hoá nhiên cách làm này là rất khó hoặc đúng hơn là không thể làm được trong trường hợp tổng quát (chẳng hạn tập D là không đếm được). Vì vậy chúng ta phải phân tách nhỏ ra bằng cách thêm một số điều kiện nào đó để được các bài toán “dễ giải”. Người ta đã phân ra một số loại bài toán như sau: + Quy hoạch tuyến tính + Quy hoạch lồi. + Quy hoạch phi tuyến. + Quy hoạch toàn phương. + Quy hoạch rời rạc. + Quy hoạch nguyên. 1.3. Một số mô hình thực tế Ta sẽ xem xét một số bài toán trong thực tế đưa đến bài toán tối ưu hoá và mô mình toán học tương ứng của nó. 1.3.1. Bài toán lập kế hoạch sản xuất cho một nhà máy Một nhà máy có khả năng sản xuất n loại sản phẩm. Để sản xuất n loại sản phẩm này thì cần m loại nguyên liệu. Biết: aij - lượng nguyên liệu loại i cần thiết để sản xuất một đơn vị sản phẩm loại j bi - lượng dự trữ nguyên liệu loại i c j - tiền lãi từ việc bán một đơn vị sản phẩm loại j i = 1,m , j = 1,n Hãy xây dựng kế hoạch sản xuất sao cho nhà máy thu được tổng lợi nhuận là nhiều nhất. Gọi x j là lượng sản phẩm loại j mà nhà máy sẽ sản xuất, rõ ràng ta có x j ≥ 0 . Kế hoạch sản xuất của nhà máy sẽ là véctơ x = (x 1, x 2, ..., x n ) . Đại lượng n ∑ j =1aijx j là tổng chi phí nguyên liệu loại i theo kế hoạch sản xuất x , theo giả n thiết ta có: ∑ j =1aijx j ≤bi Khoa Công nghệ thông tin - ĐHTN 4
  6. Thân Quang Khoát Tổng lợi nhuận thu được theo kế hoạch sản xuất x sẽ là ∑n=1c jx j . Như vậy j yêu cầu của bài toán này đưa về mô hình toán học như sau: f (x ) = ∑n=1c jx j → Max j ⎧∑n=1aijx j ≤bi , i = 1,m ⎪ j ⎪ ⎨ ⎪x j ≥ 0 , j = 1,n ⎪ ⎪ ⎩ Mô hình thu được chính là một bài toán quy hoạch tuyến tính. 1.3.2. Bài toán cái túi Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b . Có n loại đồ vật có thể đem theo. Đồ vật thứ j có trọng lượng là a j và giá trị sử dụng là c j (j = 1,n) . Hỏi rằng nhà thám hiểm cần lấy các loại đồ vật nào và số lượng bao nhiêu để cho tổng giá trị sử dụng của các đồ vật mang theo là nhiều nhất ? Gọi x j (j = 1,n) là số lượng đồ vật loại j mà nhà thám hiểm sẽ đem theo. Khi đó tổng giá trị của các đồ vật đó là ∑n=1c jx j , tổng trọng lượng của chúng là j n n ∑ j =1a jx j . Từ giả thiết ta có ∑ j =1a jx j ≤b . Như vậy yêu cầu của bài toán sẽ đưa về việc giải bài toán sau: n ∑ j =1c jx j → max ⎧∑n=1a jx j ≤b ⎪ j ⎪ ⎨ ⎪x j ≥ 0 vµ nguyªn (j = 1,n) ⎪ ⎩ Đây lại là một bài toán quy hoạch tuyến tính Nguyên. 1.3.3. Bài toán vận tải Có m kho hàng cùng chứa một loại hàng hoá, lượng hàng có ở kho thứ i là ai (i = 1,m) . Có n địa điểm tiêu thụ loại hàng nói trên, với nhu cầu tiêu thụ ở điểm j là bj (j = 1,n) . Biết cij là cước phí vận chuyển một đơn vị hàng hoá từ kho thứ i đến điểm tiêu thụ thứ j . Hãy lập kế hoạch vận chuyển hàng hoá từ các kho đến các điểm tiêu thụ sao cho tổng chi phí vận chuyển là nhỏ nhất. Ký hiệu x ij là lượng vận chuyển từ kho i đến điểm tiêu thụ thứ j , khi đó: Bộ môn Khoa Học Cơ Bản 5
  7. Bài Giảng môn Tối Ưu Hoá m n ∑ ∑ cijx ij là tổng chi phí vận chuyển i =1 j =1 n ∑ x ij là lượng hàng vận chuyển từ kho thứ i j =1 m ∑ x ij là lượng hàng vận chuyển đến điểm tiêu thụ thứ j i =1 khi đó bài toán lập kế hoạch trên có thể đưa về mô hình toán học như sau: m n ∑ ∑ cijx ij → Min i =1 j =1 ⎧∑n=1 x ij = ai ⎪ j ⎪ ⎪ n ⎪∑ x ij =bj ⎨ j =1 ⎪ ⎪ ⎪x ij ≥ 0, i = 1,m, j = 1,n ⎪ ⎪ ⎩ Đây chính là một bài toán Quy hoạch tuyến tính. §2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 2.1. Dạng tổng quát Tìm véctơ x = (x 1, x 2, ..., x n )t ∈ ℜn sao cho: n f (x ) = ∑ c jx j → Min (Max ) j =1 với các điều kiện: ⎧∑n=1aijx j ≥bi , i = 1,m1 ⎪ j ⎪ ⎪ n ⎪ ⎪∑ j =1a pjx j ≤bp , p = m1 +1,m2 ⎪ ⎪ n ⎪ ⎪∑ j =1akjx j =bk , k = m2 +1,m ⎪ D =⎪ ⎨ ⎪x j ≥ 0, j = 1,n1 ⎪ ⎪ ⎪ ⎪x j ≤ 0, j = n1 +1,n2 ⎪ ⎪ ⎪ ⎪x tù do , j = n +1,n ⎪ j ⎪ ⎩ 2 Dễ thấy rằng: 1) f (x ) → min ⇔ − f (x ) → max Khoa Công nghệ thông tin - ĐHTN 6
  8. Thân Quang Khoát n n 2) ∑ aijx j ≥bi ⇔ ∑ (−aij )x j ≤−bi j =1 j =1 n ⎧∑ aijx j ≥bi ⎪ ⎪j =1 ⎪ n 3) ∑ aijx j =bi ⇔ ⎪ ⎨n j =1 ⎪∑ a x ≤b ⎪ ij j i ⎪j =1 ⎪ ⎩ n n 4) ∑ aijx j ≥bi ⇔ ∑ aijx j −x n +i =bi , (x n +i ≥ 0) j =1 j =1 n n 5) ∑ aijx j ≤bi ⇔ ∑ aijx j + x n +i =bi , (x n +i ≥ 0) j =1 j =1 các biến x n +i được gọi là các biến bù. 6) Một biến x j không ràng buộc về dấu (tự do) có thể được thay bằng hiệu hai biến không âm: x j = x j −x j Víi x j ≥ 0, x j ≥ 0 Từ các nhận xét trên ta thấy rằng bất kỳ một bài toán quy hoạch tuyến tính nào cũng có thể đưa về một trong hai dạng sau đây: 2.2. Dạng chuẩn tắc n f (x ) = ∑ c jx j → Min j =1 n ⎧∑ aijx j ≥bi , i = 1,m ⎪ ⎪j =1 ⎪ ⎨ ⎪x ≥ 0 , j = 1,n ⎪ j ⎪ ⎩ Hay dưới dạng ma trận f (x ) = ctx → Min ⎧Ax ≥b ⎪ ⎪ ⎨ ⎪x ≥ 0 ⎪ ⎩ trong đó: c, x ∈ℜn, b ∈ℜm, A lµ ma trËn cÊp m×n 2.3. Dạng chính tắc Bộ môn Khoa Học Cơ Bản 7
  9. Bài Giảng môn Tối Ưu Hoá n f (x ) = ∑ c jx j → Min j =1 n ⎧∑ aijx j = bi , i = 1,m ⎪ ⎪j =1 ⎪ ⎨ ⎪x ≥ 0 , j = 1,n ⎪ j ⎪ ⎩ Hay dưới dạng ma trận f (x ) = ctx → Min ⎧Ax =b ⎪ ⎪ ⎨ ⎪x ≥ 0 ⎪ ⎩ Ví dụ: Cho bài toán quy hoạch tuyến tính f (x ) = 2x 1 − 3x 2 + 4x 3 − 5x 4 → max ⎧ x 1 +x 2 ⎪ −x 4 = 6 ⎪ ⎪ ⎪ −2x 2 +9x 3 +3x 4 ≥ 4 ⎪ ⎨ ⎪5x 1 +x 2 −7x 3 ⎪ ≤ 2 ⎪ ⎪x i ≥ 0, i = 1,4 ⎪ ⎪ ⎩ khi đó dạng chính tắc của bài toán sẽ là: g(x ) =−2x 1 + 3x 2 − 4x 3 + 5x 4 → min ⎧ x 1 +x 2 ⎪ −x 4 = 6 ⎪ ⎪ ⎪ −2x 2 +9x 3 +3x 4 −x 5 = 4 ⎪ ⎨ ⎪5x 1 +x 2 −7x 3 ⎪ +x 6 = 2 ⎪ ⎪x i ≥ 0, i = 1,6 ⎪ ⎪ ⎩ dạng chuẩn tắc là: g(x ) =−2x 1 + 3x 2 − 4x 3 + 5x 4 → min ⎧ x 1 +x 2 ⎪ −x 4 ≥ 6 ⎪ ⎪ ⎪ ⎪ −2x 2 +9x 3 +3x 4 ≥ 4 ⎪ ⎪−5x 1 −x 2 +7x 3 ⎨ ≥ −2 ⎪ ⎪ −x 1 −x 2 ⎪ +x 4 ≥ −6 ⎪ ⎪ ⎪x i ≥ 0, i = 1,4 ⎪ ⎩ Khoa Công nghệ thông tin - ĐHTN 8
  10. Thân Quang Khoát §3. MỘT SỐ KIẾN THỨC BỔ TRỢ 3.1. Tập hợp lồi và điểm cực biên 3.1.1. Tập hợp lồi (convex set) Đoạn thẳng: cho hai điểm a, b ∈ℜn khi đó đoạn thẳng nối hai điểm đó là tập hợp điểm có dạng {x ∈ℜ n x = λa +(1−λ)b, λ ∈[0,1]} . Nếu λ ∈ℜ thì ta sẽ có đường thẳng đi qua hai điểm a,b . Tập lồi: Tập C ⊂ℜn được gọi là tập lồi nếu lấy hai điểm bất kỳ x 1, x 2 ∈C thì đoạn thẳng nối hai điểm này thuộc hoàn toàn trong C . Hoặc ta có thể phát biểu như sau: C lµ tËp låi ⇔ ∀x 1, x 2 ∈C , ∀λ ∈ ⎡⎢0; 1⎤⎥ th× x = λx 1 +(1−λ)x 2 ∈C ⎣ ⎦ Các tập lồi Ví dụ: Trong không gian 2 chiều thì các đa giác, các hình tròn, các hình elip,… là các tập lồi. Các siêu phẳng H = {x ∈ℜn ∑n=1cix i = β} cũng là một tập lồi trong ℜn i Các nửa không gian H = {x ∈ℜn ∑n=1cix i ≥ β} là các tập lồi trong ℜn i Bổ đề: Giao của các tập lồi cũng là một tập lồi. 3.1.2. Điểm cực biên (vertex) Điểm cực biên: điểm x 0 thuộc tập lồi C được gọi là điểm cực biên của C nếu nó không là điểm trong của bất kỳ đoạn thẳng nào nối hai điểm khác nhau thuộc C . Tức là, ∃x 1, x 2 ∈C , x 1 ≠ x 2 : x 0 = αx 1 +(1−α)x 2 với α ∈ ⎡⎢0; 1⎤⎥ . ⎣ ⎦ Ví dụ: C là đa giác lồi trong ℜ2 thì các đỉnh của nó chính là các điểm cực biên, các điểm khác đều không là điểm cực biên. Tất cả các điểm trên đường tròn là Bộ môn Khoa Học Cơ Bản 9
  11. Bài Giảng môn Tối Ưu Hoá điểm cực biên của hình tròn đó. * Chú ý: - Cần phân biệt Điểm biên và Điểm Cực biên. Ví dụ các đỉnh của một tam giác là điểm cực biên, còn các điểm trên các cạnh là các điểm biên. - Có những tập lồi không có điểm cực biên, chẳng hạn: các nửa không gian, một mặt phẳng,… 3.2. Đa diện lồi (polytope) 3.2.1. Tổ hợp lồi (convex combinatorial) Định nghĩa: Một tổ hợp lồi của các điểm x i ∈ℜn (i = 1,m) là điểm x ∈ℜn có dạng x = α1x 1 + α2x 2 +...+ αmx m trong đó αi ≥ 0 (i = 1,m) và ∑m 1 αi = 1 . i= Như vậy nếu ta có 2 điểm A, B thì mọi điểm nằm trên đoạn thẳng nối hai điểm đó sẽ là tổ hợp lồi của hai điểm A và B. Định lý sau đây sẽ cho ta biết được một tập khi nào là một tập lồi. Định lý: Tập C là tập lồi khi và chỉ khi ∀x i ∈C , ∀αi ≥ 0 (i = 1,m) , ∑m 1 αi = 1 i= thì ∑m 1 αix i ∈C . i= Bổ đề: Tập hợp M gồm mọi tổ hợp lồi của hữu hạn các điểm cho trước là một tập lồi. 3.2.2. Đa diện lồi Định nghĩa: Tập hợp M gồm mọi tổ hợp lồi của một số hữu hạn điểm cho trước x 1, x 2,..., x m được gọi là một đa diện lồi sinh bởi hệ điểm đã cho. Ký hiệu: M = conv {x 1, x 2,..., x m} Như vậy ta thấy đa diện lồi là một tập hợp lồi. Tuy nhiên không phải tập lồi nào cũng là đa diện lồi, chẳng hạn hình tròn là tập lồi nhưng không là đa diện lồi. Ví dụ: Đoạn thẳng nối hai điểm A và B là một đa diện lồi. Đa diện lồi sinh bởi 3 điểm A, B, C trên mặt phẳng là một tam giác. Ba điểm A, B, C là các điểm cực biên của đa diện lồi này. Định lý: Nếu M là một đa diện lồi thì nó có điểm cực biên. Số điểm cực biên của M Khoa Công nghệ thông tin - ĐHTN 10
  12. Thân Quang Khoát là hữu hạn và mọi điểm của M đều là các tổ hợp lồi của các điểm cực biên đó. Như vậy định lý này cho chúng ta biết được một tính chất quan trọng của đa diện lồi, đó là số đỉnh cực biên của một đa diện lồi cho trước là hữu hạn. Về mặt hình học ta thấy, đa diện lồi là một tập lồi và là giao của một số các nửa không gian đóng trong ℜn . Tuy nhiên điều ngược lại chưa chắc đúng. Vậy thì làm thế nào để biết được phần giao của các nửa không gian đóng trong ℜn là một đa diện lồi ? Hai nhà toán học là Hoàng Tụy và Asmanov sẽ trả lời cho chúng ta bằng định lý sau đây: Định lý: Xét tập M = {x ∈ℜn Ax ≥b} trong đó A là ma trận cấp m ×n , b ∈ℜm . Nếu M ≠ φ và giới nội thì M là một đa diện lồi. §4. CẤU TRÚC MIỀN RÀNG BUỘC CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 4.1. Phương án cực biên và phương án cực biên tối ưu Không mất tổng quát ta xét bài toán QHTT dạng chính tắc như sau: f (x ) = c tx → Min ⎧Ax = b ⎪ (I) ⎪ ⎨ ⎪x ≥ 0 ⎪ ⎩ Ký hiệu: D = {x ∈ℜn Ax = b, x ≥ 0} Đặt: ⎛A ⎞ ⎛b ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎟, b = ⎜−b⎟ ⎜−A⎟ E ⎜ ⎟ AE = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎟ ⎜ ⎟ ⎝ ⎟ ⎜E ⎠ ⎝ ⎟ ⎜0 ⎠ khi đó ta có: D = {x ∈ℜn AEx ≥bE } Phương án cực biên: Phương án x 0 ∈ D được gọi là phương án cực biên của bài toán (I) nếu x 0 là điểm cực biên của D . Bộ môn Khoa Học Cơ Bản 11
  13. Bài Giảng môn Tối Ưu Hoá Phương án cực biên tối ưu: Nếu phương án cực biên x 0 là phương án tối ưu của bài toán (I) thì x 0 được gọi là phương án cực biên tối ưu của bài toán (I). Người ta đã chứng minh được định lý sau đây: Định lý: Xét tập G = {x ∈ℜn Ax ≥b} , Giả sử G ≠ φ . Khi đó G có điểm cực biên khi và chỉ khi rank(A) = n . Đặc biệt hơn, nếu G ≠ φ thì ∀x ∈G đều có thể được viết dưới dạng x = ∑m 1 αix i + ∑k=1 β jy j trong đó x i (i = 1,m) là các điểm i= j cực biên của G ; αi ≥ 0, ∑im 1 αi = 1, Ay j ≥ 0, β j ≥ 0 (j = 1,k ) . = Áp dụng định lý đối với miền ràng buộc D thì ta có: Do rank(AE ) = n nên theo định lý, nếu D ≠ φ (tức là bài toán (I) có phương án) thì D có đỉnh cực biên (bài toán (I) có phương án cực biên). Hơn nữa ta có kết quả sau: Hệ quả: xét miền D = {x ∈ℜn Ax =b, x ≥ 0} , A = (aij )m×n,b ∈ℜm . Khi đó nếu D ≠ φ thì nó có điểm cực biên và mọi điểm x ∈ D luôn tồn tại biểu diễn x = ∑ip=1 αix i + ∑k=1 β jy j trong đó x i (i = 1, p) là các điểm cực biên của D ; j αi ≥ 0, ∑ip=1 αi = 1, Ay j = 0, β j ≥ 0 (j = 1,k ) . Chứng minh: Ta viết lại D dưới dạng D = {x ∈ℜn AE x ≥bE } . Do rank(AE ) = n nên theo định lý, nếu D ≠ φ thì D có đỉnh cực biên. Cũng theo định lý thì mọi điểm x ∈ D luôn tồn tại biểu diễn x = ∑ip=1 αix i +∑k=1 β jy j trong đó x i (i = 1, p) là các điểm cực biên của D ; αi ≥ 0, ∑ip=1 αi = 1 , j AEy j ≥ 0, β j ≥ 0 (j = 1,k ) . Từ AEy j ≥ 0 ta có ngay Ay j ≥ 0, −Ay j ≥ 0 và do đó Ay j = 0 . Vậy ta có điều phải chứng minh. ■ Bây giờ ta sẽ dùng hệ quả này để chứng minh kết quả sau cho bài toán (I). Định lý: Nếu bài toán (I) có phương án thì sẽ có phương án cực biên, và nếu hàm mục tiêu bị chặn dưới trong D thì bài toán sẽ có phương án tối ưu, do đó có phương án cực biên tối ưu. Chứng minh: Rõ ràng theo hệ quả trên ta có: nếu bài toán (I) có phương án thì nó sẽ có Khoa Công nghệ thông tin - ĐHTN 12
  14. Thân Quang Khoát phương án cực biên. Bây giờ ta giả thiết rằng (I) có hàm mục tiêu bị chặn dưới trong D . Khi đó bài toán (I) sẽ có phương án cực biên tối ưu. Thật vậy: Theo hệ quả thì mọi phương án x của (I) đều có thể viết dưới dạng: x = ∑im 1 αix i + ∑k=1 β jy j , trong đó x i (i = 1,m) là các điểm cực biên của D ; = j αi ≥ 0, ∑m 1 αi = 1, Ay j = 0, β j ≥ 0 (j = 1,k ) . i= Gọi f (x r ) = min{f (x i ), i = 1,m} . Ta sẽ chứng minh rằng x r sẽ là phương án tối ưu của bài toán (I). a) Trước hết ta thấy rằng f (y i ) ≥ 0, ∀i = 1,k : Thật vậy, giả sử tồn tại j 0 mà f (y j0 ) < 0 thì nếu ta lấy β j = 0, ∀j ≠ j 0 còn β j0 → +∞ thì f (x ) = ∑im 1 αi f (x i )+ β j0 .f (y j0 ) → −∞ . Điều này trái với giả thiết = hàm mục tiêu bị chặn dưới trên miền ràng buộc D . b) ∀x ∈ D thì: f (x ) = ∑im 1 αi f (x i )+ ∑k=1 β j f (y j ) = j ≥ ∑im 1 αi f (x i ) = ≥ ∑im 1 αi f (x r ) = f (x r )∑im 1 αi = f (x r ) = = Vậy f (x ) ≥ f (x r ), ∀x ∈ D , hay x r là phương án tối ưu của bài toán (I). Do đó ta đi đến kết luận của hệ quả này. ■ 4.2. Điều kiện cần và đủ để một phương án là cực biên Xét bài toán QHTT dạng chính tắc (I). Ký hiệu a 1, a 2,..., a n là các véctơ cột của ma trận ràng buộc ⎛a11 a12 ... a1n ⎞ ⎟ ⎜ ⎜ ⎟ ⎜a ⎟ ⎜ A = ⎜ 21 ⎜ a22 ... a2n ⎟ ⎟ ⎟ ⎟ ⎜ ... ... ⎜ ... ... ⎟ ⎟ ⎜ ⎜ ⎟ ⎟ ⎝am1 am2 ... amn ⎠ Không mất tổng quát ta luôn giả thiết rank(A) = rank {a 1, a 2,..., a n} = m Bộ môn Khoa Học Cơ Bản 13
  15. Bài Giảng môn Tối Ưu Hoá (nếu có phương trình nào trong hệ Ax = b là tổ hợp tuyến tính của các phương trình khác thì ta có thể loại bỏ đi). Khi đó ta có định lý sau: Định lý: Phương án x 0 ∈ D là một phương án cực biên khi và chỉ khi hệ các véctơ cột của ma trận A tương ứng với các thành phần dương của x 0 độc lập tuyến tính. Ký hiệu: J +(x 0) = {j |x j0 > 0} Khi đó định lý có thể phát biểu như sau: x 0 ∈ D là phương án cực biên ⇔ {a j, j ∈J +(x 0)} độc lập tuyến tính. Chứng minh: Không mất tổng quát ta có thể giả thiết J (x 0) = {1,2,...,k} (có thể đánh lại chỉ số các biến nếu cần thiết để thu được điều kiện này). “Điều kiện cần”: giả thiết x 0 ∈ D là một phương án cực biên của (I). Giả sử hệ vectơ {a j, j ∈J +(x 0)} = {a 1,a 2,...,a k } phụ thuộc tuyến tính. Khi đó tồn tại các số z1, z 2,..., z k không đồng thời bằng 0 để z1a 1 +...+ z ka k = θ . Đặt z = (z1,..., z k,0,...,0)t ∈ℜn . Khi đó ta có: Az = θ Xét hai vectơ x ' = x 0 −λz và x '' = x 0 +λz . Khi đó Ax ' = Ax '' = Ax 0 = b (do Az = θ ). Nếu ta lấy λ đủ bé sao cho x ' ≥ 0, x '' ≥ 0 (luôn lấy được λ vì z ≠ θ ) thì ta có x ' ∈ D, x '' ∈ D . Mà ta lại có x 0 = 1 x '+ 1 x '' , trái với giả thiết x 0 là phương án 2 2 cực biên của (I). Vậy hệ {a 1,a 2,...,a k } độc lập tuyến tính. “Điều kiện đủ”: giả thiết hệ {a 1,a 2,...,a k } độc lập tuyến tính. Giả sử x0 không là phương án cực biên của (I). Khi đó ∃x ′, x ′′ ∈ D, x ′ ≠ x ′′ sao cho x 0 = 1 x ′ + 1 x ′′ . Dễ dàng thấy rằng (n −k ) thành phần cuối cùng của x′ 2 2 và x ′′ cũng bằng 0, còn các thành phần khác là không âm. Vậy ta có: Ax 0 = ∑n=1 x j0a j = ∑k=1 x j0a j = b j j Ax ′ = ∑n=1 x ′a j = ∑k=1 x ′a j = b j j j j Khoa Công nghệ thông tin - ĐHTN 14
  16. Thân Quang Khoát Ax ′′ = ∑n=1 x ′′ j = ∑k=1 x ′′ j =b j ja j ja k k k ⇒ ∑ j =1 x j0a j = ∑ j =1 x ′a j = ∑ j =1 x ′a j j j′ nhưng do hệ {a 1,a 2,...,a k } độc lập tuyến tính nên x j0 = x ′ = x ′′, (j = 1,k ) . Mà theo j j nhận xét trên thì x j0 = x ′ = x ′′= 0, (j = k +1,n) . Vậy ta có x 0 = x ′ = x ′′ . Điều này j j mâu thuẫn với giả thiết x ′ ≠ x ′′ . Do đó x 0 là phương án cực biên. ■ Ví dụ: xét miền D được xác định như sau ⎧3x 1 + x 2 + 2x 3 ⎪ =5 ⎪ ⎪ ⎪2x 1 + x 2 + 3x 3 ⎪ =5 ⎪ ⎨2x ⎪ 1 + x 3 + 2x 4 = 9 ⎪ ⎪ ⎪x ≥ 0, i = 1,4 ⎪ i ⎪ ⎩ Ta thấy x 0 = (1; 0; 1; 3)t là một phương án của D. Có J +(x 0) = {1; 3; 4} và các véctơ cột {a j | j ∈J +(x 0)} tương ứng là: a 1 = (3, 2, 2)t, a 3 = (2, 3, 1)t, a 4 = (0, 0, 2)t chúng lập thành hệ độc lập tuyến tính. Vậy x 0 = (1; 0; 1; 3)t là một phương án cực biên. Dễ dàng kiểm tra được rằng vectơ x 1 = (0;5;0; 92)t cũng là một phương án cực biên. Tuy nhiên x = (5 ; 15 ; 5 ; 47)t là một phương án của bài toán, nhưng lại 8 8 8 16 không là phương án cực biên của nó. 4.3. Cơ sở của một phương án cực biên Giả sử x 0 ∈ D = {x ∈ℜn Ax = b, x ≥ 0} là một phương án cực biên, rank(A) = m , Card (J +(x 0)) = k (số thành phần dương của x 0 là k ). Khi đó hệ {a j, j ∈J +(x 0)} là độc lập tuyến tính, suy ra k ≤ m . Nếu k < m thì ta luôn có thể bổ xung thêm (m −k ) véctơ cột khác của A để được một hệ véctơ độc lập tuyến tính cực đại gồm đủ m véctơ, nghĩa là ta tìm được tập gồm đủ m chỉ số J = {j1, j2, ..., jm}, J ⊃ J +(x 0) sao cho hệ {a j : j ∈J } là độc lập tuyến tính. Còn nếu k = m thì ta đặt J = J +(x 0) . Bộ môn Khoa Học Cơ Bản 15
  17. Bài Giảng môn Tối Ưu Hoá Cơ sở của phương án cực biên: ta gọi hệ véctơ {a j : j ∈J } nói trên là một cơ sở của phương án cực biên x 0 . Đôi khi ta còn gọi tắt J là cơ sở của x 0 . Định nghĩa: một phương án cực biên x 0 là không suy biến nếu có đúng m thành phần dương, tức là Card (J +(x 0)) = m . Ngược lại thì gọi là suy biến. Ví dụ: Đối với ví dụ trên thì rank(A) = 3 . - Phương án cực biên x 0 = (1; 0; 1; 3)t có cơ sở là J = J +(x 0) = {1; 3; 4} . Do đó nó là phương án cực biên không suy biến. - Phương án cực biên x 1 = (0;5;0; 92)t có J +(x 1) = {2; 4} nên nó là phương án cực biên suy biến. Ta có thể lấy một cơ sở của nó là J = J +(x 1)∪{3} = {2; 4; 3} . Bài toán QHTT gọi là không suy biến nếu mọi phương án cực biên của nó không suy biến. Rõ ràng là nếu một phương án là không suy biến thì nó chỉ có một cơ sở duy nhất. Như vậy nếu bài toán QHTT là không suy biến thì số cơ sở nhiều nhất là C n (vì lấy m véctơ từ n véctơ), do đó số phương án cực biên của m bài toán QHTT nhiều nhất cũng chỉ là C n . Vậy số các phương án cực biên là m hữu hạn. Khoa Công nghệ thông tin - ĐHTN 16
  18. Thân Quang Khoát Chương 2. THUẬT TOÁN ĐƠN HÌNH §1. MỞ ĐẦU 1.1. Bài toán Ta xét bài toán QHTT dạng chính tắc sau: f (x ) = c tx → Min ⎧Ax = b ⎪ (I) ⎪ ⎨ ⎪x ≥ 0 ⎪ ⎩ trong đó c, x ∈ℜn, b ∈ℜm, A lµ ma trËn cÊp m×n Hiện nay đã có rất nhiều các thuật toán khác nhau giải bài toán (I). Ta có thể liệt kê ra một số như sau: - Thuật toán đơn hình (do Dantzig đề xuất). - Các phương pháp điểm trong (do Karmarkar đề xuất). - Các phương pháp Ellipsoid (do Khachian đề xuất). Trong đó các phương pháp Điểm trong và phương pháp Ellipsoid là các phương pháp có độ phức tạp tính toán là đa thức, còn phương pháp Đơn hình thì không. Tuy nhiên trong thực tế tính toán thì người ta thấy rằng, phương pháp đơn hình là rất hiệu quả, đồng thời nó cũng là thuật toán dễ hiểu và dễ thực hiện. Một trường hợp đặc biệt là khi chúng ta xét những bài toán QHTT trong không gian 2 chiều hoặc 3 chiều thì chúng ta có thể dùng phương pháp hình học khá hữu hiệu để giải. 1.2. Phương pháp Hình Học Ta xét trong không gian 2 chiều với bài toán dạng chuẩn tắc: f (x ) = c1x 1 +c2x 2 → Min với các điều kiện: ai1x 1 +ai2x 2 ≥bi , i = 1,m Ký hiệu: D = {x = (x 1, x 2) ai1x 1 +ai2x 2 ≥bi , i = 1,m} Ta biết rằng mỗi một bất phương trình tuyến tính ai1x 1 +ai2x 2 ≥bi xác định Bộ môn Khoa Học Cơ Bản 17
  19. Bài Giảng môn Tối Ưu Hoá một nửa mặt phẳng. Như vậy tập D là giao của m nửa mặt phẳng sẽ là một đa giác lồi trên mặt phẳng. Phương trình c1x 1 +c2x 2 = α khi α thay đổi sẽ xác định trên mặt phẳng các đường thẳng song song với nhau. Định nghĩa: Với mỗi một giá trị của α thì đường thẳng c1x 1 +c2x 2 = α được gọi là một đường mức. Với mỗi điểm x = (x 1, x 2) ∈ D sẽ nằm trên đường mức có giá trị mức là c1x 1 +c2x 2 = α . Như vậy bài toán đặt ra có thể phát biểu như sau: Trong số các đường mức cắt tập D , hãy tìm đường mức có giá trị mức α nhỏ nhất. Ta thấy rằng nếu dịch chuyển các đường mức song song các đường mức theo hướng véctơ pháp tuyến của chúng c = (c1, c2) thì giá trị của mức sẽ tăng, nếu dịch chuyển theo hướng ngược lại thì giá trị mức sẽ giảm. Vì vậy chúng ta có thể giải bài toán đặt ra theo cách như sau: Bắt đầu từ một đường mức cắt D , ta dịch chuyển đường mức theo hướng ngược với hướng véctơ c = (c1, c2) cho đến khi nào việc dịch chuyển tiếp theo làm cho đường mức không cắt D nữa thì dừng. Các điểm của D nằm trên đường mức này sẽ là các lời giải cần tìm, còn giá trị mức chính là giá trị tối ưu của bài toán. Ví dụ: Giải bài toán QHTT sau f (x ) = x 1 −x 2 → min ⎧−x 1 −x 2 ≥−7 ⎪ (1) ⎪ ⎪ ⎪−x 1 + x 2 ≥−2 ⎪ (2) (D) ⎪ ⎨ ⎪2x 1 + x 2 ≥ 2 ⎪ (3) ⎪ ⎪x ≥ 0, x ≥ 0 ⎪1 ⎪ ⎩ 2 Để giải bài toán này bằng phương pháp hình học thì trước tiên ta phải biểu diễn miền D trên mặt phẳng toạ độ. Sau đó ta xác định một đường mức cắt miền D, chẳng hạn: x 1 −x 2 = 0 . Cuối cùng ta sẽ dịch chuyển đường mức theo hướng giảm (dựa vào véctơ pháp tuyến c = (1,−1) ) để tìm ra đường mức có mức nhỏ nhất cắt miền D. Khoa Công nghệ thông tin - ĐHTN 18
  20. Thân Quang Khoát x2 x1 Ta thấy miền D của bài toán chính là đa giác ABIJK. Khi dịch chuyển đường mức theo hướng véctơ −c thì điểm I chính là điểm cuối cùng mà đường mức cắt miền D. Vì vậy I chính là điểm cực biên tối ưu. Do I là giao điểm của đường thẳng (1) với Ox 2 nên toạ độ điểm I chính là nghiệm của hệ pt: ⎧−x 1 −x 2 =−7 ⎧x 1 = 0 ⎪ ⎪ ⎪ ⎨ ⇒⎪ ⎨ ⎪x 1 = 0 ⎪ ⎪x 2 = 7 ⎪ ⎩ ⎩ Vậy x * = (0; 7) là phương án tối ưu và f (x *) =− 7 §2. THUẬT TOÁN ĐƠN HÌNH 2.1. Tư tưởng của thuật toán đơn hình Xét bài toán QHTT dạng chính tắc: f (x ) = c tx → Min ⎧Ax = b ⎪ (I) ⎪ ⎨ ⎪x ≥ 0 ⎪ ⎩ Bộ môn Khoa Học Cơ Bản 19
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
3=>0