Линейное программирование

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

Большая советская энциклопедия. — М.: Советская энциклопедия. 1969—1978.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Линейное программирование" в других словарях:

  • Линейное программирование — Линейное программирование  математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование… …   Википедия

  • линейное программирование — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] линейное программирование Область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между… …   Справочник технического переводчика

  • Линейное программирование — [linear programming] область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны… …   Экономико-математический словарь

  • Линейное программирование — [linear programming] область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны… …   Экономико-математический словарь

  • ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ — (linear programming) Математическая процедура нахождения максимального или минимального значения линейной целевой функции при наличии линейных ограничений. Когда используется лишь небольшое число переменных и ограничений, можно вести расчет,… …   Экономический словарь

  • ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ — один из разделов математического программирования …   Большой Энциклопедический словарь

  • ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ — ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, математическая операция, при которой многовариантная линейная функция анализируется для того, чтобы найти максимальные и минимальные значения. Применяется при планировании бизнеса и в промышленном машиностроении для… …   Научно-технический энциклопедический словарь

  • ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ — раздел матем. программирования, изучающий задачу отыскания минимума (максимума) линейной функции многих переменных при линейных ограничениях в виде равенств млн. неравенств. Л. п. широко применяется при решении задач экономического и планово… …   Большая политехническая энциклопедия

  • ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n мерного векторного пространства, задаваемых системами линейных неравенств и равенств; Л. п. один из разделов математического… …   Математическая энциклопедия

  • линейное программирование — один из разделов математического программирования. * * * ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, один из разделов математического программирования …   Энциклопедический словарь


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»