Формы задачи линейного программирования (ЗЛП)

Различают три основные формы задачи линейного программирования, к которым может быть сведена любая содержательная постановка задачи. Записи целевых функций и ограничений в них существенно различаются. Ограничения могут иметь вид неравенств или равенств. Существует также ряд практических задач, в которых часть ограничений представлена в виде равенств, а часть — в виде неравенств.

Общая форма задачи линейного программирования (ЗЛП)

Задана система m линейных уравнений с n переменными:

a_llx₁+a₁₂x₂+... + a_1nx_n ≤ b₁

a₂₁x₁+a₂₂x₂+ + a_2nx_n ≤ b₂ (1.5.1)

………………………….

а_k1х₁+а_k2х₂+... + а_knх_n ≤ b_k

а_k+1,1х₁+а_k+1,2х₂+... + а_k+1,nх_n = b_k+1

_{…………………………………………}

a_m1х₁+а_m2х₂+... + а_mnх_n = b_m

х _j ≥ 0, где j = 1,…,n (1.5.2)

а линейная функция: F = (c₁ х₁ + c₂ х₂ + c₃ х₃ +…..+ c_n х_n) → max(min). (1.5.3)

Необходимо найти такой вектор Х=(х_1, х₂, х_3,…, х_n), который удовлетворяет ограничениям (1.5.1) и (1.5.2) и при котором линейная функции F принимает максимальное (или минимальное) значение.

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

Более кратко задачу линейного программирования в общей форме можно представить в следующем виде:

—>max(min) (1.5.4)

, где i=1,…,k (1.5.5)

, где i=k+l,...m) (1.5.6)

х _j ≥ 0, где j = 1,…,n (1.5.7)

Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение Х*=(х*₁, х*₂...х_n), удовлетворяющее системам ограничений (1.5.5) — (1.5.7), при которых линейная функция F достигает оптимального значение (минимума или максимума).

Стандартная форма задачи линейного программирования (ЗЛП)

Задача линейного программирования, представленная в форме:

a_llx₁+a₁₂x₂+... + a_1nx_n ≤ b₁

a₂₁x₁+a₂₂x₂+ + a_2nx_n ≤ b₂ (1.5.8)

_{…………………………………………}

a_m1х₁+а_m2х₂+... + а_mnх_n ≤ b_m

х _j ≥ 0, где j=1,…,n (1.5.9)

при которой целевая функция достигла бы своего max(min) значения:

F = (c₁ х₁ + c₂ х₂ + c₃ х₃ +…..+ c_n х_n) → max(min) (1.5.10)

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

Особенность данной формы состоит в том, что в ней система как функциональных, так и прямых ограничений состоит из одних неравенств, переменные х _j, где j=l,...,n являются неотрицательными, а целевая функция может стремиться как к минимуму, так и к максимуму.

Каноническая форма задачи линейного программирования (ЗЛП)

Форма, в которой:

F = (c₁ х₁ + c₂ х₂ + c₃ х₃ +…..+ c_n х_n) → max (1.5.11)

a_llx₁+a₁₂x₂+... + a_1nx_n = b₁

a₂₁x₁+a₂₂x₂+ + a_2nx_n = b₂ (1.5.13)

а₃₁х₁+а₃₂х₂+... + а_зnх_n = b₃

_{…………………………………………}

a_m1х₁+а_m2х₂+... + а_mnх_n = b_m

х _j ≥ 0, где j = 1,…,n (1.5.13)

все переменные х _j — неотрицательны, система ограничений представляет собой систему уравнений, а целевая функция стремится к максимуму, называется канонической формой задачи линейного программирования.