Operations Research

Một phương pháp vững chắc để giải quyết các vấn đề tối ưu hóa tuyến tính với dữ liệu không chắc chắn đã được đề xuất vào đầu những năm 1970 và gần đây đã được nghiên cứu và mở rộng một cách đáng kể. Theo phương pháp này, chúng tôi sẵn sàng chấp nhận một giải pháp không tối ưu cho các giá trị danh nghĩa của dữ liệu nhằm đảm bảo rằng giải pháp vẫn khả thi và gần tối ưu khi dữ liệu thay đổi. Một mối quan tâm với phương pháp như vậy là nó có thể quá bảo thủ. Trong bài báo này, chúng tôi đề xuất một phương pháp cố gắng làm cho sự trao đổi này trở nên hấp dẫn hơn; nghĩa là, chúng tôi nghiên cứu các cách để giảm cái chúng tôi gọi là giá của tính kiên cường. Cụ thể, chúng tôi điều chỉnh một cách linh hoạt mức độ bảo thủ của các giải pháp kiên cường theo các giới hạn xác suất của những vi phạm ràng buộc. Một khía cạnh hấp dẫn của phương pháp của chúng tôi là phương pháp định hình kiên cường mới cũng là một vấn đề tối ưu hóa tuyến tính. Do đó, chúng tôi tự nhiên mở rộng các phương pháp của mình đến các vấn đề tối ưu hóa rời rạc một cách dễ xử lý. Chúng tôi báo cáo các kết quả số cho một bài toán tối ưu hóa danh mục đầu tư, một vấn đề ba lô, và một vấn đề từ thư viện Net Lib.

Bài báo này xem xét thiết kế và phân tích các thuật toán cho các vấn đề lập lịch và lộ trình xe cộ với các ràng buộc thời gian. Với tính khó khăn vốn có của loại vấn đề này, các phương pháp xấp xỉ dường như mang lại nhiều hứa hẹn nhất cho các vấn đề có kích thước thực tiễn. Sau khi mô tả một loạt các phương pháp heuristics, chúng tôi tiến hành một nghiên cứu tính toán toàn diện về hiệu suất của chúng. Tập hợp các vấn đề bao gồm các môi trường lập lịch và lộ trình khác nhau về loại dữ liệu được sử dụng để tạo ra các vấn đề, tỷ lệ phần trăm khách hàng có thời gian cửa, độ chặt chẽ và vị trí của chúng, cũng như tầm nhìn lập lịch. Chúng tôi phát hiện rằng một số phương pháp heuristics hoạt động tốt trong các môi trường vấn đề khác nhau; đặc biệt, một thuật toán loại chèn liên tục đưa ra kết quả rất tốt.

Bài báo này thảo luận về một quy trình heuristic rất hiệu quả để tạo ra các giải pháp tối ưu và gần tối ưu cho vấn đề người bán hàng du lịch đối xứng. Quy trình này dựa trên một phương pháp tổng quát cho các thuật toán heuristic mà được cho là có tính ứng dụng rộng rãi trong các vấn đề tối ưu kết hợp. Quy trình này tạo ra các giải pháp tối ưu cho tất cả các vấn đề đã được thử nghiệm, bao gồm cả các bài toán "cổ điển" được đề cập trong tài liệu, cũng như các bài toán thử nghiệm được sinh ngẫu nhiên, lên đến 110 thành phố. Thời gian chạy tăng trưởng khoảng theo quy luật n²; về mặt tuyệt đối, một bài toán điển hình với 100 thành phố yêu cầu chưa đến 25 giây cho một trường hợp (GE635), và khoảng ba phút để đạt được giải pháp tối ưu với độ tin cậy trên 95 phần trăm.

