Задачи ЛП и методы их решения

69

5.3. Сетевая модель задачи и ее решение

Изобразим моменты i=1,2,..,N+1 в виде вершин графа, а пары (i,j) в виде ориентированных дуг этого графа (основные понятия теории графов и терминология приведены в Приложении). Проставим на дугах (i,j) соответствующие стоимости аренды Cij и будем считать их длинами этих дуг. Тогда произвольный план (1,i1 ,i2 ,… ,ik , N + 1) можно

представить как путь из вершины 1 в вершину N+1, а стоимость плана – длиной этого пути. Наоборот, каждый путь указанного вида является планом аренды. Оптимальным планом аренды будет кратчайший путь из 1 в N+1. Таким образом, задача об аренде оборудования является частным случаем известной задачи о нахождении кратчайшего пути (маршрута) [2- 6].

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

Найдём путь методом потенциалов [9,16,19] для бесконтурных сетей.

На 1-м этапе находим потенциалы — числа Vi для каждой вершины i, означающие

минимум берётся по всем дугам (i, j ), выходящим из вершины i .

На втором этапе, начиная с вершины i =1, находятся и выделяются дуги (i, j ), на которых потенциал начала дуги Vi в точности равен сумме потенциала конца дуги Vj и стоимости дуги Cij. Выделенные таким образом дуги дают кратчайший путь (пути), то есть оптимальные планы аренды. Потенциал V1 начальной вершины будет равен длине кратчайшего пути, то есть стоимости оптимального плана аренды.

Пример 2. . Пусть при N=6 стоимости аренды Cij заданы в таблице:

70

Определим потенциал каждого месяца:

V5 = min (C5,6+V6;C5,7 +V7) = min (51+53;101) = C5,7+V7 = 101

V4 = min (C4,5+V5;C4,6+V6;C4,7+V7) = min (49+101;98+53;148) = C4,7+V7 = 148

V3 = min (C3,4+V4;C3,5+V5;C3,6+V6;C3,7+V7) = min (48+148;95+101;147+53;189) = C3,7 +V7= 189

V2 = min (C2,3+V3;C2,4+V4;C2,5+V5;C2,6+V6;C2,7+V7) = min (50+189; 96+148; 146+101; 198+53;

247) = C2,3 + V3 = 239

V1 = min (C1,2+V2;C1,3+V3;C1,4+V4;C1,5+V5;C1,6+V6;C1,7+V7) = min (49+239; 99+189; 145+148;

197+101; 244+53; 296) = C1,2 + V2 или С1,3 + V3 = 288.

Получаем сеть следующего вида:

Найдем оптимальный план аренды оборудования.

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

Анализируя полученную модель, можно сделать вывод, что существует два оптимальных плана аренды: a) (1, 2, 3, 7) = 1мес + 1 мес + 4 мес и b) (1, 3, 7) = 2 мес + 4 мес со стоимостью Cmin = V1 =288.

5.4. Табличный метод решения задачи

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

71

последовательно снизу вверх. Клетки (i,j), для которых достигается минимум в формуле

таблицы будет не менее одной выделенной клетки.

По выделенным клеткам находим оптимальные планы аренды. Для этого в первой строчке найдем выделенную клетку (1, i1) с номером выделенного столбца i1 . Затем найдем в строке i1 выделенную клетку (i1, i2) с номером выделенного столбца i2 и так далее. Получим оптимальный план аренды (1,i1 ,i2 ,…,ik ,N +1). Другие планы, если они есть, находятся аналогично.

Рассмотрим снова пример 2 и получим следующую таблицу.

В этой таблице выделены следующие клетки:

1.(6,7),.так как V6 = C6,7+V7 = 53;

2.(5.7), так как V5 = C5,7+V7 = 101

3.(4,7),.так как V4 = C4,7+V7 = 148

4.(3,7), так как V3 = C3,7 +V7= 189

5.(2,3), так как V2 = C2,3 + V3 = 239

