Целевая функция сформулирована на минимум.

Все ограничения заданы в виде уравнений;

Все переменные неотрицательны;

Стандартная форма ЗЛП, правила построения.

Симплекс-метод решения ЗЛП.

Лекция 3

Вопросы:1. Стандартная форма ЗЛП, правила построения.

2. Канонический вид ЗЛП, начальное допустимое базисное решение (НДБР),

метод искусственного базиса.

3. Симплекс-метод.

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

Стандартная форма ЗЛП представляет собой такой вид задачи, в котором:

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

Правила построения стандартной формы ЗЛП:

1) Если F(x) = C₁x₁ + C₂x₂ + … + C_nx_n max, то можно искать

F(x) = - C₁x₁ – C₂x₂ - … - C_nx_n min.

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

Например: 2х₁ + 3х₂ 4 2х₁ + 3х₂ + х₃ = 4, х₃ - уравновешивающая переменная.

4x₁ + 2x₂ 5 4x₁ + 2x₂ – x₄ = 5, x₄ - уравновешивающая переменная.

3) Если некоторая переменная х может быть не ограничена знаком, то в стандартном виде такую переменную можно представить в виде разности двух неотрицательных переменных: x = x' – x'', x' , x'' .

При этом дополнительные переменные не входят в целевую функцию. Стандартная форма ЗЛП в матричном виде выглядит так: Ax = b, x , F(x) = C^Tx min.