Một lý thuyết đơn giản về dòng lưu thông được phát triển bằng cách thay thế các phương tiện cá nhân bằng một mật độ "chất lỏng" liên tục và áp dụng một mối quan hệ thực nghiệm giữa tốc độ và mật độ. Các đặc điểm đặc trưng của lý thuyết kết quả là một quá trình "cắt đồ thị" đơn giản để theo dõi sự phát triển của các đợt sóng giao thông theo thời gian và sự xuất hiện thường xuyên của sóng sốc. Tác động của tín hiệu giao thông đối với các dòng giao thông được nghiên cứu và phát hiện có một hiệu ứng ngưỡng, trong đó sự rối loạn là nhỏ đối với giao thông nhẹ nhưng đột ngột tăng lên giá trị lớn khi mật độ đạt đến một ngưỡng quan trọng.

Các chứng cứ cho thấy con người không phải lúc nào cũng đưa ra quyết định liên quan đến phần thưởng tiền tệ không chắc chắn như thể họ đang tối đa hóa tiện ích kỳ vọng của tài sản cuối cùng. Các giải thích cho hành vi này giả định rằng các yêu cầu nhận thức về tính nhất quán với lý thuyết như vậy là quá lớn. Tuy nhiên, tồn tại những tình huống mà trong đó không chỉ có các lối tắt về mặt tinh thần được liên quan và những bất thường này đặt ra câu hỏi về lý thuyết tiện ích kỳ vọng như một hướng dẫn cho hành vi. Bài báo này khám phá khả năng lý thuyết tiện ích kỳ vọng có vẻ như thất bại vì mô tả kết quả duy nhất - tiền - không đủ. Sau khi đưa ra quyết định trong tình huống không chắc chắn, một người có thể nhận ra, khi biết về các kết quả liên quan, rằng một phương án khác sẽ được ưa chuộng hơn. Kiến thức này có thể mang lại cảm giác mất mát, hoặc hối tiếc. Những người ra quyết định sẵn sàng đánh đổi lợi nhuận tài chính để tránh sự hối tiếc sẽ thể hiện một số nghịch lý hành vi của lý thuyết quyết định. Bằng cách rõ ràng tích hợp sự hối tiếc, lý thuyết tiện ích kỳ vọng không chỉ trở thành một dự đoán mô tả tốt hơn mà còn có thể trở thành một hướng dẫn thuyết phục hơn cho việc chỉ định hành vi cho người ra quyết định.

Trong một quá trình xếp hàng, giả sử 1/λ là khoảng thời gian trung bình giữa sự đến của hai đơn vị liên tiếp, L là số lượng đơn vị trung bình trong hệ thống, và W là thời gian trung bình mà một đơn vị trải qua trong hệ thống. Đã chỉ ra rằng, nếu ba giá trị trung bình này là hữu hạn và các quá trình ngẫu nhiên tương ứng là ổn định tuyệt đối, và nếu quá trình đến là đồng nhất về mặt kinh tế với giá trị trung bình khác không, thì L = λW.

Bài báo này xem xét vị trí của các cơ sở khẩn cấp như một bài toán bao phủ tập hợp với chi phí bằng nhau trong mục tiêu. Các tập hợp được tạo thành từ các điểm cơ sở tiềm năng trong một khoảng thời gian hoặc khoảng cách xác định của mỗi điểm nhu cầu. Một ràng buộc được viết cho mỗi điểm nhu cầu yêu cầu phải được "bao phủ", và lập trình tuyến tính được áp dụng để giải quyết bài toán bao phủ, một ràng buộc cắt đơn được thêm vào khi cần thiết để giải quyết các giải pháp phân số.

