Рассмотрим симплексный метод решения следующей задачи на минимум.
Z=\iyi+\6y2- 5уз + 2\у4 min. При ограничениях:
у,2у23у,>2 Зу,У2У,>3 у,>0, / = 1,2,3,4.
Сведем данную задачу к каноническому виду, для чего введем дополнительные переменные с отрицательным знаком, так как неравенства имеют вид « > ».
Получим систему уравнений:
у-\-2у2-Зу-у=2 Зу,-У2-у,-Уб=3.
Выберем в качестве основных переменных >з, у4, Шаг1. Основные переменные уз,У4. Неосновные переменные УиУ2,У5,Уб.
Выражаем основные переменные через неосновные:
У,=3-Зу,-У2+Уе 2 12 1
>4 = 3-->l-->2+3>5-
Первое базисное решение Yi получим, приравняв к нулю все неосновные переменные Yi = (0; 0; 3; 2/3; 0; 0).
Учитывая, что все координаты вектора Y неотрицательны, это решение допустимо.
Выразим линейную целевую функцию Z через неосновные переменные:
г=\ух + \6у2-5уз-2\у4= 18>1+ 16>2+5(3-3>1->;2 + >б) + 2\(-у,-У2у,) = 29-4у,-Зу2-1у55уе,
Zi = OZ(ri) = 29. Значение Z=29 не является оптимальным, так как функцию Z можно уменьшить за счет перевода в основные любой из переменных у1 или у2, имеющих в выражении для Z отрицательные коэффициенты. Так как у\ имеет больший по абсолютному значению коэффициент, то переведем в основные эту переменную.
Для нее наибольшее возможное значение определяется из соотношения >i = min (1,2} =1, т.е. первое уравнение становится разрешающим.
Следовательно,>зстановится неосновной переменной, Ь2\ = -4 • 1 =-4. Шаг 2. Основные переменные y\,y. Неосновные переменные
УъУъ.Уь.Уь.
Получим после преобразований:
>i=l-3>2-J>3 + 3>6
15 111
5 4И
Z = 25--y2+-y2-lys-y6- целевая функция. При базисном
решении Y2 = (1; 0; 0; 1/3; 0; 0) получаем Z2 = 2(72) = 25; Z2-Z1 = = 25-29 = -4 = AZi.
Переменную у2 переводим в основные, так как в выражении для Z она входит с отрицательным коэффициентом. Наибольшее возможное значе-• 3] 3
ниедгттЗ.г--, поэтому второе уравнение разрешающее и у4 пе-
реходит в неосновные переменные;
AZ2= -
= -1.
ШагЗ. Основные переменные дьдг. Неосновные переменныеуз, у4, у.
Получим после преобразований
4 2 3 1 2
У1=--~Уз+-У4--У5+-Уб
3 19 3 1
У2 = 5+7>з " 5>4 +-У5--Уб-
г = 24+уз + 3у4 + 6у5 + 4уб. Базисное решение Уз = (4/5; 3/5; 0; 0; 0; 0).
Оно оптимально, так как в выражении для целевой функции Z нет неосновных переменных с отрицательными коэффициентами. Поэтому
2шш=ад)=24.
Сформулируем критерии оптимальности при отыскании минимума целевой функции: если в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то решение оптимально.
В рассмотренных примерах применения симплексного метода на каждом шаге какая-либо неосновная переменная переводится в основные. При этом определяется наибольшее возможное значение вновь вводимой основной переменной.
Сформулируем все возможные случаи оценки роста неосновной переменной. Обозначим через Х{ переводимую неосновную переменную, bi- свободный член, -коэффициент при В общем виде уравнение xj= bi+,+ ... определяет наибольшее возможное значение xi по следующим правилам:
1) Xi =
, если 6у> О и Gij< 0; например: лгз = 8 - 2x2 + ...; Х2 = 8/2,
2)х/= 00, если bj и щ одного знака и щч 0; bj О например, хз = 8 + 2хз+ ...;х2= оо,
3)х/= О, если Z)y = О и а/,<О, например,хз = 0-2x2+ Х2 = О,
4)Xj= 00, если А, = О и (3/,> О, например,Хз = О + 2x2 + ...;2=
5)Ху= 00, если а,у=0, например, хз = 5 + 0*Х2+хз = -5 + 0*Х2+
Х2= 00,
6)ху= оо,если6у<0иа/,>0, например, хз=-8 +2x2+...;х2= Практические расчеты при решении реальных задач симплексным методом выполняются с использованием компьютеров. Если же задачи небольшой размерности решаются вручную, то удобнее использовать так называемые симплексные таблицы. Рассмотрим общую схему формирования симплексной таблицы.
Пусть ранг матрицы А равен т. Базисом опорного плана будем называть произвольную линейно независимую систему из т столбцов матрицы Л, включающую в себя все столбцы, соответствующие ненулевым координатам опорного плана.
Рассмотрим каноническую задачу линейного программирования в следующем виде:
max ZcfX,(3.7)