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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 13: Строка 13:
* ограничения
* ограничения
-
 
+
'''Определение 1'''. Математически задача ЛП --- задача нахождения наибольшего (или наименьшего) значения линейной функции многих переменных при линейных ограничениях типа равенств и/или неравенств, когда на переменные задачи есть (нет) ограничений на знак.
-
\textbf{Определение 1}. Математически задача ЛП --- задача нахождения наибольшего (или наименьшего) значения линейной функции многих переменных при линейных ограничениях типа равенств и/или неравенств, когда на переменные задачи есть (нет) ограничений на знак.
+
Свойство линейности функции предполагает:
Свойство линейности функции предполагает:
-
\begin{enumerate}
 
-
\item  значения левых частей ограничений задачи прямо пропорциональны  значениям переменных
 
-
 
-
\item  аддитивность переменных -- общий вклад всех переменных в значения целевой функции и левых частей неравенств ограничений является прямой суммой вкладов каждой отдельной переменной
 
-
\end{enumerate}
 
 +
* значения левых частей ограничений задачи прямо пропорциональны  значениям переменных
-
\subsection{ Математическая постановка задачи линейного программирования}
+
*  аддитивность переменных -- общий вклад всех переменных в значения целевой функции и левых частей неравенств ограничений является прямой суммой вкладов каждой отдельной переменной
 +
 +
== Математическая постановка задачи линейного программирования ==
Общая задача ЛП максимизации имеет вид:  
Общая задача ЛП максимизации имеет вид:  

Версия 17:11, 1 сентября 2015

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

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

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

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

  • переменные
  • целевую функцию
  • ограничения

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

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


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

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

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

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

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

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