На каждый день | Линейное программирование
ПРЕОБРАЗОВАНИЯ ЗАДАЧ К РАЗЛИЧНЫМ ФОРМАМ
Практически во всех случаях задача линейного программирования должна быть приведена к нормальной, канонической или смешанной форме при несвободных переменных. Это необходимо в тех случаях, когда предусматривается решение задачи с помощью компьютера.
Естественная форма задачи может быть приведена к канонической посредством перехода к двойственной задаче (формулы 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
Оптимальный план преобразованной задачи связан с оптимальным планом исходной задачи следующим образом:
Такой прием выгодно применять, когда ожидается, что в оптимальном плане исходной задачи все переменные принимают значения одного порядка.
Вернуться к списку
|
Распечатать
|
