Множество решений задачи линейного программирования

Будем называть допустимым решением задачи линейного программирования всякий n –мерный вектор , удовлетворяющий ограничениям (1) и (2). Множество всех допустимых решений называется допустимым множеством ОЗЛП.

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

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

Теорема. Если некоторая задача линейного программирования имеет более одного оптимального решения, то она имеет бесконечно много оптимальных решений.

Доказательство. Предположим, что задача имеет два оптимальных решения и . Тогда и .Пусть . Тогда и , так как значение целевой функции на всех оптимальных решениях одинаково. Рассмотрим произвольный вектор х вида , где 0< <1. Тогда, очевидно, , то есть и . Следовательно, х – допустимое решение ОЗЛП. Кроме того, , то есть –оптимальное решением при любом , что и доказывает теорему.

Аналогично доказывается теорема и в случае задачи линейного программирования общего вида.

Дата добавления: 2015-07-14