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

Общий вид моделей линейного программирования:

F(X) = c1*x1 + c2*x2 + … + cN*xN => max/min – линейная целевая функция

a11*x1 + a12*x2 + … + a1N*xN <= b1 - система линейных ограничений

a21*x1 + a22*x2 + … + a2N*xN >= b2

…………………………………………………………………………………………

aN1*x1 + aN2*x2 + … + aNN*xN = bN

x1, x2, …, xN >= 0

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

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

При решении данных задач используется симплекс-метод и его модификации, а также специализированные методы решения транспортных задач. Симплекс-метод разработан независимо американцем Дж. Данцигом (1949) и советским математиком Леонидом Витальевичем Канторовичем (1939).

Одной из разновидностей моделей линейного программирования являются целочисленные модели: одна или несколько переменных по смыслу задачи могут быть только целыми числами и округление неправомерно (рабочие, станки и т. п.). Используется метод отсечения (Гомори) и метод ветвей и границ.

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

Либо целевая функция, либо система ограничений, либо они обе нелинейны. Используются метод множителей Лагранжа, квадратичное программирование и др.

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

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