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

При определении минимума линейной функции Z возможны два пути:

1) отыскать максимум функции F, полагая и учитывая, что

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

Рассмотрим это на следующем примере.

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

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

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

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

I шаг. Основные переменные:

Неосновные переменные:

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

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

Для нее наибольшее возможное значение: , т.е. первое уравнение является разрешающим; становится неосновной переменной,

II шаг. Основные переменные:

Неосновные переменные:

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

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

III шаг. Основные переменные:

Неосновные переменные:

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

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