2018-01-08
481
Линейное программирование – один из первых и наиболее подробно изученных разделов математического программирования в смысле нахождения оптимальных значений переменных. Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного описания реальных экономических процессов.
Линейное программирование применяется при решении экономических задач оптимального управления и планирования производства; определение оптимального размещения оборудования; определение оптимального плана перевозок груза (транспортная задача); оптимальное распределение кадров и т.д.
Задача линейного программирования (ЗЛП), состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.
Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательными в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Задача линейного программирования в канонической форме при поиске минимума целевой функции может иметь вид:
|
|
|
w = cx ® min
Ax = b, x ≥ 0.
Задача линейного программирования в стандартной форме:
w = cx ® min,
Ax ≥ b, x ≥ 0.
В обоих случаях A есть матрица размерности m×n. Большинство экономических задач, решаемых методами ЗЛП, может быть сформулировано так: максимизировать некоторую экономическую целевую функцию 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 и т.д.
