EssayAI
Блог
Блог
Естественные науки

Метод угловых точек в линейном программировании

8 ноября 2026Время чтения: 8 минут
#метод угловых точек#линейное программирование#оптимизация#допустимая область#целевая функция
Метод угловых точек в линейном программировании

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

Задача: два изделия и два ресурса

Пусть предприятие выбирает объёмы выпуска двух изделий: xx и yy. Это условная модель, а не данные реального производства. Изделия приносят соответственно 3 и 2 условные единицы прибыли за штуку. Объёмы считаем непрерывными: дробные значения допустимы. При целочисленных требованиях понадобится другая постановка.

На единицу каждого изделия расходуется одна единица первого ресурса, запас которого равен 6. На изделие xx уходит две единицы второго ресурса, на изделие yy - одна; второго ресурса доступно 8 единиц. Требуется максимизировать прибыль:

Z=3x+2y→max⁡,x+y≤6,2x+y≤8,x≥0,y≥0.Z=3x+2y\to\max,\qquad x+y\le 6,\quad 2x+y\le 8,\quad x\ge0,\quad y\ge0.

Ограничения описывают ресурсы и неотрицательность выпуска, а ZZ - целевую функцию. Допустимым называется любое сочетание, удовлетворяющее всем условиям одновременно. Например, (1;2)(1;2) допустимо, но (4;2)(4;2) нарушает второе ограничение: 2⋅4+2=10>82\cdot4+2=10>8. Первая задача решающего - проверить именно модель, а не сразу искать красивую точку на рисунке.

Почему достаточно проверить вершины

Каждое линейное неравенство задаёт полуплоскость. Их пересечение выпукло: если два плана допустимы, то и любой план на отрезке между ними допустим. В нашем примере получается ограниченный многоугольник. Для линейной функции на таком многоугольнике существует оптимальная вершина: всякая внутренняя точка представима как выпуклая комбинация вершин, а её значение ZZ - как такая же взвешенная комбинация значений в них. Оно не может превысить наибольшее из этих значений.

Это утверждение не означает, что оптимум обязан быть только вершиной. Если две соседние вершины дают одно лучшее значение, то весь соединяющий их отрезок тоже оптимален. Геометрия выпуклости связана с построением выпуклой оболочки, хотя здесь мы пересекаем полуплоскости, а не строим оболочку заданного набора точек.

Линия уровня 3x+2y=c3x+2y=c содержит все планы с одинаковой прибылью cc. При росте cc она сдвигается параллельно самой себе. Последнее касание ограниченной допустимой области показывает максимальный уровень.

Линия постоянной прибыли движется параллельно: её последний контакт с допустимой областью происходит в вершине (2; 4), после чего движение возвращается к началу.

Как построить область и найти её вершины

Сначала заменим неравенства равенствами x+y=6x+y=6 и 2x+y=82x+y=8. Первая прямая пересекает оси в (6;0)(6;0) и (0;6)(0;6), вторая - в (4;0)(4;0) и (0;8)(0;8). Поскольку начало координат удовлетворяет обоим неравенствам, для каждого ограничения выбираем сторону прямой, содержащую начало. Условия x≥0x\ge0 и y≥0y\ge0 дополнительно оставляют первый квадрант.

Пересечение двух ресурсных границ найдём решением системы:

x+y=6,2x+y=8.x+y=6,\qquad 2x+y=8.

Вычитание первого равенства из второго даёт x=2x=2, затем y=4y=4. Точка удовлетворяет обоим ограничениям и потому входит в область. На осях получаем другие вершины (4;0)(4;0) и (0;6)(0;6), а также начало координат (0;0)(0;0). Например, (6;0)(6;0) лежит на первой прямой, но не является допустимой вершиной: второе ограничение там нарушено.

Удобный общий алгоритм для двух переменных таков:

  1. Записать функцию, направление оптимизации и все ограничения, включая знаки переменных.
  2. Построить граничные прямые и выбрать общую допустимую область.
  3. Найти пересечения пар границ, включая оси, и отбросить точки, нарушающие хотя бы одно условие.
  4. Подставить координаты оставшихся вершин в целевую функцию и сравнить значения.
  5. Проверить, нет ли неограниченного улучшения или нескольких оптимальных планов, и записать ответ в единицах задачи.

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

Сравниваем значения в четырёх вершинах

Подставим координаты в Z=3x+2yZ=3x+2y:

Вершина (x;y)(x;y)Вычисление ZZЗначение
(0;0)(0;0)3⋅0+2⋅03\cdot0+2\cdot000
(4;0)(4;0)3⋅4+2⋅03\cdot4+2\cdot01212
(2;4)(2;4)3⋅2+2⋅43\cdot2+2\cdot41414
(0;6)(0;6)3⋅0+2⋅63\cdot0+2\cdot61212
Допустимый многоугольник и значения прибыли в четырёх вершинах: максимум 14 в точке (2; 4)
Допустимый многоугольник и значения прибыли в четырёх вершинах: максимум 14 в точке (2; 4)

Максимальная прибыль равна 14 условным единицам, план - x=2x=2, y=4y=4. Оба ресурса при нём исчерпаны: 2+4=62+4=6 и 2⋅2+4=82\cdot2+4=8. Такие ограничения называют активными. Это свойство относится именно к найденному плану: в другой задаче оптимум может оставлять часть ресурса неиспользованной.

Ответ можно независимо подтвердить верхней оценкой. Прибавим к первому ограничению второе: 3x+2y≤143x+2y\le14. Следовательно, ни один допустимый план не даст больше 14, а найденная точка достигает этой границы. Общий принцип таких оценок раскрывает теорема двойственности линейного программирования.

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

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

