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

Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейной функции при линейных ограничениях. Так, задача (1.21) является задачей ЛП, если f, g_i, ..., g_m – линей­ные функции, а Р – полиэдр, т.е. множество, само задаваемое линейными условиями (см. (1.17)).

Задачей квадратичного программирования называется задача ми­нимизации при линейных ограничениях квадратичной функции вида

f(x)= Cx, x + d, x,

где С – симметрическая неотрицательно определенная матрица раз­мера пп, d – вектор из Rⁿ. Стало быть, задача квадратичного программирова­ния – это частный случай задачи выпуклого программирования, а задача ЛП – частный случай их обеих (С = 0). Эти два подкласса задач выпуклого программирования в настоящее время наиболее хорошо изучены.

В литературе принят ряд специальных форм записи задачи ЛП, каждая из которых удобнее других в том или ином круге вопросов. Задача ЛП в форме

,

, i =1, …, k,

, i = k+1, …, m,

x_j  0, j = 1, …, s.

называется общей, в форме

, , i = 1, …, m, (1.23)

– основной, в форме

, , i = 1, …, m, x_j  0, j = 1, …, n. (1.24)

– стандартной, в форме

, , i = 1, …, m, x_j  0, j = 1, …, n. (1.25)

– канонической. Здесь с_j, а_ij, b_i – заданные числа.

Часто прибегают к векторно-матричной записи тех же задач. Например, задачу (1.23) можно записать в виде

c, x  min, a_i, x  b_i, i = 1, …, m, (1.26)

или в виде

c, x  min, Ax  b,

где c = (c_i, ..., с_n)  Rⁿ, b = (b_i, ..., b_m)  R^m, A – матрица раз­мера тп со строками a₁, ..., a_m и элементами а_ij.

1.2.9. Задача дискретной оптимизации

В дальнейшем будем назы­вать конечные множества и счетные множества без предельных точек дискретными. Задача (1.1) (или (1.4)) называется задачей дискретной оптимизации, если либо само допустимое множество Х  Rⁿ дискретно, либо лишь некоторые из координат вектора х = (x₁, ..., x_п) пробегают дискретные множества на числовой оси, когда х пробегает X.

Часто допустимое множество задачи дискретной оптимизации имеет вид

,

где D = D₁  ...  D_n, причем D_j  {0, ±1, ±2, ...} для j  J и D_j = R для j  J. Здесь J – некоторое подмножество множества {1, ..., п}. В качестве D_j (j  J) могут выступать, например, D_j ={0, ±1, ±2,...}, D_j = {0, 1, 2,...}, D_j = {0, 1}. Это соответственно означает, что координата x_j вектора х может принимать лишь целые, натуральные, булевые значения.

Задачу (1.1) (или 1.4)) с указанным множеством Х называют задачей дискретного программирования, а при J = {1,..., п} – также задачей целочисленного программирования.

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

f(x)  min,

g_i(x)  0, i = 1, …, k, (1.30)

g_i(x)= 0, i = k+1, …, т, x  D.

Если функции f, g₁, ..., g_m линейны, то задачу (1.30) при J = {1, ..., п} называют целочисленной задачей линейного программи­рования (ЛП), а при J  {1, ..., п} – частично целочисленной зада­чей ЛП. Если D_j = {0, 1}, то иногда говорят о {частично} булевой задаче ЛП.