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

Главная » Тесты » Оптимизация в центре теории экономики. Какие существуют методы оптимизации? Методы оптимизации управленческих решений Классификация математических методов оптимизации

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

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

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

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

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

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

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

Все оптимизационные задачи имеют общую структуру. Их можно классифицировать как задачи минимизации(максимизации) M-векторного векторного показателя эффективности Wm(x), m=1,2,...,M, N-мерного векторного аргумента x=(x1,x2,...,xN), компоненты которого удовлетворяют системе ограничений-равенств hk(x)=0, k=1,2...K, ограничений-неравенств gj(x)>0, j=1,2,...J, областным ограничениям xli

Все задачи принятия оптимальных решений можно классифицировать в соответствии с видом функций и размерностью Wm(x), hk(x), gj(x) и размерностью и содержанием вектора x:

· одноцелевое принятие решений - Wm(x) - скаляр;

· многоцелевое принятие решений - Wm(x) - вектор;

· принятие решений в условиях определенности - исходные данные - детерминированные;

· принятие решений в условиях неопределенности - исходные данные - случайные.

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

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

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

· возможность неоднозначности результатов;

· возможность неоднозначности способов достижения результатов, то есть свобода выбора.

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

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

· анализ исходной ситуации;

· анализ возможностей выбора;

· выбор решения;

· оценка последствий решения и его корректировка.

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

Среди оптимизационных задач в теории принятия решений наиболее известны задачи линейного программирования, в которых максимизируемая функция F (X ) является линейной, а ограничения А задаются линейными неравенствами. Начнем с примера.

Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Обозначим: Х 1 - число изготовленных стульев, Х 2 - число сделанных столов. Задача оптимизации имеет вид:

45 Х 1 + 80 Х 2 → max ,

5 Х 1 + 20 Х 2 ≤ 400 ,

10 Х 1 + 15 Х 2 ≤ 450 ,

Х 1 ≥ 0 ,

Х 2 ≥ 0 .

В первой строке выписана целевая функция - прибыль при выпуске Х 1 стульев и Х 2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х 1 и Х 2 . При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если Х 1 = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х 1 положительно. Но невозможно представить себе отрицательный выпуск - Х 1 не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.

Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения Х 1 , а по вертикальной оси ординат - значения Х 2 . Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х 1 , Х 2) объемов выпуска в виде треугольника (рис.1).

Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х 2 , соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на

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

Аналогичным образом можно изобразить и ограничения по труду (рис.2).

Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х 2 , соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать.

Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?

Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).

Таким образом, множество возможных значений объемов выпуска стульев и столов (Х 1 , Х 2), или, в других терминах, множество А , задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений

5 Х 1 + 20 Х 2 = 400 ,

10 Х 1 + 15 Х 2 = 450 .

Из первого уравнения: 5 Х 1 = 400 - 20 Х 2 , Х 1 = 80 - 4 Х 2 . Подставляем во второе уравнение:

10 (80 - 4 Х 2) + 15 Х 2 = 800 - 40Х 2 + 15 Х 2 = 800 - 25 Х 2 = 450,

следовательно, 25 Х 2 = 350, Х 2 = 14, откуда Х 1 = 80 - 4 х 14 = 80 -56 =24.

Итак, четвертая вершина четырехугольника - это (24, 14).

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

Целевая функция 45 Х 1 + 80 Х 2 принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х 1 + 80 Х 2 = 2200 проходит между прямыми ограничений 5 Х 1 + 20 Х 2 = 400 и 10 Х 1 + 15 Х 2 = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).

Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.

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

45 Х 1 + 80 Х 2 → max , 400 W 1 + 450 W 2 → min ,

5 Х 1 + 20 Х 2 ≤ 400 , 5 W 1 + 10 W 2 ≥ 45,

10 Х 1 + 15 Х 2 ≤ 450 , 20 W 1 + 15 W 2 ≥ 80,

Х 1 ≥ 0 , W 1 ≥ 0,

Х 2 ≥ 0 . W 2 ≥ 0.

Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). При этом оптимальные значения W 1 и W 2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W 1 и W 2 называют "объективно обусловленными оценками" сырья и рабочей силы.

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

Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910-1985, родился в Нидерландах, работал в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.

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

Задача о диете (упрощенный вариант). Предположим для определенности, что необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ (для простоты, тиамина Т и ниацина Н).

Таблица 1.

Исходные данные в задаче об оптимизации смеси.

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

3,8 К + 4,2 С → min ,

0,10 К + 0,25 С ≥ 1,00 ,

1,00 К + 0,25 С ≥ 5,00 ,

110,00 К + 120,00 С ≥ 400,00 ,

К ≥ 0 ,

С ≥ 0 .

Ее графическое решение представлено на рис.4.

Рис.4. Графическое решение задачи об оптимизации смеси.

На рис.4 ради облегчения восприятия четыре прямые обозначены номерами (1) - (4). Прямая (1) - это прямая 1,00 К + 0,25 С = 5,00 (ограничение по веществу Н). Она проходит, как и показано на рисунке, через точки (5,0) на оси абсцисс и (0,20) на оси ординат. Обратите внимание, что допустимые значения параметров (К, С ) лежат выше прямой (1) или на ней, в отличие от ранее рассмотренных случаев в предыдущей производственной задаче линейного программирования.

Прямая (2) - это прямая 110,00 К + 120,00 С = 400,00 (ограничение по калориям). Обратим внимание, что в области неотрицательных С она расположена всюду ниже прямой (1). Действительно, это верно при К =0, прямая (1) проходит через точку (0,20), а прямая (2) - через расположенную ниже точку (0, 400/120). Точка пересечения двух прямых находится при решении системы уравнений

1,00 К + 0,25 С = 5,00 ,

110,00 К + 120,00 С = 400,00 .

Из первого уравнения К = 5 - 0,25 С . Подставим во второе: 110 (5- 0,25 С ) + 120 С = 400, откуда 550 - 27,5 С + 120 С = 400. Следовательно, 150 = - 92,5 С , т.е. решение достигается при отрицательном С . Это и означает, что при всех положительных С прямая (2) лежит ниже прямой (1). Значит, если выполнено ограничения по Н, то обязательно выполнено и ограничение по калориям. Мы столкнулись с новым явлением - некоторые ограничения с математической точки зрения могут оказаться лишними. С экономической точки зрения они необходимы, отражают существенные черты постановки задачи, но в данном случае внутренняя структура задачи оказалась такова, что ограничение по калориям не участвует в формировании допустимой области параметров и нахождении решения.

