Презентация Транспортные задачи онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Транспортные задачи абсолютно бесплатно. Урок-презентация на эту тему содержит всего 25 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Образование » Транспортные задачи
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:25 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:697.50 kB
- Просмотров:70
- Скачиваний:2
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Классическая постановка](/documents_5/512c9e16961be2cd52a228417934cd15/img1.jpg)
Содержание слайда: Классическая постановка задачи
В некотором географическом регионе имеется фиксированное число пунктов производства и хранения некоторого однородного продукта и конечное число пунктов потребления этого продукта. В качестве продукта может выступать, например, нефть, уголь, песок, цемент, т.д.
Для каждого из пунктов производства и хранения известен объем производства продукта или его запаса. Для каждого пункта потребления задана потребность в продукте в этом пункте потребления.
№6 слайд
![Показатели оптимальности](/documents_5/512c9e16961be2cd52a228417934cd15/img5.jpg)
Содержание слайда: Показатели оптимальности
1) Объем работы транспорта
(критерий - расстояние в т/км).
Минимум пробега удобен для оценки планов перевозок, поскольку расстояние перевозки определяется легко и точно для любого направления. Поэтому критерию нельзя решать транспортные задачи с участием многих видов транспорта.
С успехом применяется при решении транспортных задач для автомобильного транспорта и при разработке оптимальных схем перевозки однородных грузов автомобилями.
№7 слайд
![Показатели оптимальности](/documents_5/512c9e16961be2cd52a228417934cd15/img6.jpg)
Содержание слайда: Показатели оптимальности
2) Тарифная плата за перевозку груза (критерий - тарифы провозных плат).
Позволяет получить схему перевозок, наилучшую с точки зрения хозрасчетных показателей предприятия.
Все надбавки, а также существующие льготные тарифы затрудняют его использование.
№8 слайд
![Показатели оптимальности](/documents_5/512c9e16961be2cd52a228417934cd15/img7.jpg)
Содержание слайда: Показатели оптимальности
3) Эксплуатационные расходы на транспортировку грузов
(критерий - себестоимость эксплуатационных расходов).
Более верно отражает экономичность перевозок различными видами транспорта. Позволяет делать обоснованные выводы о целесообразности переключения с одного вида транспорта на другой.
№13 слайд
![Условие разрешимости](/documents_5/512c9e16961be2cd52a228417934cd15/img12.jpg)
Содержание слайда: Условие разрешимости транспортной задачи
В случае вводится фиктивный (n+1)-й пункт назначения с потребностью , и соответствующие тарифы считаются равными нулю: ci, n+1 = 0, i=1,m .
Аналогично, при вводится фиктивный (m+1)-й пункт отправления с запасом груза , и соответствующие тарифы считаются равными нулю: cm+1 , j =0, j=1,n.
Этим задача сводится к закрытой транспортной задаче.
№14 слайд
![Условие разрешимости](/documents_5/512c9e16961be2cd52a228417934cd15/img13.jpg)
Содержание слайда: Условие разрешимости транспортной задачи
Число переменных xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно m·n, а число уравнений в системе – n + m.
Тогда число линейно независимых уравнений равно
n + m – 1.
Поэтому опорный план может иметь не более
n + m – 1 отличных от нуля неизвестных.
Если в опорном плане число отличных от нуля компонент равно в точности n + m – 1, то план называется невырожденным, а если меньше – то вырожденным.
№15 слайд
![Общий алгоритм аналитического](/documents_5/512c9e16961be2cd52a228417934cd15/img14.jpg)
Содержание слайда: Общий алгоритм аналитического решения транспортной задачи
методом потенциалов
Находим первоначальный допустимый план (методы северо-западного угла, минимального элемента, двойного предпочтения, метод Фогеля);
проверяем полученный план на оптимальность (применяя свойства двойственных ЗЛП);
пока план не оптимальный переходим к плану с меньшей стоимостью перевозок.
№16 слайд
![Нахождение первоначального](/documents_5/512c9e16961be2cd52a228417934cd15/img15.jpg)
Содержание слайда: Нахождение первоначального допустимого плана
1. Метод северо-западного угла.
При нахождении опорного плана на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного x11 («северо-западный угол») и заканчивается клеткой для неизвестного xmn, т.е. как бы по диагонали таблицы.
№17 слайд
![Нахождение первоначального](/documents_5/512c9e16961be2cd52a228417934cd15/img16.jpg)
Содержание слайда: Нахождение первоначального допустимого плана
2. Метод наименьшей стоимости.
Из всей таблицы стоимостей выбирают наименьшую и в клетку (i, j), которая ей соответствует, помещают меньшее из чисел ai и bj .
Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс размещения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
№18 слайд
![Нахождение первоначального](/documents_5/512c9e16961be2cd52a228417934cd15/img17.jpg)
Содержание слайда: Нахождение первоначального допустимого плана
3. Метод двойного предпочтения.
В каждом столбце отмечают знаком «√» клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку «√√». В них находится минимальная стоимость, как по столбцу, так и по строке.
В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки.
Затем распределяют перевозки по клеткам, отмеченным знаком «√». В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.
№19 слайд
![Нахождение первоначального](/documents_5/512c9e16961be2cd52a228417934cd15/img18.jpg)
Содержание слайда: Нахождение первоначального допустимого плана
4. Метод аппроксимации Фогеля.
При определении опорного плана данным методом на каждой итерации по всем столбцам и всем строкам находят разность между двумя записанными в них минимальными тарифами.
Эти разности заносят в специально отведенные для этого строки и столбцы в таблице условий задачи.
Среди указанных разностей выбирают максимальную. В строке (или столбце), который данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.
№20 слайд
![Построенный первоначальный](/documents_5/512c9e16961be2cd52a228417934cd15/img19.jpg)
Содержание слайда: Построенный первоначальный план транспортной задачи как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода.
Построенный первоначальный план транспортной задачи как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода.
Однако из-за громоздкости симплексных таблиц, содержащих тn неизвестных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы.
№22 слайд
![Метод потенциалов Теорема](/documents_5/512c9e16961be2cd52a228417934cd15/img21.jpg)
Содержание слайда: Метод потенциалов
Теорема (критерий оптимальности)
Для того чтобы допустимый план перевозок в транспортной задаче был оптимальным, необходимо и достаточно, чтобы существовали такие числа u1, u2,…,um,v1, v2,…, vn , что
ui + vj =cij, если xij > 0,
ui + vj < cij, если xij ≤ 0.
Числа ui и vj называются потенциалами пунктов отправления Ai и назначения Bj соответственно.
№23 слайд
![Алгоритм нахождения](/documents_5/512c9e16961be2cd52a228417934cd15/img22.jpg)
Содержание слайда: Алгоритм нахождения оптимального решения транспортной задачи методом потенциалов
1. Пусть одним из рассмотренных выше методов найден опорный план.
2. Для базисных клеток плана (их m + n – 1), определяем потенциалы ui и vj так, чтобы выполнялось условие
ui. + vj = cij .
Поскольку система ограничений содержит m + n – 1 уравнений и m + n неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого определяются остальные потенциалы.
3. Для каждой из свободных клеток вычисляются величины
wij. = ui. + vj – cij.
4. Если оказалось, что wij < 0, то план оптимален. Если же хотя бы в одной свободной клетке wij > 0, то план не является оптимальным и может быть улучшен путем переноса по циклу, соответствующему данной свободной клетке.
№24 слайд
![Алгоритм нахождения](/documents_5/512c9e16961be2cd52a228417934cd15/img23.jpg)
Содержание слайда: Алгоритм нахождения оптимального решения транспортной задачи методом потенциалов
Циклом в таблице условий транспортной задачи, называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья – вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое – в столбце. Если ломанная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.
№25 слайд
![Пример На четыре базы A , A ,](/documents_5/512c9e16961be2cd52a228417934cd15/img24.jpg)
Содержание слайда: Пример
На четыре базы A1, A2, A3, A4 поступил однородный груз в следующем количестве: а1 тонн – на базу А1, а2 тонн – на базу А2, а3 тонн – на базу А3, а4 тонн – на базу А4. Полученный груз требуется перевезти в пять пунктов: b1 тонн – на базу B1, b2 тонн – на базу B2, b3 тонн – на базу B3, b4 тонн – на базу B4, b5 тонн – на базу B5. Расстояния между пунктами назначений указаны в матрице расстояний.
Скачать все slide презентации Транспортные задачи одним архивом:
Похожие презентации
-
Транспортные задачи Виды
-
Транспортная задача линейного программирования
-
Разработка программного обеспечения для решения задач теплотехники. - презентация
-
Разработка программного обеспечения для решения задач теплотехники
-
Новые педагогические технологии и изменение целей и задач образования В. С. Звонов Материалы для выступления в школе педмастерств
-
ВЛИЯНИЕ ЕВРОПЕЙСКОГО ЗОДЧЕСТВА НА ФОРМИРОВАНИЕ АРХИТЕКТУРНОГО НАСЛЕДИЯ КРЫМА ЦЕЛИ И ЗАДАЧИ: ВЛИЯНИЕ ЕВРОПЕЙСКИХ АРХИТЕКТУРНЫХ
-
Об итогах исполнения бюджета города Амурска за 1-е полугодие 2014 года и о задачах по исполнению бюджета в 2014 году
-
Федеральное государственное образовательное учреждение среднего профессионального образования «Омский автотранспортный колл
-
Введение. Цели и задачи. Основные понятия и определения. Требования к базам данных. - презентация
-
Задача 6 Зеленый заяц