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

При определении минимума линейной функции 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)¾ +73/4 +(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=оо.