на главную страницу
визитка
темы

О принятии решений

Литература
1. Дж. Данциг. Линейное программирование, его обобщения и применения.

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

   1.

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

   2.

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

   3.

   Индексом j=1, 2, ...,N обозначается j-ый тип технологического процесса, х_j - его объём, или интенсивность, причём, обычно  х_j ≥ 0

   4.

   Взаимозависимости между различными техпроцессами возникают потому, что все практические задачи программирования описываются ограничениями на ресурсы того или иного рода. Ограниченными могут быть сырьё, рабочая сила, деньги и т.п.. Все они обозначаются общим термином ингредиент и обозначаются индексом i (i = 1,2,...,M) В работах по ЛП количество ингредиента, потребляемого технологическим процессом, предполагается пропорциональным его интенсивности; если ингредиент не потребляется, но производится, то снова предполагается, что он пропорционален интенсивности этого процесса. Коэффициент пропорциональности обозначается через а_i,j. Знак при а_i,j зависит от того, потребляется ингредиент или производится. Соглашение о знаке состоит в том, что коэффициент имеет знак (+), если потребляется (чёрным ящиком, принадлежит его входу), и знак (-(, если производится (принадлежит выходу чёрного ящика)
      Параметр b_i, если он положителен, обозначает количество i-го ингредиента, поступающего в систему из внешних (экзогенных) источников. Если эта величина отрицательна, то она обозначает количество, которое должно быть произведено системой. Зависимости между величинами х_j выражаются в виде системы М линейных уравнений, причём, i-ое уравнение полностью учитывает i-ый ингредиент
      В общем случае система М линейных уравнений записывается в виде:
   a₁₁x₁ + a₁₂x₂ + ...+ a_1Nx_M = b₁
   a₂₁x₁ + a₂₂x₂ + ...+ a_2Nx_M = b₂
   ...........
   a_M1x₁ + a_M2x₂ + ...+ a_MNx_M = b_M, где x_j≥0, j=1,2,...,N.
      Любая система значений х_j удовлетворяющая этим соотношениям, называется допустимым решением, так как соответствующий план возможен.

   5.

   Стоимость может измеряться в доллларах, числом вовлеченных в процесс людей или количеством использованного дефицитного ресурса. В ЛП предполагается, что общая стоимость, обозначаемая через z, есть линейная функция интенсивностей техпроцессов:
   с₁х₁+ с₂х₂+...+с_Nх_N = z
       Линейная функция z называется целевой функцией (или формой)
      Т.о., в качестве стандартной формы ЛП принимается определение решения системы линейных уравнений в неотрицательных числах, которая минимизирует линейную форму.

   6.

   Двойственная задача ЛП
       С каждой задачей ЛП,(её можно назвать прямой задачей), связана противоположная её, называемая двойственной Если целью прямой задачи является минимизация, то двойственной - максимизация. Двойственная задача возникает как средство проверки прямой задачи..