Приведение общей задачи линейного программирования к канонической форме

В большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных.

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

Это может быть сделано следующим образом:

Возьмем линейное неравенство

и прибавим к его левой части некоторую величину , такую, что неравенство превратилось в равенство

При этом данная величина является неотрицательной.

Пример

Привести к каноническому виду задачу линейного программирования:

При наличии ограничений в виде неравенств

Решение:

Перейдем к задаче на отыскивание максимума целевой функции.

Для этого изменим знаки коэффициентов целевой функции.

Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x₄ x₅ (на математической модели эта операция отмечена буквой Д).

Переменная х₄ вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".

Переменная x₅ вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".

В целевую функцию переменные x₄ x₅ вводятся с коэффициентом. равным нулю.

Записываем задачу в каноническом виде:

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Данный метод является методом целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует.

Алгоритм симплексного метода решения задач линейного программирования

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

1. Привести задачу к каноническому виду

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)

3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Пример решения задачи симплексным методом

Пример 1

Решить симплексным методом задачу:

Минимизировать значение функции

F = 10x1 - 4x3 max

При наличии ограничений в виде неравенств

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x₅ с коэффициентом +1. В целевую функцию переменная x₅ входит с коэффицентом ноль (т.е. не входит).

Получаем:

F = 10x1 - 4x3+0∙x5 max

При наличии ограничений в виде неравенств

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,5,9/15,6) с единичным базисом Б1 = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Δ_k = C_бX_k — c_k

Где:

· C_б = (с₁, с₂, ... , с_m ) — вектор коэффициентов целевой функции при базисных переменных

· X_k = (x_1k, x_2k, ... , x_mk ) — вектор разложения соответствующего вектора А_к по базису опорного решения

· С_к — коэффициент целевой функции при переменной х_к.

·

Оценки векторов входящих в базис всегда равны нулю.

Опорное решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу:

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

В последней строке таблицы с оценками Δ_k в столбце "А₀" записываются значения целевой функции на опорном решении Z(X₁).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ₁ = -2, Δ₃= -9 для векторов А₁ и А₃ отрицательные.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции находится по формуле:

.

Вычисляем значения параметра θ₀₁ для первого и третьего столбцов по формуле:

Получаем θ₀₁ = 6 при l = 1, θ₀₃ = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора

ΔZ₁ = — 6*(- 2) = 12,

и третьего вектора ΔZ₃ = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ₀₃ достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение

Х2 = (0,0,3,21,42,0)

с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6.

Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ₀₂ для второго столбца, он равен 7 при l = 2.

Следовательно, из базиса выводим второй вектор базиса А4.

Производим преобразование Жордана с элементом х₂₂ = 3, получаем третье опорное решение

Х3 = (0,7,10,0,63,0)

Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ₁ = 7/2, Δ₄ = 2, Δ₆ = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).