она имеет только одно решение3; если же т< пи система уравнений совместна, то она имеет бесконечное множество решений. Простая иллюстрация в качестве доказательства: для уравнения х = 2 имеем т = п = 1, а его решение, очевидно, единственное. Для уравнения х + у = 1 имеем т - 1 и п = 2, этому уравнению удовлетворяет бесконечное множество решений (любая точка на прямой х + у=1 будет решением).
В алгебраическом представлении кандидаты на оптимальное решение (т.е. те же угловые точки в графическом представлении) определяются из системы линейных уравнений следующим образом. Пусть т < п (это условие выполняется для большинства задач ЛП), тогда полагаем п - т переменных равными нулю и решаем систему из т уравнений относительно оставшихся т переменных; если решение этой системы единственно, то оно соответствует угловой точке пространства решений.
Следующий пример иллюстрирует это положение.
Пример 3.2.1
Рассмотрим следующую задачу ЛП с двумя переменными.
Максимизировать z= 2хх + Зх2
при выполнении условий
2.v,+x,<4, хх + 2х.г < 5, xltx2>0.
На рис. 3.2 показано пространство решений для этой задачи. х2
0 1 2 3 4 5
Рис. 3.2. Пространство решений для примера 3.2.1
Это не совсем верно: совместная система уравнений имеет единственное решение тогда, когда она невырождена. - Прим. ред.
После преобразования к стандартной форме имеем следующую задачу ЛП.
Максимизировать z = 2хх + Зхг
при выполнении условий
2дг, + х2 + s, = 4, я, + 2хг + s2 = 5,
*2* 1 2 - *
Здесь имеем систему из т = 2 уравнений для л = 4 переменных. Согласно сформулированному выше правилу угловые точки можно определить алгебраически, присвоив я-т = 4- 2 = 2 переменным нулевых значений и решив затем систему уравнений относительно оставшихся т = 2 переменных. Если, например, положить х1 = 0их2 = 0, тогда решением системы будет s, = 4, s2 = 5. Это решение соответствует точке Л на рис. 3.2 (убедитесь, что решение 5, = 4, s2 = 5 действительно соответствует точке А). Другую угловую точку можно определить, если положить s, = 0 и 52 = 0. В этом случае надо найти решение системы
2хх + х2 = 4,
л-! + 2д-2 = 5.
Решением в данном случае будет jt, = 1 и х, = 2, что соответствует точке С на рис. 3.2.
Вас, вероятно, интересует, как определить, какие п - т переменные положить равными нулю, чтобы получить конкретную угловую точку. Без графического представление пространства решений (что возможно только для задач с двумя и тремя переменными) нельзя сказать, какие п - т нулевые переменные соответствуют той или иной угловой точке. Однако это не мешает перечислить все угловые точки пространства решений. Для этого надо просто рассмотреть все комбинации п - т переменных, приравнять их к нулю и затем найти решение полученной системы уравнений. Оптимальное решение, которое доставляет наилучшее значение целевой функции, будет среди допустимых угловых точек.
В нашем примере мы имеем = "Tj= Угловых точек. Но, глядя на рис. 3.2,
можно насчитать только 4 угловые точки -А, В, С nD. Где "спрятались" еще две точки? В действительности точки Е и F также являются угловыми точками, но это недопустимые угловые точки, поскольку они не удовлетворяют всем ограничениям задачи. Такие недопустимые угловые точки не рассматриваются как кандидаты на оптимальное решение.
Для полного перехода к алгебраическому методу решения задач ЛП необходимо как-то назвать угловые точки разного типа на "алгебраическом" языке. На этом языке п - т переменные, которые полагаются равными нулю, называются небазисными переменными. Если оставшиеся т переменные имеют единственное решение, то в этом случае они называются базисными переменными, а совокупность значений, которые они получают в результате решения системы уравнений, составляют базисное решение (см. рис. 3.1). Если при этом все переменные принимают неотрицательные значения, то такое базисное решение является допустимым. В противном случае - недопустимым.4
i В русскоязычной математической литературе также применяются термины "план", "опорный план" и "оптимальный опорный план" как эквиваленты для терминов "базисное решение" , "допустимое базисное решение" и "оптимальное базисное решение". - Прим. ред.
В следующей таблице перечислены все базисные и небазисные решения текущего примера.
Небазисные | Базисные | Базисные | Соответствующие | Допустимо | Значение |
(нулевые) | пере- | решения | угловые точки | ли решение? | целевой |
переменные | менные | | | | функции z |
(*, х2) | (Si, 8г) | (5, 4) | | | |
| (*г, 8г) | (4, -3) | | | |
(X1. s2) | (*г, Si) | (2,5, 1,5) | | | |
(*2, Si) | (*1, S2) | (2, 3) | | | |
(*2, S2) | (*1, Si) | (5, -6) | | | |
(Si, «г) | (Xi, x2) | (1,2) | | | 8 (оптимум) |
Как видно из примера 3.2.1, при возрастании размера задачи (т.е. при увеличении значений пит) процесс перечисления всех угловых точек становится отдельной чрезвычайно сложной задачей. Например, при п = 20 и т = 10, когда необходимо решить С°0 = 184756 систем уравнений порядка 10x10, получаем устрашающую, в вычислительном отношении, задачу. Здесь следует учесть, что задачи ЛП размерности 10x20 считаются небольшими - реальные задачи могут иметь сотни и даже тысячи переменных и ограничений. Однако симплекс-метод в значительной степени снимает эту проблему, поскольку он рассматривает не все возможные базисные решения (т.е. угловые точки пространства решений), а только часть всех допустимых базисных решений.
УПРАЖНЕНИЯ 3.2
1. Проверьте все базисные и небазисные решения, приведенные в конце примера 3.2.1.
2. Дана следующая задача ЛП.
Максимизировать z = 2хх + Зх2
при ограничениях
+ Здс2 < 6, Зх1 + 2хг<6, xv хг>0.
a) Запишите задачу в стандартной форме.
b) Найдите все базисные решения этой задачи и определите, какие из них допустимые, а какие - нет.
c) Путем непосредственной подстановки решений в целевую функцию определите наилучшее допустимое базисное решение.
d) Подтвердите графическим способом, что решение, полученное в предыдущем пункте, является оптимальным. Отсюда следует, что оптимальное решение можно получить путем перебора множества допустимых базисных решений.
e) Определите, чему на рисунке, где представлено пространство решений, соответствует недопустимое базисное решение.