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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
'''English: [http://scm.gsom.spbu.ru/Linear_programming]'''
 +
Линейное программирование -- это раздел более общей теории математического программирования. С помощью методов математического программирования исследуются проблемы принятия решений, которые могут быть математически сформулированы как задачи нахождения максимума (или минимума) нелинейной функции (целевой функции) многих переменных, при заданной системе ограничений на переменные решения.
Линейное программирование -- это раздел более общей теории математического программирования. С помощью методов математического программирования исследуются проблемы принятия решений, которые могут быть математически сформулированы как задачи нахождения максимума (или минимума) нелинейной функции (целевой функции) многих переменных, при заданной системе ограничений на переменные решения.

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

English: [1]

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

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

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

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

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

Определение 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