Свойства выпуклого множества

Классификация и специфика задач математического программирования.

Введение в математическое программирование.

Математическое программирование является одним из способов исследования операций в экономике. Содержание математического программирования составляют теория и методы решения задач о нахождении экстремума функции на некотором множестве. Множества могут определяться как линейными так и не линейными ограничениями. Главная цель задач математического программирования – выбор программ действий, приводящих к наилучшему результату, с точки зрения лица, принимающего решения (ЛПР). Проблема принятия решения в последовательности операции неразрывно связано с проблемами моделирования.

Определение модели.

Модель – это образ изучаемого явления или объекта.

Этапы моделирования.

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

2. Построение математической модели. Запись качественной модели в математических терминах.

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

Реальное решение может и не существовать.

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

3 этап. Исследование влияния переменных на значения целевой функции, нахождение решения, поставленной задачей.

4 этап. Сопоставление результатов вычисления, полученных на 3 этапе с моделированным объектом , т.е. критерий практики.

Здесь устанавливается степень адекватности модели и моделируемого объекта.

 

В математическом программировании можно выделить два направления:

· Собственно математическое программирование – детерминированные задачи, когда вся исходная информация полностью определена;

· Стохастическое программирование. К нему относятся задачи, в которых исходная информация содержит неопределённость, либо когда некоторые параметры носят случайный характер с известными вероятностными характеристиками.

 

В математическом программировании выделяют следующие разделы:

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

2) Нелинейное программирование. Данная задача и целевая функция и ограничения носят нелинейный характер. Задачи нелинейного программирования принято подразделять на:

a) Выпуклое программирование, когда целевая функция выпукла и выпукло множество, на котором решается задача.

b) Квадратичное программирование, когда целевая функция квадратична, а ограничения линейное равенство или неравенство.

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

3) Целочисленное программирование, когда на значения переменных или на значения целевой функции накладывается условие целочисленности.

Специфика задач математического программирования состоит в том, что, во-первых, методы классического анализа для отыскания условных экстремумов неприменимы, т.к. даже в простых задачах экстремумы достигаются в углах многогранника решения, а, следовательно, нарушается дифференцируемость функции.

Во-вторых, в практических задачах число переменных и ограничений столь велико, что если перебирать все точки в экстремальности, то может не хватить ресурсов ЭВМ, поэтому цель математического программирования создание, где возможно, аналитических методов решения, а при отсутствии таких методов – создание эффективных вычислительных способов нахождения принудительного решения.

 

Элементы выпускного анализа.

 

Множество Хназывается замкнутым если оно содержит все свои предельные точки

 

 

 

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

 

Множество Хназывается выпуклым множеством если на ряду с каждыми точками Х1, Х2 є этому множеству все точки Х равны (1-α)· , где 0≤α≤1 так же принадлежат этому множеству Х. Т.е. если множеству Х, то и отрезок, соединяющий эти точки, тоже множеству Х.

Пример:

Дано множество Ө ={х, у такие, что х+у≤1. Доказать, что данное множество является выпуклым.

0≤α≤1

 

Пусть взяли две точки ( ) и ( ) Ө (т.е. + ≤1 и + ≤1).

Доказать, что точка

 

 

 

1. Теорема 1

Пересечение выпуклых множеств является выпуклым множеством.

Доказательство:

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

Докажем, что Х выпуклое множество.

Пусть точки и Х. Докажем, что отрезок, соединяющий эти точки, тоже принадлежит множеству Х.

т.к. и Х => и Х1

Х1 выпуклое множество => отрезок [ , ] Х1

т.к. , Х => они Х2

Х2 выпуклое множество.

[ , ] Х2.

Отсюда следует, что отрезок [ , ] Х1∩Х2=Х

Теорема доказана.

2. Теорема 2.

Объединение выпуклых множеств не всегда является выпуклым.

3. Свойство определённости.

Рассмотрим двухмерное пространство, в котором имеется некоторое замкнутое и выпуклое множество Х и некая точка d ( , ), где d Х, тогда найдётся прямая

+ = с такая, что будут выполняться неравенства

 

Гиперплоскостью в пространстве R называется множество точек x ( которая удовлетворяет равенству