Файл: Баженов, Ю. М. Перспективы применения математических методов в технологии сборного железобетона.pdf

Гла в а V.

ОПТИМАЛЬНОЕ ПЛАНИРОВАНИЕ

Ѵ.1. Основные понятия. Общая методика решения за­ дач.

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

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

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

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

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

160

ограничения обязательно условие неотрицательности переменных.

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

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

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

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

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

Уравнение целевой функции L

П

(V.1)

Система ограничений по ресурсам

П

(V.2)

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

Рассмотрим составление математической модели ли­ нейного программирования на примере весьма распрост­ раненной транспортной задачи:

Надо перевезти строительный раствор с нескольких растворных узлов к нескольким строительным пло­ щадкам.

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

Примем обозначения:

щадке; Сіі— расстояние от /-того растворного узла до /-той строительной

площадки; х ц — количество раствора, перевозимое с /-того растворного узла на

У-ую строительную площадку.

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

<•=1 /=1

Для случая т —2 и м = 3 можно составить таблицу:

Целевая функция

ных перевозок, которым соответствуют отрицательные значения хг>

Для успешного решения задачи большое значение имеет правильный выбор исходных данных. К ним от­ носятся: удельные затраты материальных и трудовых ресурсов, стоимость выполненных работ, расстояние про­ бега транспортных средств, имеющиеся запасы материа­ лов, объемы подлежащих выполнению работ и др. Под­ готовка исходных данных весьма трудоемка и требует использования многочисленных нормативных и справоч­ ных материалов. Например, подготовка исходных дан­ ных по затратам на перевозку из 100 пунктов отправле­ ния в 100 пунктов назначения (т. е. 10 000 нормативных величин) занимает около 100 чел.-дней, а при увеличе­ нии числа пунктов отправления и получения грузов в 2,5 раза трудоемкость возрастает уже в б раз. Поэтому для подготовки исходных данных для подобных задач желательно использовать электронные вычислительные машины.

Расчет математических моделей выполняется по оп­ ределенному набору правил — а л г о р и т м у . Методы решения задач линейного программирования делятся на точные и приближенные. Точные методы содержат в составе алгоритма признак, по которому можно судить, что полученное решение является оптимальным и не может быть улучшено. Приближенные методы позволя­ ют решать обширные по размерам задачи в короткие

сроки, но не содержат доказательства оптимальности

решения.

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

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

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

первая — составление исходного плана (нахождение одного из возможных — базисных решений), для чего применяют простые приемы заполнения таблиц или при­ ближенные методы решения;

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

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

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

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

Решение задачи на ЭВМ включает:

составление машинной программы для расчета по имеющемуся алгоритму;

164

запись в определенном порядке исходных данных; нанесение исходных данных на перфокарты или пер­

фоленты и проверка правильности перфораций; введение данных и программы в ЭВМ и проведение

расчета; расшифровку результатов расчета.

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

Практика применения методов математического мо­ делирования в народном хозяйстве показала, что за счет принятия оптимальных решений можно получить эко­ номию в размере 5—20% .

V.2. Решение задач линейного программирования симплексным методом. Рассмотрим решение задач сим­ плексным методом на конкретном примере, опустив во­ просы теории и математических доказательств, с кото­ рыми можно познакомиться в обширной литературе по линейному программированию [10, 15, 30, 64, 65, 81], поскольку для практического использования метода не обязательно знать теорию. Начав с общей постановки задачи, проведем ее последовательный анализ вплоть до получения окончательного решения.

Пример Ѵ.1. На полигоне для строительства зданий могут из­ готовляться четыре разных вида конструкций. Изготовление арма­ турного каркаса и самих конструкций требует определенных тру­ дозатрат, ресурсы которых ограничены. На изготовление конст­ рукций расходуется различное количество бетонной смеси. Для ускорения твердения используется пропаривание, причем расход па­ ра для разных изделий различен. Возможности производства бетон­ ной смеси и мощности паросиловой установки также ограничены

(табл. Ѵ.1).

Требуется определить, какие конструкции и в каком количестве

165