28. Первая основная теорема ЛП (Теорема о существовании)

Теорема: Для того, что бы задача ЛП имела решение необходимо и достаточно, что бы допустимые множества как прямой, так и двойственной задачи были не пусты.

Док – во: Для доказательства того, что в обеих задачах существует допустимые векторы, рассмотрим ограничения-неравенства в двойственных задачах:

Т.к.

вектора У и Х неотрицательны, то:

Следовательно, если Х и У допустимые векторы то . Т.е. значение ЦФ в задаче максимизации не превосходит значение ЦФ в двойственной задаче минимизации.

Предположим, что в каждой из этих задач существуют допустимые вектора и . Допустимое множество прямой задачи содержит вектор и следовательно не пусто. ЦФ в прямой задаче ограничена, т.к. для любого допустимого вектора Х: . Следовательно прямая задача имеет решение. Т.к. при любом допустимом векторе У : то ЦФ двойственной задачи ограничена снизу. А т.к. допустимое множество в этой задаче содержит вектор, то и двойственная задача имеет решение.

Покажем, что если решение задачи ЛП существует, то допустимые множества как прямой, так и двойственной задачи не пусты.

Пусть является решением задачи максимизации. Тогда очевидно, что прямая задача имеет хотя бы 1 допустимый вектор, а именно . Известно, что ЦФ вогнута, а функции ограничений выпуклы и что выполняется условие регулярности ограничений. Поэтому если является решением задачи максимизации, то существует вектор удовлетворяющий условиям: , , т.ч. есть допустимый вектор. Теорема доказана.

<< | >>
Источник: Шпаргалка - Математические методы и модели исследования операций. 2016
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 28. Первая основная теорема ЛП (Теорема о существовании):

  1. 29. Вторая основная теорема ЛП (первая основная теорема двойственности). Доказательство. Замечание.
  2. Первая теорема двойственности(Основная).
  3. 17.теорема Лиувилля.( понятие целой ф-ции. Основная теорема алгебры)
  4. Основные теоремы о пределах. Признаки существования предела.
  5. 11. Теореми і аксіоми. Види теорем. Методи доведення теорем.
  6. 31 Третья основная теорема ЛП (теорема о дополняющей нежесткости). Доказательство.
  7. 1. Теореми і аксіоми. Види теорем. Методи доведення теорем. Геометричні і алгебраїчні задачі на доведення і дослідження.
  8. 6. Основная теорема ЛП. Принципиальная схема решения ЗЛП, вытекающая из этой теоремы.
  9. Теорема 8 (необходимый признак существования экстремума).
  10. Теорема существования.
  11. Вопрос 30. Теорема о существовании интеграла Лебега.
  12. 22. Теорема о существовании и единственности решения интегрального уравнения Фредгольма.
  13. 14. Дифференциальные уравнения, основные понятия. Задача Коши. Теорема существования и единственности решения задачи Коши.
  14. 3. МНОГОЧЛЕНЫ. КРИТЕРИИ РАВЕНСТВА МНОГОЧЛЕНОВ. ДЕЛЕНИЕ МНОГОЧЛЕНОВ. ТЕОРЕМА БЕЗУ И ЕЕ СЛЕДСТВИЯ. ОСНОВНАЯ ТЕОРЕМА АЛГЕБРЫ. РАЗЛОЖЕНИЕ МНОГОЧЛЕНОВ НА МНОЖИТЕЛИ.
  15. Теорема 14 (необходимый и достаточный признак существования вертикальной асимптоты).
  16. 33.Теорема существования оптимальных планов пары двойственных задач:
  17. 24 Первая теорема общественного благосостояния.
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -