Отыскание минимума линейной функции

При определении минимума линейной функции Z возможны два пути: 1) полагая F = -Z, отыскать максимум F, учитывая, что Z _min= - F _max; 2) модифицировать симплексный метод: на каждом шаге уменьшать линейную функцию за счет той неосновной переменной, которая входит в выражение линейной функции с отрицательным коэффициентом. Рассмотрим это на следующем примере:

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

Z= 18 y ₁ + 16 у ₂ + 5 у ₃ + 21 y ₄ min при ограничениях:

Решение. Введем дополнительные неотрицательные переменные y ₅ и y ₆, со знаком "минус", так как неравенства имеют вид " ". Получаем систему уравнений:

Если на первом шаге в качестве основных взять дополнительные переменные, то получим недопустимое базисное решение: (0;0;0;0;-2;-3). В данном случае удобно в качестве основных взять переменные у ₃и у ₄(это согласуется с правилом выбора основных переменных, сформулированным в § 5.2); так как коэффициенты при у ₃и у ₄положительны, получим в е первоначального допустимое базисное решение.

I шаг. Основные переменные: y ₃, y ₄. Неосновные переменные: y ₁, y ₂ y ₅, y ₆.

Выражаем основные переменные через неосновные:

Y ₁ = (0; 0; 3; ; 0; 0) — первое базисное решение, оно допустимое. Выражаем линейную функцию через неосновные переменные:

=29 — это значение не является минимальны так как функцию Z можно уменьшить за счет перевода в основные любой из переменных у ₁ или у ₂, имеющих в выражении для Z отрицательные коэффициенты. Так как у ₁ имеет больший по абсолютному значению коэффициент, то значение этой переменной. Для нее наибольшее возможное значение: , т.е. первое уравнение является разрешающим; у ₃ становится неосновной переменной .

II шаг. Основные переменные: y ₁, y ₂. Неосновные переменные: y ₃, y ₄ y ₅, y ₆.

Получим после преобразований:

- функция цели.

При базисном решении Y ₂ = (1;0;0;1/3;0;0) получаем . Переменную переводим в основные, так как в выражение для Z она входит с отрицательным коэффициентом. Наибольшее возможное значение у ₂ = min {3; 3/5} = 3/5, второе уравнение разрешающее, и y ₄ переходит в неосновные переменные; .

III шаг. Основные переменные: y ₁, y ₂. Неосновные переменные: y ₃, y ₄ y ₅, y ₆.

Получим после преобразований:

. Базисное решение оптимальное, так как в выражении для Z нет неосновных переменных с отрицательными коэффициентами. Поэтому

.

Сформулируем критерий оптимальности при отыскании минимума линейной функции: если в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то решение оптимально.

Замечание. На каждом шаге симплексного метода какая-либо неосновная переменная переводится в основные, притом каждое уравнение системы ограничений определяет конечное или бесконечное наибольшее возможное значение этой временной – оценочное отношение. В примерах 5.1 и 5.2 встречались различные случаи оценки роста неосновной переменной, которые зависели от знаков и значений свободного члена и коэффициента при переводимой переменной. Сформулируем все возможные случаи.

Обозначим: х_i — переводимая неосновная переменная, b_j — свободный член, а_ij — коэффициент при x_i. В общем виде уравнение определяет наибольшее возможное значение х_i по следующим правилам:

1) , если разного знака и например: или .

2) , если одного знака и например: .

3) , если , например: .

4) , если , например: .

5) , если , например: .