Большая Советская энциклопедия - линейное программирование

математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах, задаваемых системами линейных неравенств и равенств; Л. п. является одним из разделов математического программирования (См. Математическое программирование).

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

∑ⁿj=1cjxj (1)

при условиях

, i = 1, 2, ..., m, (2)

xj ≥ 0, j = 1, 2, n, (3)

где cj, aij и bi — заданные величины.

Задачи Л. п. являются математическими моделями многочисленных задач технико-экономического содержания. Рассмотрим в качестве примера следующую задачу планирования работы предприятия. Для производства однородных изделий необходимо затратить различные производственные факторы — сырьё, рабочую силу, станочный парк, топливо, транспорт и т. д. Обычно имеется несколько отработанных технологических способов производства, причём в этих способах затраты производственных факторов в единицу времени для выпуска изделий различны. Количество израсходованных производственных факторов и количество изготовленных изделий зависит от того, сколько времени предприятие будет работать по тому или иному технологическому способу. Ставится задача рационального распределения времени работы предприятия по различным технологическим способам, т. е. такого, при котором будет произведено максимальное количество изделий при заданных ограниченных затратах каждого производственного фактора. Формализуем задачу. Пусть имеется n технологических способов производства изделий и m производственных факторов. Введём обозначения: cj — количество изделий, выпускаемых в единицу времени при работе по j-му технологическому способу; aij — расход i-го производственного фактора в единицу времени при работе по j-му технологическому способу; bi — имеющиеся ресурсы i-го производственного фактора и xj — планируемое время работы по j-му технологическому способу. Величина