ЛИНЕ́ЙНОЕ ПРОГРАММИ́РОВАНИЕ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
ЛИНЕ́ЙНОЕ ПРОГРАММИ́РОВАНИЕ, раздел математики, посвящённый теории и методам решения задач об экстремумах линейных функций на множествах, задаваемых системами линейных равенств и неравенств. Задачи Л. п. являются математич. моделями разл. задач технико-экономич. содержания.
Типичной задачей Л. п. является задача нахождения максимума по $x_1,...,x_n$ линейной функции $$\sum_{j=1}^{n}c_jx_j\tag1$$при условиях$$\sum_{j=1}^n a_{ij}x_j ⩽ b_i,\;i=1,\:...,\:m, \tag2$$$$x_j⩾0,\; j=1,\:...,\:n,\tag3$$ где $n$, $m$, $c_j$, $a_{ij}$ и $b_i$ – заданные числа.
Такая задача возникает, напр., при планировании работы предприятия. Пусть предприятие может выпускать $n$ видов продукции, единица продукции вида $j$ даёт прибыль $c_j$, $j=1,...,n$. В произ-ве используются ресурсы $n$ видов (сырьё, время работы станков, рабочая сила, энергия и т. п.). Расход ресурса $i$ на произ-во единицы продукции вида $j$ составляет $a_{ij}$. Общий ресурс вида $i$ ограничен величиной $b_i$, $i= 1, ..., m$. Требуется определить производств. план (программу; отсюда назв.), т. е. найти объёмы выпуска $x_j⩾0$ по каждому из видов продукции с тем, чтобы были выполнены ограничения (2), а суммарная прибыль (1) была максимальной.
Функцию (1) в Л. п. принято называть целевой функцией (критерием оптимальности, критерием эффективности), вектор $x= (x_1,...,x_n)$, удовлетворяющий условиям (2), (3), называется допустимым решением или планом, а множество векторов $x$, определяемое условиями (2), (3), называется допустимым множеством или множеством планов. Допустимое решение $x^*$, доставляющее максимум целевой функции (1), называется оптимальным. Ещё одним примером прикладных задач Л. п. является транспортная задача.
В задачах Л. п. более общего вида по сравнению с (1)–(3) некоторые (или все) из условий (2) могут быть равенствами, а на некоторые (либо на все) переменные $x_j$ не налагаются условия неотрицательности. Любая задача Л. п. может быть приведена к эквивалентной задаче вида (1)–(3). В некоторых задачах Л. п. возникает ограничение, связанное с целочисленностью величин $x_1,...,x_n$. В этом случае говорят о задачах целочисленного линейного программирования.
Задачей Л. п., двойственной задаче (1)–(3), называется задача минимизации функции $$\sum_{i=1}^{m}b_iy_i\tag4$$при условиях$$\sum_{i=1}^ma_{ij}y_i⩾c_j,\;j=1,\:...,\:n,\tag5$$$$y_i⩾0,\; i=1,\:...,\:m.\tag6$$
Задачи (1)–(3) и (4)–(6) либо обе имеют решения, либо обе неразрешимы. Значения целевых функций (1) и (4) на решениях совпадают.
Одним из осн. методов решения задач Л. п. является симплексный метод. Его идея состоит в следующем: допустимое множество планов, задаваемое ограничениями (2) и (3), представляет собой выпуклое многогранное множество; если оно ограничено, то оно является выпуклым многогранником. Если задача Л. п. имеет решение, то существует вершина $x^*$ этого многогранника, являющаяся оптимальным планом. Симплексный метод состоит в направленном переборе, при котором значения целевой функции возрастают от вершины к вершине. Каждой вершине соответствует система уравнений, получаемая из системы неравенств (2), (3), и вычислительная процедура симплексного метода состоит в последовательном решении систем линейных алгебраич. уравнений. Простота алгоритма делает этот метод удобным для реализации. Для решения задач Л. п. применяются также итерационные методы построения последовательности приближений, пределом которой является оптимальный план.
Существенное место в Л. п. занимает проблема устойчивости. В реальных задачах (в особенности задачах технико-экономич. содержания) исходная информация обычно известна лишь с определённой точностью, и даже малые возмущения (погрешности) в исходных данных могут вызывать существенные изменения решения. При численной реализации того или иного конечного метода возникают ошибки округления, накопление которых, особенно в задачах большой размерности, может привести к значит. отклонениям полученного приближённого решения от истинного. Обе эти ситуации описывают свойство неустойчивости и присущи некорректно поставленным задачам. В Л. п. разработаны методы решения некорректных задач.
Развитие Л. п. началось в 1939 с исследований Л. В. Канторовича, в которых он предложил универсальный математич. метод для решения задач экономич. характера – таких, как задача о наилучшей загрузке машин, о раскрое материалов с наименьшими расходами, о распределении грузов по нескольким видам транспорта. Во 2-й пол. 1940-х гг. Т. Купманс обращал внимание математиков на задачи, сводящиеся к нахождению экстремумов линейных функций на многогранниках. В это же время амер. математик Дж. Данциг (ввёл термин «Л. п.») и Канторович независимо друг от друга предложили эффективный метод решения таких задач, получивший назв. симплексного метода. Этот и др. методы решения задач Л. п. требуют большого объёма вычислений; они стали эффективно реализовываться только с появлением быстродействующих ЭВМ в нач. 1950-х гг.