chương 1 trình bày mô hình tổng quát của bài toán quy hoạch tuyến tính, các thuật toán: Hình học, đơn hình, đơn hình mở rộng, và phương pháp giải bài toán quy hoạch tuyến tính tổng quát trên phần mềm MATLAB. Các kết quả là những kiến thức quan trọng được ứng dụng trong các chương sau của luận văn. Các kiến thức được tham khảo trong các tài liệu [1, 2].1 Mô hình tổng quát của bài toán quy hoạch tuyến tính 1.1 Mô hình tổng quát Tối ưu hóa là một trong những lĩnh vực quan trọng của toán học có ảnh hưởng đến hầu hết các lĩnh vực khoa học, công nghệ và kinh tế và xã hội. Việc tìm giải pháp tối ưu cho một bài toán thực tế nào đó chiếm một vai trò hết sức quan trọng như việc tiến hành lập kế hoạch sản xuất hay thiết kế hệ thống điều khiển các quá trình.
Nếu sử dụng các kiến thức trên nền tảng của toán học để giải quyết các bài toán cực trị, người ta sẽ đạt được hiệu quả kinh tế cao. Điều này phù hợp với mục đích của các vấn đề đặt ra trong thực tế hiện nay. Bài toán tối ưu tổng quát được phát biểu như sau: Cực đại hóa (cực tiểu hóa) hàm: f (X) → max(min) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 Với các điều kiện: gi (X) = bi , i ∈ J1 ; (1.4) Trong đó f (X) được gọi là hàm mục tiêu.1) được gọi là ràng buộc đẳng thức.3) được gọi là ràng buộc bất đẳng thức.4) được gọi là ràng buộc về dấu., xn ) là vectơ thuộc không gian Rn. Tập các vectơ X thỏa mãn hệ ràng buộc lập nên một miền D được gọi là miền phương án (hay miền chấp nhận được), mỗi điểm X ∈ D gọi là một phương án.
Một phương án X ∗ ∈ D làm cho hàm mục tiêu f (X) đạt max (min) được gọi là phương án tối ưu.2 Phân loại bài toán tối ưu Dựa trên mô hình tổng quát, người ta thường phân loại lớp các bài toán tối ưu như sau: • Qui hoạch tuyến tính: là những bài toán mà hàm mục tiêu f (X)và tất cả các hàm ràng buộc gi (X), gj (X), gk (X) là tuyến tính. • Qui hoạch phi tuyến: là những bài toán một trong hàm mục tiêu f (X) hoặc các hàm ràng buộc gi (X) , gj (X) , gk (X) là phi tuyến. • Qui hoạch lồi: Là các bài toán qui hoạch mà các hàm mục tiêu f (X) là lồi trên tập các ràng buộc D lồi. • Qui hoạch lõm: Là các bài toán qui hoạch mà các hàm mục tiêu f (X) là lõm trên tập các ràng buộc D lõm.
• Qui hoạch rời rạc: Bài toán tối ưu được gọi là qui hoạch rời rạc nếu miền ràng buộc D là tập hợp rời rạc. Trong trường hợp riêng khi các biến chỉ nhận giá trị nguyên thì ta có qui hoạch nguyên. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 • Qui hoạch đa mục tiêu: Nếu trên cùng một miền ràng buộc ta xét đồng thời các hàm mục tiêu khác nhau. • Trong các lĩnh vực kinh tế kỹ thuật thì qui hoạch phi tuyến, qui hoạch tuyến tính là những bài toán thường gặp.2 Bài toán quy hoạch tuyến tính Từ một số các mô hình trong thực tế, ta có mô hình tổng quát cho bài toán quy hoạch tuyến tính như sau: Xác định các biến xj (j = 1, 2, .5) j=1 n X aij xj = bi (i ∈ I2 = M \I1 ) ; (1.6) j=1 lbj ≤ xj ≤ ubj , (j ∈ J ⊂ N )., xn ) thỏa mãn các điều kiện (1.7) được gọi là một phương án của bài toán.
Tập các nghiệm thỏa mãn hệ ràng buộc được gọi là miền phương án, ký hiệu là D. Phương án thỏa mãn điều kiện để hàm mục tiêu đạt max (min) được gọi là phương án tối ưu. Dạng chính tắc: n X F (x) = cj xj → min; j=1 n X aij xj = bi (i ∈ M ) ; j=1 xj ≥ 0(j ∈ N ). LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 Dạng chuẩn tắc: n X F (x) = cj xj → min; j=1 n X aij xj ≥ bi (i ∈ M ) ; j=1 xj ≥ 0(j ∈ N ).
Sử dụng các ký hiệu vectơ và ma trận, mô hình bài toán quy hoạch tuyến tính tổng quát được biểu diễn như sau: f (X) = C T X → max(min); AX = b, AX ≥ b; lb ≤ X ≤ ub. amn xn m1 m2 mn m1 m2 b1 b1 lb1 ub1 b2 b2 lb2 ub2 b=. bm bm lbn ubn Một số phép biến đổi cơ bản: a/ Nếu hàm mục tiêu dạng max thì có thể chuyển về dạng min bằng cách đổi dấu hàm mục tiêu. b/ Một ràng buộc bất đẳng thức có thể chuyển về ràng buộc đẳng thức bằng cách thêm các ẩn giả với hệ số tương ứng bằng 0 trong hàm mục tiêu.
c/ Một biến không ràng buộc dấu được thay thế bằng 2 biến có ràng buộc dấu. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Một số phương pháp giải cơ bản 1.1 Thuật toán hình học Xét bài toán: f (x1 , x2 ) = c1 x1 + c2 x2 → M ax; a11 x1 + a12 x2 ≤ b1 ; a21 x1 + a22 x2 ≤ b2 ;. an1 x1 + an2 x2 ≤ bn ; x1 ≥ 0; x2 ≥ 0. Vì các ràng buộc của bài toán luôn luôn là các nửa mặt phẳng, do đó miền phương án luôn luôn là một đa giác lồi (là giao của các nửa mặt phẳng).
Xét đường thẳng f = m được gọi là đường mức. Hiển nhiên khi đường mức chuyển động song song trong miền phương án thì điểm chạm cuối cùng của đường mức với miền luôn luôn là 1 trong các đỉnh của đa giác (Hoặc 1 cạnh của đa giác). Đấy chính là phương án tối ưu cần tìm. Xuất phát từ nhận xét trên, chúng ta có thuật toán hình học gồm các bước như sau : Thuật toán: Bước 1: Vẽ miền phương án D là đa giác lồi bằng cách xác định miền giao của các nửa mặt phẳng trong hệ ràng buộc.
Bước 2: Xác định tọa độ của các đỉnh đa giác: Giả sử là các điểm A1 , A2 ,. Bước 3: Xác định phương án tối ưu fmax = max{f (A1 ), f (A2 ), .2 Trong trường hợp khi miền phương án không phải là miền kín thì tùy thuộc vào hướng di chuyển của đường mức, chúng ta sẽ xác định được phương án tối ưu của bài toán. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Thuật toán đơn hình Mô tả thuật toán gốc Cơ sở của phương pháp này được Dantzig công bố năm 1947 có tên gọi là phương pháp đơn hình. Xuất xứ tên gọi như vậy vì những bài toán đầu tiên được giải bằng phương pháp đó có các ràng buộc dạng: n X xj = 1, xj > 0 (j = 1, 2,.
j=1 Mà tập các điểm thoả mãn các ràng buộc trên là một đơn hình trong không gian n chiều. Tư tưởng chung Phương pháp đơn hình dựa trên hai nhận xét sau: • Nếu bài toán QHTT có phương án tối ưu thì có ít nhất một đỉnh của D là phương án tối ưu. • Đa diện lồi D có một số hữu hạn đỉnh. Như vậy phải tồn tại một thuật toán hữu hạn.
Thuật toán gồm 2 bước như sau: Bước 1: Tìm 1 phương án cực biên. Bước 2: Kiểm tra điều kiện tối ưu đối với phương án đó. + Nếu điều kiện tối ưu được thoả mãn thì phương án đó là tối ưu, nếu không ta chuyển sang phương án cực biên mới sao cho làm tốt hơn giá trị hàm mục tiêu. + Kiểm tra điều kiện tối ưu đối với phương án mới.
Người ta thực hiện một dãy các thủ tục như vậy cho đến khi nhận được phương án tối ưu, hoặc đến tình huống bài toán không có phương án tối ưu. Cơ sở lý thuyết Xét bài toán QHTT dưới dạng chính tắc: f (x) = C T X ⇒ min. LUAN VAN CHAT LUONG download : add luanvanchat@agmail., cn ), giả sử rằng hạng của ma trận A là m. Giả sử X là một phương án cực biên nào đó.
Ta ký hiệu: J ∗ = {j|xj > 0} (1. Vì các vectơ Aj , j ∈ J ∗ là độc lập tuyến tính nên |J ∗ | ≤ m.3 Phương án cực biên X được gọi là không suy biến nếu |J ∗ | = m, suy biến nếu |J ∗ | < m. Ta chọn một hệ thống m vectơ độc lập tuyến tính {Aj , j ∈ J} sao cho J ⊇ J ∗. Hệ thống đó là cơ sở của X , các vectơ Aj , j ∈ J và biến xj , j ∈ J được gọi là các vectơ và các biến cơ sở tương ứng.
Các vectơ và các biến Aj , xj , (j ∈ / J) gọi là các vectơ và các biến phi cơ sở. Nếu X không suy biến thì tồn tại một cơ sở duy nhất, đó là J = J ∗. Mọi vectơ Ak phi cơ sở có thể biểu diễn dưới dạng tổ hợp tuyến tính của các vectơ cơ sở: X Ak = zjk Aj .9) j∈J Trong các hệ số zjk được xác định duy nhất bởi việc giải hệ phương trình: X ajk = zjk aij , (i = 1, 2, .10) j∈J Bài toán QHTT được gọi là không suy biến nếu tất cả các phương án cực biên của nó đều không suy biến. Giả sử bài toán không suy biến và ta đã tìm được một phương án cực biên X = (x1 , x2 , ., 0) và cơ sở của nó A1 , A2 ,.
Đối với phương án cực biên này ta có: m X xj Aj = b, xj > 0, (j = 1, 2, .11) j=1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Với giá trị hàm mục tiêu: m X cj xj = z0 , xj > 0, (j = 1, 2, .12) j=1 Ta tính các đại lượng sau: m X zjk cj = zk .13) j=1 Ký hiệu: m X ∆k = zk − ck = zjk cj − ck .4 Nếu đối với các phương án cực biên X = (x1 , x2 , ., 0) mà các điều kiện sau được thỏa mãn: ∆k ≥ 0, ∀k = 1, 2, .15) thì X là phương án tối ưu.9) nếu Aj là một vectơ cơ sở khi đó tồn tại chỉ một hệ số zij = 1, tất cả các hệ số khác đều bằng 0 và ta có: ∆j = cj − cj = 0, j ∈ J.