Trong vấn đề cửa hàng tin tức, một người ra quyết định đối mặt với nhu cầu ngẫu nhiên cho một sản phẩm dễ hỏng sẽ quyết định số lượng cần dự trữ cho một chu kỳ bán hàng duy nhất. Vấn đề đơn giản này với giải pháp mang tính trực giác hấp dẫn là một khối xây dựng quan trọng của lý thuyết tồn kho ngẫu nhiên, bao gồm rất nhiều tài liệu tập trung vào hiệu quả hoạt động. Thông thường, trong tài liệu này, các tham số thị trường như nhu cầu và giá bán là ngoại sinh. Tuy nhiên, việc kết hợp các yếu tố này vào mô hình có thể cung cấp một phương tiện tuyệt vời để xem xét cách mà các vấn đề hoạt động tương tác với các vấn đề tiếp thị để ảnh hưởng đến việc ra quyết định tại cấp độ công ty. Trong bài báo này, chúng tôi xem xét một sự mở rộng của vấn đề cửa hàng tin tức trong đó số lượng dự trữ và giá bán được xác định đồng thời. Chúng tôi cung cấp một cái nhìn tổng thể toàn diện tổng hợp các kết quả hiện có cho vấn đề chu kỳ đơn và phát triển các kết quả bổ sung để làm phong phú thêm cơ sở tri thức hiện có. Chúng tôi cũng xem xét và phát triển cái nhìn sâu sắc về một sự mở rộng tồn kho động của vấn đề này, và tạo động lực cho tính ứng dụng của các mô hình như vậy.

Lập trình ngẫu nhiên có thể mô tả hiệu quả nhiều vấn đề ra quyết định trong các môi trường không chắc chắn. Tuy nhiên, những chương trình như vậy thường đòi hỏi tính toán cao để giải quyết. Thêm vào đó, các giải pháp của chúng có thể gây hiểu lầm khi có sự mơ hồ trong việc lựa chọn phân phối cho các tham số ngẫu nhiên. Trong bài báo này, chúng tôi đề xuất một mô hình mô tả sự không chắc chắn cả trong hình thức phân phối (rời rạc, Gaussian, mũ, v.v.) và các động lượng (trung bình và ma trận hiệp phương sai). Chúng tôi chứng minh rằng đối với một loạt các hàm chi phí, chương trình ngẫu nhiên bền vững được liên kết (hoặc min-max) có thể được giải quyết một cách hiệu quả. Hơn nữa, bằng cách phát triển một vùng tự tin mới cho trung bình và ma trận hiệp phương sai của một vector ngẫu nhiên, chúng tôi cung cấp các lập luận xác suất cho việc sử dụng mô hình của chúng tôi trong các vấn đề phụ thuộc nhiều vào dữ liệu lịch sử. Những lập luận này được xác nhận trong một ví dụ thực tiễn về việc lựa chọn danh mục đầu tư, nơi khung của chúng tôi dẫn đến các chính sách có hiệu suất tốt hơn trên phân phối "thực" nằm dưới các lợi nhuận hàng ngày của các tài sản tài chính.

Bài báo này thiết lập vấn đề kiểm soát tối ưu cho một lớp mô hình toán học trong đó hệ thống cần kiểm soát được đặc trưng bởi một quá trình Markov rời rạc với trạng thái hữu hạn. Các trạng thái của quá trình nội bộ này không thể quan sát trực tiếp từ bộ điều khiển; thay vào đó, bộ điều khiển có một tập hợp đầu ra có thể quan sát mà chỉ có mối quan hệ xác suất với trạng thái nội tại của hệ thống. Phương pháp thiết lập được minh họa bằng một ví dụ đơn giản về bảo trì máy móc, và các lĩnh vực ứng dụng cụ thể khác cũng được thảo luận. Bài báo chứng minh rằng, nếu chỉ còn một số lượng hữu hạn các khoảng thời gian kiểm soát, thì hàm chi trả tối ưu là một hàm lồi, tuyến tính từng đoạn của xác suất trạng thái hiện tại của quá trình Markov nội bộ. Ngoài ra, một thuật toán để sử dụng thuộc tính này nhằm tính toán chính sách kiểm soát tối ưu và hàm chi trả cho bất kỳ khoảng thời gian hữu hạn nào được phác thảo. Những kết quả này được minh họa bằng một ví dụ số cho vấn đề bảo trì máy móc.