Курсовая: Математическая модель транспортной задачи - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

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

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 65 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

18 Яро славский Государственный Межрегиональный колледж градостроительств а и управления Курсовая работа по дисциплине «Математические методы» Тема «Математическая модель транспортной задачи» Пров ерил ___________ ____________________ Выполнил ___________ ____________________ г. Ярославль 2006г. Содержание Введен ие ………………………………………………………………. 2 1. Постановка за дачи и ее математическая модель … 3 2. Модели трансп ортной задачи …………………………… 7 2.1. Закрытая моде ль транспортной задачи ……………... 7 2.2 . Открытая мод ель транспортной задачи ……………… 8 3. Определение о птимального и опорного плана транспортной задачи ……………………………………… 10 4. Методы определения первоначального опорного план а …………………………………… ………………………………. 12 4.1. Метод минимал ьного элемента ………………………… 12 4.2. Метод аппрокс имации Фогеля …………………………. 14 5. Методы опреде ления оптимального плана ……….. 16 5.1. Венгерский ме тод ………………………………………….. 16 5.2. Метод потенци алов ……………………………………….. 17 Список использованной литературы ………………………… 19 Введение Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в д еле рационализации постановок важнейших видов промышленной и сельскох озяйственной продукции, а также оптимального планирования грузопотоко в и работы различных видов транспорта . Кроме того, к задачам транспортного типа сводятся мног ие другие задачи линейного программирования - задачи о назначениях, сете вые, календарного планирования. Цель заданной работы - освоить математическую постановку транспортно й задачи линейного программирования. 1. Постановка задачи и ее математич еская модель Транспортная задача является ча стным типом задачи линейного программирования и формулируется следующ им образом. Имеется m пунктов отправления (или пунктов производства) А i …, А m , в которых сосредоточены запасы однородных проду ктов в количестве a 1 , ..., а m единиц. Имеется n пунктов назн ачения (или пунктов потребления) В 1 , ..., В m , потребнос ть которых в указанных продуктах составляет b 1 , ..., b n е диниц. Известны также транспортные расходы С ij , связанные с перевозкой единицы продукта из пункт а A i в пункт В j , i 1, …, m; j 1, ..., n. Предположим, чт о т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и ск олько единиц продукта везти), чтобы удовлетворить спрос всех пунктов пот ребления за счет реализации всего продукта, произведенного всеми пункт ами производства, при минимальной общей стоимости всех перевозок. Приве денная формулировка транспортной задачи называется замкнутой транспо ртной моделью. Формализуем эту задачу. Пу сть х ij - количество единиц п родукта, поставляемого из пункта А i в пункт В j . Подл ежащие минимизации суммарные затраты на перевозку продуктов из всех пу нктов производства во все пункты потребления выражаются формулой: (1) Суммарное количество продукта, направляемого из каждого пункта отправ ления во все пункты назначения, должно быть равно запасу продукта в данн ом пункте. Формально это означает, что , i 1, …, m (2) Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно потребности. Это условие пол ного удовлетворения спроса: , j 1, …, n (3) Объемы перевозок - неотрицательные числа, так как перевозки из пунктов п отребления в пункты производства исключены: x ij 0, i 1, ..., m; j 1, ..., n (4) Тр анспортная задача сводится, таким образом, к минимизации суммарных затр ат при выполнении условий полного удовлетворения спроса и равенства вы возимого количества продукта запасам его в пунктах отправления. Определение 1. Всякое неотрицательное решение сист емы линейных уравнений , j 1, …, n и , i 1, …, m , определяемое матрицей X =( x ij )( i 1, …, m ; j 1, ..., n ), называется плано м транспортной задачи . Определение 2 . План X *=( x * ij )( i 1, …, m ; j 1, ..., n ) , при которо м функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи . Обычно исходные данные записываются в виде таблицы 1. Таблица 1. Пункты отправления Пункты назначения З апасы В 1 … B j … B n А 1 A 1 C 11 X 11 … C 1j X 1j … C 1n X 1n a 1 … … … … … … … A i C i1 X i1 … C ij X ij … C in X in a i … … … … … … … A m C m1 X m1 … C mj X mj … C mn X mn a m Потребности b 1 … b j … b n Очевидно, общее наличие груза у поставщиков равно , а общая потребност ь в грузе в пунктах назначения равна единице. Если общая потребность в гр узе в пунктах назначения равна запасу груза в пунктах отправления, т.е. , ( 5 ) то модель такой транспортной задачи называется закрытой . В ряде случаев не требуется, чтобы весь произведен ный продукт в каждом пункте производства был реализован. В таких случаях баланс производства и потребления может быть нарушен: , i 1, ..., m. Введение этого условия приводит к открытой тран спортной модели . Теорема 1. Любая транспорт ная задача, у которой суммарный объем запасов совпадает с суммарным объе мом потребностей, имеет решение. 2. Модели транспортной задачи 2.1. Закрытая модель транспорт ной задачи Для доказател ьства теоремы необходимо показать, что при заданных условиях существуе т хотя бы один план задачи и линейная функция на множестве планов ограни чена. Доказательство. Пусть = M > 0 . Тогда величин ы x ij = a i b j / M ( i = 1,2,3, ... m ; j = 1,2,3, ..., n ) являются планом, так как они удовлетворяют системе ограничений ( 2 ) и ( 3 ) . Действительно, подставляя значения в (2) и (3) , находим = a i , = b j . Выберем из значений C ij наибольшее C = max C ij и заменим в линейной функции ( 1 ) все коэффициенты на C тогда, учитывая ( 2 ) , получим , Выберем из значений C ij наименьш ее C = min C ij и заменим в линейной функции все коэффициенты на C ; тогда, учитывая ( 2 ) имеем Объединяя два последних неравенства в одно двойное , окончательно получ аем C M Z C M , т. е. линейная функция ограничена на множестве планов транспортной зада чи. 2.2 . Открытая модель трансп ортной задачи Транспортная задача, в которой суммарные запасы и потребност и не совпадают, т. е. не выполняется условие , называется открытой. Для открытой модели может быть два случая : a) суммарные запас ы превышают суммарные потребности ; b) суммарные потре бности превышают суммарные запасы . Линейная функци я одинакова в обоих случаях, изменяется только вид системы ограничений. Найти минимальное значение линейной функции при ограничениях , i = 1, 2, ..., m , (случай а) , j = 1, 2, ..., n ; , i = 1, 2, ..., m , (случай б) , j = 1, 2, ..., n , x ij 0 ( i = 1, 2, ..., m ; j = 1, 2, ..., n ). Открытая модель решается приведением к закрытой модели. В случае (а), когда суммарные запасы превышают суммарн ые потребности, вводится фиктивный потребитель B n +1 , потребности которого b n +1 = . В случае (б), когда сумм арные потребности превышают суммарные запасы, вводится фиктивный пост авщик A m +1 , запасы которого a m +1 = . Стоимость перевозки единицы груза как фиктивного потребителя, так и сто имость перевозки единицы груза от фиктивного поставщика полагают равн ыми нулю, так как груз в обоих случаях не перевозится. После преобразований задача принимает вид закрытой модели и решается о бычном способом. При равных стоимостях перевозки единицы груза от поста вщиков к фиктивному потребителю затраты на перевозку груза реальным по требителям минимальны, а фиктивному потребителю будет направлен груз о т наименее выгодных поставщиков. То же самое получаем и в отношении фикт ивного поставщика. Прежде чем реш ать какую-нибудь транспортную задачу, необходимо сначала проверить, к ка кой модели она принадлежит, и только после этого составить таблицу для е е решения. 3. Определение оптимального и опор ного плана транспортной задачи Как и при решении задачи линейного программирования, симплексным мето дом, определение оптимального плана транспортной задачи начинают с нах ождения какого-нибудь ее опорного плана. Число переменных X ij в транспортной задаче с m пунктами отправления и n пунктами назн ачения равно nm , а число уравнений в системах (2) и (3) равно n + m . Так как мы предпола гаем, что выполняется условие (5), то число линейно независимых уравнений р авно n + m -1 отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонентов равно в точнос ти n + m -1, то план является не выраженным, а если меньше - то выраженн ым. Для определения опорного плана сущ ествует несколько методов. Три из них - метод северно-западного угла, мето д минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже. При составлении первоначального опорного плана ме тодом северо-западного угла стоимость перевозки единицы не учитываетс я, поэтому построенный план далек от оптимального, получение которого св язано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с пом ощью ЭВМ. Как и для всякой зад ачи линейного программирования, оптимальный план транспортной задачи является и опорным планом. Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. О днако ввиду исключительной практической важности этой задачи и специф ики ее ограничений [ каждое неизвестно е входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице ] для определения оптима льного плана транспортной задачи разработаны специальные методы. Два и з них - метод потенциалов и Венгерский метод - рассматриваются ниже. 4. Методы определения первоначального опорного плана 4.1. Метод минимального элемента Суть метода заключается в том, что из всей таблицы ст оимостей выбирают наименьшую и в клетку, которая ей соответствует, помещ ают меньшее из чисел и . Затем из рассмотрен ия исключают либо строку, соответствующую поставщику, запасы которого п олностью израсходованы, либо столбец, соответствующий потребителю, пот ребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребит еля. Из оставшейся части таблицы стоимостей снова выбирают наименьшую с тоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Пример Сост авить первоначальный опорный план методом минимального элемента для т ранспортной задачи вида: 2 3 4 15 11 6 10 1 8 9 3 3 4 1 2 21 10 20 10 Решен ие: Задача сбалансирована. Строим первоначальный опорный план методом минима льного элемента. 1. Выясним минимальную с тоимость перевозок. Первая перевозка буд ет осуществляться с пункта производства в пункт потребления и она составит макси мально возможное число единиц продукта :. В этом случае, потре бности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки .Выясним минимальную стоимость перевозок (без учета столбца № 2). 2. Вторая и третья пере возки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта : , ; 3. 4. Четвертая перевозка осуществляе тся с пункта в пункт потребле ния , т.к. (без учета первого, вт орого столбца и четвертой строки). . 5. Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, вт орого столбца, третьей и четвертой строки). . 6. Шестая перевозка осущ ествляется с пункта в пункт потребления т.к. (без учета первого, вт орого столбца, первой, третьей и четвертой строки). Опорны й план имеет вид; 10 5 0 0 1 0 0 3 0 0 11 10 4.2. Метод аппроксимации Фогеля При определени и опорного плана транспортной задачи методом аппроксимации Фогеля нах одят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отвед енных для этого строке и столбце в таблице условий задачи. Среди указанн ых разностей выбирают минимальную. В строке (или в столбце), которой данна я разность соответствует, определяют минимальная стоимость. Если ми нимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строк е ) , соответс тв ующем наибольшей разности между двумя минимальными стои мостями, находящимися в данном столбце (строке). Пример Найти м етодом аппроксимации Фогеля первоначальный опорный план транспортной задачи: (Здесь мы перенесли потребности в верхнюю строку для удобства построени я плана). Рассмотрим задачу, приведенную для методов северо-западного уг ла и минимального элемента Решение: 10 20 10 2 7 3 0 4 8 15 1 1 1 11 0 6 1 10 0 1 4 4 - 8 3 9 0 3 0 3 5 - - 4 0 1 19 2 2 21 1 1 - 2 2 1 2 2 2 2 2 2 2 - 2 - - 2 - - - Опорный пл ан имеет вид: 7 0 8 0 1 0 3 0 0 0 19 2 5. Методы определения оптима льного плана 5.1. Венгерский метод Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Строится начальный план перевозок, не удовлетворяющий в обще м случае всем условиям задачи (из некоторых пунктов производства не весь продукт вывозится, потребность части пунктов потребления не полностью удовлетворена). Далее осуществляется переход к новому плану, более близк ому к оптимальному. Последовательное применение этого приема за конечн ое число итераций приводит к решению задачи. Алгоритм венгерского метода состоит из подготовительного этапа и из ко нечного числа итераций. На подготовительном этапе строится матрица X0 (xij[0])m,n, элементы которой неотрицательны и удовлетворяют неравенствам: , i 1, …, m; , j 1, …, m. Если эти условия являются равенствами, то матрица Хo - решение транспортн ой задачи. Если среди условий имеются неравенства, то осуществляется пер еход к первой итерации. На k-й итерации строится матрица Хk (xij[0])m,n. Близость эт ой матрицы к решению задачи характеризует число Dk — суммарная невязка м атрицы Хk: . В результате первой итерации строится матрица Хl, состоящая из неотрицат ельных элементов. При этом Dl D0. Если Dl 0, то Хl - оптимальное решение задачи. Есл и Dl 0, то переходят к следующей итерации. Они проводятся до тех пор, пока Dk пр и некотором k не станет равным нулю. Соответствующая матрица Хk является р ешением транспортной задачи. Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае числ о итераций не превышает величины D0/2 (D0 - суммарная невязка подготовительно го этапа). Достоинством венгерского метода является возможность оценивать близо сть результата каждой из итераций к оптимальному плану перевозок. Это по зволяет контролировать процесс вычислений и прекратить его при достиж ении определенных точностных показателей. Данное свойство существенно для задач большой размерности. 5.2. Метод потенциалов Метод потенциалов является модификацией симплекс-метода решения задач и линейного программирования применительно к транспортной задаче. Он п озволяет, отправляясь от некоторого допустимого решения, получить опти мальное решение за конечное число итераций. Общая схема отдельной итера ции такова. По допустимому решению каждому пункту задачи сопоставляетс я число, называемое его предварительным потенциалом. Пунктам Аi соответс твуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их раз ность на k-й итерации была равна Сij - стоимости перевозки единицы продукци и между пунктами Аi и Вj: vj[k] – ui[k] Cij, i 1, ..., m; j 1, …, п . Если разность предварительных потенциалов для кажд ой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок являе тся решением задачи. В противном случае указывается способ получения но вого допустимого плана, связанного с меньшими транспортными издержкам и. За конечное число итераций находится оптимальный план задачи. Список использованной литературы 1. Е. Г. Гольштейн, Д. Б. Юдин «Задач и линейного программирования транспортного типа», Москва, 1993. 2. И. Л. Акулич, В. Ф. Стрельчонок «Мат ематические методы и компьютерные технологии решения оптимизационных задач», Рига, 2000. 3. www.fmi.asf.ru
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Когда Валуев открывает калитку и входит во двор, "Осторожно, злая собака!" становится обращением к собаке.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru