6. Задачи целочисленного программирования

Подпрограмма MNR3R, реализующая алгоритм Балаша для линейной задачи с булевыми переменными, компактно хранит входную и промежуточную информацию. При длительном счете можно выдать промежуточный результат, а потом продолжить счет, передав в программу последнее допустимое решение. Удачное допустимое решение известное apriory может существенно ускорить счет.

Полностью целочисленный алгоритм Гомори, реализованный в подпрограмме MLC2R, предназначен для решения линейных задач целочисленного программирования с большим количеством ненулевых элементов в матрице условий (больше 50%). Он требует довольно большого объема памяти и поэтому размеры решаемых задач довольно жестко ограничены: (4 + m + n) (n + 3)  10000, где m - количество ограничений, а n - количество переменных в матрице условий.

Для задач с разреженной матрицей условий в подпрограмме MLC3R реализован модифицированный вариант алгоритма Гомори. В этой программе матрица условий хранится компактно, программа требует меньше памяти, и в случае сильной разреженности матрицы условий время счета (по сравнению с MLC2R) тоже уменьшается.

7. Поиск минимума функции одной переменной

Для решения этой задачи можно использовать практически все программы следующих разделов, но наиболее эффективны будут программы поиска минимума функции многих переменных на заданном направлении (см. следующий пункт настоящего введения).

Любая из этих программ найдет локальный минимум, вообще говоря, ближайший к начальной точке. Для поиска глобального минимума функции одной переменной на заданном отрезке предназначена программа MNGGR.

8. Поиск минимума функции многих переменных на заданном отрезке или направлении

Подпрограммы этого подраздела могут быть использованы как самостоятельно - для минимизации функции одной переменной, так и в качестве блока одномерной минимизации в задаче поиска минимума функции многих переменных в некотором более широком подмножестве, например, в задаче безусловной минимизации. Из 7 подпрограмм 5 используют только значения минимизируемой функции, а 2 (MNK3R, MNL3R) - значения функции и градиента.

9. Задача поиска минимума функции многих переменных на всем пространстве

Подпрограммы, решающие эту задачу, разделены на два класса: не использующие и использующие вычисление градиента в процессе счета. Две подпрограммы первого класса (MNI2R и MNAVR) вычисляют разностный градиент, а MNI2R - даже вторые разности. Подпрограмма MNAVR предназначена для решения специального, но достаточно широко распространенного класса задач, когда надо минимизировать сумму квадратов дифференцируемых функций.

Подпрограммы второго класса (MNR1R, MNB3R, MNB4R, MNK2R) как правило дают более высокую точность результата.

10. Задача поиска минимума функции многих переменных на многомерном параллелепипеде

Подпрограммы этого подраздела тоже различаются на два класса: не использующие градиент и использующие градиент. Среди подпрограмм первого класса MN06R (покоординатный спуск) удобен, если не требуется большая точность вычислений, MN04R (случайный поиск) рекомендуется при достаточно большой размерности (N  10). Подпрограмма MNK6R (градиентный метод) вычисляет разностный градиент на каждой итерации. Иногда эта программа работает даже лучше, чем MNK4R, в которой градиент считается более точно. Подпрограммы, использующие вычисление градиента, дают обычно более точное решение. Метод условного градиента (MNK5R) особенно хорошо работает, если решение находится в вершине параллелепипеда.