Общий вид моделей линейного программирования:
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).
Одной из разновидностей моделей линейного программирования являются целочисленные модели: одна или несколько переменных по смыслу задачи могут быть только целыми числами и округление неправомерно (рабочие, станки и т. п.). Используется метод отсечения (Гомори) и метод ветвей и границ.
Поможем написать любую работу на аналогичную тему