5. Многомерная оптимизация

Линейное программирование

Оптимизация – это целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Количественная оценка оптимизируемого качества называется критерием оптимальности илицелевой функцией .Её можно записать в виде:

(5.1)

где x 1 , x 2 , … , x n – некоторые параметры объектаоптимизации.

Существуют два типа задач оптимизации – безусловные и условные.

Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции (5.1) от n действительных переменных и определении соответствующих значений аргументов.

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

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

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

Примером такой задачи является задача оптимального распределения сырья между различными производствами при максимальной стоимости продукции.

Пусть из двух видов сырья изготавливается продукция двух видов.

Обозначим: x 1 , x 2 – число единиц продукции первого и второго вида, соответственно; c 1 , c 2 –ценаединицы продукции первого и второго вида, соответственно. Тогда общая стоимость всей продукции будет :

(5.2)

В результате производства желательно, чтобы общая стоимость продукции была максимальной. R (x 1 , x 2 ) – целевая функция в данной задаче.

b 1 , b 2 –количество сырья первого ивторого видов, имеющееся в наличии; a ij – число единиц i -го вида сырья, необходимое для производства единицы j -го вида продукции.

Учитывая, что расход данного ресурса не может превышать общего его количества, запишем ограничительные условия по ресурсам:

(5.3)

Относительно переменных x 1 , x 2 можно ещё сказать, что они неотрицательныине бесконечны.:

(5.4)

Среди множества решений системы неравенств (5.3) и (5.4)требуется найти такое решение (x 1 , x 2 ), для которого функция R достигает наибольшего значения.

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

Графический метод решения задачилинейного программирования.

Пусть требуется найти x 1 и x 2 , удовлетворяющие системе неравенств:

(5.5)

и условиям неотрицательности :

(5.6)

для которых функция

(5. 7 )

достигает максимума.

Решение.

Построим в системе прямоугольных координат x 1 Ox 2 область допустимых решений задачи (рис.11). Для этого, заменяя каждое из неравенств (5.5) равенством, строим соответствующую ему граничную прямую:

(i = 1, 2, … , r )

Рис. 11

Эта прямая делит всю плоскость на две полуплоскости. Для координат x 1 , x 2 любой точки А одной полуплоскости выполняется неравенство:

а для координат любой точки В другой полуплоскости – противоположное неравенство:

Координаты любой точки граничной прямой удовлетворяют уравнению:

Для определения того, по какую сторону от граничной прямой располагается полуплоскость, соответствующая заданному неравенству, достаточно «испытать» одну какую-либо точку (проще всего точку О (0;0)). Если при подстановке её координат в левую часть неравенства оно удовлетворяется, то полуплоскость обращена в сторону к испытуемой точке, если же неравенство не удовлетворяется, то соответствующая полуплоскость обращена в противоположную сторону. Направление полуплоскости показывается на чертеже штриховкой. Неравенствам:

соответствуют полуплоскости, расположенные справа от оси ординат и над осью абсцисс.

На рисунке строим граничные прямые и полуплоскости, соответствующие всем неравенствам.

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

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

Рис. 12. Область допустимых решений пустая, что соответствует несовместности системы неравенств; решения нет

Рис. 13. Область допустимых решений изображается одной точкой А , что соответствует единственному решению системы

Рис. 14. Область допустимых решений ограниченная, изображается в виде выпуклого многоугольника. Допустимых решений бесконечное множество

Рис. 15. Область допустимых решений неограниченная, в виде выпуклой многоугольной области. Допустимых решений бесконечное множество

Графическое изображение целевой функции

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

Вектор градиента:

перпендикулярный к линиям уровня, показывает направление возрастания R .

Задача отыскания оптимального решения системы неравенств (5.5), для которого целевая функция R (5.7) достигает максимума, гео­метрически сводится к определе­нию в области допустимых реше­ний точки, через которую пройдет линия уровня, соответствую­щая наибольшему значении пара­метра R

Рис. 16

Если область допустимых решений есть выпуклый многоугольник, то экстремум функции R достигается, по крайней мере, в одной из вер­шин этогомногоугольника.

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

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

Пример.

Пусть требуется найти значения x 1 и x 2 , удовлетворяющие системе неравенств:

и условиям неотрицательности :

для которых функция:

достигает максимума.

Решение.

Заменим каждое из неравенств равенством и построим граничные прямые:

Рис. 17

Определим полуплоскости, соответствующие данным неравенствам, путём «испытания» точки (0;0). С учетом неотрицательности x 1 и x 2 получим область допустимых решений данной задачи в виде выпуклого многоугольника ОАВДЕ .

В области допустимых решений находим оптимальное решение, строя вектор градиента

показывающий направление возрастания R .

Оптимальное решение соответствует точке В , координаты которой можно определить либо графически, либо путем решения системы двух уравнений, соответствующих граничным прямым АВ и ВД:

Ответ: x 1 = 2; x 2 = 6; R max = 22.

Задания. Найти положение точки экстремума и экстремальное значение целевой функции

при заданных ограничениях.

Таблица 9
№ варианта	Экстремум				Ограничения
	M ax				; ; ; ;
	Max				; ; ; ;
					; ;
					; ; ; ;
					; ; ; ;
					; ;

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

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

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x1, …,xn на каждой итерации. Существуют также приближенные методы решения нелинейных задач. Это методы основанные на методе кусочно-линейной аппроксимации. Точность нахождения решений зависит от количества интервалов, на которых мы находим решение линейной задачи, максимально приближенной к нелинейной. Такой метод позволяет производить расчеты с помощью симплекс-метода. Обычно в линейных моделях коэффициенты целевой функции постоянны и не зависят от значения переменных. Однако существует ряд задач, где затраты зависят от объема нелинейно.

Алгоритм решения:

• 1. Работа начинается с построения регулярного симплекса в пространстве независимых переменных и оценивая значения целевой функции в каждой из вершин симплекса.
• 2. Определяется вершина - наибольшее значение функции.
• 3. Вершина проецируется через центр тяжести остальных вершин в новую точку, которая используется в качестве вершины нового симплекса.
• 4. Если функция убывает достаточно плавно, итерации продолжаются до тех пор, пока либо не будет накрыта точка min, либо не начнется циклическое движение по 2 или более симплексам.
• 5. Поиск завершается, когда или размеры симплекса, или разности между значениями функции в вершинах останутся достаточно малыми.

Задача: оптимизация емкостей. Добиться минимальных затрат на изготовление емкости объёмом 2750 литров для хранения песка.

Z = C1X1 + C2X2 + C3X3 + C4X4 + C5X5 min;

где: X1 - количество необходимого металла, кг;

C1 - стоимость металла, руб/кг;

X2 - масса требующихся электродов, кг;

C2 - стоимость электродов, руб/кг;

X3 - количество затраченной электроэнергии, кВт ч;

C3 - стоимость электроэнергии, руб/кВт ч;

X4 - время работы сварщика, ч;

C4 - тарифная ставка сварщика, руб/ч;

X5 - время работы подъемника, ч;

C5 - оплата подъемника, руб/ч.

1. Найдем оптимальную поверхностную площадь емкости:

F = 2ab+2bh+2ah min (1)

где V=2750 литров.

x1=16,331; x2=10,99

Минимум функции получен в процессе оптимизации по методу Бокса- 1196,065 дм2

В соответствие с ГОСТ 19903 - 74, примем:

h=16,50 дм, b=10,00 дм.

Выразим a из (1) и получим:

Рассчитаем оптимальную толщину листа металла

Выберем углеродистую обыкновенную сталь Ст2сп

Для этой стали 320 МПа, ;

Масса песка.

Нагрузка на стенку емкости наибольшей площади:

Высчитаем нагрузку на 1 погонный сантиметр листа шириной 100 см:

Определим толщину стенки, исходя из условия:

где: l - длина листа (желательно наибольшая, чтобы оставить дополнительный запас прочности);

q - нагрузка на 1 погонный сантиметр, кг/см;

Толщина листа металла, м

Максимально допустимое напряжение металла, Н/мм2.

Выразим из (2) толщину стенки:

Учитывая, что 320 МПа = 3263 кг/см2,

Масса металла

где: F - площадь поверхности емкости, м2 ;

Толщина стенки металла, м;

Плотность металла, кг/м3.

Цена на сталь Ст2сп составляет около 38 руб/кг.

2. Длина сварного шва:

