Математическое программирование — введение и постановка задач
Математика — это наука о количественных отношениях, пространственных формах и логических структурах, изучающая абстрактные объекты и связи между ними посредством дедуктивного метода, формальных языков и строгих доказательств; она служит универсальным инструментом моделирования реальности, позволяя выявлять закономерности, скрытые за хаосом наблюдений, и строить непротиворечивые системы знаний, применимые от фундаментальной физики до социальных процессов.
Операция — это целенаправленное действие или последовательность действий, выполняемая над одним или несколькими исходными объектами, данными или величинами, которая преобразует их в новый результат согласно заданному правилу, алгоритму или функциональной зависимости; в широком смысле операция включает любой акт преобразования, будь то арифметическое вычисление, логический вывод, технологический процесс или управленческое воздействие, причём её характеристики существенно зависят от контекста, допустимых преобразований и критериев успешности.
Исследование — это систематический процесс познания, направленный на получение новых знаний, проверку гипотез или углублённое понимание свойств, структур и закономерностей изучаемого объекта или явления; оно включает постановку проблемы, сбор и анализ эмпирических или теоретических данных, интерпретацию результатов и формулировку выводов, при этом исследование может быть фундаментальным, ориентированным на расширение границ знания, или прикладным, нацеленным на решение конкретной практической задачи, но в любом случае оно требует строгости, воспроизводимости и критической рефлексии.
Программирование — это творческий и инженерный процесс создания исполняемых инструкций для вычислительных машин или формальных систем, заключающийся в проектировании алгоритмов, выборе структур данных, написании исходного кода на искусственных языках, его отладке, тестировании и сопровождении; однако в более широком смысле программирование понимается как деятельность по формализации любой последовательной процедуры обработки информации, включая постановку задачи, декомпозицию на подзадачи, управление сложностью и адаптацию к изменяющимся условиям, причём оно неизбежно сочетает математическую логику, лингвистическое мышление и эвристическое принятие решений.
Математическое программирование — это раздел прикладной математики, изучающий теорию и методы нахождения экстремумов функций многих переменных при наличии ограничений на область допустимых значений; оно объединяет линейное, нелинейное, целочисленное, динамическое и стохастическое программирование, а также теорию игр и оптимального управления, и его суть состоит не в написании кода, а в строгой формализации задачи выбора наилучшего варианта из множества альтернатив, где цель, переменные и связи выражены в математических терминах, что позволяет применять мощный аналитический и вычислительный аппарат для обоснования решений в экономике, инженерии, логистике и военном деле.
Математическое программирование (англ. mathematical programming) — это поиск лучшего решения при ограничениях — максимум прибыли, минимум затрат, оптимальный маршрут.
Слово "программирование" здесь историческое — речь о плане и программе действий. Результаты затем реализуют в ПО.
Решение — это результат мыслительного или вычислительного акта, который устраняет неопределённость или разрешает проблемную ситуацию путём выбора одного из возможных вариантов действий, значений или интерпретаций; в математическом контексте решением называют совокупность значений неизвестных, удовлетворяющих заданным уравнениям или неравенствам, а в управленческом — это зафиксированное намерение совершить определённое действие, причём любое решение всегда принимается на основе имеющейся информации, критериев оценки и прогноза последствий, и оно может быть точным, приближённым, допустимым, оптимальным или эвристическим в зависимости от полноты данных и строгости метода.
Лучшее решение — это такое решение, которое превосходит все другие допустимые альтернативы по заранее определённому интегральному критерию качества или системе предпочтений, при этом понятие «лучше» всегда относительное и зависит от выбранной целевой функции, весовых коэффициентов, учёта рисков и временного горизонта; в строгой математической постановке лучшее решение соответствует глобальному экстремуму (максимуму или минимуму) показателя эффективности в заданной области, однако на практике оно часто понимается как парето-оптимальный или компромиссный вариант, когда невозможно улучшить один показатель без ухудшения другого, а также учитывает устойчивость к возмущениям и простоту реализации.
Ограничения — это условия, связи или границы, которые сужают множество допустимых вариантов при принятии решения или построении модели, выраженные в виде равенств, неравенств, логических условий, ресурсных лимитов, временных рамок, законодательных норм или физических законов; они играют двойственную роль: с одной стороны, они препятствуют достижению абсолютно идеального результата, с другой — придают задаче реалистичность, структуру и направляют поиск, отсекая заведомо невозможные или недопустимые альтернативы, причём в математическом программировании ограничения являются неотъемлемой частью постановки, и их характер (жёсткие или мягкие, линейные или нелинейные, детерминированные или вероятностные) определяет выбор метода решения.
Максимум — это наибольшее значение, которое может принимать некоторая функция, величина или показатель на заданном множестве допустимых аргументов или состояний; в строгом анализе различают локальный максимум, достигаемый в окрестности точки, и глобальный максимум, который является абсолютным рекордом во всей области определения, причём максимум может существовать или не существовать в зависимости от компактности множества и непрерывности функции, а в прикладных задачах под максимумом часто понимают не просто числовой пик, а наиболее предпочтительное состояние системы, соответствующее предельным возможностям при данных ограничениях, и его поиск составляет ядро оптимизационных дисциплин.
Оптимальный маршрут — это путь или последовательность переходов между заданными точками пространства, состояний или этапов процесса, который обеспечивает наилучшее значение выбранного критерия эффективности среди всех возможных путей, удовлетворяющих существующим ограничениям; таким критерием может быть минимальное время, наименьшая длина, минимальный расход топлива, максимальная безопасность, наибольшая пропускная способность или комплексный взвешенный показатель, причём оптимальность маршрута зависит не только от геометрии или топологии, но и от динамических факторов, таких как изменение скорости, загрузка узлов, случайные помехи или приоритеты, и его построение обычно требует применения методов теории графов, динамического программирования или эвристических алгоритмов.
План и программа действий — это формализованная последовательность взаимосвязанных шагов, этапов, операций или мероприятий, направленная на достижение поставленной цели в условиях определённых ресурсных, временных и организационных рамок, причём план задаёт жёсткую или гибкую структуру с указанием сроков, ответственных и контрольных точек, а программа действий представляет более развёрнутый вариант, включающий альтернативные ветви, резервные сценарии, правила пересмотра и механизмы координации; в широком смысле это инструмент перевода стратегических намерений в операциональную реальность, который сочетает прогнозирование, распределение ресурсов, синхронизацию и управление рисками, и его качество определяется полнотой охвата существенных факторов, реалистичностью допущений и адаптивностью к изменяющимся обстоятельствам.
Результаты — это фактические итоги, выходные данные или конечные состояния, которые получены по завершении некоторого процесса, эксперимента, вычисления или реализации плана; они могут быть количественными (числа, графики, статистики), качественными (выводы, классификации, оценки) или комбинированными, причём важнейшим свойством результатов является их измеримость и сопоставимость с ожиданиями, гипотезами или целевыми ориентирами; в науке и практике результаты служат основой для верификации теорий, принятия новых решений, корректировки стратегий и накопления опыта, однако их ценность определяется не только точностью, но и полнотой интерпретации, учётом погрешностей, контекстом применения и возможностью воспроизведения, а также тем, насколько они позволяют сделать следующий шаг в познании или улучшении деятельности.
В разделе Динамическое программирование и уравнение Беллмана — уравнение Беллмана и поэтапная оптимизация (исследование операций).
В разделе Алгоритмы и лаборатории — мемоизация и таблицы для задач вроде рюкзака. Термин один, области разные; мы явно разводим их по контексту.
Математическое программирование (МП, исследование операций) отвечает на вопрос — какое решение из допустимых будет лучшим по заданному критерию? В инженерной практике те же постановки встречаются в планировании релизов, распределении нагрузки, логистике и в солверах вроде scipy.optimize или Google OR-Tools.
Предварительно полезны — линейная алгебра, дискретная математика (графы для транспортных и сетевых задач). Глубокая алгебра для старта не обязательна — ниже — минимум обозначений, которого хватит, чтобы читать остальные статьи раздела.
Как читать записи, если математика давно не вспоминалась
В этом разделе встречаются буквы с индексами, суммы и знаки сравнения. Их можно читать как "таблицу в Excel", только записанную компактно.
Буквы с индексами — это способ обозначения переменных, параметров или элементов множества, при котором к основному символу добавляются нижние, верхние или комбинированные дополнительные знаки (цифры, латинские или греческие литеры), служащие для уточнения принадлежности, номера, состояния, временного слоя или иного атрибута; индексы превращают одиночный символ в информационно насыщенный идентификатор, позволяя различать, например, координаты точки в многомерном пространстве, члены последовательности, коэффициенты при неизвестных в системе уравнений или компоненты тензора, причём система индексации должна быть согласованной и однозначно интерпретируемой, чтобы избежать путаницы при выкладках.
Суммы — это результат операции сложения двух или более величин, а также сам математический объект, выражаемый через знак агрегации, будь то обычный плюс между конечным числом слагаемых или символ суммирования для бесконечных рядов и конечных наборов; в более абстрактном смысле сумма обобщается на векторы, матрицы, функции, числовые поля и даже логические высказывания, сохраняя свойства коммутативности и ассоциативности там, где это определено, и выступает фундаментальным инструментом накопления, усреднения, интегрирования и агрегирования данных, позволяя сводить множественные единичные эффекты к итоговому показателю.
Знаки сравнения — это графические или логические символы, выражающие отношения между двумя объектами, величинами или выражениями, такие как равенство, неравенство, строгое или нестрогое больше/меньше, эквивалентность, пропорциональность или принадлежность к числовому промежутку; они не только фиксируют объективное соотношение, но и задают правила преобразования — например, при умножении обеих частей неравенства на отрицательное число знак меняет направление, что делает их активными операторами в логических выводах, а в более широком контексте они служат основой для классификации, упорядочивания, отбора допустимых вариантов и построения оценочных шкал в любых измеримых системах.
Икс и игрек (x и y) — это традиционные буквенные обозначения неизвестных или варьирующихся величин, где икс чаще всего выступает первой независимой переменной или аргументом функции, а игрек — зависимой переменной, значением функции или второй координатой на плоскости, хотя их роли могут меняться в зависимости от контекста; эти символы, укоренённые в европейской математической традиции через декартову систему координат, стали архетипическими маркерами неизвестности и функциональной связи, и их использование предполагает не только формальную подстановку чисел, но и целую культуру оперирования с параметрами, где икс и игрек воплощают идею переменной как подвижной, абстрактной сущности, готовой принять любое значение из допустимого множества.
| Запись | Читается по-русски | Простой смысл |
|---|---|---|
x₁, x₂ | "икс один", "икс два" | переменные — числа, которые мы подбираем (объёмы, доли, маршруты) |
3x₁ + 2x₂ | "три икс один плюс два икс два" | линейная цель — прибыль или затраты складываются из вкладов каждой переменной |
≤ 8 | "меньше или равно восьми" | потолок — суммарный расход ресурса не больше запаса |
≥ 0 | "неотрицательные" | отрицательный объём производства в модели обычно запрещён |
max Z / min Z | максимизировать / минимизировать Z | Z — значение цели (прибыль, стоимость, время) в выбранном плане |
cᵀx | "цэ транспонированное на икс" | сокращение для c₁x₁ + … + cₙxₙ — та же цель в компактном виде |
Ax ≤ b | "А икс меньше или равно бэ" | несколько ограничений сразу — каждая строка матрицы A — одно правило |
Потолок — в математике это функция, сопоставляющая каждому действительному числу наименьшее целое число, которое не меньше данного, обозначаемая как верхнее целое, при этом она является парной к функции пола и часто используется в дискретной математике, теории вычислений и оптимизации для округления вверх; однако в переносном и прикладном смысле потолок означает верхнюю границу, предельный уровень или допустимый максимум, который нельзя превысить, будь то бюджетное ограничение, физический предел прочности, пропускная способность канала или нормативное значение, и тогда он становится жёстким ограничением в задаче, формирующим область допустимых решений.
Линейность — это фундаментальное свойство математического объекта, операции или системы, выражающееся в выполнении двух основных принципов: аддитивности, то есть результат воздействия на сумму равен сумме результатов воздействия на отдельные части, и однородности, то есть пропорционального изменения результата при масштабировании аргумента; линейность обеспечивает предсказуемость, суперпозицию и простоту анализа, позволяя разбивать сложные задачи на независимые компоненты и использовать мощные матричные методы, однако в реальных процессах линейность часто является лишь приближением, и её нарушение переводит задачу в область нелинейной динамики, где поведение становится качественно более богатым и менее тривиальным.
Линейность в бытовом смысле — если удвоить выпуск изделия A, удваивается и его расход станка (без "скидки за объём" и без квадратов). В формулах — только умножение переменной на число-коэффициент, без x₁², 1/x₁, sin(x₁).
План — конкретный набор чисел (x₁, …, xₙ), который удовлетворяет всем ограничениям. Оптимальный план — среди допустимых тот, у которого цель Z лучше всех (больше при max, меньше при min).
В задаче max Z = 5x₁ + 4x₂ при x₁=1, x₂=2 подставьте: Z = 5·1 + 4·2 = 13. Ограничение x₁ + x₂ ≤ 10 при этих значениях: 1+2=3 ≤ 10 — план допустим по этому правилу (нужно ещё проверить остальные).
Минимизация — это процесс поиска наименьшего возможного значения целевой функции на допустимом множестве переменных, являющийся зеркальным отражением максимизации и составляющий ядро оптимизационных дисциплин; она требует не только вычисления экстремумов, но и доказательства того, что найденная точка действительно является глобальным минимумом, а не локальным, причём в зависимости от структуры функции и ограничений минимизация может быть гладкой или негладкой, выпуклой или многоэкстремальной, и в практическом плане она означает стремление к экономии ресурсов, снижению затрат, уменьшению ошибок или сокращению времени, что делает её универсальным принципом рационального действия.
Транспонирование — это операция над матрицей или тензором, при которой строки меняются местами со столбцами, то есть элемент, стоящий на пересечении i-й строки и j-го столбца, перемещается на позицию с индексами j и i, причём эта операция обратима и не меняет главную диагональ; в более широком смысле транспонирование понимается как преобразование структуры данных, при котором меняется ориентация системы отсчёта или переиндексируются координаты, и оно играет критическую роль в линейной алгебре, теории операторов, дифференциальной геометрии и статистике, поскольку через него определяются симметричные, кососимметричные и ортогональные матрицы, а также сопряжённые операторы в скалярных произведениях.
Прибавление — это арифметическое действие, состоящее в увеличении исходной величины на некоторое другое значение, называемое слагаемым, в результате чего получается сумма, причём это действие коммутативно и ассоциативно в большинстве числовых систем; однако в более широком контексте прибавление можно понимать как любую операцию объединения, дополнения или инкремента, которая добавляет новый элемент к существующему множеству, увеличивает интенсивность процесса или расширяет область охвата, и оно является базовым строительным блоком для итеративных алгоритмов, накопления статистик и моделирования роста.
Вычитание — это арифметическое действие, обратное прибавлению, при котором от одной величины отнимается другая, называемая вычитаемым, чтобы найти разность, и оно не обладает коммутативностью или ассоциативностью, что вносит важную асимметрию в вычисления; в более широком смысле вычитание интерпретируется как удаление, сравнение или оценка расстояния между двумя объектами, а также как операция взятия относительной разности, и оно лежит в основе таких понятий, как изменение, приращение, остаток, дефицит и погрешность, причём в алгебре вычитание эквивалентно прибавлению отрицательного числа, что позволяет унифицировать его с более общими структурами.
Умножение — это бинарная операция, которая по двум данным величинам (множителям) ставит в соответствие третью величину — произведение, причём в арифметике она трактуется как многократное сложение, но в алгебре, анализе и теории чисел её смысл существенно расширяется: это композиция преобразований, перемножение матриц, свёртка функций, скалярное произведение векторов или умножение в группах и кольцах; умножение обычно обладает дистрибутивностью относительно сложения, ассоциативностью и, в коммутативных случаях, симметрией, и оно является ключевым инструментом для масштабирования, изменения размерности, вычисления площадей, объёмов и вероятностей совместных событий.
Деление — это операция, обратная умножению, при которой для заданных делимого и делителя ищется частное — такое число, которое при умножении на делитель даёт делимое, при этом деление на ноль исключено из-за логической противоречивости; в более широком смысле деление интерпретируется как разбиение целого на равные или пропорциональные части, определение доли, нормировка, вычисление среднего или плотности, а также как решение уравнения относительно неизвестного множителя, причём оно некоммутативно и неассоциативно, и в зависимости от контекста может выполняться точно (в рациональных числах), с остатком (в целых) или приближённо (в численных методах).
Квадрат — это результат умножения числа или выражения на само себя, то есть возведение во вторую степень, что геометрически интерпретируется как площадь квадрата со стороной, равной данному числу; в алгебре квадрат выделяется как особый случай степенной функции, обладающий свойствами чётности, неотрицательности для действительных аргументов и широкой применимостью в формулах сокращённого умножения, решении уравнений, статистической дисперсии и теории норм, при этом обратная операция — извлечение квадратного корня — тесно связана с понятием расстояния и метрики.
Арифметика — это древнейший раздел математики, изучающий количественные отношения на уровне чисел и четырёх основных действий — сложения, вычитания, умножения и деления, а также их производных, таких как возведение в степень, извлечение корня и действия с дробями, процентами и пропорциями; она служит фундаментальным языком для повседневных расчётов и базовым слоем для всех более высоких математических построений, отличается наглядностью, алгоритмичностью и тесной связью с интуитивными представлениями о количестве, однако в теоретическом плане арифметика включает также теорию делимости, простых чисел и систем счисления, выходя за рамки элементарных выкладок.
Алгебра — это раздел математики, который обобщает арифметику, вводя абстрактные символы вместо конкретных чисел и изучая структуры, операции и их свойства в самом общем виде, такие как группы, кольца, поля, модули и векторные пространства; она даёт мощный язык для описания закономерностей, преобразований и инвариантов, позволяя решать уравнения, системы, исследовать функции и строить алгебраические модели любых процессов, причём её сила заключается в формальной манипуляции символами по строгим правилам, что делает алгебру не просто набором приёмов, а целым способом мышления о структурах и отношениях.
Удвоение — это специфическая операция умножения на два, которая в арифметике сводится к прибавлению числа к самому себе и широко используется в двоичной системе счисления, пропорциях, масштабировании и рекурсивных алгоритмах; в более общем смысле удвоение означает создание точной или пропорциональной копии, увеличение интенсивности, объёма или силы в два раза, и оно служит простейшим примером геометрической прогрессии и экспоненциального роста, а также часто фигурирует в задачах деления пополам, оптимизации шага итерации и построении циклов с постоянным множителем.
Сокращение — это преобразование алгебраического или арифметического выражения, при котором общие множители в числителе и знаменателе дроби, подобные слагаемые или одинаковые сомножители в произведении исключаются, чтобы упростить запись без изменения значения, при условии, что сокращаемые величины не равны нулю; в более широком смысле сокращение понимается как любое редукционное действие — уменьшение размерности задачи, удаление избыточных переменных, упрощение логической формулы или приведение сложной системы к более компактной, но эквивалентной форме, что является важнейшим приёмом в аналитической работе, позволяющим обнажить суть и снизить вычислительную сложность.
Коэффициент — это числовой или буквенный множитель, стоящий перед переменной, степенью или целым выражением в алгебраическом термине, который показывает, сколько раз данная величина входит в сумму или произведение; однако в более широком и переносном смысле коэффициент означает любой относительный показатель, нормирующий множитель или масштабирующий параметр, например коэффициент полезного действия, корреляции, трения или эластичности, и он играет роль связующего звена между чистой математикой и конкретными дисциплинами, поскольку через коэффициенты выражаются пропорциональные зависимости, чувствительности и весовые значимости различных факторов в модели.
Формула — это символическая запись, составленная из букв, чисел, знаков операций и скобок, которая выражает некоторое тождество, закон, зависимость или правило вычисления, причём она является сжатым и однозначным кодированием математического знания, допускающим подстановку значений, преобразования и вывод следствий; формулы служат основным языком естественных и точных наук, они могут быть линейными, рекуррентными, интегральными, дифференциальными или логическими, и их создание требует не только формальной корректности, но и осмысленного выбора переменных, чтобы отражать сущность описываемого явления, а их красота и эвристическая сила часто ценятся наравне с содержательной интерпретацией.
Оптимальность — это свойство выбранного решения или состояния, означающее, что оно достигает наилучшего возможного значения заданной целевой функции среди всех допустимых альтернатив, причём это понятие всегда относительно системы критериев, граничных условий и принятых допущений о неопределённости; оптимальность не является абсолютной характеристикой — она может быть локальной или глобальной, слабой или сильной, парето-оптимальной или минимаксной, и её достижение требует баланса между стремлением к экстремуму и учётом реалистичных ограничений, а также часто предполагает компромисс между конфликтующими целями, что делает оптимальность не просто математическим итогом, а философским ориентиром рациональной деятельности, где ценятся не только численные показатели, но и устойчивость, практичность и этическая допустимость.
Маршрут по разделу
| № | Тема | Статья |
|---|---|---|
| 1 | Постановка, формы ЗЛП | эта статья |
| 2 | Выпуклость, свойства, графический метод | Выпуклые множества, свойства ЗЛП и графический метод |
| 3 | Метод Жордана–Гаусса | Метод Жордана–Гаусса в задачах линейного программирования |
| 4 | Симплекс-метод и таблицы | Симплекс-метод и симплекс-таблицы |
| 5 | Искусственный базис и M-метод | Искусственный базис и M-метод |
| 6 | Двойственность, двойственный симплекс | Двойственность в линейном программировании |
| 7 | Транспортная задача | Транспортная задача |
| 8 | Динамическое программирование, Беллман | Динамическое программирование и уравнение Беллмана |
| 9 | Решатели в коде | Решение задач оптимизации в коде |
Термины раздела — в итогах и терминологии.
Общая схема задачи оптимизации
Любая задача МП в "инженерном" виде состоит из трёх частей —
- Переменные решения
x₁, …, xₙ— то, что мы выбираем (объёмы производства, маршруты, доли бюджета). - Целевая функция
F(x)— что улучшаем (прибыль, время, риск, отклонение от плана). - Ограничения — что допустимо (ресурсы, законы, SLA, физические лимиты).
Переменные решения — это совокупность независимых величин, значения которых подлежат сознательному выбору в рамках оптимизационной задачи, и именно они составляют основу искомого плана, режима или стратегии; каждая такая переменная отражает один из управляемых факторов, будь то объём выпуска продукции, распределение ресурсов, направление инвестиций или временные интервалы, и их набор должен быть полным, непротиворечивым и достаточным для описания всех существенных альтернатив, притом что допустимые значения переменных ограничиваются внешними условиями, а их изменение напрямую влияет на значение целевой функции.
Целевая функция — это формализованное математическое выражение, ставящее в соответствие каждому допустимому набору переменных решения одно числовое значение, которое служит мерой качества, эффективности или предпочтительности данного варианта; она агрегирует разрозненные критерии в единый скалярный показатель, подлежащий максимизации, когда речь идёт о прибыли, полезности или надёжности, либо минимизации, если оцениваются затраты, время или риски, причём вид целевой функции, её линейность или нелинейность, гладкость и выпуклость во многом предопределяют выбор метода поиска оптимума и сложность всей задачи.
Ограничения — это система формальных условий, выраженных в виде равенств, неравенств или логических импликаций, которые сужают множество допустимых значений переменных решения, отражая реальные ресурсные, технические, технологические, бюджетные, правовые или природные пределы; они играют двойственную роль — с одной стороны, они препятствуют достижению абсолютно идеального (но часто нереалистичного) результата, с другой — придают задаче содержательный смысл, поскольку именно ограничения делают задачу нетривиальной, а их структура (жёсткие или мягкие, линейные или нелинейные, детерминированные или стохастические) определяет границы поиска и требует специальных методов приведения к каноническому виду.
Запись в общем виде —
АЛГОРИТМ ЗадачаОптимизации()
выбрать числа x1, x2, …, xn // план: объёмы, маршруты, доли бюджета
пока не все_ограничения_выполнены(x)
отбросить этот план
конец
среди оставшихся максимизировать Цель(x) // или минимизировать затраты
вернуть лучший_план
КОНЕЦ
найти x = (x₁, …, xₙ)
чтобы F(x) → max (или → min)
при gᵢ(x) ≤ 0, i = 1..m
hⱼ(x) = 0, j = 1..k
(часто ещё x ≥ 0)
Справочно — та же пекарня в формулах: max Z = 3x₁ + 2x₂ при 2x₁ + x₂ ≤ 100, x₁ + x₂ ≤ 80, x₁, x₂ ≥ 0.
Допустимое множество — все x, удовлетворяющие ограничениям. Оптимальное решение — допустимая точка, где F лучше, чем в любой другой допустимой точке (глобальный оптимум; локальный — лучший только в окрестности).
Множество — это фундаментальное математическое понятие, обозначающее совокупность любых объектов, объединённых по некоторому признаку, которое рассматривается как единое целое, причём сами объекты называются элементами множества; в контексте оптимизации множество выступает как абстрактный контейнер для всех возможных комбинаций переменных решения, и именно его структура — конечное оно или бесконечное, связное или дискретное, выпуклое или невыпуклое — определяет принципиальную сложность задачи, а также позволяет применять мощные теоретико-множественные инструменты, такие как отображения, отношения, включения и операции объединения, пересечения, дополнения.
Допустимость — это свойство конкретного набора переменных решения, которое означает, что данный набор удовлетворяет всем наложенным ограничениям без единого исключения, то есть принадлежит допустимому множеству, определяемому системой равенств, неравенств и целочисленных условий; допустимость является необходимым условием для того, чтобы вариант мог быть вообще рассмотрен в качестве претендента на оптимальное решение, и проверка допустимости часто требует разрешимости систем уравнений и неравенств, причём в реальных задачах нередко оказывается, что область допустимых значений пуста, что сигнализирует о противоречивости исходных требований, либо, напротив, слишком широка, что затрудняет направленный поиск.
Схема построения экономико-математической модели
ЗЛП и ЗЦЛП — это стандартные аббревиатуры, обозначающие задачу линейного программирования и задачу целочисленного линейного программирования соответственно; в первой все зависимости, как целевая функция, так и ограничения, являются линейными относительно переменных решения, а сами переменные могут принимать любые действительные значения из непрерывной области, что позволяет использовать симплекс-метод или методы внутренней точки, тогда как вторая отличается дополнительным требованием целочисленности всех или части переменных, что резко меняет природу задачи, делая её дискретной, NP-трудной в общем случае и требующей методов ветвей и границ, отсечений или динамического программирования, причём целочисленность часто возникает из-за неделимости объектов, таких как количество станков, вагонов или работников.
Экономико-математическая модель — это формализованное описание экономического объекта, процесса или системы на языке математических соотношений, которое включает переменные решения, целевую функцию, ограничения, параметры и внешние факторы, причём такая модель строится с целью анализа, прогнозирования и оптимизации хозяйственной деятельности; она является компромиссом между полнотой отражения реальности и математической трактуемостью, поэтому в ней сознательно выделяются главные связи и отбрасываются второстепенные, а её ценность определяется не столько сложностью, сколько адекватностью, валидностью и возможностью содержательной интерпретации получаемых результатов, будь то плановые показатели, цены, балансы или инвестиционные решения.
В учебниках по ЗЛП экстремальную задачу из текста переводят в формулы по одному и тому же каркасу —
- Выбрать переменные
xⱼ— числа, однозначно задающие план (объёмы продукции, килограммы корма, объёмы перевозок). - Записать ограничения — линейные равенства и неравенства, отражающие запасы, нормы, балансы.
- Ввести целевую функцию
Z— критерий, который нужно максимизировать или минимизировать.
Дальше модель приводят к стандартной или канонической форме для симплекса или солвера.
Разбор общей записи по строкам
Общая запись по строкам — это способ компактного и структурированного представления оптимизационной задачи, при котором каждое ограничение, целевая функция и условия неотрицательности или целочисленности выписываются в отдельных строках, часто с использованием матричной нотации, где коэффициенты при переменных упорядочиваются в виде таблицы; такая форма облегчает восприятие задачи человеком, позволяет легко идентифицировать каждое условие, сравнивать правые и левые части, а также служит удобным входным форматом для вычислительных алгоритмов, поскольку симплекс-метод и другие численные процедуры непосредственно оперируют именно с построчным представлением расширенной матрицы коэффициентов.
найти x = (x₁, …, xₙ)
чтобы F(x) → max (или → min)
при gᵢ(x) ≤ 0, i = 1..m
hⱼ(x) = 0, j = 1..k
(часто ещё x ≥ 0)
| Строка | Что означает на практике |
|---|---|
найти x | подобрать числа (объёмы, маршруты, доли бюджета) |
F(x) → max | сделать прибыль/полезность как можно больше |
gᵢ(x) ≤ 0 | семейство ограничений-"потолков" (ресурсы, квоты, SLA) |
hⱼ(x) = 0 | жёсткие равенства (баланс "вошло = вышло", закон сохранения) |
x ≥ 0 | переменные не могут быть отрицательными в этой модели |
В учебниках по ЗЛП чаще пишут Ax ≤ b и x ≥ 0 — это тот же смысл, только ограничения записаны в виде неравенств с неотрицательными правыми частями b.
| Вид задачи | Целевая функция и ограничения | Типичный метод |
|---|---|---|
| Линейное программирование (ЗЛП) | всё линейно | симплекс, внутренние точки |
| Целочисленное (ЗЦЛП) | линейно + часть переменных целые | отсечения, ветви и границы |
| Квадратичное | квадратичная цель, линейные ограничения | специализированные солверы |
| Нелинейное | нелинейные F или g | градиентные, эвристики |
| Динамическое (Беллман) | решение по этапам | уравнение Беллмана |
В этом разделе основной упор — на линейное программирование и связанные классические алгоритмы, плюс динамическое программирование в смысле Беллмана.
Линейное программирование (ЗЛП)
Задача линейного программирования — F и все ограничения линейны по переменным — только суммы вида a₁x₁ + … + aₙxₙ, без x₁², sin(x), произведений x₁·x₂.
Стандартная форма максимизации (часто используют в учебниках и в симплекс-таблицах) —
max Z = c₁x₁ + c₂x₂ + … + cₙxₙ
при a₁₁x₁ + … + a₁ₙxₙ ≤ b₁
…
aₘ₁x₁ + … + aₘₙxₙ ≤ bₘ
x₁, …, xₙ ≥ 0
Минимизацию сводят к максимизации: min F ⇔ max (−F) (с теми же ограничениями, если только меняется знак цели).
Другие формы записи
Формы записи — это различные стандартизованные варианты представления одной и той же оптимизационной задачи, среди которых выделяют общую форму, где ограничения могут быть любого типа и переменные произвольного знака, каноническую форму, где все ограничения суть равенства с неотрицательными правыми частями, а переменные неотрицательны, и симметричную форму, где все неравенства имеют единообразное направление; выбор конкретной формы записи диктуется не столько содержанием, сколько удобством применения конкретного метода решения — например, симплекс-метод требует канонического вида, а двойственные оценки естественно возникают в симметричной форме, причём переход между формами осуществляется с помощью введения дополнительных или балансовых переменных, а также замены разностью неограниченных переменных.
| Форма | Суть | Как привести к стандарту |
|---|---|---|
| Каноническая | только равенства =, переменные ≥ 0 | неравенства ≤ → добавочные (slack) переменные; ≥ → избыточные (surplus) |
С ограничениями ≥ | "не меньше" ресурса | surplus-переменная со знаком "минус" в строке или умножение строки на −1 |
| Свободные переменные (любой знак) | баланс, разница доход−расход | замена x = x⁺ − x⁻, обе ≥ 0 |
| Минимизация | затраты, время | min Z → max (−Z) |
Приведение неравенств к равенствам (slack, surplus), смешанные ограничения и каноническая форма — в главе 3.
Матричная запись
max cᵀx
при Ax ≤ b
x ≥ 0
Здесь c — коэффициенты цели, A — матрица ограничений, b — правые части (запасы ресурсов). Одна строка A — одно ограничение.
Пример чтения одной строки. Пусть c = (5, 4), первая строка A — (1, 1), b₁ = 10. Тогда —
- цель:
Z = 5x₁ + 4x₂(каждая единицаx₁даёт +5 кZ); - ограничение:
1·x₁ + 1·x₂ ≤ 10, то естьx₁ + x₂ ≤ 10— сумма двух величин не больше 10.
Вектор x = (x₁, x₂) — столбец значений переменных; запись cᵀx — способ не писать плюсы вручную, когда переменных десятки.
Три классических примера постановки
Постановка — это начальный и ответственный этап решения любой оптимизационной задачи, заключающийся в чётком словесном и затем математическом формулировании всех её элементов: что именно ищется, в каких пределах, по какому критерию и при каких условиях; грамотная постановка требует выявления управляемых факторов и неуправляемых параметров, выбора целевого показателя, обоснования системы ограничений, проверки на непротиворечивость и размерность, а также предварительного анализа того, существует ли решение вообще и имеет ли оно практический смысл, поскольку неполная, двусмысленная или избыточная постановка сводит на нет все последующие вычисления и делает результаты недоверчивыми или бесполезными для принятия решений.
Ниже — три шаблона постановки. Числа можно менять, структура остаётся той же.
Сюжет. Выпускают n видов продукции Pⱼ, расходуя m видов сырья Sᵢ с запасами bᵢ. На единицу Pⱼ уходит aᵢⱼ единиц Sᵢ, прибыль с единицы — cⱼ.
Переменные — xⱼ ≥ 0 — объём выпуска продукта j.
max Z = c₁x₁ + … + cₙxₙ
при a₁₁x₁ + … + a₁ₙxₙ ≤ b₁
…
aₘ₁x₁ + … + aₘₙxₙ ≤ bₘ
xⱼ ≥ 0
В табличном виде — строки "сырьё", столбцы "продукты", в ячейке aᵢⱼ, справа запас bᵢ, внизу прибыль cⱼ.
2. Рацион питания (диета, смесь)
Сюжет. Смесь из кормов P₁, P₂, P₃ должна содержать не меньше норм по питательным веществам Sᵢ, стоимость 1 кг корма j — cⱼ. Нужно минимизировать стоимость.
Переменные — xⱼ — килограммы корма j.
min Z = c₁x₁ + c₂x₂ + c₃x₃
при a₁₁x₁ + a₁₂x₂ + a₁₃x₃ ≥ b₁ (норма по веществу 1)
…
a₅₁x₁ + … + a₅₃x₃ ≥ b₅
xⱼ ≥ 0
Типичная таблица — строки "питательные вещества", столбцы "корма", нормы bᵢ, цены cⱼ в последней строке. Ограничения ≥ — признак задачи на минимум затрат при обязательных нормах.
3. Транспортная задача
Перевозки от поставщиков к потребителям при линейных тарифах — частный случай ЗЛП со своей таблицей и алгоритмами. Полная постановка, балансировка и метод потенциалов — в главе 7.
Пример — план производства двух изделий (частный случай n = 2)
Сюжет. Цех выпускает два типа деталей — A и B. Нужно выбрать объёмы x₁, x₂ (тысячи штук в месяц), чтобы максимизировать прибыль, не превысив фонд времени станков и склад сырья.
| Ресурс | Норма на 1000 шт. A | Норма на 1000 шт. B | Запас |
|---|---|---|---|
| Станки (ч) | 2 | 1 | 8 |
| Сырьё (кг) | 1 | 2 | 8 |
Прибыль — 3 у.е. за 1000 шт. A, 2 у.е. за 1000 шт. B.
Переменные — x₁ — тысячи шт. A, x₂ — тысячи шт. B.
Цель —
max Z = 3x₁ + 2x₂
Ограничения —
2x₁ + x₂ ≤ 8 (станки)
x₁ + 2x₂ ≤ 8 (сырьё)
x₁, x₂ ≥ 0
Разбор левой части первого ограничения. Если выпустить x₁ = 2 (тыс. шт. A) и x₂ = 1 (тыс. шт. B) —
2x₁ + x₂ = 2·2 + 1 = 5 ≤ 8
Станки заняты на 5 часов из 8 — запас есть. Второе ограничение — x₁ + 2x₂ = 2 + 2 = 4 ≤ 8 — сырьё тоже не исчерпано. План (2, 1) допустим — прибыль 3·2 + 2·1 = 8. Оптимум в статье 2 — около 13,33.
План (x₁, x₂) | Z = 3x₁ + 2x₂ | Станки 2x₁+x₂ | Сырьё x₁+2x₂ |
|---|---|---|---|
| (0, 0) | 0 | 0 ≤ 8 ✓ | 0 ≤ 8 ✓ |
| (4, 0) | 12 | 8 ≤ 8 ✓ | 4 ≤ 8 ✓ |
| (8/3, 8/3) | 40/3 ≈ 13,33 | 8 ✓ | 8 ✓ |
Это типичная учебная ЗЛП на две переменные — её удобно решать графически (статья 2), а затем проверить симплексом (статья 4).
Интерпретация в IT — те же числа могут означать "сколько инстансов сервиса A и B поднять", если каждый потребляет CPU/RAM по таблице, а цель — максимизировать обработанные запросы при лимите кластера.
Пример — смешивание (диета, два компонента)
Частный случай рациона из блока выше — два корма, две нормы. Нужно набрать смесь так, чтобы минимизировать стоимость, но выполнить нормы по нутриентам.
min Z = 40x₁ + 30x₂
при 2x₁ + x₂ ≥ 12 (белок)
x₁ + 3x₂ ≥ 18 (углеводы)
x₁, x₂ ≥ 0
Здесь ограничения "≥" — типичный повод ввести избыточные переменные или переписать строку (см. статью 3). Для симплекса часто переходят к эквивалентной задаче максимизации с преобразованными строками.
Смысл коэффициентов в диете. Строка 2x₁ + x₂ ≥ 12 читается так — в смеси из x₁ порций продукта 1 и x₂ порций продукта 2 суммарный белок (условно — 2 г на порцию первого + 1 г на порцию второго) должен быть не меньше 12. Цель 40x₁ + 30x₂ — минимизировать стоимость (40 и 30 — цены порций). Переменные задают "сколько порций каждого компонента взять"; белок считается линейно через нормы в строках ограничений.
Проверка допустимости на пальцах — план x₁=6, x₂=0 даёт белок 2·6+0=12 (ровно норма) и углеводы 6+0=6 < 18 — план недопустим по второму ограничению. Значит, одной "нормы по белку" мало — нужен баланс всех строк.
Связь с задачами в разработке
| Прикладная задача | Аналог в ЗЛП / МП |
|---|---|
| Распределение задач по серверам | переменные "сколько нагрузки на узел", линейные лимиты CPU/RAM |
| Выбор тарифов CDN / облака | линейные затраты + квоты |
| Планирование спринта (упрощённо) | целочисленные переменные "взять задачу или нет" |
| Кратчайший путь / поток в сети | специальные структуры; транспортная — частный случай |
| Кэширование, разбиение на этапы | динамическое программирование (Динамическое программирование и уравнение Беллмана) |
Полный перечень промышленных моделей (стохастика, робастность, многокритериальность) выходит за рамки базового курса; здесь закладывается фундамент, на который опираются солверы и дальнейшее чтение.
Когда применять ЗЛП и когда выбирать другой класс моделей
Подходит, если зависимости в модели реально близки к линейным на рабочем диапазоне — затраты пропорциональны объёму, лимиты — суммарные.
Не подходит без усложнения модели, если —
- есть пороги и скидки (нелинейная цена);
- переменные должны быть целыми (число серверов, бинарный "включить фичу");
- эффект синергии (
x₁·x₂).
Тогда переходят к целочисленному, нелинейному МП или к эвристикам — с пониманием, что оптимум может быть только приближённым.
Типичные ошибки при постановке
| Ошибка | Как избежать |
|---|---|
Перепутали max и min | затраты и время — обычно min; выручка — max |
| Разные единицы в одной строке | часы и килограммы в одном ограничении без перевода — бессмыслица |
Забыли x ≥ 0 | если переменная может быть отрицательной (баланс), введите замену x = x⁺ − x⁻ |
| Нелинейность "по привычке" | скидка "после 100 штук" — уже другой класс задач |
Практический шаблон постановки задачи
Когда формулируете новую модель из бизнес-текста, удобно идти по фиксированному шаблону —
- Цель в одном предложении — что оптимизируем (прибыль, затраты, срок, риск).
- Переменные с единицами — что означает каждая
x, в каких единицах измеряется. - Ограничения по группам — ресурсы, обязательства по спросу, технологические правила.
- Проверка размерностей — в каждой строке должны складываться сопоставимые величины.
- Проверка знаков —
max/min, тип≤/≥/=, неотрицательность или свободные переменные. - Тестовый план — подставьте 1-2 простых плана и убедитесь, что модель ведёт себя ожидаемо.
Хорошая модель отвечает на вопросы "какой план лучший" и "почему именно он" — какие ограничения стали узкими местами, какие ресурсы недоиспользованы, как меняется результат при небольшом изменении входных данных.
Интерактив — постановка и поиск оптимума
Попробуйте настроить задачу и сразу проверить, как меняется оптимальный план при новых коэффициентах цели и лимитах ресурсов.
Мини-сценарий перед запуском —
- Введите свою "бизнес-идею" через коэффициенты цели (
c1,c2) — что именно выгоднее системе. - Задайте реалистичные лимиты (
b1,b2) как ограничения ресурсов. - Подставьте тестовую точку
(x1, x2)и проверьте, допустима ли она. - Сравните ручной тест с автоматически найденным лучшим планом.
Play ITЗагрузка интерактивного демо…
Как читать результат —
- если тестовая точка недопустима, проверьте нарушение ресурсного ограничения в постановке;
- если оптимум резко уходит в одну переменную, значит ваша цель сильно асимметрична;
- если в лучшем плане один запас почти ноль, это потенциальное узкое место процесса.
Этот паттерн (постановка -> проверка допустимости -> оптимум) используйте как шаблон перед переходом к коду и симплексу.
Что дальше
- Теория и графический метод — выпуклые множества, почему оптимум ЗЛП часто в вершине, разбор примера со станками на плоскости.
- Жордан–Гаусс — приведение системы к виду, удобному для старта симплекса.
- Практика в коде — статья 9.