Итерационные методы

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

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

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

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

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

Математический аппарат сетевых моделей базируется на теории графов. Графом называется совокупность двух ко­нечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами. Если рассматриваемые пары вершин являются упорядоченными, т.е. на каждом ребре задается направле­ние, то граф называется ориентированным, в противном случае – неориентированным. Последовательность неповто­ряющихся ребер, ведущая от некоторой вершины к другой, образует путь. Граф называется связным, если для любых двух его вершин существует путь, их соединяющий; в про­тивном случае граф называется несвязным. В экономике чаще всего используются два вида графов: дерево и сеть. Дерево представляет собой связный граф без циклов, имею­щий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями. Сеть – это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть».

В экономических исследованиях сетевые модели возни­кают при моделировании экономических процессов методами сетевого планирования и управления (СПУ).

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

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

Основные понятия СМ: событие, работа и путь. На рисунке 2 графически представлена СМ, состоящая из 11 событий и 16 работ, продолжительность выполнения которых указана над работами.

Работа характеризует материальное действие, требующее использования ресурсов, или логическое, требующее лишь взаимосвязи событий. При графическом представлении ра­бота изображается стрелкой, которая соединяет два события. Она обозначается парой заключенных в скобки чисел (i, j), где i – номер события, из которого работа выходит, а j – номер со­бытия, в которое она входит. Работа не может начаться рань­ше, чем свершится событие, из которого она выходит. Каж­дая работа имеет определенную продолжительность t (i, j). Например, запись t (2, 5) = 4 означает, что работа (2, 5) имеет продолжительность 4 единицы. К работам относятся также такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой; такие работы называются фиктивными и на графике изображаются пунктирными стрелками (работа (6, 9)).

Рис. 2. Сетевая модель

Событиями называются результаты выполнения одной или нескольких работ. Они не имеют протяженности во времени. Событие свершается в тот момент, когда оканчи­вается последняя из работ, входящая в него. События обо­значаются одним числом и при графическом представле­нии СМ изображаются кружком (или иной геометрической фигурой), внутри которого проставляется его порядковый номер (i = 1, 2,..., N). В СМ имеется начальное событие (с номером 1), из которого работы только выходят, и конечное событие (с номером N), в которое работы только входят.

Путь – это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины, например, в модели, показанной на рисунке 2, путями являются L₁ = (1, 2, 3, 7, 10, 11), L₂ = (1, 2, 4, 6, 11) и др. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называют критическим и обозначают L _кр, а его продолжительность – t _кр. Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.

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

1. События правильно пронумерованы, т.е. для каждой работы (i, j) i < j (рис. 3, работы (4, 3) и (3, 2)). При невыполнении этого требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем:

нумерация событий начинается с исходного события, ко­торому присваивается № 1;

из исходного события вычеркивают все исходящие из не­го работы (стрелки), и на оставшейся сети находят событие, в которое не входит ни одна работа, ему и присваивают № 2;

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

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

2.Отсутствуют тупиковые события (кроме завершающего), т.е. такие, за которыми не следует хотя бы одна работа (событие 5);

3. Отсутствуют события (кроме исходного), которым не предшествует хотя бы одна работа (событие 7);

4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие событие с ним же самим (см. путь (2, 4, 3)).

Рис. 3. Примеры ошибок при построении сетевой модели

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