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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая страница: «Линейное программирование -- это раздел более общей теории математического программирова...»)
 
(7 промежуточных версий не показаны.)
Строка 1: Строка 1:
 +
'''English: [http://scm.gsom.spbu.ru/Linear_programming Linear programming]'''
 +
Линейное программирование -- это раздел более общей теории математического программирования. С помощью методов математического программирования исследуются проблемы принятия решений, которые могут быть математически сформулированы как задачи нахождения максимума (или минимума) нелинейной функции (целевой функции) многих переменных, при заданной системе ограничений на переменные решения.
Линейное программирование -- это раздел более общей теории математического программирования. С помощью методов математического программирования исследуются проблемы принятия решений, которые могут быть математически сформулированы как задачи нахождения максимума (или минимума) нелинейной функции (целевой функции) многих переменных, при заданной системе ограничений на переменные решения.
Строка 7: Строка 9:
При постановке задачи линейного программирования (далее -- ЛП) в первую очередь необходимо понять, что является ''переменными'' задачи. Набор всех переменных определяет некоторый план. Для того чтобы говорить об оптимальности выбранного плана, необходимо определиться с критерием оптимальности -- количественной характеристика цели, которую необходимо достичь. Этот критерий будем называть ''целевой функцией''. Как правило, целью оптимизации является поиск такого плана, при котором значение целевой функции достигает максимального или минимального значения. И, наконец, третий объект, который необходимо определить -- система  ограничений. Линейная оптимизация всегда проводится в условиях ограниченного изменения переменных. Часто такие ограничения могут быть обусловлены запасами материалов на складе, бюджетом, рыночным спросом и т.д. В результате, для постановки задачи ЛП необходимо определить:
При постановке задачи линейного программирования (далее -- ЛП) в первую очередь необходимо понять, что является ''переменными'' задачи. Набор всех переменных определяет некоторый план. Для того чтобы говорить об оптимальности выбранного плана, необходимо определиться с критерием оптимальности -- количественной характеристика цели, которую необходимо достичь. Этот критерий будем называть ''целевой функцией''. Как правило, целью оптимизации является поиск такого плана, при котором значение целевой функции достигает максимального или минимального значения. И, наконец, третий объект, который необходимо определить -- система  ограничений. Линейная оптимизация всегда проводится в условиях ограниченного изменения переменных. Часто такие ограничения могут быть обусловлены запасами материалов на складе, бюджетом, рыночным спросом и т.д. В результате, для постановки задачи ЛП необходимо определить:
-
\begin{enumerate}
+
* переменные
-
\item переменные
+
-
\item целевую функцию
+
* целевую функцию
-
\item  ограничения
+
* ограничения
-
\end{enumerate}
+
-
\textbf{Определение 1}. Математически задача ЛП --- задача нахождения наибольшего (или наименьшего) значения линейной функции многих переменных при линейных ограничениях типа равенств и/или неравенств, когда на переменные задачи есть (нет) ограничений на знак.
+
'''Определение 1'''. Математически задача ЛП --- задача нахождения наибольшего (или наименьшего) значения линейной функции многих переменных при линейных ограничениях типа равенств и/или неравенств, когда на переменные задачи есть (нет) ограничений на знак.
Свойство линейности функции предполагает:
Свойство линейности функции предполагает:
-
\begin{enumerate}
+
* значения левых частей ограничений задачи прямо пропорциональны  значениям переменных
-
\item  значения левых частей ограничений задачи прямо пропорциональны  значениям переменных
+
-
\item аддитивность переменных -- общий вклад всех переменных в значения целевой функции и левых частей неравенств ограничений является прямой суммой вкладов каждой отдельной переменной
+
* аддитивность переменных -- общий вклад всех переменных в значения целевой функции и левых частей неравенств ограничений является прямой суммой вкладов каждой отдельной переменной
-
\end{enumerate}
+
-
 
+
== Математическая постановка задачи линейного программирования ==
-
 
+
-
\subsection{ Математическая постановка задачи линейного программирования}
+
Общая задача ЛП максимизации имеет вид:  
Общая задача ЛП максимизации имеет вид:  
Строка 33: Строка 30:
при ограничениях
при ограничениях
 +
 +
<math>\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} \le b_{i} ,\, \, \, \, i=1,2,\ldots ,r} \\ {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=r+1,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,r,\, \, \, \, r\le n} \end{array}\right.</math>
 +
 +
здесь
 +
 +
<math>\,x_{j} </math>  -- искомые переменные,
 +
 +
<math>\,z=c_{1} x_{1} +\ldots +c_{n} x_{n} </math>  -- целевая функция,
 +
 +
<math>\,c_{j} ,\, \, a_{ij} ,\, \, b_{i} </math>  -- заданные параметры задачи.
 +
 +
Общая задача ЛП минимизации имеет вид:
 +
 +
<math>\,\min z=\min (c_{1} x_{1} +\ldots +c_{n} x_{n} )</math> 
 +
 +
при ограничениях
 +
 +
<math>\,\left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} \ge b_{i} ,\, \, \, \, i=1,2,\ldots ,r} \\ {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=r+1,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,r,\, \, \, r\le n} \end{array}\right. </math>
 +
 +
Для задач линейного программирования рассматривают их специальные виды: стандартную и каноническую форму.
 +
 +
== Каноническая форма задачи линейного программирования ==
 +
 +
