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

1(1 - г,)у, + 3(1 - г₂)у₂ + 1(1 - г₃)у₃ < 3

4.4. Разновидности симплекс-метода

После подстановки значений у, = 1, у_г = 2 и у₃ = 0 получим следующее неравенство (проверьте!): г, + 6г₂ > 4.

Таким образом, любые значения величин г₁ и г₂, от 0 до 1, удовлетворяющие нера­венству г, + 6г₂ > 4, приведут к доходности производства моделей поездов. Напри­мер, для значений г, = 0,6 и г_г = 0,6 получаем z, - с, = 4 - 0,6 - 6x0,6 = -0,2. Вместе с тем отметим, что сокращение времени выполнения второй операции в 6 раз эф­фективнее сокращения времени выполнения первой операции.

УПРАЖНЕНИЯ 4.3.2

1. В задаче из примера 4.3.2 предположим, что время выполнения второй опе­рации при сборке модели поезда сокращено с 3 до 1,25 минуты. На сколько должно быть сокращено время выполнения первой операции, чтобы произ­водство этой игрушки стало доходным?

2. В задаче из примера 4.3.2 предположим, что фабрика игрушек рассматрива­ет возможность производства еще одного вида игрушки — модели пожарной машины. При сборке этой модели первая операция не используется, а вторая и третья требуют соответственно 1 и 3 минуты для сборки одной модели. До­ход от одной модели пожарной машины составляет 4 долл. Посоветуете ли вы фабрике производить эти игрушки?

3. Компания использует токарные и сверлильные станки для производства четы­рех типов деталей: РР1, РР2, РРЗ и РР4. В следующей таблице представлены технологические данные, характеризующие производство этих деталей.

Станок	Время обработки одного изделия (минуты)	Фонд машинного
	РР1	РР2	РРЗ	РР4	времени (минуты)
Токарный
Сверлильный
Доход от одного изделия (долл.)

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

4. Рассмотрите оптимальное решение задачи из предыдущего упражнения. Компания подсчитала, что с помощью специальных мероприятий можно уменьшить общее время производства изделий, не вошедших в оптималь­ное базисное решение, на 20%. Будет ли после этого производство таких изделий рентабельно? Если нет, то на сколько следует сократить время производства данных изделий?

4.4. РАЗНОВИДНОСТИ СИМПЛЕКС-МЕТОДА

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

Глава 4. Двойственность и анализ чувствительности

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

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

Эти три алгоритма — прямой, двойственный и обобщенный — дают основу для проведения анализа чувствительности, как будет показано в разделе 4.5.

4.4.1. Двойственный симплекс-метод

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

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

Двойственное условие оптимальности. Вводимая в базис переменная определя­ется как переменная, на которой достигается следующий минимум:

min

нсб&шсныел:

а„<0

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

Чтобы существовало начальное оптимальное ("супероптимальное") и недопус­тимое решение, необходимо выполнение двух условий.

1. Целевая функция должна удовлетворять условию оптимальности обычного симплекс-метода (см. главу 3).

2. Все ограничения должны быть неравенствами типа "<".

Второе условие можно удовлетворить простым умножением на -1 неравенств типа ">". Если есть ограничения в виде равенств, то эти равенства заменяются на два не­равенства. Например, равенство х_х + х₂ = 2 эквивалентно двум неравенствам

4.4. Разновидности симплекс-метода

х_г + х_г<2, X, + х₂>2,

или лг, + х₂<2, -jc, — jc₂< —2.

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

Пример 4.4.1

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

Минимизировать z = Злг, + 2х_г

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

Зх, +x₂>3, 4jc, + Зл-₂ > 6, л^-, +x₂ < 3, л-,,л-₂>0.

Сначала первых два неравенства умножаются на -1, чтобы привести их к неравенст­вам типа "<". Начальная симплекс-таблица этой задачи имеет следующий вид.

Базис	x^	Х2	хз	Х4	хь	Решение
z	-3	-2
Хз	-3	-1				-3
Х4	-4	-3				-6
Х5

Поскольку Zj - Cj < 0 для всех j= 1, 5, начальное базисное решение (х₃ = -3, x_t = -6, x_s = 3) является оптимальным и недопустимым.

Двойственное условие допустимости указывает на переменную х₄ {= -6) как на ис­ключаемую из базиса. Теперь применим двойственное условие оптимальности для определения вводимой переменной. Для этого используем следующую таблицу.

Переменные xi хг хз х₄ Хб

ООО О 1 О

Приведенные отношения показывают, что вводимой переменной будет л-₂. Отметим, что переменные x_f будут кандидатами на включение в базисное решение только тогда, когда коэффициент a_4j будет строго отрицательным. По этому критерию переменные х_ъ, х₄ и х_ъ не рассматриваются как кандидаты на включение в базис.

z-строка (Zj - Су) хд-строка, щ

z,-c.

Отношение

а.

-3 -4

3 4

-2 -3

' 3

Глава 4. Двойственность и анализ чувствительности

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

Базис	Х1	Х2	хз	Xt	Х5	Решение
z	-1/3			-2/3
х3	-5/3			-1/3		-1
хг	4/3			-1/3
хъ	-1/3			1/3
Отношение	"1/5	—	—		—
Последняя таблица показывает, что из базиса исключается переменная х3 и вводит-
ся дг,. В результате получаем следующую симплекс-таблицу.
Базис	xi х2	хз	Xt		Хъ	Решение
z	0 0	-1/5	-3/5			21/5
XI	1 0	-3/5	1/5			3/5
хг	0 1	4/5	-3/5			6/5
Хъ	0 0	-1/5	2/5			6/5
Решение, представленное в последней таблице, допустимо (и оптимально), поэтому
вычисления заканчиваются. Это решение имеет вид		3/5, х2 = 6/5 иг = 21/5.

На рис. 4.2 показана последовательность шагов двойственного симплекс-метода при решении задачи из примера 4.4.1. Алгоритм начинается в крайней точке А (которой соответствует недопустимое, но "лучше, чем оптимальное" решение), за­тем он переходит к точке В (которой также соответствует недопустимое, но "лучше, чем оптимальное" решение) и заканчивается в точке С, уже принадлежа­щей области допустимых решений.

Программа TORA позволяет выполнять двойственный симплекс-метод в пошаговом режиме. Для этого -в меню SOLVE/MODIFY выберите команду Solve^Algeraic^ Iterations¹^ Dual Simplex (Решить¹^Алгебраически^ИтерацииОДвойственный сим­плекс-метод). Помните, что сначала надо ограничения в виде равенств преобразо­вать в неравенства. Неравенства типа ">" преобразовывать в противоположные не­равенства не нужно, поскольку TORA автоматически выполнит преобразование задачи к виду, необходимому для применения двойственного симплекс-метода. Ес­ли задача не удовлетворяет начальным требованиям для применения двойственно­го симплекс-метода, то на экране появится соответствующее сообщение. Как и в обычном симплекс-методе, здесь в пошаговом режиме TORA позволяет вручную указывать вводимые и исключаемые переменные.

УПРАЖНЕНИЯ 4.4.1

1. На рис. 4.3 показано пространство решений, соответствующее задаче мини­мизации целевой функции г = 2х, + х₂. Предполагается, что поиск решения выполняется двойственным симплекс-методом; оптимальное решение соот­ветствует точке F — (0,5, 1,5).

4.4. Разновидности симплекс-метода

*2

Рис. 4.2. Итерации двойственного симплекс-метода из примера 4.4.1 х₂

		-
		G				D/
		/F\
		I \
-1	L	1.		3 4
	-1
	к

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

а) Если начальное базисное (недопустимое) решение соответствует точке G, будет ли алгоритм двойственного симплекс-метода проходить через точки G, Е, F7 Обоснуйте это.

Глава 4. Двойственность и анализ чувствительности

Ь) Если начальное базисное (недопустимое) решение соответствует точке L, определите на рис. 4.3 возможную последовательность точек, через кото­рые будет проходить алгоритм двойственного симплекс-метода для дос­тижения оптимального решения в точке F.

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

a) Минимизировать z = 2х, 4- Зх₂ при ограничениях

2х, + 2х₂ < 30, x, + 2x_s>10, х„ х₂>0.

b) Минимизировать z = 5jc₁ + 6х₂ при ограничениях

х, + х₂ > 2, 4jc₁ + х₂ > 4, х,, х₂>0.

c) Минимизировать z — 4дс, + 2х₂ при ограничениях

х, + х₂ = 1, Зх,-х₂>2, х,, х₂>0.

d) Минимизировать z = 2х, + Зх₂ при ограничениях

2*; + х₂ > 3, х, + х₂ = 2, x_v х₂ > 0.

3. Двойственный "симплекс-метод с искусственными ограничениями. Дана следующая задача ЛП.

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

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

2х_г + Зх₂- 5х₃>4, -х, + 9х₂- х₃> 3, 4х, + 6х₂ + Зх₃ < 8, х„ х₂, х₃>0.

Начальное базисное решение содержит дополнительные переменные х₄, х_ь их₆ и является недопустимым, поскольку х₄ = -4 и х_б = -3. Но непосредственное применение двойственного симплекс-метода невозможно, так как переменные x_t и х₃ не удовлетворяют условию оптимальности для задачи максимизации. По­кажите, что введение искусственного ограничения х, + х₃<М (где М— доста­точно большое положительное число и такое, что данное неравенство не сужает область допустимых решений исходной задачи) и последующее использование

4.4. Разновидности симплекс-метода

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

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

a) Максимизировать z = 2х₃ при ограничениях

-я, + 2х₂ - 2х₃ > 8,

-дс, + х₂ + х₃ <4, 2х_х -х₂ + 4х₃ < 10, х_1У х₂, х₃>0.

b) Максимизировать z = х_х - Зх₂ при ограничениях

х₁~х₂<2, х, + х₂> 4, 2х_г-2х₂>3, х_г, х₂>0.

c) Минимизировать z = -х_х + х₂ при ограничениях

- 4х₂> 5, х₁-3х₂<1, 2х_х - 5х₂> 1, х_г, х₂ > 0.

d) Максимизировать z = 2х₃ при ограничениях

-х₁ + 3х₂-7х₃>5, -х₁ + х₂-х₃<1, Зх, + х₂ - lQx₃ < 8, х„ jc₂, х₃>0.

5. Решите следующую задачу ЛП тремя различными методами (используя в качестве инструмента программу TORA). Определите, какой метод будет наиболее эффективным при вычислениях.

Минимизировать z = бх, + 7х₂ + Зх₃ + 5x_t

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

5x, + 6х₂ - 3*з + 4х₄ > 12, х₂ - 5лс₃ - 6x_t > 10, 2x_l + 5x₂ + x₃ + x_i>&, x_v х₂, х₃, x_t>0.

Глава 4. Двойственность и анализ чувствительности

4.4.2. Обобщенный симплекс-метод

В прямом симплекс-методе (см. главу 3) начальное решение допустимо, но не оп­тимально. В двойственном симплекс-методе данное решение оптимально (точнее, "супероптимально"), но не допустимо. Возникает естественный вопрос: можно ли начать решение задачи ЛП с неоптимального и недопустимого решения? Мы видели, что в прямом симплекс-методе при отсутствии допустимого начального решения ис­пользуются искусственные переменные. В двойственном симплекс-методе при отсут­ствии оптимального начального решения также применяются искусственные огра­ничения. Хотя задача этих процедур и состоит в обеспечении автоматического выполнения вычислений, необходимо не терять из виду основную идею симплексных алгоритмов, а именно то, что оптимальное решение задачи ЛП достигается в одной из крайних (угловых) точек пространства допустимых решений. С учетом этих замеча­ний можно разработать симплексный алгоритм решения задач ЛП, в котором на­чальное решение будет и неоптимальным, и недопустимым. Следующий пример по­казывает, как можно обобщить симплексный алгоритм.

Пример 4.4.2

Рассмотрим задачу из упражнения 4.4.1.4, а. В качестве начальной таблицы можно принять следующую симплекс-таблицу, где представлено начальное решение (х₄, х₅, х_в), которое не оптимально (из-за переменной х,) и не допустимо (так как x_t = -8). (Заметим, что в этой таблице первое равенство умножено на -1 для того, чтобы пока­зать недопустимость решения непосредственно в столбце "Решение".)

Базис	*1	*2	хз	Х4	Х5	Хб	Решение
z			-2
Xi		-2					-8
Хъ	-1
Х6		-1

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

