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

Z = X1 + 25X2

эквивалентна минимизации функции

( -Z ) = -X1 25X2

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

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

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

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

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

Каждая последующая угловая точка должна быть смежной с предыдущей. Этот переход осуществляется по границам ( ребрам ) пространства решений.

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

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

Определим пространство решений и угловые точки агебраически. Требуемые соотнощшения устанавливаются из указанного в таблице соответствия геометрических и алгебраических определений.

Геометрическое определение	Алгебраическое определение  ( симплекс метод )
Пространство решений	Ограничения модели стандартной формы
Угловые точки	Базисное решение задачи в стандартной форме

Представление пространства решений стандартной задачи линейного программирования.

Линейная модель, построенная для нашей задачи и приведенная к стандартной форме, имеет следующий вид :

Максимизировать

  Z = X1 + 25X2 + 0S1 + 0S2

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

5X1 + 100X2 + S1  = 1000

X1 + 2X2   + S2 = 0

X1=>0, X2=>0, S1=>0, S2=>0

Каждую точку пространства решений данной задачи, представленную на рис.1, можно определить с помощью переменных X1, X2, S1 и S2, фигурирующими в модели стандартной формы. При S1 = 0 и S2 = 0 ограничения модели эквивалентны равенствам, которые представляются соответствующими ребрами пространства решений. Увеличение переменных S1 и S2 будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область. Переменные X1, X2, S1 и S2, ассоциированные с экстремальными точками А, В, и С можн о упорядочить, исходя из того, какое значение ( нулевое и ли ненулевое ) имеет данная переменная в экстремальной точке.

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





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