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

23.02.2019

Модели транспортной задачи

Модель, в которой спрос и производство равны, называется закрытой (сбалансированной).

Если баланс производства и потребления нарушен, т.е. часть произведенного продукта не вывозится а i > b j , модель транспортной задачи будет открытой. Для решения открытой модели приведем ее к виду закрытой, введя фиктивный пункт потребления. Его потребность в произведенной продукции будет равна: b m+1 = а i - b j . В случае, когда спрос превышает мощность пунктов-изготовителей, также имеем вариант открытой модели. Подход к ее решению аналогичен ранее приведенному: открытую модель сводим к закрытой, вводя соответственно фиктивного поставщика. В связи с нарушением баланса спроса и предложения изменяются и ограничительные условия: предложение больше спроса - условия х ij а i , в противном случае х ij b j .

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

Методы решения транспортных задач

Решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т.д. пунктах производства, по первому, второму и т.д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются a i (q) , а текущих неудовлетворенных потребностей - b j (q) . Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем a i (0) = a i , b j (0) = b j . Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: х i,j = min {a i (q) , b j (q) }. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

a i (q+1) = a i (q) - x i,j , b j (q+1) = b j (q) - x i,j .

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: a i (q+1) =0 или b j (q+1) =0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т.е. переместиться к следующей клетке вниз по столбцу. Если же b j (q+1) =0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.

Основываясь на условии баланса запасов и потребностей (a i = b j), нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (a i (q) = b j (q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.

Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения c i,j . В связи с этим на практике для получения исходного плана используется другой способ - метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.

Поскольку в правиле ”северо-западного угла“ значение Cij не учитывается, нельзя ожидать, что при вычислении исходного плана по этому правилу соответствующее значение линейной формы будет близким к минимальному.

1. Правило минимума по строке. Пусть минимальным элементом первой строки будет C1k (если минимальных элементов имеется более одного, то выбираем элемент с наименьшим индексом j).Предположим X1k= a, если a1<=bk; x1k=bk, если a1>bk. В первом случае полагают Xik=0 для i = k и переходят ко второй строке, заменяя bk наbk-a1. После этого находят минимальный элемент второй строки и повторяют процесс. Во втором случае заменяют a1 на a1-bk, bk-на нуль и определяют наименьший за вычетом C1k элемент первой строки, после чего описанный процесс повторяется.

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

3. Правило минимального элемента матрицы. Отыскивается минимальный элемент Cij матрицы стоимостей перевозок, после чего величина перевозки (xij) полагается равной min(aibj). Процесс повторяется до тех пор, пока весь продукт не будет перевезен.

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:

vj[k] - ui[k] = Cij, i=1,..., m; j=1, …, n.

Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

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

Метод двойного предпочтения. Если таблица стоимостей велика, то перебор всех элементов затруднителен. В этом случае используют метод двойного предпочтения, суть которого заключается в следующем.

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

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

Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида продукции из нескольких пунктов изготовления (например, заводов) в пункты доставки (например, склады).

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

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

Определение транспортной модели

При построении транспортной модели используются:

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

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

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

Рассмотрим графическое представление транспортной модели

Рисунок 6

Транспортная модель такого вида называется сетевой и имеет mисходных пунктов иnпунктов назначения. Исходные пункты и пункты назначения называются вершинами сети или соответствующего графа. Маршрут по которому перевозится продукция называется дугой, количество продукции, производимая вi-ом исходно пункте обозначается. Количество потребляемой продукции вj-ом пункте -. Стоимость перевозки.

Соответствующую математическую модель можно записать в следующем виде:

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

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

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

В том случае, если что суммарный объем производства равен суммарному объему потребления, транспортная модель называется сбалансированной.

Такая модель является канонической моделью линейного программирования.

Пример транспортной модели

Заводы автомобильной фирмы расположены в Лос-Анджелесе, Детройте и Нью-Орлеане. Центры распределения в Денвере и Майами. Объем производства заводов 1000, 1500 и 1200 автомобилей соответственно. Ожидаемый спрос равен 2300 и 1400 автомобилей соответственно.

Стоимость перевозки одного автомобиля приведена в таблице 10:

Таблица 10

- количество автомобилей, которые перевозят изi-ого пункта вj-ый (i=1,2,3;j=1,2).

Суммарный объем производства автомобилей равен 3700 и равняется суммарному ожидаемому спросу. Следовательно, данная транспортная модель является сбалансированной и ее можно записать в следующем виде:

при ограничениях

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

Лабораторная работа №4

Транспортные модели

Цель работы: научиться находить оптимальное решение задач транспортного типа.

Задание

Вариант 1. На четырех ткацких станках с объемом рабочего времени 200, 300, 250 и 400 станко-ч за 1 час можно изготовить соответственно 260, 200, 340 и 500 м ткани трех артикулов I, II, III. Составить оптимальную программу загрузки станков, если прибыль (в ден. ед.) от реализации 1 м ткани i-го артикула при ее изготовлении на j-м станке характеризуется элементами матрицы

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

Табличная модель:

Контрольные вопросы:

1. Как записывается математическая модель задачи транспортного типа?

Обозначим через x ij объем перевозок от i-го поставщика j-ому потребителю. Математическая модель задачи имеет вид:

1) объем поставок i-го поставщика должен равняться количеству имеющегося у него груза

;

2) объем поставок j-ому потребителю должен быть равен его спросу

;

3) объемы поставок должны выражаться неотрицательными числами

, ;

4) общая сумма затрат на перевозку груза должна быть минимальной

