Парадигма развития науки (стр. 57 )

неотрицательны), рис. 23.8.

Pис. 23.8

2. Алгоритм формирования плана. Полученные ре­зультаты не являются конструктивными (они отвечают предположению

τvk = const и не дают рекомендаций по выбору наилучшего плана проведения работ), однако по­зволяют интерпретировать исходную задачу планирова­ния как задачу отыскания наилучшего варианта расста­новки столбцов матрицы || τkv ||, что должно облегчить применение здесь метода динамического программирования (или методов, сход­ных с ним по идее). Усло­вия для этого следующие: рассматривается N-шаго­вый процесс планирова­ния; содержанием оче­редного шага является размещение того или ино­го столбца (как единого целого) на определенной позиции; перед началом очередного шага возможны только N состояний процесса, причем параметр со­стояния скалярный (номер столбца).

Рассмотрим время Т как функцию только τvk (v =1, 2,…, N,

k=1,…, М), имея в виду возможность исполь­зования найденных решений. Оценка Т в виде (23.28), обозначаемая в дальнейшем как, обладает рядом осо­бенностей: в общем случае представляет собой линейную комбинацию величин τvk, т. е.

где cvk—целочисленные коэффициенты; каждое значе­ние отвечает заданному порядку работ, который, в силу условия а), вполне определяется порядком проведения их первого этапа (т. е. принятыми τv1, v=1,…,N); следова­тельно, τvk является однозначно определенной функцией τv1. Учитывая эти замечания, получаем

Возможные наборы значений τv1 (v=1,…,N) образуются при перестановках N элементов первой строки матрицы || τkv ||, и множество всех таких перестановок объединяет N! элементов πj(j= 1,…,N!).

Обозначим через Р множество всех πj, допустимых по исходным ограничениям в), г). Возникает задача:

найти такие πj Р, которые доставят min.

Ее решение (однозначное или неоднозначное) есть τ*11,..., τ*N1, Т*, где

Поиск τ*v1, Т* осложняется тем, что Р является дискретным (точечным) множеством, и процесс переходов от одного элемента πj к другому (с целью улуч­шения ) должен быть как-то организован.

Пусть из совокупности τv1 (v = 1,…,N) выбрана и за­фиксирована переменная τN1 (на последнее место постав­лена одна из N работ). Если в этой ситуации найти ми­нимум по остальным τv1 (v = 1,…,N —1), допустив воз­можность перестановок соответствующих работ без нарушений условий в), г), то его величина будет опреде­ляться принятым τN1, поскольку

Здесь от τN1 зависит неявно и второе слагаемое правой части, так что

Предполагая функцию N-1(τN1) известной, можно искать Т* в виде

Таким образом, осуществляется переход к функцио­нальному уравнению

(23.24)

и основной вопрос заключается теперь в том, чтобы его решить относительно τv1 (v=1,…, N). Тем самым подтверж­дается принципиальная возможность применения метода динамического программирования в рассматриваемой задаче. Непосредственное использование оценки (23.23) в решении (23.24) связано с необходимостью составлять в каждом случае перечень номеров kN-p

(p = 0, 1, ..., N—2), выявлять зависимость v-1 от параметра состоя­ния, получать промежуточные v и т. д. В этом смысле более экономным и удобным для практической реализации представляется алгоритм непосредственного пошаго­вого формирования оптимальной последовательности работ, сводящийся к анализу промежуточных состояний и наилучших продолжений процесса планирования.

Основные этапы решения задачи

Вводится предположение о том, что (N—1)-ю по­зицию занимает первая (по исходной нумерации) ра­бота, и в рамках этого предположения исследуются варианты формирования двух последних позиций бу­дущего плана («первая и вторая работы», «первая и третья работы», ..., «первая и N - я работы»); для каж­дого такого варианта определяются wvk = τv,k-1—τv-1,k, ∆tv-1,k, Θvk при v = N, k = 2,…, M (см. выше), проверяется выполнение условий в), г) (при проверке в) используются приближенные оптимистиче­ские показатели, вычисляемые для идеализированного случая, когда все ∆tv-1,k, Θvk

(v = 2,…, N—1; k = 2,…, M) положены равными нулю; по мере накопления информации достоверность этих показателей растет, а в конечном счете они переходят в v) и оцениваются величины

Вводится предположение о том, что (N—1)-ю по­зицию занимает вторая (по исходной нумерации) ра­бота, и в рамках этого предположения исследуются варианты формирования двух последних позиций пла­на («вторая и первая работы», «вторая и третья рабо­ты», ... «вторая и N-я работы»); для каждого вариан­та ищутся wvk, ∆tv-1,k, Θvk

(v = N; k=2,…, M), проверяются условия в), г) и оцениваются Т.

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

Вводится предположение о том, что (N—2)-ю по­зицию занимает первая (по исходной нумерации) ра­бота. В рамках этого предположения исследуются варианты формирования трех последних позиций бу­дущего плана, причем (N—1)-я и N-я позиции (т. е. продолжение процесса) формируются здесь как еди­ное целое на основе использования данных первой таблицы результатов (см. 23.29). Определяются ∆tv-1,k, Θvk (v = N, N-1; k=2,…, M), проверяются условия в), г) (по оптимическим показателям) и оцениваются новые величины

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

Вводится предположение о том, что (N—3)-ю по­зицию занимает первая работа и исследуются вариан­ты формирования четырех последних позиций буду­щего плана. Набор работ, попадающих на

(N—2)-ю, (N—1)-ю, N-ю позиции, выбирается из второй табли­цы результатов, после чего проводятся стандартные проверки условий в), г), вычисляются и, наконец, составляется третья таблица результатов. Переход к новым предположениям продолжается до тех пор, по­ка не будут составлены и оценены последовательно­сти из N работ.

Общее количество исследуемых вариантов в рас­смотренном алгоритме не превысит ~N3 вместо N! при полном переборе (реальный выигрыш получается для N>5).