Linear Programming Output summary 5 страница

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

1. Если в ведущем столбце коэффициент, соответствующий нулевой базисной искус­ственной переменной, положителен, тогда ведущий элемент определяется авто­матически (поскольку ему соответствует минимальное отношение, равное нулю), и искусственная переменная на следующей итерации становится небазисной.

2. Если ведущий элемент равен нулю, следующая итерация оставляет искусст­венную переменную нулевой.

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

Итак, правило для второго этапа заключается в том, чтобы искусственные пере­менные оставлять в базисе всегда, когда коэффициент в ведущем столбце положи­телен или отрицателен. Фактически это правило применяется в конце первого эта­па, когда из базисного решения удаляются нулевые искусственные переменные, перед тем как приступить ко второму этапу (см. упражнение 3.4.2.5).

УПРАЖНЕНИЯ 3.4.2

1. Ответьте на следующие вопросы.

a) Почему на первом этапе двухэтапного метода всегда минимизируется сумма искусственных переменных?

b) Если в задаче ЛП требуется найти максимум целевой функции, то следует ли на первом этапе максимизировать сумму искусственных переменных?

Глава 3. Симплекс-метод

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

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

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

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

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

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

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

2х_х + х₂ + х₃ < 2, Зх_х + 4х₂ + 2х₃ > 8, х_х, х₂, х₃>0.

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

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

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

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

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

2х_х + х₂ + х₃ = 2, х_х + Зх₂ + х₃ = 6, Зх_х + 4х₂+2х₃>8, х_х, х₂, х₃>0.

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

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

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

3.5. Особые случаи применения симплекс-метода

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

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

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

2х, + х₂ + х₃ < 2,

Зх, + 4х₂ + 2х₃ > 8,

х„ х_г, х₃>0.

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

Базис	*1	хг	хз	хл	х5	Я	Решение
z	-5		-2	-1	-4
хг
Я	-5		-2	-1	-4

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

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

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

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

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

5х, - 6х₂ + 2х₃ > 5,

-х, + Зх₂ + 5х₃ > 8,

2х, + 5х₂ - 4х₃ < 9,

х„ х₂, х₃>0.

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

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

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

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

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

Глава 3. Симплекс-метод

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

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

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

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

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

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

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

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

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

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

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

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

Итерация	Базис	Х1	хг	хз	Xi	Решение
Начальная	z	-3	-9
Вводится хг	Хз
Исключается хз	Xi
Первая	Z	-3/4		9/4
Вводится *1	хг	1/4		1/4
Исключается х4	хЛ	1/2		-1/2		0 ■
Вторая	Z			3/2	3/2
Оптимум	хг			1/2	-1/2
	Х1			-1

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

3.5. Особые случаи применения симплекс-метода

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

Что же практически приводит к вырожденности решения? Рассмотрим рис. 3.9, графически представляющий решение этой задачи. Точка оптимума х, = О, х_г — 2 является пересечением трех прямых. Поскольку данная задача двухмерна, эта точка переопределена (на плоскости для определения точки достаточно двух пря­мых), и, следовательно, одно из ограничений избыточно.

х₂

Оптимальное вырожденное решение

Рис. 3.9. Вырожденность задачи примера 3.5.1

На практике информация о том, что некоторые ресурсы недефицитны, может быть полезной при интерпретации результатов решения задачи. Эти сведения также мо­гут помочь выявить неточности и ошибки в постановке исходной задачи. К сожале­нию, не существует способов определить избыточное ограничение непосредственно изданных симплекс-таблиц.

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

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

х, = 0, х₂ = 2, х₃ = 0, х₄ = 0, z = 18.

Можно ли, несмотря на то, что оптимальное решение не достигнуто, остановить вычисления на первой итерации (когда впервые обнаруживается вырожденность)? Ответ отрицательный, так как решение может быть только временно вырожден­ным (упражнение 3.5.1.2).

Глава 3. Симплекс-метод

УПРАЖНЕНИЯ 3.5.1

1. Рассмотрите графическое представление пространства решений (рис. 3.10). Предположим, что выполнение симплекс-метода начинается из точки А, оп­тимальное решение соответствует точке D, а целевая функция такова, что в точке А вводимой переменной будет х,.

a) Покажите (на рисунке) крайние точки, которые соответствуют последова­тельности симплекс-итераций, приводящих к точке оптимума.

b) Определите максимально возможное число симплекс-итераций, необхо­димых для достижения оптимального решения.

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

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

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

3. Используя в программе TORA опции, позволяющие управлять процессом вы­числений, выполните последовательность симплекс-итераций в следующей зада­че ЛП (задача придумана Е. М. Beale). Начальное допустимое базисное решение, состоящее из дополнительных переменных, повторится на седьмой итерации. Этот пример иллюстрирует явление зацикливания при выполнении симплекс-метода; в этом случае оптимальное решение никогда не будет достигнуто.

Рис. 3.10. Пространство решений для упражнения 1

4х,+ 3х₂<12, 4х, - х₂< 8, 4х,+ х₂<8, х,, х₂>0.

Максимизировать z

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

8х₂ - х₃ + 9х₄ < 0,

12х,

'■■>--^х* + Зх. < 0,

² 2

3.5. Особые случаи применения симплекс-метода

х₃<1,

^1' ^2> ^3' ^4 —

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

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

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

Когда прямая (если рассматривается двухмерная задача ЛП, в общем случае — гиперплоскость), представляющая целевую функцию, параллельна прямой (гиперплоскости), соответствующей связывающему неравенству (которое в точке оптимума выполняется как точное равенство), целевая функция принимает одно и то же оптимальное значение на некотором множестве точек границы простран­ства решений. Эти решения называются альтернативными оптимальными реше­ниями. Следующий пример показывает, что таких решений (если они существуют) бесконечное множество. Этот пример также проиллюстрирует практическую зна­чимость альтернативных решений.

Пример 3.5.2. Бесконечное множество решений

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

Максимизировать z = 2x_l + 4х₂

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

х, + 2х₂ < 5, х, +х,<4, x_vx₂>0.

На рис. 3.11 показано множество альтернативных оптимальных решений, которые яв­ляются следствием того, что прямая, представляющая целевую функцию, параллельна прямой;^- соответствующей связывающему ограничению. Каждая точка отрезка ВС соответствует оптимальному решению со значением целевой функции z = 10. Последовательные итерации выполнения симплекс-метода представлены в сле­дующей таблице.

Итерация	Базис	XI	Хг	х3	Xi	Решение
Начальная	z	-2	-4
Вводится хг	Хз
Исключается хз	Xl
Первая (оптимум)	Z	0.
Вводится Х\	хг	1/2		1/2		5/2
Исключается	Xi	1/2		-1/2		3/2
Вторая	Z
(альтернативный	хг				-1
оптимум)	x^			-1

Глава 3. Симплекс-метод

*2

Рис. 3.11. Альтернативные оптимумы в примере 3.5.2

На первой итерации получаем оптимальное решение х_х = 0, х_г = 5/2 и z = 10, кото­рое соответствует точке В на рис. 3.11. Как узнать из симплекс-таблицы, что суще­ствует альтернативное оптимальное решение? Посмотрите на коэффициенты неба­зисных переменных в г-строке первой итерации. Коэффициент небазисной переменной х, равен нулю, это означает, что данную переменную можно ввести в базис без изменения значения целевой функции, но значение самой переменной д-, изменится. Введение переменной х_х в базисное решение выполнено на второй ите­рации, при этом из базиса исключена переменная x_t. Получено новое решение л:, = 3, х₂ = 1, z = 10, которое соответствует точке Сна рис. 3.11.

Симплекс-метод может определить только две угловые точки В и С. Математически мы можем найти все точки (х\,х\) отрезка ВС как взвешенное среднее (с неотрица­тельными весами) точек В и С. Если 0 < ос < 1 и

В: х, = 0, х, = 5/2,

С', л", ⁼ 3, х₂ = 1,

координаты любой точки отрезка ВС можно записать следующим образом:

х\ = а х 0 + (1 - а) х 3 = 3 - За,

5 3 jc, = ах - + (1 - а) х 1 = 1 + - а. 2 2

При а = 0 (х\,х'_г) = (3, 1), что соответствует точке С. При а=1 получаем (х[,х'₂) = (0, 5/2) — это точка В. Если значение а лежит строго между 0 и 1, получа­ем внутренние точки отрезка ВС.

На практике альтернативные оптимальные решения весьма полезны, поскольку позволяют сделать выбор среди множества решений без ухудшения значения целевой функции. Например, в рассмотренной выше задаче переменная л:₂ принимает нулевое значение в точке В, тогда как в других альтернативных оптимальных решениях ее значение положительно. Если интерпретировать задачу как задачу организации про­изводства двух видов товара (которые соответствуют переменным д;, и д;₂), то с учетом конкуренции на рынке более рационально производить оба вида товара, а не один. В этом случае решение, соответствующее точке С, предпочтительнее.

3.5. Особые случаи применения симплекс-метода

УПРАЖНЕНИЯ 3.5.2

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

Максимизировать г = х, + 2х₂ + Зх₃

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

x,+2x₂-l-3x₃<10, х, + х₂ < 5,

х,, х_г, х₃>0.

2. Покажите с помощью программы TORA, что следующая задача ЛП имеет альтернативные оптимальные решения и все они небазисные. Для этой зада­чи представьте на плоскости пространство решений и прямую, соответст­вующую целевой функции.

Максимизировать г = 2х, - х₂ + Зх₃

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

х, - х₂ + 5х₃< 10, 2х, - х₂ + Зх₃ < 40, *i> х₂, х₃>0.

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

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

х, + 2х₂<5, х, + х₂-х₃<2, 7х, + Зх₂ - 5х₃ < 20, х,, х₂, х₃>0.

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

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

Неограниченность решения задачи свидетельствует только об одном: модель раз­работана не достаточно корректно. Типичные ошибки, приводящие к построению та­ких моделей, заключаются в том, что не учитываются ограничения, не являющиеся избыточными, и не точно оцениваются параметры (коэффициенты) ограничений.

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

Глава 3. Симплекс-метод

