3, 4 Опорные планы бакалавр

1.3 Опорные планы ЗЛП

Рассмотрим каноническую ЗЛП в векторной записи

Ранг r системы – это число линейно независимых уравнений.

Если r < n, (n - число неизвестных) то система (37) имеет несколько неотрицательных решений.

Если r = n, в системе единственное решение, (выбора оптимального решения нет).

Случай r > n вообще невозможен.

Пусть r < n.

В этом случае система n векторов а1, …, an будет содержать базис - максимальную линейную независимую подсистему.

Переменные, соответствующие r векторам базиса, называют базисными.

Остальные nr переменных называют свободными.

Если в базисном решении все базисные переменные принимают отрицательные значения, то его называют опорным.

Опорный план не может содержать более чем r положительных компонент.

Опорный план называется невырожденным, если он содержит точно r отличных от нуля компонент.

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

1.4 Основная теорема линейного программирования

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

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


Comments

comments

Закладка Постоянная ссылка.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *