Tìm kiếm hình chiếu của một điểm cho trước trên tập hợp các nghiệm của bài toán lập trình tuyến tính

A. I. Golikov1, Yu. G. Evtushenko1
1Dorodnitsyn Computing Centre, Russian Academy of Sciences, Moscow, Russia

Tóm tắt

Vấn đề tìm hình chiếu của các điểm trên tập hợp nghiệm của bài toán nguyên thủy và đối ngẫu của lập trình tuyến tính được xem xét. Vấn đề này được giảm về một nghiệm duy nhất của bài toán tối thiểu hóa một hàm phụ trợ mới, bắt đầu từ một giá trị ngưỡng nhất định của hệ số hình phạt. Các ước lượng về giá trị ngưỡng đã được thu được. Một việc triển khai phần mềm của phương pháp được đề xuất được so sánh với một số gói phần mềm thương mại và nghiên cứu đã biết để giải quyết các bài toán lập trình tuyến tính.

Từ khóa

#hình chiếu #bài toán lập trình tuyến tính #nguyên thủy #đối ngẫu #hàm phụ trợ #hệ số hình phạt

Tài liệu tham khảo

I. I. Eremin, Theory of Linear Optimization (Izd. Yekaterinburg, Yekaterinburg, 1999; VSP, Utrecht, 2002).

F. P. Vasil’ev and A. Yu. Ivanitskii, Linear Programming (Faktorial, Moscow, 2003) [in Russian].

A. I. Golikov and Yu. G. Evtushenko, Zh. Vychisl. Mat. Mat. Fiz. 40(12), 1766 (2000).

C. Kanzow, H. Qi, and L. Qi, J. Optim. Theory Appl. 116, 333 (2003).

A. I. Golikov, Yu. G. Evtushenko, and N. Mollaverdi, Zh. Vychisl. Mat. Mat. Fiz. 44(9), 1564 (2004).

O. L. Mangasarian, Optim. Methods Softw. 17(5), 913 (2002).

O. L. Mangasarian, J. Optim. Theory Appl. 121(1), 1 (2004).

Cs. Mészáros, Optim. Methods Softw. 11/12(1–4), 431 (1999).

E. D. Andersen and K. D. Andersen, in High Performance Optimization (Kluwer, New York, 2000), pp. 197–232.

L. D. Popov, Zh. Vychisl. Mat. Mat. Fiz. 47(2), 206 (2007).