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

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

Типичным представителем задач Л.
п. является следующая: найти максимум линейной функции

при условиях

где a, atj и bвеличины. Задачи Л. п. являются матем. моделями многочисленных задач технико-эко-
номич. содержания. Рассмотрим в качестве примера следующую задачу планирования
работы предприятия. Для производства однородных изделий необходимо затратить
различные производств, факторы - сырьё, рабочую силу, станочный парк, топливо,
транспорт и т. д. Обычно имеется неск. отработанных технологич. способов
производства, причём в этих способах затраты производств, факторов в единицу
времени для выпуска изделий различны. Количество израсходованных производств,
факторов и количество изготовленных изделий зависит от того, сколько времени
предприятие будет работать по тому или иному технологич. способу. Ставится
задача рационального распределения времени работы предприятия по различным
технологич. способам, т. е. такого, при к-ром будет произведено максимальное
количество изделий при заданных ограниченных затратах каждого производств,
фактора. Формализуем задачу. Пусть имеется п технологич. способов производства
изделий и т производств, факторов. Введём обозначения: Cj - количество
изделий, выпускаемых в единицу времени при работе по у-му технологич. способу;
aij - расход /'-го производств, фактора в единицу времени при работе по
;-му технологич. способу; bi - имеющиеся ресурсы г'-го производств, фактора
и xj - планируемое время работы по ;'-му технологич. способу. Величина

означает общий расход г'-го производственного
фактора при плане x⁽" = = (x⁽'⁾i,x"⁾('⁾-И поскольку ресурсы ограничены величинами bi, то возникают естественные
условия (2) и (3). Ставится задача отыскания такого распределения времени
(оптимального плана) х* = = (x*i,x*технологич. способу, при к-ром общий объём

продукции
был бы максимальным, то есть задача (1) - (3). Другим характерным примером
прикладных задач Л. п. является транспортная задача.

Термин "Л. п." нельзя признать удачным,
однако смысл его в том, что в Л. п. решаются задачи составления оптимальной
программы (плана) действий. В связи с этим Л. п. можно рассматривать как
один из матем. методов в исследованиях операций (см. Операций исследование).

Функцию (1) в Л. п. принято называть
целевой функцией, или критерием эффективности, вектор х = (xi, x2,...,x- планом, вектор x* = (x*i, x*планом, а множество, определяемое условиями (2) - (3), - допустимым, или
множеством планов. Одним из осн. методов решения задач Л. п. является симплексный
метод. Геометрически его идея состоит в следующем. Допустимое множество
(2)-(3) представляет собой выпуклое многогранное множество (если оно ограничено,
то - многомерный выпуклый многогранник). Если задача Л. п. имеет решение,
то существует вершина х* многогранного множества, являющаяся оптимальным
планом. Симплексный метод состоит в таком направленном переборе вершин,
при к-ром значение целевой функции возрастает от вершины к вершине. Каждой
вершине соответствует система уравнений, выбираемая спец. образом из системы
неравенств (2)-(3), поэтому вычислит, процедура симплексного метода состоит
в последовательном решении систем линейных алгебраич. уравнений. Простота
алгоритма делает этот метод удобным для его реализации на ЭВМ.

Лит.: Ю д и н Д. Б., ГольштейнЕ.
Г., Линейное программирование, М-, 1969. В. Г. Карманов.

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я