Решатель Линейного Программирования

О Решатель Линейного Программирования

Решатель линейного программирования — это онлайн-калькулятор, который находит максимум или минимум линейной целевой функции при соблюдении системы линейных неравенств или равенств. Он использует симплекс-метод (вариант Big-M), что позволяет свободно смешивать ограничения типа <=, >= и =, а для задач с 2 переменными он строит интерактивный график области допустимых решений с выделением каждой вершины и оптимума.

Что такое линейное программирование?

Задача линейного программирования (ЛП) ставит вопрос:

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

Как работает симплекс-метод

Начиная с допустимой вершины, симплекс-метод многократно улучшает целевую функцию, переходя к соседней вершине с лучшим значением. Механика процесса:

1. Стандартная форма: перевод ЛП к виду max c^Tx при условии Ax = b, x ≥ 0. Для ограничений <= добавляются дополнительные (slack) переменные; для >= вычитаются избыточные (surplus) и добавляются искусственные с большим штрафом −M; для равенств добавляются искусственные переменные.
2. Начальная таблица: базис состоит из дополнительных и искусственных переменных, что дает очевидную начальную вершину.
3. Входящая переменная: выбирается небазисная переменная с наибольшей положительной оценкой \( c_j - z_j \). Если такой переменной нет, текущее решение оптимально.
4. Выходящая переменная: для входящего столбца проводится тест минимального отношения — правая часть каждой строки делится на ее положительный элемент во входящем столбце, и выбирается строка с наименьшим отношением. Если положительных элементов нет, ЛП неограничена.
5. Итерация (Pivot): использование исключения Гаусса, чтобы сделать входящий столбец единичным вектором с единицей в выходящей строке.
6. Повторение до выполнения критерия остановки.

Если по завершении какая-либо искусственная переменная остается в базисе с положительным значением, исходная ЛП недопустима.

Графический метод (для 2 переменных)

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

Синтаксис ввода

Напишите целевую функцию в первой строке, затем по одному ограничению в строке. Именами переменных может быть любой идентификатор (x, y, x1, profit…). Операторы: <=, >= и =. Неотрицательность можно записать как x, y >= 0 для сокращения.

Пустые строки и комментарии, начинающиеся с #, игнорируются. Решатель принимает до 8 переменных решения и 20 ограничений.

Пример решения

Рассмотрим мебельную мастерскую, которая изготавливает столы и стулья. Каждый стол приносит \\$3 прибыли и требует 1 единицу древесины и 2 единицы труда. Каждый стул приносит \\$5 прибыли и требует 1 единицу древесины, 1 единицу труда и 3 единицы лака. Доступно: 10 ед. древесины, 16 ед. труда, 18 ед. лака. При x = столы и y = стулья, задача ЛП выглядит так:

Область допустимых решений — пятиугольник. Оценка Z в каждой вершине:

Таким образом, мастерской следует изготовить 6 столов и 4 стулья для получения максимальной прибыли в \\$38. Ограничения по дереву и труду являются связывающими (они равны своей правой части в оптимуме); лак имеет запас 0 (в данном случае также связывающее), что означает, что все три ресурса исчерпаны.

Общие проблемы и что обнаруживает решатель

Области применения

• Ассортимент продукции и планирование производства — сколько единиц каждого продукта производить для максимальной прибыли при ограниченных ресурсах.
• Задачи о диете и смешивании — минимизация стоимости рациона или корма при соблюдении питательных минимумов.
• Транспортные задачи и задачи о назначениях — минимизация стоимости доставки при балансе спроса и предложения.
• Оптимизация портфеля — максимизация ожидаемой доходности при ограничениях на риск или долю активов (линеаризовано).
• Сетевые потоки — задачи о максимальном потоке и потоке минимальной стоимости сводятся к ЛП с полностью унимодулярными матрицами коэффициентов.
• Составление расписаний — планирование графиков персонала с учетом требований к сменам и лимитов общего времени.

Как пользоваться калькулятором

1. Введите вашу задачу ЛП в текстовое поле. Первая строка должна начинаться с Maximize или Minimize. Каждая последующая строка содержит одно ограничение.
2. Используйте сокращение x, y >= 0, чтобы объявить неотрицательность для всех перечисленных переменных сразу.
3. Нажмите Решить задачу ЛП. Решатель выдаст оптимальное значение Z, оптимальные значения каждой переменной решения, список связывающих ограничений, а для задач с 2 переменными — интерактивный график области допустимых решений.
4. Наведите на вершину на графике, чтобы увидеть ее координаты и значение Z. Оптимум отмечен звездочкой.
5. Изучите симплекс-таблицы, чтобы увидеть каждую итерацию и проследить, как метод улучшает Z. Входящий столбец выделен янтарным цветом, выходящая строка — красным.

