Постановка задачи линейного программирвоания

Задача линейного программирования (ЛП) ассоциирует- ся с задачей распределительного типа, в которой требуется распределить ограниченные ресурсы по нескольким видам деятельности. Интерпретация задачи ЛП в этом случае состо- ит в следующем. Моделируемая экономическая информаци- онная система (ЭИС) характеризуется наличием нескольких видов деятельности j (j = 1, …, n), для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы bi, (i = 1, …, m). Интенсивность расходования каждого из ресурсов на каждый из видов деятельности ЭИС известна и равна aij. Результативность или ценность каждого j-го вида деятельности ЭИС характеризуется величиной cj. Цель пост- роения модели заключается в определении уровней каждого вида деятельности ЭИС xj, при которых оптимизируется об- щий результат деятельности ЭИС в целом при выполнении ограничений,  накладываемых  на  использование  ресурсов,  т.  е.

≤ bi, i = 1, …, m. Структура целевой функции (ЦФ) y(u) отра-

жает вклад каждого вида деятельности ЭИС в общий резуль- тат. При максимизации сj представляет собой “полезность” j-го вида деятельности (ущерб, наносимый конкуренту по бизнесу; предотвращенный ущерб), а в случае минимизации характеризует затраты (потери собственные; расход матери- альных средств).

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

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

определить

где y (u) = f (x) = , U = { u = (x 1, x 2,.,x n) |

(≤, = или ≥) b i, i = 1, …, m; x j > 0 }.

(9.1)

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

Ограничение типа ≥ нельзя рассматривать как ограниче-

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

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

чески, что позволяет осуществлять поиск ее оптимального ре- шения известными математическими методами.

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

определить max (или min) W(x) = при ограничениях: (≤, = или ≥) bi, i = 1, …, m; xj ≥ 0,

где W(x) — новое обозначение ЦФ, т. е. W(x) = y(u) = f(x).

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