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

при округлении пользоваться правилами арифметики, то мож­ но получить целочисленные значения Х\ = 4 и х2 = 3. Точка 4-— —3 также лежит вне зоны допустимых значений переменных. Це­ лочисленные оптимальные значения переменных надо искать среди всех возможных целочисленных значений, лежащих внут­ ри многоугольника, построенного ограничениями. На рис.. 13 такие точки выделены черным цветом. Если линию X i х2 передвигать параллельно самой себе, то внутри зоны возмож­ ных значений максимум этой линии пройдет через целочислен­ ные точки Х\ — 2; х 2— 3 и Х\ = 3; х 2 — 2, х { + х 2= 5 (птах).

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

§ 6.5. Метод ветвей и границ

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

Смысл метода заключается в том, что определяется нижняя

переменному нецелочисленное решение в базисном оптимальном плане. При дальнейшем разбивании получается дерево ветвле­ ний.

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

Одним из первых среди комбинаторных методов разработан алгоритм Лэнд и Дойг, смысл которого заключается в следую­

88

делей в задачах математического программирования.— В сб. «Техника и техно­ логия месторождении полезных ископаемых. Вып. VII, М., «Недра», 1969.

4

Г Л А В А V I I

МЕТОД СТАТИСТИЧЕСКИХ ИСПЫТАНИЙ (МОНТЕ-КАРЛО)

§ 7.1. Статистическое моделирование

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

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

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

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

91

— (5.5.11). При решении задачи задаются разные варианты де­ терминированных параметров, случайные величины моделируют­ ся в соответствии с законами их распределения. Решение такой задачи имитирует процесс производства, при котором достига­ ется максимум (5.5.8).

Но метод Монте-Карло может применяться и как чисто вы­ числительный, например, для вычисления определенного инте­ грала [2 ], для нахождения экстремума некоторых нелинейных функций (случайный поиск), для определения параметров кор­ реляционных формул и т. д. Основой метода является аппарат случайных чисел.

§ 7.2. Равномерная случайная последовательность чисел

Случайные процессы с известными параметрами могут быть реализованы в виде случайной последовательности чисел. Слу­

где п — количество чисел в последовательности, зависящее от числа знаков после запятой. Если после запятой идет один знак, т. е. g = 0; 0,1,..., 0,9; 1, то п = 11 и, следовательно, веро­

11 ’

Р = _1_ и т. д.

101

Дифференциальный и интегральный законы распределения РСП (0,1) приведены на рис. 15.

Естественно, что

i-i

что видно из определения вероятности Р (7.2.1) и графика 156).

92