Воспользуемся электродами для нержавеющей стали «УОНИ-13/45»

Цена 88,66 руб/кг;

где: Sшва - поперечная площадь сечения сварного шва, м2;

l - длина сварного шва, м;

Плотность наплавленного металла, кг/м3.

3. Время сварки:

где l - длина сварного шва, м;

v - скорость сварки, м/ч.

Суммарная потребляемая мощность:

Рсум = 5 17 = 85 кВт ч;

Стоимость электроэнергии 5,7 руб/ кВт ч.

4. Для ручной дуговой сварки затраты вспомогательного, подготовительно-заключительного времени и времени на обслуживание рабочего места составляют в среднем 40 - 60%. Воспользуемся средним значением в 50%.

Общее время:

Оплата сварщика VI разряда - 270 руб/час.

Плюс тарифный коэффициент 17% за работу в замкнутом плохо проветриваемом пространстве:

Оплата помощника составит 60% от оплаты сварщика:

8055 0,6 = 4833 руб.

Итого: 8055+4833 = 12888 рублей.

5. Кран понадобиться для того, чтобы держать листы металла во время сварки, погрузки и выгрузки листов металла и непосредственно готовой емкости.

Чтобы «прихватить» всю конструкцию, сварщику необходимо наложить около 30% швов.

Оплата крана - 1000 руб/час.

Общая стоимость емкости.

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

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

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

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

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

Сущность методов исследования операций

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

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

• степень обоснованности выбранных вариантов решений;
• насколько они лучше альтернативных;
• степень учета определяющих факторов;
• каков критерий оптимальности выбранных решений.

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

Методы экспертных оценок

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

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

Рассматриваемые методы оптимизации ряда управленческих решений (экспертных оценок) эффективны в решении нижеперечисленных управленческих задач в сфере производства:

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

И это лишь некоторые методы оптимизации ряда управленческих решений (экспертной оценки).

Классификация рассматриваемых методов

Методы решения задач оптимизации, исходя из числа параметров, можно подразделить на:

• Методы оптимизации одномерной.
• Методы оптимизации многомерной.

Их еще называют "численные методы оптимизации". Если быть точным, это алгоритмы ее поиска.

В рамках применения производных методы бывают:

• прямые методы оптимизации (нулевого порядка);
• градиентные методы (1-го порядка);
• методы 2-го порядка и др.

Большая часть методов многомерной оптимизации приближена к задаче второй группы методов (одномерной оптимизации).

Методы одномерной оптимизации

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

Существуют следующие методы решения задач оптимизации (одномерной):

• метод Фибоначчи;
• дихотомии;
• золотого сечения;
• удвоения шага.

Метод Фибоначчи

Для начала необходимо установить координаты т. x на промежутке в качестве числа, равного отношению разницы (x - a) к разнице (b - a). Следовательно, a имеет относительно промежутка координату 0, а b - 1, средняя точка - ½.

Если допустить, что F0 и F1 между собой равны и принимают значение 1, F2 будет равно 2, F3 - 3, …, то Fn = Fn-1 + Fn-2. Итак, Fn - числа Фибоначчи, а поиск Фибоначчи - это оптимальная стратегия так называемого последовательного поиска максимума ввиду того, что она довольно тесно связана с ними.

В рамках оптимальной стратегии принято выбирать xn - 1 = Fn-2: Fn, xn = Fn-1: Fn. При любом из двух интервалов ( либо ), каждый из которых может выступать в качестве суженного интервала неопределенности, точка (унаследованная) относительно нового интервала будет иметь либо координаты , либо . Далее, в качестве xn - 2 принимается точка, которая имеет относительно нового промежутка одну из представленных координат. Если использовать F(xn - 2), значение функции, которое унаследовано от прежнего промежутка, становится возможным сокращение интервала неопределенности и передача в наследство одного значения функции.

На финишном шаге получится прейти к такому интервалу неопределенности, как , при этом средняя точка унаследована от предыдущего шага. В качестве x1 устанавливается точка, которая имеет относительную координату ½+ε, а окончательный интервал неопределенности будет или [½, 1] по отношению к .

На 1-м шаге длина данного интервала сократилась до Fn-1: Fn (с единицы). На финишных шагах сокращение длин соответствующих интервалов представляется числами Fn-2: Fn-1, Fn-3: Fn-2, …, F2: F3, F1: F2 (1 + 2ε). Итак, длина такого интервала, как окончательный вариант примет значение (1 + 2ε) : Fn.

Если пренебречь ε, то асимптотически 1: Fn будет равно rn, при этом n→∞, а r = (√5 - 1) : 2, что приблизительно равно 0,6180.

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

Метод дихотомии

Если представить некую целевую функцию, то для начала потребуется найти ее экстремум на промежутке (a; b). Для этого ось абсцисс делится на четыре эквивалентные части, затем необходимо определить значение рассматриваемой функции в 5 точках. Далее выбирается минимум среди них. Экстремум функции должен лежать в пределах промежутка (a"; b"), который прилегает к точке минимума. Границы поиска сужаются в 2 раза. А если минимум расположен в т. a либо b, то он сужается во все четыре раза. Новый интервал также разделяется на четыре равных отрезка. В связи с тем, что значения данной функции в трех точках были определены на предыдущем этапе, далее требуется вычислить целевую функцию в двух точках.

Метод золотого сечения

Для существенных значений n координаты таких точек, как xn и xn-1 приближены к 1 - r, равное 0,3820, а r ≈ 0,6180. Толчок с данных значений весьма близок к искомой оптимальной стратегии.

Если предположить, что F(0,3820) > F(0,6180), то тогда очерчивается интервал . Однако ввиду того, что 0,6180 * 0,6180 ≈ 0,3820 ≈ xn-1, то в данной точке F уже известна. Следовательно, на каждом этапе, начиная со 2-го, необходимо только одно вычисление целевой функции, при этом каждый шаг сокращает длину рассматриваемого интервала с коэффициентом 0,6180.

В отличие от поиска Фибоначчи, в данном методе не требуется фиксация числа n еще до начала поиска.

«Золотое сечение» участка (a; b) - сечение, при котором отношение его r длины к более крупной части (a; c) идентично отношению большей части r к меньшей, то есть (a; с) к (c; b). Нетрудно догадаться, что r определяется по вышерассмотренной формуле. Следовательно, при существенных n метод Фибоначчи переходит в данный.

Метод удвоения шага

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

Сначала определяем начальную координату M0 функции F(M), минимальное значение шага h0, направление поиска. Затем определяем функцию в т. M0. Далее совершаем шаг и находим значение данной функции в данной точке.

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

Методы многомерной оптимизации

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

Группу методов 1-го порядка еще называют градиентными, потому что для установления направления поиска применяют градиент данной функции - вектор, составляющими которого выступают частные производные минимизированной функции по соответствующим оптимизированным параметрам.

В группе методов 2-го порядка применяются 2 производные (их использование достаточно ограничено ввиду наличия трудностей в их вычислении).

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

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

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

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

Также выделяют еще такие методы, которые используют сопряженные направления (Метод Дэвидона-Флетчера-Пауэлла). Его суть - преставление направлений поиска как Dj*grad(f(y)).

Классификация математических методов оптимизации

Условно, исходя из размерности функций (целевых), они бывают:

• с 1 переменной;
• многомерные.

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

По критерию применения производных математические методы оптимизации подразделяются на:

• методы вычисления 1 производной целевой функции;
• многомерные (1-я производная-векторная величина-градиент).

Исходя из эффективности вычисления, существуют:

• методы быстрого вычисления экстремума;
• упрощенного вычисления.

Это условная классификация рассматриваемых методов.

Оптимизация бизнес-процессов

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

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

Налоговая оптимизация: методы

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

Общие методы налоговой оптимизации следующие:

• проработка учетной политики компании с максимально возможным применением предоставленных российским законодательством возможностей (порядок списания МБП, выбор метода расчета выручки от реализации товара и др.);
• оптимизация посредством договора (заключение льготированных сделок, четкое и грамотное использование формулировок и т. п.);
• применение разного рода льгот, налоговых освобождений.

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

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

Классические методы безусловной оптимизации

Введение

Как известно, классическая задача безусловной оптимизации имеет вид:

Существуют аналитические и численные методы решения этих задач.

Прежде всего вспомним аналитические методы решения задачи безусловной оптимизации.

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

