Предыдущая страница реферата | 8  9  10  11  12  13  14  15  16  17  18 | Следующая страница реферата

                 (5.5)

, где .

где М – сколь угодно большая положительная величина.

Как и в L-задаче, добавление только одной искусственной переменной  (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А4, А5, А6, А7.

6. Решение М-задачи II алгоритмом симплекс-метода

Описание II алгоритма

Второй алгоритм (или метод обратной матрицы) симплекс метода основан на ином способе вычисления оценок  векторов условий Аj, чем в первом алгоритме.

Рассматривается задача линейного программирования в канонической форме (2.1) - (2.3). Пусть Х – опорный план с базисом . Все параметры, необходимые для оценки плана на оптимальность и перехода к лучшему плану, можно получить, преобразовывая от шага к шагу элементы матрицы .

Действительно, зная обратную матрицу , можно получить базисные составляющие опорного плана:

и вычислить оценки векторов условий относительно текущего базиса

,                                                                      (6.1)

предварительно определив вектор-строку  по формуле

или

.                                                                  (6.2)

Здесь - вектор-строка из коэффициентов линейной формы, отвечающих базисным переменным.

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

.

Как и в I алгоритме, вектор, подлежащий исключению из базиса, определяется величиной

.

Таким образом при втором алгоритме на каждом шаге запоминаются базисные компоненты , обратная матрица , значение линейной формы F(X) и вектор Y, соответствующие текущему опорному плану Х. Элементы столбцов матрицы  удобно рассматривать как коэффициенты  разложения единичных векторов  по векторам базиса. Рекуррентные формулы, связывающие параметры двух последовательных итераций

;                                                                                             (6.3)

.                     (6.3)

Здесь

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





Предыдущая страница реферата | 8  9  10  11  12  13  14  15  16  17  18 | Следующая страница реферата