Luận văn Cải tiến phương pháp đơn hình giải quy hoạch tuyến tính

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HUỆ CẢI TIẾN PHƯƠNG PHÁP ĐƠN HÌNH GIẢI QUY HOẠCH TUYẾN TÍNH Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.36 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học GS.TS. TRẦN VŨ THIỆU Thái Nguyên – 2011 NGUYỄN THỊ HUỆ Đề tài: CẢI TIẾN THUẬT TOÁN ĐƠN HÌNH GIẢI QUY HOẠCH TUYẾN TÍNH Soạn thảo văn bản LATEX bởi công cụ MikTeX & TeXmaker Thái Nguyên, ngày 10 tháng 10 năm 2011 1Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Mục lục 1 KIẾN THỨC CHUẨN BỊ 6 1.1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VÀ TÍNH CHẤT . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Nội dung bài toán . . . . . . . . . . . . . . . 6 1.1.2 Một số tính chất . . . . . . . . . . . . . . . . 8 1.2 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU 11 1.2.1 Dạng bài toán đối ngẫu . . . . . . . . . . . . 11 1.2.2 Định lí đối ngẫu . . . . . . . . . . . . . . . . 12 1.3 PHƯƠNG PHÁP ĐƠN HÌNH . . . . . . . . . . . . . . 13 1.3.1 Thuật toán đơn hình gốc . . . . . . . . . . . 14 1.3.2 Thuật toán đơn hình đối ngẫu . . . . . . . 17 2 PHƯƠNG PHÁP ĐƠNHÌNH GỐC - ĐỐI NGẪU CẢI BIÊN 22 2.1 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TOÁN . . . . . . 22 2.1.1 Nội dung bài toán và các kí hiệu . . . . . . 22 2.1.2 Ý tưởng thuật toán . . . . . . . . . . . . . 23 2.2 THUẬT TOÁN ĐƠN HÌNH GỐC - ĐỐI NGẪU CẢI BIÊN (RPDSA) . . . . . . . . . . . . . . . . . . . . . . 25 2.3 PHƯƠNG PHÁP M - LỚN ( BIG M - METHOD) . . 27 2.3.1 Tìm cơ sở đối ngẫu chấp nhận được B và phân hoạch ( B, N ) ban đầu. . . . . . . . . 27 2.3.2 Tìm điểm gốc chấp nhận được y ban đầu 27 12Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.3.3 Phương pháp M - lớn ( Big - M Method . 28 2.3.4 VÍ DỤ MINH HỌA . . . . . . . . . . . . . . 30 3 HAI PHƯƠNG PHÁP CẢI TIẾN KHÁC 33 3.1 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TOÁN . . . . . . 33 3.1.1 Nội dung bài toán và các kí hiệu . . . . . . 33 3.1.2 Ý tưởng thuật toán . . . . . . . . . . . . . . 34 3.2 PHƯƠNG PHÁP GÓC NGHIÊNG NHỎ NHẤT . . . . 37 3.2.1 Thuật toán . . . . . . . . . . . . . . . . . . . 37 3.2.2 Ví dụ 3.1 . . . . . . . . . . . . . . . . . . . . . 39 3.3 PHƯƠNG PHÁP CÔSIN ĐƠN HÌNH . . . . . . . . . 41 23Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI NÓI ĐẦU Quy hoạch tuyến tính là bài toán tìm cực đại ( hay cực tiểu ) của một hàm tuyến tính với các biến số thỏa mãn các phương trình hay bất phương trình tuyến tính. Quy hoạch tuyến tính là một trong những lớp bài toán tối ưu quan trọng nhất và được ứng dụng rộng rãi nhất trong thực tiễn. Thuật toán đơn hình do Dantzig đề xuất từ năm 1947, dựa trên nguyên tắc xoay vần được dùng rộng rãi và có hiệu quả để giải các bài toán quy hoạch tuyến tính. Tuy nhiên, về mặt lý thuyết nó là thuật toán thời gian mũ ( thời gian tính phụ thuộc theo cấp độ hàm mũ vào độ dài dữ liệu của bài toán cần giải ). Vì thế, nhiều nghiên cứu đã được tiến hành nhằm cải tiến nó cả về lý thuyết lẫn hiệu quả tính toán thực tế. Về lý thuyết, thành tựu nổi bật nhất là đã chứng minh được rằng bài toán quy hoạch tuyến tính có thể giải được bằng các thuật toán thời gian đa thức. L. G. Khachian ([8], 1979) là người đầu tiên đã đề xuất thuật toán ellipsoid giải quy hoạch tuyến tính trong thời gian đa thức, dựa trên những nghiên cứu trong những năm 60 - 70 của thế kỉ trước, chủ yếu ở Liên Xô (trước đây), do những tác giả khác, trước Khachian thực hiện. Tiếp đó, N. K. Karmarkar ([7], 1984) đã đề xuất thuật toán chiếu giải quy hoạch tuyến tính. Phương pháp này cũng có độ phức tạp đa thức và có hiệu quả tính toán cao đặc biệt đối với những bài toán tuyến tính cỡ lớn. Cả hai bài toán trên đều thuộc loại phương pháp điểm trong. Sau đó đã có nhiều mở rộng phương pháp điểm trong (xem [9]) để giải các bài toán tối ưu phi tuyến, quy hoạch lồi toàn phương , quy hoạch nón... Về góc độ thực tiễn, có nhiều nghiên cứu nhằm cải tiến thuật toán đơn hình sao cho đạt hiệ quả tính toán cao hơn nữa. Trong đó, đáng 34Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên kể có thuật toán đơn hình gốc đối ngẫu của K. Paparrizos et al., ([10], 2003) thuật toán cải tiến cơ sở ban đầu cho thuật toán đơn hình do H. V. Junior và M. P. E. Lins đề xuất ([6], 2005) và thuật toán cô sin đơn hình do H. W. Corley et al., đề xuất ([5], 2005) Kết quả tính toán trên các bài toán thử nghiệm cho thấy các thuật toán mới hiệu quả hơn thuật toán đơn hình cổ điển khoảng 30% và tỏ ra rất có triển vọng. Luận văn này nhằm tìm hiểu và giới thiệu một số thuật toán mới cải tiến thuật toán đơn hình, thuộc nhóm thứ hai kể trên. Cụ thể luận văn sẽ trình bày phương pháp đơn hình điểm ngoài (EPSA, RPDSA), phương pháp góc nghiêng nhỏ nhất (MA) và phương pháp côsin đơn hình (CSA). Các thuật toán này có ý tưởng rõ ràng, dễ thực thi, khối lượng tính toán giảm và do đó hiệu quả tính toán cao hơn. Vì thế, tìm hiểu và nghiên cứu chủ đề này là cần thiết và hữu ích, giúp hiểu rõ các mở rộng và ứng dụng của phương pháp đơn hình trong thực tiễn. Nội dung luận văn được chia làm ba chương: Chương 1: Kiến thức chuẩn bị Nhắc lại tóm tắt một số kiến thức cơ bản cần thiết về nài toán quy hoạch tuyến tính và bài toán quy hoạch tuyến tính đối ngẫu cùng các tính chất của chúng, về phương pháp đơn hình và đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính. Nhiều khái niệm, sự kiện trình bày ở chương này được giải thích, minh họa qua các ví dụ bằng số và hình vẽ cụ thể. Các kiến thức này sẽ được dùng đến ở các chương sau. Chương 2: Phương pháp đơn hình đối ngẫu- đối ngẫu cải biên trình bày thuật toán đơn hình gốc - đối ngẫu cải biên (RPDSA) mà thực chất là sự cải biên thuật toán đơn hình đối ngẫu. Thuật toán RPDSA cũng có thể xem như một thuật toán đơn hình điểm ngoài ( exterior point simple algorithm - EPSA), vì các nghiệm cơ sở k do thuật toán tạo ra luôn nằm ngoài miền chấp nhận được của bài toán. Chương 3: Hai phương pháp cải tiến khác trình bày phương pháp góc nghiêng nhỏ nhất giải quy hoạch tuyến tính chính tắc và phương pháp cô sin đơn hình giải quy hoạch tuyến tính chuẩn tắc. Cả hai phương pháp đều dựa trên nhận xét chung là đỉnh tối ưu của bài toán gốc hay đối ngẫu thường gần với đỉnh tạo nên bởi các ràng buộc mà góc giữa véc tơ gradian của chúng với véc tơ hệ số mục tiêu là nhỏ 45Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên nhất. Phương pháp đầu chọn các véctơ ràng buộc đó làm cơ sở xuất phát, còn phương pháp sau đưa dần các ràng buộc đó vào bài toán để giải. Do thời gian và kiến thức còn nhiều hạn chế nên luận văn này mới chỉ đề cập tới những nội dung cơ bản của các thuật toán kiểu đơn hình giải quy hoạch tuyến tính, chưa đi sâu vào kĩ thuật lập trình cụ thể. Trong kĩ thuật viết luận văn cũng như trong quá trình xử lý văn bản chắc chắn không tránh khỏi những sai xót nhất định. Tôi rất mong nhận được sự đóng góp của các thầy, cô và các bạn đồng nghiệp để luận văn được chính xác và hoàn thiện hơn. Nhân dịp nay, tôi xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng dẫn GS - TS Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tôi xin trân trọng cảm ơn các thầy, cô giáo trường Đại Học Khoa Học - Đại Học Thái Nguyên, Viện Toán học - Viện Khoa Học và Công Nghệ Việt Nam, đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tôi học tập và nghiên cứu. Tôi cũng xin chân thành cảm ơn ban giám hiệu, các Phòng, các Ban chức năng của trường Cao Đẳng Công Nghệ và Kinh tế Công Nghiệp thành phố Thái Nguyên và tập thể bạn bè đồng nghiệp cùng gia đình đã quan tâm giúp đỡ, động viên để tôi hoàn thành tốt luận văn này. Thái Nguyên, tháng 9/2011 56Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chương 1 KIẾN THỨC CHUẨN BỊ Chương này trình bày một số kiến thức cơ bản cần thiết về quy hoạch tuyến tính, phương pháp đơn hình ( thuật toán đơn hình gốc và thuật toán đơn hình đối ngẫu ) và đối ngẫu trong quy hoạch tuyến tính. Nội dung của chương chủ yếu dựa trên các tài liệu tham khảo [1] - [4] 1.1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VÀ TÍNH CHẤT Quy hoạch tuyến tính là bài toán tìm cực tiểu ( cực đại ) của một hàm tuyến tính f(x) trên một tập lồi đa diện D ⊂ Rn. Quy hoạch tuyến tính là một trong những lớp bài toán tối ưu quan trọng nhất và được ứng dụng rộng rãi nhất trong thực tiễn. Nó bắt nguồn từ nững nghiên cứu của nhà bác học Nga nổi tiếng, Viện sĩ L. V. Kantorovich trong một loạt công trình về kế hoạch hóa sản xuất công bố năm 939 và nó thực sự phát triển mạnh mẽ kể từ khi nhà toán học Mỹ G. B. Dantzig đề xuất thuật toán đơn hình giải quy hoạch tuyến tính vào năm 1947. 1.1.1 Nội dung bài toán Bài toán quy hoach tuyến tính thường được viết ở một số dạng sau: Dạng tổng quát ( abstract form ): min{f(x) = cTx : x ∈ D} 67Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên trong đó c ∈ Rn, D ⊂ Rn là một tập lồi đa diện, tức là tập nghiệm của một hệ phương trình và bất phương trình tuyến tính. T kí hiệu của chuyển vị véctơ ( ma trận ). Dạng chuẩn ( standard form): min{f(x) = cTx : Ax ≥ b, x ≥ 0} trong đó A ∈ Rm×n (ma trận cỡ m x n), b ∈ Rm, c, x ∈ Rn, x ≥ 0 Trong bài toán này, tập D = {x ∈ Rn : Ax ≥ b, x ≥ 0} là một tập lồi đa diện. Ví dụ 1.1 Quy hoạch tuyến tính dạng chuẩn hai biến: 3x1 + 2x2 → min với điều kiện x1 + 2x2 ≥ 5, 3x1 + x2 ≥ 4, x1 ≥ 0, x2 ≥ 0. Dạng chính tắc ( canonical form): min{f(x) = cTx : Ax = b, x ≥ 0} với các kí hiệu như ở trên. Ví dụ 1.2 Quy hoạch tuyến tính dạng chính tắc ba biến: x1 + 3x2 + 2x3 → min với điều kiện x1 − x2 + x3 = 5, 2x1 + x2 − x3 = 4, x1 + x2 + x3 = 3, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. 78Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Trong các dạng trên, f được gọi là hàm mục tiêu, D gọi là tập ràng buộc hay miền chấp nhận được, điểm x = (x1, x2, ......, xn) T ∈ D gọi là một phương án hay một lời giải chấp nhận được của bài toán. Một phương án cực tiểu ( cực đại ) của hàm mục tiêu gọi là phương án tối ưu hay lời giải tối ưu. Với mỗi bài toán quy hoạch tuyến tính chỉ xảy ra 1 trong 3 khả năng sau: a) Bài toán không có phương án ( tập ràng buộc D rỗng ). b) Bài toán có phương án nhưng không có phương án tối ưu. c) Bài toán có phương án tối ưu. 1.1.2 Một số tính chất Định lí sau nêu điều kiện để một quy hoạch tuyến tính có phương án tối ưu: Định lí 1.1: Nếu một quy hoạch tuyến tính có ít nhất một phương án và hàm mục tiêu bị chặn dưới trong miền ràng buộc (đối với bài toán min) thì bài toán chắc chắn có phương án tối ưu. Nhận xét 1.1: Định lí 1.1 chỉ đúng cho bài toán quy hoạch tuyến tính, định lí không còn đúng khi hàm mục tiêu hoặc một trong các ràng buộc không còn tuyến tính. Sau đây là hai ví dụ chứng minh cho nhận xét này. Ví dụ 1.3 Xét bài toán min{f(x1, x2) = x2 : x1x2 ≥ 1, x1 ≥ 0} Miền chấp nhận được D = {x ∈ R2 : x1x2 ≥ 1, x1 ≥ 0} là một tập lồi khác rỗng, nhưng không la tập lồi đa diện. Tuy hàm mục tiêu f(x) = x2 là tuyến tính và f(x) ≥ 0 với mọi x ∈ D ( f bị chặn dưới trên D), nhưng rõ ràng bài toán không có phương án tối ưu, mặc dù infx∈Df(x) = 0 (xem Hình 1.1). 89Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ví dụ 1.4 Xét bài toán min{f(x) = 1 1 + x2 : x ∈ R2}. Miền chấp nhận được D ≡ R là một tập lồi đa diện, khác rỗng. Tuy nhiên, hàm mục tiêu f(x) = 11+x2 là hàm phi tuyến tính và f(x) ≥ 0 với mọi x ∈ D ( f bị chặn dưới trên D), nhưng rõ ràng bài toán này cũng không có phương án tối ưu, mặc dù infx∈Df(x) = 0 (xem Hình 1.2). Định lí 1.2: Nếu x0 là một phương án tối ưu của bài toán quy hoạch tuyến tính (dạng bất kì) và nếu x1, x2(x1 6= x2) là 2 phương án thỏa mãn x0 = λx1 + (1− λ)x2, 0 ≤ λ ≤ 1 thì x1, x2 cũng là các phương án tối ưu. Định nghĩa 1.1: Một phương án x ∈ D mà đồng thời là đỉnh của D gọi là một phương án cực biên hay một lời giải cơ sở nghĩa là x không thể biểu diễn dưới dạng tổ hợp lồi của bất kì hai phương án khác của D. Nói cách khác, hễ có x = λx1 + (1− λ)x2, 0 ≤ λ ≤ 1 và x1, x2 ∈ D thì x = x1 = x2 Định lí 1.3: Để một lời giải chấp nhận được x¯ = {x¯1, x¯2, ....., x¯n} của quy hoạch tuyến tính chính tắc là lời giải cơ sở thì điều kiện cần và đủ là các véc tơ cột Aj của ma trận A ứng với các thành phần x¯j > 0 là độc lập 910Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên tuyến tính. Từ định lí 1.3 ta dễ dàng suy ra các hệ quả sau: Hệ Quả 1.1: Số phương án cực biên của bài toán quy hoạch tuyến tính chính tắc là hữu hạn. Hệ Quả 1.2: Số thành phần dương trong mỗi phương án cực biên của bài toán quy hoạch tuyến tính dạng chính tắc tối đa bằng m (m là số hàng của ma trận A) Người ta phân ra 2 loại phương án cực biên: Không suy biến nếu phương án cực biên đó có số thành phần dương bằng m và suy biến nếu trái lại. Định lí 1.4: Nếu bài toán quy hoạch tuyến tính dạng chính tắc có ít nhất một phương án thì nó cũng có phương án cực biên (miền ràng buộc D có đỉnh). Định lí 1.5: Nếu một quy hoạch tuyến tính ( dạng tùy ý) có phương án tối ưu và nếu tập ràng buộc D có đỉnh thì phương án cực biên tối ưu Các định lí trên cho phép tìm phương án cực biên tối ưu của bài toán quy hoạch tuyến tính chính tắc trong số các phương án cực biên của bài toán (số này là hữu hạn). 1011Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1.2 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU 1.2.1 Dạng bài toán đối ngẫu Đối ngẫu là một phương pháp mà ứng với mỗi bài toán quy hoạch tuyến tính đã cho (gọi là bài toán gốc), ta có thể thiết lập một bài toán quy hoạch tuyến tính khác ( gọi là bài toán đối ngẫu) sao cho từ lời giải của bài toán này ta sẽ thu được thông tin về lời giải của bài toán kia. Sau đây là hai dạng cặp bài toán đối ngẫu thường gặp Đối ngẫu của quy hoạch tuyến tính dạng chuẩn (quy hoạch gốc): • (P) min{f(x) = cTx : Ax ≥ b, x ≥ 0} là quy hoạch tuyến tính ( quy hoạch đối ngẫu ) • (Q) max{g(y) = bTy : ATy ≤ c, y ≥ 0} (AT là ma trận chuyển vị của A ) ATy ≤ c còn viết dưới dạng s = c− ATy ≥ 0 Ví dụ 1.5 Đối ngẫu của bài toán cho ở ví dụ 1.1 ( dạng chuẩn) là bài toán g(y) = 5y1 + 4y2 → max với điều kiện y1 + 3y2 ≤ 3, 2y1 + y2 ≤ 2, y1 ≥ 0, y2 ≥ 0. Đối ngẫu của quy hoạch tuyến tính dạng chính tắc : min{f(x) = cTx : Ax = b, x ≥ 0} là quy hoạch tuyến tính max{g(y) = bTy : ATy ≤ c} ( biến đối ngẫu y có dấu tùy ý ) 1112Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ví dụ 1.6 Đối ngẫu của bài toán ở Ví dụ 1.2 (dạng chính tắc) là bài toán g(y) = 5y1 + 4y2 + 3y3 → max với điều kiện y1 + 2y2 + y3 ≤ 1, −y1 + y2 + y3 ≤ 3, y1 − y2 + y3 ≤ 2. 1.2.2 Định lí đối ngẫu Các kết quả dưới đây đúng cho mọi cặp bài toán đối ngẫu (P)và (Q) dạng bất kì. Định lí 1.6.( Đối ngẫu yếu) Nếu x là một phương án của bài toán gốc (P) và y là một phương án của bài toán đối ngẫu (Q) thì f(x) = c1x1 + c2x2 + ...+ cnxn ≥ g(y) = b1y1 + b2y2 + ...+ bmym Từ định lí đối ngẫu yếu ta suy ra các kết luận trong hệ quả sau: Hệ quả 1.3 a) Giá trị mục tiêu của một phương án đối ngẫu bất kì là một cận dưới cho giá trị mục tiêu đối với mọi phương án của bài toán gốc b) Nếu hàm mục tiêu của bài toán gốc không bị chặn dưới trong miền ràng buộc của nó thì bài toán đối ngẫu không có bất kì một phương án nào. c) Nếu hàm mục tiêu của bài toán đối ngẫu không bị chặn dưới trong miền ràng buộc của nó thì bài toán gốc không có bất kì một phương án nào. d) Nếu x∗ là một phương án của bài toán gốc, y∗ là một phương án 1213Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên của bài toán đối ngẫu và f(x∗) = g(y∗) thì x∗ là phương án tối ưu của bài toán gốc và y∗ là phương án tối ưu của bài toán đối ngẫu. Định lí 1.7 (Đối ngẫu mạnh): Nếu một quy hoạch có phương án tối ưu thì quy hoạch đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của chúng là bằng nhau. Định lí 1.8 (Đối ngẫu cơ bản): Đối với mỗi cặp quy hoạch đối ngẫu nhau chỉ có thể xảy ra 1 trong 3 khả năng sau đây: a) Cả 2 quy hoạch đều có phương án. b) Cả 2 quy hoạch đều có phương án. Khi đó cả 2 quy hoạch đều có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu là bằng nhau. c) Một quy hoạch có phương án và quy hoạch kia không có phương án. Khi đó quy hoạch có phương án sẽ không có phương án tối ưu và hàm mục tiêu của nó không giới nội trong miền ràng buộc. Quan hệ giữa cặp quy hoạch đối ngẫu còn thể hiện ở sự kiện sau Định lí 1.9 (Định lí độ lệch bù) Mỗi cặp phương án x, y của 2 quy hoạch đối ngẫu (P) và (Q) là những phương án tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức: yi( n∑ j=1 aijxj − bi) = 0 với mọi i = 1,2.......,m xj(cj − m∑ i aijyi) = 0 với mọi j = 1,2......,n 1.3 PHƯƠNG PHÁP ĐƠN HÌNH Phương pháp đơn hình giải QHTT (do G.B. Zantzig) đề xuất 1947 dựa trên 2 tính chất quan trọng sau đây của bài toán QHTT: 1314Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên a) Nếu QHTT chính tắc có phương án tối ưu thì cũng có phương án cực biên tối ưu, nghĩa là có ít nhất 1 đỉnh của miền ràng buộc là lời giải của bài toán b) Mỗi điểm cực biên địa phương của hàm tuyến tính (cũng là hàm lồi) trên một tập hợp lồi là một điểm cực tiểu tuyệt đối. 1.3.1 Thuật toán đơn hình gốc Bằng cách thực hiện một số phép biến đổi đơn giản, ta có thể đưa bài toán quy hoạch tuyến tính từ dạng này sang dạng khác. Vì thế khi giải ta chỉ cần chọn một dạng thuận tiện để xét mà không làm giảm tính tổng quát của phương pháp. Xét quy hoạch tuyến tính chính tắc (m ràng buộc đẳng thức, n biến): min{cTx : Ax =, x ≥ 0} với A là ma trận cấp m× n (Aj ∈ Rm là cột j của A), b ∈ Rm, c, x ∈ Rn. Giả thiết: m ≤ n (m > n bài toán có thể vô nghiệm) và rank(A) = m Bài toán quy hoạch tuyến tính được gọi là không suy biến nếu tất cả các phương án cực biên của nó đều không suy biến, tức là đều có m thành phần dương. Bài toán được gọi là suy biến nếu nó có dù chỉ là một phương án cực biên suy biến ( số thành phần dương nhỏ hơn m). Xuất phát từ một phương án cực biên (đỉnh ) không suy biến. Chẳng hạn, x¯ = (x¯1, x¯2, ....., x¯m, 0, ...., 0) với xj > 0 (j = 1,2,......,m) Đặt J = {j : x¯j〉0} là tập chỉ số biến cơ sở ( xj, j ∈ J là biến cơ sở) B = {Aj : j ∈ J} là cơ sở của A , rank(B) = m và tồn tại nghịch đảo B−1 xB = B −1b là véc tơ giá trị các biến cơ sở . ((xB,0) là phương án của bài toán ) cB = {cj : j ∈ J} 1415Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên là véc tơ hệ số các biến cơ sở. Tính Zk = B −1Ak là véc tơ hệ số khai triển cột Ak theo cơ sở B( k /∈ J) ∆k = cBZk − ck với mọi k = 1,2,.....,n (∆k là ước lượng của biến xk) Định lí 1.9( Dấu hiệu tối ưu) Nếu với phương án cực biên x¯ của bài toán ta có ∆k ≤ 0 với mọi k /∈ J thì x¯ là một phương án ( cực biên ) tối ưu của bài toán. Định lí 1.10 ( Dấu hiệu bài toán không có phương án tối ưu) Nếu đối với phương án cực biên x¯ tồn tại chỉ số k /∈ J sao cho ước lượng ∆k > 0 và Zjk ≤ 0 với mọi j ∈ J thì bài toán đã cho không có pương án tối ưu Thuật toán đơn hình gốc gồm các bước sau: Bước 1. Lập bảng đơn hình ban đầu ( xem ví dụ 1.7) Bước 2 ( Dấu hiệu tối ưu). Nếu ∆k ≤ 0 với mọi k = 1, 2, ....., n thì x∗ = (xB, xN) với xB = B−1b, xN = 0 là phương án tối ưu ( Định lí 1.9): dừng quá trình giải. Trái lại, chuyển sang bước 3. Bước 3 ( Dấu hiệu bài toán không có phương án tối ưu) Nếu ∆k > 0 và Zrj ≤ 0 với mọi j = 1, 2,...., m thì bài toán không có phương án tối ưu ( Định kí 1.10): dừng quá trình giải. Trái lại chuyển sang bước 4 1516Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bước 4 ( Chọn cột quay) Chọn s = max{j : ∆j  0} Chuyển sang bước 5 Bước 5 (Chọn dòng quay) Chọn r = min{i : (B−1b)i/zis, zis  0} làm dòng quay và zrs gọi là phần tử xoay. Chuyển sang bước 6 Bước 6. Biến đôi bảng đơn hình( theo quy tắc hình chữ nhật).Trở lại bước 2 Nếu bài toán quy hoạch tuyến tính có phương án và mọi phương án cực biên của bài toán là không suy biến thì thuật toán đơn hình gốc sẽ cho ra phương án tối ưu hoặc phát hiện bài toán không có phương án tối ưu ( trị tối ưu vô cực ) sau một số hữu hạn lần thay đổi phương án cực biên. Ví dụ 1.7 Xét bài toán quy hoạch tuyến tính dạng chính tắc sau đây: f(x) = −14x1 − 12x2 → min 1617Số hóa bở