пТяг 1 Начиная о источника О, отметить знаком + каждую дугу (О,/) потоком а вершины / и О пометить знаком * . а нулевым^.! Рассмотреть любой узел /, помеченный знаком * . Поставить 4- на каждой дуге (j,k) с нулевым потоком, исходящей из вершины /, вершина k не помечена, и пометить вершину k знаком * . Поставить як - на каждой дуге {k,j) с ненулевым потоком, входящей в вершину /, гпи вершина k не помечена, и пометить вершину k знаком * . В конце шага 2 залеркнуть знак * вершины / (это указывает на то, что вершина была просмотрена). ,

Шаг 3. Повторять операции шага 2, пока не будет помечена вершина p-f 1 или все помеченные вершины не будут просмотрены. Как только проставляется метка вершины происходит прорыв, так как обнаруживается путь, увели-

чивающий поток из вершины О в вершину р+1. Этот путь можно определить в явном виде о помощью знаков + или - , проставленных на дугах, просматривая вершины в обратном направлении, начиная с вершины p-fl. Добавить единичный поток по каждой дуге, помеченной знаком + , уменьшить на единицу поток по каждой дуге, помеченной знаком - . Вернуться к шагу 1. Если по окончании шага 2 вершина р+1 остается непомеченной, текущее решение определяет максимальный поток в сети.

Задача определения кратчайшего пути на сети

- е

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

Пусть сц - длина каждой дуги и имеется путь из Sh в Sk

г = [io = Sh, iu it = Sk] (7.109)

длиной

()-ici.ti-iiV- (7.110)

Необходимо найти такой путь г, для которого /(r)-min.

Пусть Sh - источник единичной интенсивности, Sk - ее сток, остальные вершины - нейтральные; дуги имеют неограниченные пропускные способности, а стоимость перевозок равна длине соответствующей дуги.

Поток в такой сети должен удовлетворять соотношениям

1 при i = Sh,

Z-Vy -Z-ji = I - 1 при t = s ; (7.111)

. 0 при i Ф Sh, i Ф Sk.

Необходимо найти такой поток, который удовлетворял бы (7.111) и минимизировал функционал

Сцхц. (7.112)

Таким образом, задача (7.109), (7.110) сводится к задаче (7.111), (7.112).

Пусть Cj - кратчайшее расстояние между вершиной Sh и вер-Щиной /, причем Cs== 0. Необходимо найти с^.

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

Cj = min {а + Cij}. (7.113)

Таким образом, кратчайшее расстояние до вершины / определяется после нахождения кратчайшего расстояния до каждой предыдущей вершины 1, если i и / - смежные вершины, соединенные, дугой.

Рассмотрим алгоритм определения кратчайшего пути.

Шаг 1. Для вершины to = Sh расстояние Cs== Ct = 0. Величина ct включает расстояние до вершины i, которое используется для определения ближайшей вершины у .

