Файл: Золотарь, И. А. Экономико-математические методы в дорожном строительстве.pdf

Как видно из матрицы, т = 3, я= 5 и любой план должен содер­ жать т + п— 1, т. е. 3 + 5— 1 = 7 ненулевых перевозок.

Составим вначале опорный план методом северно-западного уг­ ла. В результате получаем следующую матрицу перевозок, содер­ жащую точно т + п— 1 ненулевых переменных:

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

Как видно из матрицы, она содержит меньше чем т + п— 1 нену­ левых перевозок и в данном случае всего шесть вместо необходи­ мых семи.

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

Когда же происходит последнее, то теряется ненулевая перевоз­ ка и план вырождается. В последней матрице это случилось с пере­ возкой * 1 3 = 5, которая дополнила строку (исчерпала запас мате­

риалов) и в точности удовлетворила потребность в материалах для третьего участка.

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

Тогда методом минимума по строке получаем следующий опор­ ный план:

90

перевозок — план является опорным.

Выявляя методом лестницы потенциальные клетки, найдем, что таковыми являются клетки с Хгз и Х25 при значениях A L 24= — 0,1 и ЛТ25= — 0 ,2 . Предоставляем читателю проверить справедливость этого вывода. Улучшенный план будет выражаться следующей мат­ рицей:

В этом плане потенциальной является клетка с перевозкой Хц. Второй улучшенный план примет вид:

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

91

Как показывает проверка, в этом плане потенциальных клеток нет. Все величины AL при проверке нулевых клеток оказываются положительными или равными нулю, и потому план является оп­ тимальным.

Следует учитывать, что величина е принимается малой и удов­ летворяющей условиям:

e ^ X i j для всех Xij^>0;

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

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

строительства объектов 1, 2, 3, 4, то общее время на выполнение всех работ составит 24 недели.

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

1. Находим в табл. 20 объект с минимальным временем работ ^min или Timin. В нашем случае это объект 2 с Т2 = 2 ч. Так как ми­ нимальное время относится к завершающей работе — постройке до­ рожной одежды, то ставим этот объект на последнее место по зем­ ляным работам. Нетрудно понять и смысл такого действия: после завершения на объекте 2 земляных работ работы по устройству до­ рожной одежды будут закончены в кратчайший срок (имёет место как бы минимальный период свертывания работ).

92

2.Продолжаем отыскание следующего U in или Тцпщ. В нашем примере это объекты 1 и 4, можно оперировать с любым из них. Ставим на первое место по земляным работам объект 1, характе­ ризующийся как бы минимальным временем развертывания работ.

3.Продолжая действовать таким же образом, ставим на пред­ последнее место по земляным работам объект 4. Итак, оптимальная последовательность восстановления объектов будет следующей: 1,

3, 4, 2. При этом время завершения всех работ Тк составит 21 неде­ лю (см. рис. 20) и экономия времени за счет оптимальной после­ довательности отработки объектов будет три недели.

Рис. 20. Схема к отысканию оптимальной по­ следовательности строительства объектов. (Штриховкой показан простой подразделений из-за отсутствия фронта работ)

Если приближенно принять одинаковым время перемещения между объектами, то его можно включить в величины и Г{ и тем самым учесть в Тк. Алгоритм Флада разработан и для более слож­ ных случаев (если видов работ более двух, возможно различное че­ редование работ), однако здесь эти задачи не рассматриваются.

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

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

93

Математически задача о назначении формулируется следующим образом:

Условие (V.39) означает, что величина Xi$ может быть либо ну­ лем (машина на работу не выделяется), либо единицей (машина выделяется). Условие (V.40) говорит о том, что в каждой строке и в каждом столбце распределительной матрицы может быть только

одна единица. Индекс (0) при aif в условии (V.41) означает, что

стоимостная характеристика a'lf взята из оценочной матри­ цы А0.

Из постановки задачи ясно, что решение задачи дается квадрат­ ной матрицей (п2 — матрица).

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

ответствующие оценочные характеристики аУр для фиктивных ма­ шин и работ принимаются равными нулю и тем самым исключает­ ся их влияние на целевую функцию (V.41).

Необходимо отметить, что задача о назначении есть полностью вырожденная транспортная задача. В самом деле, при любом на­ значении машины на работу всегда автоматически совпадают по­ ставки по строке со спросом по столбцу и вместо 2п— 1 мы получа­ ем всего п ненулевых значений хц. Следовательно, необходимо до­ полнить матрицу п— 1 величинами е для того, чтобы избавиться от вырожденное™. Однако такой путь решения задачи оказывается чрезмерно громоздким, и гораздо удобнее пользоваться специаль­ но разработанным Фладом методом ее решения. Он основывается на двух довольно очевидных теоремах. Первая утверждает, что ре­ шение задачи не изменится, если прибавить к любому столбцу или

строке матрицы с оценками ajP некоторую константу или вы­ честь ее.

Таким путем достаточное число величин a \ f сводится к нулю, что дает общее минимальное решение с условным итогом 0.

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

Как уже отмечалось, для п2-матрицы возможно п\ вариантов решения. Разработанный Фладом алгоритм позволяет за небольшое число шагов получить оптимальное решение задачи.

94