Вычислительные процедуры симплекс-метода.





 

симплекс-алгоритм состоит из следующих шагов.

Шаг 0. Используя линейную модель стандартной формы , определяют начальное допустимое базисное решение путем приравнивания к нулю п — т ( небазисных ) переменных.

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

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

Шаг 3. Находится новое базисное решение , соответствующее новым составам небазисных и базисных переменных . Осуществляется переход к шагу 1.

Поясним процедуры симплекс-метода на примере решения нашей задачи. Сначала необходимо представить целевую функцию и ограничения модели в стандартной форме:

Z - X1 - 25X2 +0S1 -0S2 = 0 ( Целевая функция )

5X1 + 100X2 + S1 = 1000 ( Ограничение )

-X1 + 2X2 + S2 = 0 ( Ограничение )

Как отмечалось ранее , в качестве начального пробного решения используется решение системы уравнений, в которой две переменные принимаются равными нулю. Это обеспечивает единственность и допустимость получаемого решения . В рассматриваемом случае очевидно, что подстановка X1 = X2 = 0 сразу же приводит к следующему результату: S1 = 1000 , S2 = 0 ( т. е. решению , соответствующему точке А на рис. 1 ) . Поэтому точку А можно использовать как начальное допустимое решение . Величина Z в этой точке равна нулю , так как и X1 и X2 имеют нулевое значение . Поэтому , преобразовав уравнение целевой функции так , чтобы его правая часть стала равной нулю , можно убедиться в том , что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение . Это имеет место во всех случаях , когда начальный базис состоит из остаточных переменных.

Полученные результаты удобно представить в виде таблицы :

 

Базисные переменные Z X1 X2 S1 S2 Решение  
Z -1 - 25 Z - уравнение
S1 S1 -уравнение
S2 -1 S2 - уравнение

 

Эта таблица интерпретируется следующим образом. Столбец “Базисные переменные” содержит переменные пробного базиса S1, S2, значения которых приведены в столбце “Решение”. При этом подразумевается, что небазисные переменные X1 и X2 ( не представленные в первом столбце ) равны нулю. Значение целевой функции

Z = 1*0 + 25*0 + 0*1000 + 0*1 равно нулю , что и показано в последнем столбце таблицы.

Определим , является ли полученное пробное решение наилучшим (оптимальным). Анализируя Z - уравнение, нетрудно заметить, что обе небазисные переменные X1 и X2, равные нулю, имеют отрицательные коэффициенты. Всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента, так как практический опыт вычислений показывает, что в этом случае оптимум достигается быстрее.

Это правило составляет основу используемого в вычислительной схеме симплекс-метода условия оптимальности, которое состоит в том , что , если в задаче максимизации все небазисные переменные в Z - имеют неотрицательные коэффициенты , полученное пробное решение является оптимальным . В противном случае в качестве новой базисной переменной следует выбрать ту , которая имеет наибольший по абсолютной величине отрицательный коэффициент. Применяя условие оптимальности к исходной таблице , выберем в качестве переменной , включаемой в базис , переменную Х2. Исключаемая переменная должна быть выбрана из совокупности базисных переменных S1 , S2 . Процедура выбора исключаемой переменной предполагает проверку условия допустимости, требующего , чтобы в качестве исключаемой переменной выбиралась та из переменных текущего базиса , которая первой обращается в нуль при увеличении включаемой переменной X2 вплоть до значения , соответствующего смежной экстремальной точке .

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

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

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

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

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

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

Новое уравнение = Предыдущее уравнение —

┌ ┐

│Коэффициент │

│ведущего столбца │*(Новая ведущая строка ).

│предыдущего │

│уравнения │

└ ┘

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

 

Базисные переменные Z X1 X2 S1 S2 Решение
Z            
S1            
S2 -1/2 1/2

 

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

1. Новое Z - уравнение .

старое Z - уравнение : ( 1 -1 -25 0 0 0 )

