МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Задача линейного программирования (ЛП) ассоциируется с задачей распределительного типа, в которой требуется распределить ограниченные ресурсы по нескольким видам деятельности. Интерпретация задачи ЛП в этом случае состоит в следующем. Моделируемая ЭИС характеризуется наличием нескольких видов деятельности / (j =

1,.., п), для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы b., (i = 1,.., ш). Интенсивность расходования каждого из ресурсов на каждый из видов деятельности ЭИС известна и равна а... Результативность или ценность каждого /-го вида деятельности ЭИС характеризуется величиной х, при которых оптимизируется общий результат деятельности ЭИС в целом при выполнении ограничений, накладываемых на и

использование ресурсов, т.е. bp i = l,..,w. Структура целевой п /=|

функции v(M)=Sc/v/ отражает вклад каждого вида деятельности ЭИС /=•

в общий результат. При максимизации с. представляет собой «полезность» у-го вида деятельности (ущерб, наносимый конкуренту по бизнесу; предотвращенный ущерб), а в случае минимизации характеризует затраты (потери собственные; расход материальных средств).

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

В формализованном виде задачу ЛП можно представить следующим образом:

определить и* = arg extry(u),

ueU

гае ,у(г/) =/(.*) = ? Vх; > u= I" = I ?a,,x/ (31)

(<, = или >) b(, i - l,..,m; xy> 0}.

Условие неотрицательности, накладываемое на переменные означает, что ни одному виду деятельности ЭИС не может быть приписан отрицательный уровень.

Ограничение типа > нельзя рассматривать как ограничение в буквальном смысле этого слова. Наличие такого неравенства предполагает необходимость обязательного выполнения каких-либо планов, заданий, нормативов.

Математическая формулировка задачи ЛП выглядит следующим образом: необходимо определить значения управляемых переменных х„ доставляющих экстремум целевой функции у (и) на всем множестве стратегий U = {и} и удовлетворяющих всем имеющимся в задаче ограничениям. Этой формулировкой задача ЛП считается поставленной математически, что позволяет осуществлять поиск ее оптимального решения известными математическими методами.

Формальную постановку задачи ЛП (3.1) для удобства можно представить в упрощенном виде:

п »

определить max (или min) (У(х) = Е с}' при ограничениях: Z ауxf (<, = или >) b., i = 1 ,..,/и; х. > 0, /_|

где FF(x) - новое обозначение ЦФ, т.е. 1К(х) = у(и) =Дх).

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >