Линейное программирование. Общая задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

 

Общая задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

 

F= (1)

 

при условиях

 

i=

 

i=

≥ 0

X(x₁,x₂…x_n) – вектор Х, удовлетворяющий системе ограничений (2) называется допустимым решением задачи линейного программирования (ЗЛП) или планом задачи.

Вектор Х являющийся допустимым решением, при котором целевая функция (1) достигает оптимального значения, называется оптимальным решением ЗЛП.

Пример: Простейшая задача планирования производства. Предприятие располагает m видами ресурсов и может выпускать продукцию n различными технологическими способами. За 1-цу времени использования j технологического способа расходуется A_ij единиц i-го ресурса, при этом выпускается γ_j единиц продукции. Требуется спланировать работу предприятия так, чтобы выпустить max продукции, если на каждый ресурс i-го вида есть ограничения: в наличии есть не более Bi единиц ресурса.

Решение.

 

Пусть Х_j – время использования j технологии, тогда – количество ресурса i-го вида для всего производства.

 

Составлена математическая модель ЗЛП. Ее решение производится специальными методами.

Симплексный метод решения ЗЛП основан на переходе от одного опорного плана к другому, при котором значение целевой функции улучшается (возрастает или уменьшается), при условии, что данная задача имеет оптимальный план.

 

ЗЛП вида

является основной.

 

Если каждое уравнение системы приведено к такому виду, что одна переменная входит с коэффициентом 1 только в одно уравнение и с коэффициентом 0 во все другие, причем это выполняется для каждого уравнения, (такие переменные называются базисными, остальные - свободными), а целевая функция выражена только через свободные переменные, тогда ЗЛП называется приведенной к базису или записанной в каноническом виде.

 

F= C₀+C₁*x₁+…+C_n*x_n → opt

a₁₁*X₁+a₁₂*X₂+…+a_1n*X_k +X_k+1=b₁

a₂₁*X₁+a₂₂*X₂+…+a_2n*X_k +..+X_k+2 =b₂

_…

a_k1*X₁+a_k2*X₂+…+a_kn*X_k +..+X_2k =b_k

 

X_k+1, X_k+2, …, X_2k – базисные переменные;

X₁, X₂, … X_k – свободные переменные;