Магистратура
  1. Введение в математический анализ  1.1. Теория множеств и логика в реальном анализе  1.1.1. Множества и операции в теории множеств и логике в реальном анализе  1.1.2. Отношения и функции  1.1.3. Логика и кванторы  1.1.4. Мощность множеств  1.2. Метрика  1.2.1. Введение в открытые и замкнутые множества в метрических пространствах  1.2.2. Сходимость последовательностей в метрическом пространстве  1.2.3. Непрерывная функция в метрическом пространстве  1.2.4. Компактность и полнота в метрических пространствах в реальном анализе  1.3. Последовательности и ряды  1.3.1. Сходимость последовательностей  1.3.2. Бесконечные ряды  1.3.3. Равномерная сходимость  1.3.4. Ряды степеней  1.4. Дискриминация  1.4.1. Теорема о среднем значении  1.4.2. Ряд Тейлора  1.4.3. Функции нескольких переменных  1.4.4. Частная производная  1.5. Интеграция  1.5.1. Интегрирование Римана и Лебега  1.5.2. Неправильные интегралы  1.5.3. Теория меры: фундаментальный инструмент в интеграции  1.5.4. Теорема Фубини  1.6. Функциональный анализ  1.6.1. Понимание пространства Банака  1.6.2. Пространства Гильберта  1.6.3. Операторы на пространствах  1.6.4. Спектральная теория
  2. Абстрактная алгебра  2.1. Понимание групп в абстрактной алгебре  2.1.1. Определения и примеры групп в абстрактной алгебре  2.1.2. Гомоморфизмы групп  2.1.3. Введение в нормальные подгруппы  2.1.4. Теорема Силова  2.2. Кольца и поля  2.2.1. Идеалы и фактор-кольца  2.2.2. Расширения полей  2.2.3. Теория Галуа  2.2.4. Полиномиальные кольца  2.3. Введение в модули в абстрактной алгебре  2.3.1. Гомоморфизм модуля  2.3.2. Свободные модули  2.3.3. Введение в тензорные произведения  2.3.4. Точная последовательность в модулях  2.4. Линейная алгебра  2.4.1. Векторное пространство  2.4.2. Собственные значения и собственные векторы  2.4.3. Векторное пространство с внутренним произведением  2.4.4. Диагонализация
  3. Топология  3.1. Общая топология  3.1.1. Открытые и закрытые множества  3.1.2. Компактность и связность  3.1.3. Непрерывные отображения  3.1.4. Аксиома отделимости  3.2. Алгебраическая топология  3.2.1. Понимание фундаментальных групп в алгебраической топологии  3.2.2. Гомотопия и гомология  3.2.3. Симплициальный комплекс  3.2.4. Точные последовательности в гомологии  3.3. Дифференциальная топология  3.3.1. Понимание многообразий в дифференциальной топологии  3.3.2. Гладкие функции  3.3.3. Тангенциальное и котангенциальное пространство  3.3.4. Векторные расслоения
  4. Дифференциальные уравнения  4.1. Обыкновенные дифференциальные уравнения  4.1.1. Дифференциальные уравнения первого порядка  4.1.2. Линейные уравнения второго порядка  4.1.3. Системы дифференциальных уравнений  4.1.4. Анализ устойчивости в обыкновенных дифференциальных уравнениях  4.2. Частные дифференциальные уравнения  4.2.1. Классификация уравнений с частными производными  4.2.2. Понимание рядов Фурье в уравнениях с частными производными  4.2.3. Введение в функции Грина  4.2.4. Метод характеристик  4.3. Динамические системы в дифференциальных уравнениях  4.3.1. Теория устойчивости  4.3.2. Предельные циклы в динамических системах  4.3.3. Теория хаоса  4.3.4. Теория бифуркаций
  5. Теория вероятностей и статистика  5.1. Теория вероятностей  5.1.1. Случайные переменные  5.1.2. Распределения вероятностей  5.1.3. Закон больших чисел  5.1.4. Центральная предельная теорема  5.2. Статистическое вывод  5.2.1. Проверка гипотез  5.2.2. Доверительный интервал  5.2.3. Байесовские методы  5.2.4. Метод максимального правдоподобия  5.3. Стохастические процессы  5.3.1. Цепи Маркова  5.3.2. Броуновское движение  5.3.3. Понимание процессов Пуассона  5.3.4. Мартингейлы: всестороннее исследование в вероятности и статистике
  6. Численный анализ  6.1. Численное решение уравнений  6.1.1. Оригинальное открытие  6.1.2. Итерационные методы  6.1.3. Анализ сходимости  6.1.4. Границы ошибок в численных решениях уравнений  6.2. Численная линейная алгебра  6.2.1. Факторизация матриц  6.2.2. Вычисление собственных значений  6.2.3. Разреженные матрицы  6.2.4. Методы предобработки  6.3. Численное интегрирование и дифференцирование  6.3.1. Методы квадратур  6.3.2. Введение в конечные разности  6.3.3. Анализ ошибок в численном интегрировании и дифференцировании  6.3.4. Адаптивные методы в численном интегрировании и дифференцировании
  7. Комплексный анализ  7.1. Комплексные числа  7.1.1. Полярная форма  7.1.2. Комплексные сопряженные  7.1.3. Экспоненциальная форма комплексных чисел  7.1.4. Корни из единицы  7.2. Аналитические функции  7.2.1. Уравнения Коши — Римана  7.2.2. Степенные ряды  7.2.3. Конформное отображение  7.2.4. Гармонические функции  7.3. Интегрирование на комплексной плоскости  7.3.1. Теорема Коши  7.3.2. Теорема о вычетах  7.3.3. Контурное интегрирование  7.3.4. Интегральные преобразования
  8. Математическая логика и основания  8.1. Пропозициональная логика  8.1.1. Таблицы истинности  8.1.2. Логическая эквивалентность в пропозициональной логике  8.1.3. Техники доказательства в пропозициональной логике  8.1.4. Решение в пропозициональной логике  8.2. Логика предикатов  8.2.1. Кванторы в предикатной логике  8.2.2. Формальные системы в предикатной логике  8.2.3. Полнота и правильность  8.2.4. Модельная теория  8.3. Теория множеств  8.3.1. Кардинальность и ординальность  8.3.2. Аксиоматические системы  8.3.3. Понимание теории множеств Цермело-Френкеля  8.3.4. Силы в теории множества
  9. Настройка  9.1. Линейное программирование  9.1.1. Метод симплекс  9.1.2. Двойственность в линейном программировании  9.1.3. Анализ чувствительности в линейном программировании  9.1.4. Методы внутренних точек  9.2. Нелинейное программирование  9.2.1. Градиентный спуск  9.2.2. Множители Лагранжа  9.2.3. Выпуклая оптимизация  9.2.4. Квадратичное программирование  9.3. Комбинаторная оптимизация  9.3.1. Алгоритмы графов  9.3.2. Целочисленное программирование  9.3.3. Сетевой поток  9.3.4. Алгоритмы аппроксимации
  10. Дискретная математика  10.1. Теория графов  10.1.1. Представление графов  10.1.2. Плоскость и цвет  10.1.3. Алгоритм поиска кратчайшего пути  10.1.4. Сетевой поток  10.2. Компаньонство  10.2.1. Перестановка и сочетание  10.2.2. Порождающая функция  10.2.3. Рекуррентные соотношения  10.2.4. Понимание принципа включения-исключения  10.3. Криптография  10.3.1. Применение теории чисел в криптографии  10.3.2. Симметричное и асимметричное шифрование  10.3.3. RSA и криптография на эллиптических кривых  10.3.4. Постквантовая криптография

