Алгоритмы по математике
Методическое пособие - Математика и статистика
Другие методички по предмету Математика и статистика
га (i=n), попадаем в начало планового периода, начинают прямой ход: задавая t0 и длительность планового периода, находим и строим последовательность оптимальных управлений, начиная с первого года и заканчивая последним.
Замечание: используя полученные расчетные таблицы для задачи об оптимальном распределении капиталовложений и о замене оборудования, можно получить решение с изменением (уменьшением) исходных данных (количества филиалов, выделенных средств или планового периода соответственно). Это так называемый принцип погружения метода динамического программирования.
III. Пусть спрос потребителей на продукцию составляет на 1-й, 2-й, 3-й этапы d1, d2, d3 единиц соответственно. К началу первого этапа на складе имеется y1 единицы продукции. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1, h2, h3. Затраты на производство хj единиц на j-ом этапе определяются функцией , . Для нахождения оптимального количества производимой на каждом этапе продукции, чтобы заявки были удовлетворены, а общие затраты на производство и хранение за все три этапа были наименьшими, решение проводят по алгоритму.
Алгоритм решения задачи о производстве и хранении продукции
1. Составляется таблица значений функции затрат на производство
, где
2. Выполняется обратный ход: составляются функциональные уравнения
минимальные затраты за первые k месяцев, ограничения по величине запаса к концу k-го месяца
, балансовое уравнение
,
а из него получают ограничении
а) для k=1: составляются ограничения
,
а также таблица значений функции
б) для k=2: в зависимости от значений переменой
составляются ограничения
,
а также вспомогательные таблицы значений функции
Для каждого значения выбирается минимальное значение и соответствующее ему значение ;
в) для k=3: составляются ограничения
, (причем ),
а также таблица значений функции
3. Выполняется прямой ход:
а) для определяют , из балансового уравнения
выражают ;
б) зная , из таблицы значений определяют , а из балансового уравнения
выражают ;
) зная , из таблицы значений определяют ;
г) суммарные затраты за весь период .
Задачи планирования на сетях
Граф геометрически представляет собой множество точек, называемых вершинами, соединенных линиями: а) направленными, которые называются дугами и обозначаются стрелками, или б) ненаправленными, которые называются ребрами.
Граф без петель можно задать матрицей инциденций A, строки которой соответствуют вершинам, а столбцы - дугам, причем элементы матрицы A определяются по формуле
Граф можно задать матрицей смежности вершин S, строки и столбцы которой соответствуют вершинам графа, причем элементы матрицы sij равны числу дуг/ребер, идущих из хi в хj.
Графический способ упорядочения вершин (алгоритм Фалкерсона)
1. Находятся вершины графа, в которые не входит ни одна дуга. Такие вершины образуют первую группу.
. Вершины и выходящие из них дуги установленной группы исключаются из дальнейшего рассмотрения.
. Устанавливается следующая группа вершин, в которые не входит ни одна дуга.
. Если процесс упорядочения не окончен, то переход п. 2.
. В полученном графе, изоморфном исходному, перенумеровываются вершины.
Алгоритм решения задачи о максимальном потоке
. Построить начальный поток
2. На основе заданной сети построить новую сеть:
а) каждая дуга, для которой остаётся в новой сети с первоначальной rij;
б) каждая дуга, для которой , заменяется на две: одна - того же направления с пропускной способностью rij-; а вторая - противоположенного направления с пропускной способностью .
. Если в новой сети можно найти ненулевой поток из I в S, то этот поток прибавляется к начальному. В результате получается новый поток и переходят к п. 2. Если ненулевой поток найти невозможно, то поток максимальной мощности построен.
Алгоритм расчета параметров сетевого графика
1) Изобразить события сетевого графика четырехсекторными кругами;
) перемещаясь по сетевому графику от истока к стоку по возрастанию номеров событий, найти все ранние сроки наступления событий по формулам:
(исток) и , где
3) перемещаясь по сетевому графику от стока к истоку по мере убывания номеров событий, найти поздние сроки наступления событий
(сток) и ,
4) определить резерв времени каждого события ;
) выделить критический путь - последовательность работ и событий, не имеющих резервов времени;
) вычислить свободный резерв времени и полный резерв времени каждой работы .