Khóa luận tốt nghiệp đại học: Một số ứng dụng của bài toán quy hoạch tuyến tính

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

Thêm vào BST

Báo xấu

2
lượt xem 1
download

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

Khóa luận tốt nghiệp đại học "Một số ứng dụng của bài toán quy hoạch tuyến tính" trình bày các nội dung chính sau: Các kiến thức cơ sở; Một số ứng dụng của bài toán quy hoạch tuyến tính. Đối tượng nghiên cứu: Ứng dụng của bài toán quy hoạch tuyến tính giải một số bài toán trong đời sống thực tế.

Chủ đề:

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

Lưu

Nội dung Text: Khóa luận tốt nghiệp đại học: Một số ứng dụng của bài toán quy hoạch tuyến tính

UBND TỈNH QUẢNG NAM TRƢỜNG ĐẠI HỌC QUẢNG NAM KHOA TOÁN ---------- PHẠM THỊ THÚY NGA MỘT SỐ ỨNG DỤNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH KHÓA LUẬN TỐT NGHIỆP Quảng Nam, tháng 5 năm 2018
UBND TỈNH QUẢNG NAM TRƢỜNG ĐẠI HỌC QUẢNG NAM KHOA TOÁN ---------- KHÓA LUẬN TỐT NGHIỆP Tên đề tài: MỘT SỐ ỨNG DỤNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Sinh viên thực hiện PHẠM THỊ THÚY NGA MSSV: 2114020134 CHUYÊN NGÀNH: SƢ PHẠM TOÁN KHÓA: 2014 – 2018 Cán bộ hướng dẫn TH.S PHẠM NGỌC HOÀNG Quảng Nam, tháng 5 năm 2018
LỜI CẢM ƠN Trong suốt quá trình làm khóa luận, tôi luôn nhận được sự hướng dẫn và giúp đỡ của ThS. Phạm Ngọc Hoàng. Tôi xin chân thành bày tỏ lòng cảm ơn sâu sắc đến thầy. Đồng thời, tôi xin chân thành cảm ơn quý thầy, cô trong khoa đã tạo điều kiện cho tôi được nghiên cứu nhiều kiến thức bổ ích trong khoa học và cuộc sống. Mặc dù đã có nhiều cố gắng nhưng khóa luận khó tránh khỏi những thiếu sót. Vậy mong các thầy cô giáo đóng góp ý kiến để khóa luận được hoàn thiện hơn. Xin trân trọng cảm ơn! Tam Kì, ngày 18 tháng 5 năm 2018 Sinh viên thực hiện Phạm Thị Thúy Nga
LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của bản thân tôi và được sự hướng dẫn khoa học của ThS. Phạm Ngọc Hoàng. Các nội dung nghiên cứu, kết quả trong đề tài này là trung thực và không phải sao chép từ bất kỳ tài liệu nào. Nếu không đúng như đã nêu trên, tôi xin hoàn toàn chịu trách nhiệm về đề tài của mình. Tam Kì, ngày 18 tháng 5 năm 2018 Ngƣời cam đoan Phạm Thị Thúy Nga
MỤC LỤC Chƣơng 1. CÁC KIẾN THỨC CƠ SỞ ................................................................................... 1 1.1. Bài toán quy hoạch tuyến tính .......................................................................................... 1 1.1.1. Khái niệm bài toán quy hoạch tuyến tính .................................................................... 1 1.1.2. Một số kết quả từ giải tích lồi ........................................................................................ 5 1.1.3. Một số tính chất của bài toán quy hoạch tuyến tính ................................................... 8 1.2. Phƣơng pháp đơn hình giải bài toán quy hoạch tuyến tính. ......................................... 9 1.2.1. Cơ sở lí luận .................................................................................................................... 9 1.2.2. Phƣơng pháp đơn hình giải bài toán quy hoạch tuyến tính ..................................... 10 1.3. Bài toán đối ngẫu ............................................................................................................. 14 1.3.1. Khái niệm bài toán đối ngẫu........................................................................................ 14 1.3.2. Định lý độ lệch bù ......................................................................................................... 16 1.4. Bài toán vận tải ................................................................................................................ 17 1.4.1. Khái niệm bài toán vận tải ........................................................................................... 17 1.4.2. Tính chất của bài toán vận tải ..................................................................................... 18 1.4.3. Thuật toán thế vị giải bài toán vận tải ........................................................................ 18 Chƣơng 2. MỘT SỐ ỨNG DỤNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ...... 22 2.1. Bài toán trò chơi .............................................................................................................. 22 2.1.1. Trò chơi có nghiệm ổn định ......................................................................................... 23 2.1.2. Trò chơi không có nghiệm ổn định ............................................................................. 28 2.2. Bài toán vận tải có hàm mục tiêu dạng cực đại ............................................................ 34 2.3. Bài toán có ô cấm ............................................................................................................. 38 2.4. Bài toán xe rỗng ............................................................................................................... 45 2.5. Bài toán bổ nhiệm ............................................................................................................ 47
Phần 1. MỞ ĐẦU 1.1. Lí do chọn đề tài 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 hầu hết đến các lĩnh vực khoa học – công nghệ và kinh tế.... Cùng với sự phát triển mạnh mẽ của khoa học máy tính thì các lĩnh vực của tối ưu hóa ngày càng phát triển và đa dạng. Chính vì vậy, tối ưu hóa ngày càng được các nhà toán học quan tâm và có tầm quan trọng trong đời sống xã hội. Khi con người tạo ra các sản phẩm cần thiết để phục vụ cho nhu cầu của đời sống xã hội thì việc trao đổi hàng hóa cần có sự tính toán. Từ đó con người phải tính toán để tìm ra phương pháp sao cho có lợi nhất cho mình theo những mục đích xác định. Do đó đã xuất hiện một bài toán cần phải giải quyết, đó là bài toán tìm quyết định tối ưu. Để giải quyết một cách có hiệu quả bài toán ấy, trước hết cần phải xây dựng một mô hình toán học cho nó, trên đó thể hiện được bản chất của mỗi đối tượng đã được khảo sát và sự liên quan giữa chúng, đương nhiên cần phải chỉ rõ mục tiêu mong muốn đạt được. Hiện nay, tối ưu hóa nói chung hay quy hoạch tuyến tính (QHTT) nói riêng được đưa vào giảng dạy trong nhiều chương trình đào tạo đại học cho các ngành khoa học cơ bản, kỹ thuật – công nghệ, kinh tế… Với thời lượng có 2 tín chỉ thì sinh viên chỉ được học được những nội dung cơ bản của QHTT còn phần nội dung chuyên sâu thì sinh viên tự nghiên cứu. Ngoài những bài toán tối ưu đã được học, hiện nay chúng tôi thấy có nhiều bài toán khác có ứng dụng rộng rãi trong thực tế cần đến công cụ quy hoạch tuyến tính để giải quyết như bài toán trò chơi, bài toán bổ nhiệm, bài toán xe rỗng, bài toán có ô cấm, bài toán vận tải có hàm mục tiêu dạng cực đại…Vì vậy, với một sinh viên sư phạm chuyên ngành toán học muốn nghiên cứu sâu hơn lĩnh vực của QHTT dưới sự hướng dẫn của giảng viên, tôi đã chọn đề tài: “Một số ứng dụng của Bài toán quy hoạch tuyến tính” để làm khóa luận tốt nghiệp của mình. Chúng tôi hy vọng khóa luận sẽ giúp sinh viên có thể giải quyết các bài toán thực tế và tìm ra được các quyết định tối ưu để phục vụ cho nhu cầu của đời sống xã hội. 1.2. Mục tiêu nghiên cứu Nghiên cứu một số bài toán tối ưu có nhiều ứng dụng trong thực tế. Sử dụng lý thuyết của quy hoạch tuyến tính và thuật toán giải phù hợp đối với từng bài toán trên.
1.3. Đối tƣợng và phạm vi nghiên cứu Đối tượng nghiên cứu: Ứng dụng của bài toán quy hoạch tuyến tính giải một số bài toán trong đời sống thực tế. Phạm vi nghiên cứu: Lĩnh vực Quy hoạch tuyến tính. 1.4. Phƣơng pháp nghiên cứu Nghiên cứu tài liệu, đọc hiểu tài liệu. Phân tích, tổng hợp các kiến thức. Trao đổi, thảo luận với giảng viên hướng dẫn. 1.5. Đóng góp của đề tài Cung cấp phương pháp, thuật toán để giải các bài toán tối ưu bằng công cụ của QHTT. Khóa luận có thể sử dụng như một tài liệu tham khảo để các giáo viên, sinh viên nghiên cứu, bồi dưỡng chuyên môn, nâng cao kiến thức. 1.6. Cấu trúc đề tài Khóa luận gồm phần mở đầu, kết thúc và hai chương: - Chương 1: Các kiến thức cơ sở - Chương 2: Một số ứng dụng của bài toán quy hoạch tuyến tính Phần tài liệu tham khảo.
Phần 2. NỘI DUNG Chƣơng 1. CÁC KIẾN THỨC CƠ SỞ 1.1. Bài toán quy hoạch tuyến tính 1.1.1. Khái niệm bài toán quy hoạch tuyến tính  Dạng tổng quát của bài toán quy hoạch tuyến tính Xét bài toán thực tế như sau: Trong một cuộc thi gói bánh vào dịp năm mới, mỗi đội chơi được sử dụng tối đa 20 kg gạo nếp, 2 kg thịt ba chỉ, 5 kg đậu xanh để gói bánh chưng và bánh ống. Để gói một cái bánh chưng cần 0,4 kg gạo nếp, 0,05 kg thịt và 0,1 kg đậu xanh; để gói một cái bánh ống cần 0,6 kg gạo nếp, 0,075 kg thịt và 0,15 kg đậu xanh. Mỗi cái bánh chưng nhận được 5 điểm thưởng, mỗi cái bánh ống nhận được 7 điểm thưởng. Hãy lập kế hoạch gói bánh, tức là tính xem cần gói bao nhiêu cái bánh mỗi loại để được nhiều điểm thưởng nhất. Ta xây dựng mô hình toán học cho bài toán trên: Gọi x là số bánh chưng gói được, y là số bánh ống gói được. Khi đó số điểm thưởng là: f ( x, y)  5x  7 y . Do trong cuộc thi chỉ sử dụng tối đa 20 kg gạo nếp, 2 kg thịt ba chỉ và 5 kg đậu xanh nên x và y phải chịu những ràng buộc, cụ thể: Số kg gạo nếp cần dùng là: 0,4 x  0,6 y  20 . Số kg thịt ba chỉ cần dùng là: 0,05x  0,075 y  2 . Số kg đậu xanh cần dùng là: 0,1x  0,15 y  5 . Ngoài ra còn có các ràng buộc khác đó là, x  0, y  0 vì số cái bánh không thể âm. Bằng ngôn ngữ toán học, bài toán trên có thể phát biểu như sau: Tìm x và y sao cho tại đó biểu thức f ( x, y)  5x  7 y đạt giá trị lớn nhất với các ràng buộc: 0, 4 x  0,6 y  20 0,05 x  0,075 y  2   0,1x  0,15 y  5  x  0, y  0  1
Từ bài toán đã nêu cùng rất nhiều các bài toán thực tế khác ta có thể thấy bài toán quy hoạch tuyến tính tổng quát có dạng như sau: Hãy tìm vectơ x  ( x1 , x2 ,..., xn ) sao cho tại đó hàm n f ( x)   c j x j (1) j 1 n a x j 1 ij j  ai , i  I (2) m a x i 1 ij j  bj , i  I ' (3) x j  0, j  J (4) đạt giá trị nhỏ nhất (hoặc lớn nhất) với các ràng buộc, trong đó: I  M  1,2,..., m J  N  1,2,..., n I '  M \ I. Trong bài toán trên, hàm f ( x) được gọi là hàm mục tiêu; các ràng buộc (2) và (3) được gọi là ràng buộc cưỡng bức; ràng buộc (4) được gọi là ràng buộc tự nhiên, nó cũng thuộc loại ràng buộc (2) nhưng vì muốn nhấn mạnh nên ta vẫn tách riêng. Mỗi vectơ x  ( x1 , x2 ,..., xn ) thỏa mãn tất cả các ràng buộc được gọi là một phương án. Phương án mà tại đó hàm mục tiêu đạt giá trị nhỏ nhất (hoặc lớn nhất) được gọi phương án tối ưu; giá trị ấy được gọi là giá trị tối ưu của hàm mục tiêu trên tập các phương án. Giải bài toán quy hoạch tuyến tính được hiểu là tìm được dù chỉ một phương án tối ưu; hoặc là chứng tỏ trên tập phương án hàm mục tiêu không bị chặn, tức là hàm mục tiêu có thể nhận giá trị nhỏ tùy ý đối với bài toán dạng min (hoặc lớn tùy ý đối với bài toán dạng max) trên tập phương án; hoặc chứng tỏ tập phương án là rỗng (người ta đã chứng minh được rằng, đối với bài toán quy hoạch tuyến tính chỉ xảy ra một và chỉ một trong ba khả năng kể trên). Về mặt lý thuyết ta chỉ đề cập tới các bài toán quy hoạch tuyến tính dạng min (tìm giá trị nhỏ nhất), bởi vì: f ( x)  max f ( x)   f ( x)  min[ f ( x)] xX xX 2
Khi đó, bài toán quy hoạch tuyến tính được viết dưới dạng gọn hơn: n f ( x)   c j x j  min j 1 n a x j 1 ij j  bi , i  I n a x j 1 ij j  bi , i  I ' x j  0, j  J . Để việc trình bày được ngắn gọn, ta đưa ra các kí hiệu và quy ước sau đây: a. Nếu A là ma trận cỡ (m,n) thì Ai  (ai1 , ai 2 ,..., ain ) là vectơ dòng (ma trận dòng) thứ i của A; A j  (a1 j , a2 j ,..., amj ) là vectơ cột (ma trận cột) thứ j của A. b. Nếu A  (aij ) và B  (bij ) là hai ma trận cùng kiểu thì bất đẳng thức ma trận A  B được hiểu là aij  bij với mọi i, j. Đặc biệt, với vectơ (ma trận) x  ( x1 , x2 ,..., xn ) thì x  0 được hiểu là x j  0 với mọi j. c. Mỗi vectơ được xem như ma trận cột trong các phép tính ma trận (nếu không nói gì thêm hoặc không có quy ước gì khác). Nếu c  (c1 , c2 ,..., cn ) và x  ( x1 , x2 ,..., xn ) là hai vectơ nào đó thì biểu thức (cùng kí hiệu tương ứng) n c, x   c j x j j 1 được gọi là tích vô hướng của hai vectơ c và x. Nếu xem c và x là hai ma trận cột thì  n  t cx    c j x j   j 1  là ma trận cấp 1, trong đó t c là ma trận chuyển vị của c (còn kí hiệu là c t hay cT ). Để cho gọn, sau đây ta sẽ quy ước: n t cx   c j x j  c, x . j 1 3
Như vậy, với các kí hiệu và quy ước nêu trên, bài toán quy hoạch tuyến tính tổng quát được viết dưới dạng gọn hơn như sau: f ( x)  t cx  min (1’) Ai x  bi , i  I (2’) Ai x  bi , i  I ' (3’) x j  0, j  J , (4’) trong đó A  (aij ) là ma trận cỡ (m,n).  Dạng chính tắc và dạng chuẩn tắc của bài toán quy hoạch tuyến tính Xét bài toán (1’) - (4’). a. Nếu I   và J=N thì ta có bài toán quy hoạch tuyến tính dạng chính tắc, nó có dạng: f ( x)  t cx  min Ax  b x  0, trong đó b  (b1 , b2 ,..., bm ) ; A được gọi là ma trận ràng buộc. Sau này, trong các bài toán quy hoạch tuyến tính dạng chính tắc, nếu chưa được chỉ rõ, ta luôn coi rằng A là ma trận của bài toán đó. b. Nếu I   và J=N thì ta có bài toán quy hoạch tuyến tính dạng chuẩn tắc, nó có dạng: f ( x)  t cx  min Ax  b x  0, Dễ thấy rằng, bằng các phép biến đổi thích hợp ta có thể đưa bài toán quy hoạch tuyến tính bất kì về dạng chính tắc hoặc là dạng chuẩn tắc, cụ thể là: Mỗi phương trình Ai x  bi được thay bởi hệ hai bất phương trình Ai x  bi và  Ai x  bi Mỗi bất phương trình Ai x  bi được thay bởi hệ Ai x  xni  bi và xni  0 , trong đó ẩn mới xni được gọi là ẩn phụ (hay biến phụ). 4
Mỗi bất phương trình Ai x  bi được thay bởi hệ Ai x  xni  bi và xni  0 , trong đó ẩn mới xni được gọi là ẩn phụ (hay biến phụ). Mỗi ẩn x j không có ràng buộc về dấu đều có thể viết thành hiệu của hai ẩn mới không âm: x j  x'j  x''j ; x 'j  0 ; x ''j  0 Nếu ẩn x j có điều kiện x j  0 thì ta đặt x j   x'j với x 'j  0 . Ví dụ: Chuyển bài toán dạng tổng quát về dạng chính tắc f ( x)  x1  3x2  2 x3  min 3x1  x2  2 x3  7 2 x  4 x  x  12  1 2 3  4 x1  3x2  8 x3  10  x1  0, x3  0  Giải: Đưa vào hai ẩn phụ x4  0, x5  0 ứng với hai ràng buộc thứ 1 và thứ 3. Đặt x3   x3  0 ; x2  x2  x2 ( x2  0, x2  0) ' '' ' '' ' Khi đó bài toán trở thành: Tìm x sao cho f ( x)  x1  3( x2  x2 )  2 x3  min '' ' ' 3x1  ( x2  x2 )  2 x3  x4  7 '' ' '  2 x1  4( x2  x2 )  x3  12 '' ' '  4 x1  3( x2  x2 )  8 x3  x5  10 '' ' '  x  0, x '  0, x ''  0, x '  0, x  0, x  0  1 2 2 3 4 5 1.1.2. Một số kết quả từ giải tích lồi Định nghĩa (Tổ hợp lồi): Giả sử x1 , x 2 ,..., x m là các điểm trong không gian n . Điểm x được gọi là tổ hợp lồi của các điểm ấy nếu tồn tại các số không âm 1 , 2 ,..., m với 1  2  ...  m  1 sao cho x  1 x1  2 x 2  ...  m x m . Trong trường hợp x là tổ hợp lồi của hai điểm x1 , x 2 ta thường viết: x   x1  (1   ) x 2 ,0    1. 5
Tập hợp các điểm là tổ hợp lồi của hai điểm cho trước x1 và x 2 được gọi là đoạn thẳng nối hai điểm ấy. Khi đó x1 và x 2 được gọi là các đầu mút của đoạn thẳng (theo thứ tự ứng với   1 và   0 ). Mỗi điểm của đoạn thẳng mà không phải là đầu mút được gọi là điểm trong của đoạn thẳng ấy. Định nghĩa (Tập lồi): Tập hợp L  n được gọi là tập lồi nếu như L chứa hai điểm nào thì nó chứa cả đoạn thẳng nối hai điểm ấy (tức là nếu x và y là hai điểm bất kì thuộc L thì L chứa mọi điểm có dạng  x  (1   ) y,0    1 ). Có thể kiểm tra được rằng, trong 2 đoạn thẳng, tia, đường thẳng, nữa mặt phẳng, hình tam giác (nói chung là đa giác lồi), hình tròn và cả 2 nữa là những ví dụ về tập lồi; hình vành khăn, hình sao năm cánh,… không phải là các tập hợp lồi. Tập rỗng và tập chỉ có một phần tử được xem là các tập hợp lồi. Định lí 1.1. Giao của một số bất kì các tập hợp lồi là một tập hợp lồi. Định lí 1.2. Nếu L là một tập hợp lồi và x i ( i  1, m ) là các điểm bất kì của nó thì, với mọi m, tập L chứa mọi điểm là tổ hợp lồi của các điểm ấy. Định nghĩa (Điểm cực biên): Điểm x 0 của một tập hợp lồi L được gọi là điểm cực biên của L nếu nó không thể biểu diễn được dưới dạng tổ hợp lồi thực sự của hai điểm phân biệt trong L, tức là không tồn tại trong L hai điểm phân biệt x1 , x 2 sao cho x0   x1  (1   ) x2 ,0    1 . Như vậy, x 0 là điểm cực biên của L khi và chỉ khi đẳng thức x0   x1  (1   ) x 2 với x1 , x 2  L và 0    1 chỉ xảy ra với x0  x1  x 2 . Trong 2 , nếu tập hợp lồi là một đoạn thẳng thì hai đầu mút là các điểm cực biên của nó, nếu tập hợp lồi là một hình tam giác thì ba đỉnh là các điểm cực biên của nó. Định nghĩa (Đa diện lồi): Tập hợp L gồm tất cả các điểm là tổ hợp lồi của một số hữu hạn điểm x1 , x 2 ,..., x m cho trước được gọi là đa diện lồi sinh bởi hệ điểm ấy. Có thể chứng tỏ rằng đa diện lồi là một tập lồi. Giả sử rằng sau khi loại bỏ các điểm là tổ hợp lồi của các điểm còn lại ta thu được một hệ con nào đó, chẳng hạn gồm x1 , x 2 ,..., x p ( p  m) . Người ta đã chứng minh 6
được rằng tập  x1 , x 2 ,..., x p  là tập các điểm cực biên của L, đồng thời mỗi điểm của L đều biểu diễn được dưới dạng tổ hợp lồi của các điểm cực biên ấy. Trong n đa diện lồi sinh bởi hai điểm là đoạn thẳng nối hai điểm ấy, đa giác lồi là một đa diện lồi sinh bởi các đỉnh của nó. Trong n , khái niệm đa diện lồi có thể được trình bày một cách trực quan hình học thông qua các khái niệm siêu phẳng và nửa không gian. Giả sử A  (aij ) là một ma trận cỡ (m,n) cho trước và Ai , i  1, m là vectơ dòng thứ i của nó. Siêu phẳng trong n là tập hợp các vectơ x trong không gian đó thỏa mãn phương trình Ai x  bi ; nửa không gian là tập các vectơ x  n thoả mãn bất phương trình Ai x  bi hay Ai x  bi . Trong 2 , một siêu phẳng được xác định bởi phương trình ax1  bx2  c ; một nửa không gian được xác định bởi bất phương trình ax1  bx2  c hay ax1  bx2  c . Như ta đã biết đó là đường thẳng và nửa mặt phẳng trong 2 . n Có thể chứng tỏ rằng siêu phẳng và nửa không gian trong là các tập hợp lồi. Thật vậy, xét siêu phẳng Li  {x  n : Ai x  bi } . Giả sử x1 và x 2 là hai điểm bất kì thuộc Li . Với 0    1 ta có: Ai [ x1  (1   ) x 2 ]   Ai x1  (1   ) Ai x 2  bi  (1   )bi  bi tức là,  x1  (1   ) x 2  Li . Vậy Li là một tập hợp lồi. Phép chứng minh là tương tự đối với nửa không gian. Định nghĩa (Tập lồi đa diện): Giao của một số hữu hạn các nửa không gian trong n được gọi là một tập lồi đa diện (còn gọi là khúc lồi, và rõ ràng nó là một tập lồi vì là giao của các tập lồi). Định nghĩa (Giới nội): Tập L trong n được gọi là giới nội nếu tồn tại số dương  r sao cho L là tập con của tập x  ( x1 , x2 ,..., xn ) : x12  x2  ...  xn  r . 2 2  7
Chú ý: Người ta đã chứng minh rằng một tập lồi đa diện không rỗng và giới nội là một đa diện lồi. 1.1.3. Một số tính chất của bài toán quy hoạch tuyến tính Tính chất 1: Tập hợp các phương án của bài toán quy hoạch tuyến tính là một tập lồi. Chú ý: 1) Vì tập phương án của bài toán quy hoạch tuyến tính là một tập lồi đa diện cho nên nếu tập phương án không rỗng và giới nội thì nó là một đa diện lồi. 2) Giả sử tập phương án của bài toán quy hoạch tuyến tính là X   và trong hệ ràng buộc của nó có các ràng buộc a1x1  a2 x2  ...  an xn   (hay a1x1  a2 x2  ...  an xn   ) và x j  0, j  1, n , trong đó  , a j  0, j  1, n . Khi đó ta kết luận X là một đa diện lồi. Thật vậy, nếu x  ( x1 , x2 ,..., xn ) là một phương án bất kì thì từ các ràng buộc nói   trên suy ra 0  x j  max   : j  1, n    và do đó x 2   2 với mọi j  1, n . Từ đó, ta   j aj    có x12  x2  ...  xn   n . Điều đó chứng tỏ X là một đa diện lồi và do đó bài toán 2 2 có phương án tối ưu. Tính chất 2: Tập hợp các phương án tối ưu của bài toán quy hoạch tuyến tính là một tập lồi. Tính chất 3: Nếu tập phương án của bài toán quy hoạch tuyến tính là đa diện lồi thì tồn tại phương án cực biên tối ưu. Xét bài toán quy hoạch tuyến tính dạng chính tắc: n f ( x)   c j x j  min (5) j 1 n a x j 1 ij j  bi , i  1, 2,..., m (6) x j  0, j  1,2,..., n. (7) - Hệ phương trình (6) có đúng m phương trình độc lập tuyến tính. - bi  0, i  1,2,..., m. - m  n , (trong trường hợp m  n thì tập phương án có nhiều nhất một điểm, do vậy việc tối ưu là tầm thường). 8
Kí hiệu L là tập phương án của bài toán (5), (6), (7). Vậy L là một tập lồi. Với bài toán đã cho, để tiện việc chứng minh sau này, chúng ta nhắc lại rằng: Phương án X là tối ưu khi và chỉ khi f ( X )  f (Y ) với mọi Y  L . Tính chất 4: Giả sử x0  ( x10 , x20 ,..., xn0 ) là một phương án khác không của bài toán quy hoạch tuyến tính dạng chính tắc với tập phương án X  {x  n : x1 A1  x2 A2  ...  xn An  b; x  0} Khi đó để x 0 là phương án cực biên của tập phương án, điều kiện cần và đủ là hệ vectơ liên kết với nó, tức là hệ H ( x0 )   A j : x jo  0 , là độc lập tuyến tính. Tính chất 5: Nếu bài toán quy hoạch tuyến tính dạng chính tắc có phương án tối ưu thì nó sẽ có ít nhất một phương án cực biên là phương án tối ưu. Tính chất 6: Điều kiện cần và đủ để bài toán quy hoạch tuyến tính có phương án tối ưu là tập phương án không rỗng và hàm mục tiêu bị chặn (bị chặn dưới nếu là bài toán cực tiểu hóa, bị chặn trên nếu là bài toán cực đại hóa; và nói bị chặn ta hiểu là bị chặn trên tập phương án). 1.2. Phƣơng pháp đơn hình giải bài toán quy hoạch tuyến tính. 1.2.1. Cơ sở lí luận Xét bài toán f ( x)  t cx  min (8) Ax  b (9) x0 (10) Ta giả thiết rằng bài toán (8), (9), (10) không suy biến và đã biết một phương án cực biên có dạng: x  ( x10 , x20 ,..., xn0 ) trong đó xi 0  0 với i  J 0 , J 0  m ; x j 0  0 với j  J 0 . Như vậy, cơ sở ứng với x là J 0 hay H ( x)   Ai : i  J 0  và mỗi vectơ A j ( j  1, n) đều biểu thị tuyến tính duy nhất qua H ( x) hay: A j   xij Ai , j  1, n iJ 0 9
Gọi B là ma trận có các cột là các vectơ trong cơ sở  Ai : i  J 0  và đặt x j  ( xij )  m , i  J 0 thì A j  Bx j hay x j  B 1 A j , j  1, n . Với kí hiệu x0  ( xi 0 )  m và c  (ci )  m với i  J 0 , A0  b thì rõ ràng ta có: f ( x)  t cx  cx 0   ci xi 0 ; Bx0  b t iJ 0 do đó x j  B 1 A j cũng đúng với j  0 . Gọi  j  cx j  c j   ci xij c j với j  1, n là ước lượng của ẩn x j (hay của t iJ 0 vectơ A j ) ứng với cơ sở J 0 . Ta có các định lí quan trọng sau đây: Định lí 1.3. (Dấu hiệu tối ƣu). Nếu tại phương án cực biên x , có  j  0, j  1,2,..., n thì x là phương án tối ưu. Định lí 1.4. (Kiểm tra bài toán vô nghiệm). Nếu tại phương án cực biên x , tồn tại  j  0 và mọi x j  0 ( j  1,2,..., n ) thì bài toán không có phương án tối ưu (hàm mục tiêu không bị chặn trên tập phương án). Định lí 1.5. (Điều chỉnh phƣơng án). Nếu tại phương án cực biên x , tồn tại  j  0 và có ít nhất một thành phần dương x j ( j  1,2,..., n ) thì xây dựng được phương án cực biên mới tốt hơn x . 1.2.2. Phương pháp đơn hình giải bài toán quy hoạch tuyến tính Giả sử bài toán cần giải có dạng khá đặc biệt, mà ta sẽ gọi là bài toán dạng chuẩn (hay bài toán chuẩn) sau đây: f ( x)  t cx  min x1 + a1,m1 xm1 + a1,m2 xm 2 + … + a1,n xn = b1 x2 + a2,m1 xm1 + a2,m 2 xm 2 + … + a2,n xn = b2 ………………………………………………… xm + am,m1 xm1 + am,m2 xm2 + … + am,n xn = bm x j  0, j  1, n 10
trong đó bi  0 (i  1, m) . Đó là bài toán dạng chính tắc mà ở hệ các ràng buộc phương trình có vế phải là b  (b1 , b2 ,..., bm )  0 ; còn ở vế trái, mỗi phương trình có một ẩn với hệ số bằng 1 nhưng ẩn này không có mặt (thực sự) ở các phương trình còn lại. Ta nhận biết được ngay rằng, x  (b,0)  (b1 , b2 ,..., bm ,0,...,0) là một phương án cực biên, vì nó thỏa mãn mọi ràng buộc và ứng với cơ sở đơn vị  A1 , A2 ,..., Am  với B  [A1 A2 ... Am ]  E . Ở đây, x j  B1 A j  A j  j  0, n; A0   b ; J 0  1, 2,..., m . Để tính toán các số liệu liên quan đến x ta lập bảng sau, mà ta sẽ gọi là bảng đơn hình ứng với phương án cực biên x : Cơ c1 c2 … cs … cm cm1 … cj … ck … cn 0 c x sở x1 x2 … xs … xm x m1 … xj … xk … xn c1 x1n A1 x10 1 0 … 0 … 0 x1,m1 … x1 j … x1k … c2 x2k x2n A2 x20 0 1 … 0 … 0 x2,m1 … x2 j … … … … … … … … … … … … … … … … … … cs xsn As xs 0 0 0 … 1 … 0 xs ,m1 … xsj … xsk … … … … … … … … … … … … … … … … … cm xmk xmn Am xm 0 0 0 … 0 … 1 xm,m1 … xmj … … f ( x) 0 0 … 0 … 0  m1 … j … k … n Trong bảng trên, từ cột x 0 trở đi chính là ma trận mở rộng (b A) : xi 0  bi ;   xij  aij i  1, m; j  1, n . Bƣớc 1. Dòng cuối cùng ghi giá trị của hàm mục tiêu tại x và các ước lượng  j ( j  1, n) :  Tính f ( x) : Tính vô hướng của c và x 0 11
t  Tính  j  cx j  c j : Lấy tích vô hướng của c và x j , rồi trừ đi c j ( c j được ghi sẵn ở dòng trên cùng, cùng cột với x j ). Bƣớc 2. Điểm diện tất cả các ước lượng  j ( j  1, n) .  Nếu  j  0 (j ) thì x là phương án tối ưu.  Nếu j :  j  0 và mọi x j  0 ( j  1, n) (  j và các thành phần của x j được viết trên cùng một cột) thì ta kết luận hàm mục tiêu không bị chặn.  Nếu tồn tại  j  0 và có ít nhất một thành phần dương x j thì ta tìm được phương án khác tốt hơn phương án cực biên ban đầu. Khi đó chuyển sang bước 3. Bƣớc 3. Tìm phương án khác tốt hơn phương án cực biên ban đầu Giả sử  k  0 và  k  max  j khi đó Ak sẽ được đưa vào cơ sở. Nếu các max 1i  n nói trên đạt ở quá một chỉ số thì ta chọn ngẫu nhiên hoặc chọn chỉ số nhỏ nhất trong chúng. Khi đã xác định đưa Ak vào cơ sở thì việc loại vectơ As ra khỏi cơ sở phải tuân theo tiêu chuẩn: x  x min  i 0 : xik  0, i  J 0   so  xik  xsk Khi đó các thành phần của ( x j )'  ( xij ), i  ( J 0 \{s})  {k}; j  0, n , được tính theo ' công thức, được gọi là công thức đổi cơ sở:  ' xsj  xkj  x ( j  0, n) (a)  sk   x '  x  xsj .x (i  J \ {s}) (b)  ij  ij xsk ik 0 Công thức (a): Chia mọi phần tử của dòng s cho xsk ta được dòng k mới (dòng mang chỉ số k). Công thức (b): Lấy mỗi dòng i ( i  ( J 0 \{s}) cũ trừ đi tích giữa dòng k mới (tức là dòng s cũ đã biến đổi) với phần tử nằm giao giữa dòng đang tính và cột k, ta được dòng i mới. 12
Bản chất của công thức (a), (b) là biến đổi sơ cấp ma trận ở bảng đơn hình trước sao cho cột k mới là vectơ đơn vị (phần tử 1 thế chỗ xsk ), đồng thời cột ( x0 )'  0 . Sau đó ta tính các ước lượng   j  ' ứng với x ' (như đã làm với x ). Cho x ' đóng vai trò x và tiến hành các thủ tục như đã tiến hành đối với x . Ngoài ra, ta có thể tính các ước lượng   j  ' như sau:  k .xsj j '  j  xsk Sau đó, quay lại bước 2. Quá trình như vậy cứ tiếp tục, sau một số hữu hạn bước việc tính toán sẽ kết thúc ở một trong hai tình huống: xuất hiện tối ưu hoặc dấu hiệu hàm mục tiêu không bị chặn. Cách thức tiến hành vừa trình bày trên đây để giải bài toán đã cho ở dạng chuẩn được gọi là thuật toán đơn hình (gốc). Việc thực hiện các phép biến đổi (a), (b) ở mỗi bước được gọi là phép xoay (gốc) xung quanh phần tử trục xsk , dòng s được gọi là dòng xoay, cột k được gọi là cột xoay. Ví dụ: Giải bài toán QHTT sau: f ( x)  3x1  2 x2  5x3  2 x4  min x1 + 7 x3  3x4 =7 x2  2 x3  x4 =1 3x3  x4  x5  16 x j  0, j  1,5 Giải: Bài toán ở dạng chuẩn, ta lập bảng sau: Cơ 3 2 5 -2 0 c x0 sở x1 x2 x3 x4 x5 3 A1 7 1 0 7 -3 0 2 A2 1 0 1 -2 1 0 0 A5 16 0 0 3 1 1 f ( x0 ) 23 0 0 12 -5 0 13