Прямая (4) - это прямая 0,1 К + 0,25 С = 1 (ограничение по веществу Т). Она проходит, как и показано на рисунке, через точки (10,0) на оси абсцисс и (0,4) на оси ординат. Обратите внимание, что допустимые значения параметров (К , С ) лежат выше прямой (4) или на ней, как и для прямой (1).

Следовательно, область допустимых значений параметров (К , С ) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (1) и (4) (лежит выше этих прямых, а также включает граничные отрезки). Область допустимых значений параметров, т.е. точек (К , С ), можно назвать "неограниченным многоугольником". Минимум целевой функции 3,8 К + 4,2 С может достигаться только в вершинах этого "многоугольника". Вершин всего три. Это пересечения с осями абсцисс (10,0) и ординат (0,20) прямых (1) и (4) (в каждом случае из двух пересечений берется то, которое удовлетворяет обоим ограничениям). Третья вершина - это точка А пересечения прямых (1) и (4), координаты которой находятся при решении системы уравнений

0,10 К + 0,25 С = 1,00 ,

1,00 К + 0,25 С = 5,00 .

Из второго уравнения К = 5 - 0,25 С , из первого 0,10 (5 - 0,25 С ) + 0,25 С = 0,5 - 0,025 С + 0,25 С = 0,5 + 0,225 С = 1, откуда С = 0,5/0,225 = 20/9 и К = 5 - 5/9 = 40/9. Итак, А = (40/9; 20/9).

Прямая (3) на рис.4 - это прямая, соответствующая целевой функции 3,8 К + 4,2 С . Она проходит между прямыми (1) и (4), задающими ограничения, и минимум достигается в точке А , через которую и проходит прямая (3). Следовательно, минимум равен 3,8х40/9 + 4,2х20/9 = 236/9. Задача об оптимизации смеси полностью решена.

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

3,8 К + 4,2 С → min , W 1 + 5 W 2 + 400 W 3 → max ,

0,10 К + 0,25 С ≥ 1,00 , 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8 ,

1,00 К + 0,25 С ≥ 5,00 , 0,25W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2 ,

110,00 К + 120,00 С ≥ 400,00 , W 1 ≥ 0 ,

К ≥ 0 , W 2 ≥ 0 ,

С ≥ 0 . W 3 ≥ 0 .

Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т.е. оба числа равны 236/9. Интерпретация двойственных переменных: W 1 - "стоимость" единицы вещества Т, а W 2 - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевую функцию. При этом W 3 = 0, поскольку ограничение на число калорий никак не участвует в формировании оптимального решения. Итак, W 1 , W 2 , W 3 - это т.н. объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т и Н, калорий).

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

Таблица 2.

Производственные мощности (в шт.)

	Кофеварки	Самовары
Штамповка


Объем выпуска
Удельная прибыль (на одно изделие)

При этом штамповка и отделка проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок, либо и то, и другое, не в меньшем количестве. А вот сборка проводится на отдельных участках.

Задача линейного программирования имеет вид:

Х 1 ≥ 0 , Х 2 ≥ 0 , Х 3 ≥ 0 , (0)

Х 1 / 200 + Х 2 / 300 + Х 3 / 120 ≤ 100 , (1)

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 ≤ 100 , (2)

Х 1 / 200 ≤ 100 , (3)

Х 2 / 120 ≤ 100 , (4)

Х 3 / 80 ≤ 100 , (5)

F = 15 Х 1 + 12 Х 2 + 14 Х 3 → max .

(0) - обычное в экономике условие неотрицательности переменных,

(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах),

(2) - ограничение по возможностям отделки,

(3) - ограничение по сборке для кухонь,

(4) - то же для кофемолок,

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

Наконец, целевая функция F - общая прибыль предприятия.

Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4) - из (2). Поэтому неравенства (3) и (4) можно из формулировки задачи линейного программирования ислючить.

Отметим сразу любопытный факт. Как будет установлено, в оптимальном плане Х 3 = 0, т.е. самовары выпускать невыгодно.

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

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

Простой перебор . Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х 1 + 5Х 2 ≤ 10, то, очевидно, 0 ≤ Х 1 ≤ 10/2 = 5 и 0 ≤ Х 2 ≤ 10/5 = 2. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

Проведем перебор точек параллелепипеда с шагом 1/10 n последовательно при n =2,3,…, вычисляя значения целевой функции и проверяя выполнение ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10 n .)

Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно – с помощью т.н. метода случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆. Если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

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

Рассмотрим задачу линейного программирования, сформулированную выше при рассмотрении оптимизации номенклатуры и объемов выпуска:

F = 15 Х 1 + 12 Х 2 + 14 Х 3 → max .

Х 1 / 200 + Х 2 / 300 + Х 3 / 120 ≤ 100 ,

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 ≤ 100 ,

Х 3 / 80 ≤ 100 .

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

В соответствии с симплекс-методом введем т.н. "свободные переменные" Х 4 , Х 5 , Х 6 , соответствующие недоиспользованным мощностям, т.е. от системы неравенств перейдем к системе уравнений:

Х 1 / 200 + Х 2 / 300 + Х 3 / 120 + Х 4 = 100 ,

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 + Х 5 = 100 ,

Х 3 / 80 + Х 6 = 100 ,

15 Х 1 + 12 Х 2 + 14 Х 3 = F .

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

Х 1 = Х 2 = Х 3 = 0, Х 4 = Х 5 = Х 6 = 100, F = 0.

В терминах исходной задачи это означает, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.

В соответствии с симплекс-методом выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х 1 .

Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной Х 1:

100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞ .

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

Умножим первую строку на 200, чтобы получить Х 1 с единичным коэффициентом:

Х 1 + 2/3 Х 2 + 2/1,2 Х 3 + 200 Х 4 = 20000 .

Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, чтобы исключить член с Х 1 , получим

7/900 Х 2 + 4/900 Х 3 - 2/3 Х 4 + Х 5 = 100/3.

Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит F , получим:

2 Х 2 - 11 Х 3 - 3000 Х 4 = F - 300000.

В результате система уравнений преобразуется к виду, в котором переменная Х 1 входит только в первое уравнение:

Х 1 + 2/3 Х 2 + 2/1,2 Х 3 + 200 Х 4 = 20000 ,

7/900 Х 2 + 4/900 Х 3 - 2/3 Х 4 + Х 5 = 100/3,

Х 3 / 80 + Х 6 = 100 ,

2 Х 2 - 11 Х 3 - 3000 Х 4 = F - 300000.

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

Х 1 = 20000, Х 2 = Х 3 = Х 4 = 0, Х 5 = 100/3, Х 6 = 100, F = 300000.

В терминах исходной задачи это решение означает, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции.

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

20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.

Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при Х 2 равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим Х 2 , предварительно умножив их на подходящие числа, т.е. такие, чтобы все коэффициенты при Х 2 стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:

Х 1 + 9/7 Х 3 + 1800/7 Х 4 - 600/7 Х 5 = 120000/7 ,

Х 2 + 4/7 Х 3 - 600/7 Х 4 + 900/7 Х 5 = 30000/7,

Х 3 / 80 + Х 6 = 100 ,

85/7 Х 3 - 19800/7 Х 4 - 1800/7 Х 5 = F - 308571.

Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при Х 3 = Х 4 = Х 5 = 0. Из остальных уравнений следует, что при этом Х 1 = 120000/7 = 17143, Х 2 = 30000/7 = 4286, Х 6 = 100. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено.

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

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

В качестве очередного примера рассмотрим т.н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать "прикрепление" потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.

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

Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 3.

В табл.3, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада i , i = 1,2,3, потребителю j , j = 1,2,3,4. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется 50+70 =120 единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.

Таблица 3.

Исходные данные к транспортной задаче.

	Потреби-тель 1	Потреби-тель 2	Потреби-тель 3	Потреби-тель 4	Запасы на складах



Потреб-ности

Надо спланировать перевозки, т.е. выбрать объемы Х ij поставок товара со склада i потребителю j , где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:

X 11 + Х 12 + Х 13 + Х 14 = 60 ,

X 21 + Х 22 + Х 23 + Х 24 = 80 ,

X 31 + Х 32 + Х 33 + Х 34 = 60 .

Во-вторых, известны потребности клиентов:

X 11 + Х 21 + Х 31 = 50 ,

X 12 + Х 22 + Х 32 = 40 ,

X 13 + Х 23 + Х 33 = 70 ,

X 14 + Х 24 + Х 34 = 40 .

Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений.

Целевая функция - издержки по перевозке, которые необходимо минимизировать:

F = 2 X 11 + 5 Х 12 + 4 Х 13 + 5 Х 14 + X 21 + 2 Х 22 + Х 23 + 4 Х 24 +

3 X 31 + Х 32 + 5 Х 33 + 2 Х 34 → min .

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

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

3.2.2. Целочисленное программирование

Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к целочисленному программированию. Рассмотрим несколько таких задач.

Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м 2 . Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м 2 (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м 2 и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.

Пусть Х - количество станков типа А, а У - количество станков типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы максимизировать производительность С участка (в тыс. единиц за смену):

С = 7 Х + 3 У → max .

При этом должны быть выполнены следующие ограничения:

по стоимости (в тыс. долларов США)

5 Х + 2 У ≤ 20,

по занимаемой площади (в м 2)

8 Х + 4 У ≤ 38,

а также вновь появляющиеся специфические ограничения по целочисленности, а именно,

Х ≥ 0 , У ≥ 0 , Х и У - целые числа.

Сформулированная математическая задача отличается от задачи линейного программирования только последним условием целочисленности. Однако наличие этого условия позволяет (в данном конкретном случае) легко решить задачу перебором. Действительно, как ограничение по стоимости, так и ограничение по площади дают, что Х ≤ 4. Значит, Х может принимать лишь одно из 5 значений: 0, 1, 2, 3, 4.

Если Х = 4, то из ограничения по стоимости следует, что У = 0, а потому С = 7 Х = 28.

Если Х = 3, то из первого ограничения вытекает, что У ≤ 2, из второго У ≤ 3. Значит, максимальное С У =2, а именно С = 21 + 6 = 27.

Если Х = 2, то из первого ограничения следует, что У ≤ 5, из второго также У ≤ 5. Значит, максимальное С при условии выполнения ограничений достигается при У =5, а именно С = 14 + 15 = 29.

Если Х = 1, то из первого ограничения имеем У ≤ 7, из второго также У ≤ 7. Значит, максимальное С при условии выполнения ограничений достигается при У = 7, а именно С = 7 + 21 = 28.

Если Х = 0, то из первого ограничения вытекает У ≤ 10, из второго У ≤ 9. Значит, максимальное С при условии выполнения ограничений достигается при У = 9, а именно, С = 27.

Все возможные случаи рассмотрены. Максимальная производительность С = 29 (тысяч единиц продукции за смену) достигается при Х = 2, У = 5. Следовательно, надо покупать 2 станка типа А и 5 станков типа Б.

Задача о ранце . Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес каждого предмета известен.

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

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

Перейдем к математической постановке. Предполагается, что имеется n предметов, и для каждого из них необходимо решить, класть его в ранец или не класть. Для описания решения вводятся булевы переменные Х k , k = 1,2,…, n (т.е. переменные, принимающие два значения, а именно, 0 и 1). При этом Х k = 1, если предмет размещают в ранце, и Х k = 0, если нет, k = 1,2,…, n . Для каждого предмета известны две константы: А k - вес k -го предмета, и С k - полезность k -го предмета, k = 1,2,…, n . Максимально возможную вместимость ранца обозначим В . Оптимизационная задача имеет вид

C 1 Х 1 + С 2 Х 2 + С 3 Х 3 + …. + С n Х n → max ,

А 1 Х 1 + А 2 Х 2 + А 3 Х 3 + …. + А n Х n ≤ В .

В отличие от предыдущих задач, управляющие параметры Х k , k = 1,2,…, n , принимают значения из множества, содержащего два элемента - 0 и 1.

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

Укажем два распространенных метода решения задач целочисленного программирования

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

Методы направленного перебора . Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству Х множества возможных решений Х 0 ставится в соответствие число - "граница" А(Х ). При решении задачи минимизации необходимо, чтобы А (Х 1) ≥ А(Х 2 ), если Х 1 входит в Х 2 или совпадает с Х 2 .

Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества Х С на два - Х 1С и Х 2С . При этом пересечение Х 1С и Х 2С пусто, а их объединение совпадает с Х С . Затем вычисляют границы А (Х 1С) и А (Х 2С ) и выделяют "ветвь" Х С +1 - то из множеств Х 1С и Х 2С, для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа

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

3.2.3. Теория графов и оптимизация

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

Рис.5. Примеры графов.

На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис.6.

Рис.6. Примеры ориентированных графов.

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

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

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

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

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

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

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

Задача о кратчайшем пути . Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).

Рис.7. Исходные данные к задаче о кратчайшем пути.

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

Таблица 4.

Исходные данные к задаче о кратчайшем пути.

Начало дуги	Конец дуги	Время в пути

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?

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

Для исходных данных, представленных на рис.7 и в табл.4, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С (3) = 1. Кроме того, очевидно, что С (1) = 0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

С (4) = min {С(2) + 4; С (5) + 5}.

Таким образом, проведена реструктуризация (упрощение) задачи - нахождение С(4) сведено к нахождению С(2) и С (5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

С (5) = min {С (3) + 2; С (6) + 3}.

Мы знаем, что С (3) = 1. Поэтому

С(5) = min {3; С (6) + 3}.

Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С (5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

С (2) = min {С(1) + 7; С(3) + 5; С (5) + 2}.

Нам известно, что С(1) = 0, С (3) = 1, С (5) = 3. Поэтому

С (2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Теперь мы можем найти С (4):

С (4) = min {С (2) + 4; С (5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С (5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

1 → 3 → 5 → 4 .

Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.4) полностью решена.

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

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

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

Рис.8. Исходные данные к задаче о максимальном потоке

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.8, можно также задать таблицей (табл.5).

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

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.

Таблица 5.

Исходные данные к задаче о максимальном потоке

Пункт отправления	Пункт назначения	Пропускная способность

Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 2. Их направляем в пункт 4.

Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.

Решение можно представить в виде таблицы (табл.6).

Таблица 6.

Решение задачи о максимальном потоке

Пункт отправления	Пункт назначения	План перевозок	Пропускная способность

Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х KM - объем перевозок из пункта К в пункт М . Согласно рис.8 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х KM , а именно, Х 01 , Х 02 , Х 03 , Х 12 , Х 13 , Х 14 , Х 23 , Х 24 , Х 34 . Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

F → max ,

Х 01 + Х 02 + Х 03 = F (0)

- Х 01 + Х 12 + Х 13 + Х 14 = 0 (1)

- Х 02 - Х 12 + Х 23 + Х 24 = 0 (2)

- Х 03 - Х 13 - Х 23 + Х 34 = 0 (3)

- Х 14 - Х 24 - Х 34 = - F (4)

Х 01 ≤ 2

Х 02 ≤ 3

Х 03 ≤ 1

Х 12 ≤ 4

Х 13 ≤ 1

Х 14 ≤ 3

Х 23 ≤ 1

Х 24 ≤ 2

Х 34 ≤ 2

Х КМ ≥ 0 , К, М = 0, 1, 2, 3, 4

F ≥ 0 .

Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не "рождаются" в ней. Условие (4) - это условие "выхода" грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом ("вход" равен "выходу"). Следующие девять неравенств задают ограничения на пропускную способность отдельных "веток" транспортной системы. Затем в системе ограничений задачи линейного программирования указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом "не знает").

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

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

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

Литература

1. Гасс С. Путешествие в страну линейного программирования / Пер. с англ. - М.: Мир, 1973. - 176 с.

2. Кофман А., Фор Р. Займемся исследованием операций / Пер. с франц.. - М,: Мир, 1966. -280 с.

3. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: Высшая школа, 1976. - 392 с.

4. Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными системами. – М.: Синтег, 2001. – 124 с.

5. Орлов А.И. Задачи оптимизации и нечеткие переменные. – М.: Знание, 1980. – 64 с.

6. Орлов А.И. Эконометрика. – М.: Изд-во «Экзамен», 2002. – 576 с.

Задачи по методам принятия решений

1. Изобразите на плоскости ограничения задачи линейного программирования и решите (графически) эту задачу:

400 W 1 + 450 W 2 → min ,

5 W 1 + 10 W 2 ≥ 45,

20 W 1 + 15 W 2 ≥ 80,

W 1 ≥ 0, W 2 ≥ 0.

2. Решите задачу линейного программирования:

W 1 + 5 W 2 → max ,

0,1 W 1 + W 2 ≤ 3,8 ,

0,25 W 1 + 0,25 W 2 ≤ 4,2 ,

W 1 ≥ 0 , W 2 ≥ 0 .

3. Решите задачу целочисленного программирования:

10 Х + 5 У → max .

8 Х + 3 У ≤ 40,

3 Х + 10 У ≤ 30,

Х ≥ 0 , У ≥ 0 , Х и У - целые числа.

4. Решите задачу о ранце:

Х 1 + Х 2 + 2 Х 3 + 2Х 4 + Х 5 + Х 6 → max ,

0,5 Х 1 + Х 2 + 1,5 Х 3 + 2Х 4 + 2,5Х 5 + 3Х 6 ≤ 3.

Управляющие параметры Х k , k = 1,2,…, 6 , принимают значения из множества, содержащего два элемента - 0 и 1.

5. Транспортная сеть (с указанием расстояний) приведена на рис.9. Найдите кратчайший путь из пункта 1 в пункт 4.

Рис.9. Исходные данные к задаче о кратчайшем пути.

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

Таблица 7.

Исходные данные к задаче коммивояжера

Город отправления	Город назначения	Затраты на проезд

8. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис.10) ограничена (табл.8)?

Рис.9. Транспортная сеть к задаче о максимальном потоке.

Таблица 8.

Исходные данные к задаче о максимальном потоке

Пункт отправления	Пункт назначения	Пропускная способность

Темы докладов и рефератов

1. Классификация оптимизационных задач принятия решений.

2. Решения, оптимальные по Парето.

3. Многокритериальные задачи принятия решений: различные методы свертки критериев.

4. Задачи оптимизации и нечеткие переменные (на основе работы ).

5. Моделирование и экспертные оценки при принятии решений.

6. Интерактивные системы принятия решений.

7. Методы учета неопределенностей принятия решений: вероятностные модели, теория нечеткости, интервальная математика.

8. Эконометрические методы принятия решений (на основе монографии ).

9. Имитационное моделировании и метод статистических испытаний (Монте-Карло) при принятии решений.

11. Методы теории игр (теория конфликтов), роль информации и равновесие по Нэшу в теории принятия решений.

12. Проблемы комбинированного применения различных методов в конкретных прикладных работах.

13. Информационные технологии поддержки принятия решений.

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

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

Тогда решить задачу означает одно из:

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

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

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

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

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

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

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

детерминированные;
случайные (стохастические);
комбинированные.

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

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

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

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

Помимо того, оптимизационные методы делятся на следующие группы:

аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера);
графические методы.

В зависимости от природы множества X задачи математического программирования классифицируются как:

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

Кроме того, разделами математического программирования являются параметрическое программирование , динамическое программирование и стохастическое программирование .

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

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования:

Определение границ системы оптимизации
- Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается
Выбор управляемых переменных
- «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)
Определение ограничений на управляемые переменные
- … (равенства и/или неравенства)
Выбор числового критерия оптимизации (например, показателя эффективности)
- Создаём целевую функцию

История

Канторовичем совместно с М. К. Гавуриным в 1949 году разработан метод потенциалов , который применяется при решении транспортных задач . В последующих работах Канторовича, Немчинова , В. В. Новожилова , А. Л. Лурье , А. Брудно , Аганбегяна , Д. Б. Юдина, Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования , так и приложение её методов к исследованию различных экономических проблем.

Методам линейного программирования посвящено много работ зарубежных учёных. В 1941 году Ф. Л. Хитчкок поставил транспортную задачу . Основной метод решения задач линейного программирования - симплекс-метод - был опубликован в 1949 году Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Куна (англ. ), А. Таккера (англ. ), Гасса (Saul. I. Gass), Чарнеса (Charnes A.), Била (Beale E. M.) и др.

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

Начиная с 1955 году опубликовано много работ, посвященных квадратическому программированию (работы Била, Баранкина и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования.

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

См. также

Примечания

Литература

Абакаров А. Ш., Сушков Ю. А. Статистическое исследование одного алгоритма глобальной оптимизации . - Труды ФОРА, 2004.
Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. - М .: Высшая школа, 1986.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. - М .: Мир, 1985.
Гирсанов И. В. Лекции по математической теории экстремальных задач. - М .; Ижевск : НИЦ «Регулярная и хаотическая динамика», 2003. - 118 с. - ISBN 5-93972-272-5
Жиглявский А. А., Жилинкас А. Г. Методы поиска глобального экстремума. - М .: Наука, Физматлит, 1991.
Карманов В. Г. Математическое программирование. - Изд-во физ.-мат. литературы, 2004.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М .: Наука, 1970. - С. 575-576.
Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М .: Энергоатомиздат, 1972.
Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М .: МИФИ, 1982.
Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М .: МИФИ, 1980.
Плотников А. Д. Математическое программирование = экспресс-курс. - 2006. - С. 171. - ISBN 985-475-186-4
Растригин Л. А. Статистические методы поиска. - М ., 1968.
Хемди А. Таха. Введение в исследование операций = Operations Research: An Introduction. - 8 изд. - М .: Вильямс, 2007. - С. 912. - ISBN 0-13-032374-8
Кини Р. Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. - М .: Радио и связь, 1981. - 560 с.
С.И.Зуховицкий , Л.И.Авдеева. Линейное и выпуклое программирование. - 2-е изд., перераб. и доп.. - М .: Издательство «Наука», 1967.

Ссылки

Б.П. Поляк . История математического программирования в СССР: анализ феномена // Труды 14-й Байкальской школы-семинара «Методы оптимизации и их приложения» . - 2008. - Т. 1. - С. 2-20.

Методы оптимизации
Одномерные	Метод золотого сечения Дихотомия Метод парабол Перебор по сетке Метод Фибоначчи Троичный поиск
Прямые методы	Метод Гаусса Метод Нелдера - Мида Метод Хука - Дживса Метод конфигураций Метод Розенброка
Первого порядка	Градиентный спуск Метод Зойтендейка Покоординатный спуск Метод сопряжённых градиентов Квазиньютоновские методы Алгоритм Левенберга - Марквардта
Второго порядка	Метод Ньютона Метод Ньютона - Рафсона
Стохастические	Метод Монте-Карло Имитация отжига Эволюционные алгоритмы Дифференциальная эволюция Муравьиный алгоритм Метод роя частиц
Методы линейного программирования	Симплекс-метод Алгоритм Гомори Метод эллипсоидов Метод потенциалов
Методы нелинейного программирования	Последовательное квадратичное программирование

Wikimedia Foundation . 2010 .

Допустимое множество - множество $\mathbb{X}=\{\vec{x}|\;g_i(\vec{x})\leq 0,\;i=1,\ldots,m\} \subset \mathbb{R}^n$ ;
Целевую функцию - отображение $f:\;\mathbb{X}\to\mathbb{R}$ ;
Критерий поиска (max или min).

Тогда решить задачу $f(x)\to \min_{\vec{x}\in\mathrm{X}}$ означает одно из:

Показать, что $\mathbb{X}=\varnothing$ .
Показать, что целевая функция $f(\vec{x})$ не ограничена снизу.
Найти $\vec{x}^*\in\mathbb{X}:\;f(\vec{x}^*)=\min_{\vec{x}\in\mathbb{X}}f(\vec{x})$ .
Если $\nexists \vec{x}^*$ , то найти $\inf_{\vec{x}\in\mathbb{X}}f(\vec{x})$ .

Если минимизируемая функция не является выпуклой , то часто ограничиваются поиском локальных минимумов и максимумов: точек $x_0$ таких, что всюду в некоторой их окрестности $f(x)\ge f(x_0)$ для минимума и $f(x)\le f(x_0)$ для максимума.

Если допустимое множество $\mathbb{X}=\mathbb{R}^n$ , то такая задача называется задачей безусловной оптимизации , в противном случае - задачей условной оптимизации .

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

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

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

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

детерминированные;
случайные (стохастические);
комбинированные.

Задачи оптимизации, в которых целевая функция $f(\vec{x})$ и ограничения $g_i(\vec{x}),\; i=1,\ldots,m$ являются линейными функциями, разрешаются так называемыми методами линейного программирования .
В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:
- если $f(\vec{x})$ и $g_i(\vec{x}),\;i=1,\ldots,m$ - выпуклые функции, то такую задачу называют задачей выпуклого программирования ;
- если $\mathbb{X}\subset \mathbb{Z}$ , то имеют дело с задачей целочисленного (дискретного) программирования .

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

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

Помимо того, оптимизационные методы делятся на следующие группы:

аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера);

В зависимости от природы множества X задачи математического программирования классифицируются как:

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

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

Определение границ системы оптимизации
- Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается
Выбор управляемых переменных
- «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)
Определение ограничений на управляемые переменные
- … (равенства и/или неравенства)
Выбор числового критерия оптимизации (например, показателя эффективности)
- Создаём целевую функцию

