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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Департамент образования и науки Кемеровской области

Государственное образовательное учреждение

среднего профессионального образования

Кемеровский профессионально-технический колледж

КУРСОВОЙ ПРОЕКТ

по дисциплине: «Математические методы»

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

по специальности: 230105 «Программное обеспечение ВТ и АС»

Выполнил (а): Филягин Илья

Студент (ка) группы: Пр-71

Руководитель: Новоселова Е.В.._____

Кемерово 2010г.

Аннотация

Данный курсовой проект на тему «Транспортная задача по критерию времени» выполнен Филягиным Ильей Олеговичем, специальность 230105 «Программное обеспечение вычислительной техники и автоматизированных систем», город Кемерово, Кемеровский профессионально-технический колледж, 2010 год.

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

Содержание

1. Введение

2. Теоретическая часть

2.1. Математическая постановка задачи

2.2. Алгоритм решения транспортной задачи

2.2.1. Сбалансированность транспортной задачи

2.2.2. Опорное решение транспортной задачи

2.2.3. Метод северо-западного угла

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

3. Практическая часть

4. Блок-схема

Заключение

Список используемой литературы

ВВЕДЕНИЕ

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

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

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

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

2. ТЕОРИТИЧЕСКАЯ ЧАСТЬ

2.1. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

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

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

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

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

Таблица 1

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

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

i=1,2,…,m,

j=1,2,…,n,

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

.

Если транспортная задача не сбалансирована, то возникают особенности в ее решении.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача решается в следующем порядке. Находится начальное опорное решение Х₁. Определяется значение целевой функции Т(Х1)=max{t_ij}=t_l1k1. Все свободные клетки, которым соответствует значение t_ij>T(X1), исключается из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как увеличивается значение целевой функции. Чтобы уменьшить ее значение, необходимо освободить клетку (l1, k1), в которой tij достигает максимума. Для этого строят так называемые РАЗГРУЗОЧНЫЕ циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1, k1), расставляются поочередно знаки «-» и «+» и осуществляется сдвиг на величину Q=min {x_ij}. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х₂ , на котором значение целевой функции меньше, чем на Х1.

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

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

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

Таблица 2

Для улучшение решения разгрузки освободим клетку (3,4) с помощью цикла (3,4), (2,4), (2,2), (3,2). Означим цикл, найдем Q=min{10,30}=10. Осуществив сдвиг по циклу, получим второе опорное решение:

Т(Х₂)=max{10,8,4,5,4}=10,

Достигается в клетке (1,1). Перечеркиваем клетку (3,4), т.к. время t₃₄=12 больше, чем Т(Х₂)=10

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

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

Q=min{20,20}=20.

Осуществив сдвиг по циклу, получим третье опорное решение Х₃. Максимум целевой функции на этом опорном решении:

Т(Х₃)=max {6,5,4,4,5,4}=6 и достигается в клетке (1,2). Перечеркиваем клетки (1,1) (2,2) (2,3) и (4,3) в них время больше, чем Т(Х₃)=6

Разгрузим клетку (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) в которых время перевозок не менее t₂₁=5. С помощью оставшихся не вычеркнутых клеток разгрузить клетки (2,1) и (3,3) не удается, поэтому Х₄ является оптимальным решением.

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

ЗАКЛЮЧЕНИЕ.

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

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

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

2. Сборник задач и упражнений по высшей математике: математическое программирование: учебник пособие / А.В. Кузнецов, В.А. Сакович, Н.И. Холод и др; МН.: выш. ик., 2002. - 447с.:ил.

3. Т.Л. Партыкина, И.И. Попов Математические методы: учебник. - М.: ФОРУМ: ИНФА-М, 2005. - 464 с.: ил - (профессиональное образование)

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

5. Федосеев В.В. и др. Экономико-математические методы и прикладные модели: учебное пособие для ВУЗов. - М.: Юнити, 2002.

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

Размещено на Allbest.ru