Задать вопрос юристу

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

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

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

Т.к.

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

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

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

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

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

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

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

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