Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Транспортная задача (продолжение)

Содержание

Метод Северо-западного угла. Метод минимальной стоимости (элемента).
Кафедра математики и моделированияСтарший преподаватель Е.Г. ГусевКурс «Высшая математика»Лекция 19. Тема: Транспортная Метод Северо-западного угла. Метод минимальной стоимости (элемента). ПРИМЕР. В резерве трех железнодорожных станций A, B, C находятся соответственно 60, m = 3; n = 4; m+n –1 = Общая стоимость составленного плана:Z=40·1+20·2+40·3+40·2+40·2+60·1= 40+40+120+80+80+60=420 Это не оптимальное решение. Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то очевидно, Суть метода минимальной стоимости (элемента) заключается в том, что из всей таблицы Затем из рассмотренного исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, Итак, опорный план трансформированной задачи построен, теперь надо из него получит оптимальный. Поэтому для нахождения оптимального плана транспортной задачи используют другие методы, самый распространенный Метод потенциалов. Числа и называют потенциалами поставщиков и потребителей. Для того чтобы план был оптимальным, необходимо выполнение следующих условий:1.) для каждой Если хотя бы одна незанятая клетка удовлетворяет условию (2), то опорный план Проверяем условие оптимальности для незанятых клеток: если Выбор клетки в которую необходимо послать перевозку: транспортная задача линейного программирования решается Построение цикла и определение величины перераспределения груза: отмечаем знаком « + » После перераспределения должно получиться m+n-1 занятых клеток.Если для какой-либо клетки условие оптимальности Для свободных клеток сумма потенциалов меньше, либо равна стоимости, следовательно в последней Открытая модель транспортной задачи. Стоимость перевозки единицы груза в этих случаях полагают равными нулю, т.к. груз Вопросы:1)Чем различаются открытая и закрытая модели транспортной задачи?2)В чем заключается метод потенциалов решения транспортной задачи?
Слайды презентации

Слайд 2 Метод Северо-западного угла. Метод минимальной стоимости (элемента).

Метод Северо-западного угла. Метод минимальной стоимости (элемента).

Слайд 3 ПРИМЕР. В резерве трех железнодорожных станций A, B,

ПРИМЕР. В резерве трех железнодорожных станций A, B, C находятся соответственно

C находятся соответственно 60, 80, 100 вагонов. Составить оптимальный

план перегона этих вагонов к 4-ем пунктам погрузки хлеба, если пункту №1 необходимо 40 вагонов, №2 – 60, №3 – 80, №4 – 60. Стоимость перегонов одного вагона со станции A в в указанные пункты соответственно равны 1, 2, 3, 4 ден.ед., со станции B – 4, 3, 2, 0 ден.ед. и со станции C – 0, 2, 2, 1 ден.ед..

Слайд 4

Слайд 5 m = 3; n = 4;

m = 3; n = 4; m+n –1 = 6 => План опорный

m+n –1 = 6 =>

План опорный

Слайд 6 Общая стоимость составленного плана:
Z=40·1+20·2+40·3+40·2+40·2+60·1=
40+40+120+80+80+60=420
Это не оптимальное решение.

Общая стоимость составленного плана:Z=40·1+20·2+40·3+40·2+40·2+60·1= 40+40+120+80+80+60=420 Это не оптимальное решение.

Слайд 7 Если при составлении опорного плана учитывать стоимость перевозки

Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то

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

оптимальному.

Слайд 8 Суть метода минимальной стоимости (элемента) заключается в том,

Суть метода минимальной стоимости (элемента) заключается в том, что из всей

что из всей таблицы стоимостей выбирают наименьшую, и в

клетку, которая ему соответствует, помещают меньшее из чисел и .

Слайд 9 Затем из рассмотренного исключают либо строку, соответствующую поставщику,

Затем из рассмотренного исключают либо строку, соответствующую поставщику, запасы которого полностью

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

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

Слайд 10 Итак, опорный план трансформированной задачи построен, теперь надо

Итак, опорный план трансформированной задачи построен, теперь надо из него получит

из него получит оптимальный. Можно было получить оптимальный план

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

Слайд 11 Поэтому для нахождения оптимального плана транспортной задачи используют

Поэтому для нахождения оптимального плана транспортной задачи используют другие методы, самый

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

Слайд 12 Метод потенциалов.

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

Слайд 13 Числа и

Числа и называют потенциалами поставщиков и потребителей.

называют потенциалами поставщиков и потребителей.

Слайд 14 Для того чтобы план был оптимальным, необходимо выполнение

Для того чтобы план был оптимальным, необходимо выполнение следующих условий:1.) для

следующих условий:
1.) для каждой занятой клетки сумма потенциалов должна

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

Слайд 15 Если хотя бы одна незанятая клетка удовлетворяет условию

Если хотя бы одна незанятая клетка удовлетворяет условию (2), то опорный

(2), то опорный план не является оптимальным, и его

улучшают, перемещая в клетку некоторое количество единиц груза).

Слайд 16 Проверяем условие оптимальности для незанятых клеток: если

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

, то план

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

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

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

задача линейного программирования решается на min линейной функции, поэтому

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

Слайд 18 Построение цикла и определение величины перераспределения груза: отмечаем

Построение цикла и определение величины перераспределения груза: отмечаем знаком « +

знаком « + » незанятую клетку, которую надо загрузить

