Что такое 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
  • Количество просмотров: 140
  • Количество скачиваний: 0
- Предыдущая Вежливость
Следующая - Профессии в музыке (Musical professions)

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

Турнир смекалистых 3 класс презентация к уроку по математике (3 класс) по теме Турнир смекалистых 3 класс презентация к уроку по математике (3 класс) по теме 103
найди и сосчитай геометрические фигуры найди и сосчитай геометрические фигуры 67
Распределительное свойство умножения 6 класс Распределительное свойство умножения 6 класс 113
Презентация к уроку математики Уравнение.Проверка решения уравнения презентация к уроку (математика, 1 класс) по теме Презентация к уроку математики Уравнение.Проверка решения уравнения презентация к уроку (математика, 1 класс) по теме 114
Таблица сложения 1 класс Таблица сложения 1 класс 175
Правильный многоугольник Правильный многоугольник 75
Пирамида. Площадь пирамиды Пирамида. Площадь пирамиды 102
Презентация. Математика. Понятия + и - презентация к уроку по математике (1 класс) по теме Презентация. Математика. Понятия + и - презентация к уроку по математике (1 класс) по теме 195
Обыкновенные дроби и действия с ними Обыкновенные дроби и действия с ними 118
Презентация-Танграм презентация по математике по теме Презентация-Танграм презентация по математике по теме 136
Презентация по математике Математическая гонка Презентация по математике Математическая гонка 135
Сводная таблица умножения презентация к уроку по математике (3 класс) Сводная таблица умножения презентация к уроку по математике (3 класс) 163
Урок математики в 1 классе по теме: Выше и ниже.ПНШ. план-конспект урока по математике (1 класс) по теме Урок математики в 1 классе по теме: Выше и ниже.ПНШ. план-конспект урока по математике (1 класс) по теме 112
Урок математики Урок математики 100
Презентация к уроку Отрезок. прямая. Луч математика 5 класс Презентация к уроку Отрезок. прямая. Луч математика 5 класс 126
Прямоугольные треугольники 7 класс Прямоугольные треугольники 7 класс 106
Целое и части 1 класс Целое и части 1 класс 210
Закрепление изученного материала по теме + - 1 2 3 презентация к уроку по математике (1 класс) по теме Закрепление изученного материала по теме + - 1 2 3 презентация к уроку по математике (1 класс) по теме 177
Презентация к исследовательской работе Решение банковских задач Презентация к исследовательской работе Решение банковских задач 127
презентации к урокам проект по математике (2 класс) презентации к урокам проект по математике (2 класс) 161
Числа от 1 до 100. Сложение и вычитание презентация к уроку по математике (3 класс) Числа от 1 до 100. Сложение и вычитание презентация к уроку по математике (3 класс) 262
Сложение и вычитание в пределах 100 Сложение и вычитание в пределах 100 102
Презентация Узоры и орнаменты на посуде. презентация к уроку по математике (старшая группа) Презентация Узоры и орнаменты на посуде. презентация к уроку по математике (старшая группа) 129
Математическое развитие дошкольников в контексте ФГОС ДО консультация по математике Математическое развитие дошкольников в контексте ФГОС ДО консультация по математике 134
Обозначения натуральных чисел Обозначения натуральных чисел 146
Тест по Матиматике №3 презентация к уроку (математика, 2 класс) по теме Тест по Матиматике №3 презентация к уроку (математика, 2 класс) по теме 106
Нужна ли в жизни координатная плоскость Нужна ли в жизни координатная плоскость 117
Моделирование и формализация Моделирование и формализация 100
Неравинства Неравинства 114
Производная функции Производная функции 106