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

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

Решатель линейного программирования — это онлайн-калькулятор, который находит максимум или минимум линейной целевой функции при соблюдении системы линейных неравенств или равенств. Он использует симплекс-метод (вариант 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 и более переменных вы по-прежнему получаете полное числовое решение, пошаговые таблицы и отчет об активности ограничений.

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

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