6.(1,2) и (1,3), так как V1 = C1,2 + V2 = С1,3 + V3 = 288.

Последовательность выделенных клеток (1,2), (2,3), (3,7) дает оптимальный план аренды (1, 2, 3, 7), а последовательность выделенных клеток (1, 3) и (3,7) дает оптимальный план аренды (1, 3, 7). Стоимость оптимальных планов равна 288 у.е. (первая строка, дополнительный столбец).

72

6. СЕТЕВОЕ ПЛАНИРОВАНИЕ

6.1. Предмет сетевого планирования

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

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

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

Управление большими проектами, включающими до нескольких десятков тысяч работ, является сложным делом и требует научного, т.е. математического подхода, а также автоматизации расчётов. Исторически именно необходимость в 1957-58 годах в США реализации крупных проектов, в частности, скорейшего создания ракеты "Полярис" и достаточная мощность электронно-вычислительных машин в эти годы привели к созданию первых систем управления проектами CPM, PERT, основанных на методе критического пути (Critical Path Method) – центральном методе сетевого планирования. Развитие идей сетевого планирования шло на фоне бурного развития в 50-х, 60-х годах исследования операций (и стало возможным благодаря этому) – раздела математики, изучающего принципы выбора управляющих решений оперативного характера в производственной, военной, бытовой деятельности. Таким образом,

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

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

6.2. Структурное планирование

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

Студентам для изучения основных понятий и методов сетевого планирования рекомендуется учебник [17]. Построение сетевого графика обычно рассматривается только в математической литературе, например, в [9], и поэтому подробно рассмотрено в данных методических указаниях.

73

Предшествование работ. События. Списки предшествования

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

Определение. Работа А предшествует работе В, если работа А должна быть закончена до начала работы В. ♦

Например, работа «построить стены» предшествует работе «оштукатурить стены». Условно "А предшествует В" можно записать так: А<В.

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

Для отношения предшествования работ, очевидно, выполнены два свойства, аналогичные свойствам для неравенств вещественных чисел.

если работа А предшествует работе В, (A<B), а ра-

(*)бота В предшествует работе С (B<C), то и работа А предшествует работе С (A<C) (свойство транзитивности);

работа не может предшествовать сама себе, в част-

(**)ности, последовательно предшествующие друг другу работы не могут составлять замкнутую це-

почку вида A<B<…<C<A ( свойство а н т и р е ф л е к с и в н о с т и ).

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

I.Работы, являющиеся также предшествующими для некоторой предшествующей С. Например, если A<B<C, то A – I вида.

II. Работы, между которыми и работой С нет промежуточных.

Определение. Работы вида II называются непосредственно предшествующими (для данной).

♦

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

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

75

Таблицы 2,3 яснее показывают взаимосвязь работ проекта, чем таблица 1. Например, из таблицы 3 следует, что работу E можно начать сразу после окончания двух работ A, G, т.е. после окончания последней по времени. В сетевом планировании такая зависимость одного множества работ (последующих) от другого множества работ (непосредственно им предшествующих), называется событием.

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

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

Определение. Началом проекта называется факт, необходимый для начала "первых" работ проекта – тех, у которых нет предшествующих.

Концом проекта называется факт окончания "последних" работ проекта – тех, которые не являются предшествующими ни для каких других работ. ♦

В примере 1 первыми работами являются B, D, H, последними – C, E, I. Во всех таблицах напротив B, D, H стоит прочерк – символ пустого множества, а работы C, E, I ни разу не встречаются в правой колонке.

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

В примере 1 событиями являются {—}, {D, F, H}, {D, H}, {A, G}, {B}, {D}, а также конец проекта {C, E, H}. Очевидно, событие {—} есть начало проекта.

Между событиями устанавливаются отношения предшествования, как и межу работами.

Определение. Событие I предшествует событию J , если I должно наступить не позже события J. ♦

