Структура задач математического программирования

Всякая ОЭМ включает в себя:

1) набор вариантов (это входные переменные оптимизационной модели);

2) ограничения, определяющие область допустимых значений (ОДЗ);

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

 

(X₁, X₂,.., X_n)-набор вариантов

g_j (x)> A_j

j=1,.., m _l

виды ограничений

g_j(x)< A_j

j=m _l+1,.., m_k

g_j(x)=A_j

j=m_k+1,.., m_p

f(x) → min (max) – целевая функция, которая является математическим выражением критерия относительности

Математическое программирование (МП) - наука о методах решения оптимизационных задач.

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

1. Линейное программирование. Если в постановке задачи все функции f(x), g(x) являются линейными, тогда она является задачей линейного программирования. Если хотя бы одна из указанных функций является нелинейной – рассматриваемая задача является задачей нелинейного программирования.

2. Задачи целочисленного программирования (ЦП)-неизвестные могут принимать только целые значения (0, 1, 2 и т.д.)

Если в задачах целочисленного программирования переменные могут принимать только два значения (0 или 1), то такие задачи называют моделями МП с булевыми переменными.

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

4. Если в целевой функции или в функции, определяющей ОДЗ, содержатся случайные величины, то перед нами задача стахостического программирования (СП).

5. Задачи, процесс нахождения решения которых является многоэтапным - это задачи динамического программирования (ДП).

Линейное программирование (ЛП)

Задачи линейного программирования наиболее широко применяются на практике, т.к. математические модели значительного числа экономиических систем в действительности являются линейными. При этом методология решения задач ЛП наиболее разработана.

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

Типичные примеры задач линейного программирования:

1. Маршрутизация изделий производства,

2. Управление технологическим процессом,

3. Планирование ассортимента продукции,

4. Укрупненное планирование производства,

5. Регулирование запасов,

6. Календарное планирование производства,

7. Планирование и распределение продукции,

8. Разделение и кооперация труда.

Чаще всего для решения задач ЛП используется графический метод и симплекс-метод.

Целочисленное программирование (ЦП)

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

Стохастическое программирование (СП)

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

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

Нелинейное программирование (НП)

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

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

Еще один распространенный метод решения задач НП - это градиентный метод.

Динамическое программирование (ДП)

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

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

Такие многоэтапные задачи являются задачами динамического программирования.

Типичные примеры задач динамического программирования.

1. Распределение ресурсов (капитальные вложения) между возможными направлениями их использования (по объему и по времени).

2. Планирование развития системы образования.

3. Управление запасами, т.е. установление моментов пополнения размеров запасов.

4. Календарное планирование производства.

5. Разработка плана текущего ремонта оборудования.

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

Задачи динамического программирования решаются за 2 цикла:

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

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

2 цикл: повторяется вся последовательность шагов, но теперь уже от начального к конечному этапу: состояние системы перед шагом известно и для него в качестве оптимального берется найденное на предыдущем этапе условно-оптимальное решение, что позволяет определить состояние системы на начало второго этапа и так вплоть до конечного этапа. Рассмотренный принцип решения задач динамического программирования носит название принципа Беллмана.