Для канонической формы записи задачи ЛП выполнены следующие требования:
 +
 +
*  Все ограничения являются равенствами
 +
 +
*  На все переменные наложено ограничение на знак: <math>\,\ge 0</math>
 +
 +
Каноническая форма записи задачи максимизации:
 +
 +
<math>\, \max z=\max (c_{1} x_{1} +\ldots +c_{n} x_{n} )</math> 
 +
 +
<math>\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=1,2,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,n} \end{array}\right. </math> 
 +
 +
Каноническая форма записи задачи минимизации:
 +
 +
<math>\, \min z=\min (c_{1} x_{1} +\ldots +c_{n} x_{n} )</math>
 +
 +
<math>\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=1,2,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,n} \end{array}\right. </math> 
 +
 +
Любую задачу ЛП в общем виде с помощью элементарных преобразований можно свести к любой из специальных форм.
 +
 +
Введем обозначение <math>\, x=(x_{1} ,x_{2} ,\ldots ,x_{n} )</math> . Задача ЛП состоит в поиске таких значений <math>\, x_{1}^{*} ,x_{2}^{*} ,\ldots ,x_{n}^{*} </math> , что
 +
 +
<math>\, c_{1} x_{1}^{*} +c_{2} x_{2}^{*} +\ldots +c_{n} x_{n}^{*} =\mathop{\max }\limits_{x\in M} \left(c_{1} x_{1}^{} +c_{2} x_{2}^{} +\ldots +c_{n} x_{n}^{} \right),</math>
 +
 +
где <math>\, M</math> -- множество значений <math>\, x</math> , удовлетворяющих системе ограничений задачи ЛП.
 +
 +
'''Определение 2'''. Набор <math>\, x=(x_{1} ,x_{2} ,\ldots ,x_{n} )</math> , удовлетворяющий всем ограничениям задачи ЛП, называется допустимым решением задачи ЛП. Множество всех допустимых решений задачи ЛП обозначим через <math>\, M</math> .
 +
 +
'''Определение 3'''. Допустимое решение <math>\, x^{*} =(x_{1}^{*} ,x_{2}^{*} ,\ldots ,x_{n}^{*} )</math> задачи ЛП, на котором целевая функция достигает наибольшее (наименьшее) значение, называется оптимальным решением задачи ЛП.
 +
 +
'''Определение 4'''. Число <math>\, z^{*} =c_{1} x_{1}^{*} +c_{2} x_{2}^{*} +\ldots +c_{n} x_{n}^{*} </math> называется значением задачи ЛП.
 +
 +
'''Определение 5'''. Решить задачу ЛП -- значит найти оптимальное решение и значение задачи ЛП.

Текущая версия на 17:41, 1 сентября 2015

English: Linear programming

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

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

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

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

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

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

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

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

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

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

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

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

\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} \le b_{i} ,\, \, \, \, i=1,2,\ldots ,r} \\ {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=r+1,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,r,\, \, \, \, r\le n} \end{array}\right.

здесь

\,x_{j} -- искомые переменные,

\,z=c_{1} x_{1} +\ldots +c_{n} x_{n} -- целевая функция,

\,c_{j} ,\, \, a_{ij} ,\, \, b_{i} -- заданные параметры задачи.

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

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

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

\,\left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} \ge b_{i} ,\, \, \, \, i=1,2,\ldots ,r} \\ {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=r+1,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,r,\, \, \, r\le n} \end{array}\right.

Для задач линейного программирования рассматривают их специальные виды: стандартную и каноническую форму.

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

Для канонической формы записи задачи ЛП выполнены следующие требования:

  • Все ограничения являются равенствами
  • На все переменные наложено ограничение на знак: \,\ge 0

Каноническая форма записи задачи максимизации:

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

\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=1,2,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,n} \end{array}\right.

Каноническая форма записи задачи минимизации:

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

\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=1,2,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,n} \end{array}\right.

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

Введем обозначение \, x=(x_{1} ,x_{2} ,\ldots ,x_{n} ) . Задача ЛП состоит в поиске таких значений \, x_{1}^{*} ,x_{2}^{*} ,\ldots ,x_{n}^{*} , что

\, c_{1} x_{1}^{*} +c_{2} x_{2}^{*} +\ldots +c_{n} x_{n}^{*} =\mathop{\max }\limits_{x\in M} \left(c_{1} x_{1}^{} +c_{2} x_{2}^{} +\ldots +c_{n} x_{n}^{} \right),

где \, M -- множество значений \, x , удовлетворяющих системе ограничений задачи ЛП.

Определение 2. Набор \, x=(x_{1} ,x_{2} ,\ldots ,x_{n} ) , удовлетворяющий всем ограничениям задачи ЛП, называется допустимым решением задачи ЛП. Множество всех допустимых решений задачи ЛП обозначим через \, M .

Определение 3. Допустимое решение \, x^{*} =(x_{1}^{*} ,x_{2}^{*} ,\ldots ,x_{n}^{*} ) задачи ЛП, на котором целевая функция достигает наибольшее (наименьшее) значение, называется оптимальным решением задачи ЛП.

Определение 4. Число \, z^{*} =c_{1} x_{1}^{*} +c_{2} x_{2}^{*} +\ldots +c_{n} x_{n}^{*} называется значением задачи ЛП.

Определение 5. Решить задачу ЛП -- значит найти оптимальное решение и значение задачи ЛП.

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