Понятие линейного программирования
Линейное программирование – один из первых и наиболее подробно изученных разделов математического программирования в смысле нахождения оптимальных значений переменных. Термин linear programming был предложен в середине 1940-х годов Джорджем Данцигом, еще до того, как компьютеры были использованы для решения линейных задач оптимизации. Русский эквивалент понятия «линейное программирование» – «линейное планирование». Однако термины «линейное программирование», «нелинейное программирование», «математическое программирование» и т.д. в научной литературе стали общепринятыми и сохранены.
Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного описания реальных экономических процессов.
Линейное программирование применяется при решении экономических задач оптимального управления и планированиея производства; определение оптимального размещения оборудования; определение оптимального плана перевозок груза (транспортная задача); оптимальное распределение кадров и т.д.
Задача линейного программирования
Задача линейного программирования (ЗЛП), состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.
Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательными в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Задача линейного программирования в канонической форме при поиске минимума целевой функции может иметь вид:
w = cx ® min,
Ax = b,
x ≥ 0.
Задача линейного программирования в стандартной форме:
w = cx ® min,
Ax ≥ b,
x ≥ 0.
В обоих случаях A есть матрица размерности m×n, i -строка которой совпадает с вектором ai.
Постановка задач линейного программирования и
Исследование их структуры
Большинство экономических задач, решаемых методами ЗЛП, может быть сформулировано так:
максимизировать некоторую экономическую целевую функцию F (x1,x2,…xn) при нескольких ограничениях:
g1 (x1,…xn)≤ b1;
g2 (x1,…xn)≤ b2;
……………….
gm (x1,…xn)≤ bm,
где F (x1,x2,…xn) – целевая функция, или критерий эффективности (например, прибыль от производства каких-либо видов продукции, стоимость перевозок и т.п); X = { x1,…xn } – варьируемые параметры; g1 (X),…, gm(X) – функции, которые задают ограничения на имеющиеся ресурсы.
Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи и прочие.
Рассмотрим некоторые из них.
Определение оптимального ассортимента.
Имеются m видов ресурсов в количествах b1,b2,…,bi,…, bm и n видов изделий. Задана матрица A = || aij ||, i = 1,…, n, где aij характеризует нормы расхода i -го ресурса на единицу j -го вида изделий. Эффективность производства j -го вида изделий характеризуется Cj, удовлетворяющим условию линейности. Нужно определить такой план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности будет наибольший.
Обозначим количество единиц k -го вида изделий, выпускаемых предприятием, через xk, k = 1, K. Тогда математическая модель этой задачи будет иметь такой вид:
максимизировать 
при ограничениях 
Кроме ограничений на ресурсы (1), в эту модель можно ввести дополнительные ограничения на планируемый уровень выпуска продукции x j ≥ x j0, xi: xj: xk = bi: bj: bk для всех i, j, k и т.д.