Klee-Minty’s LP and upper bounds for Dantzig’s simplex method期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Klee-Minty’s LP and upper bounds for Dantzig’s simplex method

Authors:	Tomonari Kitahara Shinji Mizuno

Affiliation:	^a Graduate School of Decision Science and Technology, Tokyo Institute of Technology, 2-12-1-W9-62, Ookayama, Meguro-ku, Tokyo, 152-8552, Japan ^b Graduate School of Decision Science and Technology, Tokyo Institute of Technology, 2-12-1-W9-58, Ookayama, Meguro-ku, Tokyo, 152-8552, Japan

Abstract:	Kitahara and Mizuno (2010) [2] get two upper bounds for the number of different basic feasible solutions generated by Dantzig’s simplex method. The size of the bounds highly depends on the ratio between the maximum and the minimum values of all the positive elements of basic feasible solutions. We show that the ratio for a simple variant of Klee-Minty’s LP is equal to the number of iterations by Dantzig’s simplex method for solving it.

Keywords:	Simplex method Linear programming Basic feasible solutions Klee-Minty&rsquo s LP
本文献已被 ScienceDirect 等数据库收录！