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.

The concepts of the “center” and the “median vertex” of a graph are generalized to the “absolute center” and the “absolute median” of a weighted graph (a graph with weights attached to its vertices as well as to its branches). These results are used to find the optimum location of a “switching center” in a communication network and to locate the best place to build a “police station” in a highway system. It is shown that the optimum location of a switching center is always at a vertex of the communication network while the best location for the police station is not necessarily at an intersection. Procedures for finding these locations are given.

An influence diagram is a graphical structure for modeling uncertain variables and decisions and explicitly revealing probabilistic dependence and the flow of information. It is an intuitive framework in which to formulate problems as perceived by decision makers and to incorporate the knowledge of experts. At the same time, it is a precise description of information that can be stored and manipulated by a computer. We develop an algorithm that can evaluate any well-formed influence diagram and determine the optimal policy for its decisions. Since the diagram can be analyzed directly, there is no need to construct other representations such as a decision tree. As a result, the analysis can be performed using the decision maker's perspective on the problem. Questions of sensitivity and the value of information are natural and easily posed. Modifications to the model suggested by such analyses can be made directly to the problem formulation, and then evaluated directly.

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.