АЛГОРИТМ ПРЕОБРАЗОВАНИЯ ЭЛЕМЕНТОВ СИМПЛЕКСНОЙ ТАБЛИЦЫ

Пусть целевая функция (3.5) и система ограничений (3.6) разрешены относительно базисных переменных через свободные.

Введём дополнительные обозначения:

xi – базисные переменные ; yi – свободные переменные; вместо aij = Sij; вместо bi = Si0; cj = Sm+1, j

Алгоритм пересчёта элементов симплексной таблицы при замене базисной переменной xr на свободную yk.

- для разрешающего элемента (3.12)

, - для разрешающий строки (3.13)

, - для разрешающего столбца (3.14)

, - для всех оставшихся элементов (3.15).

Строка r, соответствующая переменной, выводимой из базиса, называется разрешающей строкой.

Столбец k, соответствующий переменной вводимой в базис называется разрешающим.

Элемент rk называется разрешающим элементом.

Алгоритм поиска симплекс метода состоит из 2-х этапов:

1. поиск опорного решения (А ® С)

2. поиск оптимального решения (В ® С)

А – алгоритм выбора разрешающего элемента при поиске опорного.

В – алгоритм выбора разрешающего элемента при поиске оптимального решения.

С – коэффициент пересчёта коэффициентов симплексной таблицы по соотношению (9).

АЛГОРИТМ ВЫБОРА РАЗРЕШАЮЩЕГО ЭЛЕМЕНТА ПРИ ПОИСКЕ ОПОРНОГО РЕШЕНИЯ

Проводим анализ столбца свободных членов. Если все свободные члены являются положительными, то решение является опорным. Пусть какой-то элемент из столбца свободных членов имеет отрицательное значение, тогда проводим анализ элементов этой строки: если среди остальных элементов строки нет отрицательных значений, то система несовместна и не имеет решения. За разрешающий выбирается столбец с наибольшим по модулю отрицательным значением в соответствующей строке, который будем обозначать “k”.

Разрешающая строка определяется по дополнительному соотношению:

(3.16),

где Si0 – свободный член i-ой строки;

Sik – коэффициент разрешающего столбца;

В качестве разрешающей выбирается та строка, которая имеет минимальное положительное a. Разрешающую строку будем обозначать как “r”.








Дата добавления: 2015-12-22; просмотров: 1623; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2022 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.