1. Необходимые условия для точки локального минимума (максимума)

Пусть т. доставляет минимальные значения функции. Известно, что в этой точке приращение функции неотрицательно, т.е.

Найдем, используя разложения функции в окрестности т. в ряд Тейлора.

где, - сумма членов ряда порядок которых относительно приращений (двум) и выше.

Из (4) с очевидностью следует, что

Предположим, что, тогда

С учетом (6) имеем: . (7)

Предположим, что положительно, т.е. . Выберем при этом, тогда произведение, что противоречит (1).

Поэтому, действительно, очевиден.

Рассуждая аналогично относительно других переменных получаем необходимое условие для точек локального минимума функции многих переменных

Легко доказать, что для точки локального максимума необходимые условия будут точно такими же, как и для точки локального минимуму, т.е. условиями (8).

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

Полученные необходимые условия не дают ответ на вопрос: является ли стационарная точка точкой минимума или точкой максимума.

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

2. Достаточные условия для точки локального минимума (максимума)

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

Разложение (1) можно представить более кратко, используя понятие: "скалярное произведение векторов" и "векторно-матричное произведение".

Матрица двух производных от целевой функции по соответствующим переменным.

Приращение функции на основании (1") можно записать в виде:

Учитывая необходимые условия:

Подставим (3) в виде:

Квадратичная форма называется дифференциальной квадратичной формой (ДКФ).

Если ДКФ положительно определена, то и стационарная точка является точкой локального минимума.

Если же ДКФ и матрица, ее представляющая, отрицательно определены, то и стационарная точка является точкой локального максимума.

Итак, необходимое и достаточное условие для точки локального минимума имеют вид

(эти же необходимые условия можно записать так:

Достаточное условие.

Соответственно, необходимое и достаточное условие локального максимума имеет вид:

Вспомним критерий, позволяющий определить: является ли квадратичная форма и матрица, ее представляющая, положительно определенной, или отрицательно определенной.

3. Критерий Сильвестра

Позволяет ответить на вопрос: является ли квадратичная форма и матрица, ее представляющая, положительно определенной, или отрицательно определенной.

Называется матрицей Гессе.

Главный определитель матрицы Гессе

и ДКФ, которую оно представляет, будут положительно определенными, если все главные определители матрицы Гессе () положительны (т.е. имеет место следующая схема знаков:

Если же имеет место другая схема знаков для главных определителей матрицы Гессе, например, то матрица и ДКФ отрицательно определены.

4. Метод Эйлера - классический метод решения задач безусловной оптимизации

Этот метод основан на необходимых и достаточных условиях, изученных в 1.1 - 1.3; применим нахождению локальных экстремумов только непрерывных дифференцируемых функций.

Алгоритм этого метода достаточно прост:

1) используя необходимые условия формируем систему в общем случае нелинейных уравнений. Отметим, что решить аналитически эту систему в общем случае невозможно; следует применить численные методы решения систем нелинейных уравнений (НУ) (см. "ЧМ"). По этой причине метод Эйлера будет аналитически-численным методом. Решая указанную систему уравнений находим координаты стационарной точки.;

2) исследуем ДКФ и матрицу Гессе, которая ее представляет. С помощью критерия Сильвестра определяем, является ли стационарная точка точкой минимума или точкой максимума;

3) вычисляем значение целевой функции в экстремальной точке

Методом Эйлера решить следующую задачу безусловной оптимизации: найти 4 стационарные точки функции вида:

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

5. Классическая задача условной оптимизации и методы ее решения: Метод исключения и Метод множителей Лагранжа (ММЛ)

Как известно, классическая задача условной оптимизации имеет вид:

График, поясняющий постановку задачи (1), (2) в пространстве.

Уравнения линий уровня

