Bài toán qui hoạch tuyến tính đa mục tiêu

áp đơn hình giải bài toán qui hoạch tuyến tính…....................16 Mô hình toán học……………………………………….................16 Mô tả hình học của phương pháp đơn hình……………..................18 Nghiệm cơ sở và phương án cực biên..............................................18 Thuật toán đơn hình…………………………………….................19 Công thức đổi cơ sở và bảng đơn hình……………….....................26 Vấn đề cơ sở cực biên và cơ sở xuất phát………...…….................28 Đối ngẫu của qui hoạch tuyến tính..................................................29 1.3 Kết luận ...................................................................................................33 Chương II. Bài toán qui hoạch tuyến tính đa mục tiêu. 2.1 Thế nào là bài toán tối ưu đa mục tiêu………………………..................34 2.2 Mô hình toán học và cấu trúc tập nghiệm…………………….................39 2.2.1 Không gian với thứ tự từng phần………………………...................40 2.2.2 Nghiệm hữu hiệu, nghiệm hữu hiệu yếu……………..….................41 2.3 Lý do giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị .........................................................................................................................42 2.4 Kết luận.....................................................................................................43 Chương III. Bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị. 3.1 Tương đương hữu hiệu………………………………………...................45 3.2 Cơ sở lý thuyết...........................................................................................47 3.2.1 Phương pháp xấp xỉ ngoài…………………………….....................48 3.2.2 Bài toán tìm đỉnh của tập lồi đa diện………………….....................51 3.2.3 Phương pháp phân hoạch đa diện thành các đơn hình…..................60 3.3 Thuật toán xấp xỉ ngoài…………………………………….....................72 3.4 Kết luận ....................................................................................................75 Kết luận chung……………………………………………………................76 Phụ lục………………………………………………………………...............77 Tài liệu trích dẫn...……………………………………………..................109 Mở đầu Trong những năm gần đây, các phương pháp tối ưu hoá ngày càng được áp dụng sâu rộng và hiệu quả vào các nghành kinh tế, kỹ thuật, công nghệ thông tin và các nghành khoa học khác. Các phương pháp tối ưu là công cụ đắc lực giúp người làm quyết định có những giải pháp tốt nhất về định lượng và định tính. Một trong những lớp bài toán tối ưu đầu tiên được ngiên cứu trọn vẹn cả về lý thuyết lẫn thuật toán là bài toán qui hoạch tuyến tính (QHTT). Qui hoạch tuyến tính ngay từ khi ra đời (vào cuối năm 30 của thế kỷ XX) đã chiếm vị trí quan trọng trong tối ưu hoá. Mô hình tuyến tính là mô hình rất phổ biến trong thực tế vì sự phụ phuộc tuyến tính là sự phụ thuộc đơn giản và dễ hiểu nhất. Hơn nữa, về mặt lý thuyết chúng ta biết rằng có thể xấp xỉ với độ chính xác cao các bài toán phi tuyến bởi dãy các bài toán qui hoạch tuyến tính. Nói cách khác, các thuật toán giải QHTT là công cụ quan trọng trong việc nghiên cứu giải các bài toán phức tạp hơn. Thuật toán đơn hình do Dantzig đề xuất từ 1947, đến nay vẫn là một phương pháp được sử dụng rộng rãi. Mặc dù về lý thuyết đây là phương pháp có độ phức tạp mũ. Sau lớp bài toán qui hoạch tuyến tính, nhiều hướng nghiên cứu khác nhau xuất hiện như qui hoạch lồi, qui hoạch toàn cục và lý thuyết điều khiển tối ưu. Bài toán qui hoạch đa mục tiêu cũng mới được phát triển và trở thành một chuyên ngành toán học từ những năm 1950. Giải đáp những câu hỏi đặt ra mà qui hoạch tuyến tính không giải được, chẳng hạn như trong một công ty ngoài việc nâng cao chất lượng sản phẩm thì công ty cũng chú trọng tới đa dạng hoá sản phẩm, già thành rẻ, doanh thu lớn,…Khách hàng khi chọn mua hàng thì muốn hàng rẻ, vừa có chất lượng cao, vừa có hình thức đẹp. Tóm lại, mục đích của bài toán qui hoạch tuyến tính đa mục tiêu là tối ưu đồng thời nhiều hàm mục tiêu độc lập với nhau trên một miền chấp nhận được. Do không gian giá trị của lớp bài toán này không được sắp thứ tự toàn phần, nên khái niệm nghiệm thông thường không còn thích hợp. Trong qui hoạch đa mục tiêu, cùng với khái niệm thứ tự từng phần, ta sẽ sử dụng khái niệm nghiệm hữu hiệu. Một phương án chấp nhận được được gọi là nghiệm hữu hiệu nếu không tồn tại một phương án chấp nhận được khác tốt hơn nó, ít nhất là theo một mục tiêu, còn các mục tiêu khác không tồi hơn. Đầu thế kỷ XX, Pareto đã sử dụng khái niệm này khi ông nghiên cứu phúc lợi và thu nhập của dân chúng. Ông đã lập luận như sau: "Nếu thu nhập của một nhóm dân cư tăng lên, nhưng thu nhập của một nhóm khác giảm xuống thì khi đó không thể so sánh "phúc lợi" của toàn xã hội. Đó là trường hợp không so sánh được. Nhưng có thể thấy rằng, phúc lợi xã hội sẽ tăng lên nếu thu nhập của ít nhất một nhóm người nào đó lớn lên, còn thu nhập của những nhóm khác không thấp xuống". Ta nhận thấy rằng, theo quan điểm của toán học, khái niệm nghiệm hữu hiệu mà chúng ta dùng trong qui hoạch đa mục tiêu phù hợp với luận đề Pareto. Khi hàm mục tiêu đều là hàm tuyến tính và miền ràng buộc là tập lồi đa diện khác rỗng trong , ta nhận được bài toán qui hoạch tuyến tính đa mục tiêu. Cho tới nay, có rất nhiều thuật toán đưa ra để xác định một phần hoặc toàn bộ tập nghiệm hữu hiệu của bài toán, chẳng hạn: phương pháp vô hướng hoá, phương pháp tham số, phương pháp đơn hình đa mục tiêu và các dạng cải biên, phương pháp nón pháp tuyến...(xem [6, 7, 8-9, 12, 17, 19, 21-22, và 24-25]). Tuy nhiên, khối lượng tính toán của các thuật toán này tăng nhanh khi kích thước của bài toán qui hoạch tuyến tính đa mục tiêu (tức số ràng buộc của miền chấp nhận, số chiều của không gian quyết định và số hàm mục tiêu) tăng. Trong những năm gần đây nhiều nhà toán học đã chuyển sang nghiên cứu giải quyết bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị. Trong báo cáo này, em sẽ trình bày thuật toán xấp xỉ ngoài giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị của H.P. Benson, đó là nội dung bài báo: "Hybrid Approach for Solving Multipe-Objective Linear Programs in Outcome Space". Jota: Vol. 98, NO. 1, July, 1998. Trong báo cáo này ngoài phần mục lục, mở đầu, phụ lục và tài liệu trích dẫn còn có 3 chương: Chương I: Một số khái niệm cơ bản về giải tích lồi và bài toán qui hoạch tuyến tính. Chương II: Bài toán qui hoạch tuyến tính đa mục tiêu. Chương III: Bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị. Nội dung các chương như sau: Chương I: Giới thiệu một số kiến thức cơ bản về giải tích lồi để áp dụng cho các phần sau, và phương pháp đơn hình dùng để giải bài toán qui hoạch tuyến tính. Chương II: Giới thiệu tổng quát về bài toán qui hoạch đa mục tiêu: mô hình toán học, khái niệm nghiệm hữu hiệu và hữu hiệu yếu, lý do giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị. Chương III: Giới thiệu thuật toán xấp xỉ ngoài giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị. Chương I Một số khái niệm cơ bản về giải tích lồi và bài toán qui hoạch tuyến tính. Bài toán qui hoạch tuyến tính có vai trò trợ giúp quan trọng trong các bước giải bài toán qui hoạch tuyến tính đa mục tiêu. Trong chương này, trước hết em xin nhắc lại một số khái niệm cơ bản sẽ cần dùng đến trong các phần sau. Phần tiếp của chương dành để trình bày phương pháp đơn hình giải bài toán qui hoạch tuyến tính. 1.1. Một số khái niệm cơ bản 1.1.1-Tập affine * Đường thẳng đi qua 2 điểm là tập hợp tất cả các điểm x trong Rn có dạng . * Một tập M chứa đường thẳng đi qua 2 điểm bất kì của nó thì được gọi là tập affine. * Đoạn thẳng đi qua 2 điểm kí hiệu là , là tập . * Chiều của tập M trùng với chiều của không gian con song song L với nó. * Cho một tập C bất kì, tập affine nhỏ nhất chứa C được gọi là bao affine của C, kí hiệu aff C. * Siêu phẳng là tập có dạng . Ngược lại, tập bất kì có dạng trên là một siêu phẳng. Ví dụ 1.1.1 Trong không gian 2- chiều: siêu phẳng là một đường thẳng, trong không gian 3- chiều: siêu phẳng là một mặt phẳng. * Tập hợp tất cả các điểm thoả mãn bất phương trình tuyến tính: được gọi là nửa không gian đóng. * Nửa không gian được cho bởi: được gọi là nửa không gian mở. 1.1.2- Tập lồi * Một tập A trong không gian Rn được gọi là tập lồi nếu , thì . Nói cách khác, nếu A là tập lồi thì nó chứa đoạn thẳng nối hai điểm bất kì của nó. * Nếu , x=, , thì x được gọi là tổ hợp lồi của . Mệnh đề 1.1.1. Tập là lồi khi và chỉ khi nó chứa tất cả các tổ hợp lồi của các phần tử thuộc A. * Tập MèRn được gọi là một nón với đỉnh a nếu: thì =. Định lý 1.1.1 Tập lồi là đóng với phép giao, phép cộng, phép nhân với một số và phép lấy tổ hợp tuyến tính. Nếu A và B là 2 tập lồi trong Rn thì các tập sau cũng là lồi: (i) (ii) . Dễ thấy, giao của một họ bất kỳ các tập lồi cũng là tập lồi. Giao của tất cả các tập lồi chứa tập được gọi là bao lồi của tập S và kí hiệu là convS. Rõ ràng, convS là tập lồi nhỏ nhất chứa S. Ví dụ 1.1.2 Cho các tập A, B, C như Hình 1. Hình 1. Theo định nghĩa , . Định lý 1.1.2 Bao lồi của tập chứa tất cả các tổ hợp lồi của các phần tử của nó. 1.1.3- Tập lồi đa diện * Tập lồi đa diện là giao của một số hữu hạn các nửa không gian đóng. Nói cách khác, tập lồi đa diện là tập nghiệm của một hệ bất đẳng thức tuyến tính có dạng , trong đó . * Một tập lồi đa diện là bao lồi của một số hữu hạn điểm và một số hữu hạn đoạn thẳng. * Một tập lồi đa diện bị chặn thường được gọi là đa diện lồi. * Một đa diện lồi là giao của một số hữu hạn điểm. Cho tập lồi đa diện M, tập con được gọi là diện nếu: Nói cách khác, F là một diện của M nếu F chứa một điểm trong (hoặc điểm trong tương đối) của một đoạn thẳng nào đó của M thì F chứa trọn cả đoạn thẳng đó. Một diện có thứ nguyên là 0 được gọi là một đỉnh hay điểm cực biên, cạnh là diện có thứ nguyên bằng 1. * Cho C là một tập lồi đa diện, một điểm được gọi là điểm cực biên (hay đỉnh) nếu nó không chứa bất kỳ một đoạn thẳng nào của C nhận làm điểm trong của đoạn thẳng đó, tức là không tồn tại 2 điểm phân biệt sao cho . Với tập lồi đa diện, một đỉnh của diện cũng chính là đỉnh của tập đó. * Một tập hữu hạn n +1 điểm được gọi là độc lập affine khi và chỉ khi là độc lập tuyến tính. * Nếu n+1 điểm là độc lập affine thì bao lồi của nó được gọi là một n-đơn hình với các đỉnh . Ví dụ 1.1.3 Trong mặt phẳng đơn hình là một tam giác, Hình 2a. Trong không gian đơn hình là một tứ diện, Hình 2b. a) b) Hình 2. * ảnh của tập lồi: Cho và ánh xạ . Khi đó nếu S là tập lồi và f là ánh xạ tuyến tính thì ảnh f(S) của S qua ánh xạ f cũng là tập lồi. Nhắc lại rằng, ma trận C cấp chính là ánh xạ tuyến tính từ . Xét ánh xạ tuyến tính , ta có định lý sau Định lý 1.1.3. Nếu S là tập lồi đa diện thì C(S) cũng là tập lồi đa diện. Hơn nữa, nếu S là đa diện lồi thì C(S) là bao lồi của ảnh các đỉnh của S. Ví dụ 1.1.4 Cho , trong đó . S là đa diện lồi với các đỉnh , , , . Khi đó , với , , , . Hình 3. 1.1.4- Điểm trong và điểm trong tương đối * Cho tập C bất kì, một điểm x gọi là điểm trong của C nếu . Tập hợp các điểm trong của tập C được kí hiệu là int C. * Điểm x0 được gọi là điểm trong tương đối nếu Kí hiệu: ri C là tập tất cả các điểm trong tương đối của C. Ví dụ 1.1.5 Cho tập như Hình 4. A x2 , . .x1 B D Hình 4. Theo định nghĩa: , . * Giả sử C là tập lồi trong Rn, véc tơ y0 được gọi là hướng lùi xa của C nếu thì . Tập hợp tất cả các hướng lùi xa gọi là nón lùi xa, kí hiệu là rec C. Định lí 1.1.4 Mọi tập lồi đa diện không chứa trọn một đường thẳng đều có ít nhất một đỉnh. Mọi tập lồi đa diện A có đỉnh bằng tập hợp các x có dạng : , trong đó : , với mọi i, j còn là các đỉnh, dj là phương của các cạnh vô hạn của A . Định nghĩa 1.1.1 i) Ta nói hai tập con khác rỗng là được tách bởi siêu phẳng nếu . ii) Hai tập được gọi là tách mạnh (tách hẳn, tách chặt) bởi siêu phẳng nếu . Định lí 1.1.5. Cho A là một tập lồi đóng và . Lúc đó tồn tại một siêu phẳng tách hẳn A và x0. 1.1.5. Hàm lồi * Một hàm f xác định trên tập lồi A được gọi là hàm lồi trên A, nếu ta có: . * Hàm f được gọi là lồi chặt nếu: * Hàm f được gọi là lõm (lõm chặt) nếu –f là lồi (lồi chặt). * Hàm f được gọi là tựa lồi trên A, nếu tập mức là tập lồi. Hàm f được gọi là tựa lõm nếu –f là tựa lồi. 1.1.6 Tính chất cực trị Cho và (không nhất thiết lồi) ta có định nghĩa Định nghĩa 1.1.2 Một điểm được gọi là cực tiểu địa phương của f trên D, nếu tồn tại một lân cận mở U của x* , sao cho . Điểm x* được gọi là cực tiểu tuyệt đối của f trên D nếu . Định lí 1.1.7. Mọi điểm cực tiểu địa phương của một hàm lồi trên một tập lồi đều là điểm cực tiểu tuyệt đối . Định lí 1.1.8. Cực đại của một hàm lồi (nếu có) trên một tập lồi có điểm cực biên bao giờ cũng đạt tại một điểm cực biên . 1.2. Phương pháp đơn hình giải bài toán qui hoạch tuyến tính: Bài toán qui hoạch tuyến tính là bài toán tìm cực đại (hoặc cực tiểu) một phiếm hàm tuyến tính trên một miền ràng buộc là một tập nghiệm của hệ bất đẳng thức hoặc đẳng thức tuyến tính. Cho đến nay, có nhiều thuật toán hữu hiệu để giải bài toán QHTT. Nhưng thuật toán đơn hình vẫn là một phương pháp được sử dụng rộng rãi nhất. Trong mục này em trình bày thuật toán đơn hình do Dintzig đề xuất từ năm 1947. 1.2.1 Mô hình toán học Bài toán QHTT dạng tổng quát có dạng , với điều kiện , trong đó A là ma trận cấp và , . Trong nghiên cứu qui hoạch tuyến tính cũng như trong thực tế, người ta thường dùng 2 dạng * Dạng chính tắc , (LP) với điều kiện . * Dạng chuẩn tắc , với điều kiện . Như đã biết, ta có thể dễ dàng chuyển một bài toán qui hoạch tuyến tính bất kì về dạng chính tắc nhờ các phép biến đổi tương đương sau * Một ràng buộc , có thể chuyển về dạng bằng cách nhân 2 vế với –1. * Một ràng buộc bất đẳng thức , có thể chuyển về với biến phụ . Không giảm tính tổng quát, ở đây em xin trình bày phương pháp đơn hình giải bài toán qui hoạch tuyến tính dạng chính tắc (LP). 1.2.2 Mô tả hình học của phương pháp đơn hình: Xuất phát từ một điểm cực biên của tập lồi đa diện ràng buộc D, các trường hợp sau có thể xảy ra: Trên mọi cạnh của tập lồi đa diện xuất phát từ đỉnh , hàm mục tiêu đều không giảm. Do tính chất tuyến tính của hàm mục tiêu, là một nghiệm tối ưu. Có một cạnh vô hạn theo đó hàm mục tiêu giảm. Khi đó hàm mục tiêu giảm đến theo cạnh này. Vậy bài toán không có nghiệm hữu hạn. Mọi cạnh xuấ phát từ , theo đó hàm mục tiêu giảm, đều là cạnh hữu hạn. Đi theo một cạnh như thế sẽ đến một đỉnh , kề với , tại đó hàm mục tiêu có giá trị nhỏ hơn. Quá trình lặp lại với với đỉnh . Thuật toán đơn hình chính là sự mô tả ý tưởng hình học trên. 1.2.3 Nghiệm cơ sở và phương án cực biên. Một đỉnh của tập lồi ràng buộc gọi là một phương án cực biên. Do qui hoạch tuyến tính có nghiệm tại phương án cực biên, nên người ta quan tâm đến các tính chất của một phương án cực biên. Trong trường hợp tập lồi ràng buộc được cho bởi dạng chính tắc , (1.2.0) điều kiện cần và đủ để một điểm chấp nhận được là phương án cực biên cho bởi mệnh đề sau (xem chứng minh trong [2]). Mệnh đề 1.2.1. Cho thỏa mãn (1.2.0). Cho . Điều kiện cần và đủ để x là một phương án cực biên là các véc tơ là độc lập tuyến tính. Giả sử x là phương án cực biên. Đặt . Theo Mệnh đề 1.2.1 các véc tơ là độc lập tuyến tính. Cho sao cho là một cơ sở của A. Tức là véc tơ này độc lập tuyến tính và nếu thêm bất kỳ vào B thì hệ thu được sẽ phụ thuộc tuyến tính. Véc tơ x gọi là nghiệm cơ sở, B là cơ sở, J là tập chỉ số cơ sở của x. Các biến , các véc tơ được gọi là biến cơ sở và véc tơ cơ sở. Các biến và các véc tơ còn lại được gọi là biến phi cơ sở và véc tơ phi cơ sở. Từ Mệnh đề 1.2.1, thì ta thấy rằng mỗi một nghiệm cơ sở chỉ ứng với một phương án cực biên. Tuy nhiên một phương án cực biên có thể ứng với nhiều nghiệm cơ sở. Một phương án cực biên được gọi là không thoái hóa nếu nó ứng vừa đúng một nghiệm cơ sở. Một tập lồi gọi là không thoái hoá, nếu mọi phương án cực biên (đỉnh) của nó không thoái hoá. 1.2.4 Thuật toán đơn hình Giả sử ta đã có một phương án cực biên x. Gọi J là tập chỉ số cơ sở của x. Do hệ là 1 cơ sở, nên mọi cột đều là một tổ hợp tuyến tính của véc tơ (). Tức là tồn tại các số thực sao cho: (1.2.1) Do x là nghiệm cơ sở với tập chỉ số cơ sở J, nên . Vậy: (1.2.2) Giá trị hàm mục tiêu là: (1.2.3) đặt (1.2.4) (1.2.5) Chú ý rằng nếu . Ta sẽ gọi là các ước lượng của phương án cực biên (nghiệm cơ sở của x). Ta có thể viết các công thức trên dưới dạng ma trận. Giả sử đã có tập cơ sở J. Ta đưa vào các kí hiệu sau: : ma trận có các cột thuộc cơ sở J (ma trận cơ sở). : véc tơ cột có các tọa độ , : véc tơ cột có các toạ độ : véc tơ cột có các toạ độ (1.2.1) (1.2.1)’ (1.2.2) (1.2.2)’ (1.2.3) (1.2.3)’ Như vậy nếu tính được ma trận nghịch đảo thì ta tính được các đại lượng .Ta xét điều kiện đủ để x là một nghiệm tối ưu: Định lí 1.2.1 Nếu thì phương án cực biên x là nghiệm tối ưu. Chứng minh : Lấy một phương án chấp nhận bất kì y. Khi đó ta có: (1.2.6) Giá trị hàm mục tiêu là: (1.2.7) do (1.2.8) Thay Ak từ (1.2.1) vào (1.2.6) ta có: hay: (1.2.9) Do x là phương án cực biên, nên . Do các véc tơ độc lập tuyến tính nên từ đây và (1.2.9) . Vậy: . So sánh với (1.2.8) . Do y là 1 điểm chấp nhận bất kì, nên x là nghiệm tối ưu. Trong trường hợp với một k nào đó, ta có thể chuyển qua một cơ sở mới. Trong nhiều trường hợp (ví dụ như tập lồi đa diện không thoái hoá) nghiệm cơ sở ứng với cơ sở mới này sẽ cho giá trị tốt hơn. Ta có định lí sau: Định lí 1.2.2 Cho x là một nghiệm cơ sở với cơ sở B. Khi đó: Nếu và thì bài toán không có nghiệm hữu hạn. Nếu , đều có với một , thì tìm đựơc một cơ sở x1 ứng với cơ sở B1 thoả mãn . Chứng minh: Gọi J là tập chỉ số cơ sở của x. Do x là nghiệm cơ sở nên (1.2.10) Theo định nghĩa của ta có . Nhân hai vế với , ta được . Lấy (1.2.10) trừ đi ta có: (1.2.11) Lấy véc tơ x1 có các toạ độ được cho bởi: , (1.2.12) (i) Do , nên x10, với mọi . Vậy x1 là phương án chấp nhập được với mọi . Giá trị hàm mục tiêu tại x1 là: . Do , ta có: . Cho ta thấy hàm mục tiêu giảm đến . Điều đó chứng tỏ trong trường hợp này bài toán không có nghiệm hữu hạn. ii) Chọn sao cho x1 định nghĩa theo (1.2.12) chấp nhận được, do (1.2.11) đúng với mọi , nên chỉ cần chọn sao cho . Gọi J1 là tập chỉ số , theo giả thiết . Rõ ràng với . Đối với chọn: (1.2.13) (r là chỉ số cơ sở đạt min), và với . Theo đại số tuyến tính do và nên B’ là một hệ độc lập tuyến tính. Ngoài ra theo cách chọn , ta có và . Vậy là một nghiệm cơ sở của . Đối với hàm mục tiêu, tương tự như trên, ta có: . (1.2.14) Nhận xét: Qua chứng minh này, ta thấy rằng, nếu xr=0 thì chọn theo (1.2.13) khi đó theo (1.2.12) x’=x và do đó . Như vậy trường hợp này nghiệm cơ sở không thay đổi, chỉ có cơ sở thay đổi. Tức là nghiệm cơ sở x ứng với với hai cơ sở B và B’ (x thoái hoá). Nếu >0, thì theo (1.2.14) , do đó . Hiển nhiên theo (1.2.13), nếu xj>0 với mọi thì >0. Tuy nhiên có thể dương ngay cả khi xj=0 với một chỉ số , bởi vì có thể với các chỉ số này . Trong chứng minh phần (ii), ta lấy k là một chỉ số bất kì, miễn sao . Nếu có nhiều chỉ số thoả mãn điều kiện này, thì dĩ nhiên chọn k sao cho hàm mục tiêu giảm nhanh nhất . Tức là theo (1.2.14) chọn k sao cho lớn nhất. Dựa vào định lí trên, thuật toán đơn hình được tiến hành theo các bước sau. Thuật toán đơn hình: Giả sử bài toán qui hoạch tuyến tính min với điều kiện (1.2.15) và ta đã biết một phương án cực biên x0. Bước 1: Chọn một cơ sở của x0. a) Với mỗi tính zjk bằng cách giải hệ phương trình tuyến tính sau: (1.2.16) b) Tính các ước lượng: . Bước 2: Nếu thì x0 là nghiệm tối ưu của (2.2.15). Thuật toán kết thúc. Tồn tại k sao cho . Phân biệt 2 trường hợp: b1) Tồn tại và : bài toán không có nghiệm hữu hạn. Thuật toán kết thúc. b2) ứng với đều tồn tại với một . Chọn s sao cho . (Để hàm mục tiêu giảm nhanh thường chọn s sao cho lớn nhất). Bước 3: (Chọn phần tử xoay) Chọn gọi r là chỉ số đạt cực tiểu. Tức là . Bước 4: (Tạo cơ sở mới) Lấy và x1 theo công thức sau: (1.2.17) Trở lại bước 1 với x0 và J được thay bởi x1 và J1. Định lí 1.2.3. Nếu tập lồi đa diện ràng buộc không thoái hoá, thì thuật toán hữu hạn theo nghĩa: sau một số hữu hạn vòng lặp, hoặc thuật toán chỉ ra rằng hàm mục tiêu không bị chặn dưới, hoặc tìm được một lời giải tối ưu của (1.2.15). 1.2.5 Công thức đổi cơ sở và bảng đơn hình: Trong thuật toán đơn hình, qua mỗi vòng lặp, ta chuyển qua một cơ sở mới kề với một cơ sở đang xét. Do hai cơ sở kề nhau chỉ khác nhau bởi một véc tơ, nên từ đại lượng của cơ sở này, dể dàng tính được đại lượng của cơ sở kia. Giả sử tập chỉ số của cơ sở đang xét là J và của cơ sở mới là và . Theo công thức (1.2.17) và chú ý , phương án cực biên ứng với là (1.2.15) Để tính các đại lượng zjk, ta nhớ lại rằng . Từ đây lấy Ar ra, ta có (1.2.16) mặt khác . Thay Ar từ (1.2.16) vào đây ta được: . Đây là công thức biểu diễn các cột của ma trận A qua cơ sở mới. Gọi các hệ số trong biểu diển này là , ta được: (1.2.17) Sau khi có , ta tính: (1.2.18) . (1.2.19) Nếu qui ước rằng: thì các công thức (1.2.18), (1.2.19) có thể thống nhất lại trong công thức (1.2.17) với . Để việc tính toán thuận lợi hơn, người ta thực hiện thuật toán đơn hình theo một bảng sau, gọi là bảng đơn hình. Mỗi một nghiệm cơ sở ứng với một bảng đơn hình. Giả sử trong bảng đơn hình dưới đây, các cột A1,..,..Am là một cơ sở. Cột Ar trong cơ sở sẽ được đưa ra và thay bởi cột As ở ngoài cơ sở. Bảng đơn hình Cj Aj xj c1 … cj … cr … cm … ck … cs … cn A1 … Aj … Ar ... Am … Ak … As … An c1 A1 x1 1 … 0 … 0 …..0 … .z1k … z1s … z1n c2 A2 x2 0 … 0…. .0… . .0… z2k… .z2s… z2n cj Aj xj 0…. 1… ..0… . .0… .zjk ….zjs …zjn cr Ar xr 0… .0… .1… ..0… .zrk… .zrs ….zrn cm Am xm 0… .0 ….0… ..1 ….zmk …zms… zmn 0 ….0 ….0… ..0 …. 1.2.6 Vấn đề phương án cực biên và cơ sở xuất phát: Để thực hiện được thuật toán đơn hình ta phải có một phương án cực biên và cơ sở xuất phát. Khi miền ràng buộc cho bởi: , với A là ma trận cấp () và . Ta luôn giả sử được rằng (bằng cách nhân với –1, nếu b<0). Đưa vào biến giả tạo t=(t1,t2,…,tm) và xét tập . Dễ dàng chứng minh được rằng, x là một đỉnh của D khi và chỉ khi (x,0) là một đỉnh của . Vì vậy để tìm một phương án cực biên của D ta giải bài toán: min t1+t2+…tm , với ràng buộc: Ax+t=b, (x,t)0. Đối với bài toán này, ta luôn biết trước một phương án cực biên (0,b) và một cơ sở của nó là B=(e1,…,em), trong đó ei là véc tơ đơn vị thứ i trong Rm. Vậy ta có thể dùng thuật toán đơn hình để giải bài toán này. Bài toán này luôn có nghiệm vì hàm mục tiêu luôn bị chặn dưới bởi 0. 1.2.7 Đối ngẫu của qui hoạch tuyến tính. Đối ngẫu là một bài toán khá quan trọng về cả phương diện lý thuyết lẫn ứng dụng thực tế và giải số. ý tưởng cơ bản của bài toán đối ngẫu là xây dựng cho bài toán qui hoạch tuyến tính đang xét một bài toán "đối" với nó (gọi là bài toán đối ngẫu) sao cho thay vì giải bài toán ban đầu ta chỉ cần giải bài toán dối ngẫu. Trong nhiều trường hợp giải quyết bài toán sau dễ dàng hơn nhiều. Hơn nữa trong khi nghiên cứu bài toán đối ngẫu, có thể thu nhận được những kết luận hay, cả về ý nghĩa toán học, lẫn ý nghĩa kỹ thuật hoặc kinh tế. Dưới đây là các dạng đối ngẫu của bài toán qui hoạch tuyến tính. a. Dạng bài đối ngẫu của qui hoạch tuyến tính. Cho qui hoạch tuyến tính dưới dạng chuẩn tắc , (P) với điều kiện , trong đó A là ma trận cấp và , . Ta gọi bài toán qui hoạch đối ngẫu của bài toán (P) là bài toán QHTT sau (D) với điều kiện , trong đó là ma trận chuyển vị của A, . Cặp bài toán đối ngẫu (P) và (D) có các tính chất sau Định lý 1.2.4. Với mọi phương án chấp nhận x của bài toán gốc (P) và y của bài toán đối ngẫu (D) ta có (i) , (ii) khi và chỉ khi x là nghiệm tối ưu của (P) và y là nghiệm tối ưu của (D). Định lý 1.2.5 Đối với một cặp bài toán QHTT đối ngẫu (P) và (D) chỉ xãy ra một trong ba trường hợp sau: 1) Cả hai bài toán không có phương án chấp nhận. 2) Cả hai bài toán đều có phương án chấp: lúc đó cả hai đều có phương án chấp nhận và giá trị tối ưu của chúng bằng nhau. 3) Một trong hai bài toán qui hoạch có phương án chấp nhận, qui hoạch kia không: lúc đó qui hoạch này không có phương án tối ưu hữu hạn (hàm mục tiêu không hữu hạn trên miền chấp nhận được). Định lý 1.2.6 Điều kiện cần và đủ để một cặp phương án chấp nhận x,y của cặp QHTT đối ngẫu (P) và (D) tối ưu là 1) . 2) b. Thuật toán đơn hình đối ngẫu Xét qui hoạch tuyến tính , (P) với điều kiện , trong đó A là ma trận cấp và , . Ta gọi bài toán qui hoạch đối ngẫu của bài toán (P) là bài toán QHTT sau (D) với điều kiện , trong đó là ma trận chuyển vị của A, . Giả sử B là một cơ sở của các cột của A và J là tập chỉ số cơ sở. Ta nói là một phương án cơ sở đối ngẫu của (D) nếu , . Xét hệ phương trình Giả sử hệ này có nghiệm là x. Ta gọi x là giả phương án của (P). Các biến gọi là các biến cơ sở của giả phương án, các biến còn lại là các biến phi cơ sở. THUậT TOáN Bước 1. Xuất phát từ một cơ sở với tập chỉ số cơ sở J. Xây dựng bảng đơn hình cho giả phương án x với tập chỉ số cơ sở J. Bước 2. Kiểm tra tính chấp nhận được của giả phương án 2a) Nếu thì x là phương án tối ưu. Dừng thuật toán. 2b) Nếu tồn tại ít nhất . Xãy ra mọt trong hai trường hợp sau (i) Có và . Lúc đó hàm mục tiêu của bài toán đối ngẫu không bị chặn trên (lớn vô cùng). Theo Định lý 1.2.4, qui hoạch gốc không có phương án chấp nhận được. Thuật toán kết thúc. (ii) Với mọi đều tồn tại sao cho . Tiến hành các thủ tục tính toán sau Tìm véc tơ để đưa ra khỏi cơ sở theo Thay bằng , trong đó s được xác định như sau Cơ sở mới thu được bằng cách đưa ra và đưa vào cơ sở. Lấy . Quay lại Bước 1 với tập chỉ số cơ sở J được thay bằng . Ví dụ 1.2.1 Giải bài toán QHTT sau bằng phương pháp đơn hình: min(x1-2x2+x3-3x4+2x5) với ràng buộc Ta có phương án cực biên: . Với các véc tơ cơ sở là: A1, A2, A3. Sau 2 bước lặp ta thu được bảng đơn hình sau Cj Cơ sở Aj P.án xj 1 -2 1 -3 2 A1 A2 A3 A4 A5 1 -2 1 A1 A2 A3 3 8 10 1 0 0 1 2 0 1 0 0 1 0 0 1 1 0 -3 0 0 0 5 -4 -3 -2 1 A4 A2 A3 3 8 7 1 0 0 1 2 0 1 0 0 1 -1 0 0 0 -2 -18 -5 0 0 0 -10 Theo kết quả thu được từ bảng đơn hình ta được nghiệm tối ưu là của bài toán trên là x2=8, x3=7, x4=3, fmin=-18. 1.3 Kết luận Trong chương này, em đã trình bày một số khái niệm cơ bản về giải tích lồi để làm sáng tỏ cho các khái niệm khi được đưa vào ở các chương sau. Phương pháp đơn hình là một trong nhiều phương pháp được sử dụng rỗng rãi để giải bài toán qui hoạch tuyến tính cũng được trình bày ở đây. Chương Ii bài toán qui hoạch tuyến tính đa mục tiêu 2.1. Thế nào là tối ưu đa mục tiêu Như đã biết, nhiều bài toán ứng dụng trong các lĩnh vực khác nhau của khoa học kỹ thuật cũng như thực tiễn cuộc sống của con người, có thể mô hình hoá như bài toán tối ưu một hàm mục tiêu duy nhất theo những điều kiện nhất định. Ví dụ bài toán qui hoạch tuyến tính như đã mô tả ở Chương I là tối ưu một hàm tuyến tính trên một tập lồi đa diện . Tuy nhiên, thực tế cùng một lúc người ta thường phải theo đuổi nhiều mục tiêu khác nhau. Ví dụ khi lựa chọn mua nhà ở, chúng ta phải tính đến nhiều yếu tố như giá cả, môi trường, tiện nghi. Thường nhà rẻ hơn thì môi trường hoặc tiện nghi kém hơn. Điều đó dẫn đến mô hình bài toán tối ưu nhiều mục tiêu (qui hoạch đa mục tiêu). Để hiểu rõ hơn về bài toán này ta xét 2 ví dụ dưới đây. Ví dụ 2.1.1.(Tối ưu phương án thiết kế nhà ở) Giả sử trong thiết kế nhà ở như Hình 5, cách bố trí các phòng cũng như một số thông số và ràng buộc được cho trước. Vấn đề phải xác định các thông số còn lại nhằm cực đại diện tích sử dụng và cực tiểu chi phí xây dựng. x1 x2 x3 2.45 Phòng ăn 1.83 Wc 3.35 Phòng ngủ 1 3.98 Phòng ngủ 2 Sảnh x43.05 Bếp x5 Phòng ngủ 3 Hình 5. Chi phí xây dựng được cho bảng dưới đây Loại phòng Diện tích min (m2) Diện tích max (m2) Giá (USD) Bếp 5 12 200 Phòng ngủ 10 18 100 Phòng ăn 15 20 300 Sảnh 1,83 7,2 324,7 Tắm 4,5 6,5 324,7 Lập bài toán: Gọi S là diện tích sử dụng thì S là hàm số của x1, x2, x3 theo công thức: S(x1, x2, x3, x4, x5)=7,33(x1+ x2+ x3). Gọi C là chi phí xây dựng thì C hàm số của x1, x2, x3, x4, x5 theo công thức: C=(4,28x1).300+ (2,45x2)324,7+ (1,83x2)324,7+ (3,05x4)200+ (3,05x5+ 3,35x3+ 3,98x3)100 = 1284x1+1389,716x2+ 733x3+ 610x4+ 305x5. Ngoài ra ta còn có các ràng (R) buộc sau: Đối với bếp : Đối với phòng ăn : Đối với phòng tắm : Đối với sảnh : Đối với phòng ngủ 1: Đối với phòng ngủ 2: Đối với phòng ngủ 3: Ràng buộc hình học (R): và . Chúng ta có bài toán tối ưu hai mục tiêu sau: Tìm sao cho max S(x1,x2,x3) min C(x1,x2,x3,x4,x5) với các ràng buộc R tức là với . Ví dụ 2.1.2. (Lập chế độ ăn kiêng) Giả sử cho trước danh sách các món ăn chính như thịt, cá, rau với những hàm lượng dinh dưỡng như đạm, mỡ, vitamin, lượng calo và giá cả...Chúng ta phải xác định khẩu phần để cực tiểu chi phí ăn uống, cực tiểu lượng calo và cực đại ngon miệng. Lập bài toán: Kí hiệu x1, x2, x3 là lượng thịt, cá, rau (tính bằng gram) cho mỗi khẩu phần. Hàm lượng dinh dưỡng, calo và giá cả của mỗi gram thức ăn nói trên được biết như sau Đạm Mỡ Vitamin Calo Giá Thịt P1 l1 v1 c1 Cá P2 l2 v2 c2 Rau P3 l3 v3 c3 Gọi G là chi phí cho mỗi khẩu phần: . Gọi C là số calo cho mỗi khẩu phần cung cấp: . Đối với sự ngon miệng T thường được đánh giá bởi tỷ lệ thịt cá so với rau: Ta nói khẩu phần (x1, x2, x3) ngon nếu , hay Khẩu phần (x1, x2, x3) ngon hơn khẩu phần (y1, y2, y3) nếu (x1-y1, x2-y2, x3-y3) bảo đảm tỷ lệ trên. Những ràng buộc đối với lượng dinh dưỡng (D): lượng đạm : lượng mỡ : lượng vitamin: Như vậy chúng ta có bài toán tối ưu đa mục tiêu sau: minG, minC, maxT với các ràng buộc D. Nhận xét: Trong hai ví dụ trên có mục tiêu đối kháng (như diện tích sử dụng và giá cả). Mục tiêu T ở ví dụ 2 không dễ xử lý vì không phải 2 phương án nào cũng so sánh được. 2.2. Mô hìn._.