В.1 Математическая модель — это математическое представление реальности.

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

Классификация математических моделей используемых на практике:

1. По способу описания:

• Описательные (неформализованные);

• Формализованные (математические выражения).

2. В зависимости от используемого математического аппарата:

• Статические и динамически;

• Детерминированные и вероятностные;

• Дискретные и непрерывные;

• Аналитические и численные.

Статистическая- описывает поведение модели в определённый момент времени.

Динамическая- описывает поведение модели изменяющейся с течением времени.

Детерминированные – описывают процессы, в которых не учитываются случайные факторы.

Вероятностные – отражают случайные процессы.

Дискретные описывают процессы с дискретными переменными (непрерывными).

Аналитические – модели в виде логических условий.

Численные – отражают явления с сохранением их логической структуры и последовательностью протекания во времени.

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

Различают пассивное и активное стохастическое программирование.

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

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

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

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

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

Многоэтапные (динамич.) задачи по мере получения информации о развивающемся процессе имеют возможность неоднократно корректировать решения. Идею динамического программирования предложил Беллман.

В.3 Один из классификационных признаков делит оптимизационные задачи на два класса: 1)задачи безусловной оптимизации(без ограничений);

2)Задачи условной оптимизации (с ограничениями).

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

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

• В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:

  • если и  — выпуклые функции, то такую задачу называют задачей выпуклого программирования;

• если , то имеют дело с задачейцелочисленного (дискретного) программирования.

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

Формально: в виде целевой функции

;

могут быть ограничения;

на переменные накладываются требования неотрицательности.

Задача без ограничений – задача безусловной оптимизации, с ограничениями – условной.

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

Множество допустимых решений – область допустимых решений.

Оптимальное значение целевой функции - max/min значение из области допустимых решений.

Допустимое решение оптимальное, если оно доставляет ЦФ максимально/минимальное значение.

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

Классификация методов математического программирования:

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

2. Нелинейное: целевая функция и ограничения могут быть нелинейными функциями; 

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

4. Динамическое программирование: для отыскания оптимального решения планируемая операция разбивается на ряд этапов и планирование осуществляется последовательно от этапа к этапу; 

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

6. Стохастическое линейное программирование: коэффициенты при ц.ф. и ограничениях являются случайными величинами.

7. Геометрическое: задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области, задачи раскроя материала.

8. Задачи теории массового обслуживания: анализ и исследование явлений, возникающих в системах обслуживания. Минимум времени ожидания, минимум средней длины очереди.

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

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

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

1) Замена некоторых критериев ограничениями вида ≤ или ≥. Например, минимизация стоимости , может быть заменена ограничением вида , где A максимально допустимая стоимость.

2) Свертка критериев. Создается один глобальный скалярный критерий, целевая функция которого является некоторой функцией от исходных целевых функций.

3) Ранжирование критериев. Критерии ранжируются по степени важности.

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

Подходы 1) и 2) приводят к однокритериальной задаче. Подход 3) приводит к задаче с упорядоченными критериями. Подход 4) приводит к задаче с независимыми критериями.

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

В задаче с независимыми критериями требуется найти множество эффективных решений. Эффективное решение лучше любого другого допустимого решения хотя бы по одному критерию либо не хуже по всем критериям. Множество эффективных решений также называется множеством Парето.

В.7Деление пополам — раздвоенность, последовательное деление на две части, не связанные между собой. Служит для образования классификации элементов.

Метод перебора по сетке - простейший из методов поиска значений функций по какому-либо из критериев сравнения (на максимум, на минимум, на определённую константу).

Метод золотого сечения (Фибоначчи) — метод поиска значений функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации.

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

В.8Классификация методов многомерной оптимизации:

1. Метод нулевого порядка – при выборе направления спуска требует вычисления только значения функции (Метод Гаусса-Зейдаля, метод Хукка-Дживса, алгоритм Розенброта, Пауэла).

2. Методы первого порядка – требуют вычисления точного либо приближённого градиента функции (градиентные, сопряжённых градиентов, метод Флетчера-Ривза).

3. Методы второго порядка – требуют вычисления значения как градиента, так и матрицы.

4. Методы с переменной метрикой – занимает место между методами 1-го и 2-го порядка.