Базисное решение задачи ЛП. Свойство базисных решений задачи ЛП.

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

Теорема. Если система векторов А1 А2, ..., Аn содержит m линейно независимых векторов A1, A2, ..., Am, то допустимый план

х= (x1,; х2; ...; xm; 0; 0; ...; 0) (1)

является крайней точкой многогранника планов.

Доказательство. Так как векторы А1 А2, ..., Аn линейно независимы, то вектор Ао может быть выражен через них единственным образом:

A1x1+ A2x2+…+ Amxm=A0 (2)

Предположим, что точка (1) не является крайней. Тогда ее можно представить как выпуклую линейную комбинацию двух других различных точек x 1 и х 2 многогранника планов, т. Е.

x= λ 1 x 1 + λ 2 x 2

где

Получим

Отсюда:

Так как по предположению х — не крайняя точка, то

x j>0 (j=1, m), λ 1 > 0, λ 2 > 0

Отсюда следует, что

xj(1)>0, xj(2)>0 (j=1, m).

Из xj = 0 (j= m+1, n) и λ 1 > 0, λ 2 > 0следует xj(1)=0,

xj(2)=0 (j= m+1, n). Точки x1 и x 2 имеют ту же структуру, что и точка х, т. е.:

Поскольку векторы - допустимые планы, они должны удовлетворять векторному равенству (1). Имеем:

(3)

Так как A 1, A 2, ..., Am линейно независимы, то равенство (3) выполняется при условии x1(1)= x1(2), x2(1)= x2(2), ..., xm(1)= xm(2) т. е. x1= x2. Пришли к противоречию. Точку х невозможно представить как выпуклую линейную комбинацию двух различных точек многогранника планов. Точка х — крайняя точка многогранника решений.

18.

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

Еще по теме Базисное решение задачи ЛП. Свойство базисных решений задачи ЛП.:

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