Шаг 2. Пусть t = (о. 2.1. Вычислить расстояние Cj - a для всех вершин /. 2.2. Если Сг j > Cj - Ci для всех /, то между вершинами i и / не существует более короткого пути. Если i = Sk, перейти к п. 2.4; если нет, принять i = i + I и перейти к п.2.1. 2.3. Если csj < Cj - d, вычислить Cj, используя формулу с/ = = ct -\- сц, а затем определить с,- по формуле (7.113). Для i = j заменить Cj И Ci на с^ и с'Если i = Sk, перейти к п. 2.4, если нет, принять i = t -f 1 и

перейти к п.2.1. 2.4. Если значение с,- в п.2.3 изменилось, перейти к шагу 2, если нет, перейти к шагу 3.

Ш а г 3. Полученные значения с,- определяют кратчайшее расстояние между вершинами о и /= I,Sk. Последняя дуга (ij,/) в пути должна удовлетворять условию

После определения вершины ii предпоследняя вершина is должна удовлетворять условию

Ci, = Ci,-C4i,.

Процесс продолжается, пока не будет достигнута вершина io = н.

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

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

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

Каждой операции соответствует дуга ориентированного графа. Дуга (t, /) соединяет вершину i с вершиной /ив вершину i входят только дуги, соответствующие непосредственно предшествующим дугам данной операции. Часто в граф вводятся фиктивные дуги.

Вершины сетевого графика называются событиями.

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

Сетевой график не содержит контуров.

Пусть задан сетевой график G={V, L) с множеством событий V н мгтожеством операций L, в котором содержится одно событие - !;сток (в него не входит ни одна дуга) и одно событие - сток (!1 псго не выходит ни одна дуга). Такие события называются соответственно начальным и конечным событием.

Все события графа G нумеруются таким образом, чтобы для каждой дуги (i, j)L соблюдалось условие Kj-

Пусть для события iV имеем Гн(0 и Tjx{i)-соответственно наиболее раннее и наиболее позднее время его возможного наступления, допускающее своевременное окончание всего проекта.

Наиболее ранние сроки наступления событий определяются следующим образом:

Ги(/)= max {7н(0-ft,/)}, (7.114)

где t{i, j) -время выполнения работы (операции), соответствующей дуге (i, /) eL. Например (рис. 7.4),

Тп{9) = max {Гн(3) + (3,9), Гн(4) -f/(4,9), Гн(5)-Ь f(5,9)} = = max {2 -f 6,6 + 3,7 -Ь 2} = 9.

Наиболее поздние сроки наступления событий определяются следующим образом:

7 (О = min {Г„(/) - t(i, j)}. (7.115)

i:(i,3)et

/в f3) = 2 0 (8) 18) = 17

rj4) =6(2)-(l0)r (10) =9 r(15) =12(g . 0 r(21) =20

H.fS) = 7 (б) * r (26) = 24

Рис. 7.4. Определение сроков наступления событий: <i - ранних; б - поздних

V28 2ео 225

Например,

Г„(15) =min{r (18) -(15,18), Г„(21) -(15,21), Г„(26) -(15,26)} =min {17 - 4. 20 - 8, 24 -6} = 12.

Увеличение наиболее поздних сроков окончания всего проекта 7к( ) на t единиц времени приведет к увеличению наиболее поздних сроков всех событий также на / единиц. Наиболее ранний срок Гн(/) события / соответствует наибольшей длине пути от начального события (истока) к событию /, а разность Тк{п)-?,((/) - наибольшей длине пути от события / к конечному событию п.

Если Тк{п)Тн(п), то Г„(/)>ГнШ для всех событий /. Часто требуется определить максимально возможные длительности операций при условии своевременного окончания выполнения всего проекта. Поскольку любая операция (i,/) может начаться не ранее Гн(0 и должна окончиться не позднее 7к(/), то задержки выполнения всего проекта не будет, если на операцию (i, /)eL выделено Tk{J)-Тн{{) единиц времени. Поэтому при выполнении операции (i, /) можно допустить максимальную задержку Tk{j) - T{i)-t{i,j)0. Величина Rn{i, /) =Гк(/)-Гн(0-(t, /) называется полным резервом времени операции (i, j).

Допустим, что на последующие операции (после операции (i, /)) не накладываются временные ограничения. Тогда на выполнение операции (t, /) можно выделить не более Гн(/)-7h(i) единиц времени.

Величина Rc{i, J)=Th{j)-7н(0-t(i, }) называется свободным резервом времени операции {i, j). Он равен максимальной задержке выполнения операции (i, /), не влияющей на выполнение последующих операций.

При отсутствии дополнительных временных ограничений на любую операцию проекта на выполнение операции (i, /) можно выделить не более 7н(/)-7к(0 единиц времени.

Величина Rnii, /) = 7н(/)-Тк(1)-t{i, j) называется независимым резервом, времени операции (f,/). При Ra{i,j)<.0 любая задержка в выполнении операции (i, /) приведет к дополнительным ограничениям на выполнение других операций.

Для любой операции (i, /)

Ru{i,i)>Rc{i,i)>Ru(i,i).

Операция называется критической, если любая задержка ее выполнения приводит к задержке выполнения всего проекта. Для критической операции Rn(i, j) =0.

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

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

Если Тн{п) -Тк(п), то каждая операция пути наибольшей дли-

Т (п) от начального к конечному событию сетевого графика является критической.

плимер Пусть задан сетевой график (рис. 7.5). (h->(f)-

Пути ИЗ начального события в конечное имеют \

следующие длины:

(l,2)-(2,5)-3-f 6 = 9;

(1,3)-1(3,5)-5-f 5= 10;

(1,4) - (4,5) 5 -f 2 = 7. Рис. 7.5. Сетевой график вы-

Путь (1,3)-(3,5) имеет наибольшую длину и яв- полнения проекта

ляется критическим.

При выполнении некритических операций путей (1,2)-(2,5) и (1,4)-(4,5) можно допустить некоторые задержки, не приводящие к превышению времени завершения проекта, равному 10 ед.

В случае неопределенности длительности выполнения операций для определения критического пути существует метод PERT (Pro-grar voluation Review Technique). Ожидаемое время выполнения операции (t, /) вычисляется на основании трех временных оценок по формуле

Aij 4 Cij

где Ац, Bij, Cij - соответственно оптимистическая, реалистическая и пессимистическая оценки времени выполнения. Дисперсия времени выполнения операции (t, /) определяется так:

в этом случае Тн{{) и TK{i) означают соответственно ожидаемый наиболее ранний и наиболее поздний сроки выполнения события i, Т^(п)-ожидаемый наиболее ранний срок завершения всего проекта.

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

Критический путь определяется следующим образом:

начиная с истока, для которого 7н(0)=0, по формуле (7.114) определяются ранние сроки наступления всех событий /, включая событие-сток, т. е. Ти{п);

начиная с последнего события-стока по формуле (7.115) определяются поздние сроки наступления всех событий i, включая событие-сток, т. е. f к (0);

операция (t, /) принадлежит критическому пути, если выполняются следующие условия:

Тп{1) =Ы1); ТнЦ) - r (i) = Г (/) - Гк(0 = t{i,j),

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

7.3. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ И КОМБИНАТОРНАЯ ОПТИМИЗАЦИЯ

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

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

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

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

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

п

Есл- (7.П6)

при условиях

Е ClijXj < а,о, i=\,m; (7.117)

Хз>0, /=1,п; (7.118)

Xj - целые, / = ТЛ ik<n). (7.119)

Рели k=ti, модель (7.116) -(7.119) описывает полностью целочисленную'задачу линейного программирования, если /г<п, то - частично целочисленную.

В зависимости от содержания задачи оптимизация целевой функции (7.116) может соответствовать максимизации или минимизации.

Модель задачи целочисленного программирования (7.116) - (7.119) отличается от модели задачи линейного программирования только наличием дополнительного ограничения (7.119). Это ограничение приводит к тому, что максимальное значение целевой функции задачи целочисленного программирования меньше значения целевой функции соответствующей задачи линейного программирования.

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

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

Часто исследователи прибегают к приближенному результату решения, полученного путем округления до целых значений результатов решения задачи линейного программирования (7.116) - (7.118). При округлении обычно нарушается допустимость решения, т. е. не выполняются ограничения вида (7. 117).

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

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

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

Vs-bS 260 . . 229

ся за конечное число итераций, но это число может быть очень большим.

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

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

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

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

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

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

при ограничениях

ECjXj (7.120)

Е atjXj = Яго, i = 1, m; (7.121)

ATjO, /= l,n; (7.122)

все Xj - целые. (7.123)

Для полностью целочисленных задач математик Гомори разработал следующий метод. Вначале рассматривается выпуклое множество допустимых решений, определенное линейными огра-ничениями и условиями неотрицательности переменных исходной задачи (7.121) -(7.122), и'находится экстремальная точка этого множества. Если такое решение оказывается нецелочисленным, то добавляют ограничение, отсекающее текущую экстремальную точку и уменьшающее выпуклое множество, но не отсекающее ни одной экстремальной точки выпуклой оболочки множества допустимых целочисленных решений. Процедура повторяется, т. е. строится такое число дополнительных ограничений, пока экстремальная точка усеченного выпуклого множества допустимых решений

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

Это дополнительное линейное ограничение, которому должно удовлетворять любое решение, допустимое по условиям (7.121) - (7 123), строится следующим образом.

Просуммируем по всем i правые и левые части условий (7.121):

£ол = ао, (7.124)

где

Оз = Z Оо = Ц аго.

1=1 г=1

Из соотношения (7.124) и условий (7.122), (7.123) следует

t[aj]Xjao, (7.125)

где Id}] - целая часть числа flj, т. е. наибольшее число, меньшее н авное действительному числу flj. 1 . Поскольку выражение в правой части (7.125) -целое число, тО

:[G,],<[flo] (7.126).

или

Е[ з]з + У== Ы, (7.127)

где и целое число.

Если к ограничениям (7.121) добавить ограничение (7.127), названное отсечением в целых частях, исходная задача останется целочисленной.

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

I: i-dj) Xj + x = -do, (7.128)

где dj и do удовлетворяют соотношениям:

[Oj] + dj = Uj и [Go] + do = Co; 0dj<l; 0<do<l;

/ = l,n.

Алгоритм отсекающих плоскостей содержит три шага.

Шаг 1. Решить задачу линейного программирования (7.120)-(7.122), условия (7.123) отбрасываются.

Шаг 2. Если полученное решение является целочисленным, прекратить вычисления, так как оно является решением исходной задачи (7.120)-(7.123), если же нет, выбрать одну из дробных базисных переменных и составить отсечение Б дробных частях (7.128) из ограничения, содержащего эту базисную Р^менную Б текущем оптимальном решении задачи линейного программиро-

Шаг 3. Расширить исходную задачу линейного программирования полученным новым ограничением (отсечением). Решить расширенную задачу и перейти к шагу 2.

/+8* 231

Пусть на последней итерации Xs - базисная переменная в i-й строке сим-шекс-та блицы:

Xs + 2] = о. {7Л29)

