Математическая модель транспортной задачи.

Пусть хij – количество груза, перевозимого с i-го в j-й пункт.

Целевая функция:

Система ограничений:

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

Сбалансированная ТЗ:

Несбалансированная ТЗ:

Для сбалансированной ТЗ ограничения принимают вид равенств, то есть получаем m+n ограничений, в которых все переменные линейно зависимы. В результате допустимое решение сбалансированной ТЗ может быть получено, если заполнять клетки транспортной таблицы таким образом, чтобы сумма перевозок в каждой строке должна быть равна запасам ai, а сумма перевозок в каждом столбце равна соответствующей заявке вj. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной.

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

29 НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ — раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями.

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

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

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

30 НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ — раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями.

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ — раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.

31 БЕЛЛМАНА ПРИНЦИП ОПТИМАЛЬНОСТИ [Bellman’s optimality principle] — важнейшее положение динамического программирования, которое гласит: оптимальное поведение в задачах динамического программирования обладает тем свойством, что каковы бы ни были первоначальное состояние и решение (т. е. “управление”), последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения. Этот принцип можно выразить и рассуждая от противного: если не использовать наилучшим образом то, чем мы располагаем сейчас, то и в дальнейшем не удастся наилучшим образом распорядиться тем, что мы могли бы иметь.

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

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

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

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

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

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

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

Ряды динамики включает два обязательных элемента:

1) период времени, за который или по состоянию на который приводятся цифровые значения (показатель времени t);

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

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

1) форме представления уровней - ряды абсолютных, относительных или средних величин;

2) интервал времени или расстоянию между уровнями- равномерные или неравномерные (полные и неполные);

3) По наличию основной тенденции изучаемого процесса- стационарные и нестационарные ряды;

4) Показателю времени - моментные и интервальные.

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

Методы сглаживания временных рядов делятся на две основные группы:

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

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

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

35 Сетевое планирование в условиях неопределенности.

Продолжительность выполнения работ часто трудно задать точно и потому в практической работе вместо одного числа (детерминированная оценка) задаются две оценки минимальная и максимальная. Минимальная (оптимистическая) оценка tmin(i,j) характеризует продолжительность выполнения работы при наиболее благоприятных обстоятельствах, а максимальная (пессимистическая) tmin(i,j) при наиболее неблагоприятных. Продолжительность работы в этом случае рассматривается, как случайная величина, которая в результате реализации может принять любое значение в заданном интервале. Такие оценки называются вероятностными (случайными), и их ожидаемое значение tox оценивается по формуле (при бета-распределении плотности вероятности): tож(i,j)=(3tmin (i,j) + 2t max(i,j)): 5.

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

S2 (i,j) = (t max (i,j) t min (i,j) 2 :5 2 = = 0.04 ( t max (i,j) t min (i,j)2.

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

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

1. определить вероятность того, что продолжительность критического пути tкр не превысит заданного директивного уровня Т;

2. определить максимальный срок выполнения всего комплекса работ Т при заданном уровне вероятности р.

Первая задача решается на основе интеграла вероятностей Лапласа Ф(г) использованием формулы: P (t kp < T) = 0,5 + 0,5 Ф(z), где нормированное отклонение случайной величины: z = (Т - tKp)/S Kp; SKp среднее квадратическое отклонение, вычисляемое как корень квадратный из дисперсии продолжительности критического пути.

Соответствие между z и симметричным интегралом вероятностей приведено в табл. 2. Более точно соответствие между этими величинами (когда z вычисляется более чем с одним знаком в дробной части) можно найти в специальной статистической литературе. При достаточно большой полученной величине вероятности (более 0,8) можно с высокой степенью уверенности предполагать своевременность выполнения всего комплекса работ.

Для решения второй задачи используется формула:

Т = t ож (Lkp )+ z *S kp

Таблица 2. Фрагмент таблицы стандартного нормального распределения

zФzzФz0,10,07971,50,86640,20,15851,60,89040,30,23581,70,91040,40,31081,80,92810,50,38291,90,95450,60,45152,00,96430,70,51612,10,97220,80,57632,20,97860,90,63192,30,98361,00,68272,40,98761,10,72872,50,99071,20,76992,60,99311,30,80642,70,99491,40,83852,80,9963. Кроме описанного способа расчета сетей с детерминированной структурой и вероятностными оценками продолжительности выполнения работ, используется метод статистических испытаний (метод Монте-Карло). В соответствии с ним на вычислительной технике многократно моделируется продолжительность выполнения работ и рассчитывается на основе этого основные характеристики сетевой модели. Большой объем испытаний позволяет более точно выявить закономерность моделируемой сети.

37 Основные задачи анализа и моделирования временных рядов. Формирование уровней ряда определяют закономерности трех основных типов - инерция тенденции, инерция взаимосвязи между последовательными уровнями ряда и инерция взаимосвязи между исследуемым показателем и показателями-факторами. Соответственно этому различают задачи анализа и моделирования: а) тенденций; б) взаимосвязи между последовательными уровнями ряда; в) причинных взаимодействий между результативным показателем и показателями-факторами. Первая из них решается с помощью методов компонентного анализа, вторая — с помощью адаптивных методов и моделей, третья - на основе эконометрического моделирования, базирующегося на методах корреляционно-регрессионного анализа.

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

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

2. Предварительный анализ исходных временных рядов и формирование набора моделей прогнозирования.

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