Файл: Шепелев, И. Г. Математические методы планирования и управления в строительстве конспект лекций.pdf

нейного программирования не может быть решена методом ли­ нейного программирования.

Поставленная здесь задача с разрывной целевой функцией может быть преобразована в задачу целочисленного програм­ мирования. Для этого вводят дополнительные переменные г/у, и целевую функцию (6 .2 .1 1 ) приводят к виду

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

•*11 = М ц У у ,

отсюда у,-= — тогда целевая функция примет вид

■УП Му

и ее решают как обычную задачу линейного программирова­ ния. Существуют специальные методы приближенного решения задачи № 4, например, метод Балинского i[7], который не тре­ бует приведения задачи к целочисленной.

82

§ 6.3. Методы решения задач дискретного программирования

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

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

получают нецелочисленное решение, которое после округляют до целых чисел. Также тривиально иногда поступают и при решении задачи типа № 1 и № 2 , причем в задаче № 1 получен­ ные результаты, отличные от целых чисел, заданных ограниче­ нием, оставляют в оптимальном плане. Такое нарушение целочисленности часто оправдывается тем, что за получение целочис­

в связи с потерей оптимальности функционала. Так автор ,[4] утверждает: «Не боясь парадоксов, скажу, что потери от нецелочисленности могут быть меньше, чем потери от достижения целочисленного результата», подразумевая под последним умень­ шение значения функционала в целочисленном оптимальном плане.

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

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

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

численного программирования.

Более корректными методами являются методы, основанные на принципах отсечения нецелочисленных решений и методы с применением комбинаторики. Наибольшее распространение по­ лучили методы отсечения Гомори и методы «ветвей и границ». При решении ряда задач применяются приближенные методы решения целочисленных задач.

§6.4. Принцип метода отсечения

ипервый алгоритм Гомори

Сущность метода отсечения заключается в том, что в цело­ численной задаче линейного программирования вначале полу­ чают обычное оптимальное решение. Если оптимальный план будет целочисленным, то задача решена. Если в оптимальном плане имеются нецелочисленные переменные, которые по усло­ виям задачи должны быть целочисленными, то производится правильное отсечение нецелочисленной части решения. Кратко рассмотрим алгоритм Гомори в изложении ([7]. Иллюстрацион­ ный пример взят из этого же источника.

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

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

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

84

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

Задача разрешима

Рис. 12. Блок-схема первого алгоритма Гомери

85

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

Далее эту таблицу оптимизируют. Из оптимального плана выбывает в первой итерации дополнительная строка, а выбран­ ная строка становится целочисленной, но первое решение не обязательно будет оптимальным. Необходимо провести столько преобразований, сколько нужно для получения оптимального плана. Если в этом плане имеются нецелочисленные перемен­ ные, выбираем новую строку, к которой строим правильное от­ сечение согласно формуле (6.4.1), оптимизируем полученную таблицу и т. д. Блок-схема первого алгоритма Гомори приведе­ на на рис. 1 2 .

Решение задачи целочисленного программирования методом

то можно построить геометрическую схему ее решения, изобра­ женную на рис. 13. Предельные линии ограничений (6.4.3) и (6.4.5) образуют выпуклый многоугольник, на гранях которого и следует искать оптимальное значение Х\ и Хг. На рисунке видно, что решению соответствует линия

x t х 2 = 7

Как видим, получены нецелочисленные решения. Если ок­ руглить значения Xj и.хг до целых чисел, то эти «псевдооптимальные» ответы не будут соответствовать ограничениям зада­ чи. Допустим, путем простого отбрасывания дробной части мы округлили Х\ и х2 и получили Х\ — 4 и Х2 = 2, т. е. точка 4—2 не лежит внутри зоны допустимых значений переменных. Если

86