Симплексные таблицы
Последовательность симплексных преобразований системы уравнений удобно оформлять в виде симплексных таблиц. Переход от одной таблицы к другой соответствует одной итерации, то есть переходу от одного базиса к другому, при этом значений целевой функции уменьшается. Симплексные таблицы составляют следующим образом. Вверху таблицы помещают все переменные и коэффициенты, с которыми соответствующие переменные входят в целевую функцию. Первый столбец состоит из коэффициентов целевой функции при переменных, вошедших в базис. Затем следует столбец базисных переменных и свободных членов уравнений.
Столбец с наименьшей положительной оценкой (для задач на минимум) или наибольшей отрицательной оценкой (для задач на максимум) называется разрешающим столбцом, а переменная столбца должна вводится в базис. Чтобы установить переменную, которая должна быть выведена из базиса, определяют отношения свободных членов к положительным элементам разрешающего столбца. Строка с наименьшим отклонением называется разрешающей строкой, а переменная этой строки выводится из базиса. Если окажется несколько равных наименьших отношений свободных членов к коэффициентам разрешающего столбца, то следует брать отношение с наибольшим знаменателем.
Алгоритм симплексного метода состоит из следующих итераций (при решении задачи на минимум):
- систему ограничений задачи линейного программирования необходимо решить относительно какого-либо базиса. Выразить линейную форму (целевую функцию) через свободные переменные;
- составить симплексную таблицу. Если в индексной строке все элементы отрицательны, то базисное решение оптимально. Задача решена;
- если в индексной строке симплексной таблицы есть положительные элементы, то столбец, соответствующий максимальному из них, принимается за разрешающий. Рассчитываются отношения элементов столбца свободных членов к положительным элементам разрешающего столбца. Строка, соответствующая минимальному из этих отношений, является разрешающей. Элемент таблицы, находящийся на пересечении разрешающего столбца и разрешающей строки, называется разрешающим;
- переходить к новому базису следует, исключая из старого базиса переменную, соответствующую разрешающей строке, вводя вместо нее переменную, которая соответствует разрешающему столбцу. Составляется новая симплексная таблица, соответствующая новому базису. Действия, начиная со второго, повторяются.
Элемент симплексной таблицы, находящийся на пересечении разрешающего столбца и разрешающей строки, называется разрешающим элементом. Затем осуществляется симплексное преобразование таблицы, в результате которого переменная столбца вводится в базис. Это означает, что эта переменная должна быть исключена из всех остальных строк таблицы (из остальных уравнений системы), а в разрешающей строке должна присутствовать с коэффициентом +1.
Для этого сначала каждый элемент разрешающей строки делится на разрешающий элемент, а затем разрешающая строка вычитается из остальных строк, включая индексную. Для этого каждый новый элемент разрешающей строки умножается на элемент разрешающего столбца и вычитается из каждого элемента соответствующей строки. Такое действие производится для всех элементов всех строк симплексной таблицы, включая индексную строку.
В результате расчетов в разрешающем столбце все элементы будут иметь нулевое значение, за исключением разрешающего элемента, который равен 1, что означает, что новая базисная переменная будет входить только в одно уравнение с коэффициентом +1. Симплексные преобразования выполняются до тех пор, пока в индексной строке не останется положительных элементов (для задачи на минимум) или отрицательных элементов (для задачи на максимум).
- Назначение и классификация складов
- Требования к транспортированию и хранению массовых грузов
- Автоматическая идентификация грузов
- Пломбирование и индикация грузов
- Силы, действующие на груз при транспортировке
- Причины недостачи грузов
- Естественная убыль грузов и ее нормирование
- Виды несохранности грузов при перевозке
- Транспортная маркировка грузов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу