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

Обшая задача линейного программирования состоит в следующем. Даны (m x n) - матрица A, m - вектор b и n - вектор c. Требуется найти n - вектор x, являющийся точкой максисума целевой функции

на множестве, заданном m неравенствами, которые можно записать как Ax≤b.

Для решения задач линейного программирования используют методы:

• Симплекс-метод. Используют для решения задачи линейного программирования. Требует экспоненциального времени.
• Метод эллипсоидов. Используют для решения задачи линейного программирования за полиномиальное время, но на практике работает медленно.
• Алгоритм Кармакара. Полиномиальный алгоритм, сравнимый по практической эффективности с симплекс-методом.

Задача линейного программирования может заключаться, в некоторых случаях, в нахождении допустимого решения, т.е. требуется найти решение неравенств Ax≤b. Нас интересуют задачи именно этого типа.

Система ограничений на разности - это система линейных неравенств Ax≤b, для которой в каждой строке матрицы A присутствуют ровно два ненулевых элемента, один из которых равен 1, а другой -1. Т.е. все неравенства имют вид:

Если система ограничений на разности представлена в виде Ax≤b, где A - (m x n) - матрица, удобно рассмотреть ориентированный граф, для которого A будет матрицей инцидентности. Т.е. свяжем с системой взвешенный оринтированный граф ограничений G = (V, E), в котором V = {v₀, v₁, ..., v_n}, а каждому неравенству x_i - x_j ≤ b_k соответствует ребро (v_i, v_j) с весом b_k. В графе имеются n рёбер (v₀, v₁), (v₀, v₂), ..., (v₀, v_n) (каждое - веса 0).

Пример: граф ограничений, соответствующий системе линейных неравенств.

Решение систем ограничений на разности

Решение системы ограничений на разности можно найти с помощью алгоритма Беллмана-Форда.

Система m ограничений на разности с n неизвестными порождает граф с n + 1 вершиной и не более чем n + m рёбрами. Поэтому найти хотя бы одно решение можно за время

O((n+1)(n+m))=O(n²+mn).