Геометрический смысл задач линейного программирования - Матпрограмирование - Каталог для студента - Каталог статей - Школьный и студенчиский сайт
Воскресенье, 04.12.2016, 05:52
Приветствую Вас Гость | RSS

Школьный и студенческий сайт

Поиск
Категории раздела
Английский язык
Алгоритмизация
Болонский процесс
Бухгалтерский учет
Государственное регулирование экономики
Деньги и кредит
Защита информации и программ
История экономических учений
Информационные системы
Информационные системы и технологии в финансах и банковском деле
Корпоративное управление
Методички
Менеджмент
Международная экономика
Макроэкономика
Политология
Планирование
Политэкономия
Размещение продуктивных сил
Современная экономическая история
Стратегическое управление
Страхование
Системный анализ
Украинский язык
Учет и аудит
Финансы предприятия
Финансовый менеджмент
Финансы
Экономика предприятия
Экономическое обоснование хозяйственных решений
Экономический анализ
Матпрограмирование
Исследование операций
Основы создания информационных систем
Экономика и организация иновационной деятельности
Форма входа

Каталог статей

Главная » Статьи » Каталог для студента » Матпрограмирование

Геометрический смысл задач линейного программирования

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

Примерами выпуклых множеств являются: сектор, круг, многогранная область, прямая, отрезок, полуплоскость.       

Теорема 1. Пересечение любого числа выпуклых множеств есть выпуклое множество.       

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

        Определение. Точка множества называется внутренней, если в некоторой ее окрестности содержатся точки только данного множества.

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

        Определение. Точка множества называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

        Для выпуклого множества угловые точки всегда совпадают с вершинами многоугольника (многогранника), а для невыпуклого множества - это не обязательно.

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

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

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

Множество всех допустимых решений совместной системы m линейных уравнений с n переменными (m<n) является выпуклым многогранником (выпуклой многогранной областью) в n-мерном пространстве.                      

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

Определение. Точка Х называется выпуклой линейной комбинацией точек Х1, Х2, …, Хп если выполняются условия:

Х=L1*X1+L2*X2+…+Ln*Xn. [1]

Li>=0

СуммаLi равна 1.

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

Основная теорема линейного программирования. Если существует оптимальное решение Х0 задачи линейного программирования, то существует базисное оптимальное решение Х01,то есть Х01-это вершина выпуклого многогранника.

F(X01)=F(X0)

Определение. Градиентом функции F(X)=(X1, X2,…,Хп) называется вектор, проекциями которого на координатные оси служат соответствующие частные производные.

N=(dF/dX1;dF/dX2,…dF/dXn)

Направление градиента является направлением наибольшего возрастания функции.

 

Категория: Матпрограмирование | Добавил: eklion (09.06.2010)
Просмотров: 3455
Наш опрос
Оцените мой сайт
Всего ответов: 1329
Статистика
Счетчики


Каталог@MAIL.RU - каталог ресурсов интернет
Украина онлайн

Copyright MyCorp © 2016
Конструктор сайтов - uCoz