Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Значения всех переменных модели неотрицательны ;

Целевая функция подлежит максимизации или минимизации.

Покажем, каким образом любую линейную модель можно привести к стандартной.

Ограничения

Исходное ограничение, записанное в виде неравенства типа <= ( =>),

можно представить в виде равенства, прибавляя остаточную переменную к левой части ограничения ( вычитая избыточную переменную из левой части ).

Например, в левую часть исходного ограничения

5X1 + 100X2 <= 1000

вводистя остаточная переменная S1 > 0, в результате чего исходное неравенство обращается в равенство

5X1 + 100X2 + S1 = 1000, S1 => 0

Если исходное ограничение определяет расход некоторого ресурса, переменную S1 следует интерпретировать как остаток, или неиспользованную часть, данного ресурса.

Рассмотрим исходное ограничение другого типа :

X1 2X2 => 0

Так как левая часть этого ограничения не может быть меньше правой, для обращения исходного неравенства в равенство вычтем из его левой части избыточную переменную S2 > 0. В результате получим

X1 2X2 S2 = 0, S2 => 0

Правую часть равенства всегда можно сделать неотрицательной, умножая оби части на -1.

Например равенство X1 2X2 S2 = 0 эквивалентно равенству X1 + 2X2 + S2 = 0

Знак неравенства изменяется на противоположный при умножении обеих частей на -1.

Например можно вместо 2 < 4 записать 2 > 4, неравенство X1 2X2 <= 0 заменить на X1 + 2X2 => 0

Переменные

Любую переменную Yi, не имеющую ограничение в знаке, можно представить как разность двух неотрицательных переменных :

Yi=Yi’-Yi’’, где Yi’,Yi’’=>0.

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

Обычно находят решение задачи ЛП, в котором фигурируют переменные Yi’ и Yi’’, а затем с помощью обратной подстановки определяют величину Yi. Важная особенность переменных Yi’ и Yi’’ состоит в том, что при любом допустимом решении только одна из этих переменных может принимать положительное значение, т.е. если Yi’>0, то Yi’’=0, и наоборот. Это позволяет рассматривать Yi’ как остаточную переменную, а Yi’’ как избыточную переменную, причем лишь одна из этих переменных может принимать положительное значение. Указанная закономерность широко используется в целевом программировании и фактически является предпосылкой для использования соответсвующих преобразований в задаче 2.30

Целевая функция

Целевая функция линейной оптимизационной модели, представлена в стандартной форме, может подлежать как максимизации, так и минимизации. В некоторых случаях оказывается полезным изменить исходную целевую функцию.

Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот. Например максимизация функции

Рекомендуем скачать другие рефераты по теме: мировая война реферат, конспект урока 3.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата