Пример 3.4.

.

1. Система приведена к каноническому виду (см. раздел 2).

2. Ранг основной и расширенной матрицы r = 3, тогда в соответствии с теоремой Кронекера-Капелли система совместна и базис относительно переменных х ₁, х ₂, х ₃ уже выделен. Свободные члены после выражения базисных переменных остаются положительными.

Целевая функция выражена через свободные переменные х ₄ и х ₅ и стремится к min.

3. Приравниваем свободные переменные х ₄ и х ₅ к нулю и получим начальное опорное решение

для которого . Все вышеперечисленные действия представляют собой 0-й шаг. Обращаем внимание, что свободные переменные равны нулю, а базисные переменные приняли положительные значения.

4. На 1-м шаге попытаемся уменьшить значение f (), что можно добиться только увеличением значения х ₅, так как оно стоит со знаком «–». Увеличим значение х ₅ так, чтобы х ₁, х ₂, х ₃ не стали отрицательными, оставив х ₄ = 0. Из 2-го уравнения системы следует, что х ₅ можно увеличить до 2. Т. о., получаем новое решение = (5, 0, 1, 0, 2) и f () = – 2 уменьшилось.

На 2-м шаге за свободные переменные принимают х ₂и х ₄ (нулевые значения в ), а остальные переменные за новый базис х ₁, х ₃, х ₅ (ненулевые значения в ). Для этого из 2-го уравнения системы выражают х ₅ через х ₂ и х ₄. Базисные переменные х _1, х ₃ и целевую функцию f () также выражаем через новые свободные переменные х ₂и х _4.

.

Для уменьшения будем увеличивать х ₄. Из системы видно, что при условии неотрицательности х ₃ (х ₂=0) значение х ₄ можно увеличить до х ₄= (третье уравнение). Тогда новое допустимое решение =(, 0, 0, , ) и f () = – .

3-й шаг. Свободные переменные х ₂ и х ₃, а базисные х ₁, х ₄, х ₅. Из третьего уравнения выражаем х ₄ через х ₂ и х _3, а в первом и третьем уравнениях делаем преобразования с учетом выражения х ₄ через х ₂ и х _3. Кроме того, преобразовываем значение целевой функции с учетом выражения х ₄ через х ₂ и х _3. Получим:

Т. к. в последнее выражение целевой функции все переменные входят с положительными коэффициентами, то её наименьшее значение достигается при х ₂ = 0, х ₃ = 0. Это означает что решение = (, 0, 0, , ) является оптимальным, т.е. f _min() = – .

Анализируя ход решения, т.е. минимизацию, можно сделать выводы:

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

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

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