Если суммарный объем отправляемых грузов равен суммарному объему потребностей в этих грузах по пунктам назначения

то такая транспортная задача называется закрытой (сбалансированной), в противном случае - открытой (несбалансированной).

Если указанные затраты неизвестны (не указаны) соответствующие значения с ij полагают равными нулю.

модель поставка потребность затрата

2. Как свести открытую транспортную задачу к закрытой?

Если имеет место открытая транспортная задача, ее необходимо свести к закрытой:

1) в случае перепроизводства – ввести фиктивного потребителя с необходимым объемом потребления (элементы матрицы с ij , связывающие фиктивные пункты с реальными, имеют значения, равные затратам на хранение невывезенных грузов);

2) в случае дефицита – ввести фиктивного поставщика с недостающим объемом отправляемых грузов (элементы матрицы с ij , связывающие фиктивные пункты с реальными, имеют значения, равные штрафам за недопоставку продукции).

3. Каковы основные ситуации, описывающие дополнительные ограничения транспортной задачи?

При решении практических задач зачастую приходится учитывать ряд дополнительных ограничений.

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

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

3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту A i B j можно провести не более qединиц груза, то B j -й столбец матрицы разбивается на два столбца –

и . В первом столбце спрос принимается равным , во втором – . Несмотря на то, что фактические затраты с ij в обоих столбцах одинаковы и равны исходным, в столбце вместо истинного тарифа с ij ставится искусственно завышенный тариф М (клетка блокируется). Затем задача решается обычным способом.

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

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

Вывод: я научилась находить оптимальное решение задач транспортного типа.

Под названием транспортная задача объединяется широкий круг задач с единой матетической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом. Однако, обычная транспортная задача имеет большое число переменных и решение ее симплексным методом громозко. С другой стороны матрица системы ограничений транспортной задачи весьма своеобразна, поэтому для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить последовательность опорных решений, которая завершается оптимальным решением.

Общая характеристика транспортной задачи

Условие:
Однородный груз сосредоточен у m поставщиков в объемах a 1 , a 2 , ... a m .
Данный груз необходимо доставить n потребителям в объемах b 1, b 2 ... b n .
Известны C ij , i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю.
Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.

Исходные данные транспортной задачи записываются в виде таблицы:

Исходные данные задачи могут быть представлены в виде:

вектора А=(a 1 ,a 2 ,...,a m) запасов поставщиков
вектора B=(b 1 ,b 2 ,...,b n) запросов потребителей
матрицы стоимостей:

Математическая модель транспортной задачи

Переменными (неизвестными) транспортной задачи являются x ij , i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю.
Эти переменные могут быть записаны в виде матрицы перевозок:

Так как произведение C ij *X ij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:

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

Система ограничений задачи состоит из двух групп уравнений.
Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид:

Вторая группа из n уравнений выражает требование удовлетворить запросы всех n потребителей полностью и имеет вид:

Учитывая условие неотрицательности объемов перевозок математическая модель выглядит следующим образом:

В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарынм запросам потребителей, т.е.:

Такая задача называется задачей с правильным балансом , а модель задачи закрытой . Если же это равенство не выполняется, то задача называется задачей с неправильным балансом , а модель задачи — открытой .

Математическая формулировка транспортной задачи такова: найти переменные задачи X=(x ij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (цифра 2 на математической модели) , (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1)

Пример 34.1

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

Решение:
1. Вводим переменные задачи (матрицу перевозок):

2. Записываем матрицу стоимостей:

3. Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.

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

4. Составим систему ограничений задачи.
Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика:

Это означает, что запасы поставщиков вывозятся полностью.

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

Это означает, что запросы потребителей удовлетворяются полностью.

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

Ответ : Таким образом, математическая модель рассматриваемой задачи записывается следующим образом:
Найти переменные задачи, обеспечивающие минимум целевой функции (1) и удовлетворяющие системе ограничений (2) и условиям неотрицательности (3).

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

Транспортные модели бывают имитационные, оптимизационные, прогнозные.

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

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

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

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

Транспортная модель города является прогнозной моделью.

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

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

Для построения транспортного спроса собирается различная статистическая информация о транспортных районах, которые являются местами генерации и местами притяжения транспортных потоков. Пример собираемой информации для каждого транспортного района:

емкость района (население);
доля работающих;
доля учащихся;
количество зарегистрированных автомобильных средств;
количество рабочих мест;
количество рабочих мест в сфере услуг;
количество мест в учебных заведениях;
и др.

Далее составляются слои спроса - возможные перемещения, например Дом-Работа, Работа-Дом, Дом-Школа, Школа-Дом, Дом-Прочее, Прочее – Дом. Чем больше слоев спроса, тем выше точность модели. Для каждого слоя спроса и для каждого вида транспорта(общественный, индивидуальный) составляется матрица корреспонденции – матрица, содержащая количественные данные о перемещениях людей из района в район. Далее эти матрицы соединяются по каждому виду транспорта. Это и будет являться результатом моделирования транспортного спроса.

Следующий этап построения транспортной модели - совмещение транспортного предложения и транспортного спроса. Ищется точка равновесия, при которой существующее транспортное предложение будет удовлетворять транспортный спрос. При этом учитывается важный принцип: каждое транспортное средство стремится уменьшить время и стоимость своего перемещения.

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

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

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

Создание комплексной транспортной схемы (КТС), программы комплексного развития транспортной инфраструктуры (ПКРТИ), комлексной схемы организации дорожного движения (КСОДД), а также комплексной схемы организации транспортного обслуживания населения общественным транспортом невозможно без наличия транспортной модели.