Задачи целочисленного линейного программирования

Лекция 4. Понятие об оптимизационных моделях и оптимизационных задачах

Способы оптимизации включают, в частности

1. способы математического программирования,

2. способы стохастического программирования,

3. модели и сетевые методы,

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

5. способы многокритериальной оптимизации, и т.д.

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

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

Формулировка задачи ЛП: Выяснить экстремум (т.е. минимум либо максимум) линейной целевой функции

, (1)

при ограничениях

, (2)

. (3)

Функция именуется целевой функцией либо критерием оптимальности.

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

Метод ответа задач линейного программирования разглядим на следующем примере.

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

Предприятие располагает определенным числом трудовых, сырьевых и денег.

Требуется выяснить, какое количество продукции четырех типов П1, П2, П3, П4 необходимо выпустить, для получения максимальной прибыли. Нормы расхода и прибыль от реализации единицы каждого вида продукции, и имеющиеся ресурсы приведены в таблице.

Ресурс П1 П2 П3 П4 наличие ресурса
прибыль
Трудовые ресурсы
Сырье
Финансы

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

— количество производимой продукции типа ( );

— количество располагаемого ресурса вида ( );

норма расхода –го ресурса для выпуска единицы продукции типа ;

— прибыль, приобретаемая от реализации единицы продукции типа .

Так, необходимо максимизировать целевую функцию

при ограничениях

где левая часть воображает выражение для величины требуемого ресурса,
а правая – его количество.

Ответ задачи, к примеру, посредством Поиска ответа Excel, дает оптимальные значения производимого продукта, снабжающие большую прибыль

Задачи целочисленного линейного программирования

При ответе многих задач компоненты вектора малоизвестных выражаются в целых числах (к примеру, при физически цельных объектов — технологических линиях, конторах, инвестиционных проектах, транспортных единицах и т.д.). Эти задачи именуются задачами целочисленного линейного программирования (ЦЛП) иформулируются следующим образом:

при ограничениях

Довольно часто переменные смогут принимать только значения 0 либо 1 (модели бинарного целочисленного линейного программирования), что типично для моделей о назначениях, размещения производственных объектов, управления и производственного планирования инвестиционными сумками.

Разглядим пример задач для того чтобы типа.

Ответ целочисленной задачи линейного программирования способом Гомори


Также читать:

Понравилась статья? Поделиться с друзьями: