1. Основы линейного программирования: графический метод и симплекс-метод
Основы линейного программирования: графический метод и симплекс-метод
Представьте себе директора мебельной фабрики, которому нужно решить, сколько производить столов и стульев, чтобы получить максимальную прибыль. Ресурсы ограничены: древесины на складе конечное количество, рабочие часы мастеров лимитированы, а спрос на рынке не бесконечен. Если он произведет только столы, он может не использовать весь запас человеко-часов. Если только стулья — может не хватить дерева. Линейное программирование (ЛП) — это математический аппарат, который позволяет найти ту самую «золотую середину», обеспечивающую наилучший результат в условиях жестких ограничений.
Структура задачи линейного программирования
Любая задача ЛП состоит из трех фундаментальных компонентов. Понимание этой структуры — первый шаг к успешному решению любого экзаменационного билета.
Геометрически каждое ограничение-неравенство отсекает часть пространства. Пересечение всех этих «полуплоскостей» (в двумерном случае) или «полупространств» (в многомерном) образует область допустимых решений (ОДР). Если ОДР существует, она представляет собой выпуклый многогранник. Фундаментальная теорема ЛП гласит: своего оптимального значения целевая функция достигает в одной из вершин этого многогранника.
Графический метод: визуализация успеха
Графический метод применим, когда в задаче всего две переменные ( и ). Это идеальный способ понять логику ЛП перед тем, как переходить к сложным алгоритмам.
Рассмотрим классическую задачу. Пусть предприятие выпускает два вида изделий. На производство изделия №1 требуется 2 кг сырья и 4 часа труда. На изделие №2 — 5 кг сырья и 2 часа труда. Запасы сырья составляют 20 кг, трудовой ресурс — 16 часов. Прибыль от продажи единицы изделия №1 равна 300 руб., изделия №2 — 500 руб.
Составим модель:
Алгоритм построения ОДР
Сначала построим прямые, соответствующие границам неравенств. Для этого заменим знаки на .
На координатной плоскости проводим эти линии. Поскольку в обоих случаях стоит знак «меньше или равно», допустимая область находится ниже и левее этих прямых, но в первой четверти (так как ). ОДР в данном случае — это четырехугольник с вершинами , , (точка пересечения прямых) и .
Поиск оптимума через вектор-градиент
Чтобы найти максимум, нужно построить вектор . Он указывает направление самого быстрого роста целевой функции. Однако на практике удобнее использовать упрощенный вектор, сохранив пропорции, например .
Затем мы строим линию уровня (она перпендикулярна вектору ) и начинаем перемещать её параллельно самой себе в направлении вектора до тех пор, пока она не коснется «последней» точки ОДР перед выходом из неё. В нашей задаче этой точкой будет точка .
Найдем координаты , решив систему уравнений:
Умножим первое уравнение на 2: . Вычтем второе из полученного: . Подставим в любое уравнение: .
Максимальная прибыль: руб.
Каноническая форма и подготовка к симплекс-методу
Когда переменных становится три и более, чертежи бессильны. Здесь вступает в дело симплекс-метод — алгебраический итерационный процесс. Но прежде чем его запустить, задачу нужно привести к каноническому виду.
Каноническая форма требует:
Чтобы превратить неравенство в уравнение, вводятся дополнительные переменные (слабительные переменные).
> Важный нюанс: дополнительные переменные в целевую функцию входят с коэффициентом 0, так как они не приносят прибыли напрямую.
Симплекс-метод: пошаговый алгоритм
Симплекс-метод — это направленный перебор вершин многогранника. Мы начинаем в одной вершине (обычно в начале координат) и на каждом шаге переходим к соседней, где значение целевой функции лучше.
Шаг 1: Построение начальной таблицы
Для примера возьмем ту же задачу, что и в графическом методе, приведя её к каноническому виду:
Здесь и называются базисными переменными, потому что в каждом уравнении они встречаются по одному разу с коэффициентом 1 и образуют единичную матрицу. Остальные () — свободные. В начальной точке мы полагаем свободные переменные равными нулю. Тогда .
| Базис | | | | | Решение () | | :--- | :--- | :--- | :--- | :--- | :--- | | | 2 | 5 | 1 | 0 | 20 | | | 4 | 2 | 0 | 1 | 16 | | | -300 | -500 | 0 | 0 | 0 |
Шаг 2: Проверка на оптимальность
Смотрим на строку (индексную строку). Если в ней (для задачи на максимум) есть отрицательные коэффициенты, значит, решение можно улучшить. У нас это и .
Шаг 3: Выбор ведущего столбца и строки
Шаг 4: Пересчет таблицы (Метод Жордана-Гаусса)
Наша цель — сделать так, чтобы на месте разрешающего элемента оказалась 1, а в остальном ведущем столбце — 0.
Новая таблица:
| Базис | | | | | Решение | | :--- | :--- | :--- | :--- | :--- | :--- | | | 0,4 | 1 | 0,2 | 0 | 4 | | | 3,2 | 0 | -0,4 | 1 | 8 | | | -100 | 0 | 100 | 0 | 2000 |
Шаг 5: Повторение итерации
В строке всё еще есть отрицательное число . Значит, должен войти в базис.
После пересчета в строке окажется: . Все коэффициенты в индексной строке неотрицательны. Оптимум найден! , , .
Вырожденность и особые случаи
В процессе решения можно столкнуться с аномалиями, которые часто встречаются в экзаменационных задачах для проверки бдительности студента.
Альтернативный оптимум
Если в финальной симплекс-таблице коэффициент при какой-либо свободной переменной в строке равен нулю, это означает, что задача имеет бесконечное множество решений. Геометрически это соответствует ситуации, когда линия уровня целевой функции параллельна одной из сторон многогранника ОДР. В этом случае любая точка на этом отрезке будет давать одно и то же максимальное значение функции.Неограниченность целевой функции
Если при выборе ведущей строки оказывается, что все элементы ведущего столбца отрицательны или равны нулю, значит, область допустимых решений не замкнута в направлении роста функции. Вы не можете посчитать отношения . В этом случае говорят, что , и задача не имеет конечного оптимума.Отсутствие допустимых решений
Если при использовании метода искусственного базиса (который применяется, когда нельзя сразу найти начальный опорный план) в финальном решении остаются искусственные переменные с ненулевыми значениями, значит, система ограничений противоречива. ОДР — пустое множество.Двойственность в линейном программировании
Каждой задаче ЛП (прямой) соответствует двойственная задача. Это не просто математический фокус, а мощный инструмент экономического анализа.
Если прямая задача ищет максимум прибыли при ограничениях на ресурсы, то двойственная ищет минимальную общую оценку этих ресурсов. Коэффициенты целевой функции прямой задачи становятся правыми частями ограничений двойственной, и наоборот. Матрица коэффициентов транспонируется.
Свойства двойственности:
На экзамене знание двойственности помогает проверить себя: если вы решили симплекс-методом прямую задачу, значения переменных двойственной задачи уже содержатся в финальной строке под столбцами дополнительных переменных. В нашем примере значения и — это и есть оптимальные значения двойственных переменных. Они показывают ценность сырья и труда для данного производства.
Практические советы по расчету
Симплекс-метод крайне чувствителен к арифметическим ошибкам. Одно неверное деление в начале — и вся таблица «поплывет».
Линейное программирование — это фундамент, на котором строится логистика, планирование производства и даже алгоритмы поисковых систем. Освоив переход от графики к таблицам симплекс-метода, вы получаете ключ к решению огромного класса оптимизационных задач.