Бакалавриат → Линейное программирование и оптимизация ↓
Понимание метода симплекс в линейном программировании и оптимизации
Введение в линейное программирование
Линейное программирование — это математическая техника для оптимизации линейной целевой функции при условии линейных равенств и неравенств. Это способ достижения наилучшего результата в математической модели, чьи требования представлены линейными отношениями. Этот вид оптимизации важен в различных областях, таких как экономика, инженерия, военное дело и бизнес-планирование.
Целевая функция и ограничения
В линейном программировании наша цель состоит в том, чтобы максимизировать или минимизировать линейную целевую функцию. Обобщенная задача линейного программирования может быть представлена следующим образом:
Максимум или минимум: Z = c 1 x 1 + c 2 x 2 + ... + c n x n при условии: a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1 a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2 , a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m x 1 , x 2 , ..., x n ≥ 0
Здесь x 1 , x 2 , ..., x n — переменные, c 1 , c 2 , ..., c n — коэффиценты целевой функции, a ij — коэффициенты ограничений и b i — константы в уравнениях ограничений.
Метод симплекс: Обзор
Метод симплекс — это популярный алгоритм, используемый для решения задач линейного программирования. Он был разработан Джорджем Данцигом в 1947 году. Этот метод состоит из следующих основных шагов:
- Преобразование задачи линейного программирования в стандартную форму.
- Поиск начального допустимого решения.
- Итерационный процесс улучшения целевой функции до достижения оптимального решения.
Преобразование в стандартную форму
Перед применением метода симплекс необходимо преобразовать данную задачу линейного программирования в стандартную форму. Это включает в себя приведение всех ограничений к форме равенств и добавление значений, наложений или искусственных переменных, если это необходимо.
Предположим, у нас есть ограничение вида: a 11 x 1 + a 12 x 2 ≤ b 1
Чтобы превратить это в равенство, мы вводим добавочную переменную s 1 :
a 11 x 1 + a 12 x 2 + s 1 = b 1
Поиск начального допустимого решения
После приведения задачи в стандартную форму необходимо найти базисное допустимое решение. Это включает в себя установку нуля для небазисных переменных и решение системы уравнений для нахождения значений базисных переменных.
Итерационный процесс
Основная цель метода симплекс — улучшение значения целевой функции за счет обработки допустимых решений для выявления оптимального решения. Это достигается путем опорных перестановок.
Пример
Рассмотрим пример задачи линейного программирования. Предположим, у нас есть следующая задача:
Максимум: Z = 3x 1 + 5x 2 при условии: x 1 + 2x 2 ≤ 8 3x 1 + 2x 2 ≤ 12 x 1 , x 2 ≥ 0
В приведенном выше примере ограничения x 1 + 2x 2 = 8 и 3x 1 + 2x 2 = 12 изображены в виде линий. Допустимая область, ограниченная зеленым многоугольником, показывает, где выполняются все условия.
Опорные перестановки в методе симплекс
Для улучшения целевой функции мы выберем опорные элементы. Критерии входа и выхода помогают определить, какая переменная входит в базис, а какая выходит. Опорные перестановки изменяют наш базис таким образом, чтобы он двигался к соседнему допустимому решению с более высоким значением (в случае максимизации) для целевой функции.
Шаги, связанные с опорными перестановками
Процесс опорных перестановок включает в себя следующие основные шаги:
- Определите входящую переменную:
- Смотрите на строку целевой функции (также называемую строкой издержек) в симплексной таблице. Выберите переменную, коэффициент которой наиболее положителен (для задач максимизации). Это наша входящая переменная.
- Определите выходную переменную:
- Чтобы найти выходную переменную, вычислите минимальное соотношение правой части и положительных коэффициентов входящей переменной в каждой строке ограничения.
- Выполните операции с рядами:
- Преобразуйте таблицу, чтобы отразить этот новый базис. Это включает в себя операцию с опорным элементом, чтобы установить другие элементы в столбце входящей переменной на ноль.
Продолжение примера
Применим эти шаги к нашему предыдущему примеру.
Симплексная таблица для начального базиса
Первоначальная таблица для преобразования неравенств в равенства составляется с расслабленными переменными s 1 и s 2 для каждого ограничения:
| x 1 | x 2 | s 1 | s 2 | правая часть | , , 1 | 2 | 1 | 0 | 8 | , 3 | 2 | 0 | 1 | 12 | , , -3 | -5 | 0 | 0 | 0 |
Давайте определим входящие и выходящие переменные:
Для максимизации наибольший отрицательный коэффициент в строке целевой функции — -5 (под x 2). Это означает, что x 2 — наша входящая переменная.
Чтобы найти выходную переменную, вычислим соотношение правой части и положительного коэффициента x 2:
8/2 = 4 (для первой строки) 12/2 = 6 (для второй строки) Минимальное соотношение равно 4, что указывает на то, что первая строка будет выходить.
Выполните операции с рядами, чтобы создать исходную переменную x 2 в первой строке.
Соответствующим образом обновите остальную часть таблицы.
Оптимальное решение
Продолжайте аналогичные шаги опорных перестановок до тех пор, пока в строке целевой функции не будет отрицательных коэффициентов (для максимизации), указывающих на достижение оптимального решения.
Заключение
Метод симплекс — это эффективный алгоритм, который поэтапно проходит через вершины допустимой области. Он особенно полезен для линейных задач, которые включают в себя большое количество переменных и ограничений, подтверждая свою полезность как в теоретической математике, так и в практических сценариях принятия решений. Тщательное выполнение и понимание каждого шага позволит студентам эффективно использовать силу метода симплекс для нахождения оптимальных решений сложных задач.
комментарии