где / - множество индексов небазисных переменных; оо - имеет дробное значение; pij - коэффициенты при небазисных переменныхв i-й строке. На шаге 2 отсечение в дробных частях:

У! i-dis)Xi + 2/ = -do, (7.130)

где dij--дробная часть pij, а do - дробная часть ао.

Текущее решение задачи линейного программирования не удовлетворяет новому ограничению (7.130), так как у = -do (отрицательно). При расширении задачи соотношением (7.130) и требовании у^О текущее решение задачи линейного программирования становится недопустимым, т. е. дробное решение отсекается и область допустимых решений сужается. Отсюда следует, что на шаге 3 значение целевой функции может только уменьшиться, а не возрасти.

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

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

Метод ветвей и границ. Пусть требуется решить задачу (7.120) - (7.123), к которой добавлены ограничения вида

Mi < Xj < Nj, j = 1, п. (7.131)

Метод ветвей и границ базируется на следующей идее. Введем целое число К, удовлетворяющее соотношение

MjK<Nj-l.

Оптимальное решение задачи (7.120) - (7.123), (7.131) должно удовлетворять одному из двух линейных ограничений:

1) Xj>K+ 1; (7.132)

2) XjK. (7.133) Допустим, решение задачи линейного программирования

(7.120) -(7.122), (7.131) содержите, = 1-.,

Решим две задачи линейного программирования (7.120) - (7.122), одна из которых дополнена условием 2XiNi, а другая- условием MiXil. Пусть решение каждой из этих задач целочисленно, т. е. выполняются условия (7.123). Оптимальным решением исходной задачи целочисленного программирования является то решение, при котором значение целевой функции (7.120) будет большим.

Приведем алгоритм метода ветвей и границ.

На первой итерации алгоритма решаем исходную задачу линейного программирования (7.120) -(7.122), (7.131). Значение целевой функции (7.120)