(знаки (-;+) чередуются). Затем находим min , где – перевозки, стоящие в вершинах цикла, отмеченных знаком « - ».
Величина min определяет сколько единиц груза надо перераспределить.

Слайд 19 После перераспределения должно получиться m+n-1 занятых клеток.

Если для

После перераспределения должно получиться m+n-1 занятых клеток.Если для какой-либо клетки условие

какой-либо клетки условие оптимальности не выполняется, то можно улучшить

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

Слайд 20 Для свободных клеток сумма потенциалов меньше, либо равна

Для свободных клеток сумма потенциалов меньше, либо равна стоимости, следовательно в

стоимости, следовательно в последней таблице должно быть получено оптимальное

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

Слайд 21 Открытая модель транспортной задачи.

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

Слайд 22

Слайд 23

Слайд 24

Слайд 25

Слайд 26

Слайд 27 Стоимость перевозки единицы груза в этих случаях полагают

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

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

  • Имя файла: transportnaya-zadacha-prodolzhenie.pptx
  • Количество просмотров: 135
  • Количество скачиваний: 0
- Предыдущая Родная природа в стихотворениях русских поэтов 19 века
Следующая - Философы круга В. С. Соловьёва

Похожие презентации

Презентация по математике Статистические представлениям как форма подсчета участников Великой Отечественной Войны Презентация по математике Статистические представлениям как форма подсчета участников Великой Отечественной Войны 100
Поворот. (Геометрія. 9 клас) Поворот. (Геометрія. 9 клас) 94
Коллекция игр для устного счета план-конспект урока по математике Коллекция игр для устного счета план-конспект урока по математике 65
Интегрированный урок (математика + изо), 2 класс методическая разработка по математике (2 класс) Интегрированный урок (математика + изо), 2 класс методическая разработка по математике (2 класс) 134
Конспект по формированию элементарных математических представлений в старшей группе Математическое королевство план-конспект занятия по математике (старшая группа) Конспект по формированию элементарных математических представлений в старшей группе Математическое королевство план-конспект занятия по математике (старшая группа) 111
Учебно - методический комплект (технологическая карта урока математики Конкретный смысл действия умножения и мультимедийная презентация) 2 класс учебно-методический материал по математике (2 класс) Учебно - методический комплект (технологическая карта урока математики Конкретный смысл действия умножения и мультимедийная презентация) 2 класс учебно-методический материал по математике (2 класс) 101
Комбинаторные задачи в 5 - 6 классах Комбинаторные задачи в 5 - 6 классах 166
Презентация по математике на тему Тригонометрические неравенства Презентация по математике на тему Тригонометрические неравенства 49
Обучающий кроссворд. 1 класс. Математика. презентация к уроку по математике (1 класс) Обучающий кроссворд. 1 класс. Математика. презентация к уроку по математике (1 класс) 148
Презентация к интегрированному уроку Замечательные точки треугольника или что такое центр тяжести№ Презентация к интегрированному уроку Замечательные точки треугольника или что такое центр тяжести№ 118
Методы решения уравнений и неравенств Методы решения уравнений и неравенств 140
Презентация по математике на тему: Решение задач на зависимость между величинами. Время делать покупки Презентация по математике на тему: Решение задач на зависимость между величинами. Время делать покупки 171
Презентация к уроку математики Приведение дробей к наименьшему общему знаменателю Презентация к уроку математики Приведение дробей к наименьшему общему знаменателю 116
Путешествие по математике Путешествие по математике 109
Интерактивный тренажёр Помогите мышатам! по теме Сложение и вычитание чисел в пределах 100 Интерактивный тренажёр Помогите мышатам! по теме Сложение и вычитание чисел в пределах 100 102
Симметрия в пространстве Симметрия в пространстве 148
Математика и космос Математика и космос 141
Умножение и деление Умножение и деление 109
Интересные и быстрые способы вычисления Интересные и быстрые способы вычисления 147
Арифметический диктант к уроку математика 4 класс презентация к уроку по математике (4 класс) по теме Арифметический диктант к уроку математика 4 класс презентация к уроку по математике (4 класс) по теме 118
Открытый урок по математике на тему Тела вращения Открытый урок по математике на тему Тела вращения 132
Разработка урока Разработка урока 150
Презентация и конспект урока Круглые двузначные числа методическая разработка по математике (1 класс) Урок  математики в 1 классе Презентация и конспект урока Круглые двузначные числа методическая разработка по математике (1 класс) Урок  математики в 1 классе 138
Презентация Решение олимпиадных задач презентация к уроку по математике (3 класс) Презентация Решение олимпиадных задач презентация к уроку по математике (3 класс) 157
2-2 2-2 102
Нахождение объемов тел и их частей, полученных вращением плоских фигур Нахождение объемов тел и их частей, полученных вращением плоских фигур 105
Учебно-методическое пособие - дидактическая игра Кто в домике живёт? методическая разработка по математике (старшая группа) Учебно-методическое пособие - дидактическая игра Кто в домике живёт? методическая разработка по математике (старшая группа) 133
Ученический проект Числа вокруг нас творческая работа учащихся по математике (1 класс) по теме Ученический проект Числа вокруг нас творческая работа учащихся по математике (1 класс) по теме 133
Число 9, цифра 9 Число 9, цифра 9 99
Линия уравнений и неравенств школьного курса математики Линия уравнений и неравенств школьного курса математики 119