Магистратура → Настройка → Линейное программирование ↓


Метод симплекс


Метод симплекс — это алгоритм, используемый для решения задач линейного программирования, который включает в себя поиск максимального или минимального значения линейной функции, удовлетворяющей линейным ограничениям. Линейное программирование является важным инструментом оптимизации в таких областях, как экономика, инженерия, военная сфера, бизнес и наука.

Введение в линейное программирование

Линейное программирование включает в себя набор уравнений и неравенств, представляющих математическую модель, оптимальное решение которой необходимо найти. Для задачи линейного программирования целью является оптимизация (максимизация или минимизация) линейной целевой функции при условии линейных равенств и/или неравенств. Общая форма задачи линейного программирования представлена следующим образом:

Максимум (или минимум): 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

Что такое метод симплекс?

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

Процедура метода симплекс

  1. Преобразование задачи в стандартную форму.
  2. Определение пригодного начального решения.
  3. Продолжать искать более лучшее решение, пока улучшение невозможно.
  4. Оценка и интерпретация решения.

Шаг 1: Преобразование в стандартную форму

Чтобы применить метод симплекс, задача линейного программирования должна быть преобразована в стандартную форму. Это включает в себя:

  • Удовлетворение, чтобы все ограничения были в виде линейных уравнений.
  • Введение избыточных переменных для преобразования неравенств в равенства.
  • Обеспечение того, чтобы все переменные были неотрицательными.

Рассмотрим следующий пример:

Максимум: 3x 1 + 5x 2

при условии:
x 1 + 2x 2 ≤ 8
3x 1 + 2x 2 ≤ 12

x 1 , x 2 ≥ 0

