Стандартная форма линейных оптимизационных моделей 2 страница

⇐ ПредыдущаяСтр 7 из 12Следующая ⇒

Базисные переменные	z	x_e	x_i	S₁	S₂	S₃	S₄	Решение Отношение
z		-3	-2
S₁								6 6/1=6
S₂								8 8/2=4
S₃		-1
S₄		0

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

Столбец С-Т, ассоциированный с вводимой переменной, будем называть ведущим столбцом.

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

После того как определены включаемая и исключаемая переменные (с использованием условий оптимальности и допустимости), следующая итерация (поиск нового базисного решения) осуществляется методом исключения переменных, или методом Гаусса – Жордана. Этот процесс изменения базиса включает вычислительные процедуры двух типов:

Тип1. (формирование ведущего уравнения).

Новая ведущая строка = предыдущая ведущая строка/ Ведущий элемент

Тип 2 (формирование всех остальных уравнений, включая z – уравнение)

Новое уравнение = Предыдущее уравнение – (коэффициент ведущего столбца предыдущего уравнения) х (Новая ведущая строка).

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

Применяя к исходной таблице процедуру типа 1, мы делим S₂– уравнение на ведущий элемент, равный 2. Так как в столбце базисных переменных x_e занимает место переменной S₂, указанная процедура приводит к следующим изменениям исходной симплекс – таблицы:

Базисные переменные	z	x_e	x_i	S₁	S₂	S₃	S₄	Решение
z
S₁
x_e			1/2		1/2			8/2=4
S₃
S₄

Заметим, что в столбце «Решение» теперь фигурирует новое значение переменной x_e =4, которое равно минимальной величине отношений, анализируемых при проверке условия допустимости.

Чтобы составить новую симплекс – таблицу выполним необходимые вычислительные процедуры типа 2.

1. Z – уравнение. Предыдущие z- уравнение: (1 –3 –2 0 0 0 0 0)

- (-3) Новая ведущая строка: (0 3 3/2 0 3/2 0 0 12)

=Новое z - уравнение: (1 0 –1/2 0 3/2 0 0 12)

2. S₁-уравнение

Предыдущее S₁-уравнение: (0 1 2 1 0 0 0 6)

-(1)х Новая ведущая строка: (0 -1 -1/2 0 -1/2 0 0 -4)

= Новое S₁- уравнение: (0 0 3/2 1 –1/2 0 0 2)

3. S₃- уравнение.

Предыдущее S₃- уравнение: (0 -1 1 0 0 1 0 1)

-(-1)х Новая ведущая строка: (0 1 ½ 0 ½ 0 0 4)

= Новое S₃- уравнение: (0 0 3/2 0 ½ 1 0 5)

4. S₄- уравнение. Новое S₄- уравнение будет таким же, как и предыдущее, поскольку соответствует коэффициент ведущего столбца равен нулю.

Новая симплекс – таблица, полученная с помощью рассмотренных операций, имеет следующий вид:

Базисные переменные	Z	X_E	X_i	S₁	S₂	S₃	S₄	Решение
Z		0	-1/2		3/2		0
S₁	0	0	3/2	1	-1/2	0	0	2 2/(3/2)=4/3
X_E			1/2		1/2			4 4/(1/2)=8
S₃			3/2		1/2			5 5/(3/2)=10/3
S₄			1					2 2/1=2

В новом решении Х_Е= 4 и Х₁ = 0 (т.В на рис. 2). Значение Z возросло с 0 до 12. Это увеличение обусловлено тем, что прирост Х_Е на единицу обеспечивает увеличение Z на 3 единицы: таким образом, прирост целевой функции Z составляет 3 х 4 = 12.

Заметим, что новая симплекс – таблица обладает такими же характеристиками, как и предыдущая: только небазисные переменные Х₁ и S₂равны нулю, а значение базисных переменных, как и раньше, представлены в столбце «Решение». Это в точности соответствует результатам, получаемым при использовании метода Гаусса – Жордана.

Из последней таблицы следует, что на очередной итерации в соответствии с условием оптимальности в качестве вводимой переменной следует выбрать Х₁, так как коэффициент при этой переменной в Z- уравнении равен – ½.

Исходя из условия допустимости, определяем, что исключаемой переменной будет S₁. Отношения, фигурирующие в правой части таблицы, показывают, что в новом базисном решении значение включаемой переменной Х₁ будет равен 4/3(= min отношению). Это приводит к увеличению целевой функции на (4/3) х (1/2) = 2/3.

К получению симплекс – таблицы, соответствующий новой итерации, приводят следующие вычислительные операции метода Гаусса – Жордана.

1. Новое ведущее (Х₁) – уравнение = Предыдущее S₁ – уравнение /(3/2).

2. Новое Z – уравнение = предыдущее Z – уравнение – (-1/2) х новое ведущее уравнение.

3. Новое Х_Е – уравнение = предыдущее Х_Е – уравнение – (1/2) х новое ведущее уравнение.

4. Новое S₃ – уравнение = предыдущее S₃ – уравнение – (3/2) х новое ведущее уравнение.

5. Новое S₄ – уравнение = предыдущее S₄ – уравнение –(1) х новое ведущее уравнение.

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

Базисные переменные	z	x_e	x_i	S₁	S₂	S₃	S₄	Решение
z				1/3	4/3			12 х 2/3
_Х_i				2/3	-1/3			4/3
х_е				-1/3	2/3			10/3
S₃				-1
S₄				-2/3	1/3			2/3

В новом базисном решении Х_Е = 3 х 1/3 и Х₁ = 1 х 1/3 (точка С на рис. 2) Значение Z увеличилось с 12 (предыдущий симплекс – таблица) до 12 х 2/3. Этот результирующий прирост целевой функции (12 х 2/3 – 12) = 2/3 обусловлен увеличением Х₁ от 0 до 4/3, так как из Z- строки предыдущий симплекс – таблицы следует, что возрастанию данной переменной на единицу соответствует увеличение целевой функции на ½.

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

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

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

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

Упражнения.

1. Предположим, что при использовании симплекс – метода в задаче на отыскание максимума в качестве включаемой в базис переменной выбирается любая из небазисных, имеющих отрицательный коэффициент в Z – уравнении. Приведут ли в этом случае итерации симплекс – метода получению оптимального решения?

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

2. Воспользуйтесь графическим методом решения для задачи фирмы Reddy Mikks (рис. 2). Пусть начальному решению соответствует т. А, причем Х₁ представляет собой переменную, включаемую в базис на следующий итерации. Определите отношения, используемые при проверке условия допустимости, непосредственно из графика. Сравните полученные результаты с данными исходной симплекс – таблицы. Какая переменная подлежит исключению из базиса?

Ответ: Отношения (координаты точки пересечения с осью Х₁) равны 3, 8, 1 и 2. Исключению из базиса подлежит переменная S₃.

3. Применительно к условиям з. №2 определите увеличение целевой функции в базис переменной Х₁, не пользуясь методом Гаусса – Жордана.

Ответ: (увеличение Z = 2 х 1 = 2

4. Используя рис. 2 определите, сколько итераций потребуется для нахождения оптимального решения (т. С), если в исходной С-Т в качестве вводимой в базис переменной будет выбрана Х₁.

Ответ: Пять итераций, соответствуют экстремальным т. А, F, E, D и C.

5. Используя таблицу, содержащую оптимальное решение задачи фирмы Reddy Mikks, определите исключаемую переменную в соответствии изменение величины Z (увеличение или уменьшение), если в качестве новой базисной переменной будет выбрана

а) S₁ (Ответ: Исключению подлежит Х₁ при этом Z уменьшается на 2х1/2=2/3)

б) S₂ (Ответ: Исключению подлежит S₄ при этом Z уменьшается на 2х4/3=8/3

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ ТАТАРСТАН

АЛЬМЕТЬЕВСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЯНОЙ ИНСТИТУТ

Е.И. Егорова

Математическое моделирование

курс лекций

АЛЬМЕТЬЕВСК 2009

УДК 621.09.06(076)

Е.И. Егорова

Математическое моделирование: Курс лекций по дисциплине «Математическое моделирование» для студентов специальности 151001 «Технология машиностроения» всех форм обучения. – Альметьевск: Альметьевский государственный нефтяной институт, 2009.-42с.

В курсе лекцийизложены:исследование операций как наука и искусство. Искусство моделирования. Предварительная классификация моделей исследования операций. Построение математической модели для задачи линейного программирования. Построение математических моделей. Стандартная форма линейных оптимизационных моделей. Приведение линейной формы математической модели к стандартному виду. Понятие остаточных и избыточных переменных. Симплекс – метод.Искусственное начальное решение. Интерпретация симплекс – таблиц. Анализ модели на чувствительность. Линейное программирование: двойственность. Транспортная модель.Решение транспортной задачи.

Рекомендуется для студентов высших учебных заведений, обучающихся по направлению 151000 «Конструкторско – технологическое обеспечение машиностроительных производств» для специальности 151001 «Технология машиностроения»

Лекция 8:

ИСКУССТВЕННОЕ НАЧАЛЬНОЕ РЕШЕНИЕ. М – метод (МЕТОД БОЛЬШИХ ШТРАФОВ). ДВУХЭТАПНЫЙ МЕТОД

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

В рассмотренной вычислительной схеме СМ для получения начального базисного решения использовались остаточные переменные. Однако, когда исходное ограничение записано в виде равенства или имеет знак ³, нельзя сразу же получить допустимое начальное базисное решение. Покажем это на следующем примере:

минимизировать Z = 4x₁ + x₂

при ограничениях 3х₁ + х₂=3 х₁, х₂ ³ 0

4х₁ +3х₂ ³ 6

х₁ + 2х₂ £ 4

Чтобы записать задачу в стандартной форме, введем в левую часть ограничения (2) избыточную х₃, а в левую часть ограничения (3) – остаточную переменную х₄. В результате получим следующую формулировку задачи:

минимизировать Z = 4х₁ + х₂

при ограничениях 3х₁ + х₂ = 3

4х₁ + 3х₂ – х₃= 6

х₁ + 2х₂ + х₄ = 4

х₁; х₂; х₃; х₄³ 0

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

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

Добиться желаемого результата позволяет использование в итерационном процессе обратной связи, обеспечивающий в конечном итоге получение оптимального решения при нулевых значениях искусственных переменных (при условии, что допустимое оптимальное решение задачи существует.) Для построения требуемой схемы вычислений можно применить следующий прием: наложить «штраф» за использование искусственных переменных, вводимых в целевую функцию. Разработаны два (тесно связанных между собой) метода получения стартовой точки, в которых используется «штрафование» искусственных переменных:

1. М-метод, или метод больших штрафов.

2. Метод, предусматривающий решение исходной задачи в два этапа (двухэтапный метод.)

Рассмотрим М – метод на примере сформулированной выше задачи.

М – метод (метод больших штрафов).

Рассмотрим введенную ранее линейную модель, приведенную к стандартной форме:

минимизировать: Z = 4х₁ + х₂

при ограничениях: 3х₁ + х₂ = 3

4х₁ + 3х₂ – х₃ = 6

х₁ + 2х₂ + х₄ = 4

х₁; х₂; х₃; х₄ ³ 0

В (1) и (2) уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из этих уравнений по одной искусственной переменной, обозначив их через R₁ и R₂:

3х₁ + х₂ + R₁ = 3

4x₁ + 3x₂ – x₃ + R₂ = 6

За использование этих переменных в составе целевой функции можно ввести штраф, приписывая или достаточно большой положительный М. Такой способ введения искусственных переменных R₁ и R₂ приводит к следующей линейной модели:

Минимизировать Z = 4х₁ + х₂ + МR₁ + MR₂

При ограничениях 3х₁ + х₂+ R₁ = 3

4x₁ + 3x₂ – x₃ + R₂ = 6

x₁ + 2x₂ + x₄ = 4

x₁; x₂; x₃; x₄; R₁; R₂ ³ 0

Обратим внимание на логику использования искусственных переменных. Имеются три уравнения и 6 неизвестных. Следовательно, начальное базисное решение должно включить 6 – 3 =3 нулевые переменные. Если положить = 0 переменные х₁; х₂; х₃, то сразу же будет получено требуемое начальное допустимое решение:

R₁ = 3 R₂ = 6 и х₄ = 4.

Рассмотрим теперь, каким образом «новая» структура модели автоматически приводит к тому, что на конечной стадии процесса оптимизации переменные R₁и R₂ принимают нулевое значение. Так как мы имеем дело с задачей на отыскание минимума, а переменные R₁ и R₂ в целевой функции приписан большой по величине положительный коэффициент М, то метод оптимизации, направленный на нахождение минимального значения Z, приведет к тому, что переменные R₁ и R₂ в оптимальном решении обратятся в нуль. Заметим, что все промежуточные итерации, предшествующие получению оптимума, не имеют значения с точки зрения окончательного результата. Поэтому не важно, фигурируют ли на этих итерациях положительные искусственные переменные.

Как следует видоизменить М – метод, если целевая функция подлежит не минимизации, а максимизации? Используя тот же самый прием штрафования искусственных переменных, следует приписать этим переменным в целевой функции достаточно большой по абсолютной величине отрицательный коэффициент –М (М > 0), что обусловит недопустимость положительных значений искусственных переменных в оптимальном решении.

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

Ответ: Максимизировать Z = 4х₁ + х₂ – МR₁ – MR₂

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

R₁ = 3 – 3x₁ – x₂

R₂ = 6 – 4x₁ – 3x₂ + x₃

В результате получается следующие выражения для Z:

Z = 4х₁ + х₂ + М(3 – 3х₁ – х₂) + М(6 – 4х₁- 3х₂ + х₃) = (4 – 7М)х₁ + (1 – 4М)х₂– Мх₃ + 9М

При этом Z – уравнение в С-Т будет иметь вид:

Z – (4 – 7М)х₁ – (1 –4М)х₂ – Мх₃ = 9М

Таким образом, стартовой точке, в которой х₁ = х_{2 =}х₃ = 0, соответствует значение Z = 9М, как это и должно быть при R₁ = 3 и R₂ = 6.

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

№1а. минимизировать: Z = 4х₁ + х₂

при ограничениях: 3х₁ + х₂ = 3

4х₁ + 3х₂ ³ 6

х₁ + 2х₂³ 4

х₁; х₂ ³ 0

минимизировать: Z = 4х₁ + х₂

при ограничениях: 3х₁ + х₂ = 3

4х₁ + 3х₂ – х₃ = 6

х₁ + 2х₂ – х₄ = 4

х₁; х₂; х₃; х₄ ³ 0

минимизировать: Z = 4х₁ + х₂ + MR₁ + MR₂ +MR₃

при ограничениях: 3х₁ + х₂ + R₁ = 3