Алгоритм симплекс метода для решения задач линейного программирования

Процесс решения задач подразделяется на несколько этапов:

1. Математическая формулировка условий задач в виде систем неравенств и уравнений;

Записывают математическую формулировку базовой ЭММ

2. Решение задачи симплекс- методом;

§ приведение задач к канонической форме и нахождение первоначального варианта допустимого плана;

§ проверка найденного варианта плана на оптимальность;

§ последовательное улучшение плана до получения оптимального;

3. Экономический анализ и корректировка оптимального плана.

*** 1)определение переменной, вводимой в базис.

2)определение переменной, выводимой из базиса.

3)определение главного элемента

4) перерасчет коэффициентов главной строки

5)перевычисление остальных коэффициентов

6)определение значения целевой функции и коэффициентов индексной строки

7) контроль решения задачи

Переменная, вводимая в базис, соответствует max отрицательному значению коэффициента индексной строки.

Переменной, удаляемой из базиса соответствует min значение отношения элементов столбца А_io на соответствующее значение элементов ключевого столбца min

Главный элемент находится на пересечении ключевого столбца и ключевой строки.

Перевычисление коэффициентов главной строки:

Арифметический контроль решения:

разница между коэффициентами столбца ∑ и ∑_к должны отличаться не более чем на 0,003

контроль вычисления значений индексной строки Z=C_ijX_j-C_j

Логический контроль вычислений:

1)Значение целевой функции должно возрастать после каждой итерации при решении задач на max или уменьшаться при решении задач на min.

2)в столбце А_io не должно возникать отрицательных величин

3)при переменной, вошедшей в базис, имеет место единичный вектор.

Опорное решение предполагает, что остаточные переменные приравниваются ресурсам, а основные переменные равны нулю.

Коэффициенты индексной строки вычисляются по формуле:

; - коэффициенты при неизвестных в уравнении для целевой функции;

- оценка целевой функции;

- коэффициенты ограничений;

Если среди дополнительных переменных есть только остаточные, то, т. к. =0, т. е. каждый j-ый элемент индексной строки равен взятому с обратным знаком коэффициенту при соответствующей переменной в целевой функции.

Значение целевой функции при этом равно 0,.

Решение оптимально, когда все элементы индексной строки положительны в задачах на максимум; (отрицательны в задачах на минимум).

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

Увеличивая соответствующую небазисную переменную, в данном примере это X3,, вводя ее в базис, мы увеличиваем значение Z. Для определения выводимой из базиса переменной поочередно разделим значения элементов столбца свободных членов Aio на соответствующие положительные элементы ключевого столбца Aio/Aiкл..

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

Переменная X8 подлежит выводу из базиса в нашем примере. Элемент, находящийся на пересечении ключевого столбца и ключевой строки, называют ключевым (разрешающим).

Расчет всех элементов новой симплекс-таблицы

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

Пересчет элементов начальной строки (ключевой) производим по формуле:

А`кл.j=Aклj/Aкл. Все элементы ключевой строки делят на ключевой элемент.

Все без исключения коэффициенты новой таблицы рассчитываются на основе предыдущей через ключевой элемент. Любой элемент следующей таблицы равен соответствующему элементу предыдущей таблицы минус произведение соответствующего элемента ключевого (i) столбца на соответствующий (j) элемент начальной строки.