Luận văn Thạc sĩ Toán học: Vấn đề ngược của vấn đề tối thiểu hóa thời gian trễ tối đa trên mô hình máy đơn

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:54

Thêm vào BST

Báo xấu

15
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn này trình bày về bài toán ngược của bài toán tối thiểu hóa thời gian trễ tối đa của các công việc với thời gian đến như nhau trên mô hình máy đơn. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Vấn đề ngược của vấn đề tối thiểu hóa thời gian trễ tối đa trên mô hình máy đơn

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– BẾ NHẬT VINH VẤN ĐỀ NGƯỢC CỦA VẤN ĐỀ TỐI THIỂU HÓA THỜI GIAN TRỄ TỐI ĐA TRÊN MÔ HÌNH MÁY ĐƠN THÁI NGUYÊN, THÁNG 5/2018
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– BẾ NHẬT VINH VẤN ĐỀ NGƯỢC CỦA VẤN ĐỀ TỐI THIỂU HÓA THỜI GIAN TRỄ TỐI ĐA TRÊN MÔ HÌNH MÁY ĐƠN Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC GIÁO VIÊN HƯỚNG DẪN TS. PHẠM HỒNG TRƯỜNG THÁI NGUYÊN, THÁNG 5/2018
1 Mục lục Danh mục các ký hiệu 3 Lời nói đầu 4 1 Kiến thức chuẩn bị 6 1.1. Vận trù học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2. Vấn đề tối ưu hóa tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3. Lời giải của vấn đề gia công trên mô hình máy đơn . . . . . . . . . . 10 1.3.1. Trình tự khả thi và trình tự tối ưu . . . . . . . . . . . . . . . 10 1.3.2. Trình tự gia công không trì hoãn và trình tự gia công trì hoãn được . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4. Vấn đề tối thiểu hóa thời gian trễ tối đa của các công việc với thời gian đến như nhau trên mô hình máy đơn 1kLmax . . . . . . . . . . . 12 1.5. Vấn đề sắp xếp ngược . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6. Vấn đề quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . 17 1.7. Định nghĩa ba loại chuẩn l1 , l2 , l∞ . . . . . . . . . . . . . . . . . . . . 18 2 Vấn đề ngược của vấn đề tối thiểu hóa thời gian trễ tối đa của các công việc với thời gian đến như nhau trên mô hình máy đơn 20 2.1. Sơ lược về vấn đề sắp xếp ngược . . . . . . . . . . . . . . . . . . . . . 21
2 2.2. Điều kiện cần và đủ của vấn đề tối thiểu hóa thời gian trễ tối đa . . . 24 2.2.1. Điều kiện đủ của vấn đề 1kLmax là tối ưu . . . . . . . . . . . . 24 2.2.2. Điều kiện cần và đủ của vấn đề 1kLmax . . . . . . . . . . . . . 26 2.3. Điều chỉnh kỳ hạn (Adjustable Due Dates) . . . . . . . . . . . . . . . 28 2.3.1. Bài toán ngược 1 |adjustable dj , π| Lmax . . . . . . . . . . . . . 28 2.3.2. Bài toán ngược 1 |adjustable dj , L∗ | Lmax . . . . . . . . . . . . 37 2.4. Điều chỉnh thời gian gia công (Adjustable Processing Times) . . . . . 40 2.4.1. Bài toán ngược 1 |adjustable pj , π| Lmax . . . . . . . . . . . . . 41 2.4.2. Bài toán ngược 1 |adjustable pj , L∗ | Lmax . . . . . . . . . . . . 47 Kết luận 49 Tài liệu tham khảo 51
3 Danh mục các ký hiệu Tj Công việc thứ j của một dãy công việc được đưa ra. pj Thời gian gia công của công việc Tj . dj Kỳ hạn của công việc Tj . Cj Thời gian hoàn thành của công việc Tj . P Cj Tổng thời gian hoàn thành các công việc có trọng số như nhau. P w j Cj Tổng thời gian hoàn thành các công việc có trọng số khác nhau. Lmax Thời gian trễ tối đa EDD Quy tắc ưu tiên sắp xếp kỳ hạn sớm nhất. 1kLmax Vấn đề tối thiểu hóa thời gian trễ tối đa của của các công việc trên mô hình máy đơn. 1|adjustable dj , π|Lmax Bài toán điều chỉnh kỳ hạn dj để dãy công việc π là tối ưu. 1|adjustable dj , L∗ |Lmax Bài toán điều chỉnh kỳ hạn dj để trễ tối đa Lmax ≤ L∗ . 1|adjustable pj , π|Lmax Bài toán điều chỉnh thời gian gia công pj để dãy công việc π là tối ưu. 1|adjustable pj , L∗ |Lmax Bài toán điều chỉnh thời gian gia công pj để trễ tối đa Lmax ≤ L∗ .
4 Lời nói đầu Từ thế kỷ XX tối ưu hóa đã có ứng dụng nhiều và hiệu quả trong các lĩnh vực như quản trị kinh doanh, chế tạo sản xuất, quy hoạch tài nguyên, công nghệ thông tin, hỗ trợ cho vấn đề ra quyết định quản lý, mục tiêu của nghiên cứu tối ưu hóa tìm ra giải pháp tốt nhất từ một số lượng lớn các giải pháp khả thi. Trong mô hình tối ưu hóa truyền thống thì tất cả các thông số được đưa ra và mục tiêu là tìm giải pháp tối ưu đáp ứng các ràng buộc cụ thể, đối với tối ưu hóa ngược thì đã xác định trước một giải pháp cùng với các giá trị của một số thông số không được cho chính xác và mục tiêu là tìm các giá trị chính xác của các thông số để giải pháp được đưa ra ban đầu là tối ưu, như vậy tối ưu hóa ngược có thể giúp cải thiện hệ thống đã có sẵn. Trong những năm gần đây, vấn đề tối ưu hóa ngược đã trở thành một chủ đề được nghiên cứu nhiều hơn, tầm quan trọng và ứng dụng của tối ưu hóa ngược ngày càng được gia tăng. Luận văn này trình bày về bài toán ngược của bài toán tối thiểu hóa thời gian trễ tối đa của các công việc với thời gian đến như nhau trên mô hình máy đơn. Vấn đề trình tự gia công các công việc là một vấn đề của bài toán tối ưu hóa tổ hợp. Với vấn đề tối ưu hóa của trình tự gia công thuận thì dãy các công việc được đưa ra cùng với các thông số cho trước (ví dụ như thời gian gia công hay kỳ hạn của từng công việc) ta cần sắp xếp lại trình tự các công việc để sao cho độ trễ tối đa là nhỏ nhất. Tuy nhiên khi trình tự các công việc này được ấn định thì mục
5 tiêu của tối ưu hóa ngược là ta cần điều chỉnh các thông số cho trước để sao cho trình tự đã cho là tối ưu hoặc để đạt được độ trễ tối đa thỏa mãn một thời hạn cho trước. Chính vì vậy việc nghiên cứu bài toán ngược của bài toán tối thiểu hóa thời gian trễ tối đa của các công việc với thời gian đến như nhau trên mô hình máy đơn là cần thiết. Giải quyết bài toán này nhằm để đáp ứng được kỳ hạn giao hàng cho khách hàng, hoặc khi khách hàng có một dãy các công việc được ấn định trước sao cho độ trễ tối đa trong sản xuất là nhỏ nhất. Luận văn này được hoàn thành tại Trường Đại học Khoa học - Đại học Thái Nguyên dưới sự hướng dẫn của TS. Phạm Hồng Trường. Tôi xin tỏ lòng kính trọng và biết ơn sâu sắc đối với thầy, người đã trực tiếp hướng dẫn tôi rất tận tình trong việc học tập, nghiên cứu để hoàn thành bản luận văn này. Xin chân thành cảm ơn Lãnh đạo Trường Đại học Khoa học - Đại học Thái Nguyên, Ban chủ nhiệm khoa Toán - Tin cùng toàn thể các thầy cô trong và ngoài trường đã giảng dạy giúp tôi trau dồi thêm rất nhiều kiến thức phục vụ cho việc học tập và nghiên cứu của bản thân. Cuối cùng tôi xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi trong quá trình học tập, nghiên cứu và hoàn thành luận văn này. Xin chân thành cảm ơn! Thái Nguyên, ngày 10 tháng 5 năm 2018 Tác giả luận văn Bế Nhật Vinh
6 Chương 1 Kiến thức chuẩn bị 1.1. Vận trù học Vận trù học (Operations Research-OR) được hình thành từ việc lập kế hoạch của các nhà quân sự trong chiến tranh thế giới thứ II. Mục tiêu của Vận trù học lúc đó là sử dụng sao cho hiệu quả nhất các nguồn lực quân sự bằng cách sử dụng các kỹ thuật định lượng. Kết quả ứng dụng đầu tiên được thực hiện bởi Patrick Blackett. Trong thế chiến thứ nhất, ông đã thành lập một nhóm được gọi là Circus giúp giảm số lượng pháo phòng không với tầm xa cần thiết để bắn hạ một chiếc máy bay của đối phương từ mức trung bình hơn 20000 đầu đạn ở trận đầu của cuộc chiến xuống chỉ còn 4000 đầu đạn vào năm 1941. Trong những thập kỷ sau chiến tranh, các kỹ thuật này bắt đầu được áp dụng rộng rãi hơn cho các vấn đề trong kinh doanh, công nghiệp và xã hội. Từ đó Vận trù học đã mở rộng và được sử dụng rộng rãi trong các ngành công nghiệp từ hóa dầu đến các hãng hàng không, hậu cần và chính phủ, tập trung vào việc phát triển các mô hình toán học có thể được sử dụng để phân tích và tối ưu hóa các hệ thống phức tạp và trở thành một lĩnh vực được học tập và nghiên cứu. Vận trù học với mục đích nghiên cứu phân bổ nguồn lực tối ưu, vận trù học cung cấp cơ sở hợp lý cho việc ra quyết định bằng cách tìm hiểu và cấu trúc các
7 tình huống phức tạp, dự đoán hành vi của hệ thống và cải thiện hiệu suất của hệ thống. Phần lớn công việc thực tế được thực hiện bằng cách sử dụng các kỹ thuật phân tích và số để phát triển và vận dụng các mô hình toán học của các hệ thống tổ chức bao gồm người, máy móc và các hoạt động trong đó. Vai trò của vận trù học trong cả hai lĩnh vực công và lĩnh vực tư nhân đang gia tăng nhanh chóng. Vận trù học giải quyết nhiều vấn đề khác nhau trong giao thông vận tải, lập kế hoạch kiểm kê, kế hoạch sản xuất, hoạt động truyền thông, hoạt động máy tính, quản lý tài sản, quản lý rủi ro, quản lý doanh thu và nhiều lĩnh vực khác. Trong lĩnh vực công, các nghiên cứu của vận trù học có thể tập trung vào chính sách năng lượng, quốc phòng, chăm sóc sức khoẻ, quy hoạch tài nguyên nước, thiết kế và vận hành các hệ thống khẩn cấp đô thị hoặc thực thi pháp luật. Nghiên cứu trong vận trù học, khoa học quản lý có thể phân loại thành ba lĩnh vực chính sau: Một là nghiên cứu cơ sở hoặc nền tảng trong ba lĩnh vực của toán học (Xác suất, tối ưu hóa, và lý thuyết hệ động lực). Hai là nghiên cứu mô hình trong việc thiết lập mô hình, phân tích chúng về mặt toán học, mã hóa chúng lên máy tính, giải chúng bằng các công cụ phần mềm, đánh giá hiệu quả thu được từ dữ liệu máy tính. Mức này chủ yếu nhờ máy tính và được định hướng chính bởi xác suất và kinh tế lượng và thứ ba là nghiên cứu ứng dụng trong vận trù học, giống như trong các ngành kĩ thuật và kinh tế, sử dụng các mô hình thu được để áp dụng cho các vấn đề thực tế. Trong vận trù học, các nhà nghiên cứu được yêu cầu phải mô hình hóa các vấn đề thực tế bằng cách áp dụng các kỹ thuật toán học, thống kê, ứng dụng máy tính và sau đó tìm các giải pháp tối ưu cho các mô hình bị hạn chế về thời gian, nguồn lực lao động, nguồn lực vật liệu và các quy tắc kinh doanh với các mục tiêu cụ thể. Các lý thuyết mới, các mô hình toán học đã được phát minh ra trong vận trù học để mô tả và phân tích các hành vi, đặc điểm, sự thay đổi của các vấn đề thực tế, để
8 giúp mọi người ra quyết định tốt hơn để phát triển và quản lý quy trình và doanh nghiệp của mình với lợi nhuận tối đa. Mô hình tối ưu có thể được mô tả như sau max ( min) f (x) s.t. Điều kiện ràng buộc. Các giải pháp đáp ứng các yêu cầu nêu trên thường được gọi là các giải pháp khả thi. Tối ưu hóa là tìm ra các giải pháp tối ưu trong số các giải pháp khả thi. 1.2. Vấn đề tối ưu hóa tổ hợp Tối ưu hoá tổ hợp là một nhánh con của tối ưu hóa toán học và xuất hiện trong toán học rời rạc, vận trù học, lý thuyết thuật toán và lý thuyết tính toán phức tạp. Mục tiêu của nghiên cứu tối ưu hóa tổ hợp là tìm ra giải pháp tốt nhất từ một số lượng lớn các giải pháp khả thi. Trong nhiều vấn đề, chẳng hạn như phân công tối ưu, cây khung ngắn nhất, vận chuyển và bài toán người giao hàng, các giải pháp là rời rạc và việc tìm kiếm toàn diện là không khả thi. So với các ngành toán học ứng dụng khác, tối ưu hóa tổ hợp là tương đối trẻ. Xem xét lịch sử của một loạt các nghiên cứu độc lập đã diễn ra riêng biệt. Chỉ trong những năm 1950, khi công cụ đại số tuyến tính và số nguyên trở nên thống nhất và có sẵn thì lĩnh vực tối ưu tổ hợp bắt đầu thu hút sự chú ý và các mối quan hệ giữa chúng đã được đặt ra. Thật vậy, tối ưu hóa tuyến tính tạo thành bản lề trong lịch sử tối ưu hóa tổ hợp. Quan niệm ban đầu của Kantorovich và Koopmans được thúc đẩy bởi các ứng dụng tổ hợp, đặc biệt là trong vận chuyển và chuyển tải. Sau khi xây dựng quy hoạch tuyến tính như là một bài toán tổng quát, và phát triển vào năm 1947 bởi Dantzig về phương pháp đơn hình như một công cụ, Dantzig đã cố gắng giải quyết tất cả các bài toán tối ưu hóa tổ hợp với các phương pháp quy hoạch tuyến tính và thường là rất thành công. Tối ưu hóa tổ hợp liên quan đến các mô hình và phương pháp để tối ưu hóa các
9 lựa chọn rời rạc. Nó bắt nguồn từ lý thuyết quy hoạch tuyến tính, và có liên kết chặt chẽ với toán học rời rạc, lý thuyết xác suất, lý thuyết khoa học máy tính, và lý thuyết tính độ phức tạp tính toán. Một số vấn đề trong lĩnh vực được nghiên cứu tương đối tốt và chấp nhận giải pháp để tối ưu hóa trong thời gian đa thức. Nhiều bài toán khác là NP–hard. Có ba cách để giải quyết tốt nhất các bài toán tối ưu hóa tổ hợp. Cách thứ nhất là sử dụng một phương pháp liệt kê được đảm bảo để tạo ra một giải pháp tối ưu. Cách thứ hai là áp dụng một thuật toán xấp xỉ chạy trong thời gian đa thức. Cách thứ ba là sử dụng một số kỹ thuật tìm kiếm kinh nghiệm, mà không có sự đảm bảo trước về chất lượng giải pháp hoặc thời gian chạy. Nhiều vấn đề về quyết định trong cuộc sống thực tế có thể được xây dựng như các vấn đề tối ưu hoá tổ hợp và do đó có sự quan tâm lớn và ngày càng tăng về cả lý thuyết và thực tiễn. Một số vấn đề về bài toán người giao hàng, việc lên kế hoạch mua sắm, tham quan, vấn đề của bác sĩ hoặc người đưa thư. Tương tự như vậy, phân công công việc, vận tải, kết nối hình thành các vấn đề cơ bản đã được rất nhiều nhà toán học xem xét. Nói chung, các bài toán tối ưu tổ hợp thường có quy mô lớn và khó giải quyết. Do đó, nghiên cứu sự phức tạp về mặt tính toán và thiết kế thuật toán để phát triển các thủ tục giải quyết hiệu quả là trọng tâm của các nhà nghiên cứu trong việc tối ưu hóa tổ hợp. Một vấn đề tối ưu tổ hợp P = (S, f ) có thể được chỉ ra như sau • Các miền biến D1 , D2 , ..., Dn , • Các ràng buộc giữa các biến, • Một hàm mục tiêu f tối thiểu hóa (hoặc tối đa hóa), trong đó f : D1 × D2 × ... × Dn −→ R+ .
10 Tập hợp tất cả các giải pháp khả thi S = {s ∈ D1 × D2 × ... × Dn | s thỏa mãn các ràng buộc}. S thường được gọi là không gian tìm kiếm (hoặc tập hợp các giải pháp), vì mỗi phần tử của S có thể được xem như một giải pháp khả thi. Để giải quyết Bài toán tối ưu tổ hợp có nghĩa là tìm một giải pháp s∗ ∈ S với giá trị hàm tối thiểu hóa (hoặc tối đa hóa); nghĩa là, f (s∗ ) ≤ f (s), ∀ s∗ ∈ S (hoặc f (s∗ ) ≥ f (s), ∀ s∗ ∈ S, s∗ được gọi là Giải pháp tối ưu của (S, f ) và để sao cho tập S ∗ ⊆ S là tập hợp các giải pháp tối ưu. 1.3. Lời giải của vấn đề gia công trên mô hình máy đơn (Xem [1]) 1.3.1. Trình tự khả thi và trình tự tối ưu Vấn đề trình tự gia công là một bài toán tối ưu hóa tổ hợp. Các nhiệm vụ, số lượng các máy cần xử lý trong vấn đề trình tự gia công đều là hữu hạn do đó lời giải tối ưu của đại bộ phận vấn đề trình tự đều được tìm ra từ hữu hạn các giải pháp khả thi của vấn đề trình tự ban đầu, làm cho hàm mục tiêu đạt giá trị tối ưu. Trong vấn đề trình tự gia công, ta gọi giải pháp khả thi là trình tự khả thi, giải pháp tốt ưu được gọi là trình tự tối ưu. Trong vấn đề trình tự gia công, một trình tự khả thi là một dãy thứ tự mà dựa vào đó có thể sắp xếp tất cả các nhiệm vụ gia công trên máy xử lý. P Ví dụ 1.1. Cho vấn đề trình tự gia công 1k wj Cj trong đó, n = 6, p = (12, 4, 7, 11, 6, 5), ω = (4, 2, 5, 5, 6, 3). Một trình tự gia công bất kì của tập các công việc đều là trình tự khả thi, trong đó [T5 , T3 , T6 , T2 , T4 , T1 ] là tối ưu. Ví dụ 1.2. Cho vấn đề trình tự gia công F2 ||Cmax trong đó n = 5.
11 Hình 1.1: Trình tự tối ưu của ví dụ 1.2.   4 4 10 6 2 P = . 5 1 4 10 3 Một trình tự gia công bất kỳ của tập các công việc đều là trình tự khả thi, trong đó [J5 , J1 , J4 , J3 , J2 ] là trình tự tối ưu. Hình 1.2: Sơ đồ Grant Charts. 1.3.2. Trình tự gia công không trì hoãn và trình tự gia công trì hoãn được Trong quá trình giải quyết các vấn đề trình tự gia công, có một loại trình tự khả thi rất quan trọng được định nghĩa. Định nghĩa 1.1. Đối với một trình tự khả thi, nếu có các công việc đều được chuẩn bị trước, máy xử lý không có thời gian nghỉ trong cả quá trình gia công, loại trình tự gia công này được gọi là trình tự gia công không trì hoãn. Nếu ngược lại, sẽ được gọi là trình tự gia công trì hoãn được. Trình tự gia công không trì hoãn tương đương với việc không được để máy xử lý có thời gian nghỉ trong quá trình gia công. Đối với đa số các vấn đề về trình tự gia
12 công, bao gồm tất cả các trình tự gia công có thể trì hoãn, trình tự tối ưu là trình tự không trì hoãn, tuy nhiên cũng có một vài vấn đề thì trình tự gia công có thể trì hoãn mà trình tự tối ưu của nó là trình tự trì hoãn được. P Ví dụ 1.3. Trình tự gia công 1|rj | wj Cj , n = 2, p = (10, 5), r = (0, 1), w = (1, 5). Vấn đề này có hai trình tự khả thi đó là: Hình 1.3: Trình tự khả thi của ví dụ 1.3 1.4. Vấn đề tối thiểu hóa thời gian trễ tối đa của các công việc với thời gian đến như nhau trên mô hình máy đơn 1kLmax Một số ký hiệu trong bài toán 1kLmax : Tj là công việc thứ j trong một dãy công việc đưa ra, pj là thời gian gia công của công việc Tj , dj là thời gian hoàn thành hạn định đối với công việc Tj , j P Cj = ps là thời gian hoàn thành thành công công việc Tj , s=1 Thời gian trễ tối đa (maximum latenes) Lmax = max{Lj }
13 trong đó, Lj = Cj − dj là thời gian trễ của công việc Tj . Bài toán 1.1. Tìm thời gian trễ tối đa của các công việc được sắp thứ tự lần lượt từ công việc T1 −→ T2 −→ T3 −→ T4 −→ T5 −→ T6 với các dữ kiện được cho theo bảng 1.1. Công việc Tj T1 T2 T3 T4 T5 T6 Thời gian gia công tương ứng (pj ) 3 1 4 1 3 2 Kỳ hạn hoàn thành tương ứng (dj ) 2 10 6 4 11 12 Bảng 1.1 Hình 1.4: Trình tự thực hiện các công việc của bài toán 1.1 Ta được: C1 = 3; C2 = 4; C3 = 8; C4 = 8; C5 = 12; C6 = 14. Khi đó thời gian trễ của các công việc Tj là: L1 = 1; L2 = −6; L3 = 2; L4 = 5; L5 = 1; L6 = 2. Vậy trễ tối đa Lmax = 5. Mặt khác, nếu thay đổi thứ tự các công việc hoàn thành T1 −→ T3 −→ T4 −→ T2 −→ T5 −→ T6 . Ta được:
14 Hình 1.5: Trình tự thực hiện các công việc của bài toán 1.1 theo thứ tự mới. Khi đó, thời gian trễ của các công việc Tj là L1 = 1; L3 = 1; L4 = 4; L2 = −1; L5 = 1; L6 = 2. Vậy trễ tối đa Lmax = 4. Như vậy có thể thấy rằng, khi thay đổi thứ tự thực hiện các công việc, thì thời gian trễ tối đa (có thể) khác nhau. Vậy vấn đề đặt ra là, khi thực hiện gia công một tập hợp các công việc với thời gian hoàn thành hạn định đối với các công việc đã được định sẵn, thì thứ tự thực hiện của các công việc đó nên sắp xếp thế nào để thời gian trễ tối đa là nhỏ nhất. Bài toán 1kLmax là tương đối đơn giản, và nó được giải quyết bằng cách sắp xếp các nhiệm vụ theo quy tắc ưu tiên kỳ hạn sớm nhất (Earliest Due Date first viết tắt là EDD) ta sẽ thu được trình tự tối ưu. Theo quy tắc này, các công việc được sắp xếp theo trình tự không giảm của các dj . 1.5. Vấn đề sắp xếp ngược Lý thuyết vật lý cho phép chúng ta đưa ra dự đoán, đưa ra mô tả đầy đủ về một hệ thống vật lý hoặc dự đoán kết quả của một số phép đo. Khi đó việc dự đoán kết quả đo được gọi là mô hình hóa hoặc vấn đề thuận. Một vấn đề ngược lại là ta chuyển đổi các phép đo, các quan sát thành thông tin về một vật thể hoặc hệ thống vật lý mà chúng ta quan tâm. Trong khi vấn đề thuận có giải pháp duy nhất thì vấn đề ngược thì không. Ví dụ, xem xét các phép đo trọng lượng trên một hành tinh: cho phân bố khối lượng
15 bên trong hành tinh, chúng ta có thể xác định duy nhất các giá trị của lực hấp dẫn xung quanh hành tinh, nhưng trong các không gian tương đồng bên ngoài hành tinh có các phân bố khối lượng khác nhau trong cùng một môi trường trọng lực. Do đó, trong vấn đề ngược lại suy ra sự phân bố khối lượng từ quan sát các môi trường của trọng lực thì có nhiều giải pháp. Vì vậy trong vấn đề ngược ta cần phải xem xét, kiểm tra cẩn thận chính xác về các thông số của mô hình. Tối ưu hóa ngược liên quan đến việc xác định sự thay đổi tối thiểu đối với thông số của một vấn đề, để cho phép một giải pháp nhất định trở nên tối ưu. Khi giải quyết bài toán tối ưu, chúng ta thường giả sử rằng các thông số như chi phí, năng lực, vv ... đã biết và ta quan tâm đến một giải pháp tối ưu. Tuy nhiên, trong thực tế có thể xảy ra nhiều trường hợp mà chúng ta chỉ biết ước lượng cho các tham số. Ngoài ra, chúng ta có thể biết rằng các giải pháp nhất định là tối ưu từ quan sát hoặc từ thí nghiệm cụ thể. Ý tưởng tối ưu ngược là tìm ra các giá trị của các tham số làm cho các giải pháp đưa ra là tối ưu và lượng thay đổi của các tham số so với các ước lượng ban đầu càng ít càng tốt. Các vấn đề sắp xếp thuận đề cập đến cách sắp xếp một dãy các công việc với mục tiêu tối thiểu hóa một vài thông số của công việc (ví dụ như thời gian hoàn thành). Tuy nhiên, những vấn đề sắp xếp ngược lại giả định rằng một trình tự công việc đã được đưa ra trước và mục tiêu là xác định sự thay đổi tối thiểu đối với các thông số của công việc (ví dụ như thời gian xử lý) sao cho dãy trình tự đã đưa ra trở thành tối ưu đối với một hàm mục tiêu được chọn trước. Vấn đề sắp xếp thuận rất hữu ích cho việc thiết kế một hệ thống mới, trong khi vấn đề sắp xếp ngược lại có ý nghĩa quan trọng để cải thiện hiệu quả của một hệ thống đã tồn tại. Trong những năm gần đây, vấn đề tối ưu hóa ngược đã trở thành một chủ đề được nghiên cứu nhiều hơn. Các nghiên cứu về vấn đề này có thể được tìm thấy trong một số ví dụ sau: Các vấn đề lập trình tự ngược ứng dụng trong vận chuyển.
16 Các vấn đề ngược của một lập trình đơn máy để giảm thiểu tổng số thời gian hoàn thành công việc. Một số kết quả mới về các vấn đề phân loại ngược. Vào năm 2005 C. Koulamas đã nghiên cứu và đưa ra kết quả về việc lập trình tự ngược với các thông số công việc kiểm soát được. Ông đã nghiên cứu các vấn đề lập trình tự ngược của tổng số thời gian hoàn thành có trọng số trên máy đơn và các vấn đề lập trình tự ngược của tổng số thời gian hoàn thành vấn đề trên máy đơn. Tuy nhiên, trong nghiên cứu của mình ông đã không xem xét đến việc giá trị kết quả của tiêu chí lập trình tự có thể cao hơn giá trị của tiêu chí lập trình tự ban và nhưng điều này là không mong muốn. Chen đã chỉ ra và khắc phục được điểm yếu trong kết quả của Koulamas (2005), họ đã sử dụng công cụ lập trình toán học để nghiên cứu các vấn đề ngược của một lập trình máy đơn để giảm thiểu tổng trọng số. P Thời gian hoàn thành, 1k wj Cj và các giải pháp tối ưu tương ứng thu được theo các chuẩn l1 , l2 , l∞ . Hơn nữa, các vấn đề đảo của tổng thời gian hoàn thành P vấn đề trên máy đơn 1k Cj và các giải pháp tối ưu liên quan của nó cũng đã được nghiên cứu. Brucker và Shakhlevich [7] đã nghiên cứu lập kế hoạch ngược với vấn đề khách quan tối đa. Trong bài toán lập kế hoạch này, họ đã nghiên cứu các đối số ngược của bài toán lập trình trên mô hình máy đơn 1kLmax trong trường hợp có thể điều chỉnh ngày tháng hoặc thời gian xử lý dưới các loại của các tiêu chuẩn: l1 , l2 , l∞ . Hai vấn đề của họ dường như là NP-khó; cho các vấn đề, họ đã tạo ra công thức lập trình toán học của họ và phát triển các thuật toán giải pháp hiệu quả. Các kết quả được tóm tắt trong bảng 1.2.
17 Điều chỉnh kì Điều chỉnh thời gian Chuẩn Chuẩn hạn dj gia công pj Bài toán ngược với trình tự cho O(n log n) l1 , l2 O(n2 log n) l1 , l2 trước π 3 O(n log n) l∞ O(n ) l∞ ∗ 2 Bài toán ngược với giá trị L cho O(n ) l1 , l2 O(n log n) l1 , l2 trước 2 O(n ) l∞ O(n log n + cn) l∞ Bảng 1.2: Độ phức tạp của bài toán ngược của bài toán 1kLmax đối với các loại chuẩn l1 , l2 , l∞ . 1.6. Vấn đề quy hoạch tuyến tính Quy hoạch tuyến tính là một trường hợp đặc biệt của lý thuyết tối ưu hóa và nó giải quyết các bài toán tối ưu (như chi phí tối đa hoặc tối thiểu). Các vấn đề quy hoạch tuyến tính gồm một hàm mục tiêu tuyến tính (gồm một số lượng các biến nhất định) được tối thiểu hóa hoặc tối đa hóa theo một số ràng buộc tuyến tính nhất định. Các ràng buộc tuyến tính đều là hàm và các phương trình hoặc bất phương trình tuyến tính của các biến được sử dụng trong hàm mục tiêu. Quy hoạch tuyến tính liên quan chặt chẽ đến đại số tuyến tính; sự khác biệt đáng chú ý nhất là quy hoạch tuyến tính với các điều kiện ràng buộc thường là bất phương trình tuyến tính. Quy hoạch tuyến tính là một trong những phương pháp thành công nhất trong nghiên cứu về tối ưu tổ hợp. Trong thực tế, nhiều vấn đề thực tế có thể được mô tả như là các vấn đề quy hoạch tuyến tính. Quy hoạch tuyến tính đã được sử dụng rất nhiều trong kinh tế và quản lý công ty. Mặc dù các vấn đề quản lý hiện đại đang thay đổi, hầu hết các công ty muốn tối đa hóa lợi nhuận hoặc giảm thiểu chi phí với nguồn lực hạn chế. Vì vậy, nhiều vấn đề thực tế có thể được thể hiện như là các vấn đề quy hoạch tuyến tính để đạt được lợi nhuận tối đa như quy hoạch, sản xuất, vận chuyển, công nghệ,. . . Thật vậy, các ý tưởng từ quy hoạch tuyến tính đã đưa ra rất nhiều các khái
18 niệm trọng tâm của lý thuyết tối ưu hóa, như tính hai mặt, sự phân hoạch, và tầm quan trọng của tính lồi và các khái quát hóa của nó. Một số trường hợp đặc biệt của quy hoạch tuyến tính, chẳng hạn như các vấn đề về mạng lưới và các vấn đề đa giao thức được coi là quan trọng đủ để tạo ra nhiều nghiên cứu về thuật toán chuyên dụng cho giải pháp được ứng dụng trong thực tế. 1.7. Định nghĩa ba loại chuẩn l1 , l2 , l∞ Một hàm f : Rn −→ R với domf = Rn được gọi là một chuẩn nếu: • f là không âm: f (x) ≥ 0, ∀ x ∈ Rn , • f là đồng nhất: f (tx) = |t|f (x), ∀ x ∈ Rn , t ∈ R, • f thỏa mãn bất đẳng thức tham giác: f (x + y) ≤ f (x) + f (y), ∀ x, y ∈ Rn . Ta sử dụng ký hiệu f (x) = |x|, có nghĩa là để cho thấy rằng một chuẩn là một sự suy rộng của giá trị tuyệt đối trên R. Khi ta xác định một chuẩn cụ thể, ta sử dụng ký hiệu |x|symb , trong đó chỉ số dưới là một phép ghi nhớ để chỉ ra định nghĩa nào là có ý nghĩa. Cho p ≥ 1 là một số thực. Trên một không gian Euclide n chiều, khái niệm trực quan về độ dài của vector x = (x1 , x2 , ..., xn ) được thu được bằng cách: Đối với p ≥ 1, chuẩn p của x ∈ Rn được định nghĩa là: n ! p1 X p kxkp = |xi | . i=1 Có thể chứng minh rằng các tính chất sau đây của chuẩn Euclidean trên thực tế