История

Канторовичем совместно с М. К. Гавуриным в 1949 году разработан метод потенциалов , который применяется при решении транспортных задач . В последующих работах Канторовича, Немчинова , В. В. Новожилова , А. Л. Лурье , А. Брудно , Аганбегяна , Д. Б. Юдина , Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования , так и приложение её методов к исследованию различных экономических проблем.

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

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

См. также

Напишите отзыв о статье "Оптимизация (математика)"

Примечания

Литература

Абакаров А. Ш., Сушков Ю. А. . - Труды ФОРА, 2004.
Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. - М .: Высшая школа, 1986.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. - М .: Мир, 1985.
Гирсанов И. В. Лекции по математической теории экстремальных задач. - М .; Ижевск : НИЦ «Регулярная и хаотическая динамика», 2003. - 118 с. - ISBN 5-93972-272-5 .
Жиглявский А. А., Жилинкас А. Г. Методы поиска глобального экстремума. - М .: Наука, Физматлит, 1991.
Карманов В. Г. Математическое программирование. - Изд-во физ.-мат. литературы, 2004.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М .: Наука, 1970. - С. 575-576.
Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М .: Энергоатомиздат, 1972.
Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М .: МИФИ, 1982.
Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М .: МИФИ, 1980.
Плотников А. Д. Математическое программирование = экспресс-курс. - 2006. - С. 171. - ISBN 985-475-186-4 .
Растригин Л. А. Статистические методы поиска. - М ., 1968.
Хемди А. Таха. Введение в исследование операций = Operations Research: An Introduction. - 8 изд. - М .: Вильямс , 2007. - С. 912. - ISBN 0-13-032374-8 .
Кини Р. Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. - М .: Радио и связь, 1981. - 560 с.
С.И.Зуховицкий , Л.И.Авдеева. Линейное и выпуклое программирование. - 2-е изд., перераб. и доп.. - М .: Издательство «Наука», 1967.
А.А. Болонкин ,. Новые методы оптимизации и их применение. Краткий конспект лекций по курсу «Теория оптимальных систем».. - М .: МВТУ им.Баумана, 1972, 220 стр. viXra.org/abs/1503.0081.

