Модуль 1. Лекция 2. (2 часа)

Тема 2. Классификация задач мп. Постановка задачи линейного программирования. Различные формы записи моделей лп.

2.1. Классификация задач МП.

2.2. Постановка задачи ЛП.

2.3. Формы записи моделей ЛП.

1. Классификация задач мп.

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

В МП принято среди детерминированных задач традиционно выделять следующие:

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

2. Целочисленное программирование (ЦП). В этом классе задач часть или все переменные должны удовлетворять требованию целочисленности.

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

4. Нелинейное программирование (НП). В задачах этого класса нелинейны целевая функция и (или) ограничения.

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

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

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

• взаимозаменяемость ресурсов и многовариантность их использования для достижения цели.

Типичными примерами применения модели линейного программирования являются следующие:

• укрупненное планирование производства (составление графиков производства, минимизирующих общие издержки в связи с изменением ставки процента);

• планирование ассортимента изделий (определение оптимальной структуры производства продуктов питания для человека);

• маршрутизация производства изделий (определение оптимального технологического маршрута изготовления изделия),

• регулирование запасов (определение оптимального сочетания проектов на складе);

• календарное планирование производства (составление календарных планов, минимизирующих издержки с учетом расходов на содержание запасов, оплату сверхурочной работы и заказов на стороне);

• планирование распределения грузов и др