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


Под конечностью любого итеративного алгоритма решения математической задачи понимается возможность получения решения за конечное количество шагов. Симплекс–метод конечен, поскольку здесь выполняется направленный перебор базисных решений, а общее количество базисов для принятой системы ограничений конечно и определяется числом сочетаний из 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):

;

.

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

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

.

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

или

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

.



Дата добавления: 2020-07-18; просмотров: 1006;


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

Воспользовавшись поиском можно найти нужную информацию на сайте.

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

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.012 сек.