Ссылки

Б.П. Поляк . // Труды 14-й Байкальской школы-семинара «Методы оптимизации и их приложения». - 2008. - Т. 1 . - С. 2-20 .
.

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

Одномерные

Прямые методы

Первого порядка

Второго порядка

Стохастические

Методы линейного программирования

Методы нелинейного программирования

Отрывок, характеризующий Оптимизация (математика)

Князь Андрей провел Пьера на свою половину, всегда в полной исправности ожидавшую его в доме его отца, и сам пошел в детскую.
– Пойдем к сестре, – сказал князь Андрей, возвратившись к Пьеру; – я еще не видал ее, она теперь прячется и сидит с своими божьими людьми. Поделом ей, она сконфузится, а ты увидишь божьих людей. C"est curieux, ma parole. [Это любопытно, честное слово.]
– Qu"est ce que c"est que [Что такое] божьи люди? – спросил Пьер
– А вот увидишь.
Княжна Марья действительно сконфузилась и покраснела пятнами, когда вошли к ней. В ее уютной комнате с лампадами перед киотами, на диване, за самоваром сидел рядом с ней молодой мальчик с длинным носом и длинными волосами, и в монашеской рясе.
На кресле, подле, сидела сморщенная, худая старушка с кротким выражением детского лица.
– Andre, pourquoi ne pas m"avoir prevenu? [Андрей, почему не предупредили меня?] – сказала она с кротким упреком, становясь перед своими странниками, как наседка перед цыплятами.
– Charmee de vous voir. Je suis tres contente de vous voir, [Очень рада вас видеть. Я так довольна, что вижу вас,] – сказала она Пьеру, в то время, как он целовал ее руку. Она знала его ребенком, и теперь дружба его с Андреем, его несчастие с женой, а главное, его доброе, простое лицо расположили ее к нему. Она смотрела на него своими прекрасными, лучистыми глазами и, казалось, говорила: «я вас очень люблю, но пожалуйста не смейтесь над моими ». Обменявшись первыми фразами приветствия, они сели.
– А, и Иванушка тут, – сказал князь Андрей, указывая улыбкой на молодого странника.
– Andre! – умоляюще сказала княжна Марья.
– Il faut que vous sachiez que c"est une femme, [Знай, что это женщина,] – сказал Андрей Пьеру.
– Andre, au nom de Dieu! [Андрей, ради Бога!] – повторила княжна Марья.
Видно было, что насмешливое отношение князя Андрея к странникам и бесполезное заступничество за них княжны Марьи были привычные, установившиеся между ними отношения.
– Mais, ma bonne amie, – сказал князь Андрей, – vous devriez au contraire m"etre reconaissante de ce que j"explique a Pierre votre intimite avec ce jeune homme… [Но, мой друг, ты должна бы быть мне благодарна, что я объясняю Пьеру твою близость к этому молодому человеку.]
– Vraiment? [Правда?] – сказал Пьер любопытно и серьезно (за что особенно ему благодарна была княжна Марья) вглядываясь через очки в лицо Иванушки, который, поняв, что речь шла о нем, хитрыми глазами оглядывал всех.
Княжна Марья совершенно напрасно смутилась за своих. Они нисколько не робели. Старушка, опустив глаза, но искоса поглядывая на вошедших, опрокинув чашку вверх дном на блюдечко и положив подле обкусанный кусочек сахара, спокойно и неподвижно сидела на своем кресле, ожидая, чтобы ей предложили еще чаю. Иванушка, попивая из блюдечка, исподлобья лукавыми, женскими глазами смотрел на молодых людей.
– Где, в Киеве была? – спросил старуху князь Андрей.
– Была, отец, – отвечала словоохотливо старуха, – на самое Рожество удостоилась у угодников сообщиться святых, небесных тайн. А теперь из Колязина, отец, благодать великая открылась…
– Что ж, Иванушка с тобой?
– Я сам по себе иду, кормилец, – стараясь говорить басом, сказал Иванушка. – Только в Юхнове с Пелагеюшкой сошлись…
Пелагеюшка перебила своего товарища; ей видно хотелось рассказать то, что она видела.
– В Колязине, отец, великая благодать открылась.
– Что ж, мощи новые? – спросил князь Андрей.
– Полно, Андрей, – сказала княжна Марья. – Не рассказывай, Пелагеюшка.
– Ни… что ты, мать, отчего не рассказывать? Я его люблю. Он добрый, Богом взысканный, он мне, благодетель, рублей дал, я помню. Как была я в Киеве и говорит мне Кирюша юродивый – истинно Божий человек, зиму и лето босой ходит. Что ходишь, говорит, не по своему месту, в Колязин иди, там икона чудотворная, матушка пресвятая Богородица открылась. Я с тех слов простилась с угодниками и пошла…
Все молчали, одна странница говорила мерным голосом, втягивая в себя воздух.
– Пришла, отец мой, мне народ и говорит: благодать великая открылась, у матушки пресвятой Богородицы миро из щечки каплет…
– Ну хорошо, хорошо, после расскажешь, – краснея сказала княжна Марья.
– Позвольте у нее спросить, – сказал Пьер. – Ты сама видела? – спросил он.
– Как же, отец, сама удостоилась. Сияние такое на лике то, как свет небесный, а из щечки у матушки так и каплет, так и каплет…
– Да ведь это обман, – наивно сказал Пьер, внимательно слушавший странницу.
– Ах, отец, что говоришь! – с ужасом сказала Пелагеюшка, за защитой обращаясь к княжне Марье.
– Это обманывают народ, – повторил он.
– Господи Иисусе Христе! – крестясь сказала странница. – Ох, не говори, отец. Так то один анарал не верил, сказал: «монахи обманывают», да как сказал, так и ослеп. И приснилось ему, что приходит к нему матушка Печерская и говорит: «уверуй мне, я тебя исцелю». Вот и стал проситься: повези да повези меня к ней. Это я тебе истинную правду говорю, сама видела. Привезли его слепого прямо к ней, подошел, упал, говорит: «исцели! отдам тебе, говорит, в чем царь жаловал». Сама видела, отец, звезда в ней так и вделана. Что ж, – прозрел! Грех говорить так. Бог накажет, – поучительно обратилась она к Пьеру.
– Как же звезда то в образе очутилась? – спросил Пьер.
– В генералы и матушку произвели? – сказал князь Aндрей улыбаясь.
Пелагеюшка вдруг побледнела и всплеснула руками.
– Отец, отец, грех тебе, у тебя сын! – заговорила она, из бледности вдруг переходя в яркую краску.
– Отец, что ты сказал такое, Бог тебя прости. – Она перекрестилась. – Господи, прости его. Матушка, что ж это?… – обратилась она к княжне Марье. Она встала и чуть не плача стала собирать свою сумочку. Ей, видно, было и страшно, и стыдно, что она пользовалась благодеяниями в доме, где могли говорить это, и жалко, что надо было теперь лишиться благодеяний этого дома.
– Ну что вам за охота? – сказала княжна Марья. – Зачем вы пришли ко мне?…
– Нет, ведь я шучу, Пелагеюшка, – сказал Пьер. – Princesse, ma parole, je n"ai pas voulu l"offenser, [Княжна, я право, не хотел обидеть ее,] я так только. Ты не думай, я пошутил, – говорил он, робко улыбаясь и желая загладить свою вину. – Ведь это я, а он так, пошутил только.
Пелагеюшка остановилась недоверчиво, но в лице Пьера была такая искренность раскаяния, и князь Андрей так кротко смотрел то на Пелагеюшку, то на Пьера, что она понемногу успокоилась.

