Математическое программирование

Пример прикладных задач Задача 1. Производственная задача

Фирма хочет наладить производство некоторых товаров с тем, чтобы от их реализации получалась max прибыль с учетом ограниченности ресурсов

Введем обозначения:

n – число различных товаров

m – число различных товаров

– прибыль от j-го товара ( )

– количество i-го ресурса ( )

расход i-го ресурса при производстве единицы j-го товара

– объем выпускаемого j-го товара

– производственный план

– прибыль

– необходимо максимизировать

– количество единиц i-го ресурса, которого будет реализовано в связи с планом

Построенная математическая модель представляет собой задачу линейного программирования.

Задача 2. О строительстве зрительного зала

Необходимо спроектировать зрительный зал в здании, имеющем форму полу эллипсоида max объема в форме прямоугольника, боковые стены которого должны быть плоскостям симметрии полу эллипсоида.

a, b, c – размеры полу эллипсоида

x – вершина прямоугольника (принадлежащая полу эллипсоида)

Тогда объем

2е т.к. вершина должна лежать на полу эллипсоиде

Мы построили задачу типа классических задач Лагранжа – задача нелинейного программирования

Общая задача математического программирования при ограничениях: – множество допустимых решений задачи
ОПРЕДЕЛЕНИЕ
ОПРЕДЕЛЕНИЕ
ОПРЕДЕЛЕНИЕ
ОПРЕДЕЛЕНИЕ
ОПРЕДЕЛЕНИЕ Оптимальное решение – глобальный экстремум

Под стандартной формой задачи математического программирования понимают

Под канонической формой понимают

Правила перехода от одной формы к другой

1. Связь между типами экстремумов

2. Если « », то умножив на (-1) поменяем тип неравенства на « »

3. Если ограничение имеет форму неравенства, вводим дополнительную переменную и заменяем неравенство на равенство

4. Переход от равенств к неравенствам:

1 вариант.

2 вариант. За счет выражения одной переменной через другую

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

1. Задачи линейного программирования (ЗЛП)

имеет вид

2. Задачи выпуклого программирования (ЗВП)

Необходимо, чтобы

ОПРЕДЕЛЕНИЕ

Множество X называется выпуклым, если

– выпуклая комбинация 2-х точек (при фиксированном )

Все выпуклые комбинации 2х точек образуют выпуклую оболочку, натянутую на 2

ОСНОВНОЕ СВОЙСТВО

выпуклых множеств всегда выпукло

ОПРЕДЕЛЕНИЕ

Функция , определенная на выпуклом множестве , называется выпуклой, если

	ПРИМЕР Если – выпуклая, то функция – тоже выпуклая
ЦЕНТРАЛЬНОЕ СВОЙСТВО локальный выпуклой функции является глобальным ( локальный вогнутой функции является глобальным)

Среди задач выпуклого программирования выделяются задачи выпуклого квадратичного программирования (ЗВКП).

, где D-матрица 2-ых частных производных