Построение модели состава в силу многообразия природы и форм элементов также не является простым делом. Это можно объяснить тремя факторами:
1.неоднозначностью понятия "элементарного элемента";
2.многоцелевым характером объекта, объективно требующим выделить под каждую цель соответствующий ей состав;
3.условностью (субъективностью) процедуры деления целого на части (системы на подсистемы, элементы).
Простота и доступность моделей "черного ящика" и состава позволяет решать с их использованием множество практических задач. Вместе с тем для более детального (глубокого) изучения систем необходимо устанавливать в модели состав отношения (связи) между элементами. Описание системы через совокупность необходимых и достаточных для достижения целей отношений между элементами назовем моделью структуры системы.
Перечень связей между элементами, на первый взгляд, является не-сколько отвлеченной, абстрактной моделью. На самом деле как рассматривать связи, если не рассмотрены сами элементы.
ПРАКТИЧЕСКАЯ ЧАСТЬ
Словесное описание
Фирма , производящая некоторую продукцию осуществляет её рекламу двумя способами через радиосеть и через телевидение . Стоимость рекламы на радио обходится фирме в 5 $ , а стоимость телерекламы - в 100$ за минуту .
Фирма готова тратить на рекламу по 1000 $ в месяц . Так же известно , что фирма готова рекламировать свою продукцию по радио по крайней мере в 2 раза чаще , чем по телевидению .
Опыт предыдущих лет показал , что телереклама приносит в 25 раз больший сбыт продукции нежели радиореклама .
Задача заключается в правильном распределении финансовых средств фирмы .
Математическое описание .
X1 - время потраченное на радиорекламу .
X2 - время потраченное на телерекламу .
Z - искомая целевая функция , оражающая максимальный сбыт от 2-ух видов рекламы .
X1=>0 , X2=>0 , Z=>0 ;
Max Z = X1 + 25X2 ;
5X1 + 100X2 <=1000 ;
X1 -2X2 => 0
Использование графического способа удобно только при решении задач ЛП с двумя переменными . При большем числе переменных необходимо применение алгебраического аппарата . В данной главе рассматривается общий метод решения задач ЛП , называемый симплекс-методом .
Информация , которую можно получить с помощью симплекс-метода , не ограничивается лишь оптимальными значениями переменных . Симплекс-метод фактически позволяет дать экономическую интерепритацию полученного решения и провести анализ модели на чувствительность .
Процесс решения задачи линейного программирования носит итерационный характер : однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор , пока не будет получено оптимальное решение . Процедуры , реализуемые в рамках симплекс-метода , требуют применения вычислительных машин - мощного средства решения задач линейного программирования .
Симлекс-метод - это характерный пример итерационных вычислений , используемых при решении большинства оптимизационных задач . В данной главе рассматриваются итерационные процедуры такого рода , обеспечивающие решение задач с помощью моделей исследования операций .
В гл 2 было показано , что правая и левая части ограничений линейной модели могут быть связаны знаками <= , = и => . Кроме того , переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или не иметь ограничения в знаке . Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме , которую назовем стандатрной формой линейных оптимизационных моделей . При стандартной форме линейной модели
1. Все ограничения записываются в виде равенств с неотрицательной правой частью ;
1. Значения всех переменных модели неотрицательны ;
1. Целевая функция подлежит максимизации или минимизации .
Покажем , каким образом любую линейную модель можно привести к стандартной .
Ограничения
1. Исходноеограничение , записанное в виде неравенства типа <= ( =>) ,
можно представить в виде равенства , прибавляя остаточную переменную к левой части ограничения ( вычитая избыточную переменную из левой части ) .
Например , в левую часть исходного ограничения
5X1 + 100X2 <= 1000
вводистя остаточная переменная S1 > 0 , в результате чего исходное неравенство обращается в равенство
5X1 + 100X2 + S1 = 1000 , S1 => 0
Если исходное ограничение определяет расход некоторого ресурса , переменную S1 следует интерпретировать как остаток , или неиспользованную часть , данного ресурса .
Рассмотрим исходное ограничение другого типа :
X1 - 2X2 => 0
Так как левая часть этого ограничения не может быть меньше правой , для обращения исходного неравенства в равенство вычтем из его левой части избыточную переменную S2 > 0 . В результате получим
X1 - 2X2 - S2 = 0 , S2 => 0
2. Правую часть равенства всегда можно сделать неотрицательной , умножая оби части на -1 .
Например равенство X1 - 2X2 - S2 = 0 эквивалентно равенству - X1 + 2X2 + S2 = 0
3. Знак неравенства изменяется на противоположный при умножении обеих частей на -1 .
Например можно вместо 2 < 4 записать - 2 > - 4 , неравенство X1 - 2X2 <= 0 заменить на - X1 + 2X2 => 0
Переменные
Любую переменную Yi , не имеющую ограничение в знаке , можно представить как разность двух неотрицательных переменных :
Yi=Yi’-Yi’’, где Yi’,Yi’’=>0.
Такую подстановку следует использовать во всех ограничениях , которые содержат исходную переменную Yi , а также в выражении для целевой функции .
Обычно находят решение задачи ЛП , в котором фигурируют переменные Yi’ и Yi’’ , а затем с помощью обратной подстановки определяют величину Yi . Важная особенность переменных Yi’ и Yi’’ состоит в том , что при любом допустимом решении только одна из этих переменных может принимать положительное значение , т.е. если Yi’>0 , то Yi’’=0, и наоборот . Это позволяет рассматривать Yi’ как остаточную переменную , а Yi’’ - как избыточную переменную , причем лишь одна из этих переменных может принимать положительное значение . Указанная закономерность широко используется в целевом программировании и фактически является предпосылкой для использования соответсвующих преобразований в задаче 2.30
Целевая функция
Целевая функция линейной оптимизационной модели , представлена в стандартной форме , может подлежать как максимизации , так и минимизации . В некоторых случаях оказывается полезным изменить исходную целевую функцию .
Максимизация некоторой функции эквивалентна минимизации той же функции , взятой с противоположным знаком , и наоборот . Например максимизация функции
Z = X1 + 25X2
эквивалентна минимизации функции
( -Z ) = -X1 - 25X2
Эквивалентность означает , что при одной и той же совокупности ограничений оптимальные значения X1 , X2 , в обоих случаях будут одинаковы . Отличие заключается только в том , что при одинаковых числовых значениях целевых функций их знаки будут противоположны .
Симплекс-метод .
В вычислительной схеме симплекс-метода реализуется упорядоченный процесс , при котором , начиная с некоторой исходной допустимой угловой точки ( обычно начало координат ) , осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор , пока не будет найдена точка , соответствующая оптимальному решению .
Общую идею симплекс-метода можно проиллюстрировать на примере модели , посроенной для нашей задачи . Пространство решений этой задачи представим на рис. 1 . Исходной точкой алгоритма является начало координат ( точка А на рис. 1 ) . Решение , соответствующее этой точке , обычно называют начальным решением . От исходной точки осуществляется переход к некоторой смежной угловой точке .
Выбор каждой последующей экстремальной точки при использовании симплекс-метода определяется следующими двумя правилами .
1. Каждая последующая угловая точка должна быть смежной с предыдущей . Этот переход осуществляется по границам ( ребрам ) пространства решений .
2. Обратный переход к предшествующей экстремальной точке не может производиться .
Таким образом , отыскание оптимального решения начинается с некоторой допустимой угловой точки , и все переходы осуществляются только к смежным точкам , причем перед новым переходом каждая из полученных точек проверяется на оптимальность .
Определим пространство решений и угловые точки агебраически . Требуемые соотнощшения устанавливаются из указанного в таблице соответствия геометрических и алгебраических определений
.
|
Геометрическое определение
|
Алгебраическое определение ( симплекс метод ) |
Пространство решений |
Ограничения модели стандартной формы |
Угловые точки |
Базисное решение задачи в стандартной форме |
Представление пространства решений стандартной задачи линейного программирования .
Линейная модель , построенная для нашей задачи и приведенная к стандартной форме , имеет следующий вид :
Максимизировать
Z = X1 + 25X2 + 0S1 + 0S2
При ограничениях
5X1 + 100X2 + S1 = 1000
- X1 + 2X2 + S2 = 0
X1=>0 , X2=>0 , S1=>0 , S2=>0
Каждую точку пространства решений данной задачи , представленную на рис.1 , можно определить с помощью переменных X1 , X2 , S1 и S2 , фигурирующими в модели стандартной формы. При S1 = 0 и S2 = 0 ограничения модели эквивалентны равенствам , которые представляются соответствующими ребрами пространства решений . Увеличение переменных S1 и S2 будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область. Переменные X1 , X2 , S1 и S2 , ассоциированные с экстремальными точкамиА , В , и Сможно упорядочить , исходя из того , какое значение ( нулевоеили ненулевое )имеет данная переменная в экстремальной точке .
|
Экстремальная точка
|
Нулевые переменные |
Ненулевые переменные |
А |
S2 , X2 |
S1 , X1 |
В |
S1 , X2 |
S2 , X1 |
С |
S1 , S2 |
X1 , X2 |
Анализируя таблицу , легко заметить две закономерности:
1. Стандартная модель содержит два уравнения и четыренеизвестных , поэтому в каждойиз экстремальных точек две ( = 4 - 2 ) переменные должныиметь нулевые значения .
2.Смежныеэкстремальные точки отличаются только одной пе-ременной в каждой группе ( нулевых и ненулевых переменных ) ,
Первая закономерность свидетельствует о возможности опре-деления экстремальных точек алгебраическим способом путем при-равнивания нулю такого количества переменных , которое равноразности между количеством неизвестных и числом уравнений .В этом состоит сущность свойстваоднозначностиэкстремальныхточе на рис 1 каждойнеэкстремальной точке соответствуетне более одной нулевой переменной . Так , любая точка внутреннейобласти пространства решений вообще неимеет ни одной нулевойпеременной, а любая неэкстремальная точка , лежащая на границе ,всегда имеет лишь одну нулевую переменную .
Свойство однозначности экстремальных точек позволяет опре-делить ихалгебраическимметодом. Будем считать , что линейнаямодель стандартной формы содержиттуравнений ип ( т <= п )не-известных (правые частиограничений — неотрицательные ) . Тогдавседопустимые экстремальные точки определяются каквсеодно-значные неотрицательные решения системыmуравнений , в ко-торыхп — mпеременных равны нулю.
Однозначные решения такой системы уравнений, получаемыепутемприравнивания к нулю( п — т )переменных , называютсябазисными решениями . Если базисное решение удовлетворяеттребованию неотрицательности правых частей , оно называетсядопустимым базисным решением. Переменные , имеющие нулевоезначение ,называются небазисными переменными , остальные —базисными переменными.
Из вышеизложенного следует , что при реализации симплекс-метода алгебраическое определение базисных решений соответст-вует идентификации экстремальных точек , осуществляемой пригеометрическом представлении пространства решений . Таким об-разом , максимальное числоитераций при использовании симплекс-метода равно максимальному числу базисных решений задачиЛП ,представленной в стандартной форме . Этоозначает , что количествоитерационных процедур симплекс-метода не превышает
Cпт= n! / [ ( n - m )!m! ]
Вторая из ранее отмеченных закономерностей оказываетсявесьма полезной дляпостроения вычислительных процедур симп-лекс-метода , при реализации которогоосуществляется последова-тельныйпереход отоднойэкстремальной точки к другой, смежной с ней . Так как смежные экстремальные точки отличаются толькооднойпеременной, можно определить каждую последующую ( смеж-ную) экстремальную точку путем замены однойиз текущих не-базисных ( нулевых ) переменных текущей базисной переменной.В нашем случае получено решение , соответствующее точкеА, откуда следует осуществить переход в точкуВ .Для этого нужно увеличивать небазисную переменную X2от исходногонулевого значения до значе-ния , соответствующего точкеВ( см. рис. 1 ). В точкеB переменнаяS1( которая в точкеАбыла базисной )автоматически обращается внуль и , следовательно , становитсянебазиснойпеременной . Такимобразом , между множествомнебазисныхи множеством базисныхпеременных происходитвзаимообменпеременными X2иS1. Этотпроцесс можно наглядно представитьв видеследующей таблицы.
|
Экстремальная точка
|
Нулевые переменные |
Ненулевые переменные |
А |
S2 , X2 |
S1 , X1 |
В |
S1 , X2 |
S2 , X1 |
Применяя аналогичную процедуру ко всем экстремальным точкамрис. 1 , можно убедиться в том , что любую последующую экстре-мальную точку всегда можно определить путем взаимной заменыпо одной переменной в составе базисных и небазисных переменных( предыдущей смежной точки ) . Этот фактор существенно упрощаетреализацию вычислительных процедур симплекс-метода.
Рассмотренный процесс взаимной замены переменных приводитк необходимости введения двух новых терминов . Включаемой пе-ременной называется небазисная в данный момент переменная ,которая будет включена в множество базисных переменных на сле-дующей итерации ( при переходе к смежной экстремальной точке ) .Исключаемая переменная — это та базисная переменная , котораяна следующей итерации подлежит исключению из множества ба-зисных переменных .
Вычислительные процедуры симплекс-метода .
симплекс-алгоритм состоит из следующих шагов.
Шаг 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 |
-1 |
- 25 |
0 |
0 |
0 |
Z – уравнение |
S1 |
0 |
5 |
100 |
1 |
0 |
1000 |
S1 –уравнение |
S2 |
0 |
-1 |
2 |
0 |
1 |
0 |
S2 – уравнение |
Эта таблица интерпретируется следующим образом. Столбец« Базисные переменные » содержит переменные пробного базиса S1 ,S2 , значения которых приведены в столбце « Решение » . Приэтом подразумевается , что небазисные переменные X1 и X2 ( не пред-ставленные в первом столбце ) равны нулю . Значение целевой функ-ции Z = 1*0 + 25*0 + 0*1000 + 0*1 равно нулю , что и показано в последнем столбце таблицы .
Определим , является ли полученное пробное решение наи-лучшим ( оптимальным ) . Анализируя Z - уравнение , нетрудно заме-тить , что обе небазисные переменные X1 и X2 , равные нулю , имеютотрицательныекоэффициенты . Всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента ( в Z - уравнении ) , так как практический опыт вычислений показывает , что в этом случае оптимум достигается быстрее .
Это правило составляет основу используемого в вычислительнойсхеме симплекс-метода условия оптимальности , которое состоит втом , что , если в задаче максимизациивсенебазисные переменные вZ - Уравнение имеютнеотрицательныекоэффициенты , полученное пробное решение является оптимальным . В противном случае в ка-честве новой базисной переменной следует выбрать ту , которая имеетнаибольший по абсолютной величине отрицательный коэффициент .
Применяя условие оптимальности к исходной таблице , выберемв качестве переменной , включаемой в базис , переменную Х2 . Исклю-чаемая переменная должна быть выбрана из совокупности базисныхпеременных S1 , S2 . Процедура выбора исключаемой переменной предполагает проверкуусловия допустимости ,требующего , чтобы в качестве исключаемой переменной выбиралась та из пере-менных текущего базиса , которая первой обращается в нуль при уве-личении включаемой переменной X2 вплоть до значения , соответствующего смежной экстремальной точке .
Интересующее нас отношение ( фиксирующее искомую точку пе-ресечения и идентифицирующее исключаемую переменную ) можноопределить из симплекс-таблицы. Для этого в столбце , соответствующем вводимой переменной X2,вычеркиваются отрицательные и нулевые элементы ограничений . Затем вычисляются отношения постоянных , фигурирующих в правых частях этих ограничений , к оставшимся элементам столбца , соответствующего вводимой переменной X2.Исключаемой переменной будет та переменная текущего базиса , для которой указанное выше отношение минимально.
Начальная симплекс-таблица для нашей задачи , получаемая после проверкиусловия допустимости( т. е. после вычисления соответствующих отношений и определения исключаемой переменной ) , воспроизведена ниже . Для удобства описания вычислительных процедур , осуществляемых на следующей итерации , введем ряд необходимых определений . Столбец симплекс-таблицы , ассоциированный с вводимой переменной , будем называть ведущим столбцом . Строку , соответствующую исключаемой переменной , назовем ведущей строкой ( уравнением ) , а элемент таблицы , находящийся на пересечении ведущего столбца и ведущей строки , будем называть ведущим элементом .
