2. Метод жесткого многогранника

1) не следует применять для решения прикладных задач из-за его низкой точности;

2) следует применять в первую очередь из-за его простоты;

3) не эффективен из-за относительно больших затрат машинного времени на его реализацию при необходимости получить высокую точность решаемых задач;

4) применим лишь в задачах на безусловный экстремум.

3. Метод деформируемого многогранника

1) применим лишь в задачах на безусловный минимум или максимум;

2) имеет весьма сложный алгоритм;

3) требует большой подготовительной работы;

4) применим в задачах как на условный, так и безусловный минимум (максимум).

4. Метод случайного поиска

1) следует применять только в задачах с ограничениями типа «неравенства»;

2) эффективен при наличии большого количества ограничений типа «неравенства»;

3) не обеспечивает отыскания минимума (максимума) целевой функции;

4) эффективен при сравнительно большой размерности вектора x и наличии большого количества ограничений.

Глава IV. Линейное программирование

Введение. Линейное программирование стало быстро развиваться, начиная с 50-х годов прошлого столетия, привлекая инженеров, экономистов и математиков широким практическим применением и строгой математической постановкой. Линейное программирование нашло широкое применение при

1. оптимальном регулировании полетов на воздушных линиях;

2. распределении во времени транспортировки грузов из одного пункта в другой;

3. планировании промышленного производства;

4. распределении кадров;

5. организации потоков в транспортных сетях и многих других задачах, среди которых можно упомянуть, например, даже такую задачу как организация рационального откорма животных и т.п.

Линейное программирование – наиболее часто используемый метод при решении задач оптимизации. Около 75% всех оптимизационных задач приходится на этот метод.

4.1. Необходимые сведения

Ранг матрицы. Рассмотрим - матрицу

, . (4.1)

Для этой же матрицы широко применима и такая запись

. (4.2)

Выделим произвольные k строк и произвольные k столбцов. Определитель из элементов, стоящих на пересечении этих выделенных строк и столбцов, называется минором k- го порядка. Например, для матрицы

, (4.3)

определитель

есть минор второго порядка, полученный для первой, третьей строки и второго, четвертого столбцов.

Наибольший из порядков миноров отличных от нуля называется рангом матрицы. Ранг обозначается как или , или просто r. Ранг обладает следующими свойствами:

(нулевые матрицы не рассматриваются);

, т.е. ранг матрицы не может превышать наименьшего из чисел m или n.

Назовем базисным минором любой из минор порядка , который отличен от нуля.

Пример. Найдем ранг матрицы

.

Легко убедиться в том, что все миноры третьего порядка этой матрицы равны нулю. Следовательно, ранг матрицы A не может быть равен трем. Отличные от нуля миноры второго порядка имеются, так, например,

,

следовательно, .

Базисными минорами являются, например, миноры

,

и т.д.

Совместные системы. Рассмотрим систему уравнений

, (4.4)

где А – матрица коэффициентов, векторы , . Если существует такой вектор , что (имеет место арифметическое тождество), то – решение системы уравнений (4.4). Система уравнений (4.4) называется совместной, если существует хотя бы одно решение этой системы.

Так система

;

не совместна, т.к. нельзя указать ни одного решения, которое бы обращало в тождество оба уравнения.

Теорема Кронекера-Капелли. Рассмотрим систему (4.4)

(4.5)

и расширенную матрицу

Теорема. Для совместности системы (4.5) необходимо и достаточно, чтобы

. (4.6)

Теорема приводится без доказательства. Однако заметим, что поскольку всякий минор матрицы А является так же и минором матрицы U, то

.

Теорема утверждает, что для совместности системы должно иметь место равенство .

Пример. Рассмотрим систему

;

,

для этой системы

, , ,

, , следовательно, – система не совместная.

Пример. Для системы

;

, , , ,

система совместная.

Практическая ценность теоремы Кронекера-Капелли состоит в том, что она позволяет исключить из рассмотрения те задачи, которые не имеют решения.