Итак, ОДР в рассматриваемой задаче представляет собой некоторую кривую, представленную уравнением (2").

Как видно из рисунка, точка является точкой безусловного глобального максимума; точка - точкой условного (относительного) локального минимума; точка - точка условного (относительного) локального максимума.

Задачу (1"), (2") можно решить методом исключения (подстановки), решив уравнение (2") относительно переменной, и подставляя найденное решение (1").

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

Метод исключения (подстановки).

Пусть целевая функция зависит от переменных:

называются зависимыми переменными (или переменными состояния); соответственно можно ввести вектор

Оставшиеся переменных называются независимыми переменными решения.

Соответственно можно говорить о вектор-столбце:

и вектора.

В классической задаче условной оптимизации:

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

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

не равен нулю (см. соответствующую теорему в курсе МА)

Как видно, функции, должны быть непрерывными дифференцируемыми функциями, во-вторых, элементы определителя должны быть вычислены в стационарной точке целевой функции.

Подставляем из (3) в целевую функцию (1), имеем:

Исследуемая функция на экстремум можно произвести методом Эйлера - методом безусловной оптимизации непрерывно дифференцируемой функции.

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

Недостаток метода исключения: трудности, а иногда и невозможность получения системы выражений (3). Свободный от этого недостатка, но требующий выполнения условия (4) является ММЛ.

5.2. Метод множителей Лагранжа. Необходимые условия в классической задаче условной оптимизации. Функция Лагранжа

ММЛ позволяет исходную задачу классической условной оптимизации:

Преобразовать в задачу безусловной оптимизации специально сконструированной функции - функции Лагранжа:

где, - множители Лагранжа;

Как видно, представляет собой сумму, состоящую из исходной целевой функции и "взвешенной" суммы функций, - функции, представляющие их ограничения (2) исходной задачи.

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

Используя концепция зависимых и независимых переменных - зависимые переменные; - независимые переменные, тогда представим (5) в развернутом виде:

Из (2) с очевидностью следует система уравнений вида:

Результат вычисления полного дифференциала для каждой из функций

Представим (6) в "развернутом" виде, используя концепцию зависимых и независимых переменных:

Заметим, что (6") в отличии от (5") представляет собой систему, состоящую из уравнений.

Умножим каждое -ое уравнение системы (6") на соответствующий -ый множитель Лагранжа. Сложим их между собой и с уравнением (5") и получим выражение:

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

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

Структуру такой системы уравнений легко получить приравняв выражение в квадратной скобке под знаком первой суммы нулю:

Перепишем (8) в виде

Система (8") представляет собой систему из линейных уравнений относительно известных: . Система разрешима, если (вот почему, как и в методе исключения в рассматриваемом случае должно выполняться условие). (9)

Поскольку в ключевом выражении (7) первая сумма равна нулю, то легко понять, что и вторая сумма будет равняться нулю, т.е. имеет место следующая система уравнений:

Система уравнений (8) состоит из уравнений, а система уравнений (10) состоит из уравнений; всего уравнений в двух системах, а неизвестных

Недостающие уравнений дает система уравнений ограничений (2):

Итак, имеется система из уравнений для нахождения неизвестных:

Полученный результат - система уравнений (11) составляет основное содержание ММЛ.

Легко понять, что систему уравнений (11) можно получить очень просто, вводя в рассмотрение специально сконструированную функцию Лагранжа (3).

Действительно

Итак, система уравнений (11) представима в виде (используя (12), (13)):

Система уравнений (14) представляет необходимое условие в классической задаче условной оптимизации.

Найденное в результате решение этой системы значение вектора называется условно-стационарной точкой.

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

5.3 Достаточные условия в классической задаче условной оптимизации. Алгоритм ММЛ

Эти условия позволяют выяснить, является ли условно-стационарная точка точкой локального условного минимума, или точкой локального условного максимума.

Относительно просто, подобно тому, как были получены достаточные условия в задаче на безусловный экстремум. Можно получить достаточные условия и в задаче классической условной оптимизации.

Результат этого исследования:

где - точка локального условного минимума.

где - точка локального условного максимума, - матрица Гессе с элементами

Матрица Гессе имеет размерность.

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

тогда достаточные условия будут иметь вид:

Точка локального условного минимума.

Точка локального условного максимума.

Доказательство: Алгоритм ММЛ:

1) составляем функцию Лагранжа: ;

2) используя необходимые условия, формируем систему уравнений:

3) из решения этой системы находим точку;

4) используя достаточные условия, определяем, является ли точка точкой локального условного минимума или максимума, затем находим

1.5.4. Графо-аналитический метод решения классической задачи условной оптимизации в пространстве и его модификации при решении простейших задач ИП и АП

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

В - общая касательная для функции и функции, представляющей ОДР.

