Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Базисные решения. Базисные допустимые решения (БДР)




Пусть задана задача ЛП (2.1.1) в стандартной форме. Предположим, что матрица , имеет ранг , т.е. имеет линейно – независимых столбцов. Обозначим - допустимое множество.

Базисом матрицы называется набор линейно независимых столбцов .

Базисным решением, соответствующим базису , называется вектор , для которого , , есть -я компонента вектора , .

Базисные решения ограничений могут быть получены, если приравнять нулю переменных и решить уравнений относительно оставшихся переменных. Предполагается, что эти уравнения имеют единственное решение.

Если базисное решение , то называется базисным допустимым решением.

Отрезок определяется соотношением

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

Вершиной или углом выпуклого множества называется любая точка, не лежащая внутри произвольного отрезка, соединяющего разные точки множества.

Выпуклой оболочкой точек называется множество точек вида

Теорема 1. Допустимая область задачи (2.1.1) является выпуклым множеством.

Теорема 2. Базисные допустимые решения задачи (2.1.1) соответствуют вершинам допустимого выпуклого множества .

Теорема 3. Если множество непусто и матрица имеет ранг , то в задаче (2.1.1) существует, по крайней мере, одно БДР.

Теорема 4. Если в задаче (2.1.1) имеется конечный минимум, то по крайней мере одно оптимальное решение является БДР.

Пример. Задача (2.0.1) может быть приведена к следующему виду

(2.0.1.а)

В матричной форме ограничения задачи имеют вид

Все возможные базисные решения могут быть сведены в таблицу

 

   
           
        -525  
          A
  566     466 C
      -700    
          B

 

Допустимые базисные решения изображены на рис. 1.





Поделиться с друзьями:


Дата добавления: 2015-02-12; Мы поможем в написании ваших работ!; просмотров: 1328 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Логика может привести Вас от пункта А к пункту Б, а воображение — куда угодно © Альберт Эйнштейн
==> читать все изречения...

2432 - | 2384 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.008 с.