Базис	Х1	Х2	хз	Х4	хъ	Хб	Решение
z			-2
	-1/2		-1	-1/2
хъ	-1/2			1/2
Хъ	3/2			-1/2

4.5. Анализ чувствительности оптимального решения

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

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

УПРАЖНЕНИЯ 4.4.2

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

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

4.5. АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОПТИМАЛЬНОГО РЕШЕНИЯ

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

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

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

Результат изменения исходной задачи

Текущее базисное решение остается оптимальным и допустимым

Текущее решение становится недопустимым

Текущее решение становится неоптимапьным

Текущее решение становится неоптимальным и недопустимым

Рекомендуемые действия Никаких действий не производится

Используется двойственный симплекс-метод для восстановления допустимости решения

Используется прямой симплекс-метод для восстановления оптимальности решения

Используется обобщенный симплекс-метод для получения нового решения

Первые три ситуации рассмотрены в этом разделе. Четвертая ситуация как ком­бинация второй и третьей представлена в комплексной задаче 4.3.

Глава 4. Двойственность и анализ чувствительности

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

Прямая задача

Двойственная задача Минимизировать w = 430yi + 460у₂ + 420уз при ограничениях

У\ + Зу₂ + у₃ > 3,

2yi + 4у₃ > 2,

У: + 2у₂ > 5,

У1.У2, Уз 5 0.

Максимизировать z= 3xi + 2х₂ + 5хз

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

xi + 2x2 + х₃ < 430 (операция 1), 3xi + 2х₃ < 460 (операция 2), xi + 4х₂ < 420 (операция 3), Хь х₂, х₃> 0.

Оптимальное решение

xi = 0, х₂ = 100, х₃ = 230, z = 1350 долл.

Оптимальное решение у, = 1, у₂ = 2, уз = 0, w = 1350 долл.

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

Базис	Х1	х2	Хз		хь	х6	Решение
z
х2	-1/4			1/2	-1/4
Хз	3/2				1/2
х6				-2

4.5.1. Изменения, влияющие на допустимость решения

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

Изменение правых частей ограничений. Изменение правых частей ограничений исходной задачи требует повторных вычислений правых частей ограничений в симплекс-таблице, для чего используется формула 1 из раздела 4.2.4.

Обратная матрица 1 ГНовый столбец правых' из симплекс-таблицы на /-й итерации

Новый столбец правых частей ограничений в симплекс-таблице на i-й итерации

частей ограничении исходной задачи

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

4.5. Анализ чувствительности оптимального решения

Пример 4.5.1

Предположим, что фабрика игрушек TOYCO планирует расширить производство своей продукции путем увеличения возможностей сборочных линий на 40%, что даст следующий фонд рабочего времени для каждого вида сборочной операции: 602, 644 и 588 минут соответственно. Эти изменения влияют только на правые час­ти неравенств ограничений (и на оптимальное значение целевой функции). Нахо­дим новое базисное решение задачи.

— —- 0

'6024		'140'
	=
,588,		,28,

Таким образом, текущие базисные переменные х_г, х₃ и х₆ с новыми значениями 140, 322 и 28 по-прежнему составляют допустимое решение. Соответствующее этому решению оптимальное значение целевой функции (максимальный доход) равно 1890 долл.

Хотя новое решение и приводит к увеличению дохода фабрики, реализация меро­приятий, необходимых для такого наращивания производства, требует определен­ного времени. Временной альтернативой такой модернизации производства может служить "перенос" неиспользуемого фонда рабочего времени третьей операции (х₆ = 20 минут) в фонд первой. Тогда фонд рабочего времени трех сборочных опера­ций будет равен 450, 460 и 400 минут соответственно. С учетом новых ограничений получаем следующее решение.

			\
							'по)
хъ	-					-
					,400,		,-40,
	,-2		К

Полученное решение не является допустимым, поскольку теперь д:₆ = -40. Для воз­врата в область допустимых решений применим двойственный симплекс-метод. Сна­чала изменим значения в столбце "Решение" симплекс-таблицы (эти новые значения выделены в следующей симплекс-таблице). Отметим, что соответствующее значение целевой функции равно г = 3х0 + 2х110 + 5х 230 = 1370 долл.