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

Материал из Supply Chain Management Encyclopedia

Версия от 17:08, 1 сентября 2015; Zyatchin (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

Определение задачи линейного программирования

При постановке задачи линейного программирования (далее -- ЛП) в первую очередь необходимо понять, что является переменными задачи. Набор всех переменных определяет некоторый план. Для того чтобы говорить об оптимальности выбранного плана, необходимо определиться с критерием оптимальности -- количественной характеристика цели, которую необходимо достичь. Этот критерий будем называть целевой функцией. Как правило, целью оптимизации является поиск такого плана, при котором значение целевой функции достигает максимального или минимального значения. И, наконец, третий объект, который необходимо определить -- система ограничений. Линейная оптимизация всегда проводится в условиях ограниченного изменения переменных. Часто такие ограничения могут быть обусловлены запасами материалов на складе, бюджетом, рыночным спросом и т.д. В результате, для постановки задачи ЛП необходимо определить:

\begin{enumerate} \item переменные

\item целевую функцию

\item ограничения \end{enumerate}

\textbf{Определение 1}. Математически задача ЛП --- задача нахождения наибольшего (или наименьшего) значения линейной функции многих переменных при линейных ограничениях типа равенств и/или неравенств, когда на переменные задачи есть (нет) ограничений на знак.

Свойство линейности функции предполагает:

\begin{enumerate} \item значения левых частей ограничений задачи прямо пропорциональны значениям переменных

\item аддитивность переменных -- общий вклад всех переменных в значения целевой функции и левых частей неравенств ограничений является прямой суммой вкладов каждой отдельной переменной \end{enumerate}


\subsection{ Математическая постановка задачи линейного программирования}

Общая задача ЛП максимизации имеет вид:

\, \max z=\max (c_{1} x_{1} +\ldots +c_{n} x_{n} )

при ограничениях

Личные инструменты
Our Partners