Giáo trình Quy hoạch tuyến tính: Phần 1

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:100

Thêm vào BST

Báo xấu

171
lượt xem 46
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 1 giáo trình "Quy hoạch tuyến tính" của tác giả Trần Xuân Sinh gồm 3 chương: Chương 1 - Bài toán quy hoạch tuyến tính, chương 2 - Tính chất bài toán quy hoạch tuyến tính, chương 3 - Phương pháp đơn hình. Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Quy hoạch tuyến tính: Phần 1

t ) u H Ọ C VINH TRUNG TÁM mõm TIN-THƯV1ỆN 4N X U Â N S I N H 519.3 TS 274q/ 03 DT.009345 Quy hoạch SP NHÀ XUẤT BẢN ĐẠI H Ọ C s ư PHÀM
T R Ấ N XUÂN SINH Q U Y H O Ạ C H T U Y Ế N TÍNH • NHÀ X U Ấ T BẢN ĐAI H O C sư PHÀM
Mã số: 01.01-57/103 - ĐH 2003
MỤC L Ụ C trang Lời nói đầu 5 C h ư ơ n g 1. Bài t o á n quy hoạch t u y ế n t í n h 7 §1. Mơ đ ầ u 7 §2. Bài toán quy hoạch tuyên tính 8 §3. Mô t ả hình học bài toán quy hoạch tuyến tính và thuật toán đồ thị 16 Câu hỏi và bài tập chướng Ì 19 C h ư ơ n g 2. T í n h c h ấ t b à i t o á n quy hoạch t u y ế n t í n h 22 §1. Một số vấn để cớ bản của giải tích l ồ i 22 §2. Tính chất bài t o á n quy hoạch tuyến tính 39 §3. Cặp bài toán đối ngẫu 48 Câu hỏi và bài tập chương 2 62 Chương 3. P h ư ơ n g p h á p đ ơ n h ì n h 69 §1. Cơ sụ lý luận của phương p h á p 69 §2. Công thức biến đổi và bảng đơn hình 77 §3. Thuật toán đớn h ì n h và ví dụ 80 §4. Tìm phương án cực biên xuất phát 83 §5. Tính hữu hạn của t h u ậ t toán đơn h ì n h 87 Câu hỏi và bài tập chương 3 93 3
Chương4. Các p h ư ơ n g p h á p đơn h ì n h đ ặ c biệt 99 §1. Phương pháp đơn hình cải biên 99 §2. Phương pháp đơn hình đối ngẫu 104 §3. Phương pháp phân phối 112 Câu hỏi và bài tập chương 4 126 Chương 5. Một sô v â n đ ể k h á c liên quan b à i t o á n quy hoạch t u y ê n t í n h 128 §1. Độ phức tạp tính toán của thuật toán đơn hình 128 §2. Bài toán quy hoạch nguyên 130 §3. Thuật toán Khachiart và thuật toán điểm trong Karmarkar giải bài toán quy hoạch tuyến tính 151 §4. Thuật toán Frank-Wolfe giải bài toán quy hoạch lồi vối ràng buộc tuyến tính 170 Câu hỏi và bài tập chương 5 174 Tài l i ệ u tham khảo 177 4
L Ờ I NÓI Đ Ầ U Một số giáo t r ì n h quy hoạch tuyến tính trong những n ă m qua gần như chi dừng l ạ i ỏ những k ế t quả từ trước những n ă m 50. Trong sự p h á t t r i ể n của khoa học ngày nay. chúng ta không thê không nói tới một số t h à n h tựu mới gần đây (kê cả lý t h u y ê t và ứng dụng). Ngày nay, k h i nói đèn phương pháp giải một bài t o á n , người ta quan t â m nhiều đến độ phức tạp tính toán của nó. Độ phức tạp tính toán ỏ đây thông thường xét theo hai mật: Tốc độ tính toán và dung lượng bộ nhớ. cả hai đều phụ thuộc vào độ dài dữ l i ệ u cở k của bài toán. Ta sẽ gọi t h u ậ t toán A có độ phức tạp T (k) thời gian đa thức nếu A t ồ n t ạ i đa thức P (k) sao cho T (k) < P (k). Trong trường m A m hợp còn l ạ i . ta nói t h u ậ t toán A có độ phức tạp thời gian mũ. Cho đến nay. người ta thấy rằng thuật toán đơn hình (1949) có độ phức tạp tính toán thời gian mũ. N ă m 1979, Khachian (nhà toán học Nga) đã đưa ra thuật toán Ellipsoid, với thời gian đa thức. Và n ă m 1984, Karmarkar (nhà toán học Mỹ) công bố thuật toán điểm trong, cũng với thòi gian đa thức. Với k ế t quả của Khachian và Karmarkar đã chỉ ra r ằ n g bài toán quy hoạch tuyến tính thuộc lớp bài t o á n có độ phức tạp thòi gian đa thức. Kết quả đó đ ậ t ra câu hỏi: phải chăng t h u ậ t toán đơn hình kém hơn các 5
thuật toán vừa nêu? Người ta nhận thấy rằng với những bài toán cỡ vừa, thường gặp, xét theo độ phức tạp trung bình thì t h u ậ t toán đơn hình vẫn t h ế h i ệ n t í n h ưu việt của nó. Tuy nhiên, người ta hy vọng rằng trong tương lai, với những bài toán cỡ lớn thì các t h u ậ t toán Ellipsoid và điểm trong sẽ có lợi t h ế hơn nhiều. Vì vậy, c h ú n g tôi sẽ giới t h i ệ u sơ lược một sứ k ế t quả mới trong phạm vi cho phép của cuứn sách. Trong cuứn sách này, chúng ta chủ yêu đi sâu nghiên cứu bài toán quy hoạch tuyến tính. Ngoài ra. chúng tôi cũng sẽ để cập đến một sứ v ấ n đề mỏ rộng khác có liên quan với quy hoạch tuyến t í n h như: quy hoạch nguyên, quy hoạch l ồ i . . . nhằm làm cho sinh viên h i ể u biết t h ê m một sứ lứp bài toán rộng hơn (trong k h i chưa có điều k i ệ n t r ì n h bày lý thuyết t ứ i ưu). Do vậy, chương t r ì n h bộ môn Quy hoạch tuyến t í n h không nhất t h i ế t p h ả i có chương 5. Trong trường hợp này, chương 5 được xem như phần phụ lục tham khảo. Đe t h u ậ n t i ệ n cho người đọc, sau mỗi chương chúng tôi có đưa ra hệ thứng câu hỏi và bài tập ôn luyện. Để đọc được cuứn sách này, độc giả cần biết các k i ế n thức cơ bản về Đ ạ i sứ tuyên tính, H ì n h học giải tích và Giải tích cổ điển. Tác giả 6
Chương 1. BÀI TOÁN QUY HOẠCH TUYÊN TÍNH §1. Mở đầu Từ khi loài người biết tính toán làm ăn, con người phải thường xuyên tìm câu trả lời cho bài toán: Làm t h ế nào đê công việc đ ạ t được sự mong muốn, t r ê n cơ sở những điểu k i ệ n h i ệ n có. Sự mong muốn của con người là vô cùng, n h ư n g điều k i ệ n bao giờ cũng có hạn. Vậy làm t h ế nào để đ ạ t được sự mong muốn, trên cơ sở những điều k i ệ n có hạn ây. N h i ề u câu chuyện lịch sử của t h ế giới cũng như của nước ta đã chỉng tỏ trí tuệ tuyệt vời của các nhà bác học g i ả i quyết những bài toán n h ư vậy (xem [1], [2], [3]). Tuy n h i ê n chỉ mới vào những năm 40 của t h ê kỷ 20, những vấn đề lý l u ậ n h o à n chỉnh mới được p h á t t r i ể n mạnh mẽ, trở t h à n h bộ môn khoa học lý luận và ỉng dụng có hiệu quả, đó là Lý thuyết quy hoạch toán học. N h à toán học Liên xô (cũ) Kantorovich, người được giải thưởng Nôbel về kinh t ế n ă m 1975, từ n ă m 1939, l ầ n đầu t i ê n đã công bố những công t r ì n h khoa học về kê hoạch hoa và điều k h i ể n sản xuất vối các p h ư ơ n g p h á p giải t ố i ưu. Đặc biệt, sau các công t r ì n h của Dantzig, n h à toán học M ỹ , tác giả của 7
p h ư ơ n g p h á p đ ơ n h ì n h được c ô n g b ố n ă m 1949, bộ m ô n Lý t h u y ế t quy hoạch được p h á t t r i ể n n h a n h c h ó n g . D ạ n g t ổ n g q u á t của b à i t o á n quy hoạch là: T ì m vectơ X = (X), x , 2 x„), l à m cực t i ể u (hoặc cực đ ạ i ) h à m s ố f ( X ) , v ớ i các đ i ề u k i ệ n gi(X) < 0, i = 1,2,..., m; Xị > 0, j = Ì , 2, k. k < n. Tức là c ầ n g i ả i b à i t o á n min(max)f(X) (1.1) . . í e g,(X) < 0 , 1 = 1 , 2,..., m (1.2) Với điêu kiện i [ Xj > 0, j = Ì , 2,..., k , k < n . (1.3) H à m f(X) gọi là hàm mục tiêu, các đ i ề u k i ệ n (1.2)(1.3) g ọ i là điều kiện buộc của b à i t o á n . M ỗ i vectơ X = ( X j ) e IR" t h o a m ã n h ệ đ i ề u k i ệ n buộc gọi là m ộ t phương án. Ta k ý h i ệ u t ừ p p h ư ơ n g á n l à M . M ộ t p h ư ơ n g á n l à m cực t i ể u (hoặc cực đại) h à m mục t i ê u gọi là phương án tối ưu (hoặc gọi là nghiệm) của bài toán. D ễ d à n g c h ứ n g m i n h (xem n h ư b à i t ừ p ) h a i b à i t o á n sau đ â y là t ư ơ n g đ ư ơ n g : minf(X) [ max (g(X) = - f ( X ) } và ị X 6 M [ X e M. Vì v ừ y , t ừ nay v ề sau ta chỉ x é t t r ư ờ n g hợp min f(X). T u y theo h à m f(X) hoặc t ừ p M m à n g ư ờ i t a c h i a b à i t o á n (1.1)(1.2)(1.3) t h u ộ c các lớp b à i t o á n k h á c n h a u (xem các t ả i l i ệ u t h a m k h ả o ) . 8
Đặc biệt, khi f(X) và gj(X) (ì = 1. 2,..., m) là các h à m tuyên tính, M cz IR" thì bài toán đã cho được gọi là bài toán quy hoạch tuyến tính (bt qhtt). §2. B à i t o á n quy h o ạ c h t u y ế n t í n h Ví d ụ 1. Bài toán lập kê hoạch sản xuất Một cơ sở có thê sản xuất hai loại sản phẩm A và B, từ các nguyên liệu ì, l i . H I . Chi phí từng loại nguyên liệu và t i ề n lãi của một đơn vị sản phẩm, cũng như dự trầ nguyên liệu cho trong bảng sau đây: Bảng 1. ^ ^ ^ ^ N g u y ê n liệu ì li IU Lãi Sản phẩm ^^"^--^^ A 2 0 1 3 B 1 1 0 5 Dự t r ầ 8 4 3 Hãy lập bài toán t h ể hiện kê hoạch sản xuất sao cho có tống sô lãi lốn nhất, t r ê n cơ sở dự trầ nguyên liệu đã có. Gọi X , y l ẩ n lượt là số sản phẩm A và B được sản xuất (x, y > 0, đơn vị sản phẩm). K h i đó ta cần tìm X , y > 0 sao cho đ ạ t lãi lốn nhất f(X) = 3x + 5y —> max với điều kiện nguyên l i ệ u 2x + y < 8 9
Ly < 4 l.x < 3. Tức là ta cần giải bài toán max |f(X) = 3x + 5y} 2x + y < 8 y 0. Ví d ụ 2. Bài toán p h â n công lao động Một lớp học cần tổ chức lao động với hai loại công việc: xúc đất và chuyển đất. Lao động của lóp được chia làm 3 loại A, B, c, với số lượng l ầ n lượt là 10, 20, 12. N ă n g suất của từng loại lao động t r ê n từng công việc cho trong bảng sau đây: Bảng 2. — L a o động A (10) B (20) C(12) Công việc Xúc đất 6 5 4 Chuyển đất 4 3 2 Hãy tổ chức lao động sao cho có tổng n ă n g suất lớn nhất. B n g kinh nghiệm, độc giả t h ử tìm cách p h â n công lao động hợp lý nào đó và so s á n h các k ế t quả để thấy được sự t h i ế t thực của t í n h toán có lợi. 10
L ậ p b à i t o á n : G ọ i x,j l à sô l a o đ ộ n g l o ạ i j l à m c ô n g v i ệ c i ( j = Ì , 2, 3; Ì = Ì , 2; x„ > 0. n g u y ê n ) . K h i đ ó n ă n g s u ấ t lao đ ộ n g c ủ a c ô n g v i ệ c đ à o đ ấ t sẽ l à 6 X ị ! + ÕX]., + 4x , i : i c ò n c h u y ê n đ ấ t sẽ l à 4 x , + 3x-r, + 2 x 2 2 ; i . Dễ dàng thấy rằng đê có năng suất lớn nhất thì k h ô n g t h ê có l a o đ ộ n g d ô i t h ừ a . t ứ c l à p h ả i c â n b à n g g i ữ a 2 công v i ệ c . Vì v ậ y tu có b à i toán (tạm bỏ qua điều kiện nguyên) max (6x n + 5x,2 + 4JC ) 13 6 x + õx,2 + 4 x n 1 3 - 4x - 3x 2 1 2 2 - 2x 2 3 = 0 Xu + x 2 1 = 10 với điều kiện x 1 2 + X,., = 20 x 1 3 + x 2 3 = 12 Xy > 0, i = Ì , 2; j = Ì , 2. 3. V í d ụ 3. B à i t o á n k h ẩ u p h ầ n t h ứ c ă n M ộ t k h ẩ u p h ầ n t h ứ c ă n có k h ố i l ư ợ n g p , có t h ể c ấ u t ạ o t ừ n l o ạ i t h ứ c ă n . G i á mua m ộ t đ ơ n vị t h ứ c ă n l o ạ i j là Cj. Đ ể đ ả m bảo cơ t h ể p h á t t r i ể n b ì n h t h ư ờ n g t h ì khẩu p h ầ n cần m loại chất dinh dưõng. C h ấ t dinh dưỡng t h ứ i c ầ n tôi t h i ể u cho k h ẩ u p h ầ n là b ị v à có t r o n g m ộ t đ ơ n vị t h ứ c ă n l o ạ i j là ãịị. H ỏ i n ê n cấu tạo một k h ẩ u p h ầ n thức ă n n h ư t h ê n à o đ ế ă n đ ủ no, đ ủ c h ấ t d i n h d ư ỡ n g m à có g i á t h à n h r ẻ n h ấ t . li
Lập bài toán: Gọi X, (x, > 0) là số đơn vị thức ăn loại j được cấu tạo trong k h â u phần. K h i đó giá t h à n h của khẩu phần là n f(X) = ^ c,x, —> min. j=i Đồng thời phải thoa m ã n điêu k i ệ n đủ no va đủ chất n n a x X, = p, i) j - b,, i = Ì, 2. .... m. j=i j=l Ta có bài toán min f(X) = ]T CjXj} j=i n =p z^ j=l n với điều kiên < a,jXj > b„ i = Ì, 2, m j=i L X; > 0. j = Ì, 2, .... n. Qua ba ví dụ đã nêu, cho t h ấ y c h ú n g thuộc lớp bài toán quy hoạch tuyến t í n h tông q u á t là min {f(X) = ^ CjXj j=i 12
Y a„x, = b, , i = Ì, 2, k j=i n VỐI đ i ê u k i ê n < 2 a„x., > b,. i = k+1, m j=i X, > 0, j = 1. 2, r, r < n. Trong trường hợp đặc biệt. bài toán quy hoạch tuyến tính có dạng min (f(X) = 2_! c j x ; (1.4) j=i ]T a Xị Ví = b, , Ì = Ì, 2, m (1.5) vối điều kiên < j=i I X, > 0, j = Ì, 2, n. (1.6) Bài t o á n có dạng (1.4)(1.5)(1.6) được gọi là bài toán quy hoạch t u y ế n t í n h dạng chính tắc. Chú ý r ằ n g b à i toán quy hoạch tuyến tính tống quát có t h ể đưa vê bài toán quy hoạch t u y ê n tính dạng chính tắc tương đương nhờ các quy tắc sau đây (xin dành cho độc giả phần chứng minh tương đương). + Nếu có max f(X) thì đối t h à n h min {- f(X)}. n n + N ế u có b ấ t đẳng thức ^ a.jX, > b, hoặc a,jXj < j=i j=i bị t h ì ta đưa t h ê m ẩn phụ x n + 1 > 0, với hệ số hàm mục tiêu c = 0 để có n+i 13
ti ^ a.jXj - x„ , = b, + hoặc y\ a Xj ụ +x n+1 = bị 3=1 J=1 + Nếu có ẩn x chưa r à n g buộc về dấu, t h ì có t h ể thay k nó bởi hai biến mới x ' và x " không âm, theo công thức: k k x = x x k k' ' k • Ví dụ: Đưa bài toán sau đâv về dạng chính tắc min (x, - X; - x) 3 X, + x 2 + X;j = 5 vối điều kiê n < 2x, + X, 4 3 Xu Xa > 0. Ta đưa thêm ẩn phụ x.|, x > 0 và thay x bởi X ọ ' . X ọ " 5 2 không âm, v ố i X., = x ' 2 - X./' đ ể có min (x, - Xọ' + x " -x ) 2 :j X, + x ' 2 - x " 2 + X;ị - 5 với điều kiện X, - 2x ' + 2x " + 2 2 x : ì + X., =3 X, + X," X, =4 X|. Xọ' ,x" . 2 X;;. X . , , x f) > 0. Như vậy, tờ nay về sau ta chỉ cần nghiên cứu bài toán quy hoạch tuyến tính ở dạng chính tắc. Trong trường hợp cần thiết, chúng ta sẽ nhắc l ạ i với các dạng khác nhau. Để thuận lợi trong t r ì n h bày. chúng ta đưa ra các cách viết khác nhau của bài toán (1.4)(1.5)(1.6) n h ư sau: 14
• D ạ n g ma t r ậ n Ký h i ệ u ma t r ậ n h à n g c = (c, Cọ ... c„)i, „ v à các ma trận: X = (X] x ... x„) 2 n x] T b = (b, b , ... b ) m m x , = a A ( i j ) m x li t r o n g đó T ký h i ệ u cho p h é p c h u y ể n vị ma t r ậ n . Ta có b à i t o á n min cx AX = b với đ i ể u k i ê n x>0. • D ạ n g vectơ Ký h i ệ u các vectơ c = (c,. Cọ. c„) X = (x„ X, x„) Ao = ( b „ b,. b ) m Aj = (à,,, a j, .... a j ) , ì = Ì, , 2 m : Ta có b à i t o á n m i n (C, X ) X , A , + X . A . Ị + ... + x„A = A„ n với đ i ể u k i ệ n Xj, x , 2 x„ > 0. 15
§3. Mô tả h ì n h học bài t o á n quy hoạch tuyến t í n h và thuật t o á n đ ồ thị 1.3.1. Nhận xét 2 Trong không gian R với hệ trục toa độ vuông góc xOy, ta có: + Phướng t r ì n h ax + by = c, biểu diễn đường thẳng vuông góc vối vectơ pháp tuyên n(a, b). + Các điểm (x, y) thoa m ã n ax + by < c nằm trên nửa mặt phang giới hạn bởi đường thẳng ax + by = c. + Phương t r ì n h ax + by = f, k h i f thay đối sẽ cho ta họ đường thắng song song vối vectơ chậ phương V (b, - a). Giá trị f càng lớn khi dịch chuyển các đường thẳng của họ theo phương fi(a, b). Vì vậy, hình ảnh hình học của bài toán quy hoạch tuyến tính trong ÍR2 được mô tả theo thuật toán đồ thị như sau. 1.3.2. Thuật toán đồ thị Bước 1. Biểu diễn các điêu kiện buộc của bài toán lên mặt phang toa độ vuông góc xOy. Xác định tập phương án M . Bước 2. Biểu diễn phương của h à m mục tiêu c,x + c,y = f, bằng cách cho f một giá trị f„ nào đó. Đường thắng C]X + c y = f được gọi là đường mức. 2 0 Bước 3. Tịnh tiên song song đường mức trên tập phương án để tìm phương án t ố i ưu. 16
Chú ý rằng, thay vì xác định vectơ n(c Cọ), hướng u tăng, ta có t h ể kiểm tra giá trị h à m mục tiêu ở gốc toa độ 0(0,0). Ví dụ 1. Ta xét ví dụ Ì đã nêu ở §2 vối bài toán max (f(X) = 3x + 5y} 2x + y < 8 y 0. Trên hình Ì, đa giác OABCD là tập phương án. Đường mức 3x + 5y = 15 (đường chấm). Rõ r à n g f majr = f(B) = f(2, 4) = 26. Phương án t ố i ưu là: Hình Ì x,. = B = (2, 4). ư ơ ví dụ trên, nếu t h ê m điêu k i ệ n 2x + y > 9 thì tập phương án rỗng (bài toán không có phương án t ố i ưu). Ví dụ 2. Xét bài toán min {f(X) = Xi -x} 2 - 2x, + x < 4 2 với điêu kiên < Xi - 2x < 2 2 X,, x 2 > 0. 17
Tập phương án M của bài toán là miền l ồ i không bị chặn (Hình 2). Đường mức X] - x = - 2. 2 Dịch chuyên đường mức, ta n h ậ n thấy f không bị chặn t r ê n tập phương án (bài toán không có phương án t ố i ưu). Độc giả có t h ể k i ể m tra thấy rằng vối ví dụ 2, n h ư n g thay cực đ ạ i h à m mục tiêu Hình 2 f = - 2xj + x 2 thì phưừng án t ố i ưu lúc này là đỉnh A(0, 4). Hơn t h ế nữa, t ấ t cả các điểm trên tia xuất p h á t từ A song song vối đường mức đều t ố i ưu ( f = 4). m a x Nhận x é t : Từ các ví dụ đã nêu trong R' , ta có các k ế t 1 luận (ta sẽ chứng minh các nhận xét n à y trong các chương sau). 1. Tập phương án có t h ể rỗng (0) hoặc khác rỗng. 2. Tập phương án là một miền l ồ i (hoặc là đa giác l ồ i hoặc là miền l ồ i không bị chặn). 3. Nêu bài toán có phương án t ố i ư u t h ì ít nhất có một đỉnh của miền l ồ i t ố i ưu. 4. Nếu tập phương án là đa giác l ồ i t h ì chắc chắn có một đỉnh t ố i ưu. 18