Странница успокоилась и, наведенная опять на разговор, долго потом рассказывала про отца Амфилохия, который был такой святой жизни, что от ручки его ладоном пахло, и о том, как знакомые ей монахи в последнее ее странствие в Киев дали ей ключи от пещер, и как она, взяв с собой сухарики, двое суток провела в пещерах с угодниками. «Помолюсь одному, почитаю, пойду к другому. Сосну, опять пойду приложусь; и такая, матушка, тишина, благодать такая, что и на свет Божий выходить не хочется».
Пьер внимательно и серьезно слушал ее. Князь Андрей вышел из комнаты. И вслед за ним, оставив божьих людей допивать чай, княжна Марья повела Пьера в гостиную.
– Вы очень добры, – сказала она ему.
– Ах, я право не думал оскорбить ее, я так понимаю и высоко ценю эти чувства!
Княжна Марья молча посмотрела на него и нежно улыбнулась. – Ведь я вас давно знаю и люблю как брата, – сказала она. – Как вы нашли Андрея? – спросила она поспешно, не давая ему времени сказать что нибудь в ответ на ее ласковые слова. – Он очень беспокоит меня. Здоровье его зимой лучше, но прошлой весной рана открылась, и доктор сказал, что он должен ехать лечиться. И нравственно я очень боюсь за него. Он не такой характер как мы, женщины, чтобы выстрадать и выплакать свое горе. Он внутри себя носит его. Нынче он весел и оживлен; но это ваш приезд так подействовал на него: он редко бывает таким. Ежели бы вы могли уговорить его поехать за границу! Ему нужна деятельность, а эта ровная, тихая жизнь губит его. Другие не замечают, а я вижу.
В 10 м часу официанты бросились к крыльцу, заслышав бубенчики подъезжавшего экипажа старого князя. Князь Андрей с Пьером тоже вышли на крыльцо.
– Это кто? – спросил старый князь, вылезая из кареты и угадав Пьера.
– AI очень рад! целуй, – сказал он, узнав, кто был незнакомый молодой человек.
Старый князь был в хорошем духе и обласкал Пьера.
Перед ужином князь Андрей, вернувшись назад в кабинет отца, застал старого князя в горячем споре с Пьером.
Пьер доказывал, что придет время, когда не будет больше войны. Старый князь, подтрунивая, но не сердясь, оспаривал его.
– Кровь из жил выпусти, воды налей, тогда войны не будет. Бабьи бредни, бабьи бредни, – проговорил он, но всё таки ласково потрепал Пьера по плечу, и подошел к столу, у которого князь Андрей, видимо не желая вступать в разговор, перебирал бумаги, привезенные князем из города. Старый князь подошел к нему и стал говорить о делах.
– Предводитель, Ростов граф, половины людей не доставил. Приехал в город, вздумал на обед звать, – я ему такой обед задал… А вот просмотри эту… Ну, брат, – обратился князь Николай Андреич к сыну, хлопая по плечу Пьера, – молодец твой приятель, я его полюбил! Разжигает меня. Другой и умные речи говорит, а слушать не хочется, а он и врет да разжигает меня старика. Ну идите, идите, – сказал он, – может быть приду, за ужином вашим посижу. Опять поспорю. Мою дуру, княжну Марью полюби, – прокричал он Пьеру из двери.
Пьер теперь только, в свой приезд в Лысые Горы, оценил всю силу и прелесть своей дружбы с князем Андреем. Эта прелесть выразилась не столько в его отношениях с ним самим, сколько в отношениях со всеми родными и домашними. Пьер с старым, суровым князем и с кроткой и робкой княжной Марьей, несмотря на то, что он их почти не знал, чувствовал себя сразу старым другом. Они все уже любили его. Не только княжна Марья, подкупленная его кроткими отношениями к странницам, самым лучистым взглядом смотрела на него; но маленький, годовой князь Николай, как звал дед, улыбнулся Пьеру и пошел к нему на руки. Михаил Иваныч, m lle Bourienne с радостными улыбками смотрели на него, когда он разговаривал с старым князем.
Старый князь вышел ужинать: это было очевидно для Пьера. Он был с ним оба дня его пребывания в Лысых Горах чрезвычайно ласков, и велел ему приезжать к себе.
Когда Пьер уехал и сошлись вместе все члены семьи, его стали судить, как это всегда бывает после отъезда нового человека и, как это редко бывает, все говорили про него одно хорошее.

