ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐỒN DUY LÂM THUẬT TỐN NĨN XOAY GIẢI BÀI TỐN QUY HOẠCH TUYẾN TÍNH DẠNG CHUẨN TRONG TRƯỜNG HỢP TÁI TỐI ƯU HĨA Chun ngành: Tốn Ứng Dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học TS.Nguyễn Anh Tuấn Thái Nguyên - 2013 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 Mở đầu Bài tốn tối ưu tổng qt số mơ hình tốn thực tế 1.1 Bài tốn tối ưu tổng quát 1.2 Một số mơ hình thực tế 1.2.1 Bài toán vốn đầu tư 1.2.2 Bài toán vận tải 1.2.3 Mơ hình phân bố máy bay cực tiểu tổng chi phí tồn mạng đường bay hàng khơng 1.3 Tập lồi đa diện 1.3.1 Một số khái niệm 1.4 Bài toán quy hoạch tuyến tính tổng quát số phương pháp giải 1.4.1 Bài toán quy hoạch tuyến tính tổng quát 1.4.2 Dạng chuẩn dạng tắc 1.4.3 Đưa toán quy hoạch tuyến tính dạng chuẩn dạng tắc 1.5 Một số phương pháp giải tốn quy hoạch tuyến tính 1.5.1 Phương pháp đơn hình [6] 1.5.2 Phương pháp đơn hình cải biên [6] 1.5.3 Phương pháp KARMARKAR (điểm trong)[6] Bài tốn quy hoạch tuyến tính dạng chuẩn tổng quát phương pháp nón xoay 2.1 Một số khái niệm liên quan đến hàm số tuyến tính 2.2 Khái niệm miền ràng buộc tuyến tính khơng bị chặn, phương vơ hạn chấp nhận hướng tăng, giảm hàm gần lồi-gần lõm 2.3 Bài tốn quy hoạch tuyến tính dạng chuẩn tổng qt 2.4 Khái niệm nón tuyến tính, cạnh nón nón - 2.4.1 Khái niệm nón đơn hình tuyến tính 2Số hóa Trung tâm Học liệu – Đại học Thái Nguyên ii 1 2 6 8 10 10 13 15 17 17 19 21 22 22 http://www.lrc-tnu.edu.vn 2.5 2.4.2 Khái niệm cạnh nón đơn hình 2.4.3 Khái niệm nón xoay M(r,s) sinh từ nón M 2.4.4 Định nghĩa Nón - Min Phương pháp nón xoay tuyến tính 2.5.1 Thuật tốn nón xoay tuyến tính 2.5.2 Bảng lặp giải tốn qui hoạch tuyến tính thuật tốn nón xoay tuyến tính ví dụ minh hoạ Bài tốn quy hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hóa thuật tốn nón xoay TT 3.1 Bài tốn quy hoạch tuyến tính dạng chuẩn tái tối ưu hố 3.2 Thuật tốn nón xoay tái tối ưu hóa 3.2.1 Xây dựng nón - ban đầu 3.2.2 Thuật tốn nón xoay TT 3.3 Bảng lặp nón xoay giải tốn qui hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hố thuật tốn TT ví dụ minh hoạ 3.4 Thuật tốn nón xoay TT giải ví dụ KLEE – MINTY với n=3 Kết luận Tài liệu tham khảo i 3Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 22 27 29 33 34 36 43 43 46 46 46 48 59 64 65 http://www.lrc-tnu.edu.vn Mở đầu Trong thập kỷ qua, lý thuyết tối ưu có bước tiến lớn với phát triển không ngừng công nghệ thông tin Nhiều nội dung kinh điển tưởng ổn định phương pháp giải tốn quy hoạch tuyến tính có đổi liên tục gắn liền với tên tuổi nhiều nhà toán học L.V Kantorovich (1939), George Dantzig (1947), Lemke (1954), Leonid Khachian (1979), Karmarkar (1984), Một lớp toán quy hoạch phi tuyến gần với quy hoạch tuyến tính tốn quy hoạch có hàm mục tiêu đơn điệu , mà gọi hàm gần lồi – gần lõm có thuật toán tương tự để giải thuật tốn đơn hình đơn hình đối ngẫu quy hoạch tuyến tính (xem [1], [5]) Luận văn trình bày phương pháp nón xoay tuyến tính giải trực tiếp tốn quy hoạch tuyến tính dạng chuẩn thuật tốn nón xoay tuyến tính giải cho tốn quy hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hố gọi thuật tốn nón xoay TT Trong trường hợp giải toán quy hoạch tuyến tính nguyên phương pháp cắt-nhánh cận tái tối ưu hố việc áp dụng thuật tốn nón xoay tỏ hiệu Như biết để có điểm chấp nhận miền ràng buộc ta phải giải toán quy hoạch tuyến tính khác Các tốn quy hoạch tuyến tính xây dựng từ thực tế nhiều chưa biết điểm chấp nhận miền ràng buộc, đồng thời miền ràng buộc bị thối hóa, chí ràng buộc miền khơng tương thích.Các thuật tốn trình bày luận văn giải tốn thuật tốn nón xoay trình bày luận văn xây dựng để giải trực tiếp cho toán quy hoạch tuyến tính dạng chuẩn khơng phải chuyển dạng tắc phương pháp đơn hình quen thuộc phương pháp đơn hình đối ngẫu, số chiều tốn khơng tăng lên, đồng thời hiệu giải toán trường hợp cần tái tối ưu thuận lợi áp dụng vào phương pháp cắt giải toán quy hoạch tuyến tính nguyên Luận văn gồm chương: Chương 1: Trình bày tốn quy hoạch tổng qt, khái niệm tập lồi số mơ hình thực tế đưa tốn quy hoạch tuyến tính dạng chuẩn với số phương pháp giải tốn quy ii 4Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn hoạch tuyến tính quen thuộc thơng dụng Chương 2: Trình bày khái niệm liên quan đến hàm số tuyến tính, từ làm sở lý thuyết cho việc xây dựng phương pháp nón xoay tuyến tính giải trực tiếp tốn quy hoạch tuyến tính dạng chuẩn biết nón-min hàm mục tiêu tốn Chương 3: (dựa phương pháp nón xoay đề nghị chương 2) Trình bày việc xây dựng thuật tốn nón xoay TT giải tốn quy hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hố ví dụ số minh hoạ cho thuật tốn Thuật tốn nón xoay TT giải tốn quy hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hố trình bày luận văn xây dựng chi tiết, bước thuật tốn trình bày cho dễ dàng lập trình chuyển sang chương trình máy tính ngôn ngữ Pascal, C, Java, Luận văn hoàn thành hướng dẫn đạo tận tình TS.Nguyễn Anh Tuấn - Tổng Cơng Ty Hàng Khơng Việt Nam Từ đáy lịng Em xin bày tỏ lòng biết ơn sâu sắc quan tâm động viên đạo tận tình hướng dẫn thầy Em xin chân thành cảm ơn thầy cô Trường Đại học Khoa Học - Đại học Thái Nguyên, Phòng đào tạo trường Đại học Khoa Học Đồng thời em gửi lời cảm ơn tới tập thể lớp Cao Học Toán k5 - Trường Đại học Khoa Học động viên giúp em trình học tập làm luận văn Tuy nhiên hiểu biết thân khuôn khổ luận văn thạc sĩ Nên trình nghiên cứu khơng tránh khỏi thiếu sót,em mong dạy đóng góp ý kiến thầy cô độc giả quan tâm tới luận văn Thái Nguyên, tháng năm 2013 Tác giả Đồn Duy Lâm iii 5Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương Bài tốn tối ưu tổng qt số mơ hình toán thực tế 1.1 Bài toán tối ưu tổng quát Bài toán tối ưu tổng quát phát biểu sau: Cực đại hoá (cực tiểu hoá) hàm f (x) → max(min), (1.1) gi (x)(≤, =, ≥)bi , i = 1, , m (1.2) x ∈ X ⊂ Rn (1.3) Với điều kiện Bài toán (1.1)–(1.3) gọi quy hoạch, hàm f (x) gọi hàm mục tiêu, hàm gi (x), i = 1, , m gọi hàm ràng buộc, đẳng thức hệ (1.2) gọi ràng buộc Tập hợp D = {x ∈ X \ gi (x)(≤, =, ≥)bi , i = 1, , m}, (1.4) Được gọi miền ràng buộc (hay miền chấp nhận được) Mỗi điểm (x = x1 , x2 , , xn ) ∈ D gọi phương án (hay lời giải chấp nhận được) Một phương án x∗ ∈ D đạt cực đại (hay cực tiểu) hàm mục tiêu, cụ thể : f (x∗ ) ≥ f (x), ∀x ∈ D, f (x∗ ) ≤ f (x), ∀x ∈ D Được gọi phương án tối ưu (hay lời giải) tốn (1.1) (1.3) 6Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Sau trình bày bước xây dựng, khảo sát phân tích mơ hình tốn học từ vấn đề thực tế Việc mơ hình hóa tốn học cho vấn đề thực tế chia làm bước: Bước 1: Xây dựng mơ hình định tính cho vấn đề thực tế, tức xác định yếu tố có ý nghĩa quan trọng xác lập quy luật mà chúng phải tuân theo Bước 2: Xây dựng mơ hình cho vấn đề xét, tức diễn tả lại dạng ngôn ngữ tốn học cho mơ hình định tính Bước 3: Sử dụng cơng cụ tốn học để khảo sát giả tốn hình thành Bước Bước 4: Phân tích kiểm định lại kết thu Bước Ở xảy hai khả sau: Khả 1: Mơ hình kết tính tốn phù hợp với thực tế Khi cần lập bảng tổng kết ghi rõ cách đặt vấn đề, mơ hình tốn học thuật tốn tối ưu, chương trình, cách chuẩn bị số liệu để đưa vào máy tính Khả 2: Mơ hình kết tính tốn khơng phù hợp với thực tế Trong trường hợp cần phải xem xét nguyên nhân 1.2 1.2.1 Một số mơ hình thực tế Bài tốn vốn đầu tư Người ta cần lượng tối thiểu chất dinh dưỡng (i = 1, , m) thức ăn (j = 1, , n) cung cấp Giả sử: aij số lượng chất dinh dưỡng loại i có đơn vị thức ăn loại j với (i = 1, , m) (j = 1, , n) bi nhu cầu tối thiểu loại dinh dưỡng i cj giá mua đơn vị thức ăn loại j Vấn đề đặt phải mua để tổng chi phí bỏ mà đáp ứng yêu cầu dinh dưỡng.Vấn đề giải theo mơ hình sau : Gọi xj ≥ (i = 1, n) số lượng thức ăn thứ j cần mua Tổng chi phí cho việc mua thức ăn : 7Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn n z= cj xj = c1 x1 + c2 x2 + cn xn j=1 Vì chi phí bỏ để mua thức ăn phải thấp nên yêu cầu cần thỏa mãn : n z = cj xj = c1 x1 + c2 x2 + cn xn j=1 Lượng dinh dưỡng i thu từ thức ăn ai1 x1 với i = → m Lượng dinh dưỡng i thu từ thức ăn ai2 x2 Lượng dinh dưỡng i thu từ thức ăn n ain xn Vậy lượng dinh dưỡng thứ i thu từ loại thức ăn : ai1 x1 + ai2 x2 + + ain xn với (i = → m) Vì lượng thứ i thu phải thỏa mãn yêu cầu bi dinh dưỡng loại nên ta có ràng buộc sau : ai1 x1 + ai2 x2 + + ain xn ≥ bi với (i = → m) ta có mơ hình tốn : n z = cj xj = c1 x1 + c2 x2 + cn xn j=1  a11 x1 + a12 x2 + + a1n xn ≥ b1      a21 x1 + a22 x2 + + a2n xn ≥ b2   a x + am2 x2 + + amn xn ≥ bm    m1 xj ≥ 0(j = 1, , n) 1.2.2 Bài tốn vận tải Có m kho hàng chứa loại hàng hóa (đánh số i = 1, , m), lượng hàng hóa kho i , i = 1, , m Gọi kho i điểm phát i Có n địa điểm tiêu thụ loại hàng (đánh số j = 1, , n với nhu cầu tiêu thụ điểm j bj , j = 1, , m) Gọi điểm tiêu thụ j điểm thu j Gọi cij cước vận chuyển đơn vị hàng hóa từ điểm phát i đến điểm thu j Hàng chuyển từ điểm phát i đến điểm thu j Hãy lập kế hoạch vận chuyển hàng hóa từ điểm phát tới điểm thu cho tổng chi phí vận chuyển nhỏ Ký hiệu xij 8Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn lượng hàng vận chuyển từ điểm phát i đến điểm thu j Khi ta có mơ hình tốn học: m n cij xij → min, i=1 j=1 Với điều kiện n xij = , i = 1, , m, j=1 m xij = bj , j = 1, , n, i=1 xij ≥ 0, i = 1, , m; j = 1, , n Ngoài cịn có điều kiện thu phát: m m = i=1 1.2.3 bj j=1 Mơ hình phân bố máy bay cực tiểu tổng chi phí tồn mạng đường bay hàng không d.1 Các tham số định toán: Giả sử khai thác sử dụng K loại máy bay (777, 767, A321, A330, A320, AT7, ),Mk số máy bay loại k khai thác sử dụng (k = 1, 2, , K), giả sử số sân bay (thành phố) tham gia vào mạng N Ta sử dụng ký hiệu sau đây: (i, j) chặng bay từ sân bay i đến sân bay j(i, j = 1, , N ) Ta giả thiết chiều dài trung bình Dij thực tế chiều dài thương mại chặng bay Pij số lượng khách trung bình dự báo có thu nhập thực tế chun chở chặng bay (i, j) (trong tuần) Sk số ghế tương ứng (số ghế tối đa phép xếp khách cho chặng bay loại máy bay k) gij ghế suất (hệ số sử dụng ghế suất) trung bình chặng bay (i, j) hmax - số khai thác bay trung bình lớn cho phép k máy bay loại k tuần vk - vận tốc bình quân thực tế máy bay loại k min(ij) max(ij) Fk , Fk tương ứng tần xuất bay nhiều (số chuyến bay tuần) loại máy bay k chặng bay (i, j) 9Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Cijk chi phí theo chuyến bay ( tuần) chặng bay (i, j) loại máy bay k fijk tần suất bay (số chuyến bay tuần) loại máy bay k chặng bay (i, j) (biến định) d.2 Hàm mục tiêu: Ta ký hiệu Cost tổng chi phí theo chuyến bay cho tất máy bay dang khai thác sử dụng thời kỳ phân tích (một tuần) tuyến bay tồn mạng Thời kỳ phân tích khoảng thời gian cần nghiên cứu cần phân tích mà ta quy định tuần, tháng, quý, sáu tháng, năm, Hàm mục tiêu C tổng chi phí cho chuyến bay tồn mạng xác định sau: Cijk fijk Cost = C0 + ij (1.5) k Trong C0 (chi phí cố định) tổng chi phí khơng phát sinh thêm chuyến bay thực như: giá thuê máy bay, bảo hiểm máy bay, bảo dưỡng sửa chữa máy bay, khấu hao thiết bị máy bay, quản lí chung Cijk chi phí biến đổi theo chuyến bay loại máy bay k xuất thực chuyến bay như: phục vụ hàng khách, bay, hàng hóa, nhiên liệu d.3 Các ràng buộc toán: Ràng buộc thương mại: min(ij) ≤ Fk max(ij) ≤ fijk ≤ Fk (1.6) Ràng buộc có nghĩa tần suất bay fijk loại máy bay k min(ij) max(ij) chặng bay (i, j) khơng Fk không nhiều Fk (ràng buộc hạn chế thương mại) Ràng buộc khai thác: Với vịng bay j (Pairing) ta có: fjik = i fijk (1.7) i (j = 1, 2, N, k = 1, 2, , K) Ràng buộc (1.7) có nghĩa khoảng thời gian phân tích (của chu kỳ bay) đội bay loại máy bay k rời sân bay j 10Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn tốn dạng tắc với số biến phụ thêm vào sau:   −3x1 − 5x2 − 4x3 − 6x4 →     3x1 + 2x2 − x3 + 2x4 + x5 = 60      x1 + x2 + 2x3 + x4 + x6 = 45 2x1 − 4x2 − 3x3 + 4x4 + x7 = 120   x1 + 2x2 − 2x3 + 2x4 + x8 = 30      x1 + x2 + x3 + x4 + x9 = 34    x ≥ 0, j = 1, , j Bảng đơn hình cho lời giải sau bước lặp: cj xj 0 0 Bc0 0 -6 Bc1 0 -6 -4 Bc2 x5 x6 x7 x8 x9 x5 x6 x7 x4 x9 x5 x6 x7 x4 x3 x1 -3 60 45 120 30 34 30 30 1/2 60 15 1/2 19 1/2 41/2 7/4 3/2 -1/4 101/2 -1/4 49/2 3/4 19/2 1/4 -10/4 P/A x2 -5 -4 0 -8 -1 0 -8 -1 x3 x4 x5 x6 x7 -4 -6 0 -1 0 1 -3 0 -2 [2] 0 1 0 0 1 0 0 1 0 -1 0 [2] 0 0 10 0 0 0 0 0 0 0 1 0 0 0 0 0 x8 0 0 0 -1 -1/2 -2 1/2 -1/2 -3 -3/4 1/4 -7/4 1/4 -1/4 -1/2 x9 0 0 0 0 -1/2 -3/2 -1/2 1/2 1/2 -5 Từ bảng đơn hình ta nhận phương án tối ưu xopt =(0, 0, 19/2, 49/2, 41/2, 3/2, 101/2, 0, 0).Vậy phương án tối ưu toán ban đầu xopt =(0, 0, 19/2, 49/2) Bây ta giải ví dụ theo thuật tốn nón xoay TT: Đưa số liệu ban đầu vào bảng nón xoay thu gọn tính tốn theo quy tắc chọn số đưa vào sở max ta được: 52 57Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn CS bj -3 -1 0 0 0 -60 -45 -120 -30 -34 (6) -45 1 0 -30 Bước x0 -34 1 0 -30 Bước x1 -4 -1 0 -4 0 0 0 0 -5 0 -1 -1 -3 -2 -1/3 -1/6 1/6 10 -1/2 -1/4 1/4 19/2 -6 Ai (x0 ) Ai (x1 ) 0 0 0 -10 -11 -1 -25 -23 0 -20 -25 -50 -41 -6 (1) -1/3 [-2/3] (5) -2/3 1/6 -1 -1/3 -1/6 25 -1/2 -3/4 -1 -1/4 49/2 Bảng nón xoay thu gọn cho lời giải sau bước lặp xopt =( 0, 0, 19/2, 49/2) Vậy ta nhận phương án tối ưu toán sau bước lặp Rõ ràng lời giải tốn tái tối ưu hố tìm theo thuật toán TT ngắn gọn phương pháp đơn hình, tốn giải phương pháp đơn hình số chiều tăng lên phải đưa tốn dạng tắc số bước lặp số phép tính tốn bước lặp nhiều rõ rệt 53 58Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ví dụ 3.3 Cho biết tốn quy hoạch tuyến tính dạng chuẩn sau[6]:  −20x1 − 30x2 →      −x1 ≤     −x2 ≤     −3.x1 + x2 − ≤     −x1 + x2 − ≤      −x1 + 2x2 − ≤ x2 − ≤   x1 + 2x2 − 18 ≤      x1 − ≤     x1 − x2 − ≤     x1 − 2x2 − ≤     x1 − 3x2 − ≤    x1 + x2 − 40/3 ≤ Có lời giải xopt =x0 =(26/3, 14/3) với tập số sở tương ứng {7, 12} với véc tơ phương cạnh nón – tương ứng với đỉnh xác định từ hệ (2.4) z07 ( 1, -1), z012 (-2, 1) Hãy giải toán tái tối ưu hoá toán thêm vào ràng buộc bổ sung sau: 4x1 + 5x2 ≤ 56 Dễ thấy lời giải toán ban đầu không thoả mãn ràng buộc bổ sung Bài toán tái tối ưu hoá tương ứng là:  −20x1 − 30x2 →     −x1 ≤      −x2 ≤     −3.x1 + x2 − ≤     −x1 + x2 − ≤     −x1 + 2x2 − ≤    x2 − ≤ x1 + 2x2 − 18 ≤      x1 − ≤     x1 − x2 − ≤     x1 − 2x2 − ≤     x1 − 3x2 − ≤     x1 + x2 − 40/3 ≤    4x1 + 5x2 − 56 ≤ Nếu ta giải ví dụ phương pháp đơn hình tốn phải 54 59Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn đưa dạng tắc thêm vào 11 biến bù sau:  −20x1 − 30x2 →     −3.x1 + x2 + x3 =      −x1 + x2 + x4 =     −x1 + 2x2 + x5 =     x2 + x6 =      x1 + 2x2 + x7 = 18 x1 + x8 =   x1 − x2 + x9 =      x1 − 2x2 + x10 =     x1 − 3x2 + x11 =     x1 + x2 + x12 = 40/3     4x1 + 5x2 + x13 = 56    xj ≥ 0, j = 1, 2, , 13 55 60Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn xj cj x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 0 0 0 0 0 0 -30 0 0 0 0 0 -30 -20 0 0 0 0 -30 -20 0 0 0 0 Bước x2 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 Bước x2 x1 x5 x6 x7 x8 x9 x10 x11 x12 x13 Bước x2 x1 x3 x6 x7 x8 x9 x10 x11 x12 x13 Bước P/ án 18 40/3 56 16 6 37/3 51 1 9 11 14 25/3 32 2 12 16 19/3 23 x1 x2 x3 -20 -30 -3 [1] -1 -1 0 1 0 -1 -2 -3 1 20 30 -3 1 [2] -1 -2 -1 -2 0 -2 -5 -8 -1 19 -5 110 -30 -1/2 -1/2 0 [1/2] 0 1/2 0 3/2 0 1/2 0 0 -1/2 0 -1 0 0 9/2 0 25 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 x4 0 0 0 0 0 0 0 0 0 0 0 3/2 1/2 -5/2 -3/2 -7/2 -1/2 5/2 -2 -19/2 -55 -1 -2 -5 [1] -1 13 70 56 61Số hóa Trung tâm Học liệu – Đại học Thái Nguyên x5 x6 x7 x8 x9 x10 x11 x12 x13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -3 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 -9 0 0 0 -50 0 0 0 0 http://www.lrc-tnu.edu.vn x2 x1 x3 x4 x7 x8 x9 x10 x11 x12 x13 Bước x2 x1 x3 x4 x5 x8 x9 x10 x11 x12 x13 Bước x2 x1 x3 x4 x5 x8 x9 x10 x11 x12 x6 Bước -30 -20 0 0 0 0 -30 -20 0 0 0 0 -30 -20 0 0 0 0 6 12 17 10/3 10 6 13 3 10 15 4/3 16/3 22/3 53/3 14/3 5/3 22/3 35/3 2/3 2/3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -3 -1 [1] 1 1 20 0 0 0 0 0 0 0 0 0 0 -4 -2 -1 -3 -13 -70 -2 -7 -3 -4 [3] 10 0 0 0 0 0 0 0 0 0 0 0 1 -1 -1 -1 -1 -1 -4 -20 4/3 -5/3 19/3 -3 -13/3 5/3 13/3 17/3 1/3 -4/3 -20/3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Sau bước đơn hình ta nhận lời giải tốn trung gian là: xopt =(22/3, 16/3, 53/3, 5, 14/3, 2/3, 0, 5/3, 4, 22/3, 35/3, 2/3, 0) Vậy ta suy lời giải toán tái tối ưu hoá ban đầu xopt =(22/3, 16/3) Bây ta giải lại ví dụ thuật tốn nón xoay TT, đưa số liệu ban đầu vào bảng nón xoay thu gọn tính tốn ta được: theo thuật tốn, nón – ban đầu tốn có tập số sở {7, 12}, có bảng nón xoay lặp thu gọn sau với quy tắc chọn số đưa vào sở max: 57 62Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 0 0 0 0 0 0 0 0 0 0 -1/3 2/3 7/3 4/3 -2/3 -1 -4/3 -5/3 -1/3 1/3 -10/3 CS bj -20 -30 Ai (x0 ) Ai (x1 ) -1 -26/3 -22/3 0 -1 -14/3 -16/3 -1 -3 -67/3 -53/3 -3 -1 -7 -5 -8 -1 -22/3 -14/3 -6 -4/3 -2/3 -18 0 -9 -1/3 -5/3 -6 -1 -2 -4 10 -4 -2 -14/3 -22/3 11 -3 -3 -25/3 -35/3 12 -40/3 1 -2/3 13 -56 (2) -18 -1 -1 10 (12) -40/3 -2 [-3] (10/3) Bc x 26/3 14/3 -18 5/3 -4/3 13 -56 -2/3 1/3 Bc x1 22/3 16/3 Lời giải toán tái tối ưu hoá nhận sau bước lặp x =(22/3, 16/3).Vậy ta nhận phương án tối ưu toán tái tối ưu hoá sau bước lặp Rõ ràng lời giải tốn tái tối ưu hố tìm theo thuật tốn TT ngắn gọn phương pháp đơn hình, tốn giải phương pháp đơn hình số chiều tăng lên phải đưa tốn dạng tắc, khơng tận dụng thơng tin lời giải tốn cần tái tối ưu số bước lặp số phép tính toán bước lặp nhiều rõ rệt opt 58 63Số hóa Trung tâm Học liệu – Đại học Thái Ngun http://www.lrc-tnu.edu.vn 3.4 Thuật tốn nón xoay TT giải ví dụ KLEE – MINTY với n=3 Xét tốn quy hoạch tuyến tính dạng chuẩn Rn sau:  n  G(X) = 10n−j xj → max    j=1  xj ≥ 0, j = 1, 2, , n  i−1    10i−j xj + xi ≤ 100i−1 , i = 1, 2, , n 2 j=1 Chúng Ta đưa toán dạng tốn tìm sau:  n  F (X) = −G(X) = − 10n−j xj →    j=1  xj ≥ 0, j = 1, 2, , n  i−1    10i−j xj + xi ≤ 100i−1 , i = 1, 2, , n 2 j=1 Chúng ta biết ví dụ giải thuật tốn đơn hình cổ điển sau 2n − bước lặp đến nghiệm tối ưu toán Sau giải toán trường hợp cụ thể với n=3:  G(X) = 100.x1 + 10.x2 + x3 → max      xj ≥ 0, j = 1, 2, x1 ≤   20.x1 + x2 ≤ 100    200.x1 + 20.x2 + x3 ≤ 10000 Để giải toán thuật tốn đơn hình, đưa dạng tốn quy hoạch tuyến tính dạng tắc R6 sau:  F (X) = −G(X) = −100.x1 − 10.x2 − x3 →      x1 + x4 = 20.x1 + x2 + x5 = 100    200.x1 + 20.x2 + x3 + x6 = 10000   xj ≥ 0, j = 1, 2, , Ở phải thêm vào biến bù x4 , x5 , x6 dễ dàng thấy chúng biến sở ban đầu để tiến hành tính toán, kết cho bảng sau qua bước lặp: 59 64Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn cj Aj 0 Bc0 -100 0 Bc1 -100 -10 Bc2 -10 Bc3 -10 -1 Bc4 -100 -10 -1 Bc5 -100 -1 Bc6 0 -1 Bc7 A4 A5 A6 A1 A5 A6 A1 A2 A6 A4 A2 A6 A4 A2 A3 A1 A2 A3 A1 A5 A3 A4 A5 A3 P/án -100 A1 [1] 100 20 10000 200 100 1 80 9800 0 1 80 8200 0 1 100 20 8000 -200 -100 [1] 100 20 8000 -200 100 1 80 8200 0 1 80 9800 0 1 100 20 10000 200 -200 -10 -1 0 A A A A A6 0 0 0 20 0 10 0 0 0 [1] -20 20 -200 10 -100 0 0 [1] 0 -20 0 200 -20 1 100 -10 0 0 0 0 [1] -20 1 -10 0 0 0 0 -20 0 10 -1 0 0 -20 [1] 0 200 -20 0 10 -1 0 0 -20 20 -200 -10 200 -1 0 0 0 20 0 -20 0 -1 Vậy sau bước lặp ta nhận nghiệm tối ưu là: xopt =(0, 0, 10 000, 1, 100, 0) Suy phương án tối ưu toán ban đầu xopt =(0, 0, 10 000) Bây ta giải toán theo thuật tốn nón xoay TT, trước hết 60 65Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn dễ thấy từ ràng buộc cuối tốn, ta có: x1 ≤ 1, x2 ≤ 100, x3 ≤ 1002 Vậy toán KLEE-MINTY với n=3 tương đương với tốn quy hoạch tuyến tính sau:   G(X) = −100.x1 − 10.x2 − x3 →     −xj ≤ 0, j = 1, 2,      x1 ≤ (G) 20.x1 + x2 ≤ 100   200.x1 + 20.x2 + x3 ≤ 1002      x2 ≤ 100    x ≤ 1002 Bài toán giải phương pháp tái tối ưu hoá sau: Dễ dàng thấy toán quy hoạch tuyến tính dạng chuẩn:  G(X) = −100.x1 − 10.x2 − x3 →      −xj ≤ 0, j = 1, 2, (T ) x1 ≤   x ≤ 100    x3 ≤ 1002 Có lời giải xopt =(1, 100, 1002 ) Lời giải chưa phải phương án toán (G) Vậy để giải toán (G) trước hết giải toán (G∗) sau thuật toán TT với ràng buộc bổ sung vào miền ràng buộc toán (T ) là: 200x1 + 20x2 + x3 ≤ 1002 Ta toán sau:  G(X) = −100.x1 − 10.x2 − x3 →     −xj ≤ 0, j = 1, 2,    x1 ≤ (G∗ ) x2 ≤ 100      x ≤ 1002   200x1 + 20x2 + x3 ≤ 1002 Dễ dàng thấy toán với nón – xuất phát ban đầu có tập số sở {4, 5, 6} xác định hệ bất phương trình tuyến tính:   x1 ≤ x2 ≤ 100  x3 ≤ 1002 61 66Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Đỉnh nón – x0 =( 1,100, 1002 ) có bảng lặp nón xoay thu gọn với quy tắc chọn số đưa vào sở số max sau: Chỉ số Cs (5) Bước (4) Bước Bước bj −102 -10 -1 Aj (x0 ) Aj (x1 ) Aj (x2 ) -1 0 -1 -1 0 -1 -100 (10) 2 0 -1 -100 -100 -1002 -1 0 0 -1 -100 0 -110 -100 -100 0 0 -100 200 20 (2200) 0 -1 -1 0 -200 1/2 -100 -1 [-20] (1/2) -100 0 -1 -1 x 100 100 -1 -1 10 [-10] (0) -100 -1/20 1/20 -100 1/20 -1 [-1/20] 10 x -10 100 -1/10 -100 -1/200 0 -1002 1/200 -1 x 0 1002 Ta có lời giải tốn (G∗ ) xopt =(0, 0, 10000) Và ta kiểm tra dễ dàng nhận thấy phương án tốn (G), lời giải toán (G) Vậy sau bước lặp nhận lời giải tối ưu tốn (G), cịn giải thuật tốn đơn hình phải sau bước lặp số phép tính tốn bước nhiều Qua nhiều ví dụ minh hoạ trên, thấy giải tốn quy hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hóa thuật tốn nón xoay TT số bước lặp đến lời giải tốn nói chung số bước lặp giải thuật tốn đơn hình đối ngẫu tương ứng Và rõ ràng bảng lặp rút gọn ma trận ràng buộc A véc tơ cột B cần khai báo lần sở liệu đầu vào bước lặp đầu tiên, bước lặp sau giữ nguyên giá trị Cịn giải tốn phương pháp đơn hình đối ngẫu tất phần tử ma trận ràng buộc A véc tơ cột B 62 67Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn phải tính lại sau bước lặp (vì cột véc tơ sở bị thay đổi vị trí bảng sau bước lặp biết) 63 68Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Kết luận Luận văn trình bày: Bài toán tối ưu tổng quát số mơ hình tốn thực tế 2.Xây dựng phương pháp nón xoay tuyến tính giải trực tiếp tốn quy hoạch tuyến tính dạng chuẩn biết nón-min hàm mục tiêu tốn Thuật tốn nón xoay TT giải tốn quy hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hoá ví dụ số minh hoạ cho thuật tốn 64 69Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Tài liệu tham khảo [1] Nguyễn Anh Tuấn- Nguyễn Văn Quý Quy hoạch tuyến tính với phương pháp nón xoay, NXB giáo dục Việt Nam Năm 2012,164 trang [2] Nguyễn Anh Tuấn Quy hoạch gần lồi-gần lõm ứng dụng vào quy hoạch tuyến tính, NXB Khoa học kỹ thuật Năm 2011, 128 trang [3] Nguyen Anh Tuan and Pham Canh Duong Minimization of An Almost-convex and Almost-concave Function Vietnam Journal of Mathematics, Volume 24, Number 1, 1996 (57-74) [4] Nguyen Anh Tuan, Tran Van Yen and Nguyen Van Tuan An Application of Mathematico-Economic Modeling to the Analysis of Air Transportation Planning of the Vietnam Airlines Corporation Vietnam Journal of Applied Mathematics, 2005, III(2): 55-66 [5] A.C Belenski Minimization monotone function in a polyhedron set, Automatic and Tele-Mechanics 9, 1982 (112-121) [6] Bùi Thế Tâm - Trần Vũ Thiệu Các phương pháp tối ưu hố, NXB Giao thơng vận tải, Năm 1998 408 trang [7] H Tuy Convex Analysis and Global Optimization, Kluwer 1998 [8] Hoàng Tuỵ Lý thuyết quy hoạch Tập NXB Khoa học kỹ thuật Năm 1967 108 trang [9] Nguyễn Đức Nghĩa Tối ưu hố (quy hoạch tuyến tính rời rạc) NXB Giáo dục Hà Nội 1997 192 trang [10] Bùi Minh Trí Bài tập Tối ưu hố Nhà xuất khoa học kỹ thuật Năm 2008.326 trang [11] Phan Quốc Khánh – Trần Huệ Nương Quy hoạch tuyến tính Nhà xuất Giáo dục Năm 2002 457 trang 65 70Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn [12] Phạm Đình Phùng - Nguyễn Văn Quý Toán Kinh tế NXB Thống kê Hà Nội Năm 1993 265 trang [13] Lê Thanh Huệ Một số kết toán quy hoạch tuyến tính Luận án Tiến sĩ Tốn học (Thư viện Viện Tốn học, Viện khoa học Cơng nghệ Việt Nam) 2009 76 trang [14] Lê Dũng Mưu Nhập môn phương pháp tối ưu NXB Khoa học kỹ thuật Năm 1998 [15] Trần Túc Bài tập Quy hoạch tuyến tính NXB Khoa học kỹ thuật Năm 2000 299 trang [16] Phí Mạnh Ban Bài tập quy hoạch tuyến tính NXB Đại học Sư phạm Năm 2011 379 trang [17] Nguyễn Văn Quý Bài tập toán Kinh tế NXB Tài Chính Năm 2010 168 trang 66 71Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ... lặp giải tốn qui hoạch tuyến tính thuật tốn nón xoay tuyến tính ví dụ minh hoạ Bài tốn quy hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hóa thuật tốn nón xoay TT 3.1 Bài tốn quy hoạch tuyến. .. nón xoay TT giải tốn quy hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hố ví dụ số minh hoạ cho thuật tốn Thuật tốn nón xoay TT giải tốn quy hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu. .. hoạch tuyến tính dạng chuẩn trường hợp tái tối ưu hoá gọi thuật tốn nón xoay TT Trong trường hợp giải tốn quy hoạch tuyến tính ngun phương pháp cắt-nhánh cận tái tối ưu hố việc áp dụng thuật tốn nón