Стандартная форма задач линейного программирования

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

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

1. Максимизация целевой функции Z = c_1×x₁ + c_2×x₂ +... + c_n×x_n равносильна минимизации целевой функции Z = - c_1×x₁ - c_2×x₂ -... - c_n×x_n.

2. Ограничение в виде неравенств, например 4×x₁ + 5×x₂ 800, может быть при­ведено к стандартной форме 4×x₁ + 5×x₂ + x₃ = 800, где x₃ - новая неотрицательная переменная.

Ограничение может быть приведено к стандартной форме , где новая переменная x₅ неотрицательна.

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

, где и .

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

Приведем к стандартной форме задачу, рассмотренную в примере 1.

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

минимизировать функцию Z = - 20x₁ - 40x₂

при ограничениях

3x₁ + 4x₂ + x₃ = 1700,

2x₁ + 5x₂ + x₄ = 1600,

, i = 1, …,4.

В матричной форме ограничения можно записать следующим образом:

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

решением.

Конечно, имея два уравнения с четырьмя неизвестными, можно получить

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

Переменные, приравненные нулю, называются небазисными переменными.

Остальные называются базисными и образуют базис.

Дата добавления: 2014-01-06