Реферат: Математические методы и языки программирования: симплекс метод

Переход ко второй итерации:

Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.

Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.

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

На пересечении строки и столбца находится разрешающий элемент.

На этом этапе осуществляется к переходу к последующим итерациям.

Переход к итерациям:

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

2. Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент.

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

4. Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.

5. Остальные элементы переносятся по формуле:

Метод искусственного базиса.

(Вторая симплекс таблица)

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

1. Построение искусственного базиса и оптимизация функции суммы искусственных переменных, т.е. F0=Y1+Y2+…+Yn = 0 (Fmin). Если при этом F0=0, то искусственный базис мы вывели из состава переменных, переходим ко второй фазе – решаем задачу по первой симплекс таблице с действительными переменными. Если же F00, т.е. искусственный базис не выведен из состава переменных – ОЗЛП решений не имеет.

2. Решение преобразованной системы ограничений с заданной целевой функцией и действительными переменными. При этом столбцами искусственных переменных в симплекс методе пренебрегаем.

Замечания:

1. При решении задач на max с искусственным базисом следует переходить к решению на min, меняя лишь только целевую функцию:

Fmax = - Fmin.

2. При решении ОЗЛП с искусственным базисом особое внимание следует обратить на вычисление элементов индексных строк.

a) Для столбцов X вычисление элементов идет по формулам:

j =  qij.

 yi = y1+y2+…+yR.

Hi=F0.

Примечание: только для строк Y.

б) Для столбцов Y работает старая формула:

j =  ciqij-cj.

1. СХЕМА АЛГОРИТМА И ЕЕ ОПИСАНИЕ

1. Начало программы