русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2015-09-15; просмотров: 1440; Нарушение авторских прав


В основе линейного программирования лежит теория выпуклых множеств. В школьном курсе математики вы рассматривали выпуклые многоугольники. Только напомним.

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

Среди точек выпуклого множества можно выделить внутренние, граничные и угловые.

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

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

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

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

 

На рис. приведены примеры различных точек:

М – внутренняя;

N – граничная;

А – угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например отрезка АР, она не является внутренней; точка А – внутренняя для отрезка KL, но этот отрезок не принадлежит целиком многоугольнику.

Для выпуклого многоугольника угловые точки всегда совпадают с вершинами многоугольника.

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

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



 

Сформулируем без доказательства 2 теоремы, которые имеют отношение к поиску решения задачи линейного программирования и опираются на теорию выпукл

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

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

Согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них оптимального, необходимо исследовать конечное число угловых точек многоугольника решений.

 



<== предыдущая лекция | следующая лекция ==>
Общая форма | 


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.