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

При оптимизации экономических планов возникают задачи на минимум линейной функции, переменных при наличии линейных дополнительных условий трех типов:

Каждое из условий типа неравенств (416) или (41 г) определяет полупространство, ограниченное гиперплоскостью; все эти условия вместе определяют выпуклый -мерный многогранник J, являющийся пересечением соответствующих полупространств. С математической точки зрения условия (41б) и (41 г) однотипны; но по традиции их записывают указанным образом. Условия типа равенств (41 в) выделяют из -мерного пространства -мерную плоскость.

Ее пересечение с областью J дает выпуклый -мерный многогранник G; наша задача состоит в том, чтобы найти минимум линейной функции (41а) в этом многограннике

Примером такой задачи является распределение производства однотипной продукции по разным заводам. Пусть — выпускаемое заводом количество продукции (оно должно быть неотрицательным), с — себестоимостью одного изделия на этом заводе, при -расход сырья вида и при — расход заработной платы и других аналогичных показателей вида при выпуске единицы продукции на данном заводе. Положим тогда будет суммарным выпуском продукции по всем заводам, — полной заработной платой и аналогичными данными по всей отрасли, суммы (41 г) - расходом сырья по всем заводам, a L — себестоимостью общей продукции. Требуется, чтобы себестоимость продукции была минимальной, выпуск продукции, расход заработной платы и т. заданными, а фонды сырья не перерасходовались. Нас интересует, как распределить неотрицательные плановые задания по заводам так, чтобы удовлетворить всем этим требованиям.

Отметим терминологию, установившуюся в экономике. Вектор удовлетворяющий всем дополнительным условиям, называют планом; если он, к тому же, соответствует вершине многогранника G, то опорным планом. Решение экстремальной задачи (41) называют оптимальным планом, столбцы прямоугольной матрицы А — векторами условий, а столбец b — вектором ограничений. В задачах экономики обычно все коэффициенты , хотя для последующего изложения это несущественно.

Многогранник условий -выпуклый (он может быть и неограниченным). Поэтому внутри него линейная функция не может достигать минимума. Ее минимум (если он существует) достигается обязательно в какой-нибудь вершине многогранника. При вырождении он может достигаться во всех точках ребра или даже -мерной ограничивающей плоскости . Поэтому теоретически задача линейного программирования проста. Достаточно вычислить значения функции в конечном числе точек — в вершинах многогранника и найти среди этих значений наименьшее.

Сложность заключается в другом. Типичное в экономике число переменных — это сотни и даже тысячи. При этом число вершин многогранника G становится астрономическим. Для того чтобы оценить это число, рассмотрим способ нахождения вершин.

Находить вершины самого многогранника G неудобно. Лучше преобразовать задачу к канонической форме, не содержащей условий третьего типа. Для этого введем в качестве новых переменных невязки условий третьего типа:

Доопределим коэффициенты экстремальной задачи (41) следующим образом:

Тогда задача линейного программирования примет каноническую форму:

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

Будем считать, что строки новой матрицы А линейно-независимы: в противном случае или одно условие лишнее, или система условий, несовместна. Тогда ранг этой прямоугольной матрицы равен М, и среди ее столбцов найдется по крайней мере один набор из М линейно-независимых столбцов. Все линейно-независимые наборы столбцов матрицы А соответствуют точкам пересечения плоскости условий с координатными гиперплоскостями.

Чтобы найти вершину, возьмем один такой набор столбцов. Для удобства записи перенумеруем переменные так, чтобы первыми стояли столбцы, соответствующие этому набору (базису). Перепишем условия второго типа (44в) в следующем виде:

Обозначим через элементы матрицы, обратной к базисной квадратной матрице, стоящей в левой части системы (45). Приравнивая внебазисные координаты нулю и решая эту систему, получим координаты точки пересечения плоскости условий с координатной гиперплоскостью

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

Если мы забракуем все точки, это означает, что условия первого и второго рода образуют несовместную систему.

Различные столбцы матрицы А могут образовать наборов. Поэтому в самом неблагоприятном случае многогранник условий может иметь до вершин. Если то это число настолько велико, что простой перебор вершин невозможен. Нетрудно подсчитать, что для ЭВМ типа БЭСМ-6 простой перебор посилен только при