Например, очевидно, что событие {D, H} должно наступить не позднее события {D, F, H}, так как после {D, H} нужно ещё ждать окончания работы F. Если F уже было закончено до наступления {D, H}, то события {D, H} и {D, F, H} наступают одновременно.

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

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

Сети. Сетевой график проекта

Математическим, формальным представлением объектов, между которыми попарно установлены некоторые связи, является граф [9,17,18,21]. Сети являются частным случаем графов. Ограничимся случаем, необходимым в сетевом планировании.

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

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

76

шины. В дальнейшем дугу будем записать в виде упорядоченной пары (a, b), где a – начало дуги, b – конец дуги.

(vk−1,vk ) являются дугами. Графически путь представляет непрерывную направленную линию из дуг, согласованную с направлениями стрелок ("движения по стрелкам"). Если v0 = vk , т.е. если начало пути совпадает с концом пути, то путь называется контуром. Цепочкой из вершины v0 в вершину vk называется последовательность из различных вершин, в которой дугами являются (v0 ,v1) или (v1,v0 ) , (v1,v2 ) или (v2 ,v1) , и т.д. Таким обра-

( a, b, c, a ) – цикл

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

Определение. Конечная совокупность вершин и дуг (и их графическое изображение) называется сетью, если выполняются условия:

а) связности;

б) отсутствия петель (начало и конец дуги различны);

в) отсутствие параллельных дуг. ♦

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

Замечание. В литературе встречается также термин ациклическая сеть.

Сеть на рис.1 не является безконтурной, т.к. есть контур ( b, d, f, c, b).

Н у м е р а ц и я вершин сети – это сопоставление вершинам номеров – натуральных чисел, при этом различным вершинам сопоставляются различные номера.

Определение. Нумерация называется правильной, если

а) номера идут подряд: 1, 2, …, m, где m – число вершин;

б) номер начала дуги меньше номера конца дуги, т.е. все дуги записываются в виде (i, j) , где i < j . ♦

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

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

77

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

2.Присвоим найденной вершине текущий номер. Первый раз таким номером является m – число вершин сети.

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

Замечание. 1. Если не удаётся найти вершину в шаге 1, то в сети есть контур и правильная нумерация невозможна, так что алгоритм Форда является проверкой, будет ли сеть безконтурной.

2. Правильных нумераций в сети может быть несколько.

Пример 2.

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

Определение. Вершина I предшествует вершине J, если из I в J существует хотя бы один путь, т.е. есть путь, в котором I встречается раньше, чем J .

Дуга (i, j) предшествует дуге (l,k) , если существует хотя бы один путь вида (i, j,...,l,k) , т.е. путь, первой дугой которого является (i, j) , и последней — (l,k) .

♦

Отношение предшествования дуг и вершин безконтурной сети также обладает свойствами

(*) и (**) (транзитивностью и антирефлексивностью).

Сетевой график. Аналогия между работами, событиями с одной стороны и дугами, вершинами с другой стороны указывает на возможность представления проекта в виде безконтурной сети. Такое представление называется с е т е в ы м графиком. Есть два вида сетевых графиков:

(1 и 2, 4 и 5 можно поменять местами)

1-й вид: Работам проекта соответствуют дуги, а событиям – вершины.

2-й вид: Работам проекта соответствуют вершины, события при этом не имеют чётко выраженного представления.

78

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

H C

Рис. 3. (Дуги поставлены в точном соответствии с таблицей 3.)

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

Итак, работы проекта соответствуют дугам, а события – вершинам сетевого графика.

Определение. Сетевым графиком проекта называется безконтурная сеть со следующими свойствами:

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

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

3)Работы, события проекта, предшествуют друг другу тогда и только тогда, когда соответствующие им дуги, вершины предшествуют друг другу. ♦

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

Пример 3. Проект состоит из двух независимых работ A, B.

Событий, очевидно, также два: {—} – начало проекта и {A, B} – конец проекта. Сетевой график должен был бы выглядеть так:

с определением сети. Поэтому правильный сетевой график должен выглядеть так: