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

х, + 2х₂ - Зх₃ + 5x_t + x_s = 4, 5x_l - 2х₂ + 6х₄ + х₆ = 8, 2х_г + Зх₂ - 2х₃ + 3x_t + х₇ = 3, -x_l + х₃- 2х₄ + x_s = О, Xj, Х₂у... _t Х₃ ^ 0.

Пусть переменные х_ь, х₆, х₇ и х₃ составляют начальное допустимое базисное ре­шение. Предположим, что в базис вводится переменная х_г Определите, какую из переменных текущего базисного решения следует исключить из базиса так, что­бы все переменные остались неотрицательными. Найдите значение переменной х, в этом новом базисе. Повторите это упражнение для переменных х₂, х₃ и х₄.

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

Максимизировать г = х,

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

5х, + х₂ = 4, 6х, + х₃ = 8, Зх, -Ь х^ ~ 3, х,, х₂, х„ х₄>0.

a) Решите эту задачу путем нахождения точек пересечений (не используя метод Гаусса-Жордана), на каждом шаге интерпретируя полученные ре­зультаты в терминах базисных решений симплекс-метода.

b) Повторите решения задачи ЛП при тех же ограничениях, что и в п. а, но для минимизации целевой функции г = х,.

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

Максимизировать г = 5х, - 6х₂ + Зх₃ - 5х₄ + 12х₅

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

х, + Зх₂ + 5х₃ + 6х₄ + Зх₅ < 90, Xj, Х₂, х₃, Х₄, х₅ — 0. (Подсказка. Базисное решение содержит только одну переменную.)

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

3.3. Алгоритм симплекс-метода

Базис	X:	хг	хз	*4	*5		Х7	хв	Решение
z		-5			-1	-10
Хв				-2	-3	-1
Хз
Х\		-1				-4

a) Разделите все переменные на базисные и небазисные и найдите их значения.

b) Пусть решается задача максимизации. Определите небазисные перемен­ные, которые потенциально могут увеличить значение целевой функции. Для каждой такой переменной, предполагая, что она вводится в базис, найдите исключаемую переменную и соответствующее изменение целевой функции. Не используйте метод Гаусса-Жордана.

c) Повторите упражнение п. Ь, предполагая, что решается задача минимизации.

d) Какие небазисные переменные не смогут изменить значение целевой функции, если их ввести в базис?

7. Рассмотрите двухмерное пространство решений на рис. 3.7.

a) Пусть целевая функция имеет следующий вид:

максимизировать z = Зд:, + 6д:₂.

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

b) Определите вводимую переменную, значения соответствующих отношений в условии допустимости и значение целевой функции, полагая, что реали­зация симплекс-метода начинается в точке А и целевая функция имеет вид

максимизировать z = 4л:, + л:₂.

c) Повторите п. b применительно к целевой функции

максимизировать z = х, + 4д;₂.

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

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

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

Максимизировать г = 16л:, + 15л:₂

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

40л:, + 31л:₂< 124, -JC, + л:₂ < 1, л:, <3, л:,, л:₂>0.

a) Решите поставленную задачу симплекс-методом, выбирая в качестве вво­димой небазисную переменную, имеющую наибольший по абсолютной величине отрицательный коэффициент в z-строке симплекс-таблицы.

b) Решите поставленную задачу симплекс-методом, выбирая в качестве вво­димой небазисную переменную, имеющую наименьший по абсолютной величине отрицательный коэффициент в z-строке симплекс-таблицы.

c) Подсчитайте количество итераций, используемых для решения задачи в пп. а и Ь. Действительно ли выбор вводимой переменной среди небазис­ных, имеющих наибольший по абсолютной величине отрицательный ко­эффициент в z-строке, ведет к уменьшению числа итераций, выполняе­мых при реализации симплекс-метода?

d) Предположим, что задача максимизации целевой функции z заменена на задачу минимизации путем умножения функции г на -1. Как это скажет­ся на количестве итераций симплекс-метода?

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

Расход ресурса на производство одного изделия Ограничение на ресурс

Ресурс	Сумка	Чемодан	Рюкзак	(ежедневно)
Кожа (кв. футы)
Прошивка (часы)
Отделка (часы)		0,5
Отпускная цена (долл.)

Сформулируйте задачу линейного программирования, с помощью програм­мы TORA найдите ее оптимальное решение и определите статус ресурсов.

3.3.3. Реализация симплекс-метода в системе TORA

В программной системе TORA можно выполнить все итерации симплекс-метода так же, как это было описано в разделе 3.3.2. Сначала введите условия задачи (как это сделать, см. приложение Б). Затем из меню SOLVE/MODIFY выберите команду SolveOAIgebraic^lterations^AII-Slack. (Команда All-Slack (Все остаточные) указывает на то, что начальное базисное решение состоит только из остаточных дополнитель­ных переменных. Остальные команды из подменю Iterations будут описаны

3.3. Алгоритм симплекс-метода

далее в разделах 3.4, 4.3 и 7.4.2.) Далее задается точность, с которой будут отобра­жаться выходные результаты, остается щелкнуть на кнопке Go То Output Screen (Перейти к экрану вывода).

На рис. 3.8 представлено окно, в котором показаны результаты расчетов для каждой итерации для модели Reddy Mikks (файл ch3ToraReddyMikks.txt). Чтобы перейти к следующей итерации, щелкните на кнопке Next Iteration (Следующая итерация, это режим пошагового выполнения). Чтобы сразу получить окончатель­ный ответ, щелкните на кнопке All Iterations (Все итерации). Если вы выполняете вычисления в пошаговом режиме, то на каждой итерации можно указать вводимую и исключаемую переменные, щелкнув на соответствующих столбце и строке. Если ваш выбор корректен, то столбец закрасится зеленым цветом, а строка — красным. В противном случае получите сообщение об ошибке. Такой тип вычислений должен помочь вам понять основные базовые концепции симплекс-метода без громоздких вычислений по методу Гаусса-Жордана.

| TORA D:\Work\ToraFilesteh3ToraRedclyMikks.txl

LINEAR PROGRAMMING

__________________ _________ SIMPI f X 1ЛН1 I АН (Starting All Slack Method)

Title: Re ddy Mi klet mod el, Exa mple 7. 2A (Maximize) _______

Step* for oenerrtine NEXT tableau tram CURRENT one:

1. ENTERING variable: Click a NONBASIC variable (rf correct, column turn* green)

?. LEAVING variable: Click а BASIC variable (it correct, row lurna red) __3. Click c ommand button NEXT ITERATION (or Alt ITERATIONS) Thta atep maybe executed without Stcpa 1 inciter 2.

Рис. 3.8. Модель Reddy Mikks в программе TORA

УПРАЖНЕНИЯ 3.3.3

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

Максимизировать z = х_г + х₂ + Зх₃ + 2x_t при ограничениях

х₁ + 2х₂ - Зх₃ + 5х₄ < 4, 5х_г - 2х₂ + 6х₄ < 8,

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

2x_l + 3x₂-2x₃ + 3x_i<3, -x_l + х₃ + 2х₄ < О,

■^1» "^2' *^3' "^4 —

a) С помощью программы TORA найдите оптимальное решение данной задачи.

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

3.4. ИСКУССТВЕННОЕ НАЧАЛЬНОЕ РЕШЕНИЕ

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

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

3.4.1. М-метод

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

Переменная i?, с помощью достаточно большого положительного числа М штра­фуется путем ввода в целевую функцию выражения -MR_t в случае максимизации целевой функции и выражения +МД — в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной R_t. Следующий пример проясняет дета­ли этого метода.

⁵ М-метод также называют методом больших штрафов. — Прим. ред.

3.4. Искусственное начальное решение

Пример 3.4.1

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

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

Зх, -¥ х₂ ⁼ 3, 4х, + Зх₂ > 6, х, + 2х₂ < 4, х„х₂>0.

Стандартная форма этой задачи получается в результате добавления дополнитель­ной (избыточной) переменной х₃ во второе неравенство и дополнительной (остаточной) переменной х₄ в третье неравенство. Эта задача в стандартной форме будет записана следующим образом.

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

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

Зх, +х₂ = 3, 4х, + Зх₂ - х₃ = 6, х, + 2х₂ +х₄ = 4, х,, х₂, х₃, х₄ — 0.

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

Минимизировать z = 4х, + х₂ + МЛ, + MR₂

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

Зх, + х₂ + Л, = 3,

4х, + Зх₂ - х, + R₂ = 6,

х, + 2х₂ +х₄ = 4,

" х,, х₂, х₃, х₄, R₂j — 0.

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

Базис	Х1	хг	Хз	«1	Fk	*4	Решение
z	-4	-1		-М	-М
Ri
Fk			-1		ШШМШй
х4					1/

Прежде чем применять симплекс-метод, надо согласовать значения в z-строке с ос­тальной частью таблицы. В частности, значение функции z, соответствующее на­чальному базисному решению Л, = 3, Л₂ = 6 и х₄ = 4, должно равняться ЗМ+ 6М+ 0 = 9М, а не 0, как показано в таблице. Это противоречие связано с тем,

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

что переменным Л, и R₂ соответствуют ненулевые коэффициенты (-М, -М) в строке г (сравните с начальным решением в примере 3.3.1, где дополнительным перемен­ным соответствуют нулевые коэффициенты в z-строке). Чтобы сделать эти коэффи­циенты нулевыми, следует умножить элементы строк Л, и R₂ на величину М, и затем сложить эти строки с г-строкой. (Обратите внимание на "подсвеченные" единицы в этих строках — если бы эти коэффициенты были отличны от единиц, то необходимо было бы сначала разделить все элементы этих строк на данные коэф­фициенты.) Кратко это действие можно записать следующим образом.

Новая z-строка = старая z-строка + М х /?,-строка + М х /?₂-строка

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

Базис	*1	хг	хз	я.	Яг	Xi	Решение
z	-4 + 7М	-1 + AM	-М				9М
■ Я|
я2			-1
Xi

Отметим, что теперь z = 9М, что соответствует базисному решению Л, = 3, R₂ = 6 и х₄-4.

Последняя таблица готова к применению симплекс-метода с использованием усло­вий оптимальности и допустимости, описанных в разделе 3.3.2. Поскольку мы ми­нимизируем целевую функцию, находим наибольший положительный коэффици­ент в z-строке. Наибольший коэффициент -4 + 7М соответствует переменной д-,, которая и будет вводимой. Условие допустимости указывает на переменную Л, в качестве исключаемой.

Поскольку вводимая и исключаемая переменные определены, новую симплекс-таблицу можно вычислить с помощью метода Гаусса-Жордана. Заметим, что вы­числения в z-строке, где присутствует М, следует проводить алгебраически. Так, для получения новой г-строки надо новую ведущую строку умножить на -(-4 + 7М) и сложить с текущей z-строкой. В результате получим следующую таблицу.

Базис	Х\	хг		R-i	Яг	Xi	Решение
z		(1 + 5А*)/3	-м	(4 - 7М)/3			4 +2М
Х\		1/3		1/3
R.			-1	-4/3
Xi		3/5		-1/3

Отметим, что уже первая итерация исключила из базисного решения искусственную переменную R_lt что является результатом включения штрафа в целевую функцию.

Последняя таблица показывает, что следующими (вводимой и исключаемой) пере­менными будут х₂ и R₂ соответственно. Конечно, для получения оптимального ре­шения может потребоваться больше двух итераций. В данной задаче оптимальным решением будет х_х = 2/5, х₂ = 9/5, х_г = 1 и z = 17/5.

3.4. Искусственное начальное решение

При использовании М-метода следует обратить внимание на следующие два об­стоятельства.

1. Использование штрафа М может и не привести к исключению искусствен­ной переменной в конечной симплекс-итерации. Если исходная задача ли­нейного программирования не имеет допустимого решения (например, сис­тема ограничений несовместна), тогда в конечной симплекс-итерации по крайней мере одна искусственная переменная будет иметь положительное значение. Это "индикатор" того, что задача не имеет допустимого реше­ния. В разделе 3.5.4 показана такая ситуация.

2. Теоретически применение М-метода требует, чтобы М—Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Как понимать термин "достаточно боль­шая" — это открытый вопрос. Величина М должна быть настолько большой, чтобы выполнять роль "штрафа", но не слишком большой, чтобы не умень­шить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении вычислений, в которых совместно участвуют как большие, так и малые числа.

УПРАЖНЕНИЯ 3.4.1

1. Завершите решение задачи из примера 3.4.1 и получите оптимальное решение.

2. Найдите решение задачи из примера 3.4.1 с помощью программы TORA (файл ch3ToraMmethodEx3-4-l.txt), используя команду Iterations¹^M-method (Итерации^М-метод). Сравните решения при М=1,М=10иМ = 1000. Ка­кое заключение можно сделать из этого эксперимента?

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

a) Третье ограничение имеет вид л:, + 2х₂ > 4.

b) Второе ограничение имеет вид 4л:, + Зх₂ < 6.

c) Второе ограничение имеет вид 4л:, + Зх₂ = 6.

d) Целевая функция имеет вид: максимизировать z = 4л:, + х₂.

4. Существует следующее множество ограничений.

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

a) Максимизировать z = 5л:, + 6л:₂ при ограничениях (1), (3) и (4).

b) Максимизировать z = 2л;, - 7л:₂ при ограничениях (1), (2), (4) и (5).

c) Минимизировать z = Зл;, + 6л;₂ при ограничениях (3), (4) и (5).

-2xi + Зх₂ = 3,

4xi + 5х₂> 10, xi + 2x2 < 5, 6x1 + 7х₂ < 3, 4xi + 8x2 > 5,

(1) (2) (3) (4) (5)

x1, x₂>0.

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

d) Минимизировать z = 4х, + 6х₂ при ограничениях (1), (2) и (5).

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

5. Дано следующее множество ограничений:

2х, - Ъх₂ + х_г > 10,

При этих ограничениях решите задачи ЛП для следующих целевых функций.

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

b) Минимизировать z = 2х, + Зх₂ - Ъх_г.

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

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

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

Максимизировать z = 2х, + 4х₂ + 4х₃ - Зх₄ при ограничениях

Х^ "I^- ^2 ^3

х, -f 4х₂ + х₄ = 8, Xj, Х₂, Х₃, х₄ ^ 0.

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

7. Без применения искусственных переменных решите следующую задачу, ис­пользуя в начальном базисном решении переменные х₃ и х₄.

Минимизировать z = 3x_t + 2х₂ + Зх₃

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

х, -f 4х₂ + х₃ > 7, 2х, + х₂ + х₄ > 10, х,, х₂, Х₃, х₄ ^ 0.

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

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

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

х, + 2х₂ + х₃ = 3, х^ — 0»

В первом равенстве переменная х₃ может войти в базисное решение вместо искусственной переменной. Однако во втором равенстве искусственная пере­менная R₂ необходима. Используя начальное базисное решение, состоящее из переменных х₃ и Д₂, найдите оптимальное решение этой задачи.

9. Покажите, как с помощью М-метода можно определить, что следующая за­дача не имеет допустимого решения.

3.4. Искусственное начальное решение

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

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

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

3.4.2. Двухэтапный метод

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

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

Этап 2. Оптимальное базисное решение, полученное на первом этапе, исполь­зуется как начальное допустимое базисное решение исходной задачи.

Пример 3.4.2

К задаче из примера 3.4.1 применим двухэтапный метод. Этап 1

Минимизировать г = Л, + R₂

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

Зх, +х₂ + Л, = 3, 4х, + Зх₂ - х, + R₂ = 6, х, + 2х₂ + х₄ = 4, х,, Х₂, Хд, х₄, Л,, R₂, — 0. Соответствующая таблица имеет следующий вид.

Базис	X1	хг	хз	Я,	Fk	хл	Решение
г				-1	-1
fli
Fk			-1
Х{

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

Как и в А/-методе, сначала вычисляется новая r-строка по формуле новая r-строка = старая r-строка + 1 х /?,-строка + 1 х Л₂-строка

Новая r-строка используется для решения задачи первого этапа, что приведет к следующему оптимальному решению (проверьте с помощью программы TORA, выполнив команду Iterations Two-phase Method).

Базис		Хг	хг	«1	Fk	Xi	Решение
г				-V:	-1
X,			1/5	3/5	-1/5		3/5
хг			-3/5	-4/5	3/5		6/5
Xi					-1

Поскольку достигнут минимум г = О, значит, на первом этапе получено допустимое базисное решение,v, = 3/5, х_г = 6/5 и jr₄ = 1. Искусственные переменные полностью выполнили свою "миссию", поэтому из последней таблицы можно удалить их столбцы. Переходим ко второму этапу.

Этап 2

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

Минимизировать г = 4л, + х₂

с ограничениями

х, Н— х = —, ' 5 ³ 5

_ 3 ₌ 6

x₃+x_t = 1, л*,, х₂, л*₃, л*₄ ^0.

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

Базис	*i	хг	хз	Xi	Решение
z	-4
*1			1/5		3/5
хг			-3/5		6/5
Xi

Поскольку базисные переменные х₁ и х_г имеют ненулевые коэффициенты в г-строке, эту строку следует преобразовать.

Новая z-строка = старая г-строка + 4 х х,-строка + 1 х л-₂-строка. Начальная таблица второго этапа примет следующий вид.

3.4. Искусственное начальное решение

Базис	*i	хг	хз	Xi	Решение
z			1/5		18/5
*1			1/5		3/5
Хг			-3/5		6/5
хл
Так как решается задача минимизации, следует ввести переменную хъ в базис. Применение алгоритма симплекс-метода уже на следующей итерации приведет к оптимальному решению (проверьте с помощью TORA!).

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