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

В гл 2 было показано , что правая и левая части ограничений линейной модели могут быть связаны знаками . Кроме того , переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или не иметь ограничения в знаке . Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме , которую назовем стандатрной формой линейных оптимизационных моделей . При стандартной форме линейной модели
1. Все ограничения записываются в виде равенств с неотрицательной правой частью ;
1. Значения всех переменных модели неотрицательны ;
1. Целевая функция подлежит максимизации или минимизации .
Покажем , каким образом любую линейную модель можно привести к стандартной
.

Ограничения

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

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

5X1 + 100X2 0 , в результате чего исходное неравенство обращается в равенство

5X1 + 100X2 + S1 = 1000 , S1 => 0
Если исходное ограничение определяет расход некоторого ресурса , переменную
S1 следует интерпретировать как остаток , или неиспользованную часть , данного ресурса .

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

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

X1 - 2X2 - S2 = 0 , S2 => 0
2. Правую часть равенства всегда можно сделать неотрицательной , умножая оби части на -1 .
Например равенство X1 - 2X2 - S2 = 0 эквивалентно равенству - X1 + 2X2 +
S2 = 0
3. Знак неравенства изменяется на противоположный при умножении обеих частей на -1 .

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

Переменные

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

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

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

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

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

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

Z = X1 + 25X2 эквивалентна минимизации функции

( -Z ) = -X1 - 25X2
Эквивалентность означает , что при одной и той же совокупности ограничений оптимальные значения X1 , X2 , в обоих случаях будут одинаковы . Отличие заключается только в том , что при одинаковых числовых значениях целевых функций их знаки будут противоположны .

Симплекс-метод .

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

Общую идею симплекс-метода можно проиллюстрировать на примере модели , посроенной для нашей задачи . Пространство решений этой задачи представим на рис. 1 . Исходной точкой алгоритма является начало координат ( точка А на рис. 1 ) . Решение , соответствующее этой точке , обычно называют начальным решением . От исходной точки осуществляется переход к некоторой смежной угловой точке .

Выбор каждой последующей экстремальной точки при использовании симплекс-метода определяется следующими двумя правилами .

1. Каждая последующая угловая точка должна быть смежной с предыдущей .

Этот переход осуществляется по границам ( ребрам ) пространства решений .

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



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

Поделитесь этой записью или добавьте в закладки