--- title: "Линейное программирование" source: "https://systems-analysis.info/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5" wiki: "systems-analysis.info/wiki" article: "Линейное_программирование" language: "ru" categories: - "Категория:Russian" - "Категория:Исследование операций" - "Категория:Математическое моделирование" revision_id: 272 wiki_created_at: 2026-09-06T22:06:25Z wiki_modified_at: 2026-09-06T22:06:25Z downloaded_at: 2026-09-07T22:18:46Z --- # Линейное программирование **Линейное программирование** — это раздел математического программирования и широко используемый метод исследования операций, посвящённый разработке теории и методов решения задач об отыскании экстремума (максимума или минимума) линейной функции при наличии линейных ограничений. ЛП является одним из наиболее мощных и часто применяемых инструментов для решения задач оптимизации в экономике, управлении, планировании, логистике и других областях. ## Предмет и назначение **Основная задача линейного программирования** — найти наилучший (оптимальный) способ распределения ограниченных ресурсов для достижения некоторой цели, когда и цель, и ограничения на использование ресурсов могут быть выражены линейными зависимостями. - Линейное программирование позволяет решать такие практические задачи, как: - Оптимальное планирование производства. - Оптимизация транспортных потоков (транспортная задача). - Оптимальное распределение инвестиций. - Оптимальный раскрой материалов. Задача о назначениях. ## Математическая постановка задачи ЛП Стандартная задача линейного программирования формулируется следующим образом: Требуется найти значения переменных решения, которые максимизируют или минимизируют линейную целевую функцию. При этом на переменные решения накладываются ограничения в виде системы линейных равенств и/или линейных неравенств. Как правило, добавляется условие неотрицательности переменных решения (их значения должны быть больше или равны нулю), что часто диктуется физическим или экономическим смыслом задачи. Математически это означает работу с линейными функциями и системами линейных уравнений/неравенств. ## Основные понятия ЛП - Переменные решения (Управляемые переменные): Величины, значения которых необходимо определить в процессе решения задачи (например, объемы производства различных продуктов, количество ресурсов, направляемых на разные цели). - Целевая функция: Линейная функция от переменных решения, значение которой требуется максимизировать или минимизировать. Она количественно выражает цель задачи (например, общая прибыль, суммарные издержки). - Ограничения: Система линейных равенств и/или неравенств, которым должны удовлетворять переменные решения. Ограничения отражают лимиты ресурсов, технологические требования, плановые задания и другие условия задачи. - Область допустимых решений (ОДР): Множество всех наборов значений переменных решения, которые удовлетворяют всем ограничениям задачи. Геометрически в многомерном пространстве ОДР представляет собой выпуклый многогранник (полиэдр), возможно, неограниченный или пустой. - Допустимое решение: Любой набор значений переменных, принадлежащий ОДР. - Оптимальное решение: Допустимое решение, при котором целевая функция достигает своего экстремального (максимального или минимального) значения. Если оптимальное решение существует, оно всегда находится на границе ОДР, как минимум в одной из вершин выпуклого многогранника ОДР (основная теорема ЛП). ## Методы решения задач ЛП Существует несколько основных методов для решения задач линейного программирования: - Графический метод: Применяется для задач с двумя переменными решения. Позволяет наглядно изобразить ОДР и целевую функцию на плоскости и найти оптимальное решение путем анализа вершин ОДР или перемещения линии уровня целевой функции. - Симплекс-метод: Универсальный итерационный алгоритм, разработанный Джорджем Данцигом. Метод последовательно переходит от одной вершины ОДР к соседней, улучшая значение целевой функции на каждом шаге, пока не будет найдено оптимальное решение. Является классическим и наиболее известным методом решения задач ЛП. - Методы внутренней точки: Альтернативный класс алгоритмов, появившихся позже симплекс-метода. Они движутся к оптимальному решению внутри ОДР, а не по её границам. Эти методы особенно эффективны для решения задач ЛП очень большой размерности. ## Двойственность в линейном программировании Каждой задаче линейного программирования (называемой прямой) можно сопоставить другую задачу ЛП, называемую двойственной. Прямая и двойственная задачи тесно связаны между собой: Решение одной задачи дает информацию о решении другой. Оптимальные значения целевых функций в обеих задачах совпадают (если они существуют). Переменные двойственной задачи имеют важную экономическую интерпретацию — они соответствуют теневым ценам (или двойственным оценкам) ресурсов, показывая, насколько изменится оптимальное значение целевой функции прямой задачи при небольшом изменении ограничения на соответствующий ресурс. ## Применение ЛП Линейное программирование находит широкое применение в: - Экономике и бизнесе (планирование производства, логистика, финансы, маркетинг). - Промышленности (оптимизация технологических процессов, управление запасами, раскрой материалов). - Транспорте (оптимизация маршрутов, расписаний). Сельском хозяйстве (оптимизация посевных площадей, рационов кормления). - Энергетике (оптимизация загрузки генерирующих мощностей). ## См. также - [Исследование операций](https://systems-analysis.info/wiki/%D0%98%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9 "Исследование операций") - [Оптимизация](https://systems-analysis.info/wiki/%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F "Оптимизация") - [Целевая функция](https://systems-analysis.info/wiki/%D0%A6%D0%B5%D0%BB%D0%B5%D0%B2%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F "Целевая функция") - [Ограничения](https://systems-analysis.info/wiki/%D0%9E%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%B5%D0%BD%D0%B8%D1%8F "Ограничения") - [Область допустимых решений](https://systems-analysis.info/wiki/%D0%9E%D0%B1%D0%BB%D0%B0%D1%81%D1%82%D1%8C_%D0%B4%D0%BE%D0%BF%D1%83%D1%81%D1%82%D0%B8%D0%BC%D1%8B%D1%85_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B9 "Область допустимых решений") - [Оптимальное решение](https://systems-analysis.info/wiki/%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 "Оптимальное решение") ## Литература - *Данциг Дж.* Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966. - *Юдин Д. Б., Гольштейн Е. Г.* Линейное программирование (теория, методы и приложения). — М.: Наука, 1969. - *Taha, Hamdy A.* Operations Research: An Introduction. — Pearson. (10th ed., 2017) - *Hillier, Frederick S.; Lieberman, Gerald J.* Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)