Математическое описание .

X1 - время потраченное на радиорекламу .

X2 - время потраченное на телерекламу   .

Z - искомая целевая функция , оражающая максимальный сбыт от 2-ух видов рекламы .

X1=>0 , X2=>0 , Z=>0 ;

Max Z = X1 + 25X2 ;

5X1 + 100X2 <=1000 ;

X1 -2X2 => 0

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

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

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

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

     В гл 2 было показано , что правая и левая части ограничений линейной модели могут быть связаны знаками <= , = и => . Кроме того , переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или не иметь ограничения в знаке . Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме , которую назовем стандатрной формой линейных оптимизационных моделей . При стандартной форме линейной модели

1. Все ограничения записываются в виде равенств с неотрицательной правой частью ;

2. Значения всех переменных модели неотрицательны ;

3. Целевая функция подлежит максимизации или минимизации .

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

 

 

Ограничения

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! ]

Вторая из ранее отмеченных закономерностей оказывается
весьма полезной для построения вычислительных процедур симп-
лекс-метода , при реализации которого осуществляется последова-
тельный переход от одной экстремальной точки к другой, смежной с ней . Так как смежные экстремальные точки отличаются только
одной переменной, можно определить каждую последующую ( смеж-
ную) экстремальную точку путем замены одной из текущих не-
базисных ( нулевых ) переменных текущей базисной переменной.
В нашем случае получено решение , соответствующее точке А , откуда следует осуществить переход в точку В . Для этого нужно увеличивать небазисную переменную X₂ от исходного нулевого значения до значе-
ния , соответствующего точке В ( см. рис. 1 ). В точке B переменная
S₁ ( которая в точке А была базисной ) автоматически обращается в
нуль и , следовательно , становится небазисной переменной . Таким
образом , между множеством небазисных и множеством базисных
переменных происходит взаимообмен переменными X₂ и S₁ . Этот
процесс можно наглядно представить в виде следующей таблицы.

 

Экстремальная точка	Нулевые переменные	Ненулевые переменные
А	S2 , X2	S1 , X1
В	S1 , X2	S2 , X1

 

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

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