Транспортная задача по критерию времени

Курсовой проект

Название «транспортная задача» объединяет широкий круг задач с единой математической моделью. Классическая транспортная задача — проблема наиболее дешевого транспортного плана однородного продукта или взаимозаменяемых продуктов от точек производства до точек потребления, чаще всего встречается в практических приложениях линейного программирования. Линейное программирование — это одна из ветвей математического программирования, область математики, которая разрабатывает численную теорию и методы решения экстремальных многомерных задач с ограничениями.

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

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

В данной курсовой работе рассмотрены метод северо-западного угла.

ТЕОРИТИЧЕСКАЯ ЧАСТЬ, МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Транспортная проблема — однородная нагрузка сосредоточена в объемах тонн поставщиков .

Данный груз необходимо доставить п потребителям в объемах .

Известны (i=1,2,…,m; j=1,2,…,n)- стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. необходимо разработать транспортный план, при котором запасы всех поставщиков полностью вывозятся, потребности всех потребителей полностью удовлетворяются, а общие затраты на транспортировку всех товаров минимальны.

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

Таблица 1

… … … … …

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

13 стр., 6340 слов

Сущность и задачи транспортной логистики

... задачам транспортной логистики в первую очередь относят задачи, решение которых усиливает согласованность действий непосредственных участников транспортного процесса. Существуют такие задачи транспортной логистики как создание транспортного коридора и транспортной цепи. Транспортный ... транспорт. Транспортная система стран СНГ (10% мировой транспортной сети), занимает первое место по общему объему ...

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

i=1,2,…,m,

j=1,2,…,n,

i=1,2,…,m; j=1,2,…,n.

Целевая функция задачи выражает необходимость обеспечения минимума общих затрат на транспортировку всех товаров. Первая система m уравнений описывает тот факт, что запасы всех m поставщиков полностью экспортируются. Вторая группа из n уравнений выражает требования для полного удовлетворения потребностей всех n потребителей. Неравенства — это условия неотрицательности всех переменных задачи.

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

i=1,2,…,m; j=1,2,…,n,

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

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

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

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

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

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

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

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

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

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

Ответ: математическая модель задачи формулируется следующим образом: найти переменные задачи, обеспечивающие минимум функции

и удовлетворяющие системе ограничений и условиям неотрицательности.

2 АЛГОРИТМ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

2.1 СБАЛАНСИРОВАННОСТЬ ТРАНСПОРТНОЙ ЗАДАЧИ

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

Если транспортная проблема не сбалансирована, то в ее решении есть свои особенности.

Особенности решения транспортных задач с неправильным балансом:

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

то необходимо ввести фиктивного (n+1)-го потребителя с запросами равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза

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

то необходимо ввести фиктивного (m+1)-го поставщика с запасами равные разности суммарных запросов потребителей и запасов поставщиков, и нулевыми стоимостями перевозок единиц груза

48 стр., 23921 слов

Логистика запасов

... также запасы на пути товаров от поставщика к потребителю, то есть у оптовиков, оптовиков и мелких розничных торговцев, в закупочных организациях и в запасах в пути./1/ Запасы сырья, в свою ... данной работы является ООО «Ландыш». Теоретические аспекты логистики запасов 1.1 Понятие, сущность и виды материальных запасов Запасы являются неотъемлемой частью текущей деятельности организации. Наиболее общую ...

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

2.2 ОПОРНОЕ РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

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

Ввиду того, что ранг системы векторов условий транспортной задачи равен N=m+n-1, опорное решение не может иметь отличных от нуля координат больше, чем N.

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

Цикл — это последовательность ячеек в таблице проблем транспорта, где две и только смежные ячейки находятся в одной строке или столбце, а первая и последняя ячейки также находятся в одной строке или столбце.

Векторная система условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих ячеек таблицы невозможно сформировать единый цикл. Следовательно, допустимое решение транспортной задачи , i=1,2,…,m; j=1,2,…,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.

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

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

Метод минимальной стоимости. Данный метод позволяет построить опорное решение, которое достаточно близко к оптимальному, так как использует матрицу стоимостей транспортной задачи , i=1,2,…,m; j=1,2…,n. Данный метод состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одна строка(поставщик) или один столбец(потребитель).

Очередную клетку, соответствующую , заполняют также. Поставщик исключается из рассмотрения, если его запасы заканчиваются. Потребитель исключается из рассмотрения, если его запросы полностью удовлетворены. На каждом шаге исключается либо один поставщик, либо один потребитель. Кроме того, если поставщик не исключен, но его запасы равны нулю, то на этапе, когда он должен доставить груз, базовый ноль вводится в соответствующую ячейку таблицы, и только после этого поставщик исключается из рассмотрения. Аналогично поступают с потребителем.

35 стр., 17390 слов

Транспортная задача. Метод потенциалов

... тогда, когда из занятых клеток таблицы нельзя образовать ни одного цикла. 2.1 Метод вычеркивания Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным. Пусть допустимое решение транспортной задачи, которое имеет m+n-1 отличных ...

Решение является «вычеркиваемым» и, следовательно, опорным.

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

Тележка «загружается» в выбранную свободную ячейку, и одна из занятых ячеек освобождается, получая новый поддерживающий раствор.

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

Для удобства вычислений вершины циклов нумеруют и отмечают нечетные знаком «+», а четные знаком «- ». Такой цикл называется означенным.

Сдвигом по циклу на величину называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», и уменьшение объемов перевозок на ту же величину во всех не четных клетках, отмеченных знаком «- ».

2.3 МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

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

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

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

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

ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЮ ВРЕМЕНИ

Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется m поставщиков с запасами однородной загрузки в количестве a1, a2,…, а также потребители, которым этот груз доставляется каждым i-м поставщиком каждому j-му потребителю. необходимо составить такой план перевозок, при котором запасы всех товаров минимальны.

Составим математическую модель этой задачи. Обозначим x ij — объем перевозимого груза от i-го поставщика j-му потребителю. Система ограничений задачи не отличается от системы ограничений традиционной транспортной задачи. Пусть Х=(Хij), i=1,2 …,m; j=1,2,…, n — некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т(Х) наибольшее значение элементов матрицы Т=(tij), i=1,2,…, m; j=1,2,…, n, соответствующих клеткам таблицы, занятым опорным решением: Т(Х)= max{tij}. Таким образом, за время Т(Х) план перевозок будет выполнен полностью.

5 стр., 2147 слов

Транспортная задача

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

Задача решается в следующем порядке. Находится начальное опорное решение Х 1. Определяется значение целевой функции Т(Х1)=max{tij}=tl1k1. Все свободные клетки, которым соответствует значение tij>T(X1), исключается из рассмотрения (перечеркиваются).

Занять эти ячейки нецелесообразно, поскольку значение целевой функции увеличивается. Чтобы уменьшить ее значение, необходимо освободить клетку (l1, k1), в которой tij достигает максимума. По этой причине строятся так называемые циклы РАЗГРУЗКИ, которые могут включать в себя несколько свободных ячеек. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1, k1), расставляются поочередно знаки «-» и «+» и осуществляется сдвиг на величину Q=min {xij}. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается).

Получается новое опорное решение Х2 , на котором значение целевой функции меньше, чем на Х1.

Далее снова пытаются разгрузить клетку, соответствующую Т(Х 2)=max{tij}=tl2k2. Процесс продолжается до тех пор, пока не исчезнет возможность скачать соответствующую ячейку.

ПРАКТИЧЕСКАЯ ЧАСТЬ

Составляем начальное опорное решение Х 1 по методу северо-западного угла. Максимальной целевой функции T(X1)=max {10,8,5,12,4}=12 достигается в клетке (3,4).

Перечеркиваем клетку (4,1), в которой время доставки груза t41=15 больше, чем T(X1)=12.

Таблица 2

B j Ai 203040602010 20 6 3 2 305 — 8 30 7 + 4 502 + 4 5 40 — 12 10 5015 5 9 4 50

Для улучшение решения разгрузки освободим клетку (3,4) с помощью цикла (3,4), (2,4), (2,2), (3,2).

Означим цикл, найдем Q=min{10,30}=10. Осуществив сдвиг по циклу, получим второе опорное решение:

2 )=max{10,8,4,5,4}=10,

34=12 больше, чем Т(Х2)=10

транспортная разгрузка сбалансированность

B j Ai 2030406020- 10 20 + 6 3 2 30+ 5 — 8 20 7 4 10 502 4 10 5 40 12 5015 5 9 4 50

Разгружаем клетку (1,1) с помощью цикла (1,1), (1,2), (2,2), (2,1).

Означим цикл, найдем:

Q=min{20,20}=20.

3 . Максимум целевой функции на этом опорном решении:

Т(Х 3)=max {6,5,4,4,5,4}=6 и достигается в клетке (1,2).

Перечеркиваем клетки (1,1) (2,2) (2,3) и (4,3) в них время больше, чем Т(Х3)=6

8 стр., 3809 слов

Организация первой помощи при ДТП

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

B j Ai 203040602010 — 6 20 + 3 2 305 20 8 7 4 10 502 + 4 10 — 5 40 12 5015 5 9 4 50

Разгрузим клетку (1,2) с помощью цикла (1,2), (1,3), (3,3), (3,2).

Означим цикл, найдем:

Q=min {20,20}=20

4 ).

Т(Х4) =max {5,4,4,5,4}=5 и достигается в клетках (2,1) и (3,3).

Перечеркиваем клетки (1,2) и (4,2) в которых время перевозок не менее t21=5. С помощью оставшихся не вычеркнутых клеток разгрузить клетки (2,1) и (3,3) не удается, поэтому Х4 является оптимальным решением.

B j Ai 203040602010 6 3 20 2 305 20 8 7 4 10 502 4 30 5 20 12 5015 5 9 4 50

Ответ: min T(X)=5 при Х*=

ЗАКЛЮЧЕНИЕ.

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

СПИСОК ЛИТЕРАТУРЫ:

[Электронный ресурс]//URL: https://obzone.ru/kursovoy/reshenie-transportnoy-zadachi/

1. Общий курс высшей математики для экономистов. Учебник / под ред В.И. Ермакова.- М.: ИНФА — М. — 656 с. — (серия «высшее образование»).

  • Сборник задач и упражнений по высшей математике: математическое программирование: учебник пособие / А.В. Кузнецов, В.А. Сакович, Н.И. Холод и др;
  • МН.: выш. ик., 2002. — 447с.:ил.
  • Т.Л. Партыкина, И.И. Попов Математические методы: учебник. — М.: ФОРУМ: ИНФА-М, 2005. — 464 с.: ил — (профессиональное образование)
  • И.Г.

Семакин Основы программирования: учебник для сред. проф. Образования / И.Г. Семакин, А.П.Шестаков. — 2-е изд., стер,- М.: Издательский центр «Академия», 2003.-432 с.

  • Федосеев В.В. и др. Экономико-математические методы и прикладные модели: учебник для вузов. — М.: Юнити, 2002.
  • Коршунов Ю.М.

математические основы кибернетики: учебное пособие для ВУЗов. — М.: Энергоатомиздат, 1987.