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




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

Методы оптимизации включают, в частности

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

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

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

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

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

 

 

Здесь мы ограничимся методами решения линейных оптимизационных задач.

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

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

, (1)

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

, (2)

. (3)

 

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

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

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

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

 

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

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

 

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

 

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

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

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

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

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

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

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

 

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

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

 

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

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

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

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

Рассмотрим пример задач такого типа.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: