Линейное программирование. 
Численные методы

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

при наличии линейных дополнительных условий трех типов.

Каждое из условий типа неравенств (1.57) или (1.59) определяет полупространство, ограниченное гиперплоскостью; все эти условия вместе определяют выпуклый п-мерный многогранник J, являющийся пересечением соответствующих полупространств. С математической точки зрения условия (1.57) и (1.59) однотипны, но по традиции их записывают указанным образом. Условия типа равенств (1.58) выделяют из п-мерного пространства (п — т)-мерную плоскость. Ее пересечение с областью J дает выпуклый (п — т)-мерный многогранник G; задача состоит в том, чтобы найти минимум линейной функции (1.56) в многограннике G.

ПРИМЕР. Задача распределения производства однотипной продукции по разным заводам.

Пусть х₁ — выпускаемое t-м заводом количество продукции (оно должно быть неотрицательным), с, — себестоимость одного изделия на этом заводе, сг при j > т — расход сырья /-го вида и при 2 < / < т — расход заработной платы и других аналогичных показателей /-го вида при выпуске единицы продукции на данном заводе. Положим a_yj = 1; тогда Ь_х является суммарным выпуском продукции по всем заводам, а b_j при 2 < j < т — полной заработной платой и аналогичными данными по всей отрасли, суммы (1.59) — расходом сырья по всем заводам, а L — себестоимостью общей продукции. Требуется, чтобы себестоимость продукции была минимальной, выпуск продукции, расход заработной платы и т. д. — заданными, а фонды сырья при т < j не перерасходовались. Задача заключается в том, чтобы распределить неотрицательные плановые задания х_у по всем заводам так, чтобы удовлетворить всем этим требованиям.

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

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

Сложность заключается в том, что типичное в экономике число переменных — это сотни и даже тысячи. Предложен ряд способов уменьшения числа искомых вершин, в частности СИМПЛЕКС-МЕТОД.