کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871325 1440183 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On inverse linear programming problems under the bottleneck-type weighted Hamming distance
ترجمه فارسی عنوان
در مسائل برنامه نویسی خطی معکوس در فاصله جابجایی هامینگ با وزن تنگنا
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a linear programming problem with the objective function coefficients vector c and a feasible solution x0 to this problem, a corresponding inverse linear programming problem is to modify the vector c as little as possible to make x0 form an optimal solution to the linear programming problem. The modifications can be measured by different distances. In this article, we consider the inverse linear programming problem under the bottleneck-type weighted Hamming distance. We propose an algorithm based on the binary search technique to solve the problem. At each iteration, the algorithm has to solve a linear programming problem. We also consider the inverse minimum cost flow problem as a special case of the inverse linear programming problems and specialize the proposed method for solving this problem in strongly polynomial time. The specialized algorithm solves a shortest path problem at each iteration. It is shown that its complexity is better than the previous one.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 240, 11 May 2018, Pages 92-101
نویسندگان
, ,