Часто задаваемые вопросы

Что такое задача линейного программирования?

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

Как работает симплекс-метод?

Симплекс-метод перемещается по вершинам допустимого многогранника. Каждый шаг (итерация) заменяет одну переменную в базисе на другую, переходя к соседней вершине со строго лучшим значением целевой функции. Алгоритм останавливается, когда итерация больше не может улучшить Z — текущая вершина тогда считается оптимальной. Инструмент использует вариант Big-M для работы со смешанными типами ограничений.

Что такое область допустимых решений?

Область допустимых решений — это набор всех значений переменных, удовлетворяющих всем ограничениям одновременно. Для 2 переменных это 2D выпуклый многоугольник; для n переменных — n-мерный многогранник. Пустой многогранник означает, что задача недопустима; многогранник, бесконечно уходящий в сторону улучшения, означает, что задача неограничена.

Что означает "неограниченная" в линейном программировании?

Задача ЛП является неограниченной, когда область допустимых решений тянется в бесконечность в том направлении, где целевая функция продолжает улучшаться. Например, Maximize x при условии x ≥ 0 не имеет предела. В реальности такие результаты обычно указывают на отсутствие важного ограничения, например, лимита ресурсов.

Что означает "альтернативный оптимум"?

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

Сколько переменных и ограничений принимает решатель?

До 8 переменных решения и 20 ограничений. Интерактивный график строится только для задач с 2 переменными; для 3 и более переменных вы по-прежнему получаете полное числовое решение, пошаговые таблицы и отчет об активности ограничений.

Дополнительная литература

• Линейное программирование — Википедия
• Симплекс-метод — Википедия
• М-метод (метод больших штрафов) — Википедия
• Двойственность в оптимизации — Википедия

Продвинутые математические операции:

• Антилогарифмический Калькулятор
• Калькулятор бета-функции
• Калькулятор биномиального коэффициента
• Калькулятор биномиального распределения
• Побитовый калькулятор Рекомендуемое
• Калькулятор центральной предельной теоремы
• Комбинированный калькулятор
• Калькулятор дополнительной функции ошибки
• Калькулятор комплексных чисел Рекомендуемое
• Калькулятор Энтропии
• Калькулятор функции ошибки
• Калькулятор экспоненциального распада
• Калькулятор экспоненциального роста: высокая точность
• Калькулятор экспоненциального интеграла
• калькулятор-показателей-высокая-точность
• Калькулятор факториала
• Калькулятор гамма-функции
• Калькулятор золотого сечения
• Калькулятор полураспада
• Калькулятор процентного роста
• Калькулятор перестановок
• Калькулятор распределения Пуассона
• Калькулятор корней многочленов с подробными шагами
• Калькулятор вероятности
• Калькулятор распределения вероятностей
• Калькулятор пропорций
• Калькулятор квадратичных формул
• Научный Калькулятор
• Калькулятор экспоненциальной записи
• Калькулятор значащих цифр Новый
• Калькулятор суммы кубов
• Калькулятор суммы последовательных чисел
• Калькулятор суммы квадратов
• Генератор таблицы истинности
• Калькулятор теории множеств
• Генератор диаграммы Венна (3 множества)
• Калькулятор китайской теоремы об остатках
• Калькулятор функции Эйлера
• Калькулятор расширенного алгоритма Евклида
• Калькулятор модулярного мультипликативного обратного
• Калькулятор цепных дробей
• Калькулятор кратчайшего пути Дейкстры
• Калькулятор минимального остовного дерева
• Валидатор последовательности степеней графа
• Калькулятор беспорядков (субфакториал)
• Калькулятор чисел Стирлинга
• Калькулятор принципа голубятни
• Калькулятор стационарного распределения цепи Маркова
• Калькулятор округления Новый
• Калькулятор отрицательного биномиального распределения Новый
• Калькулятор перестановок с повторениями Новый
• Калькулятор Модульного Возведения в Степень Новый
• Калькулятор первообразного корня
• Упроститель Булевой Алгебры Новый
• Решатель Карты Карно (K-Map) Новый
• Калькулятор раскраски графов Новый
• Калькулятор топологической сортировки Новый
• Калькулятор матрицы смежности Новый
• Калькулятор формулы включений-исключений Новый
• Решатель Линейного Программирования Новый
• Решатель задачи коммивояжёра (TSP) Новый
• Проверка Гамильтонова Пути Новый
• Проверка планарного графа Новый
• Калькулятор сетевого потока (Максимальный поток) Новый
• Решатель задачи о стабильных браках Новый
• Калькулятор Порядка в Теории Групп Новый
• Калькулятор Колец и Полей Новый