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

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

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

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

при условиях

ai1x1 + ai2x2 +… + ainxn ≤ bi, i = 1, 2, ..., m; j = 1,2, …, n,

или

–ai1x1 – ai2x2 –… – ainxn + bi ³ 0.

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

ai1x1 + ai2x2 +… + ainxn + xn+1 = bi.

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

L = c1x1 + c2x2 +… + cnxn

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

ai1x1 + ai2x2 +… + ainxn = bi, i = 1, 2, ..., m

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