Методы оптимальных решений

Классическая теория оптимизации. Функция скаляризации Чебышева. Критерий Парето-оптимальность. Марковские процессы принятия решений. Метод изменения ограничений. Алгоритм нахождения кратчайшего пути. Процесс построения минимального остовного дерева сети.

Рубрика Экономико-математическое моделирование
Вид контрольная работа
Язык русский
Дата добавления 18.01.2015
Размер файла 182,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Санкт-Петербургский государственный политехнический университет» (ФГБОУ ВПО «СПбГПУ»)

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

«Санкт-Петербургский государственный политехнический университет» в г. Череповце (ИМИТ «СПбГПУ»)

Кафедра экономики

Контрольная работа

Методы оптимальных решений

Выполнил студент группы з.623

Жохов Артем Валерьевич

Руководитель

Лысова Наталия Викторовна

г. Череповец 2015

1. Многокритериальные задачи. Парето-оптимальность

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

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

Определение.

Задача многокритериальной оптимизации формулируется следующим образом:

где это k ( ) целевых функций.

Векторы решений относятся к не пустой области определения S.

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

Эталонные точки

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

идеальная точка, Y I,

утопическая точка, Y U,

надир ( надир ), Y N.

В некоторых случаях эти точки могут быть решениями.

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

Точка надир определяется как вектор:

Утопическую точку Y U вычисляют на основе идеальной:

где > 0, U - единичный вектор.

Критерии оптимальности. Критерий Парето.

Вектор решения называется оптимальным по Парето если не существует такого, что для всех и для хотя бы одного i. Множество оптимальных по Парето решений можно обозначить как P ( S ). Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимальный по Парето. Множество оптимальных по Парето целевых векторов можно обозначить как P ( Z ).

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

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

Множество оптимальных по Парето решений также называют Парето-фронтом ( англ. Pareto-frontier ).

Лексикографический порядок.

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

Отношение лексикографического порядка <lex между векторами и выполняется, если A Q < B Q, где. То есть, первые q компонент вектора меньше компоненты вектора, а компоненты q + 1 - уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

Вектор является лексикографическим решением, если не существует вектора такого, что

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

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

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

Скаляризация.

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

Пусть F - функция скаляризации, что превращает векторную функцию на скалярную. Если F сохраняет упорядоченность по Парето, то есть, если для произвольных выполняется:

тогда решение, что минимизирует F на X является решением по Парето.

Если F сохраняет отношение порядка < в, то есть, если для произвольных выполняется:

тогда решение, что минимизирует F на X является слабым по Парето.

Если F непрерывна, и единственная точка минимума F на X, тогда является решением по Парето.

Взвешенная сумма

Приведенная функция F 1 сохраняет упорядоченность по Парето для w > 0. Поэтому решения, минимизирующие F 1 на X для произвольных w > 0 являются оптимальными по Парето. Однако F 1 не сохраняет упорядоченность по Парето для а сохраняет лишь отношение < и поэтому решения, минимизирующие F 1 на X для являются слабыми по Парето.

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

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

Функция скаляризации Чебышева.

Взвешенная функция скаляризации Чебышева сохраняет отношения < и поэтому минимум является слабым по Парето.

Метод изменения ограничений.

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

при условиях:

Значение могут рассматриваться как допустимые уровни для

Методы решения. Интерактивность.

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

Эволюционные методы.

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

2. Марковские процессы принятия решений

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

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

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

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

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

Такими примерами СФ являются: колебания напряжения в электрической цепи, скорость движения автомобиля на участке дороги с ограничением скорости, шероховатость поверхности детали на определенном участке и т.д.

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

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

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

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

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

Рис. 1. Схема процесса без последействия

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

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

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

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

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

Марковский СП называется однородным, если переходные вероятности остаются постоянными в ходе процесса.

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

1. Имеется совокупность переходных вероятностей в виде матрицы:

.

2. Имеется вектор начальных вероятностей

описывающий начальное состояние системы.

Матрица (2) называется переходной матрицей (матрицей перехода). Элементами матрицы являются вероятности перехода из i-го в j-е состояние за один шаг процесса.

Переходная матрица (2) обладает следующими свойствами:

a)

б)

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

Рис. 2. Ориентированный взвешенный граф

Вершины графа обозначают состояние , а дуги- переходные вероятности.

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

1. Невозвратное множество (рис. 3).

Рис. 3. Невозвратное множество

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

2. Возвратное множество (рис. 4).

Рис. 4. Возвратное множество

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

3. Эргодическое множество (рис. 5).

Рис. 5. Эргодическое множество

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

4. Поглощающее множество (рис. 6)

Рис. 6. Поглощающее множество

При попадании системы в это множество процесс заканчивается.

Кроме описанной выше классификации множеств различают состояния системы:

а) существенное состояние (рис.7): возможны переходы из в и обратно.

Рис. 7. Существенное состояние

б) несущественное состояние (рис. 8): возможен переход из в , но невозможен обратный.

Рис. 8. Несущественное состояние

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

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

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

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

Рис. 9. Классификация марковских процессов

3. Классическая теория оптимизации

Классическая теория оптимизации базируется на аппарате дифференциального исчисления.

На рис.1 легко заметить, что первая производная функции f(x) (тангенс угла наклона касательной к графику функции) равна 0 во всех ее экстремальных точках. Однако это условие выполняется и в точках перегиба и седловых точках (x5).

Т.о. xi, являющиеся решениями уравнения f'(x) = 0, - это либо точки экстремума либо точки перегиба. Условие f'(x) = 0 называют необходимым условием наличия экстремума.

Исследование производных высших порядков позволяет убедиться, что точка xi - экстремум и более того, является она точкой максимума или минимума. Для этого необходимо найти вторую производную f”(x) и в нее подставить значения xi, полученные при решении уравнения f'(x) = 0:

- если f”(xi) > 0 - то в точке xi минимум функции;

- если f”(xi) < 0 - то в точке xi максимум функции;

- если f”(xi) = 0 - то необходимо исследовать следующие производные. В этом случае, если первые (n-1) производных равны 0 и f(n)(xi) <> 0, то в точке xi функция имеет:

- точку перегиба, если n - нечетное;

- минимум, если n - четное и f(n)(xi) > 0;

- максимум, если n - четное и f(n)(xi) < 0.

Эти условия называются достаточными.

Таблица Примеры определения экстремумов функции

№ п/п

Функция

Экстремумы

График функции

1

y = f(x) = x2

f'(x) = 2x

2x = 0

x0 = 0 - точка экстремума или перегиба.

f”(x) = 2 > 2 > 0

x0 = 0 - точка минимума.

2

y = f(x) = x3 - 2x2 + x + 1

f'(x) = 3x2 - 4x + 1

3x2 - 4x + 1 = 0

x1 = 1/3 и x2 = 1 - точки экстремума или перегиба.

f”(x) = 6x - 4 >

f”(x1) = 6 * 1/3 - 4 = -2

f”(x1) < 0

x1 = 0 - точка максимума;

f”(x2) = 6 * 1 - 4 = 2

f”(x2) > 0

x2 = 0 - точка минимума.

3

y = f(x) = 2x4

f'(x) = 8x3

8x3 = 0

x0 = 0 - точка экстремума или перегиба.

f”(x) = 24x2

f”(x0) = 24 * 02 = 0

f(3)(x) = 48x

f(3)(x0)=48 * 0 = 0.

f(4)(x) = 48

48 > 0 и n = 4 - четное

x0 = 0 - точка минимума.

4

y = f(x) = 2x3

f'(x) = 6x2

6x2 = 0

x0 = 0 - точка экстремума или перегиба.

f”(x) = 12x

f”(x0) = 12 * 02 = 0.

f(3)(x) = 12

n = 3 - нечетное

x0 = 0 - точка перегиба.

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

Например, для функции из 2-ого примера f(x) = x3 - 2x2 + x + 1 требуется найти максимум при ограничениях x ? -2 и x ? 3. Тогда помимо точек экстремума x1 = 1/3 (f(x1) = 1.15) и x2 = 1 (f(x2) = 1), проверяем значения функции в точках x3 = -2 (f(x3) = -17) и x4 = 3 (f(x4) = 13). Таким образом, искомое оптимальное значение функции в точке x4 = 3.

4. Графы. Построение минимального остовного дерева. Задача определения кратчайшего пути

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

Построение минимального остовного дерева сети.

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

Рассмотрим процедуру построения минимального остовного дерева.

Введем обозначения:

X={ x1, x2, …, xn } - множество узлов сети;

Ck - связное множество узлов сети, соединенных алгоритмом после выполнения k-й итерации;

- множество узлов сети, не соединенных с узлами множества Ck после выполнения k-й итерации;

Алгоритм построения минимального остовного дерева сети:

1. Взять произвольный узел сети xi, C1={xi}, = X\{xi};

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

