Сделай Сам Свою Работу на 5

Матричная форма замены базиса





Нетрудно видеть, что формулы (8.14), (8.15) являются отражением жорданова исключения переменной в системе линейных уравнений. Это позволяет формализовать процедуру замены базиса в матричной форме. Матричное решение может быть представлено следующей структурой

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

представляется только через независимые переменные .

После определения варьируемой независимой переменной формируется столбец , анализ которого позволяет выделить выводимую из базиса переменную . Производится замена столбцов β матрицы Е и α матрицы , а также обмен переменных в строках и (правая часть первой структуры). Далее выполняется одновременное преобразование (жорданово исключение) объединенной матрицы так, чтобы в левой части образовалась единичная матрица (вторая часть структуры). Промежуточная строка и результирующая получаются матричными умножением и вычитанием указанных компонент.

Очередная варьируемая независимая переменная, как и на первом шаге, определяется по знаку и величине компонент вектора ,.Если всекомпонентыположительны, то решение найдено. При этом . Если имеется отрицательная компонента, - производится новый шаг расчетного процесса.



Конечность алгоритма

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

Рис. 8.3. Блок – схема алгоритма  

,

где m – ранг матрицы А линейных ограничений (число столбцов больше числа строк), .

Обычно симплекс–метод сходится за 3m шагов. Блоксхема симплекс–метода представлена на рис. 8.3

 

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

Требуется найти вектор переменных, минимизирующий линейную функцию

(8.16)

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

(8.17)

Нетрудно видеть, что в системе линейных уравнений переменные достаточно просто выражаются через . При этом при все компоненты вектора положительны, т.е. определено (первое) допустимое базисное решение:



.

Замена переменных

Выражаем целевую функцию через независимые переменные

(8.18)

Для первого базисного решения Ф=-10.

Анализ коэффициентов целевой функции показывает, что для уменьшения Ф целесообразно снять с нуля переменную (отрицательный коэффициент). Ищем переменную, которую следует вывести из базиса. Для этого выписываем систему ограничений (8.17) с учетом того, что .

Вектор . При увеличении на 0,5 переменная становится равной нулю. Эта переменная выводится из базиса, в то время как переходит в состав базиса ( ).

Разрешим третье уравнение системы ограничений относительно

и подставим данное выражение в первое и второе уравнения системы ограничений:

После приведения подобных членов получаем систему ограничений в новом виде:

(8.19)

Новое допустимое базисное решение (х3, х5 – независимые переменные)

.

Выражаем целевую функцию через новые независимые переменные:

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

.

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

Вектор . Переменная переходит через ноль при . Ее и следует вывести из базиса: ( ).

Из второго уравнения системы ограничений можно получит представление переменной



.

Данное выражение подставляется в первое и третье уравнения системы (8.19):

;

.

Новая форма системы ограничений:

Новое допустимое базисное решение

.

Выражаем целевую функцию через независимые переменные:

или

Отсутствие отрицательных коэффициентов показывает, что достигнуто оптимальное значение.

.

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.