Введение избыточных переменных:

x 1 + 2x 2 + s 1 = 8
3x 1 + 2x 2 + s 2 = 12

x 1 , x 2 , s 1 , s 2 ≥ 0

Избыточные переменные s 1 и s 2 представляют собой неиспользованные ресурсы из ограничений.

Шаг 2: Определение начального решения

При установке равным нулю переменных решения (в данном случае x 1 и x 2) и установке избыточных переменных равными значениям ограничений, определяется начальное базовое допустимое решение.

В нашем примере начальное решение:

x 1 = 0, x 2 = 0, s 1 = 8, s 2 = 12

Шаг 3: Повторение для улучшения решения

Чтобы выполнить рекурсию, создается таблица. Строка целей содержит отрицательные коэффициенты целевой функции. Рекурсия включает в себя:

  • Цель - выбрать входящую переменную, имеющую самый отрицательный коэффициент в строке.
  • Выбор выпадающих переменных с использованием теста минимальной пропорции.
  • Поворот для обновления решения.
Начальная таблица:
| базис | x 1 | x 2 | s 1 | s 2 | правая сторона |
| S 1 | 1 | 2 | 1 | 0 | 8 |
| S 2 | 3 | 2 | 0 | 1 | 12 |
| z | -3 | -5 | 0 | 0 | 0 |

Итерация 1:

Входящая переменная - x 2 (самый отрицательный коэффициент в z-строке: -5 ).

Для минимального соотношения: RHS / коэффициент x 2 = min(8/2, 12/2) = 4, следовательно, s 1 - выпадающая переменная.

Поворот для замены s 1 на x 2.

Панторная таблица:
| базис | x 1 | x 2 | s 1 | s 2 | правая сторона |
| x 2 | 0.5 | 1 | 0.5 | 0 | 4 |
| S2 | 2.0 | 0 | -1 | 1 | 4 |
| z | -0.5 | 0 | 2.5 | 0 | 20 |

Итерация 2:

Самый отрицательный коэффициент в новой z-строке: -0.5 (для x 1).

Используя минимальное соотношение: RHS / коэффициент x 1 = min(4/0.5, 4/2) = 2, так что s 2 - выпадающая переменная.

Поворот для замены s 2 на x 1.

Поворотная таблица:
| базис | x 1 | x 2 | s 1 | s 2 | правая сторона |
| x 2 | 0.5 | 1 | 0.5 | 0 | 4 |
| x1 | 1 | 0 | -0.5 | 0.5 | 2 |
| Z | 0 | 0 | 3 | 0.5 | 22 |

Значение целевой функции улучшилось до 22, и больше нет отрицательных коэффициентов, следовательно, текущее решение является оптимальным.

Визуальный пример

Затененная область на графике представляет собой допустимую область, где все ограничения пересекаются. Круг отмечает точку оптимального решения, в которой достигается максимальное значение целевой функции.

Шаг 4: Оценка и интерпретация решения

Метод симплекс предоставляет наилучшие возможные значения для переменных решения в пределах допустимой области. Из окончательной таблицы мы можем определить оптимальное решение:

x 1 = 2, x 2 = 4

Значение целевой функции: 22

Это означает, что максимальное значение целевой функции 3x 1 + 5x 2 равно 22 при x 1 = 2 и x 2 = 4.

Свойства метода симплекс

  • Метод симплекс движется по ребру допустимой области, обеспечивая улучшение или сохранение решения на каждом шаге, пока не будет найдено оптимальное решение.
  • Он эффективно обрабатывает линейные целевые функции с ограничениями, что делает его подходящим для крупномасштабных задач линейного программирования.
  • Хотя метод обычно начинается с нуля, все же требуется некоторая предварительная обработка для преобразования любой задачи в стандартную форму.
  • Алгоритм конечен; он либо сходится к оптимальному решению, либо распознает, что для заданных ограничений не существует решения.

Преимущества и ограничения

Преимущества метода симплекс включают его способность обеспечивать точные оптимальные решения задач линейного программирования и его применимость к широкому диапазону задач, выходящих за рамки только ограничений вида ≤. Тем не менее, у этого метода есть некоторые ограничения:

Преимущества

  • Обеспечивает точное решение.
  • Может эффективно обрабатывать сложные задачи.
  • Он широко понятен и используется, существуют множество библиотек и программного обеспечения для его поддержки.

Ограничения

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

Заключение

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


Магистратура → 9.1.1


U
username
0%
завершено в Магистратура

← предыдущая (9.1)
Линейное программирование
следующая (9.1.2) →
Двойственность в линейном программировании

комментарии 



Метод симплекс

https://www.buddymath.com/g/9.1.1?bmal=ru