1.Линейное программирование. Построение моделей линейного программирования простейших экономических задач. Методы решения задач линейного программирования.

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

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

Преобразование  ЗЛП:

1. Преобразование целевой функции:

задача max Z равносильна min (-Z).

2. Преобразование ограничений

А) неравенство в равенство:

введение неотрицательных  переменных

Б) равенство  в неравенство:

выразить базисные переменные через свободные и  воспользоваться условием неотрицательности базисных переменных.

3. Преобразование переменных:

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

Решение, в котором  все свободные переменные равны нулю, называется базисным.

Базисное решение, в котором все переменные неотрицательные называется опорным.

Неотрицательное решение системы ограничений  является допустимым.

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

Методы  решения:

Графический метод

Для задач n – m = 2

Алгоритм:

1. Преобразовать ограничения (выразить базисные переменные через свободные и воспользоваться условием неотрицательности базисных переменных)
2. Выразить целевую функцию через свободные переменные
3. Построить ОДР
4. Построить линию уровня
5. Определить оптимальное решение

 

Симплекс-метод (табличный алгоритм)

Алгоритм:

1.Найти исходное  опорное решение 
 
 

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

2.Проверка найденного решения на оптимальность

А) если оценки всех свободных переменных не положительны, то решение оптимально;

Б) если среди  свободных переменных найдется хотя бы один положительный элемент, столбец  которого содержит хотя бы один положительный коэффициент, то найденное решение может быть улучшено;

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

3.Переход к  новому опорному решению

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

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

В)Разделим элементы разрешающей строки на разрешающий элемент. Заполним базисные столбцы.

Все остальные  элементы пересчитать по формуле:

Г)Переходим  к шагу 2. 

Двухэтапный метод

Решается задача нахождения оптимального решения для задачи: 

1 этап – Составляется  вспомогательная задача, где

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

 

2 этап – Найденное  оптимальное решение на 1 этапе  берется в качестве ИОР для  исходной задачи и оптимальное решение ищется с помощью симплекс-метода. 

2.Нелинейное программирование. Выпуклое и квадратичное программирование. Методы решения задач квадратичного программирования.

Если хотя бы одна из функций gi(x) не линейна – это задача нелинейного программирования.

Проблема:

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

2.ЗНЛП может  иметь локальный и глобальный  экстремум.

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

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

Методы:

1)Если задача  содержит две переменные, то она  решается графически

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

3)Численные методы(условного  градиента; проекции градиента;  штрафных функций) 

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

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

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

Выпуклое  программирование

Найти max(min) функции f(x) на множестве  X

Х - выпуклое множество;

- выпуклая функция на данном  множестве;

- допустимое решение

x* - оптимальное решение, решение при котором f(x) достигает экстремума .

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

Функция Лагранжа:

Если  квадратичная функция, то это задача квадратичного программирования.

Квадратичное  программирование

Квадратичная  форма 

- симметричная матрица с элементами  .

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

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

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

Если главные миноры матрицы  D=½Q положительны, то квадратичная форма положительно определенная. Если , то квадратичная форма положительно полуопределенная.

Если знаки  чередуются, причем , то квадратичная форма отрицательно определенная. Если знаки чередуются ( ) и то квадратичная форма отрицательно полуопределенная.  
 

3.Динамическое программирование. Примеры задач, решаемых методом динамического программирования. Сущность вычислительного метода. 

Раздел математического  программирования, в котором процесс  принятия решения разбивается на этапы.

Постановка  задачи

Рассматривается система S, которая с течением времени может менять состояние. Говорят, что в системе протекает процесс. Процесс является управляемым. Управление – способ воздействия на систему.

Процесс принятия решения можно разбить на n шагов.

Si- состояние системы после i-ого шага.

S0начальное состояние системы (может быть элементом множества начальных состояний ).

Sn - конечное состояние системы (может быть элементом множества конечных состояний ).

Ui- управление на i-ом шаге.

U(U1…Un) - вектор управления.

Под действием  U(U1…Un)  система переходит из S0 в Sn.

С переходом  из S0 в Sn связана заинтересованность с помощью критерия W.

Среди всех возможных  управлений U, переводящих систему из S0 в Sn выбрать то, которое доставляет максимум функции W. 

Методы  решения:

1.Методом прямой прогонки

2.Методом обратной  прогонки

Процесс нахождения решения разбивается да две стадии:

1)условная  оптимизация;

2)безусловная  оптимизация.

На стадии условной оптимизации определяются условные оптимальные выигрыши на данном и всех шагах, и условные оптимальные управления на данном шаге.

Прямая  прогонка: от первого шага к последнему.

Обратная  прогонка: от последнего шага к первому.

На стадии безусловной  оптимизации определяются безусловные  оптимальные управления для каждого  шага

Прямая  прогонка: от последнего шага к первому.

Обратная  прогонка: от первого шага к последнему.

Рассмотрим  метод обратной прогонки

В основе метода лежит принцип оптимальности  Беллмана:

Управление на каждом шаге нужно выбирать так, чтобы  сумма выигрыша на данном шаге и  оптимального выигрыша на всех последующих шагах была максимальна.

Уравнение состояния: Si=Si(Ui,Si-1)  - система перешла в состояние Si из состояния Si-1 под управлением Ui, при этом получен выигрыш fi(Ui,Si-1).

Wi+1(Si) - оптимальный выигрыш на последующих шагах. 
 
 

- выигрыш на этом шаге и  на всех последующих.

Согласно принципу Беллмана управление Ui надо выбрать так, что эта сумма была максимальной.

Условная  оптимизация

  - основное функциональное уравнение.

- функциональное уравнение для  последнего шага.

Безусловная оптимизация

Если начальное  состояние задано, то .

Если начальное  состояние не задано, но сказано, что  оно принадлежит какому-либо множеству, то . 
 

4.Сетевое планирование. Сетевая модель, ее основные элементы. Расчет сетевой модели. Построение календарного графика и распределение ресурсов. 

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

Сетевое планирование включает в себя 3 этапа:

1.Структурное  планирование

Определяются  работы, их продолжительность и взаимосвязь. Строится сетевой график.

2.Календарное  планирование

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

3.Оперативное  управление

Управление работами на основе календарного графика.

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