Материал: 1620

B1, B2, B3, ... , Bn,

подавших заявки соответственно на b1, b2, b3, ... , bn единиц товара (груза).

Предполагается, что сумма всех заявок равна сумме всех запасов:

Известна сто мость Cij перевозки единицы товара от каждого

отправлен я Аi в j-й пункт назначения Вj (i=1,2,3,...,m; j=1,2,3,...,n). Неотр цательные переменные х11, х12,..., хmn должны удовлетворять следующим условиям:

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

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

Суммарная стоимость всех перевозок, т.е. сумма величин хij, умноженных на соответствующие стоимости Сij , должна быть

2.Суммарное количество грузаД, доставляемое в каждый пункт изо

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

-пункты отправления и назначения; -запасы, имеющиеся в пунктах отправления; -заявки, поданные пунктами назначения;

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

31

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

Решение транспортной задачи начинается с нахождения опорного плана.

План называется опорным, если в нем отличны от нуля не более r=m+n–1 базисных перевозок хij, а остальные перевозки равны нулю (m – кол чество строк транспортной таблицы; n – количество

столбцу

Обозначим ui –Апотенциалы столбцов, а vj – потенциалы строк транспортной та лицы. Тогда сумма потенциалов в базисных клетках должна быть равна стоимости перевозок (условие 1), а для свободных клеток эта сумма должна ыть меньше или равна стоимости

перевозок (условие 2):

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

Один из видов распределительных задач связан с отысканием оптимальной последовательности строительства объектов. меется п объектов, фронт работы на которых открыт. На каждом из объектов требуется выполнить вначале земляные работы, а затем устроить дорожную одежду. Известно время, требуемое на выполнение этих работ. Предполагается, что имеется возможность начать работы с любого объекта. Будем полагать, что расстояние между объектами невелико и затраты времени на пepeмещение малы по сравнению с временем работы и потому могут не учитываться. В теории

32

распределительных задач доказывается, что общее число возможных последовательностей строительства объектов равно числу перестановок из п по одному, т.е. n! Алгоритм, разработанный

и смысл такого действия: после завершения на объекте земляных работ работы по устройству дорожной одежды будут закончены в кратчайш й срок ( меет место как бы минимальный период свертыван я работ).

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

1.Все запасы должны быть распределеныИ, потребности удовлетворены.

2.К каждой вершине должна подходить или выходить из неё хотя бы одна стрелка.

3.Общее количество стрелок должно быть на единицу меньше числа вершин.

4.Стрелки не должны образовывать замкнутый контур.

33

Опорный план проверяется на оптимальность методом потенциалов. Одной из вершин присваиваем произвольное значение (например, равное 10). Двигаясь по стрелкам, определяем потенциалы остальных вершин по правилу: если стрелка выходит из вершины, то к потенциалу этой вершины прибавляется показатель стоимости Сij, если направление стрелки противоположно, то вычитается Сij.

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

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

34

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

Для решения проблем, возникающих в строительном

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

35