Указания по выполнению решению задач линейного программирования

Задачи математического программирования делятся на задачи линейного и нелинейного программирования. Если все функции f и g_i - линейные, то соответствующая задача является задачей линейного программирования. Если хотя бы одна из указанных функций - нелинейная, то соответствующая задача является за­дачей нелинейного программирования.

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

В общем виде задача линейного программирования (ЗЛП) ста­вится следующим образом: найти вектор Х = (х_l, х₂,..., х_n), максимизирующий линейную форму

(1.1) и удовлетворяющий условиям: (1.2) x_j ≥ 0, j = 1,..., n. (1.3)

Линейная функция f (Х) называется целевой функцией задачи. Условия (1.2) называются функциональными, а (1.3) - прямыми ограничениями задачи.

Вектор Х = (x_l, х₂,..., х_n) компоненты которого удовлетворяют функциональным и прямым ограничениям задачи, будем назы­вать планом, или допустимым решением ЗЛП.

Все допустимые решения образуют область определения зада­чи линейного программирования, или область допустимых решений. Допустимое решение, максимизирующее целевую функцию f (X), называется оптимальным планом задачи f (X^*) = max f (X),

где Х^* = (x_l^*, х₂^*,..., х_n^*) - оптимальное решение ЗЛП.

На практике хорошо зарекомендовали себя следующие моде­ли, относящиеся к оптимизационным: определения оптимальной производственной программы; оптимального смешивания ком­понентов; оптимального раскроя; оптимального размещения предприятий некоторой отрасли на определенной территории; формирования оптимального портфеля ценных бумаг; транспорт­ной задачи.

Для решения ЗЛП существует универсальный метод - метод последовательного улучшения плана, или симплекс-метод, кото­рый состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).

Рассмотрим пример задачи линейного программи­рования.