Как видно из рисунка точка - точка безусловного минимума, точка точка условного локального минимума, точка - точка условного локального максимума.

Докажем, что в точках условных локальных экстремумов кривая и соответствующие линии уровня

Из курса МА известно, что в точке касания выполняется условие

где - угловой коэффициент касательной, проведенной соответствующей линией уровня; - угловой коэффициент касательной, проведенной к функции

Известно выражение (МА) для этих коэффициентов:

Докажем, что эти коэффициенты равны.

потому что об этом "говорят" необходимые условия

Вышесказанное позволяет сформулировать алгоритм ГФА метода решения классической задачи условной оптимизации:

1) строим семейство линий уровня целевой функции:

2) строим ОДР, используя уравнение ограничения

3) с целью внесения исправления возрастания функции, находим и выясняем характер экстремальных точек;

4) исследуем взаимодействие линий уровня и функции, находя при этом из системы уравнений координаты условно стационарных точек - локальных условных минимумов и локальных условных максимумов.

5) вычисляем

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

5.5. О практическом смысле ММЛ

Представим классическую задачу условной оптимизации в виде:

где - переменные величины, представляющие в прикладных технических и экономических задачах переменные ресурсы.

В пространстве задача (1), (2) принимает вид:

где - переменная величина. (2")

Пусть - точка условного экстремума:

При изменении изменяется

Соответственно изменится и значение целевой функции:

Вычислим производную:

Из (3), (4), (5). (6)

Подставим (5") в (3) и получаем:

Из (6), что множитель Лагранжа характеризует "реакцию" значение (ортогональна значению целевой функции) на изменения параметра.

В общем случае (6) принимает вид:

Из (6), (7), что множитель, характеризует изменение при изменении соответствующего -того ресурса на 1.

Если - максимальная прибыль или минимальная стоимость, то, характеризует изменения этой величины при изменении, на 1.

5.6. Классическая задача условной оптимизации, как задача о нахождении седловой точки функции Лагранжа:

Пара называется седловой точкой, если выполняется неравенство.

Очевидно, что из (1). (2)

Из (2), что. (3)

Как видно система (3) содержит уравнений, подобных тем уравнениям, которые представляют необходимое условие в классической задаче условной оптимизации:

где - функция Лагранжа.

В связи с аналогией систем уравнений (3) и (4), классическую задачу условной оптимизации можно рассматривать как задачу о нахождении седловой точки функции Лагранжа.

Подобные документы

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

контрольная работа , добавлен 26.11.2011


Характеристика классических методов безусловной оптимизации. Определение необходимого и достаточного условия существования экстремума функций одной и нескольких переменных. Правило множителей Лагранжа. Необходимые и достаточные условия оптимальности.

курсовая работа , добавлен 13.10.2013


Методика и особенности решения задач оптимизации, в частности о распределении инвестиций и выборе пути в транспортной сети. Специфика моделирования с помощью методов Хэмминга и Брауна. Идентификация, стимулирование и мотивация как функции управления.

контрольная работа , добавлен 12.12.2009


Постановка, анализ, графическое решение задач линейной оптимизации, симплекс-метод, двойственность в линейной оптимизации. Постановка транспортной задачи, свойства и нахождение опорного решения. Условная оптимизация при ограничениях–равенствах.

методичка , добавлен 11.07.2010


Критический путь в графе. Оптимальное распределение потока в транспортной сети. Задача линейного программирования, решаемая графическим методом. Несбалансированная транспортная задача. Численные методы решения одномерных задач статической оптимизации.

курсовая работа , добавлен 21.06.2014


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

контрольная работа , добавлен 15.10.2010


Оптимизационные методы решения экономических задач. Классическая постановка задачи оптимизации. Оптимизация функций. Оптимизация функционалов. Многокритериальная оптимизация. Методы сведения многокритериальной задачи к однокритериальной. Метод уступок.

реферат , добавлен 20.06.2005


Применение методов нелинейного программирования для решения задач с нелинейными функциями переменных. Условия оптимальности (теорема Куна-Таккера). Методы условной оптимизации (метод Вульфа); проектирования градиента; штрафных и барьерных функций.

реферат , добавлен 25.10.2009


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

курсовая работа , добавлен 21.01.2012


Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.