В следующей таблице перечислены все базисные и небазисные решения текущего примера.

Как видно из примера 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) Определите, чему на рисунке, где представлено пространство решений, соответствует недопустимое базисное решение.

3. Путем перебора всех базисных решений найдите оптимальные решения следующих задач линейного программирования.

a) Максимизировать z = 2хх - 4х2 + Ьх3 - 6xt при ограничениях

хг + 4х2 - 2х3 + 8xt < 2, -л:, + 2л:.,-1-Зл:3-1-4л:4<1, х х2, х3, х4 0.

b) Минимизировать z = л:, + 2х2 - Зх3 - 2xt при ограничениях

л:, + 2х2 - Зх3 + х4 = 4, jc, + 2л:2 + х3 + 2xt = 4, Хр х2, х3, х4 - 0.

4. Покажите, что все базисные решения следующей задачи ЛП недопустимы.

Максимизировать z = л:, + х2

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

л:, + 2х2<6, 2л:, + х2 > 16, л: jc2>0.

5. Дана следующая задача ЛП.

Максимизировать z = 2л:, + Зх2 + Ъх3

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

-6л:, + 7л:2- 9л:3>4, -л:, + л:2 + 4л:3 = 10, л: л:3>0,

л:2 - свободная переменная. Приведите задачу к стандартной форме, используя для этого подстановку л, =х* - л, . Покажите, что в этой задаче не существует базисных решений, в

которые входили бы одновременно х, и х\.

6. Рассмотрите следующую задачу ЛП.

Максимизировать z = л:, + Зл:2

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

л:, + л:2< 2, -л:, + л:2 < 4,

л:, - свободная переменная, л:2>0.

a) Найдите все допустимые базисные решения этой задачи.

b) С помощью подстановки решений в целевую функцию определите наилучшее базисное решение.

c) Решите эту задачу графическим способом и докажите, что решение, найденное в предыдущем пункте, является оптимальным.

3.3. АЛГОРИТМ СИМПЛЕКС-МЕТОДА

Основываясь на определениях из раздела 3.2, мы можем найти оптимальное решение задачи линейного программирования, записанной в стандартной форме, путем простого перебора всех базисных (допустимых) решений. Но, конечно, такая процедура не эффективна. Алгоритм симплекс-метода находит оптимальное решение, рассматривая ограниченное количество допустимых базисных решений. В разделе 3.3.1 мы покажем итерационную природу симплекс-метода, а в разделе 3.3.2 - вычислительные детали его алгоритма.

3.3.1. Итерационная природа симплекс-метода

На рис. 3.3 показано пространство решений задачи ЛП из примера 3.2.1. Обычно алгоритм симплекс-метода начинается с исходной точки, где хх = х2 = 0 (точка А). В этой начальной точке значение целевой функции г равно нулю. Возникает естественный вопрос: если одна или обе небазисные переменные хх и х2 примут положительные значения, то приведет ли это к улучшению (возрастанию) значений целевой функции? Для ответа на этот вопрос рассмотрим целевую функцию

максимизировать г = 2хх + Зх2.

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

1. Если увеличивать значение переменной хх, то (см. рис. 3.3) ее значение должно возрасти таким образом, чтобы соответствовать угловой точке В (повторим, что внутренние точки отрезка от точки А до точки В неприемлемы, поскольку кандидатом на оптимальное решение может быть только угловая точка). В точке В симплекс-метод должен увеличить значение переменной х2, перемещаясь при этом в угловую точку С. Так как точка С соответствует оптимальному решению, то на этом процесс вычислений заканчивается. Таким образом, алгоритм симплекс-метода создает путь А-> В - С.

2. Если сначала увеличивать значение переменной х2, то следующей угловой точкой будет точка D, из которой процесс решения переходит в оптимальную точку С. Здесь алгоритм симплекс-метода создает путь А -> Z) - С.

Отметим, что оба пути, A>B->CnA->D->C, расположены вдоль границы пространства решений. Это означает, что симплекс-метод не может сразу перескочить из точки А в точку С.

Может возникнуть правомерный вопрос: существует ли правило, в соответствии с которым можно было бы определить, какую небазисную переменную сделать положительной в данной угловой точке? Например, в точкеА как переменная хх, так и переменная х2 могут увеличить значение целевой функции. Симплекс-метод предлагает простое правило выбора переменных, которое в основном применяется в его программных реализациях. Поскольку здесь мы рассматриваем задачу максимизации, то следует выбирать такую небазисную переменную, которая имеет наибольший положительный коэффициент в выражении целевой функции. Если таких переменных несколько, то выбор произвольный. Необходимо понимать, что это эмпирическое правило, сформулированное на основе многочисленных компьютерных вычислений симплекс-метода - в большинстве случаев (но не обязательно всегда) применение этого правила ведет к наименьшему числу итераций, затрачиваемых на поиск оптимального решения.