Большой энциклопедический словарь:
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ — один из разделов математического программирования.
Большая советская энциклопедия:
Линейное программирование
Математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах, задаваемых системами линейных неравенств и равенств; Л. п. является одним из разделов математического программирования (См. Математическое программирование).
Типичным представителем задач Л. п. является следующая: найти максимум линейной функции
nj=1cjxj (1)
при условиях
, i = 1, 2, ..., m, (2)
xj 0, j = 1, 2, n, (3)
где cj, aij и bi — заданные величины.
Задачи Л. п. являются математическими моделями многочисленных задач технико-экономического содержания. Рассмотрим в качестве примера следующую задачу планирования работы предприятия. Для производства однородных изделий необходимо затратить различные производственные факторы — сырьё, рабочую силу, станочный парк, топливо, транспорт и т. д. Обычно имеется несколько отработанных технологических способов производства, причём в этих способах затраты производственных факторов в единицу времени для выпуска изделий различны. Количество израсходованных производственных факторов и количество изготовленных изделий зависит от того, сколько времени предприятие будет работать по тому или иному технологическому способу. Ставится задача рационального распределения времени работы предприятия по различным технологическим способам, т. е. такого, при котором будет произведено максимальное количество изделий при заданных ограниченных затратах каждого производственного фактора. Формализуем задачу. Пусть имеется n технологических способов производства изделий и m производственных факторов. Введём обозначения: cj — количество изделий, выпускаемых в единицу времени при работе по j-му технологическому способу; aij — расход i-го производственного фактора в единицу времени при работе по j-му технологическому способу; bi — имеющиеся ресурсы i-го производственного фактора и xj — планируемое время работы по j-му технологическому способу. Величина
означает общий расход i-го производственного фактора при плане х(i) = (x(i)1, x(i)2, ..., x(i)n). И поскольку ресурсы ограничены величинами bi, то возникают естественные условия (2) и (3). Ставится задача отыскания такого распределения времени (оптимального плана) х* = (x*1, х*2, ..., х* n) работы по каждому технологическому способу, при котором общий объём продукции nj=1cjxjбыл бы максимальным, то есть задача (1) — (3). Другим характерным примером прикладных задач Л. п. является Транспортная задача.
Термин «Л. п.» нельзя признать удачным, однако смысл его в том, что в Л. п. решаются задачи составления оптимальной программы (плана) действий. В связи с этим Л. п. можно рассматривать как один из математических методов в исследованиях операций (см. Операций исследование).
Функцию (1) в Л. п. принято называть целевой функцией, или критерием эффективности, вектор х = (x1, x2, ..., xn) — планом, вектор x*=(x*1, x*2, ..., x*n) — оптимальным планом, а множество, определяемое условиями (2) — (3), — допустимым, или множеством планов. Одним из основных методов решения задач Л. п. является симплексный метод. Геометрически его идея состоит в следующем. Допустимое множество (2) — (3) представляет собой выпуклое многогранное множество (если оно ограничено, то — многомерный выпуклый многогранник). Если задача Л. п. имеет решение, то существует вершина х* многогранного множества, являющаяся оптимальным планом. Симплексный метод состоит в таком направленном переборе вершин, при котором значение целевой функции возрастает от вершины к вершине. Каждой вершине соответствует система уравнений, выбираемая спец. образом из системы неравенств (2) — (3), поэтому вычислительная процедура симплексного метода состоит в последовательном решении систем линейных алгебраических уравнений. Простота алгоритма делает этот метод удобным для его реализации на ЭВМ.
Лит.: Юдин Д. Б., Гольштейн Е. Г., Линейное программирование, М., 1969.
В. Г. Карманов.
Математическая энциклопедия:
Математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных неравенств и равенств; Л. п. — один из разделов математического программирования. Типичной задачей Л. п. является следующая: найти максимум линейной функции при условиях где — заданные числа. Задачи Л. п. являются математич. моделями многочисленных задач технико-экономич. содержания. Примером может служить следующая задача планирования работы предприятия. Для производства однородных изделий необходимо использовать различные производственные факторы: сырье, рабочую силу, станочный парк, топливо, транспорт и т. д. Обычно имеется несколько отработанных технологич. способов производства, причем в этих способах затраты производственных факторов в единицу времени для выпуска изделий различны. Количество израсходованных производственных факторов и количество изготовленных изделий зависит от того, сколько времени предприятие будет работать по тому или иному технологич. способу. Ставится задача рационального распределения времени работы предприятия по различным технологич. способам, т. е. такого, при к-ром будет произведено максимальное количество изделий при заданных ограниченных затратах каждого производственного фактора. Формализуем задачу. Пусть имеется птехнологич. способов производства изделий и тпроизводственных факторов. Пусть cj — количество изделий, выпускаемых в единицу времени при работе по j-му технологич. способу; aij- расход i-го производственного фактора в единицу времени при работе по j-му технологич. способу; bj — имеющиеся ресурсы i-гo производственного фактора и xj — планируемое время работы, по j-му технологич. способу. Величина означает общий расход i-гo производственного фактора при плане x=(x1 x2, . . ., х п). И поскольку ресурсы ограничены величинами bi, то возникают естественные условия (2) и (3). Ставится задача отыскания такого распределения времени (оптимального плана) = работы по каждому технологич. способу, при к-ром общий объем продукции был бы максимальным, т. е. задача (1) — (3). Другим характерным примером прикладных задач Л. п. является транспортная задача. Задачи Л. п. являются вспомогательными во многих методах решения нелинейных задач математич. программирования. Так, в методе возможных направлений (см. Математическое программирование).для отыскания направления спуска на каждой итерации необходимо решить соответствующую задачу Л. п. Смысл термина "Л. п." в том, что в Л. п. решаются задачи составления оптимальной программы (плана) действий. В связи с этим Л. п. можно рассматривать как один из математич. методов в исследовании операций. В задачах Л. п. более общего вида по сравнению с (1) — (3) нек-рые (или все) из условий (2) могут быть равенствами, а на нек-рые (либо на все) переменные xj не накладываются условия неотрицательности. Любая задача Л. п. может быть приведена к эквивалентной задаче вида (1) — (3). Основу изучения свойств задач Л. п. составляет теория двойственности. Двойственной з а д а ч е й Л. п. к задаче (1) — (3) наз. задача минимизации функции при условиях Задачи (1) — (3) и (4) — (6) либо обе имеют решения, либо обе неразрешимы. Значения целевых функций (1) и (4) на решениях совпадают. Одним из основных методов решения задач Л. п. является симплексный метод. Геометрически его идея состоит в следующем. Допустимое множество (2) и (3) представляет собой выпуклое многогранное множество (если оно ограничено, то — многомерный выпуклый многогранник). Если задача Л. п. имеет решение, то существует вершина х* многогранного множества, являющаяся оптимальным планом. Симплексный метод состоит в таком направленном переборе вершин, при к-ром значение целевой функции возрастает от вершины к вершине. Каждой вершине соответствует система уравнений, выбираемая специальным образом из системы неравенств (2), (3), поэтому вычислительная процедура симплексного метода состоит в последовательном решении систем линейных адгебраич. уравнений. Простота алгоритма делает этот метод удобным для его реализации на ЭВМ. В Л. п. разработан целый ряд других конечных методов, напр. двойственный симплексный метод, когда решение прямой задачи (1) — (3) получают в результате применения симплексного метода к двойственной задаче (4) — (6). Наряду с терминами "симплексный метод" и "двойственный симплексный метод" приняты термины "метод последовательного улучшения плана" и "метод последовательного уточнения оценок". При моделировании реальных явлений часто возникают задачи Л. п. больших размерностей. Содержание этого термина зависит от возможностей вычислительных алгоритмов и характеристик, используемых ЭВМ, таких, как объем оперативной памяти, скорость и др. Для решения задач больших размерностей создаются методы, учитывающие специфич. структуру матриц условий. В основе многих из них лежит идея декомпозиции — разложения системы ограничений на подсистемы, для каждой из к-рых необходимо решать подзадачу Л. п. меньшей размерности по сравнению с исходной задачей. Для решения задачи Л. п. наряду с конечными методами применяются также итерационные методы построения последовательности приближений, пределом к-рой является оптимальный план. К ним относятся методы, основанные на применении штрафных функций (см. Штрафных функций метод), итерационные методы теории игр, применение к-рых основано на эквивалентности любой матричной игры соответствующей паре двойственных задач Л. п., и ряд других методов. Существенное место в Л. п. занимает проблема устойчивости. В реальных задачах (в особенности задачах технико-экономич. содержания) исходная информация обычно известна лишь с определенной степенью точности, и даже малые возмущения (погрешности) в исходных данных могут вызывать существенные отклонения возмущенного решения от истинного. При численной реализации того или иного конечного метода возникают ошибки округления, накопление к-рых, особенно в задачах большой размерности, может привести к значительным отклонениям полученного приближенного решения от истинного. Обе эти ситуации характеризуют свойство неустойчивости и присущи некорректно поставленным задачам. В Л. п. разработаны методы решения некорректных задач. Так, в методе регуляризации, используя нек-рую дополнительную информацию о решении, аппроксимируют исходную задачу параметрич. последовательностью устойчивых задач таким образом, чтобы последовательность их решений сходилась к решению исходной задачи. Наряду с конечномерными задачами Л. п. рассматриваются также задачи Л. п. в бесконечномерных пространствах. К этим задачам относятся, напр., линейные задачи оптимального управления со смешанными ограничениями. Лит.:[1] Юдин Д. Б., Г о л ьш т е й н Е. Г., , М., 1969: [2] Данциг Д ж., , его применения и обобщения, М., 1966; [3] Еремин И. И., Астафьев Н. Н., Введение в теорию линейного и выпуклого программирования, М., 1976; [4] Карманов В. Г., Математическое программирование, М., 1975; [5] Тер-Крикоров А. М., Оптимальное управление и математическая экономика, М., 1977. В. Г. Карманов.
Научно-технический словарь:
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, математическая операция, при которой многовариантная линейная функция анализируется для того, чтобы найти максимальные и минимальные значения. Применяется при планировании бизнеса и в промышленном машиностроении для производства оптимальных условий управления, так как при управлении запасами стоимость должна быть минимальной в связи со сроками хранения, местом для хранения товаров, уровнем покупательского спроса, временем пополнения запасов и транспортных затрат.
© «СловоТолк.Ру» — толковые и энциклопедические словари, 2007-2020