Автор работы: Пользователь скрыл имя, 16 Января 2013 в 17:09, курсовая работа
Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи)
2. Описание методов решения транспортных задач
2.1 Математическая
постановка и общая
Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача ,определяеться широкий круг задач с единой математической моделью эти задачи относяться к задачам линейного программирования и могут быть решены оптимальным методом. Однако ,спец.метод решения транспортнои задачи позволяет существенно упростить её решение по скольку транспортная задача разрабатывалась для минимизирования стоимости перевозок .
2.2. Математические методы решения транспортных задач
История поиска методов решения.
Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.
Решение транспортной задачи начинается с поиска допустимого начального решения (плана перевозок), чтобы все запасы поставщиков были распределены по потребителям. Допустимое начальное решение не обязательно оказывается оптимальным, а метод его нахождения может быть как простейшим (метод северо-западного угла) или более сложным и приближенным к оптимальному решению (метод минимальных тарифов), или же вообще произвольным.
Допустимое (но не всегда оптимальное с точки зрения стоимости доставки) начальное решение транспортной задачи можно построить, последовательно перебирая строки таблицы (то есть поставщиков) сверху вниз. В пределах каждой строки, нужно перебрать слева направо не охваченных или не полностью охваченных поставками потребителей, записывая в соответствующие ячейки объем поставляемого груза от поставщика в данной строке, и так до исчерпания возможностей поставщика. Таким образом, весь груз от поставщиков будет распределен по потребителям. Этот метод был предложен Данцигом в 1951 г. и назван Чарнесом и Купером «правилом северо-западного угла».
Метод наименьшего элемента.
Суть решения задачи методом минимального (наименьшего) элемента заключается в сведении к минимуму побочных перераспределений товаров между потребителями.
Алгоритм:
Алгоритм метода потенциалов:
Один из потенциалов задается произвольно, скажем, полагается .
Рассматривается система линейных уравнений вида для тех наборов индексов i , j , для которых , и находятся потенциалы и всех складов и всех пунктов потребления.
Для всех остальных наборов индексов i , j (для которых ) проверяется условие.
Если это условие выполняется для всех наборов индексов i , j , для которых , то рассматриваемый план является оптимальным. Если же, хотя бы
для одной пары, то план не оптимален.
3. Аналитическое решение задачи.
3.1 Решение в табличном процессоре MS Excel.
3.2 Ручной расчет.
3.2.1 Метод северо-западного угла.
Дано:
Пункты |
Запасы | |||||
12 |
14 |
32 |
20 |
3 |
54 | |
8 |
10 |
12 |
24 |
12 |
32 | |
6 |
8 |
12 |
24 |
18 |
85 | |
10 |
18 |
4 |
8 |
9 |
162 | |
Потребности |
100 |
70 |
30 |
45 |
50 |
Запасы: 54+32+85+162=333
Потребности: 100+70+30+45+50=295
Запасы меньше потребностей, значит, добавляем столбец с разностью запасов и потребностей. Уравниваем:
Пункты |
Запасы | ||||||
12 |
14 |
32 |
20 |
3 |
0 |
54 | |
8 |
10 |
12 |
24 |
12 |
0 |
32 | |
6 |
8 |
12 |
24 |
18 |
0 |
85 | |
10 |
18 |
4 |
8 |
9 |
0 |
162 | |
Потребности |
100 |
70 |
30 |
45 |
50 |
38 |
Вычисляем:
Пункты |
Запасы | ||||||
54 |
0 |
0 |
0 |
0 |
0 |
0 | |
32 |
0 |
0 |
0 |
0 |
0 |
0 | |
14 |
70 |
1 |
0 |
0 |
0 |
0 | |
0 |
0 |
29 |
45 |
50 |
38 |
0 | |
Потребности |
0 |
0 |
0 |
0 |
0 |
0 |
F(x) =
F(x) = 12*54+8*32+6*14+70*8+12*1+4*
= 648+256+84+560+12+116+360+450 = 2486
Ответ: F(x) = 2486.
3.2.1 Метод минимального элемента.
Дано:
Пункты |
Запасы | |||||
12 |
14 |
32 |
20 |
3 |
54 | |
8 |
10 |
12 |
24 |
12 |
32 | |
6 |
8 |
12 |
24 |
18 |
85 | |
10 |
18 |
4 |
8 |
9 |
162 | |
Потребности |
100 |
70 |
30 |
45 |
50 |
Запасы: 54+32+85+162=333
Потребности: 100+70+30+45+50=295
Запасы меньше потребностей, значит, добавляем столбец с разностью запасов и потребностей. Уравниваем:
Пункты |
Запасы | ||||||
12 |
14 |
32 |
20 |
3 |
0 |
54 | |
8 |
10 |
12 |
24 |
12 |
0 |
32 | |
6 |
8 |
12 |
24 |
18 |
0 |
85 | |
10 |
18 |
4 |
8 |
9 |
0 |
162 | |
Потребности |
100 |
70 |
30 |
45 |
50 |
38 |
Решение:
Пункты |
Запасы | ||||||
0 |
0 |
0 |
0 |
16 |
38 |
0 | |
15 |
17 |
0 |
0 |
0 |
0 |
0 | |
85 |
0 |
0 |
0 |
0 |
0 |
0 | |
0 |
53 |
30 |
45 |
34 |
0 |
0 | |
Потребности |
0 |
0 |
0 |
0 |
0 |
0 |
F(x) =
F(x) = 8*15+6*85+10*17+18*53+4*30+8*
= 120+510+170+954+120+360+48+306 = 2588
Ответ: F(x) = 2588.
4.Заключение.
В результате выполнения
курсового проекта был
5. Список литературы
5.1. Основная литература
5.1.1. Партыка Т.Л., Попов И.И. Математические методы. Гриф УМО МО РФ, 2009. – Изд-во: Форум. Серия: Профессиональное образование – 464 с.: ил.
5.1.2. Стрикалов А.И., Печенежская
И.А. экономико-математические
5.1.3. Макаров С.И., Севастьянова С.А. и др. Экономико-математические методы и модели. Гриф УМО МО РФ. Учебное пособие, 2009. – Изд-во: КноРус, 240 с.: ил.
5.1.4. Макаров С.И., Севастьянова С.А. и др. Экономико-математические методы и модели. Задачник. Гриф УМО МО РФ., 2009. – Изд-во: КноРус, 202 с.: ил.