До использования результата стоит проверить и допущения модели. Постоянная прибыль на единицу и постоянный расход ресурсов предполагают линейность на всём рассматриваемом диапазоне. Скидки на сырьё, ограничения партий, спрос или время переналадки в исходной системе не учтены. При наличии таких условий их нужно включить в постановку или выбрать более подходящую модель; геометрическая точность сама по себе не исправит пропущенные условия.

Что меняется при другой прибыли

Пусть теперь Z=ax+2yZ=ax+2y, а ограничения прежние. В вершинах значения равны соответственно 00, 4a4a, 2a+82a+8 и 1212. Калькулятор изменяет aa от 1 до 5 и каждый раз сравнивает именно эти четыре величины. При a=3a=3 он воспроизводит исходный ответ (2;4)(2;4) и Z=14Z=14.

При a=2a=2 функция становится 2x+2y2x+2y: максимум 12 достигается в (0;6)(0;6) и (2;4)(2;4) и во всех точках между ними. Линия уровня совпадает с частью границы x+y=6x+y=6. При a=4a=4 максимум 16 достигается на всём отрезке между (2;4)(2;4) и (4;0)(4;0): линия уровня параллельна второй ресурсной границе. Между этими значениями единственная оптимальная вершина - (2;4)(2;4); ниже 2 выигрывает (0;6)(0;6), выше 4 - (4;0)(4;0).

Такой анализ показывает чувствительность решения к коэффициентам прибыли. Он не заменяет пересчёт при изменении запасов: тогда изменится сама допустимая область, и её вершины придётся определить заново.

Когда простой перебор требует осторожности

Допустимая область может быть пустой, если ограничения противоречат друг другу. Тогда допустимого плана и оптимума нет. Если область не ограничена, нужно проверить направление изменения цели: например, при x,y≥0x,y\ge0 максимум x+yx+y не существует, поскольку значение можно увеличивать без предела. Однако неограниченность области сама по себе не исключает конечного оптимума: минимум x+yx+y в том же квадранте достигается в начале координат.

При наличии оптимума на произвольном неограниченном множестве вершина вообще может отсутствовать: например, в полосе 0≤y≤10\le y\le1 при свободном xx максимум yy равен 1, но угловых точек нет. Поэтому безопасная формулировка для нашего алгоритма - непустой ограниченный многоугольник. В более общих задачах необходимы дополнительные условия и проверка направлений неограниченности. Эти различия обсуждаются в материалах MIT по графическому методу.

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

Частые ошибки

  • Проверять каждое ограничение отдельно. Точка должна удовлетворять всей системе, иначе она не кандидат на оптимум.
  • Забывать оси. При x,y≥0x,y\ge0 пересечения с ними могут быть вершинами, как (4;0)(4;0) в примере.
  • Округлять координаты до сравнения. Сначала решите системы точно, затем округляйте итог при необходимости.
  • Объявлять единственную точку при равенстве соседних вершин. В линейной задаче весь отрезок между ними даёт то же значение.
  • Игнорировать тип переменных. Если выпуск обязан быть целым, непрерывная модель может дать недопустимый дробный план.

FAQ

Можно ли найти минимум тем же методом?
Да. Для непустого ограниченного многоугольника сравните значения во всех вершинах и выберите наименьшее. Если соседние вершины дают одинаковый минимум, оптимален и соединяющий их отрезок.

Всегда ли пересечение двух граничных прямых является вершиной?
Нет. Оно должно удовлетворять всем ограничениям. Параллельные прямые могут не иметь общей точки, а пересечение вне допустимой области нужно отбросить.

Чем метод отличается от симплекс-метода?
В двумерном примере мы перечисляем и сравниваем все вершины. Симплекс-метод работает с базисными решениями и обычно переходит между ними по правилам улучшения; он применим и к задачам с большим числом переменных.

Коротко

Метод угловых точек сводит линейную оптимизацию на ограниченном многоугольнике к сравнению значений в его вершинах. В примере ограничения дают четыре вершины, а максимум 3x+2y=143x+2y=14 достигается при (2;4)(2;4). Перед выводом важно проверить допустимость каждой точки, наличие оптимума и возможность целого отрезка оптимальных решений.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Метод ветвей и границ в целочисленном программировании

Метод ветвей и границ в целочисленном программировании

Метод ветвей и границ для целочисленной задачи: LP-релаксация, верхняя оценка, ветвление по дробной переменной и доказательство оптимума на числовом примере.

8 ноября 20268 минут
Экономико-математические методы анализа: виды и пример

Экономико-математические методы анализа: виды и пример

Экономико-математические методы анализа: как выбрать модель, оценить связь показателей и найти оптимальный план выпуска с учётом ограниченных ресурсов.

7 ноября 20269 минут
Метод минимального элемента: транспортная задача

Метод минимального элемента: транспортная задача

Метод минимального элемента в транспортной задаче: пошаговый алгоритм начального плана, таблица тарифов, критерий оптимальности. Примеры и частые ошибки.

17 июня 20266 минут
Метод Ньютона в оптимизации: формула и пример

Метод Ньютона в оптимизации: формула и пример

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

8 ноября 20268 минут
Задача размещения производства: модель и пример

Задача размещения производства: модель и пример

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

8 ноября 20269 минут
Бинарный поиск по ответу: метод и примеры задач

Бинарный поиск по ответу: метод и примеры задач

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

11 июня 20267 минут