Калькулятор решает задачи линейного программирования для двух переменных. Целевая функция F = c1·x + c2·y максимизируется при заданных линейных ограничениях вида a·x + b·y ≤ c и условиях неотрицательности x ≥ 0, y ≥ 0.
Как работает симплекс-метод для двух переменных
Задача линейного программирования F = c1·x + c2·y достигает максимума в одной из вершин области допустимых решений. Вершины образуются пересечениями прямых ограничений a·x + b·y = c между собой и с осями координат. Калькулятор перебирает все вершины, вычисляет значение функции в каждой и выбирает точку с наибольшим результатом.
Для двух переменных перебор вершин эквивалентен симплекс-методу. Область допустимых решений представляет собой выпуклый многоугольник, а максимум всегда находится в угловой точке.
Разбор примера с числами
Целевая функция F = 3x + 2y максимизируется при ограничениях x + y ≤ 8, 2x + y ≤ 12, x ≥ 0, y ≥ 0. Вершины области: (0; 0), (6; 0), (4; 4), (0; 8). Значения функции в этих точках: F(0; 0) = 0, F(6; 0) = 18, F(4; 4) = 20, F(0; 8) = 16.
Максимум F = 20 достигается в точке x = 4, y = 4. Эта вершина находится на пересечении прямых x + y = 8 и 2x + y = 12. Решение системы: из первого уравнения y = 8 - x, подстановка во второе даёт 2x + 8 - x = 12, откуда x = 4 и y = 4.
Типовые задачи и их решения
| Целевая функция | Ограничения | Оптимальное решение | Максимум F |
|---|---|---|---|
| F = 2x + 3y | x + y ≤ 5, x ≤ 3, y ≤ 4 | x = 1, y = 4 | 14 |
| F = 5x + 4y | 2x + y ≤ 10, x + 2y ≤ 10 | x = 3,33, y = 3,33 | 30 |
| F = x + y | x + 2y ≤ 6, 2x + y ≤ 6 | x = 2, y = 2 | 4 |
| F = 4x + y | x + y ≤ 7, 3x + y ≤ 15 | x = 4, y = 3 | 19 |
Первая задача имеет оптимум в точке, где активны ограничения y ≤ 4 и x + y ≤ 5. Вторая задача симметрична, оптимум лежит на пересечении двух наклонных прямых.
Как решить задачу линейного программирования онлайн
Калькулятор требует ввода коэффициентов целевой функции c1 и c2, затем списка ограничений. Каждое ограничение задаётся тремя числами: коэффициент при x, коэффициент при y, правая часть неравенства. Например, для 3x + 2y ≤ 15 вводится строка 3 2 15.
После ввода всех ограничений калькулятор строит область допустимых решений, находит вершины и вычисляет значение функции в каждой. Результат показывает координаты оптимальной точки и максимальное значение F.
Проверка результата вручную
Для проверки нужно найти все вершины области и вычислить функцию в каждой. Вершины на осях координат находятся пересечениями ограничений с осями при x = 0 или y = 0. Остальные вершины находятся решением систем двух уравнений.
В примере F = 3x + 2y вершина (4; 4) проверяется подстановкой. Первое ограничение: 4 + 4 = 8 ≤ 8, выполнено. Второе: 2·4 + 4 = 12 ≤ 12, выполнено. Значение функции: F = 3·4 + 2·4 = 20.
Частые ошибки при расчёте
Неправильный порядок коэффициентов в ограничениях приводит к искажению области. Если вместо 2x + y ≤ 12 ввести 1 2 12, получится x + 2y ≤ 12, что меняет наклон прямой. Калькулятор построит другой многоугольник, и оптимум сместится.
Пропуск условий неотрицательности x ≥ 0, y ≥ 0 расширяет область в отрицательную полуплоскость. Калькулятор автоматически учитывает эти ограничения, но при ручной проверке их легко забыть.
Границы применимости калькулятора
Калькулятор работает только с двумя переменными x и y. Задачи с тремя и более переменными требуют другого алгоритма. Область допустимых решений должна быть ограниченной, иначе максимум не существует.
Ограничения должны быть линейными и иметь вид a·x + b·y ≤ c. Нелинейные неравенства, квадратичные функции не поддерживаются. Коэффициенты должны быть числами.
Связанные расчёты
Двойственная задача линейного программирования находит минимум функции при ограничениях противоположного знака. Решение двойственной задачи даёт оценки ресурсов и показывает, на сколько изменится прибыль при увеличении лимита на единицу.
Целочисленное программирование требует, чтобы x и y были целыми числами. Симплекс-метод находит вещественное решение, которое затем округляется методом ветвей и границ.