ĐẠ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 Chun ngành: TỐ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 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn NGUYỄN THỊ HUỆ Đề tài: CẢI TIẾN THUẬT TỐN ĐƠN HÌNH GIẢI QUY HOẠCH TUYẾN TÍNH Soạn thảo văn LATEX công cụ MikTeX & TeXmaker Thái Nguyên, ngày 10 tháng 10 năm 2011 1Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục KIẾN THỨC CHUẨN BỊ 1.1 1.2 1.3 BÀI TỐN QUY HOẠCH TUYẾN TÍNH VÀ TÍNH CHẤT 1.1.1 Nội dung toán 1.1.2 Một số tính chất BÀI TỐN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU 11 1.2.1 Dạng toán đối ngẫu 11 1.2.2 Định lí đối ngẫu 12 PHƯƠNG PHÁP ĐƠN HÌNH 13 1.3.1 Thuật tốn đơn hình gốc 14 1.3.2 Thuật tốn đơn hình đối ngẫu 17 PHƯƠNG PHÁP ĐƠN HÌNH GỐC - ĐỐI NGẪU CẢI BIÊN 22 2.1 2.2 2.3 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TOÁN 22 2.1.1 Nội dung toán kí hiệu 22 2.1.2 Ý tưởng thuật toán 23 THUẬT TỐN ĐƠN HÌNH GỐC - ĐỐI NGẪU CẢI BIÊN (RPDSA) 25 PHƯƠNG PHÁP M - LỚN ( BIG M - METHOD) 27 Tìm sở đối ngẫu chấp nhận B phân hoạch ( B, N ) ban đầu 27 Tìm điểm gốc chấp nhận y ban đầu 27 2.3.1 2.3.2 2Số hóa Trung tâm Học liệu – Đại học Thái Nguyên1 http://www.lrc-tnu.edu.vn 2.3.3 Phương pháp M - lớn ( Big - M Method 28 2.3.4 VÍ DỤ MINH HỌA 30 HAI PHƯƠNG PHÁP CẢI TIẾN KHÁC 3.1 3.2 3.3 33 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TOÁN 33 3.1.1 Nội dung tốn kí hiệu 33 3.1.2 Ý tưởng thuật toán 34 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 PHƯƠNG PHÁP CƠSIN ĐƠN HÌNH 41 3Số hóa Trung tâm Học liệu – Đại học Thái Nguyên2 http://www.lrc-tnu.edu.vn LỜI NĨI ĐẦU Quy hoạch tuyến tính tốn tìm cực đại ( hay cực tiểu ) hàm tuyến tính với biến số thỏa mãn phương trình hay bất phương trình tuyến tính Quy hoạch tuyến tính lớp tốn tối ưu quan trọng ứng dụng rộng rãi thực tiễn Thuật tốn đơn hình Dantzig đề xuất từ năm 1947, dựa nguyên tắc xoay vần dùng rộng rãi có hiệu để giải tốn quy hoạch tuyến tính Tuy nhiên, mặt lý thuyết thuật tốn thời gian mũ ( thời gian tính phụ thuộc theo cấp độ hàm mũ vào độ dài liệu toán cần giải ) Vì thế, nhiều nghiên cứu tiến hành nhằm cải tiến lý thuyết lẫn hiệu tính tốn thực tế Về lý thuyết, thành tựu bật chứng minh tốn quy hoạch tuyến tính giải thuật toán thời gian đa thức L G Khachian ([8], 1979) người đề xuất thuật tốn ellipsoid giải quy hoạch tuyến tính thời gian đa thức, dựa nghiên cứu năm 60 - 70 kỉ trước, chủ yếu Liên Xô (trước đây), tác giả khác, trước Khachian thực 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 có độ phức tạp đa thức có hiệu tính tốn cao đặc biệt tốn tuyến tính cỡ lớn Cả hai toán thuộc loại phương pháp điểm Sau có nhiều mở rộng phương pháp điểm (xem [9]) để giải tốn tối ưu phi tuyến, quy hoạch lồi tồ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 tốn đơn hình cho đạt hiệ tính tốn cao Trong đó, đáng 4Số hóa Trung tâm Học liệu – Đại học Thái Nguyên3 http://www.lrc-tnu.edu.vn kể có thuật tốn đơn hình gốc đối ngẫu K Paparrizos et al., ([10], 2003) thuật toán cải tiến sở ban đầu cho thuật tốn đơn hình H V Junior M P E Lins đề xuất ([6], 2005) thuật tốn sin đơn hình H W Corley et al., đề xuất ([5], 2005) Kết tính tốn toán thử nghiệm cho thấy thuật tốn hiệu thuật tốn đơn hình cổ điển khoảng 30% tỏ có triển vọng Luận văn nhằm tìm hiểu giới thiệu số thuật tốn cải tiến thuật tốn đơn hình, thuộc nhóm thứ hai kể Cụ thể luận văn trình bày phương pháp đơn hình điểm ngồi (EPSA, RPDSA), phương pháp góc nghiêng nhỏ (MA) phương pháp cơsin đơn hình (CSA) Các thuật tốn có ý tưởng rõ ràng, dễ thực thi, khối lượng tính tốn giảm hiệu tính tốn cao Vì thế, tìm hiểu nghiên cứu chủ đề cần thiết hữu ích, giúp hiểu rõ mở rộng ứng dụng phương pháp đơn hình thực tiễn Nội dung luận văn chia làm ba chương: Chương 1: Kiến thức chuẩn bị Nhắc lại tóm tắt số kiến thức cần thiết nài tốn quy hoạch tuyến tính tốn quy hoạch tuyến tính đối ngẫu tính chất chúng, phương pháp đơn hình đơn hình đối ngẫu giải tốn quy hoạch tuyến tính Nhiều khái niệm, kiện trình bày chương giải thích, minh họa qua ví dụ số hình vẽ cụ thể Các kiến thức dùng đến 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 tốn đơn hình gốc - đối ngẫu cải biên (RPDSA) mà thực chất cải biên thuật tốn đơn hình đối ngẫu Thuật tốn RPDSA xem thuật tốn đơn hình điểm ngồi ( exterior point simple algorithm - EPSA), nghiệm sở k thuật tốn tạo ln nằm ngồi miền chấp nhận tố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ỏ giải quy hoạch tuyến tính tắc phương pháp sin đơn hình giải quy hoạch tuyến tính chuẩn tắc Cả hai phương pháp dựa nhận xét chung đỉnh tối ưu toán gốc hay đối ngẫu thường gần với đỉnh tạo nên ràng buộc mà góc véc tơ gradian chúng với véc tơ hệ số mục tiêu nhỏ 5Số hóa Trung tâm Học liệu – Đại học Thái Nguyên4 http://www.lrc-tnu.edu.vn Phương pháp đầu chọn véctơ ràng buộc làm sở xuất phát, phương pháp sau đưa dần ràng buộc vào tốn để giải Do thời gian kiến thức nhiều hạn chế nên luận văn đề cập tới nội dung thuật tốn kiểu đơn hình giải quy hoạch tuyến tính, chưa sâu vào kĩ thuật lập trình cụ thể Trong kĩ thuật viết luận văn trình xử lý văn chắn khơng tránh khỏi sai xót định Tơi mong nhận đóng góp thầy, bạn đồng nghiệp để luận văn xác hồn thiệ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 đỡ suốt q trình làm luận văn Tơi xin trân trọng cảm ơn thầy, cô giáo trường Đại Học Khoa Học - Đại Học Thái Nguyên, Viện Tốn học - Viện Khoa Học Cơng Nghệ Việt Nam, giảng dạy tạo điều kiện thuận lợi q trình tơi học tập nghiên cứu Tôi xin chân thành cảm ơn ban giám hiệu, Phòng, Ban chức trường Cao Đẳng Công Nghệ Kinh tế Công Nghiệp thành phố Thái Nguyên tập thể bạn bè đồng nghiệp gia đình quan tâm giúp đỡ, động viên để tơi hoàn thành tốt luận văn Thái Nguyên, tháng 9/2011 6Số hóa Trung tâm Học liệu – Đại học Thái Nguyên5 http://www.lrc-tnu.edu.vn Chương KIẾN THỨC CHUẨN BỊ Chương trình bày số kiến thức cần thiết quy hoạch tuyến tính, phương pháp đơn hình ( thuật tốn đơn hình gốc thuật tốn đơn hình đối ngẫu ) đối ngẫu quy hoạch tuyến tính Nội dung chương chủ yếu dựa tài liệu tham khảo [1] - [4] 1.1 BÀI TỐN QUY HOẠCH TUYẾN TÍNH VÀ TÍNH CHẤT Quy hoạch tuyến tính tốn tìm cực tiểu ( cực đại ) hàm tuyến tính f (x) tập lồi đa diện D ⊂ Rn Quy hoạch tuyến tính lớp tốn tối ưu quan trọng ứng dụng rộng rãi thực tiễn Nó bắt nguồn từ nững nghiên cứu nhà bác học Nga tiếng, Viện sĩ L V Kantorovich loạt cơng trình kế hoạch hóa sản xuất cơng bố năm 939 thực phát triển mạnh mẽ kể từ nhà toán học Mỹ G B Dantzig đề xuất thuật tốn đơn hình giải quy hoạch tuyến tính vào năm 1947 1.1.1 Nội dung toán Bài toán quy hoach tuyến tính thường viết số dạng sau: Dạng tổng quát ( abstract form ): min{f (x) = cT x : x ∈ D} 7Số hóa Trung tâm Học liệu – Đại học Thái Nguyên6 http://www.lrc-tnu.edu.vn c ∈ Rn , D ⊂ Rn tập lồi đa diện, tức tập nghiệm hệ phương trình bất phương trình tuyến tính T kí hiệu chuyển vị véctơ ( ma trận ) Dạng chuẩn ( standard form): min{f (x) = cT x : Ax ≥ b, x ≥ 0} A ∈ Rm×n (ma trận cỡ m x n), b ∈ Rm , c, x ∈ Rn , x ≥ Trong toán này, tập D = {x ∈ Rn : Ax ≥ b, x ≥ 0} 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 → với điều kiện x1 + 2x2 ≥ 5, 3x1 + x2 ≥ 4, x1 ≥ 0, x2 ≥ Dạng tắc ( canonical form): min{f (x) = cT x : Ax = b, x ≥ 0} với kí hiệu Ví dụ 1.2 Quy hoạch tuyến tính dạng tắc ba biến: x1 + 3x2 + 2x3 → với điều kiện x1 − x2 + x3 = 5, 2x1 + x2 − x3 = 4, x1 + x2 + x3 = 3, x1 ≥ 0, x2 ≥ 0, x3 ≥ 8Số hóa Trung tâm Học liệu – Đại học Thái Nguyên7 http://www.lrc-tnu.edu.vn Trong dạng trên, f gọi hàm mục tiêu, D gọi tập ràng buộc hay miền chấp nhận được, điểm x = (x1 , x2 , , xn )T ∈ D gọi phương án hay lời giải chấp nhận toán Một phương án cực tiểu ( cực đại ) hàm mục tiêu gọi phương án tối ưu hay lời giải tối ưu Với tốn quy hoạch tuyến tính xảy khả sau: a) Bài tốn khơng có phương án ( tập ràng buộc D rỗng ) b) Bài tốn có phương án khơng có phương án tối ưu c) Bài tố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 để quy hoạch tuyến tính có phương án tối ưu: Định lí 1.1: Nếu quy hoạch tuyến tính có phương án hàm mục tiêu bị chặn miền ràng buộc (đối với tốn min) tốn chắn có phương án tối ưu Nhận xét 1.1: Định lí 1.1 cho tốn quy hoạch tuyến tính, định lí khơng cịn hàm mục tiêu ràng buộc khơng cịn tuyến tính Sau hai ví dụ chứng minh cho nhận xét Ví dụ 1.3 Xét tốn min{f (x1 , x2 ) = x2 : x1 x2 ≥ 1, x1 ≥ 0} Miền chấp nhận D = {x ∈ R2 : x1 x2 ≥ 1, x1 ≥ 0} tập lồi khác rỗng, không la tập lồi đa diện Tuy hàm mục tiêu f (x) = x2 tuyến tính f (x) ≥ với x ∈ D ( f bị chặn D), rõ ràng tốn khơng có phương án tối ưu, infx∈D f (x) = (xem Hình 1.1) 9Số hóa Trung tâm Học liệu – Đại học Thái Nguyên8 http://www.lrc-tnu.edu.vn Chương HAI PHƯƠNG PHÁP CẢI TIẾN KHÁC Chương trình bày cách tiếp cận khác cho vấn đề cải tiến thuật toán xoay vần kiểu đơn hình giải quy hoạch tuyến tính Ý tưởng xuất phát từ đỉnh miền chấp nhận cho gần với đỉnh tối ưu, nhờ làm giảm số bước lặp đơn hình ( khoảng 33% theo tính tốn thử nghiệm) Thuộc hướng tiếp cận có hai phương pháp góc nghiêng nhỏ phương pháp cơsin đơn hình Nội dung chương chủ yếu dựa tài liệu [3], [5] [6] 3.1 3.1.1 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TỐN Nội dung tốn kí hiệu Xét tốn quy hoạch tuyến tính sau đây, gọi toán gốc: min{f(x) = cT x : Ax = b, x ≥ 0}, (LP ) A ∈ Rm×n (ma trận m hàng n cột), c, x ∈ Rn , b ∈ Rm T kí hiệu chuyển vị Giả thiết m ≤ n ma trận hệ số A có hạng m (full row rank) Đối ngẫu (LP) toán: max{bT y : AT y ≤ c} hay dạng tương đương: max{g(y) = bT y : AT y + s = c, s ≥ 0}, (DP) A ∈ Rm×n , y, b ∈ Rm , c, s ∈ Rn Cũng chương trước, ta sử dụng kí hiệu sau: aij phần 34Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 33 http://www.lrc-tnu.edu.vn tử hàng i cột j A; Aˆi (i số dưới) hàng thứ i A; Aj (j số trên) cột thứ j A J J¯ hai tập số cho J ∪ J¯ = {1, 2, ., n} v J ∩ J¯ =∅ Phần tử thứ r tập số J kí hiệu J(r) Thành phần thứ j √ véc tơ x kí hiệu xj Chuẩn Euclid véc tơ x, kí hiệu x , số xT x Nếu J gồm m số hệ véc tơ cột Aj : j ∈ J} độc lập tuyến tính J gọi sở B = {Aj : j ∈ J} gọi ma trận ¯ Khi đó, (B,N) gọi phân hoạch sở sở Đặt N = {Aj : j ∈ J} ¯ A Với x ∈ Rn , kí hiệu xB = {xj : j ∈ J} xN = {xj : j ∈ J} Nghiệm xB = B −1 b, xN = gọi nghiệm sở Cơ sở B gọi gốc chấp nhận xB ≥ Đặt cB = {cj : j ∈ J} véc tơ hàng y T = (cB )T B −1 gọi nhân twr đơn hình (simplex multipliers) Khi đó, y nghiệm sở (DP) Cơ sở B gọi đối ngẫu chấp nhận s = c − AT y ≥ Một sở mà nghiệm (xB , xN ) chấp nhận (LP) nghiệm (y, s) chấp nhận (DP) gọi sở tối ưu (với nghiệm ta ln có cT x = bT y ) Bảng đơn hình tắc có dạng sau: 3.1.2 Ý tưởng thuật toán Giả sử B (ma trận) sở tối ưu tốn (LP) Khi đó, nghiệm sở đối ngẫu y với y T = (cB )T B −1 đỉnh thuộc miền ràng buộc toán đối ngẫu (DP) Nghiệm tạo nên giao m ràng buộc chặt độc lập tuyến tính (m biến số đối ngẫu) Ta nhận thấy m ràng buộc ràng buộc có góc nghiêng gần với góc nghiêng hàm mục tiêu đối ngẫu Điều minh họa 35Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 34 http://www.lrc-tnu.edu.vn Hình 3.1, có đường nét đứt thể hàm mục tiêu đường nét đậm biểu thị ràng buộc gần độ nghiêng với hàm mục tiêu Vì thế, biến gốc(các biến xj tốn (LP) có tương ứng 1-1 với ràng buộc toán đối ngẫu (DP) nên sở tối ưu toán gốc tạo nên biến tương ứng với ràng buộc đối ngẫu mà giao ràng buộc đỉnh tối ưu toán đối ngẫu (DP) Ta quy ước gọi ràng buộc CA ràng buộc đối ngẫu có góc nghiêng gần với góc nghiêng hàm mục tiêu đối ngẫu sở CA sở tạo nên ràng buộc CA (Closest in Angle) Do giá trị tối ưu hàm mục tiêu toán gốc đối ngẫu nên ta lấy sở CA làm sở xuất phát giải tốn (LP) Để tìm ràng buộc đối ngẫu tạo nên sở CA, ta tính góc (hay cơsin góc) véc tơ radian ràng bc véc tơ radian mục tiêu Đỉnh tối ưu gần với đỉnh tạo m ràng buộc độc lập tuyến tính có góc bé (cơsin lớn nhất) Có thể xảy khả sau: TH1: Cơ sở gốc đối ngẫu chấp nhận Cơ sở tối ưu: dừng 36Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 35 http://www.lrc-tnu.edu.vn TH2: Cơ sở gốc chấp nhận được, không đối ngẫu chấp nhận được: Giải (LP) theo thuật toán đơn hình gốc nhận lời giải tối ưu TH3: Cơ sở đối ngẫu chấp nhận được, không gốc chấp nhận được: Giải (LP) theo thuật tốn đơn hình đối ngẫu nhận lời giải tối ưu TH4: Cơ sở không gốc đối ngẫu chấp nhận được: Sửa toán (LP) biến đổi sở thành đối ngẫu chấp nhận (TH3) nhờ dùng phương pháp M - lớn (Big M - method) Sau giải (LP) theo thuật tốn đơn hình đối ngẫu nhận lời giải tối ưu Phương pháp biến đổi sở không gốc đối ngẫu chấp nhận thành sở đối ngẫu chấp nhận biến thể phương pháp M - lớn gọi kĩ thuật biến giả.Phương pháp sau: Giả sử sở B không gốc đối ngẫu chấp nhận Như vậy, có phần tử xB (véc tơ biến sở (LP)) biến sj s (véc tơ biến bù (DP)) có giá trị âm Vì ta muốn tìm nghiệm đối ngẫu chấp nhận (nếu toán (DP) có nghiệm chấp nhận được) nên ta cần biến đổi s thành véc tơ không âm Nếu ta thêm vào toán (DP) biến snew buộc biến nhận giá trị tối ưu sở CA biến đổi thành sở chấp tốn (DP) mới, kí hiệu (DP1 ): g(y) = bT y + M snew → max (DP1 ) với điều kiện y T Aj + sj = cj ∀j ∈ J T j y A + sj + snew = cj ∀j ∈ J¯ s ≥ 0, snew ≤ 0, M → +∞ Vì snew nhận giá trị âm nên làm cho tất biến sj khác có 37Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 36 http://www.lrc-tnu.edu.vn giá trị khơng âm Sau đó, giả sử ràng buộc y T Aj + sj + snew = cj ¯ s ≥ 0, snew ≤ ∀j ∈ J, chấp nhận được, hệ số mục tiêu biến snew toán (DP1 ) số lớn nên giá trị tối ưu snew (DP1 ) có nghiệm chấp nhận Ta không thêm biến bù snew vào ràng buộc j với j ∈ J, ràng buộc dã chấp nhận đươc tức giá trị biến bù Giá trị biến snew cần có cho ràng buộc (DP1 ) chấp nhận giá trị nhỏ biến sj sN Vì thế, ta cần thêm vào sở J số biến có giá trị nhỏ nhận sở đối ngẫu chấp nhận Cách làm tương đương với việc ta thêm vào (LP) ràng buộc phụ xét toán (LP1 ) (cB )T xB + (cN )T xN (LP1 ) với điều kiện BxB + N xN = b eT xN + xn+1 = M xB , xN , xn+1 ≥ (M - số dương đủ lớn, e ∈ Rn−m - véc tơ gồm toàn số xn+1 - biến ¯ < sở đối ngẫu bù) Khi đó, J ∪ {p} với sp = min{sj : j ∈ J} chấp nhận (LP1 ) Ở đây, sN = cN − N T y với y T = (cB )T B −1 , tức sN = cN − (B −1 N )T cB 3.2 3.2.1 PHƯƠNG PHÁP GĨC NGHIÊNG NHỎ NHẤT Thuật tốn Có thể mơ tả hình thức ý tưởng sau Bước Tính góc tạo cột A (hàng AT - ràng buộc đối ngẫu) véc tơ b (hệ số mục tiêu đối ngẫu): bT A j angle(xj ) = arccos j , j = 1, 2, n A b 38Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 37 (3.1) http://www.lrc-tnu.edu.vn Bước Cơ sở ban đầu cho (LP): J = m số đầu, xếp theo góc tăng dần ( giả sử {Aj : j ∈ J} độc lập tuyến tính) Đặt B = {Aj : j ∈ J} Bước Tính xB = B −1 b, y T = (cB )T B −1 , sN = cN − N T y = cN − (B −1 N )T cB , ¯ chọn p ∈ J¯ cho sp = β α = min{xj : j ∈ J}, β = min{sj : j ∈ J}, Bước a) α ≥ 0, β ≥ ⇒ B sở tối ưu Dừng thuật toán: (xB , xN ) lời giải b) α ≥ 0, β < ⇒ giải (LP) theo đơn hình gốc, sau dừng thuật tốn c) α < 0, β ≥ ⇒ giải (LP) theo đơn hình đối ngẫu, dừng thuật toán d) α < 0, β < ⇒ dùng phương pháp M - lớn + Thêm vào (LP) ràng buộc phụ eT xN + xn+1 = M (M số lớn tùy ý, e ∈ Rn−m gồm toàn số 1) nhận toán (LP1 ) + Đặt B ← B ∪ {Ap }, giải tốn (LP1 ) theo đơn hình đối ngẫu Cũng phương pháp toán M với quy hoạch tuyến tính, để tránh phải chọn số M đủ lớn, tính tốn ta tách vế phải ràng buộc toán (LP1 ) thành hai phần, hệ số phụ thuộc M không phụ thuộc M nhau: b = b1 + M b2 với b1 = (b, 0)T b2 = (0, , 0, 1)T Khi đó, giá trị bến xj , j ∈ J có dạng: xj = αj + M βj xj ≥ βj > βj = αj ≥ Cũng vậy, biến ¯ có dạng sj = uj + M vj sj ≥ vj > 0, sj , j ∈ J, vj = uj ≥ 39Số hóa Trung tâm Học liệu – Đại học Thái Ngun 38 http://www.lrc-tnu.edu.vn 3.2.2 Ví dụ 3.1 Giải tốn (LP) sau đây: f (x) = 10x1 + 26x2 + 11x3 + 17x4 + 32x5 → với điều kiện −x1 + x2 + x3 + x4 + 4x5 = 2x1 + 4x2 + x3 + 2x4 + x5 = x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ Bài toán đối ngẫu (DP) có dạng: g(y) = 6y1 + 5y2 → max với điều kiện −y1 + 2y2 ≤ 10 y1 + 4y2 ≤ 26 y1 + y2 ≤ 11 y1 + 2y2 ≤ 17 4y1 + y2 ≤ 32 Góc cột Aj A vectơ b cho bảng 3.1 Bảng cho thấy chọn sở ban đầu cho (LP) B = {A3 , A4 } 40Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 39 http://www.lrc-tnu.edu.vn Bảng đơn hình tương ứng với sở B chọn có dạng: Do có x4 = −1 < s2 = −3 < nên B = {A3 , A4 } không sở gốc đối ngẫu chấp nhận Vì ta dùng phương pháp M - lớn: đưa vào (LP) ràng buộc phụ x1 + x2 + x5 + xn+1 = M, xn+1 ≥ đưa cột A2 (ứng với s2 nhỏ nhất) vào sở, ta nhận sở ban đầu cho toán (LP1 ) B = {A2 , A3 , A4 } Bảng đơn hình tương ứng với sở có dạng (chọn M = 1000): 41Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 40 http://www.lrc-tnu.edu.vn Bảng cho ta thấy sở B = {A2 , A3 , A4 } không gốc chấp nhận (do x4 = -3001 < ), đối ngẫu chấp nhận (LP1 ) Vì ta thực biến đổi bảng theo thuật tốn đơn hình đối ngẫu: loại x4 khỏi sở đưa xn+1 vào sở ta nhận sở B = {A2 , A3 , An+1 } với bảng đơn hình: Tiếp đó, loại x2 khỏi sở đưa x5 vào sở ta nhận sở tối ưu (LP1 ), B = {A5 , A3 , An+1 } với bảng đơn hình (tối ưu): Do sn+1 = nên Bopt = {A3 , A5 } sở tối ưu lời giải tối ưu T opt = (7 4)T ) toán (LP) xopt = (0 14 3 ) với fmin = 62.(y 3.3 PHƯƠNG PHÁP CƠSIN ĐƠN HÌNH Xét tốn (LP) cho dạng chuẩn: max{z = cT x : Ax ≤ b, x ≥ 0}, (LP ) Trong đó, A ∈ Rm×n (ma trận m hàng n cột, thường m ≥ n), c, x ∈ Rn b ∈ Rm Giả thiết D ≡ {x ∈ Rn : Ax ≤ b, x ≥ 0} = ∅ có ràng buộc r 42Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 41 http://www.lrc-tnu.edu.vn cho arj > với j br > Khi đó, D bị chặn ( xj ≤ abrjr với j ) tốn chắn có lời giải tối ưu Kí hiệu hàng thứ i ma trận A Aj ( i số ) Thay cho giải toán với tất ràng buộc, phương pháp cơsin đơn hình tốn với ràng buộc (cùng ràng buộc dấu), sau (nếu cần ) thêm dần vào toán ràng buộc một, theo thứ tự sin góc véc tơ gradian ràng buộc với véc tơ hệ số mục tiêu giảm dần (tức góc tăng dần) Nếu lời giải tối ưu tốn trước thỏa mãn ràng buộc cịn lại lời giải cần tìm tốn ban đầu Nếu trái lại chọn đưa vào toán ràng buộc vi phạm theo thứ tự kể dùng kĩ thuật tái tối ưu hóa giải tốn Q trình tiếp tục nhận lời giải tối ưu toán ban đầu Thuật tốn sin đơn hình tiến hành theo bước sau đây: Bước T Tính cosθi = Aci A ic , i = 1, , m(i = r) Xếp ràng buộc theo thứ tự cosθ giảm dần (góc θi tăng dần Bước Giải (P1 max{cT x : (Ar )T x ≤ br , x ≥ 0} Giả sử lời giải x1 , đặt k = Bước Kiểm tra ràng buộc lại theo thứ tự cosθi giảm dần Chọn ràng buộc xk vi phạm, sang bước Trái lại, xk lời giải tối ưu: Dừng thuật tốn 43Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 42 http://www.lrc-tnu.edu.vn Bước Đặt k ← k + Thêm ràng buộc vi phạm vào bảng đơn hình cuối (Pk ) nhận (Pk+1 ) Dùng đơn hình đối ngẫu tìm lời giải tối ưu xk Trở lại bước Thuật tốn cơsin đơn hình tiếp tục nghiên cứu cải tiến thử nghiệm Tuy nhiên, kết tính tốn cho thấy so với thuật tốn đơn hình thơng thường, thuật tốn cơsin đơn hình có số nét đặc điểm sau: • Tỏ hiệu toán quy hoạch tuyến tính cỡ nhỏ • Khơng cần dùng đến biến giả • Bỏ qua ràng buộc thừa • Có khả ngăn ngừa tượng xoay vịng • Chạy tốt toán Klee - Minty ( thuật tốn đơn hình có thời gian mũ ) Ví dụ 3.2 (xem [5]) Giải toán quy hoạch tuyến tính dạng chuẩn: z = 4x1 + 5x2 + 9x3 + 11x4 → max với điều kiện 3x1 + 5x2 + 10x3 + 15x4 ≤ 100, x1 + x2 + x3 + x4 ≤ 15, 7x1 + 5x2 + 3x3 + 2x4 ≤ 120, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ Giải: Các giá trị cosθi bước với hai số lẻ thập phân, tương ứng với ba ràng buộc toán, 0,99; 0,93 0,70 Mỗi ràng buộc có tác dụng chặn miền chấp nhận tốn bỏ qua bước Do ràng buộc đầu có cosθi lớn nên tốn nới lỏng cần giải có dạng: z = 4x1 + 5x2 + 9x3 + 11x4 → max với điều kiện 3x1 + 5x2 + 10x3 + 15x4 ≤ 100, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 44Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 43 http://www.lrc-tnu.edu.vn Gải toán áp dụng thuật toán cơsin đơn hình, ta nhận bảng đơn hình sau: Ràng buộc thứ hai trở thành ràng buộc chặt bảng thứ hai Trong 55 695 bảng thứ ba, lời giải x1 = 50 , x2 = 0, x3 = , (z = ) thỏa mãn ràng buộc thứ ba cịn lại, lời giải tối ưu toán ban đầu Các biến x5 x6 biến bù đưa ràng buộc thứ thứ hai vào toán Ví dụ sau cho thấy thuật tốn cơsin đơn hình xử lí hiệu tốn Klee - Minty, lớp tốn đưa để chứng tỏ thuật tốn đơn hình thuật tốn thời gian mũ: số bước lặp đơn hình cần để giải toán tỉ lệ với 2n (n số biến tốn), thuật tốn cơsin đơn hình lần lặp Ví dụ 3.3 Giải toán Klee - Minty biến: z = 4x1 + 2x2 + x3 → max với điều kiện 8x1 + 4x2 + x3 ≤ 125 4x1 + x2 ≤ 25 x1 ≤5 x1 ≥ 0, x2 ≥ 0, x3 ≥ Giải: 45Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 44 http://www.lrc-tnu.edu.vn Bước Các giá trị cosθi với hai số lẻ thập phân, tương ứng với ba ràng buộc tốn, 0,99; 0,95 0,87 Bước Ràng buộc thứ có tác dụng chặn miền chấp nhận toán nên toán nới lỏng cần giải có dạng: z = 4x1 + 2x2 + x3 → max với điều kiện 8x1 + 4x2 + x3 ≤ 125 x1 ≥ 0, x2 ≥ 0, x3 ≥ Giải toán áp dụng thuật tốn sin đơn hình, ta nhận bảng đơn hình sau Bảng thứ hai cho lời giải tối ưu: x1 = x2 = 0, x3 = 1, z = 125 (x4 ,x5 hai biến bù đưa ràng buộc thứ thứ hai vào tốn) • Tóm lại, chương giới thiệu phương pháp góc nghiêng nhỏ để tìm sở ban đầu cho tốn quy hoạch tuyến tính tắc phương pháp sin đơn hình có ý tưởng tương tự, giải toán quy hoạch tuyến tính dạng chuẩn Các kết tính tốn thử nghiệm máy (theo phương pháp ) nêu tài liệu tham khảo [5] [6] Ở đưa ví dụ số đơn giản để minh họa cho thuật tốn trình bày 46Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 45 http://www.lrc-tnu.edu.vn KẾT LUẬN Quy hoạch tuyến tính toán tối ưu đơn giản sử dụng rộng rãi thực tiễn Thuật tốn đơn hình thuật tốn có hiệu để giải quy hoạch tuyến tính Tuy nhiên, lý thuyết thuật thời gian mũ, có nhiều nghiên cứu nhằm cải tiến lý thuyết lẫn hiệu tính tốn thực tế Luận văn nhằm giới thiệu số kết nghiên cứu theo hướng thuật tốn cải tiến thuật tốn đơn hình cho có hiệu Luận văn đề cập tới nội dung sau Các kiến thức quy hoạch tuyến tính: tốn quy hoạch tuyến tính (LP) tốn quy hoạch tuyến tính đối ngẫu (DP) tính chất chúng, phương pháp đơn hình ( thuật tốn đơn hình gốc thuật tốn đơn hình đối ngẫu ) Phương pháp gốc - đối ngẫu cải biên (RPDSA) giải quy hoạch tuyến tính tắc Phương pháp tạo dãy nghiệm sở xk (LP) dãy nghiệm sở chấp nhận {(y k , sk )} (DP) hội tụ tới nghiệm tối ưu Có thể xem RPDSA cải biên phương pháp đơn hình đối ngẫu dạng phương pháp đơn hình điểm ngồi (EPSA) Phương pháp góc nghiêng nhỏ dựa nhận xét trực quan đỉnh tối ưu thường gần với đỉnh tạo nên ràng buộc mà góc véc tơ grandian chúng với véctơ hệ số mục tiêu nhỏ Phương pháp chọn ràng buộc làm sở xuất phát Phương pháp sin đơn hình dựa vào nhận xét trên, cách làm ngược lại: đưa dàn ràng buộc vào tốn nới lỏng để giải, nhận lời giải tối ưu Hướng phát triển đề tài nghiên cứu vận dụng thuật toán đề xuất vào số tốn tối ưu cụ thể 47Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 46 http://www.lrc-tnu.edu.vn TÀI LIỆU THAM KHẢO [1] N T B Kim, Giáo trình phương pháp tối ưu - Lý thuyết 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 phương pháp tối ưu.Nxb Khoa học Kỹ thuật Hà Nội, 1998 [3] T V Thiệu, Giáo trình tối ưu tuyến tính Nxb Đại Học Quốc Gia Hà Nội, 2004 [4] T V Thiệu 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 tốn đa thức 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 Algorithms in Convex Programing SIAM, Philadelphia, 1994 [10] K Paparrios et al., A New Efficient Primal Dual Simplex Algorithm Computers & Operation Reseach, 30 (2003), 1383 - 1399 48Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 47 http://www.lrc-tnu.edu.vn ... thức quy hoạch tuyến tính: tốn quy hoạch tuyến tính (LP) tốn quy hoạch tuyến tính đối ngẫu (DP) tính chất chúng, phương pháp đơn hình ( thuật tốn đơn hình gốc thuật tốn đơn hình đối ngẫu ) Phương. .. chương trình bày tốn quy hoạch tuyến tính tính chất, lý thuyết đối ngẫu quy hoạch tuyến tính, phương pháp đơn hình ( thuật tốn gốc thuật tốn đối ngẫu ) giải quy hoạch tuyến tính Có thể tìm thấy... quy hoạch đối ngẫu xảy khả sau đây: a) Cả quy hoạch có phương án b) Cả quy hoạch có phương án Khi quy hoạch có phương án tối ưu giá trị tối ưu hàm mục tiêu c) Một quy hoạch có phương án quy hoạch