..
ĐẠ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
Tài liệu tham khảo
49
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
P
Thời gian hoàn thành của công việc Tj .
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ý.
Ví dụ 1.1. Cho vấn đề trình tự gia công 1k
P
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.
Ví dụ 1.3. Trình tự gia công 1|rj |
P
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
Cj =
là thời gian hoàn thành hạn định đối với công việc Tj ,
j
P
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ố.
Thời gian hoàn thành, 1k
P
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ì
hạn dj
Bài toán ngược với trình tự cho
trước π
O(n log n)
O(n log n)
∗
Bài toán ngược với giá trị L cho
trước
Chuẩn
l1 , l2
Điều chỉnh thời gian
gia công pj
O(n2 log n)
3
Chuẩn
l1 , l2
l∞
O(n )
l∞
2
l1 , l2
O(n log n)
l1 , l2
2
l∞
O(n log n + cn)
l∞
O(n )
O(n )
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à:
! p1
n
X
p
|xi |
.
kxkp =
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ế
- Xem thêm -