На каждый день | Линейное программирование

ПРЕОБРАЗОВАНИЯ ЗАДАЧ К РАЗЛИЧНЫМ ФОРМАМ

Практически во всех случаях задача линейного программирования должна быть приведена к нормальной, канонической или смешанной форме при несвободных переменных. Это необходимо в тех случаях, когда предусматривается решение задачи с помощью компьютера.

Естественная форма задачи может быть приведена к канонической посредством перехода к двойственной задаче (формулы 1, 2 - "Двойственные задачи линейного программирования") с последующим преобразованием свободных переменных по одному из приведенных ниже приемов.

ЗАМЕНОЙ ПЕРЕМЕННЫХ yi=Mi+xi, где Mi - достаточно большие положительные числа, можно обеспечить выполнение условий yi≥0 (у≥0) и, учитывая, что xi=yi-Mi (i=1, 2, ..., n), получается следующая смешанная форма задачи с несвободными переменными yi≥0 (i=1, 2, ..., n).

(1)

где р-Вm,

Здесь число неизвестных не изменяется, однако если Mi - достаточно большие числа, то оптимальный план может быть определен с большой погрешностью.

УДВОЕНИЕ ЧИСЛА ПЕРЕМЕННЫХ. Каждая переменная xi заменяется разностью двух неотрицательных переменных xi=x i* -xi** или в векторной форме х=х*-**. В этом случае задача (формула 5 - "Формулировка задач линейного программирования") записывается

(2)

Такой метод приводит к удвоению числа переменных, а в вычислительном плане предъявляет повышенные требования к точности всех вычислений.

ВВЕДЕНИЕ ДОПОЛНИТЕЛЬНОЙ ПЕРЕМЕННОЙ ω≥0 и переход к новым переменным по правилу yi=xi+ω, yn+1=ω приводит к новым (n+1) переменным, на которые можно наложить требования неотрицательности yi≥0 (i=1, 2,..., n+1).

Преобразованная задача выглядит следующим образом:

(3)

Здесь В и А соответственно матрицы m×(n+1) и s×(n+1), образованные из матриц В и А по правилу

где b=(b1, b2, ..., bm)′ и a=(a1, a2, ..., as)′ - векторы размерности m и s соответственно и являются дополнительными столбцами в матрицах и

Компоненты этих векторов являются суммой всех элементов строк матриц В и A, взятых с обратным знаком. Вектор с имеет размерность n+1

 

Оптимальный план преобразованной задачи связан с оптимальным планом исходной задачи следующим образом:

Такой прием выгодно применять, когда ожидается, что в оптимальном плане исходной задачи все переменные принимают значения одного порядка.

Поделитесь ссылкой в социальных сетях