( - ( -25 ) * ( 0 -1/2 1 0 1/2 0 )

( 1 -131/2 0 0 121/2 0 )

2.Новое S1 - уравнение

старое S1 - уравнение : ( 0 5 100 1 0 1000 )

( - 100 ) * ( 0 -1/2 1 0 1/2 0 )

( 0 55 0 1 -50 1000 )

 

Новая симплекс-таблица будет иметь вид :

 

Базисные переменные Z X1 X2 S1 S2 Решение  
Z -131/2 121/2 Z - уравнение
S1 -50 S1 -уравнение
X2 -1/2 1/2 X2 - уравнение

В новом решении X1 = 0 и S2 = 0 . Значение Z не изменяется .

Заметим , что новая симплекс-таблица обладает такими же характеристиками , как и предыдущая : только небазисные переменные X1 и S2 равны нулю , а значения базисных переменных, как и раньше, представлены в столбце “ Решение ” . Это в точности соответствует результатам , получаемым при использовании метода Гаусса—Жордана .

Из последней таблицы следует , что на очередной итерации в соответствии с условием оптимальности в качестве вводимой переменной следует выбрать X1 ,так как коэффициент при этой переменной в Z-ypaвнении равен -131/2 . Исходя из условия, определяем, что исключаемой переменной будет S1. Отношения , фигурирующие в правой части таблицы, показывают, что в новом базисном решении значение включаемой переменной X1 будет равно 1000/55 ( = минимальному отношению ) . Это приводит к увеличению целевой функции на ( 1000/55 ) * ( -131/2 ) = ( 2455/11 ) .

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

1)Новое ведущее S1 - уравнение = Предыдущее S1 - уравнение / ( 55 ) .

 

Базисные переменные Z X1 X2 S1 S2 Решение
Z            
S1 1/55 - 50/55 1000/55
X2            

 

 

2) Новое Z - новое = Предыдущее Z - уравнение - ( -131/2 ) * Новое /ведущее уравнение :

( 1 -131/2 0 0 121/2 0 )

- ( -131/2 ) * ( 0 1 0 1/55 -50/55 1000/55 )

( 1 0 0 27/110 5/22 2455/11 )

3) Новое X2 - уравнение = Предыдущее X2 - уравнение - ( -1/2 ) * Новое ведущее уравнение :

( 0 -1/2 1 0 1/2 0 )

- ( - 1/2 ) * ( 0 1 0 1/55 -50/55 1000/55 )

( 0 0 1 1/110 1/22 91/11 )

 

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

 

Базисные переменные Z X1 X2 S1 S2 Решение
Z 27/110 5/22 2455/11
X1 1/55 -50/55 1000/55
X2 1/110 1/22 91/11

В новом базисном решении X1=1000/55 и X2=91/11 . Значение Z увеличилось с 0 ( предыдущая симплекс-таблица ) до 2455/11 ( последняя симплекс-таблица ) . Этот результирующий прирост целевой функции обусловлен увеличением X1 от О до 1000/55 , так как из Z - строки предыдущей симплекс-таблицы следует , что возрастанию данной переменной на единицу соответствует увеличение целевой функции на( -131/2 ) .

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

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

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

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

 

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

 

С точки зрения практического использования результатов решения задач ЛП классификация переменных, предусматривающая их разделение на базисные и небазнсные, не имеет значения и при анализе данных , характеризующих оптимальное решение, может не учитываться . Переменные, отсутствующие в столбце “Базисные переменные ”, обязательно имеют нулевое значение. Значения остальных переменных приводятся в столбце “Решение”. При интерпретации результатов оптимизации в нашей задаче нас прежде всего интересует количество времени , которое закажет наша фирма на радио и телевидение , т. е. значения управляемых переменных X1 и X2 . Используя данные , содержащиеся в симплекс-таблице для оптимального решения , основные результаты можно представить в следующем виде :

 

Управляемые переменные Оптимальные значения Решение
X1 1000/55 Время выделяемое фирмой на телерекламу
X2 91/11 Время выделяемое фирмой на радиорекламу
Z 2455/11 Прибыль получаемая от рекламы .

 

Заметим, что Z = X1 + 25X2 = 1000/55 + 25 * 91/11 = 2455/11 . Это решение соответствует данным заключительной симплекс-таблицы.

 





Читайте также:
Жанры народного творчества: Эпохи, люди, их культуры неповторимы. Каждая из них имеет...
Основные направления модернизма: главной целью модернизма является создание...
Основные этапы развития астрономии. Гипотеза Лапласа: С точки зрения гипотезы Лапласа, это совершенно непонятно...
Роль химии в жизни человека: Химия как компонент культуры наполняет содержанием ряд фундаментальных представлений о...

Рекомендуемые страницы:



Вам нужно быстро и легко написать вашу работу? Тогда вам сюда...

Поиск по сайту

©2015-2021 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Мы поможем в написании ваших работ! Мы поможем в написании ваших работ! Мы поможем в написании ваших работ!
Обратная связь
0.021 с.