2. Для каждой задачи из упражнения 3.4.1.4 запишите соответствующую целевую функцию для первого этапа.

3. Решите задачи из упражнения 3.4.1.5 двухэтапным методом.

4. Покажите, что следующая задача не имеет допустимого решения. Запишите задачу ЛП для первого этапа и затем примените программу TORA для поиска ее решения.

Максимизировать z = 2х, + 5х2 при выполнении условий

Зх, + 2х2>6, 2х,+ х2<2, х х2>0.

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

Максимизировать z = 2х, + 2х2 + 4х3 при выполнении условий

2х, + х2 + х3 < 2, Зх, + 4х2 + 2х3>8, х х2, х3>0.

a) Используя программу TORA, покажите, что первый этап закончится с нулевой искусственной базисной переменной.

b) Выполните вручную вычисления второго этапа с нулевой искусственной переменной, являющейся частью начального базисного решения. Убедитесь, что искусственные переменные никогда не принимают положительных значений.

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

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

Максимизировать z = Зх, + 2х2 + Зх3 при выполнении условий

2х, + х2 + х3 = 2, х, + Зх2 + х3 = 6, Зх, + 4х2+ 2х3>8, х х2, х3>0.

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

b) Покажите, что описанная в упражнении 5.3 процедура, применяемая в конце первого этапа, может только одну из двух нулевых искусственных переменных сделать небазисной.

c) Покажите, что исходное ограничение, соответствующее нулевой искусственной переменной, которую нельзя сделать небазисной в п. Ь, является избыточным. Следовательно, строку этого ограничения, как и его искусственную переменную, можно удалить перед началом второго этапа.

7. Дана следующая задача линейного программирования.

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

при выполнении условий

2х, + х2 + х3 < 2,

Зх, + 4х2 + 2х3 > 8,

х х2, х3>0.

Оптимальная симплекс-таблица, полученная в конце первого этапа, имеет следующий вид

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

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

8. Дана задача линейного программирования.

Минимизировать z = 2х, - 4х2 + Зх3

при выполнении условий

5х, - 6х2 + 2х3 > 5,

-х, + Зх2 + 5х3 > 8,

2хх + 5х2 - 4х3 < 9,

х х2, х3>0.

Покажите, что неравенства можно свести к множеству равенств, которое потребует введения только одной искусственной переменной (вместо возможных двух искусственных).

3.5. ОСОБЫЕ СЛУЧАИ ПРИМЕНЕНИЯ СИМПЛЕКС-МЕТОДА

В этом разделе рассмотрим четыре особых случая, встречающихся при использовании симплекс-метода.

1. Вырожденность.

2. Альтернативные оптимальные решения.

3. Неограниченные решения.

4. Отсутствие допустимых решений.

При изучении этих случаев основное внимание мы уделим, во-первых, теоретическому обоснованию причин, приводящих к таким ситуациям, и, во-вторых, их практическим интерпретациям применительно к реальным задачам.

3.5.1. Вырожденность

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

В вырожденном решении нет никакой опасности, за исключением небольших теоретических неудобств, которые мы далее кратко обсудим. С практической точки зрения вырожденность объясняется тем, что в исходной задаче присутствует по крайней мере одно избыточное ограничение. Для того чтобы лучше понять практические и теоретические аспекты явления вырожденности, рассмотрим численный пример. Графическая интерпретация задачи поможет наглядно разобраться в этом явлении.

Пример 3.5.1. Вырожденное оптимальное решение

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

Максимизировать z = Зх, + Эх,

при выполнении условий

х, + 4х2 < 8, х, + 2х,<4, х х2>0.

Обозначим через х3 и х4 дополнительные переменные. Результаты применения симплекс-метода представлены в следующей таблице.

На начальной итерации в качестве исключаемой можно выбрать как переменную хъ, так и х4. Если оставить в базисе переменную х4, на следующей итерации она