Меню
Главная
Авторизация/Регистрация
 
Главная arrow Экономика arrow Исследование операций в экономике

Определение минимума линейной функции

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

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

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

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

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

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

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

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

Неосновные переменные: yv у2, у5, у6.

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

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

Ζ, = Z(T,) = 29 – это значение не является минимальным, так как функцию Z можно уменьшить за счет перевода в основные любой из переменных у, или у2, имеющих в выражении для Z отрицательные коэффициенты. Так как ух имеет больший по абсолютному значению коэффициент, то начнем с этой переменной. Для нее наибольшее возможное значение: yl = min {3/3; 2/3; 1/3} = 1, т.е. первое уравнение является разрешающим; у3 становится неосновной переменной, ΔΖ, =-4-1 = -4.

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

Неосновные переменные: уТ y:i, у., у().

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

Z = 25-(5/3)¾ +(4/3)¾ +7¾ +(11 /3)¾ – линейная функция. При базисном решении У2 = (1; 0; 0; 1 /3; 0; 0) получаем Z2 = Z(Y2) = 25. Z2 – Z, = 25 – 29 = -4 = ΔΖ,. Переменную у2 переводим в основные, так как в выражение для Z она входит с отрицательным коэффициентом. Наибольшее возможное значение у2 = min {3; 3/5} = 3/5, второе уравнение разрешающее, и уА переходит в неосновные переменные; ΔΖ2 =(3/5)(-5/3) = -1.

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

Неосновные переменные: у.Л, у4, у-, у6.

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

Z = 24+у3 +3уА +6у5 + 4г/6. Базисное решение Y., = (4/5; 3/5; 0; 0; 0; 0) оптимальное, так как в выражении для Z нет неосновных переменных с отрицательными коэффициентами. Поэтому Zmjn=Z3=Z(Y3) = 24. Ζ3 -Ζ2 = 24-25 = -1 = ΔΖ2. ► Сформулируем критерий оптимальности при отыскании минимума линейной функции: если в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то решение оптимально.

Замечание. На каждом шаге симплексного метода какая-либо неосновная переменная переводится в основные, при этом каждое уравнение системы ограничений определяет конечное или бесконечное наибольшее возможное значение этой переменной – оценочное отношение. В задачах 5.1 и 5.2 встречались различные случаи оценки роста неосновной переменной, которые зависели от знаков и значений свободного члена и коэффициента при переводимой переменной. Сформулируем все возможные случаи. Обозначим: х(. – переводимая неосновная переменная, Ь■ – свободный член, а~ – коэффициент при х. В общем виде уравнение х-=/"• + ...+в^хг+... определяет наибольшее возможное значение х. по следующим правилам:

  • 1) Xj =|fy/eJ, если bj па~ разного знака и аГ) *0, !>■ #0; например: х3 = 8 – 2х2 +...; х2 =8/2 = 4 или х3 = -8 + 2х2+...; х2 =8/2 = 4;
  • 2) х,- = оо, если bj и ay одного знака и а~ ф 0, bj ф 0; например: Х3 = 8 + 2х2 +...; Х2 = оо;
  • 3) xi = 0, если Ь = 0 и аТ <0; например: х3 =0-2.х2 + ...; х2=0;
  • 4) X/ = о®, если Ь. = 0 и ау >0; например: х3 =0 + 2х2 +...; Х2 = оо;
  • 5) х(. = оо, если a.j = 0; например: х3 =5 + 0-х2 +...; х3 = -5 + 0-х2+...; х2=оо.
 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы