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

Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида^[3]:

Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)

,

.

Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства^[4]:

,

 

Модель не полностью описывает объект вследствие:

1)ресурсы могут быть частично заменяемы

2)Затраты не строго пропорциональны, так как существуют постоянные затраты связанные с объемом производства.

3)Цена продукции может зависеть от объема реализации.

 

Однако данным методом можно решить ряд задач:

1)Транспортная задача

2)Задача о смесях. Приобретение на рынке некоторых смесей с целью получения нужного сосотава.

3)Создание запасов на складе

4)Задача об использовании производственных мощностей.

Нелинейное программирование (NLP, англ. N on L inear P rogramming) — случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.

Задача нелинейного программирования ставится как задача нахождения оптимума определённой целевой функции при выполнении условий

где — параметры, — ограничения, — количество параметров, — количество ограничений.

Решение задач НЛПР связано с трудностями:

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

2)Наличие ограничений приводит к необходимости решения задачи и поиску локального экстремума.

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

4) НЛП используются гораздо реже, чем ЛП

 

 

Динамическое программирование применяется при решении задач оптимизации динамических систем, меняющихся в течении времени эволюции, широко применяются при решении задач управления запасами/календарного планирования.

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

Задачи динамического программирования предполагают наличие опр-х этапов при условии: оптимальные решения отдельных шагов создают общее оптимальное решение.

н/р: задача оптимального расхода топлива при наборе высоты

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

Число на осях определяет расход топлива в сек.

Для многих случаев справедлива модель формулы

 

Особенности модели динамического программирования:

1)Задачи интерпретируются как пошаговый процесс управления

2)Целевая функция = сума целевых функций каждого шага

3)выбор управления на R-ом шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги.

4)Состояние Sr после R-го шага управления зависит только от предшествующего шага Sr-1 и управления Xr (Отсутствие последствия).

5) На каждом шаге управления Xr зависит от конкретного числа управляющих переменных, а Sr от конечного числа параметров.

 

Принцип оптимальности впервые был сформулирован Р. Беллманом в 1953 г. Каково бы ни было состояние s системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование — процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.