Đăng ký Đăng nhập
Trang chủ PHƯƠNG PHÁP SỐ TRONG LÝ THUYẾT TỐI ƯU...

Tài liệu PHƯƠNG PHÁP SỐ TRONG LÝ THUYẾT TỐI ƯU

.PDF
72
553
108

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Lê Đại Phước PHƯƠNG PHÁP SỐ TRONG LÝ THUYẾT TỐI ƯU LUẬN VĂN THẠC SĨ TOÁN HỌC Thành phố Hồ Chí Minh - 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Lê Đại Phước PHƯƠNG PHÁP SỐ TRONG LÝ THUYẾT TỐI ƯU Chuyên ngành: Toán giải tích Mã số: 60 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Trịnh Công Diệu Thành phố Hồ Chí Minh – 2013 LỜI CẢM ƠN Đầu tiên, tôi xin bày tỏ lòng biết ơn sâu sắc đối với TS. TRỊNH CÔNG DIỆU khoa Toán trường Đại học Sư phạm Thành phố Hồ Chí Minh đã dành thời gian và công sức và tận tình hướng dẫn giúp tôi hoàn thành luận văn này. Tôi xin gửi lời cảm ơn đến quý Thầy Cô trong hội đồng chấm luận văn đã dành thời gian đọc, chỉnh sửa và đóng góp ý kiến giúp cho tôi hoàn thành luận văn này một cách hoàn chỉnh. Bên cạnh đó, tôi xin chân thành cảm ơn Ban giám hiệu trường Đại học Sư phạm Thành phố Hồ Chí Minh, Ban chủ nhiệm khoa Toán và quý Thầy Cô đã giảng dạy, tạo điều kiện cho chúng tôi hoàn thành khóa học này. Và để có được kết quả như ngày hôm nay, tôi đã nhận được những lời động viên, đóng góp ý kiến của bạn bè và người thân. Cuối cùng, trong quá trình viết luận văn này, khó tránh khỏi những thiếu sót, tôi mong nhận được những ý kiến đóng góp của bạn đọc. Xin chân thành cảm ơn! Thành phố Hồ Chí Minh, tháng 10 năm 2013 Lê Đại Phước 1 MỤC LỤC LỜI CẢM ƠN .............................................................................................................. 1 MỤC LỤC .................................................................................................................... 2 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT............................................ 4 MỞ ĐẦU....................................................................................................................... 5 1. Lý do chọn đề tài ............................................................................................................. 5 2. Mục đích của đề tài ......................................................................................................... 5 3. Đối tượng và phạm vi nghiên cứu ................................................................................. 5 4. Ý nghĩa khoa học và thực tiễn ....................................................................................... 6 CHƯƠNG 1: KIẾN THỨC CHUẨN BỊ ................................................................... 7 1.1. Một số khái niệm và kết quả cơ bản từ giải tích lồi .................................................. 7 1.1.1. Không gian Euclid  n ............................................................................................7 1.1.2. Hàm nhiều biến .......................................................................................................8 1.1.3. Tập lồi......................................................................................................................9 1.1.4. Hàm lồi ..................................................................................................................10 1.2. Bài toán tối ưu ............................................................................................................ 11 1.2.1. Bài toán tối ưu và các khái niệm cơ bản ...............................................................11 1.2.2. Các loại bài toán tối ưu..........................................................................................12 CHƯƠNG 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ..................................... 13 2.1. Thuật toán đơn hình dạng bảng ............................................................................... 15 2.1.1. Thuật toán ..............................................................................................................15 2.1.2. Chương trình .........................................................................................................19 2.1.3. Các ví dụ ................................................................................................................23 2.2. Thuật toán đơn hình dạng ma trận nghịch đảo ...................................................... 25 2.2.1. Thuật toán ..............................................................................................................25 2.2.2. Chương trình .........................................................................................................27 2.2.3. Các ví dụ ................................................................................................................29 2.3. Thuật toán đơn hình đối ngẫu .................................................................................. 30 2.3.1. Thuật toán: .............................................................................................................30 2.3.2. Chương trình: ........................................................................................................31 2.3.3. Ví dụ: .....................................................................................................................33 CHƯƠNG 3: BÀI TOÁN QUY HOẠCH PHI TUYẾN KHÔNG RÀNG BUỘC35 3.1. Phương pháp Gradient .............................................................................................. 36 2 3.1.1. Thuật toán: .............................................................................................................36 3.1.2. Chương trình .........................................................................................................37 3.1.3. Ví dụ ......................................................................................................................38 3.2. Phương pháp Newton ................................................................................................ 38 3.2.1. Thuật toán: .............................................................................................................38 3.2.2. Chương trình .........................................................................................................39 3.2.3. Ví dụ ......................................................................................................................40 3.3. Phương pháp tìm kiếm trực tiếp .............................................................................. 41 3.3.1. Trường hợp n = 1 ..................................................................................................41 3.3.2. Trường hợp n = 2 .................................................................................................44 CHƯƠNG 4: BÀI TOÁN QUY HOẠCH PHI TUYẾN CÓ RÀNG BUỘC ........ 50 4.1. Phương pháp tuyến tính hóa .................................................................................... 50 4.1.1. Thuật toán: .............................................................................................................51 4.1.2. Sự hội tụ: ...............................................................................................................53 4.1.3. Ví dụ: .....................................................................................................................55 4.2. Phương pháp hàm phạt ............................................................................................. 59 4.2.1. Phương pháp hàm phạt điểm trong .......................................................................60 4.2.2. Phương pháp hàm phạt điểm ngoài .......................................................................65 KẾT LUẬN VÀ KIẾN NGHỊ................................................................................... 68 TÀI LIỆU THAM KHẢO ........................................................................................ 70 3 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT  tập số thực n không gian Euclid n chiều x∈D x thuộc tập D x∉D x không thuộc tập D ∅ tập rỗng C\D hiệu của tập C và D C∪D hợp của tập C và tập D C∩D giao của tập C và tập D C⊂D C là một tập con của D x, y tích vô hướng của x và y x chuẩn Euclid của x x giá trị tuyệt đối của x dom f miền xác định hữu hiệu của f epi ( f ) epigraph của hàm f f ′ ( x0 , d ) đạo hàm theo hướng của hàm f theo hướng d tại x0 ∇f ( x ) vectơ gradient của hàm f tại điểm x AT ma trận chuyển vị của ma trận A A−1 ma trận nghịch đảo của ma trận khả nghịch A Im ma trận đơn vị cấp m rank ( A ) hạng của ma trận A ∀x với mọi x ∃x tồn tại x 4 MỞ ĐẦU 1. Lý do chọn đề tài Có nhiều tình huống xã hội, từ cuộc sống đời thường đến các hoạt động kinh tế, kỹ thuật, công nghệ và quản lý hiện đại… người ta phải quan tâm tới bài toán tìm ra phương án tốt nhất để đạt mục tiêu mong muốn trong những điều kiện ràng buộc nhất định. Đó là các bài toán tối ưu. Chính những nỗ lực nhằm giải các bài toán tối ưu đã góp phần kích thích sự phát triển của Giải tích Toán học thế kỷ XVII – XVIII với sự đóng góp to lớn của những nhà toán học lỗi lạc của mọi thời đại: Fermat, Leibniz, Euler…Tuy nhiên, phải đến những năm 30, 40 của thế kỷ XX, Quy hoạch toán học (Mathematical Programming) hay còn gọi là Toán Tối Ưu (Optimization) mới hình thành với tư cách là một lý thuyết độc lập với nhiều hướng nghiên cứu khác nhau: đầu tiên là Quy hoạch tuyến tính (Linear Programming), tiếp đó là Quy hoạch lồi (Convex Programming), Quy hoạch toàn cục (Global Programming), Lý thuyết điều khiển tối ưu (Optimization Control). Danh sách các tài liệu về chủ đề này có đến hàng trăm. Nó nói lên vai trò quan trọng của việc tìm cực trị trong các bài toán ứng dụng. Có nhiều tình huống thực tế việc tìm kết quả chính xác rất phức tạp trong khi chỉ cần 1 kết quả gần đúng là có thể sử dụng được, đồng thời cần có 1 thuật toán hiệu quả cho các máy tính theo đó xử lý. Học viên quan tâm đến các phương pháp chuyển đổi các công thức lý thuyết đẹp đẽ thành những kết quả bằng số cụ thể. 2. Mục đích của đề tài Vì những lý do trên, học viên thực hiện luận văn này sẽ khảo sát các phương pháp số tiêu biểu và có nhiều ứng dụng để giải quyết một vài bài toán quy hoạch tuyến tính và phi tuyến. 3. Đối tượng và phạm vi nghiên cứu Xét các bài toán quy hoạch tuyến tính và phi tuyến. Với mỗi bài toán trình bày thuật toán, cơ sở lý luận của thuật toán, cho ví dụ minh họa. 5 4. Ý nghĩa khoa học và thực tiễn Quy hoạch tuyến tính là một bộ phận quan trọng của quy hoạch toán học. Đây là mô hình toán của nhiều bài toán thực tế thuộc các lĩnh vực khác nhau như kinh tế, viễn thông, xây dựng… Các thuật toán giải quy hoạch tuyến tính còn là công cụ để giải các bài toán phức tạp hơn như quy hoạch phi tuyến, tối ưu đa mục tiêu… Ngày nay, với sự trợ giúp của cuộc cách mạng công nghiệp thông tin, quy hoạch toán học ngày càng phát triển mạnh mẽ. Các phương pháp tối ưu đã được ứng dụng rộng rãi trong mọi lĩnh vực khoa học, kỹ thuật, công nghệ, quản lý, kinh tế, khai thác dữ liệu (data mining), viễn thông, v.v… 6 CHƯƠNG 1: KIẾN THỨC CHUẨN BỊ 1.1. Một số khái niệm và kết quả cơ bản từ giải tích lồi 1.1.1. Không gian Euclid  n 1.1.1.1. Điểm hay vectơ trong  n Trong luận văn này chúng ta sẽ làm việc trên không gian Euclid  n . Mỗi điểm trong không gian  n là một bộ số thực được sắp có thứ tự và được viết dưới dạng cột số  x1   2 x x :=       n  x  Mỗi số xi , i ∈ {1,..., n} , được gọi là tọa độ thứ i của điểm x . Để thuận tiện khi viết, ta qui ước  x1   2 x n T 1 2 = x (= x , x ,..., x ) :       n  x  1.1.1.2. Tích vô hướng ( 1 2 n Tích vô hướng của hai vectơ x = ( x1 , x 2 ,..., x n ) và y = y , y ,..., y T ) T là một số thực, ký hiệu là x, y , được xác định như sau x, y =: x1 y1 + x 2 y 2 + ... + x n y n . 1.1.1.3. Chuẩn Euclid của vectơ n Chuẩn Euclid (hay độ dài) của vectơ x ∈  , ký hiệu là x , là một số thực xác định bởi 1 = x : 2 2  n = x, x  ∑ x i   i =1  7 1.1.2. Hàm nhiều biến 1.1.2.1. Định nghĩa Hàm f từ  n và  là một quy tắc ứng mỗi điểm x thuộc  n với một số thực nào đó và kí hiệu số thực đó là f ( x ) . Cách viết f : X →  , với X ⊆  n , nói rằng f ( x ) chỉ xác định với các điểm x ∈ X . Khi đó, ta gọi X là miền xác định của hàm f . Vì biến số ở đây là các phần tử thuộc  n nên nó có n thành phần có thể được xem như một biến độc lập. Do đó người ta thường gọi hàm xác định trên  n , với n ≥ 2 , là hàm nhiều biến. 1.1.2.2. Gradient Cho hàm f xác định trên tập mở X ⊆  n . Giả sử rằng tại x0 , các đạo hàm riêng của hàm f theo mọi biến tồn tại. Khi đó, vectơ  ∂f ( x0 ) ∂f ( x0 )  ,...,   1 ∂x n   ∂x T được gọi là Gradient của f tại x0 và ký hiệu là ∇f ( x0 ) . 1.1.2.3. Đạo hàm theo hướng Cho hàm f xác định trên  n và một vectơ d ∈  n \ {0} . Giới hạn lim+ t →0 f ( x0 + td ) − f ( x0 ) t , nếu tồn tại (hữu hạn hoặc vô cùng), được gọi là đạo hàm theo hướng d của hàm f tại điểm x0 ∈  n và ký hiệu f ′ ( x0 , d ) . Mệnh đề 1.1 ([1, tr. 14]) Cho hàm f xác định trên  n và điểm x0 ∈  n . Nếu f khả vi tại x0 thì f ′ ( x0 , d ) = ∇f ( x0 ) , d , ∀d ∈  n \ {0} . 1.1.2.4. Hàm tuyến tính, hàm afin Một hàm số f ( x ) xác định trên  n được gọi là tuyến tính nếu f ( λ x1 + µ x2 )= λ f ( x1 ) + µ f ( x2 ) 8 với mọi x1 , x2 ∈  n và với mọi λ , µ ∈  . Một hàm tuyến tính xác định trên  n luôn có dạng f ( x ) = c, x , trong đó vectơ c ∈  n cho trước. Hàm số có dạng f= ( x) c, x + α , trong đó vectơ c ∈  n và α ∈  cho trước, được gọi là hàm afin hay hàm tuyến tính afin. 1.1.3. Tập lồi 1.1.3.1. Tập lồi Cho hai điểm x1 và x2 thuộc  n . Tập tất cả các điểm có dạng x = λ x1 + (1 − λ ) x2 = x2 + λ ( x1 − x2 ) với 0 ≤ λ ≤ 1 , được gọi là đoạn thẳng nối x1 và x2 , ký hiệu là [ x1 , x2 ] . Tập M ⊆  n được gọi là tập lồi nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó, tức là mọi x1 , x2 ∈ M và 0 ≤ λ ≤ 1 ta có λ x1 + (1 − λ ) x2 ∈ M . 1.1.3.2. Nửa không gian Ta gọi tập {x ∈  n | a, x ≤ α } hoặc { x ∈  n | a, x ≥ α } với a ∈  n \ {0} và α ∈ R là nửa không gian đóng. 1.1.3.3. Tập lồi đa diện Tập lồi đa diện P ⊂  n là giao của một số hữu hạn nửa không gian đóng. Nói cách khác nó là tập nghiệm của một hệ hữu hạn các bất đẳng thức tuyến tính ai , x ≥ bi , i = 1,..., l Mỗi bất đẳng thức trong hệ trên được gọi là một ràng buộc. Ràng buộc k ∈ {1,..., l} là ràng buộc thừa nếu {x | ai , x ≥ bi , i= 1,.., l}= {x | ai , x ≥ bi , i ∈ {1,..., l} \ {k }} hàng là ai Nếu ta kí hiệu A là ma trận cấp l × n với các = = b ∈  , x ( x ,..., x ) ( b ,..., b )= 1 l T l 1 n T a ,..., a ) , i (= i1 in 1,..., l ; vectơ ∈  n thì hệ trên được viết dưới dạng ma trận như sau Ax ≥ b 9 Vì một phương trình tuyến tính có thể biểu diễn tương đương với hai bất phương trình tuyến tính nên tập nghiệm của hệ phương trình và bất phương trình tuyến tính i ai ,= x b= , i 1,..., l1 ai , x ≥ bi , i =+ l1 1,..., l cũng là một tập lồi đa diện. Dễ thấy rằng tập lồi đa diện là một tập lồi, đóng. Một tập lồi đa diện bị chặn được gọi là đa diện lồi hay gọi tắt là đa diện. 1.1.4. Hàm lồi 1.1.4.1. Định nghĩa Hàm f được gọi là hàm lồi xác định trên tập lồi X ⊆  n nếu f ( λ x1 + (1 − λ ) x2 ) ≤ λ f ( x1 ) + (1 − λ ) f ( x2 ) với bất kỳ x1 , x2 ∈ X số thực λ ∈ [ 0,1] . Miền xác định hữu hiệu của hàm f là domf=: { x ∈ X | f ( x ) < +∞} Epigraph của hàm lồi f là tập epi ( = f ): {( x, ξ ) ∈ X ×  | ξ ≥ f ( x )} ⊂  n +1 Hàm lồi f : X →  ∪ {+∞} có thể được mở rộng thành một hàm lồi trên toàn không gian  n bằng cách đặt f ( x ) = +∞ nếu x ∉ domf . Vì vậy, để đơn giản, ta thường xét f là hàm lồi trên  n . 1.1.4.2. Đạo hàm theo hướng của hàm lồi Định lý 1.1 ([1, tr. 33]) Nếu f : X →  là một hàm lồi xác định trên tập lồi X ⊂  n thì nó có đạo hàm theo mọi hướng d ∈  n \ {0} tại mọi điểm x0 ∈ dom f và f ′ ( x0 , d ) ≤ f ( x0 + d ) − f ( x0 ) . Hệ quả 1.1 ([1, tr. 33]) Nếu f là hàm lồi khả vi xác định trên tập lồi mở X thì f có đạo hàm theo mọi hướng d ∈  n \ {0} tại mọi điểm x0 ∈ dom f và 10 ∇f ( x0= ) , d f ′ ( x0 , d ) ≤ f ( x0 + d ) − f ( x0 ) 1.2. Bài toán tối ưu 1.2.1. Bài toán tối ưu và các khái niệm cơ bản Bài toán tối ưu tổng quát được phát biểu như sau: min f ( x ) với điều kiện x ∈ D (BT1) max f ( x ) với điều kiện x ∈ D (BT2) hoặc trong đó D ⊆  n được gọi là tập phương án chấp nhận được hay tập ràng buộc và f : D →  là hàm mục tiêu. Mỗi điểm x ∈ D được gọi là một phương án chấp nhận được (có thể gọi tắt là một phương án). Điểm x* ∈ D mà f ( x* ) ≤ f ( x ) ∀x ∈ D được gọi là nghiệm tối ưu, hoặc đơn giản là nghiệm của bài toán. Người ta còn gọi một nghiệm tối ưu là một phương án tối ưu hay lời giải của bài toán đã cho. Giá trị tối ưu của bài toán (BT1) được kí hiệu là min f ( x ) hoặc min { f ( x ) | x ∈ D} x∈D Nếu bài toán (BT1) có nghiệm tối ưu là x* thì = f ( x* ) min { f ( x ) | x ∈ D} Chú ý: i) Bài toán (BT1) tương đương với bài toán max − f ( x ) với điều kiện x ∈ D . Theo nghĩa tập nghiệm tối ưu của hai bài toán này là trùng nhau và giá trị tối ưu của chúng thì ngược dấu, tức là min { f ( x ) | x ∈ D} = − max {− f ( x ) | x ∈ D} Vì vậy, không giảm tổng quát, ta chỉ cần xét bài toán (BT1) hoặc bài toán (BT2). 11 ii) Nếu D =  n thì ta nói (BT1) là bài toán tối ưu không ràng buộc. Ngược lại, nếu D ⊂  n thì ta nói (BT1) là bài toán tối ưu có ràng buộc. Trong các bài toán tối ưu có ràng buộc, tập D thường được xác định bởi D :={ x ∈  n | gi ( x ) ≤ 0, i =1,..., p} với gi , i = 1,..., p , là các hàm thực xác định trên tập A ⊃ D (thông thường A =  n ) Ta gọi gi ( x ) , i = 1,..., m , là các hàm ràng buộc. Mỗi hệ thức gi ( x ) ≤ 0, i ∈ {1,..., p} , được gọi là một ràng buộc của bài toán. Vì ràng buộc gi ( x ) ≥ 0 ⇔ − gi ( x ) ≤ 0 và  gi ( x ) ≤ 0 gi ( x )= 0 ⇔  − gi ( x ) ≤ 0 nên rõ ràng biểu diễn D bên trên bao gồm hết các loại ràng buộc. 1.2.2. Các loại bài toán tối ưu Người ta thường chia các bài toán tối ưu thành một số lớp dựa trên tính chất của hàm mục tiêu và tập chấp nhận được. Sau đây, ta sẽ nêu khái niệm các bài toán được xét trong luận văn, các bài toán khác chỉ nêu tên. - Quy hoạch tuyến tính: hàm mục tiêu f ( x ) là hàm tuyến tính và tập chấp nhận được D ⊂  n là tập lồi đa diện (tức là các hàm ràng buộc gi ( x ) , i = 1,..., m là các hàm afin). - Quy hoạch phi tuyến: hàm mục tiêu f ( x ) hoặc một trong các hàm ràng buộc gi ( x ) , i = 1,..., m không phải hàm afin. Trong các bài toán tối ưu phi tuyến có hai lớp đặc biệt quan trọng, đó là: Quy hoạch lồi và quy hoạch lõm. +Quy hoạch lồi: là bài toán cực tiểu một hàm mục tiêu f ( x ) là hàm lồi trên tập chấp nhận được D ⊆  n là tập lồi. Ngoài ra còn có: Quy hoạch nguyên, Quy hoạch động, Quy hoạch đa mục tiêu, Quy hoạch ngẫu nhiên, Quy hoạch tham số …. 12 CHƯƠNG 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Một số ký hiệu và định nghĩa Lưu ý: trong chương này ta dùng chỉ số dưới để chỉ các thành phần của vectơ ( xi là thành phần thứ i của vectơ x ) trong  n . I = {1, 2,..., m} - tập chỉ số các ràng buộc. J = {1, 2,..., n} - tập chỉ số của các biến số. = x x= Tập các biến số x1 , x2 ,..., xn ∈  được viết dưới dạng vectơ (J ) {x j : j ∈ J} c =c ( J ) ={c j ∈  : j ∈ J } b =b ( I ) ={bi ∈  : i ∈ I } Các hệ số aij ( i ∈ I , j ∈ J ) được viết dưới dạng ma trận A = A ( I , J ) = {aij ∈  : i ∈ I , j ∈ J } x 0 ( x ≥ 0 ) được hiểu theo nghĩa từng thành phần, tức là Hệ thức= xj = 0 (x j ≥ 0) , j ∈ J Các vectơ là vectơ cột, để chỉ vectơ dòng ta dùng ký hiệu chuyển vị “T”. Các phép tính đối với ma trận và vectơ được hiểu theo quy tắc thông thường của đại số ma trận. Dưới dạng ma trận – vectơ ta xét bài toán quy hoạch tuyến tính (QHTT) sau:  f= ( x ) c, x → min  (TT0)  Ax = b x ≥ 0   Ta sẽ gọi vectơ c là vectơ hệ số hàm mục tiêu, b là vectơ điều kiện, A là ma trận ràng buộc. Hệ ràng buộc Ax = b gọi là hệ ràng buộc cơ bản, còn bất phương trình x ≥ 0 gọi là ràng buộc dấu của bài toán (QHTT).  Vectơ n chiều x thỏa mãn tất cả các ràng buộc của bài toán được gọi là phương án chấp nhận được. 13 D  Tập = = { x : Ax b, x ≥ 0} tất cả các phương án chấp nhận được của bài toán được gọi là tập chấp nhận được hay tập ràng buộc của bài toán.  Phương án chấp nhận được x* đem lại giá trị nhỏ nhất cho hàm mục tiêu, tức là: c, x* ≤ c, x , ∀x ∈ D ( ) được gọi là phương án tối ưu, còn giá trị f x* = c, x* là giá trị tối ưu của bài toán. Giả thiết rằng hạng của ma trận A là bằng m .  Ta gọi cơ sở của ma trận A là một bộ gồm m vectơ độc lập tuyến tính { B = Aj1 ,..., Ajm } của nó. Giả sử B = A ( I , J B ) , trong đó J B = { j1 ,..., jm } là một cơ sở của ma trận A .  Khi đó vectơ x = ( x1 ,..., xn ) thỏa mãn: x j = 0, j ∈ J N = J \ J B ; x jk là thành phần thứ k của vectơ B −1b ( k = 1,..., m ) sẽ được gọi là phương án cơ sở tương ứng với cơ sở B . Các biến x j , j ∈ J B được gọi là biến cơ sở, còn x j , j ∈ J N là biến phi cơ sở.  Phương án cơ sở được gọi là phương án cơ sở chấp nhận được nếu như nó là phương án chấp nhận được. Bài toán đối ngẫu của (TT0) là  by → max g ( y) =  T  A y ≤ c  Ta gọi phương án cơ sở đối ngẫu tương ứng với cơ sở B là vectơ y thu được bằng cách giải hệ phương trình sau: yT B = cB (tức là y = cBT B −1 ).  Cơ sở B được gọi là chấp nhận được đối ngẫu, nếu phương án cơ sở đối ngẫu tương ứng với nó là phương án chấp nhận được của bài toán đối ngẫu. 14 2.1. Thuật toán đơn hình dạng bảng 2.1.1. Thuật toán Đầu vào: Bài toán quy hoạch tuyến tính (QHTT)  c, x → min  (TT0 )  Ax = b x ≥ 0  {a trong đó A= A ( I , J )= ij : i ∈ I , j ∈ J } , I= {1, 2,..., m} , J= {1, 2,..., n} với giả thiết i/ rank A = m ; D ii/ = = { x : Ax b, x ≥ 0} ≠ ∅ ; iii/ Biết một phương án cơ sở chấp nhận được x với cơ sở tương ứng là = B A , A ,..., A } , J { j , j ,..., j } . {= j1 j2 jm B 1 2 m Đầu ra: Kết luận hàm mục tiêu của bài toán không bị chặn dưới hoặc là xuất ra phương án tối ưu x* và giá trị tối ưu f ( x* ) . Các số liệu cần thiết ở mỗi bước lặp sẽ ghi trong bảng sau Bảng 2.1 Bảng đơn hình c j cơ Cơ sở sở Phương án c1 A1 … … cj Aj … … cn θi An c j1 A j1 x j1 x j1 j θj … … … … … θi … ci Ai xi xij … … … … c jm Ajm x jm x jm j ∆j ∆ Cột đầu tiên của bảng ghi hệ số hàm mục tiêu của các biến cơ sở. Cột thứ hai ghi tên các cột trong cơ sở. 15 1 θj m Cột thứ ba ghi các giá trị của các biến cơ sở (các thành phần của vectơ xB= {x j : j ∈ J B }= B −1b ). Các cột tiếp theo: các phần tử xij , i ∈ J B của bảng được tính theo công thức: ( x , i ∈ J=) ij B B −1 Aj= , j 1, 2,.., n Cột cuối cùng dùng để ghi các tỉ số θi . Dòng đầu tiên của bảng ghi hệ số hàm mục tiêu của các biến ( c j ) tương ứng với các cột (A ). j Dòng tiếp theo ghi tên các cột A1 ,..., An . Dòng cuối cùng gọi là dòng ước lượng, các phần tử của nó tính theo công thức: = ∆j ∑c x i∈J B i ij −= c j , j 1,..., n Có thể thấy rằng ∆ j= 0, j ∈ J B Các bước lặp Bước 1: -Nếu ∆ j ≤ 0, j = 1,..., n thì phương án cơ sở chấp nhận được đang xét là tối ưu. Thuật toán kết thúc. -Trái lại chuyển sang bước 2. Bước 2: -Nếu có ∆ j > 0 và x jj ≤ 0, j ∈ J B thì hàm mục tiêu của bài toán là không bị chặn dưới. 0 0 Thuật toán kết thúc. -Trái lại, tìm ∆= j 1,..., n} > 0 . max {∆ j := j 0  xi  , xij0 > 0 ,i ∈ JB = Tính θi  xij0  +∞, x ≤ 0 ij0  Tìm i0 sao = cho θi0 min {θi : i ∈ J B } Chuyển sang Bước 3. Bước 3: i/ Các phần tử dòng i0 trong bảng mới xi j ( ) 0 bảng cũ chia cho phần tử xi j : = xi j 0 0 0 xi0 j xi0 j0 16 , j∈J bằng các phần tử tương ứng trong ii/ Các phần tử ở vị trí cột j0 trong bảng mới, ngoại trừ phần tử nằm trên vị trí xi 0 j0 bằng 1, còn tất cả là bằng 0. ( ) iii/ Các phần tử cần tính còn lại trong bảng mới xij , ∆ j được tính từ các phần tử tương ứng trong bảng cũ theo công thức sau: x ij =xij − ∆ j =∆ j − xi0 j xij0 xi0 j0 , i ∈ J B ( i ≠ i0 ) , j ∈ J ( j ≠ j0 ) xi0 j ∆ j0 xi0 j0 , j ∈ J ( j ≠ j0 ) Các công thức trên dễ dàng ghi nhớ nhờ các hình chữ nhật sau: Quay lại Bước 1. Thuật toán đơn hình hai pha Đầu vào: Xét bài toán (QHTT) (TT0 )  c, x → min   Ax = b x ≥ 0  1, 2,...m Không giảm tổng quát ta có thể giả thiết rằng bi ≥ 0, i = (nếu có bi < 0 chỉ cần nhân hai vế của phương trình tương ứng với −1 ). Đầu ra: Kết luận bài toán không có phương án chấp nhận được hoặc là hàm mục tiêu của bài toán không bị chặn dưới hoặc là xuất ra phương án tối ưu x* và giá trị tối ưu f ( x* ) . Ta đặt bài toán phụ sau: 17 (TT ) 0  e, xu → min  b  Ax + xu =  x ≥ 0, x ≥ 0 u  x ( J u ) , J u =+ Trong đó: xu = {n 1,..., n + m} là m − vectơ các biến giả, e = (1,1,...,1) là m − vectơ có các thành phần đều bằng 1. ( ) x ( J ) 0,= x ( J u ) b với cơ sở Bài toán TT0 có một phương án cơ sở chấp nhận được của là= tương ứng B = { An +1 ,..., An + m } trong đó kí hiệu Aj , j ∈ J u là các vectơ cột trong ma trận ràng ( ) buộc của bài toán TT0 ứng với các biến giả x j , j ∈ J u . Pha thứ nhất: ( ) -Dùng thuật toán đơn hình 2.1.1 giải bài toán TT0 . -Kết thúc pha thứ nhất ta xây dựng được phương án cơ sở chấp nhận được tối ưu ( x* , xu* ) với cơ sở tương ứng là = B* {A j ( ) : j ∈ J B* } của bài toán TT0 . -Khi đó xảy ra 1 trong 3 trường hợp sau: i/ xu* ≠ 0 Kết luận: bài toán (TT0 ) không có phương án chấp nhận được. Thuật toán kết thúc. ii/ xu* = 0 và ma trận B* không chứa các cột ứng với biến giả, tức là nó chứa toàn cột của ma trận ràng buộc của bài toán (TT0 ) : B* = ∅. { Aj : j ∈ J B* } , J B* ∩ J u = Trường hợp này x* là phương án cơ sở chấp nhận được của bài toán (TT0 ) với cơ sở tương ứng là B* . Chuyển sang pha thứ hai. iii/ xu* = 0 và ma trận B* có chứa cột ứng với biến giả, tức là= B* {A j : j ∈ J B* } , J B* ∩ J u ≠ ∅ . - Kí hiệu xi* , i* ∈ J B* ∩ J u là một thành phần biến giả trong phương án cơ sở chấp nhận được ( ) tối ưu ( x* , xu* ) của bài toán TT0 . - Kí hiệu xi j , j ∈ J ∪ J u là các phần tử của dòng i* trong bảng đơn hình tương ứng với * ( ) phương án tối ưu ( x* , xu* ) của bài toán TT0 . 18
- Xem thêm -

Tài liệu liên quan