Пример 3.5.3. Неограниченная целевая функция

Рассмотрим задачу

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

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

х,-х₂<10, 2х, < 40, х„ х₂ > 0.

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

Базис	Xi	хг	Хз	Х4	Решение
z	-2
хз
Х4

Из этой таблицы видно, что в качестве вводимой переменной можно взять как х,, так и х₂. Поскольку переменная х, имеет максимальный (по абсолютной величине) отрицательный коэффициент в z-строке, именно ее следует ввести в базисное реше­ние. Однако заметим, что во всех ограничениях коэффициенты, стоящие перед пе­ременной х₂, отрицательны или равны нулю. Это означает, что значение перемен­ной х₂ может возрастать до бесконечности, и при этом не нарушается ни одно ограничение. Поскольку увеличение на 1 значения переменной х₂ приводит к уве­личению на 1 значения целевой функции, следовательно, неограниченное увеличе­ние значения переменной х₂ ведет к неограниченному увеличению значения целе­вой функции. Эта ситуация проиллюстрирована на рис. 3.12. На этом рисунке видно, что пространство допустимых решений не ограничено в направлении оси х₂, и значение целевой функции может быть каким угодно большим.

Неограниченное пространство решений

2x^40

Неограниченное значение целевой функции

Рис. 3.12. Неограниченность решения в примере 3.5.3

3.5. Особые случаи применения симплекс-метода

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

УПРАЖНЕНИЯ 3.5.3

1. В задаче из примера 3.5.3 с помощью программы TORA покажите, что при­менение симплекс-метода, когда согласно условию оптимальности вычисле­ния начинаются с переменной л:, в качестве вводимой, обязательно приведет к неограниченному решению.

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

Максимизировать z = 20л:, + 10л:₂ + л:₃ при выполнении условий

Зл:, - Зх₂ + 5л:₃ < 50, л:, + л:₃< 10, х, - л:₂ + 4л:₃ < 20, х„ х₂, х₃>0.

a) Рассмотрев ограничения, определите направление (по оси л:,, л:₂ илил:₃), в котором пространство допустимых решений не ограничено.

b) Без дополнительных вычислений сделайте заключение относительно оп­тимального значения целевой функции.

3. В некоторых плохо построенных моделях ЛП пространство допустимых ре­шений может быть неограниченным даже тогда, когда задача имеет конечное (ограниченное) оптимальное решение. Такое может случиться, если при по­строении ограничений допущены ошибки. В больших задачах иногда трудно визуально определить, является ли пространство допустимых решений огра­ниченным. Разработайте процедуру определения неограниченности про-

• странства решений.

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

Если ограничения задачи ЛП несовместны (т.е. они не могут выполняться одно­временно), то задача не имеет допустимых решений. Такая ситуация не может воз­никнуть, если все неравенства, составляющие систему ограничений, имеют тип "<" с неотрицательными правыми частями, так как в этом случае дополнительные пе­ременные могут составить допустимое решение. Для других типов ограничений ис­пользуются искусственные переменные. И хотя в оптимальном решении все искус­ственные переменные в силу штрафов равны нулю, такой исход возможен только тогда, когда задача имеет непустое пространство допустимых решений. В против­ном случае в оптимальном решении будет присутствовать хотя бы одна положи­тельная искусственная переменная.

С практической точки зрения отсутствие допустимых решений свидетельствует о том, что задача плохо сформулирована.

Глава 3. Симплекс-метод

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

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

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

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

2а-, + х_г<2, Зх, + 4х₃> 12, x_ltx₂>0.

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

Итерация	Базис	*1	хг	Xi	Хз	Я	Решение
Начальная	z	-3-ЗМ	-2-AM	М			-12М
Вводится хг	хз
Исключается хз	Я			-1
Первая	Z	1 +5М		М	2 + 4М		4-4М
(псевдооптимум)	хг
	R	-5		-1	-4

Данные из этой таблицы показывают, что в точке оптимума искусственная пере­менная R имеет положительное значение (= 4), что свидетельствует об отсутствии до­пустимого решения. На рис. 3.13 графически представлена ситуация данной задачи. Алгоритм симплекс-метода, допуская положительные значения искусственной пе­ременной, по существу, превращает неравенство Зд-,+ 4дг₃>12 в Зх, + 4дг₃ < 12. (Объясните, почему так происходит.) В результате получаем то, что можно назвать псевдооптимальным решением.

х₂

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

Литература

УПРАЖНЕНИЯ 3.5.4

1. Компания производит изделия трех типов Tl, Т2 и ТЗ. На их изготовление расходуется материал Ml и М2 согласно данным следующей таблицы.

	Расход материалов на единицу изделия
Материал	Т1 Т2	ТЗ
М1	3 5
М2	5 3

Ежедневно можно использовать не более 1000 единиц материала Ml и 1200 еди­ниц материала М2. Отдел маркетинга настаивает, чтобы суммарное ежеднев­ное производство изделий составляло не менее 500 единиц. Может ли произ­водство удовлетворить это требование? Если ответ отрицательный, помогите компании составить наиболее выгодную структуру производства изделий. 2. Дана следующая задача ЛП.