ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HỒNG THỊ NINH THUẬT TỐN NĨN XOAY GIẢI BÀI TỐN QUY HOẠCH TUYẾN TÍNH DẠNG CHUẨN VỚI BIẾN BỊ CHẶN LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2013 Số 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 ii 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 lập kế hoạch sản xuất 1.2.2 Bài toán vận tải 1.2.3 Bài toán túi 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 tốn quy hoạch tuyến tính tổng qt 1.4.2 Dạng chuẩn dạng tắc 1.4.3 Đưa tố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] 11 1.5.3 Phương pháp KARMARKAR (điểm trong)[6] 12 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 2.4.2 Khái niệm cạnh nón đơn hình Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 15 17 19 19 19 20 i 2.5 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 với biến bị chặn thuật tốn nón xoay BBC 3.1 Thuật tốn nón xoay giải tốn quy hoạch tuyến tính dạng chuẩn với biến bị chặn 3.1.1 Xây dựng nón – ban đầu: 3.1.2 Thuật tốn nón xoay giải tốn qui hoạch tuyến tính với biến bị chặn: 3.1.3 Bảng nón xoay thu gọn giải tốn qui hoạch tuyến tính với biến bị chặn thuật tốn BBC ví dụ minh hoạ: 3.2 Thuật tốn nón xoay BBC giải ví dụ KLEE – MINTY với n=3 3.3 Vài nét độ phức tạp tính toán thuật toán BBC kết luận Tài liệu tham khảo Số hóa Trung tâm Học liệu – Đại học Thái Nguyên 24 27 31 31 34 41 41 42 43 44 51 56 58 http://www.lrc-tnu.edu.vn ii Mở đầu Quy hoạch tuyến tính phận quan trọng quy hoạch tốn học.Nhiều vấn đề thực tế mơ tả dạng tốn quy hoạch tuyến tính.Các toán quy hoạch phi tuyến thường giải hiệu cách xấp xỉ thơng qua tốn quy hoạch tuyến tính.Trong thập kỷ qua, với phát triển mạnh mẽ công nghệ thông tin, quy hoạch tốn học có bước tiến lớn phải nói đến phương pháp giải tốn quy hoạch tuyến tính gắn liền với tên tuổi nhà toán học L.V Kantorovich (1939),George Dantzig (1947),Lemke (1954),Leonid Khachian (1979),Karmarkar (1984) Bài toán quy hoạch tuyến tính có hai dạng dạng chuẩn dạng tắc,hai dạng có quan hệ mật thiết với nhau.Bài tốn quy hoạch tuyến tính dạng chuẩn tốn có miền ràng buộc hệ bất phương trình tuyến tính,cịn tốn quy hoạch tuyến tính dạng tắc tốn quy hoạch có miền ràng buộc hệ phương trình tuyến tính với biến có dấu khơng âm.Chúng ta biết,qua phép biến đổi dễ dàng đưa tốn từ dạng chuẩn dạng tắc,khi làm cho số chiều toán tăng lên đáng kể số ràng buộc bất phương trình tuyến tính tốn dạng chuẩn lớn,vì phải thêm vào nhiều biến bù (để đưa ràng buộc bất phương trình phương trình) Thuật tốn đơn hình cổ điển đơn hình đối ngẫu George Dantzig Lemke đề xuất vào năm 1947 1954 giải tốn quy hoạch tuyến tính dạng tắc.Chúng coi thuật toán sử dụng giải toán thực tế viện nghiên cứu ứng dụng giảng dạy trường Đại học,Cao đẳng nước Thế giới Để giải tốn qui hoạch tuyến tính thuật tốn đơn hình hay đơn hình đối ngẫu cần biết trước sở đơn vị xuất phát ban đầu,đôi để có sở lại phải giải toán quy hoạch tuyến tính khác giải tốn tương đương nhiều chiều với sở “chấp nhận được” gọi giả phương án ta phải trải qua nhiều bước lặp (không cần thiết) vượt khỏi giả phương án để đến lời giải toán ban đầu Sự thật tốn quy hoạch tuyến tính xây dựng từ thực tế thông thường dạng chuẩn chưa biết điểm chấp nhận miền ràng buộc.Như để giải tốn quy hoạch tuyến tính phương pháp đơn hình đơn hình đối ngẫu,địi hỏi phải thực hành qua nhiều bước trung gian nhận lời giải Số hóa Trung tâm Học liệu – Đại học Thái Ngun http://www.lrc-tnu.edu.vn iii tốn gốc Chính lý nên 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 lớp tốn quy hoạch tuyến tính dạng chuẩn với biến bị chặn gọi thuật tốn nón xoay BBC,với sở xuất phát ban đầu nhận biết dễ dàng trường hợp tổng quát xuất phát từ gốc toạ độ đỉnh nón Ortang n dương R+ hay từ véc tơ đơn vị gần đơn vị.Hơn nữa,dù miền ràng buộc tốn bị thối hố khơng ảnh hưởng đến tính hữu hạn bước lặp phương pháp nón xoay.Các thuật tốn nón xoay biến thể từ phương pháp nón-min giải tốn quy hoạch gần lồi-gần lõm đề xuất sách “Quy hoạch gần lồi-gần lõm ứng dụng vào quy hoạch tuyến tính”([2]) Trong trường hợp giải tố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 quả.Một số ví dụ số minh hoạ cho thuật tốn nón xoay giải chúng luận văn lấy từ sách,giáo trình nhiều tài liệu,cơng trình nghiên cứu nước nước tác giả khác nhau.Kết tính tốn đến lời giải tốn thuật tốn nón xoay cho thấy hầu hết số bước lặp số phép toán bước lặp rõ rệt so với việc giải chúng thuật tốn đơn hình hay đơn hình đối ngẫu Luận văn gồm chương: Chương 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 hoạch tuyến tính quen thuộc thơng dụng Chương 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 toán Chương (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 BBC giải tốn quy hoạch tuyến tính dạng chuẩn với biến bị chặn ví dụ số minh hoạ cho thuật tốn giải Thuật tốn nón xoay BBC giải tốn quy hoạch tuyến tính dạng chuẩn với bíến bị chặn đề nghị luận văn xây dựng chi tiết, bước thuật toán trình bày cho dễ dàng lập trình chuyển sang chương trình máy tính Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv ngôn ngữ Pascal,C,Java Luận văn hoàn thành dựa sách “Quy hoạch gần lồi - gần lõm ứng dụng vào quy hoạch tuyến tính” ([2]) “Quy hoạch tuyến tính với phương pháp nón xoay” [1] sách, tài liệu có phần tài liệu tham khảo Thái Nguyên, tháng năm 2013 Tác giả Hoàng Thị Ninh Số 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 toá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ển 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,các hàm gi (x), i = 1, , m gọi hàm ràng buộc,mỗi đẳ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) toán (1.1) (1.3) Số 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 tn 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 3.Ở 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 ngun nhân 1.2 1.2.1 Một số mơ hình thực tế Bài tốn lập kế hoạch sản xuất Bài toán lập kế hoạch sản xuất tối ưu phát biểu sau:Giả sử xí nghiệp sản xuất n loại sản phẩm sử dụng m loại nguyên liệu khác nhau.Ta đưa vào kí hiệu sau,xj lượng sản phẩm loại j(j = 1, , n) mà xí nghiệp sản xuất,cj tiền lãi (hay giá bán) đơn vị sản phẩm j(j = 1, , n), aij suất chi phí tài nguyên loại i để sản xuất đơn vị sản phẩm loại j, bi lượng dự trữ tài nguyên loại i(i = 1, , n).Trong điều kiện cho,hãy xác định giá trị xj , j = 1, , n cho tổng tiền lãi (hay tổng giá trị sản lượng hàng hóa) lớn với số tài ngun có Mơ hình tốn học có dạng tốn quy hoạch tuyến tính sau: n cj xj → max, j=1 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Với điều kiện n aij xj ≤ bi , i = 1, , m, j=1 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 bất kỳ.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ỏ nhất.Ký hiệu xij 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 Bài toán túi Một người du lịch muốn đem theo túi nặng khơng q b kilogam.Có n loại đồ vật mà dự định đem theo.Mỗi đồ vật loại j có khối lượng aj kilogam giá trị cj Người du lịch muốn chất vào Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn túi đồ vật cho tổng giá trị đồ vật đem theo lớn Ký hiệu xj số đồ vật loại j chất vào túi.Ta có toán sau: n cj xj → max, j=1 n aj xj ≤ b, j=1 xj ≥ 0, j = 1, , n, xj nguyên, j = 1, , n Đây toán quy hoạch nguyên 1.3 1.3.1 Tập lồi đa diện Một số khái niệm Đường thẳng,đoạn thẳng,siêu phẳng Cho hai điểm a, b ∈ Rn Ta gọi đường thẳng qua a, b tập hợp điểm có dạng: x ∈ Rn : x = λa + (1 − λ)b, ∀λ ∈ R1 Nếu ≤ λ ≤ ta có đoạn thẳng [a, b] Trong khơng gian hai chiều,phương trình bậc ax + by = c xác định đường thẳng,một bất phương trình ax + by ≤ c xác định nửa mặt phẳng.Trong khơng gian ba chiều,một phương trình bậc ax + by + cz = d xác định mặt phẳng,một bất phương trình ax + by + cz ≤ d xác định nửa không gian Ta suy rộng kết cho khơng gian n chiều.Tập hợp tất điểm không gian n chiều thỏa mãn phương trình a1 x1 + a2 x2 + + an xn = α gọi siêu phẳng Một bất phương trình a1 x1 + a2 x2 + + an xn ≤ α xác định nửa khơng gian Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 45 giải phương pháp thuật toán khác chẳng hạn phương pháp xử lý biến bị chặn trình bày [6] Ví dụ 3.1(xem)[6]: Giải tốn quy hoạch tuyến tính dạng chuẩn sau:   f = −2x1 − 3x2 + 2x3 − 5x4 →     2x1 + 2x2 + x3 + 2x4 ≤      x1 + 2x2 − 3x3 4x4 ≤ ≤ x1 ≤   ≤ x2 ≤      ≤ x3 ≤    ≤ x ≤ Giải phương pháp đơn hình ta phải thêm vào nhiều biến bù,sau giải ví dụ thuật tốn nón xoay BBC đề nghị Bài toán thuộc dạng toán quy hoạch tuyến tính với biến bị chặn (N )ta đưa dạng toán (N+ ):  f = −2x1 − 3x2 + 2x3 − 5x4 →      −x1 ≤     −x2 ≤     −x3 ≤      −x4 ≤ x1 − ≤   x2 − ≤      x3 − ≤     x4 − ≤     2x1 + 2x2 + x3 + 2x4 − ≤    x + 2x − 3x + 4x − ≤ Theo phương pháp xác định nón-min ban đầu tốn quy hoạch tuyến tính (N ) trình bày có tập số sở ban đầu : I0 = IH0 := Ic+ ∪ {i : i = + j, ∀j ∈ Ic− }, với Ic− = {1, 2, 4} ; Ic+ = {3} với I0 = {3, 5, 6, 8} nón-min ban đầu tốn nón đơn hình:H0 := x ∈ R3 : −x3 ≤ 0; x1 − ≤ 0; x2 − ≤ 0; x4 − ≤ Đỉnh x0 = (1, 1, 0, 1) Đưa số liệu vào bảng nón xoay lặp thu gọn tương ứng tiến hành tính toán với quy tắc chọn số đưa vào sở max kết sau: Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 46 CS (1) 10