Xreferat.com » Рефераты по информатике и программированию » Транспортная задача по критериям стоимости и времени

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

Размещено на /

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра Автоматизированных систем


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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по дисциплине

Теория принятия решения


Иркутск 2009г.


Содержание:


1. Постановка задачи

2. Обоснование математической модели

3. Краткие сведения о методе решения задачи

4. Проверка достоверности полученных результатов

5. Алгоритм решения задачи

6. Листинг программы, реализующий алгоритм задачи

7. Руководство пользователя

7.1 Системные требования

7.2 Описание возможностей

7.3 Использование

7.4 Использование инженерного режима

8. Решение задачи курсовой работы на ПЭВМ по исходным данным индивидуального варианта

9. Список использованной литературы


1. Постановка задачи


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

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

Удельные стоимости Транспортная задача по критериям стоимости и времени и время перевозок Транспортная задача по критериям стоимости и времени приведены в таблице, при этом:

1) на пропускные способности коммуникаций ограничения не накладываются;

2) Транспортная задача по критериям стоимости и времени и Транспортная задача по критериям стоимости и времени - количество условных единиц продукта;

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


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


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

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

а) количество пунктов отправления может быть или 6, или 7, или 8;

б) количество пунктов отправления может быть или 7, или 8, или 9;

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

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

д) удельные стоимости могут быть назначены из диапазона Транспортная задача по критериям стоимости и времени;

е) значения времени перевозок могут быть назначены из диапазона Транспортная задача по критериям стоимости и времени


2. Обоснование математической модели


В пункте Транспортная задача по критериям стоимости и времени производится Транспортная задача по критериям стоимости и времениединиц однородного продукта. В пункте Транспортная задача по критериям стоимости и времени требуется Транспортная задача по критериям стоимости и времени единиц этого продукта.

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


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

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


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

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

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

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

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


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


Для дооптимизации по времени необходимо использовать следующую целевую функцию:

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


3. Краткие сведения о методе решения задачи


Сведение открытой модели транспортной задачи к открытой

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

Транспортная задача по критериям стоимости и времени, тогда вводят фиктивный пункт потребления Транспортная задача по критериям стоимости и времени, а дополнительный столбик матрицы С заполняют очень большими числами (М). После того, как решение получено, все перевозки xi,n+1 (Транспортная задача по критериям стоимости и времени), в оптимальном плане Хk считают равными нулю.

Транспортная задача по критериям стоимости и времени, тогда вводят фиктивный пункт производства Транспортная задача по критериям стоимости и времени, а дополнительную строку матрицы С заполняют очень большими числами (М). После того, как решение получено, все перевозки xm+1,j (Транспортная задача по критериям стоимости и времени), в оптимальном плане Хk считают равными нулю

Метод минимального элемента

Используют для нахождения начального опорного плана Т-задачи.

Элементы матрицы С нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х0 :

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

Пусть элементом с минимальным порядковым номером оказался


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


Возможны три случая:

а) если Транспортная задача по критериям стоимости и времени, то Транспортная задача по критериям стоимости и времени и всю оставшуюся i-ю строку заполняют нулями, а Транспортная задача по критериям стоимости и времени, Транспортная задача по критериям стоимости и времени;

б) если Транспортная задача по критериям стоимости и времени, то Транспортная задача по критериям стоимости и времени и весь оставшийся j-й столбец заполняют нулями, а Транспортная задача по критериям стоимости и времени, Транспортная задача по критериям стоимости и времени;

в) если Транспортная задача по критериям стоимости и времени, то Транспортная задача по критериям стоимости и времени и оставшийся j-й столбец и i-ю строку заполняют нулями, а Транспортная задача по критериям стоимости и времени, Транспортная задача по критериям стоимости и времени.

На этом один шаг метода заканчивается.

Далее этот процесс повторяют с незаполненной частью матрицы X0.

Метод потенциалов:

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

Числа Транспортная задача по критериям стоимости и времени называются потенциалами соответственно Транспортная задача по критериям стоимости и времениго поставщика и Транспортная задача по критериям стоимости и времениго потребителя.

Для оптимального плана Т-задачи необходимо выполнение условий:

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

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

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

Данная теорема носит название теоремы о потенциалах. На ней основан специальный метод решения ТЗ, названный методом потенциалов.

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

Метод потенциалов позволяет, исходя из некоторого опорного плана перевозок, найти за конечное число итераций решение транспортной задачи.

Общая схема метода.

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

Описание алгоритма метода потенциалов. Алгоритм складывается из предварительного этапа и конечного числа однотипных итераций.

Предварительный этап. С помощью известного метода определяют начальный опорный план Х0 и вычисляют предварительные потенциалы Транспортная задача по критериям стоимости и времени.

Вычисление предварительных потенциалов производят так. По найденному плану Х0 строят схему Т-задачи из основных коммуникаций плана.

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

После того как потенциалы всех пунктов найдены, строят матрицу


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


Если матрица C1 не содержит отрицательных элементов, то Х0 - оптимальный план. В противном случае Х0 - неоптимальный план, который может быть улучшен. Тогда переходят к выполнению однотипных итераций. Цель (k + 1)-й итерации - построение матрицы Сk, а также либо установление оптимальности плана Хk, либо нахождение более экономичного плана Хk+1.

Каждая итерация, кроме первой, где отсутствует первый этап, состоит из двух этапов.

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

Затем выделяют столбцы матрицы Ck, которые содержат элементы множества Xk-существенных элементов, которые находятся в столбцах матрицы Ck и отличны от элементов множества.

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

Далее строят матрицу Ck+1. Для этого наибольший по модулю отрицательней элемент матрицы Ck прибавляют ко всем выделенным столбцам и вычитают из всех выделенных строк матрицы Ck. При этом все выделенные Xk-существенные элементы матрицы Ck остаются равными нулю.

Если все элементы матрицы Ck+1 окажутся неотрицательными, то Xk— оптимальный план, и на этом процесс заканчивается. В противном случае переходят ко второму этапу.

Второй этап. Производят улучшение плана Хk. Выбирают наибольший по модулю отрицательный элемент матрицы Ck+1. Затем составляют, применив, например метод вычеркивания, цепочку из положительных элементов плана Xk, которая замыкается на выбранном элементе.

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

Новый план Xk+1.построен. Он является опорным, так как число его ненулевых перевозок не изменилось.


4. Проверка достоверности полученных результатов


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

Целевая функция считается 2 способами:


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


Пусть минимальным элементом матрицы С(k) оказался элемент с индексами μ, κ, тогда значение целевой функции на этом шаге будет равно:


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


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

Если условие выполняется, то полученный результат (на данной итерации) достоверен.

При

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: