Лекция 4. Понятие об оптимизационных задачах и оптимизационных моделях
Методы оптимизации включают, в частности
1. методы математического программирования,
2. методы стохастического программирования,
3. сетевые методы и модели,
4. методы динамического программирования
5. методы многокритериальной оптимизации, и т.д.
Здесь мы ограничимся методами решения линейных оптимизационных задач.
Задачи линейного программирования (ЛП) (или задачи линейной оптимизации) содержат лишь линейные зависимости целевой функции и ограничений от переменных. Они широко используются в практике принятия управленческих решений.
Формулировка задачи ЛП: Определить экстремум (т.е. минимум или максимум) линейной целевой функции
, (1)
при ограничениях
, (2)
. (3)
Функция 
называется целевой функцией или критерием оптимальности.
Вектор неизвестных 
, удовлетворяющих условию данной задачи, называется допустимым решением (или допустимым планом). Допустимое решение 
называется оптимальным, если оно оптимизирует (т.е. максимизирует или, в зависимости от условий задачи, - минимизирует) значение целевой функции.
Алгоритм решения задач линейного программирования рассмотрим на следующем примере.
Примеры оптимизационных задач в экономике и управлении. Построение модели оптимального распределения ресурсов
Предприятие располагает определенным количеством трудовых, сырьевых и финансовых ресурсов.
Требуется определить, какое количество продукции четырех типов П1, П2, П3, П4 нужно выпустить, чтобы получить максимальную прибыль. Нормы расхода и прибыль от реализации единицы каждого вида продукции, а также имеющиеся ресурсы приведены в таблице.
| Ресурс | П1 | П2 | П3 | П4 | наличие ресурса |
| прибыль | - | ||||
| Трудовые ресурсы | |||||
| Сырье | |||||
| Финансы |
Введем обозначения:
- количество выпускаемой продукции типа 
(
);
- количество располагаемого ресурса вида 
(
);
- норма расхода 
–го ресурса для выпуска единицы продукции типа ;
- прибыль, получаемая от реализации единицы продукции типа 
.
Таким образом, нужно максимизировать целевую функцию
при ограничениях
где левая часть представляет выражение для величины требуемого ресурса,
а правая – его количество.
Решение задачи, например, с помощью Поиска решения Excel, дает оптимальные значения выпускаемого продукта, обеспечивающие максимальную прибыль
Задачи целочисленного линейного программирования
При решении многих задач компоненты вектора неизвестных 
выражаются в целых числах (например, в случае физически цельных объектов - технологических линиях, офисах, инвестиционных проектах, транспортных единицах и т.д.). Эти задачи называются задачами целочисленного линейного программирования (ЦЛП) иформулируются следующим образом:
при ограничениях
Часто переменные могут принимать лишь значения 0 или 1 (модели двоичного целочисленного линейного программирования), что типично для моделей о назначениях, размещения производственных объектов, производственного планирования и управления инвестиционными портфелями.
Рассмотрим пример задач такого типа.