C1, C2={ xi, xj }, = X\{ xi, xj };

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

За конечное число шагов будут обработаны все узлы сети и построено минимальное остовное дерево

Cn=X, =f.

Задача нахождения кратчайшего пути.

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

Введем следующие обозначения:

x1 - исходный узел;

xn - узел назначения;

dij - расстояние на сети между смежными узлами xi и xj;

Uj - кратчайшее расстояние от узла x1 до узла xj, U1=0.

Алгоритм нахождения кратчайшего пути состоит в последовательном нахождении значений Uj для каждого узла от исходного узла до узла назначения. Значение Uj для каждого узла рассчитывается по формуле

={ Ui + dij }

Процедура заканчивается, когда получено значение Un для узла назначения.

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

Сетевое планирование

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

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

Фиктивная работа - это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.

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

Путь - это любая непрерывная последовательность (цепь) работ и событий.

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

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

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

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

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

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

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

Из исходного события 1 вычеркивают все исходящие из него работы, на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2.

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

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

Рассмотрим прямой проход.

tiр.н - ранний срок начала всех операций, выходящих из события i.

Если i = 0, то t0 p. н = 0.

tjр.н - ранний срок начала всех операций, входящих в j.

tjр.н = max { tip.н + tij } для всех (i, j),

где tij - продолжительность операции (i, j).

Различают два вида резервов времени: полный резерв (rп) и свободный резерв (rсв).

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

r п = tijп.н - tip.н.

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

rсвij = tjp.н - tiр.н - tij.

Используя результаты вычислений при прямом и обратном проходах, можно определить операции критического пути. Операция (i, j) принадлежит критическому пути, если она удовлетворяет условиям:

tiр.н = tiп.о,

tjр.н = tjп.о,

tjр.н - tiр.н = tjп.о - tiп.о = ti j.

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

Определив зависимость "затраты - продолжительность", для всех операций сети принимают нормальную продолжительность.

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

На следующем этапе рассматривается возможность сокращения продолжительности работ.

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

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

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

скаляризация парето оптимальность алгоритм

Список используемых источников и литературы

1. В.Д. Ногин. Принятие решений при многих критериях. Учебно-методическое пособие, 2007 - 104 с.

2. Парето-оптимальные решения многокритериальных задач. Подинвоский В.В., Ногин В.Д, 2006 - 256с.

3. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления.2009 - 120 с.

4. Вентцель Е.С. Элементы динамического программирования. 2005 - 176 с.

5. Щетинин Е.Ю., «Математические методы оптимизации»,2003 -254с

6. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Под ред. И. В. Красикова. 2005 - 1296 с

Размещено на Allbest.ur


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

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

    контрольная работа [1,2 M], добавлен 11.06.2011

  • Принятие решений в условиях неопределенности. Критерий Лапласа и принцип недостаточного основания. Критерий крайнего пессимизма. Требования критерия Гурвица. Нахождение минимального риска по Сэвиджу. Выбор оптимальной стратегии при принятии решения.

    контрольная работа [34,3 K], добавлен 01.02.2012

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

    контрольная работа [57,1 K], добавлен 04.10.2010

  • Теория статистических решений как поиск оптимального недетерминированного поведения в условиях неопределенности. Критерии принятия решений Лапласа, минимаксный, Сэвиджа, Гурвица и различия между ними. Математические средства описания неопределенностей.

    контрольная работа [66,0 K], добавлен 25.03.2009

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

    контрольная работа [437,2 K], добавлен 14.02.2011

  • Применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Описание метода Минти. Выбор среды разработки. Система программирования Delphi. Параметры программного продукта.

    курсовая работа [961,9 K], добавлен 31.05.2012

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

    контрольная работа [106,4 K], добавлен 09.07.2014

  • Аналитические и численные методы безусловной оптимизации. Метод исключения и метод множителей Лагранжа (ММЛ). Метод Эйлера – классический метод решения задач безусловной оптимизации. Классическая задача условной оптимизации. О практическом смысле ММЛ.

    реферат [387,0 K], добавлен 17.11.2010

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

    учебное пособие [2,0 M], добавлен 15.06.2015

  • Рассмотрение методов северо-западного пути, наименьшего элемента и аппроксимации Фогеля. Определение минимального значения целевой функции. Система ограничений в каноническом виде. Поиск наименьшего значения линейной функции графическим методом.

    контрольная работа [463,9 K], добавлен 18.03.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.