Thạc Sĩ Cải tiến phương pháp đơn hình giải quy hoạch tuyến tính

Luận văn thạc sĩ năm 2011
Đề tài: CẢI TIẾN PHƯƠNG PHÁP ĐƠN HÌNH GIẢI QUY HOẠCH TUYẾN TÍNH

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 . c
1.1.1 Nội dung bài toán c
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 dố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 đdn hình gốc 14
1.3.2 Thuật toán đdn hình đối ngẫu . 17
2 PHƯƠNG PHÁP ĐƠN HÌ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 DƠ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Ì111 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 đưdc y ban đầu 27
2.3.3 Phưdng 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 TIEN 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 Dơx HÌNH 41

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 rĩề xuất từ năm 1947« dựa trên nguyên tắc xoay vần rĩượ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ề lv 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 rtã đề 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ỉ tritó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 rta 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

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àv 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 IĨ1Ở 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 quv hoạch tuyến tính và bài toán quv 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àv sẽ được dùng đến ở các chương sau.
Chương 2: Phương pháp đdn 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 - EPS A), vì các nghiệm cơ sỏ [SUP]k[/SUP] 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 phiídng 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 (lựa trên nhận xét chung là đỉnh tối lí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ỏ 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 cĩó vào bài toán để giai.
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 Iihấ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 Dại Học Khoa Học - Dạ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 Dang 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

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 đdn 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 TUYEN 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 c R". Quy hoạch tuyến tính là một trong nhftng 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ừ tiling nghiên crtu 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ế trt 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 hoaeh tuyến tính thường được viết ở một số dạng sau:
Dạng tống quát ( abstract form ):
min{/(x) = C[SUP]T[/SUP]X : X £ D}

trong đó c G R'\ D c R[SUP]n[/SUP] 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) = C[SUP]T[/SUP]X : Ax > ò, X >0}
trong đó A e R[SUP]mxn[/SUP] (ma trận cỡ m X n), b € R[SUP]m[/SUP], c, X e R[SUP]n[/SUP]\ X > 0 Trong bài toán này, tập D = {x G R[SUP]n[/SUP] : 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:
3xị 4- 2x2 min
với điều kiện
X\ 4- 2x2 > 5,
3xi 4- Xo > 4,
x\ > 0, X2 > 0.
Dạng chính tắc ( canonical form):
min{/(x) = C[SUP]T[/SUP]X : Ax = 6, 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:
x\ 4- 3x2 4- 2*3 —> min
với điều kiện
X\-X[SUB]2[/SUB] + X$ = 5,
2x\ + x-2 — = 4,
Xi 4- Xo 4- x[SUB]ẵ[/SUB] = 3,
X\ > 0. X2 > 0, X3 > 0.

TÀI LIỆU THAM KHẢO
[1] N. T .B. Kim, Giáo trình các phương pháp tối ưu - Lý thuyết và thuật toán,Nhập Nxb Đại Học Bách Khoa Hà Nội, 2008.
[2] L. D. Mưu, Nhập môn các phương pháp tối trtí.Nxb Khoa học Kỹ thuật Hà Nội, 1998.
[3] T. V. Thiệu, Giáo trình tối líu tuyến tính. Nxb Dại Học Quốc Gia Hà Nội, 2004.
[4] T. V. Thiệu và B. T. Tâm. Các phương pháp tối ưu hóa. Nxb Giao Thông Vận Tải, Hà Nội, 1998.
[5] H. w. Corley et al The cosine simple algrithm (2005).
[6] H. V. Junior and M. p. E. Lins, An improve initial basis for the simplex algorithm. Computers & Operation Reseach. 32 (2005), 1383 - 1393
[7] N. K. Karmarkar. A New Polynomial - Time Algorithm for Linear Programming. Combinatorica. 4: 373 - 395, 1984.
[8] L. G. Khachian. Thuật toán đa thức trong quy hoạch tuyến tính. Báo Cáo Viện Hàn Lâm Khoa Học Liên Xô, 1979, 244, N05. 1093 - 1096 (tiếng Nga).
[9] Y. Nesterov and A. Nemirovs. Interior - Point Polynomial Algo rithms in Convex Programing. SIAM. Philadelphia, 1994.
[10] K. Paparrios et al A New Efficient Primal Dual Simplex Al gorithm. Computers & Operation Reseach. 30 (2003). 1383 - 1399.