Задачи линейного программирования

ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Большинство задач оптимизации относится к нелинейным, но решение нелинейных задач – это сложная вычислительная проблема. Поэтому практически во всех реальных приложениях для решения нелинейных задач используются приближенные методы решения. Линейное программирование выделяется среди других методов программирования как основа для многих процедур решения.

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

(2.1)

L = c₁x₁ + c₂x₂ +... + c_nx_n =

при условиях

a_i1x₁ + a_i2x₂ +... + a_inx_n ≤ b_i, i = 1, 2,..., m; j = 1,2, …, n,

или

–a_i1x₁ – a_i2x₂ –... – a_inx_n + b_i ³ 0.

Словесно задачу линейного программирования можно сформулировать так: требуется найти максимум линейной формы от n переменных при m ограничениях в виде неравенств или равенств. Нетрудно убедиться, что всегда можно говорить только о равенствах, так как введением дополнительных переменных x_{n+ υ} (υ = 1,..., p ≤ m) неравенства всегда можно свести к равенствам. Так, ограничение

(2.2)

a_i1x₁ + a_i2x₂ +... + a_inx_n ≤ b_i

(2.3)

можно свести к равенству, добавив переменную x_n+1:

a_i1x₁ + a_i2x₂ +... + a_inx_n + x_n+1 = b_i.

Тогда условие (2.2) сведется к (2.3) и условию неотрицательности переменной x_n+1. Поэтому можно сказать, что при решении задачи линейного программирования определяются такие значения n переменных x_j, которые бы обращали в максимум линейную форму

L = c₁x₁ + c₂x₂ +... + c_nx_n

при условии выполнения m равенств

a_i1x₁ + a_i2x₂ +... + a_inx_n = b_i, i = 1, 2,..., m

и n неравенств x_j, j = 1,2, …, n.