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

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

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

Многие вопросы экономики, а также различные задачи других наук в своей математической постановке являются задачами Л. п.

В качестве примера приведем следующую задачу. «Предприятие выпускает  видов изделий из  видов сырья. Заданы числа , , , означающие количество сырья i-го вида, необходимого для производства единицы продукции вида . Известны также наличные запасы сырья (сырье вида  имеется в количестве  единиц, ). Наконец, заданы цены, по которым предприятие продает выпущенную продукцию ( — цена единицы изделия i-го вида, ).

Требуется составить план выпуска изделий, т. е. указать, сколько изделий каждого вида следует изготовить с тем расчетом, чтобы, во-первых, хватило бы запасов сырья и, во-вторых, суммарная стоимость произведенной продукции была бы наибольшей».

Если  — планируемые количества изделий видов  соответственно, то описанная выше задача имеет следующую математическую постановку.

Найти  такие, что

, ,

и линейная форма  в точке  принимает максимальное значение.

К задаче Л. п. сводятся многие вопросы технико-экономического содержания, такие, как задача о раскрое материала, задача о диете, задача о смесях и др. Отдельной главой Л. п. является теория транспортных задач. В простейшей постановке транспортная задача формулируется следующим образом: даны запасы (однородного) товара у поставщиков ( — запас i-го поставщика, ), потребности потребителей ( — потребность j-го потребителя, ), а также тарифы, т. е. числа , означающие стоимость перевозки единицы товара от i-го поставщика к j-му потребителю. Требуется составить план перевозок с наименьшими транспортными расходами, т. е. вычислить числа , , , означающие количество перевозимого товара от i-го поставщика к j-му потребителю; при этом

 ,

и линейная форма  принимает минимальное значение.

Решение задач Л. п. может быть проведено с помощью так называемого симплексного метода. Сущность этого метода состоит в следующем. Множество точек , удовлетворяющих заданной системе линейных неравенств и уравнений (допустимая область), представляет собой выпуклое множество, граница которого разделяется на «куски» — грани различных размерностей. Так, в трехмерном пространстве переменных допустимая область является многогранником (возможно пустым или незамкнутым), граница которого состоит из граней (размерность два), ребер (размерность один), вершин (размерность нуль); n-мерный случай аналогичен трехмерному. Экстремум линейной формы на выпуклом множестве не может быть во внутренней точке и, если существует, находится на границе множества. Оказывается, что в задаче Л. п. экстремум линейной формы совпадает с одной из вершин допустимой области. Вычисление такой вершины согласно симплексному методу происходит следующим образом: 1) выбирается начальная вершина; 2) решается вопрос о том, существует ли вершина соседняя (по ребру) к начальной вершине, с лучшим значением линейной формы (т. е. с большим значением, если искомый экстремум — максимум, и с меньшим значением, если экстремум — минимум). Решение этого вопроса производится по правилам, предписываемым симплексным методом; 3) если такая вершина есть, то ее выбирают за начальную, и все операции повторяются; если такой вершины нет, то изучаемая вершина является искомым экстремумом. Практическое решение задач Л. п. по симплексному методу связано с построением и пересчетом симплексных таблиц; каждая таблица соответствует вершине допустимой области.

Л. п. как наука возникла в конце 30-х г. нашего века в трудах советского математика Л. В. Канторовича. В 1958 г. американский математик ван Данциг разработал описанный выше симплекс-метод в современной редакции.