Большая Советская энциклопедия II

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах, задаваемых системами линейных неравенств и равенств; Л. п. является одним из разделов математического программирования (См. Математическое программирование).
Типичным представителем задач Л. п. является следующая: найти максимум линейной функции
∑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.
В. Г. Карманов.

  1. линейное программирование—один из разделов математическогопрограммирования....Большой энциклопедический словарь II
  2. линейное программирование—ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ один из разделов математического программирования....Большой энциклопедический словарь III
  3. линейное программирование—ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ один из разделов математического программирования....Большой Энциклопедический словарь V
  4. линейное программирование—один из разделов матем. программирования....Естествознание. Энциклопедический словарь
  5. линейное программирование—Техника поиска максимального значения какоголибо уравнения являющегося предметом указанных линейных ограничений....Инвестиционный словарь
  6. линейное программирование—лнейнае праграмаванне...Краткий русско-белорусский словарь экономических терминов
  7. линейное программирование—метод применяемый для нахождения оптимального решения задачи распределения ресурсов в условиях действующих ограничений....Краткий словарь по теории экономического анализа
  8. линейное программирование—математическая дисциплина посвященная теории и методам решения задач об экстремумах линейных функций на множествах nмерного векторного пространства задаваемых системами л...Математическая энциклопедия
  9. линейное программирование—ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕstrong математическая операция при которой многовариантная линейная функция анализируется для того чтобы найти максимальные и минимальные значени...Научно-технический энциклопедический словарь
  10. линейное программирование—mathprogrammation linaire...Политехнический русско-французский словарь
  11. линейное программирование—linear programming матем....Русско-английский политехнический словарь
  12. линейное программирование—linear programming...Русско-английский психологический словарь
  13. линейное программирование—linear programming...Русско-английский словарь по машиностроению
  14. линейное программирование—linear programming...Русско-английский словарь по физике
  15. линейное программирование—linear programming...Русско-английский словарь по электронике
  16. линейное программирование—linear programming...Русско-английский технический словарь
  17. линейное программирование—linear programming матем. компьют....Русско-английский экономический словарь
  18. линейное программирование—лнейнае праграмаванне...Русско-белорусский математический словарь
  19. линейное программирование—programacin lineal...Русско-испанский экономический словарь
  20. линейное программирование—programmazione lineare in linea...Русско-итальянский политехнический словарь
  21. линейное программирование—programmazione lineare...Русско-итальянский экономический словарь
  22. линейное программирование—Linearprogrammierung...Русско-немецкий политехнический словарь
  23. линейное программирование—lineare Programmierung...Русско-немецкий экономический словарь
  24. линейное программирование—лнйне програмування...Русско-украинский политехнический словарь
  25. линейное программирование—linern programovn...Русско-чешский словарь
  26. линейное программирование—Математический метод используемый для поиска оптимального значения целевой функции при наличии ограничений заданных линейными функциями. Линейное программирование может и...Словарь терминов по управленческому учету
  27. линейное программирование—ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ один из разделов математического программирования....Современный энциклопедический словарь
  28. линейное программирование—linear programming. Математические методы с помощью которых достигается такое распределение ограниченных ресурсов которое оптимизирует результаты их использования....Финансовый менеджмент для неспециалистов
  29. линейное программирование—отыскание экстремальных крайнихминимальных и максимальных значений линейных функций определенных количественных зависимостей....Хрестоматия по экономической теории. Словарь экономических терминов и иностранных слов
  30. линейное программирование—ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ linear programming Математическая процедура нахождения максимального или минимального значения линейной целевой функции при наличии линейных огр...Экономический словарь
  31. линейное программирование—ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ один из разделов математического программирования....Энциклопедический словарь естествознания