Элементы матричной алгебры




НазваниеЭлементы матричной алгебры
страница9/24
Дата публикации23.06.2013
Размер1.64 Mb.
ТипДокументы
lit-yaz.ru > Математика > Документы
1   ...   5   6   7   8   9   10   11   12   ...   24
^

3.2. Свойства задачи линейного программирования.



Рассмотрим задачу линейного программирования в канонической (основной) форме: найти вектор , максимизирующий (минимизирующий) линейную целевую функцию max (min) (3.1)

при ограничениях:

(3.3)

Определение 1. Вектор , удовлетворяющий функциональным ограничениям (3.2) и прямым (3.3) (условию неотрицательности переменных) называется допустимым решением или планом задачи линейного программирования.

Определение 2. Допустимое решение ЗЛП, при котором целевая функция (3.1) достигает экстремума (максимума или минимума) называется оптимальным (оптимальный план).

Следовательно, X*оптимальный (максимальный) план, если для любого выполняется условие .

Теорема 1. Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто).

Теорема 2. Если основная задача линейного программирования имеет оптимальный план, то максимальное (минимальное) значение целевая функция задачи принимает в одной из вершин многогранника решений (в угловой точке).

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

Теорема 3. Каждому допустимому базисному решению (опорному решению) задачи линейного программирования соответствует угловая точка многогранника решений. И наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение основной задачи линейного программирования.

Так как система линейных уравнений имеет конечное число опорных решений ( не более , где r ранг системы уравнений), то область допустимых решений имеет конечное число угловых точек.

Определение 3. Выпуклое множество с конечным числом угловых точек называется выпуклым многогранником. Угловая точка–вершина многогранника.

Сформулированные теоремы позволяют сделать следующие выводы:

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

  • Каждая вершина этого многогранника определяет опорный план.

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

Таким образом, теоремы 2 и 3 указывают принципиальный путь решения задач линейного программирования:

вместо исследования бесконечного множества допустимых решений для нахождения оптимального решения необходимо исследовать лишь конечное число угловых точек (конечное число опорных решений).
1   ...   5   6   7   8   9   10   11   12   ...   24

Похожие:

Элементы матричной алгебры iconКурсовая работа по дисциплине «Информатика» на тему «Применение алгебры...
Элементы алгебры высказываний. Примеры использования алгебры высказываний в информатике

Элементы матричной алгебры iconКурсовая работа по информатике на тему: «применение алгебры высказываний в информатике»
Алгебра – это наука, которая изучает множество некоторых элементов и действия (операции) над ними. Если элементы алгебры – натуральные...

Элементы матричной алгебры iconКонспект урока на тему «Основы логики (повторение). Решение логических...
Основы логики; познакомить учащихся с методами решения логических задач; формирование у учащихся практических умений и навыков решения...

Элементы матричной алгебры iconМетод «от пролога к эпилогу»
«все его элементы суть элементы смысловые» (Лотман Ю.). Исходя из этих положений, выделяем основные приемы, опробуем их на уроке

Элементы матричной алгебры iconЭлементы радиочастотных линий передачи
Элементы радиочастотных линий передачи: Учебно-методическое пособие по курсу «Устройства свч и антенны» / В. В. Паслен, Е. С. Нестругина....

Элементы матричной алгебры iconДипломной практике «система управления ртк для обработки сложных поверхностей»
Обычно изделия изготавливаются из мягких цветных металлов, пластика или дерева. Это могут быть элементы орнамента для декорирования...

Элементы матричной алгебры iconУрок по геометрии в 8 классе на тему «теорема пифагора»
Осуществление межпредметной связи алгебры с географией, историей, литературой, геометрией

Элементы матричной алгебры icon15. Уроки алгебры Кирилла и Мефодия,10-11 класс
МАрк sql. Автоматизированная информационно-библиотечная система. Версия для школьных библиотек

Элементы матричной алгебры iconРабочая программа факультативного курса «Элементы статистики и теории вероятностей»
«Элементы комбинаторики, статистики и теории вероятностей». Так как в этом году учащиеся 9 класса изучают программный материал по...

Элементы матричной алгебры iconИсследование свойств алгебры множеств
Цель работы: Изучение множества, его подмножеств и законов сочетания подмножеств, образующих алгебраическую систему, называемую булевой...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница