Для некоторого обобщения минимаксной задачи о назначениях, представляющего собой транспортную задачу с минимаксным критерием и ограниченными целочисленными переменными, предложен алгоритм, который в общем случае является псевдополштомиаль-ным. В случае несбалансированной минимаксной задачи о назначениях алгоритм полиномиален, а при определенном соотношении параметров задачи его оценка трудоемкости линейным образом зависит от размерности задачи.
展开▼