Возвратившись в этот раз из отпуска, Ростов в первый раз почувствовал и узнал, до какой степени сильна была его связь с Денисовым и со всем полком.
Когда Ростов подъезжал к полку, он испытывал чувство подобное тому, которое он испытывал, подъезжая к Поварскому дому. Когда он увидал первого гусара в расстегнутом мундире своего полка, когда он узнал рыжего Дементьева, увидал коновязи рыжих лошадей, когда Лаврушка радостно закричал своему барину: «Граф приехал!» и лохматый Денисов, спавший на постели, выбежал из землянки, обнял его, и офицеры сошлись к приезжему, – Ростов испытывал такое же чувство, как когда его обнимала мать, отец и сестры, и слезы радости, подступившие ему к горлу, помешали ему говорить. Полк был тоже дом, и дом неизменно милый и дорогой, как и дом родительский.
Явившись к полковому командиру, получив назначение в прежний эскадрон, сходивши на дежурство и на фуражировку, войдя во все маленькие интересы полка и почувствовав себя лишенным свободы и закованным в одну узкую неизменную рамку, Ростов испытал то же успокоение, ту же опору и то же сознание того, что он здесь дома, на своем месте, которые он чувствовал и под родительским кровом. Не было этой всей безурядицы вольного света, в котором он не находил себе места и ошибался в выборах; не было Сони, с которой надо было или не надо было объясняться. Не было возможности ехать туда или не ехать туда; не было этих 24 часов суток, которые столькими различными способами можно было употребить; не было этого бесчисленного множества людей, из которых никто не был ближе, никто не был дальше; не было этих неясных и неопределенных денежных отношений с отцом, не было напоминания об ужасном проигрыше Долохову! Тут в полку всё было ясно и просто. Весь мир был разделен на два неровные отдела. Один – наш Павлоградский полк, и другой – всё остальное. И до этого остального не было никакого дела. В полку всё было известно: кто был поручик, кто ротмистр, кто хороший, кто дурной человек, и главное, – товарищ. Маркитант верит в долг, жалованье получается в треть; выдумывать и выбирать нечего, только не делай ничего такого, что считается дурным в Павлоградском полку; а пошлют, делай то, что ясно и отчетливо, определено и приказано: и всё будет хорошо.
Вступив снова в эти определенные условия полковой жизни, Ростов испытал радость и успокоение, подобные тем, которые чувствует усталый человек, ложась на отдых. Тем отраднее была в эту кампанию эта полковая жизнь Ростову, что он, после проигрыша Долохову (поступка, которого он, несмотря на все утешения родных, не мог простить себе), решился служить не как прежде, а чтобы загладить свою вину, служить хорошо и быть вполне отличным товарищем и офицером, т. е. прекрасным человеком, что представлялось столь трудным в миру, а в полку столь возможным.
Ростов, со времени своего проигрыша, решил, что он в пять лет заплатит этот долг родителям. Ему посылалось по 10 ти тысяч в год, теперь же он решился брать только две, а остальные предоставлять родителям для уплаты долга.

Армия наша после неоднократных отступлений, наступлений и сражений при Пултуске, при Прейсиш Эйлау, сосредоточивалась около Бартенштейна. Ожидали приезда государя к армии и начала новой кампании.
Павлоградский полк, находившийся в той части армии, которая была в походе 1805 года, укомплектовываясь в России, опоздал к первым действиям кампании. Он не был ни под Пултуском, ни под Прейсиш Эйлау и во второй половине кампании, присоединившись к действующей армии, был причислен к отряду Платова.
Отряд Платова действовал независимо от армии. Несколько раз павлоградцы были частями в перестрелках с неприятелем, захватили пленных и однажды отбили даже экипажи маршала Удино. В апреле месяце павлоградцы несколько недель простояли около разоренной до тла немецкой пустой деревни, не трогаясь с места.
Была ростепель, грязь, холод, реки взломало, дороги сделались непроездны; по нескольку дней не выдавали ни лошадям ни людям провианта. Так как подвоз сделался невозможен, то люди рассыпались по заброшенным пустынным деревням отыскивать картофель, но уже и того находили мало. Всё было съедено, и все жители разбежались; те, которые оставались, были хуже нищих, и отнимать у них уж было нечего, и даже мало – жалостливые солдаты часто вместо того, чтобы пользоваться от них, отдавали им свое последнее.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

прямые методы оптимизации (нулевого порядка);
градиентные методы (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-я производная-векторная величина-градиент).

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

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

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

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

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

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

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

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

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

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

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

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

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

История

См. также

Примечания

Литература

Ссылки

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

История

См. также

Напишите отзыв о статье "Оптимизация (математика)"

Примечания

Литература

Ссылки

Отрывок, характеризующий Оптимизация (математика)

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

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

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

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

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

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

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

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

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

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

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

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

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

Учебная литература

Биология-репетитор

Биология

Общая биология

Ботаника

Зоология

Жизненные ресурсы

Книга по ботанике