Характеризация типов полностью нецелочисленных вершин многогран­ника трехиндексной аксиальной задачи о назначениях

Abstract

The characterization and combinatorial properties of all types of completely non-integer vertices (all positive components of vertices are fractional) of the three-index axial assignment problem polytope is researched. Доказано, что для любого числа r e {2n, 2n+1,..., 3n-2} и только для такого, многогранник трехиндексной аксиальной задачи о назначениях порядка n>2 имеет вершины, все положительные компоненты которых являются дробными и их число равно r. Для каждого числа r e {2n, 2n+1,..., 3n-2} охарактеризованы все типы таких вершин.