Инфоурок / Математика / Другие методич. материалы / Транспортная задача

Транспортная задача

Напоминаем, что в соответствии с профстандартом педагога (утверждён Приказом Минтруда России), если у Вас нет соответствующего преподаваемому предмету образования, то Вам необходимо пройти профессиональную переподготовку по профилю педагогической деятельности. Сделать это Вы можете дистанционно на сайте проекта "Инфоурок" и получить диплом с присвоением квалификации уже через 2 месяца!

Только сейчас действует СКИДКА 50% для всех педагогов на все 111 курсов профессиональной переподготовки! Доступна рассрочка с первым взносом всего 10%, при этом цена курса не увеличивается из-за использования рассрочки!

ВЫБРАТЬ КУРС И ПОДАТЬ ЗАЯВКУ

Выбранный для просмотра документ опорный конспект транспортная задача.doc

библиотека
материалов

Транспортная задача. Метод потенциалов


Задача: Фирма должна отправить некоторое количество компьютеров с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 компьютеров, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 компьютеров. Стоимость перевозки одного компьютера со склада в магазин приведены в таблице.

Склады

Магазины

B1

B2

B3

B4

B5

A1

1

0

3

4

2

A2

5

1

2

3

3

A3

4

8

1

4

3


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


Пример 1: Составить опорный план задачи методом северо-западного угла.

Решение:

hello_html_12f93df4.png

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

F =


Метод наименьшего элемента


Пример 2: Составить опорный план методом наименьшего элемента.

Решение:

hello_html_m5e1ece07.png

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

F =


Метод потенциалов решения транспортных задач


Пример 3: См. пример 1. Проверить построенный план на оптимальность методом потенциалов.

Решение: Возьмем таблицу с построенным планом и добавим еще столбец и строку потенциалов.

По заполненным клеткам вычислим потенциалы по правилу hello_html_6d956266.gif:

Для пустых клеток вычислим их оценки hello_html_m79798a92.gif.

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

hello_html_m46834b54.png


Пример 4: Для плана примера 3 построим цикл перерасчета (в предыдущей таблице) и построим второй опорный план:

hello_html_m46834b54.png

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

F =

Проверим план на оптимальность методом потенциалов.

Так среди оценок пустых клеток есть отрицательные. План - ____________________.

Построим цикл перерасчета таблицы.

Третий опорный план:

hello_html_m46834b54.png

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

F =

Проверим план на оптимальность методом потенциалов. План - __________________.

Построим цикл перерасчета таблицы.

Четвертый опорный план:

hello_html_m46834b54.png

При этом суммарная стоимость перевозок

F =

Проверим план на оптимальность методом потенциалов. План - __________________.

Ответ:




Контрольные вопросы:

  1. Как построить опорный план транспортной задачи?

  2. В чем суть метода потенциалов?

  3. Как строится цикл перерасчета?

Задача:

На трех базах А1, А2, А3 имеется однородный груз в количестве 160, 155,85 условных единиц соответственно. Этот груз требуется перевести в четыре пункта потребления В1, В2 , В3 и В4 в количестве 115, 85, 130, 70 условных единиц соответственно. Стоимости перевозок единицы груза от поставщиков потребителям указаны в таблице в матрице стоимостей С. Составить такой план перевозки грузов, при котором транспортные расходы будут наименьшими.

hello_html_m6a6c38b2.gif

Выбранный для просмотра документ план урока транспортная задача.doc

библиотека
материалов

План урока

Учебная дисциплина МАТЕМАТИЧЕСКИЕ МЕТОДЫ

Тема урока Транспортная задача. Метод потенциалов

Цели урока

Учебные:

  1. Изучить понятие транспортной задачи и методы ее решения.

  2. Развить и закрепить навыки решения транспортных задач при помощи метода потенциалов.

Развивающие и воспитательные:

  1. Развитие личностно смыслового отношения к изучаемой дисциплине.

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

  3. Демонстрация применения получаемых знаний во многих профессиональных сферах нашей жизни.

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

  5. Воспитание сотрудничества в коллективной деятельности.

  6. Воспитание дисциплинированности, целеустремленности студентов.



Оснащение урока: дидактический материал, опорный конспект, компьютерный кабинет, проектор, электронная презентация, интерактивная доска.



Ход урока:

  1. Организационный момент:

проверка отсутствующих, заполнение журнала.



  1. Актуализация опорных знаний: новая тема



  1. Изучение нового материала:



(1 слайд)

Тема лекции: «Транспортная задача»

План лекции

  1. Введение.

  2. Постановка транспортной задачи.

  3. Методы решения транспортных задач.

  4. Метод потенциалов решения транспортных задач.


1. Введение


Здравствуйте, ребята.

На прошлых занятиях мы рассмотрели общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые в силу своей структуры допускают решения более простыми методами. Сегодня мы остановимся на одной из них – так называемой, транспортной задаче.

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью.


? вопрос? Кто нам напомнит основную задачу математических методов?


(2 слайд)

Мы рассмотрим классическую транспортную задачу – это задача об оптимальном плане перевозок продукта(-ов) из пунктов отправления в пункты потребления, встречается чаще всего в практических приложениях линейного программирования.


(проф. направленность)

Где могут пригодиться вам полученные сегодня знания.

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

Логисты обязательно должны уметь работать в Word, Excel, Access. Так как все эти знания вы имеете, то вполне можете работать логистами в дальнейшем.

Логистов иначе называют «транспортными богами».


(цель) Сегодня на уроке нам необходимо разобрать транспортную задачу, научиться строить математическую модель этой задачи и решать ее.


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



(3 слайд)

(Историческая справка) Но прежде, чем перейти к самой задаче, обратимся к истории:


Историческую справку нам сообщит ______________________.


(сообщение студента)

_______________________________________________________________

Проблема транспортной задачи была впервые формализована французским математиком Гаспаром Монжем в 1781 году, который выполнил работу о наиболее экономном способе перемещения масс для строительства военных укреплений.


А основное продвижение было сделано советским математиком и экономистом Леонидом Канторовичем.

В 1939 году к 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”.


Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.


В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за “вклад в разработку теории и оптимального использования ресурсов в экономике”.

______________________________________________________________________


Прослушав данное сообщение, вы еще раз можете убедиться, какое широкое применение имеет транспортная задача.


(4 слайд)

2. Постановка транспортной задачи


Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и равна cij (i = 1, m; j = 1, n).

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


Замечание:

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

hello_html_109bb24d.png

называется закрытой.


Чтобы мы могли решать данную задачу нам необходимо записать ее математическую модель.

? вопрос? Кто нам напомнит, что такое математическая модель?



(5 слайд)

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


hello_html_m74d4fc82.png

Наша задача найти значения х, которые удовлетворяют системе ограничений и целевой функции.

При этом нам понадобятся несколько определений:


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

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


3.Методы решения транспортных задач

Перейдем к решению задачи.

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


(6слайд)

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij ≥ 0, а в маленькие клетки – соответствующие тарифы Cij.

hello_html_m7ec9f2db.png


(пояснения)

Наша задача заполнить все клетки числами xij (количеством перевозимого товара) так, чтобы их сумма по строкам была равна аi, по столбцам -bj. Затем эти числа умножаем на стоимости перевозок Cij и складываем. И эта сумма должна принимать минимальное значение.


? вопрос? Сколько клеток нам необходимо заполнить, чтобы план был опорным?


(7 слайд)

Решение задачи разбивается на два этапа:


  1. Определение опорного плана.

  2. Нахождение оптимального решения путем последовательных операций.


Рассмотрим подробно каждый из этапов:


  1. Опорный план транспортной задачи можно найти, используя метод "северо-западного угла" или метод "минимального элемента".


(8 слайд)

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


Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj.


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


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

В конспекте записана задача, которую мы будем решать различными методами.


(9 слайд)

Задача: Фирма должна отправить некоторое количество компьютеров с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 компьютеров, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 компьютеров. Стоимость перевозки одного компьютера со склада в магазин приведены в таблице.

Склады

Магазины

B1

B2

B3

B4

B5

A1

1

0

3

4

2

A2

5

1

2

3

3

A3

4

8

1

4

3


Пример 1: Составить опорный план задачи методом северо-западного угла.

Решение: (интерактивная доска)

Исходная транспортная таблица имеет вид:


hello_html_12f93df4.png


Построим опорный план.

Магазин В1 подал заявку на 20 компьютеров, но со склада А1 мы можем перевести 15 компьютеров, ещё 5 компьютеров мы перевезём со склада А2. Спрос для магазина В1 удовлетворён. Рассмотрим магазин В2. В него необходимо доставить 12 компьютеров - доставим их со склада А2.

На складе А2 осталось 8 компьютеров. Выделим из них пять для магазина В3. На складе А2 осталось 3 компьютера. Выделим их на магазин В3, но потребности магазина ещё не удовлетворены, поэтому выделим ему со склада А3 ещё пять компьютеров. Осталось 15 компьютеров, столько, сколько требуется в магазин В5.


hello_html_m50a118d9.png


Все заявки удовлетворены, все запасы израсходованы.

Проверим, является ли полученный план опорным: количество ячеек с ненулевыми перевозками равно m+n-1 = 7.


Опорный план: Х11 = 15, Х21 = 5, Х22 = 12, Х23 = 5, Х24 = 3, Х34 = 5, Х35 = 15.

Все остальные Xij = 0. Такие клетки будем называть пустыми.

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

F = 1*15+5*5+1*12+2*5+3*3+4*5+3*15 = 136

Будет ли это минимальная стоимость перевозок, а план – оптимальным, проверим позже.

А сейчас рассмотрим другой метод составления опорного плана.


(10 слайд)

Метод наименьшего элемента


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


(интерактивная доска)

Пример 2: Составить опорный план задачи методом наименьшего элемента.

Решение: Исходная транспортная таблица имеет вид:

hello_html_m5e1ece07.png


Построим опорный план.


Находим в таблице наименьшую стоимость перевозки – это 0 в клетке A1B2. Записываем в этой клетке значение 12 (наименьшее из сумм по строке и столбцу).

hello_html_m598e2c03.png

Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на 12.

hello_html_m7c00d59.png

Находим следующую наименьшую по стоимости ячейку – их несколько, например, A1B1. Присваиваем ей значение 3, а сумму по столбцу заменяем на 17.

hello_html_19d25b49.png

Вычеркиваем первую строку.

hello_html_43892c67.png

Выбираем ячейку A3B3, присваиваем ей значение 5. Вычеркиваем третий столбец. Сумму по третьей строке заменяем на 15.

hello_html_3d238673.png

Выбираем ячейку A2B5, записываем в ней 15, уменьшаем вторую строку на 15 и вычеркиваем пятый столбец.

hello_html_bac25c0.png

Выбираем ячейку A3B1, присваиваем ей 15. Уменьшаем первый столбец на 15 и вычеркиваем третью строку.

hello_html_m78315b6e.png

Ячейке A2B1 присваиваем 2 и вычеркиваем первый столбец. Сумму по второй строке заменяем на 8.

hello_html_mcc1a348.png

Ячейке A2B4 присваиваем 8 и вычеркиваем четвертый столбец.

hello_html_125f3445.png

Опорный план построен.

hello_html_m117d28d4.png

Количество заполненных клеток 3+5-1=7.

Х11 = 3, Х12 = 12, Х21 = 2, Х24 = 8, Х25 = 15, Х31 = 15, Х33 = 5.

Все остальные Хij = 0.

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

F = 3*1+0*12+5*2+3*8+3*15+5*1 = 147.

147>136, т.е. данный план точно не оптимальный.


Итак, мы изучили 2 способа построения первого опорного плана. При решении задачи вы выбираете тот способ, который вам больше понравился (долее понятен).


2.Теперь необходимо проверить, будет ли построенный план оптимальным, т.е. получим ли мы минимальную стоимость перевозок.


Для этого воспользуемся методом потенциалов.


4.Метод потенциалов решения транспортных задач

(11 слайд)

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


Введем строку потенциалов ui и столбец потенциалов vj.

Полагая, что u1=0, остальные ui и vj найдем так, чтобы

а) для заполненных клеток выполнялись равенства hello_html_6d956266.gif;

б) для незаполненных клеток выполнялись равенства hello_html_m79798a92.gif (оценки пустых клеток).


(12 слайд)

Критерий оптимальности:


Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия hello_html_m24cdf183.gifто Х0 является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.


Пример3: Проверить план, построенный методом северо-западного угла на оптимальность методом потенциалов.


Возьмем таблицу с построенным планом и добавим еще столбец и строку потенциалов.

(перепишите в свою заготовленную таблицу план, полученный методом северо-западного угла).

hello_html_m344fec28.png

По заполненным клеткам вычислим потенциалы по правилу hello_html_6d956266.gif:

hello_html_m103b8596.png

Таким образом, мы вычислили потенциалы заполненных клеток.

Для пустых клеток вычислим их оценки hello_html_m79798a92.gif.

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

hello_html_m69f77153.png

Так среди оценок пустых клеток есть отрицательные – план не оптимальный.

Необходимо построить следующий план. Для этого построим цикл перерасчета таблицы.


(13 слайд)

Цикл перерасчёта таблицыэто последовательность клеток, удовлетворяющая условиям:

  • Одна клетка пустая с отрицательной оценкой, все остальные заполненные.

  • Любые две соседние клетки находятся в одной строке или в одном столбце.

  • Пустой клетке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

(14 слайд)

Далее составляем новую таблицу по следующему правилу:

  • Клетки вне цикла остаются без изменения.

  • В минусовых клетках находят число X = min(Xij).

  • В плюсовых клетках цикла добавляем Х.

  • Из минусовых клеток цикла вычитаем Х.

Получим новую таблицу, дающую новое решение Х, такое, что F (X1) ≤ F (X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.


(интерактивная доска)

Пример4: Для плана примера 3 построим цикл перерасчета.


Заполним одну из пустых клеток с отрицательной оценкой. Возьмем клетку А3В3, так как в ней стоимость меньше, чем в клетке А3В1.

Построим цикл перерасчета:

hello_html_c3daac7.png

Построим второй опорный план:

Заполненных клеток должно быть 3+5-1=7.

hello_html_26df9a70.png

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

F = 15*1+5*5+12*1+0*2+5*1+8*3+15*3=126.

Проверим план на оптимальность методом потенциалов.

hello_html_6642bd90.png

Так среди оценок пустых клеток есть отрицательные – план не оптимальный.

Построим следующий план.

Для этого построим цикл перерасчета таблицы.

hello_html_30e82fd.png

Третий опорный план:

hello_html_56c0ccd7.png

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

F = 15*1+5*5+12*1+5*1+8*3+0*3+15*3=126.

Проверим план на оптимальность методом потенциалов.

hello_html_38b41cc8.png

Так среди оценок пустых клеток есть отрицательные – план не оптимальный.

Построим следующий план.

Для этого построим цикл перерасчета таблицы.

hello_html_m6003a4a8.png

Четвертый опорный план:

hello_html_c0e68fa.png

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

hello_html_6bd3d95f.gif

При этом суммарная стоимость перевозок

F = 15*1+5*4+12*1+5*1+8*3+0*3+15*3=121 является минимальной.


Запишем ответ задачи:

Ответ: Чтобы транспортные расходы были минимальными 121 ден.ед. необходимо перевозить: с 1-го склада – 15 компьютеров в 1-ый магазин; со 2-ого склада – 12 - во 2-ой магазин, 8 - в 4-ый и 5 - в 5-ый магазин; с 3-его склада – 5 компьютеров в 1-ый магазин, 5 – во 2-ой и 10 – в 5-ый.


4. Закрепление нового материала: ответы на контрольные вопросы: (15 слайд)

  1. Как построить опорный план транспортной задачи?

  2. В чем суть метода потенциалов?

  3. Как строится цикл перерасчета?



(16, 17 слайды)

Еще хотелось бы обратить ваше внимание, на различные виды циклов перерасчета таблицы.

hello_html_1ccf1bf9.png

hello_html_m3a299f9c.png

5. Подведение итогов урока: выводы, оценки, домашнее задание:

Наш урок подходит к концу. Работой вашей на уроке я довольна, но хотелось бы обратить внимание _________________________________________.


За подготовленное сообщение _________________получает оценку _______.

За работу у доски ____________________________________________.


На следующем занятии - практическая работа №4 по изученной теме.

Чтобы лучше ее выполнить запишите Домашнее задание.

Контрольные вопросы и задача записаны в опорном конспекте.

Если у вас остались вопросы по решению систем линейных уравнений, то еще не поздно их задать.

Спасибо за урок.

До свидания.

Домашнее задание:

Контрольные вопросы.

Задача:

На трех базах А1, А2, А3 имеется однородный груз в количестве а1, а2, а3 условных единиц соответственно. Этот груз требуется перевести в четыре пункта потребления В1, В2 , В3 и В4 в количестве b1, b2 , b3 и b4 условных единиц соответственно. Стоимости перевозок единицы груза от поставщиков потребителям указаны в таблице в матрице стоимостей С.

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

а1=160, а2=155, а3=85

b1=115, b2 =85, b3=130, b4=70

hello_html_m6a6c38b2.gif





Подпись преподавателя





Приложение 1

Решение задачи методом минимального элемента

Найдём оптимальный план для рассмотренной выше задачи.

В качестве опорного плана возьмем план, полученный с помощью метода "минимального элемента" Х11 = 3, Х12 = 12, Х21 = 2, Х24 = 8, Х25 = 15, Х31 = 15, Х33 = 5. Все остальные элементы равны 0.


Так как у нас получились отрицательные значения, то полученный план не является оптимальным. Выберем ячейку для пересчета A2B2. Получим:

hello_html_m4d25737e.png

X = min(2, 12) = 2

Строим следующую транспортную таблицу.

hello_html_90f28af.png

Проверим полученный план на оптимальность с помощью метода потенциалов.

Т.к. есть отрицательные оценки пустых ячеек, то построенный план не является оптимальным, следовательно, производим пересчет. Выберем ячейку A3B5.


X = min(15, 10, 15) = 10, значит вычитать и прибавлять в ячейках, будем 10.

Строим следующую транспортную таблицу.

hello_html_7dad9974.png

Проверим построенный план на оптимальность.

Т.к. отрицательных оценок пустых ячеек нет, то полученный план является оптимальным. Х11 = 15, Х22 = 12, Х24 = 8, Х25 = 5, Х31 = 5, Х33 = 5, Х35 = 10. Все остальные Хij = 0.


F = 1*15+1*12+3*8+3*5+4*5+1*5+3*10 = 121.



Выбранный для просмотра документ таблица 1.doc

библиотека
материалов

hello_html_12f93df4.png

Выбранный для просмотра документ таблица 12.doc

библиотека
материалов

hello_html_12f93df4.png

Выбранный для просмотра документ таблицв 2.doc

библиотека
материалов

hello_html_432d5ce6.png

hello_html_432d5ce6.png

Выбранный для просмотра документ транспортная задача .ppt

библиотека
материалов
Классическая транспортная задача - задача об оптимальном плане перевозок прод...
Историческая справка Гаспар Монже Канторович Л.В.
Постановка транспортной задачи Однородный груз, имеющийся в m пунктах отправл...
Математическая модель транспортной задачи Определение: Построенный план назыв...
Математическая модель транспортной задачи При решении условие задачи удобно р...
Решение транспортной задачи 1. Определение опорного плана. 2. Нахождение опти...
Определение опорного плана 1. Метод северо-западного угла (диагональный)   Су...
Пример Фирма должна отправить некоторое количество компьютеров с трёх складов...
Определение опорного плана 2. Метод наименьшего элемента Сущность метода закл...
Нахождение оптимального плана Метод потенциалов: Введем строку потенциалов ui...
Нахождение оптимального плана Критерий оптимальности Если известны потенциалы...
Цикл перерасчёта таблицы Цикл перерасчёта таблицы – это последовательность кл...
Цикл перерасчёта таблицы Далее составляем новую таблицу по следующему правилу...
Контрольные вопросы Как построить опорный план транспортной задачи? В чем сут...
Виды циклов перерасчета Циклы перерасчета могут быть различной формы:
Виды циклов перерасчета Циклы перерасчета могут быть различной формы:
17 1

УЖЕ ЧЕРЕЗ 10 МИНУТ ВЫ МОЖЕТЕ ПОЛУЧИТЬ ДИПЛОМ

от проекта "Инфоурок" с указанием данных образовательной лицензии, что важно при прохождении аттестации.


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


Список всех тестов можно посмотреть тут - https://infourok.ru/tests

Описание презентации по отдельным слайдам:

№ слайда 1
Описание слайда:

№ слайда 2 Классическая транспортная задача - задача об оптимальном плане перевозок прод
Описание слайда:

Классическая транспортная задача - задача об оптимальном плане перевозок продукта(-ов) из пунктов отправления в пункты потребления. Чаще всего встречается в практических приложениях линейного программирования.

№ слайда 3 Историческая справка Гаспар Монже Канторович Л.В.
Описание слайда:

Историческая справка Гаспар Монже Канторович Л.В.

№ слайда 4 Постановка транспортной задачи Однородный груз, имеющийся в m пунктах отправл
Описание слайда:

Постановка транспортной задачи Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и равна cij (i = 1, m; j = 1, n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются, а суммарные транспортные расходы минимальны. Замечание: Задача в данной формулировке называется закрытой:

№ слайда 5 Математическая модель транспортной задачи Определение: Построенный план назыв
Описание слайда:

Математическая модель транспортной задачи Определение: Построенный план называется опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0. Определение: Опорный план называется оптимальным, если он приводит к минимальной суммарной стоимости перевозок.

№ слайда 6 Математическая модель транспортной задачи При решении условие задачи удобно р
Описание слайда:

Математическая модель транспортной задачи При решении условие задачи удобно располагать в таблице:

№ слайда 7 Решение транспортной задачи 1. Определение опорного плана. 2. Нахождение опти
Описание слайда:

Решение транспортной задачи 1. Определение опорного плана. 2. Нахождение оптимального решения путем последовательных операций.  

№ слайда 8 Определение опорного плана 1. Метод северо-западного угла (диагональный)   Су
Описание слайда:

Определение опорного плана 1. Метод северо-западного угла (диагональный)   Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj.   Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj.

№ слайда 9 Пример Фирма должна отправить некоторое количество компьютеров с трёх складов
Описание слайда:

Пример Фирма должна отправить некоторое количество компьютеров с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 компьютеров, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 компьютеров. Стоимость перевозки одного компьютера со склада в магазин приведены в таблице. таблица 1

№ слайда 10 Определение опорного плана 2. Метод наименьшего элемента Сущность метода закл
Описание слайда:

Определение опорного плана 2. Метод наименьшего элемента Сущность метода заключается в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.   таблица 1

№ слайда 11 Нахождение оптимального плана Метод потенциалов: Введем строку потенциалов ui
Описание слайда:

Нахождение оптимального плана Метод потенциалов: Введем строку потенциалов ui и столбец потенциалов vj. Полагая, что u1=0, а остальные ui и vj найдем так, чтобы : а) для заполненных клеток выполнялись равенства б) для незаполненных клеток выполнялись равенства

№ слайда 12 Нахождение оптимального плана Критерий оптимальности Если известны потенциалы
Описание слайда:

Нахождение оптимального плана Критерий оптимальности Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных клеток выполняются условия ,то Х0 является оптимальным планом. Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались. таблица 2

№ слайда 13 Цикл перерасчёта таблицы Цикл перерасчёта таблицы – это последовательность кл
Описание слайда:

Цикл перерасчёта таблицы Цикл перерасчёта таблицы – это последовательность клеток, удовлетворяющая условиям: Одна клетка пустая с отрицательной оценкой, все остальные заполненные. Любые две соседние клетки находятся в одной строке или в одном столбце. Пустой клетке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

№ слайда 14 Цикл перерасчёта таблицы Далее составляем новую таблицу по следующему правилу
Описание слайда:

Цикл перерасчёта таблицы Далее составляем новую таблицу по следующему правилу: Клетки вне цикла остаются без изменения. В минусовых клетках находят число X = min(Xij). В плюсовых клетках цикла добавляем Х. Из минусовых клеток цикла вычитаем Х.

№ слайда 15 Контрольные вопросы Как построить опорный план транспортной задачи? В чем сут
Описание слайда:

Контрольные вопросы Как построить опорный план транспортной задачи? В чем суть метода потенциалов? Как строится цикл перерасчета?

№ слайда 16 Виды циклов перерасчета Циклы перерасчета могут быть различной формы:
Описание слайда:

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

№ слайда 17 Виды циклов перерасчета Циклы перерасчета могут быть различной формы:
Описание слайда:

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

Выбранный для просмотра документ транспортная опорный конспект.doc

библиотека
материалов

Тема лекции: «Транспортная задача»

План лекции

  1. Построение математической модели транспортной задачи.

  2. Методы решения транспортных задач.

  3. Метод потенциалов решения транспортных задач.


1. Построение математической модели транспортной задачи

Мы рассмотрели общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые в силу своей структуры допускают решения более простыми методами. Мы остановимся только на одной из них – так называемой транспортной задаче.


Постановка транспортной задачи

Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и cij (i = 1, m; j = 1, n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е:hello_html_109bb24d.png а суммарные транспортные расходы минимальны.


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

hello_html_570300a1.png

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

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


2.Методы решения транспортных задач

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

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij ≥ 0, а в маленькие клетки – соответствующие тарифы Cij.

hello_html_m7ec9f2db.png

Затем решение задачи разбивается на два этапа:

  1. Определение опорного плана.

  2. Нахождение оптимального решения путем последовательных операций.


  1. Найдем вначале допустимое (опорное) решение транспортной задачи. Это решение можно найти, используя метод "северо-западного угла" или метод "минимального элемента".


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

Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Хij горизонтальным и вертикальным уравнениям.


Пример 1: Построим опорный план методом северо-западного угла.

hello_html_m5e1ece07.png


Метод наименьшего элемента

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


Пример 2: Построим опорный план методом наименьшего элемента.

hello_html_m5e1ece07.png


3.Метод потенциалов решения транспортных задач

Для проверки построенного опорного плана на оптимальность применяется метод потенциалов.

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

Введем строку потенциалов ui и столбец потенциалов vj. Полагая, что u1=0, а остальные ui и vj найдем так, чтобы

а) для заполненных ячеек выполнялись равенства hello_html_6d956266.gif;

б) для незаполненных ячеек выполнялись равенства hello_html_m79798a92.gif

Критерий оптимальности

Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия hello_html_m24cdf183.gifто Х0 является оптимальным планом транспортной задачи.

Для построения второго опорного плана необходимо применить цикл перерасчёта таблицы – это последовательность ячеек, удовлетворяющая условиям:

  1. Одна ячейка пустая, все остальные занятые.

  2. Любые две соседние ячейки находятся в одной строке или в одном столбце.

Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

В минусовых клетках находят число X = min(Xij). Далее составляют новую таблицу по следующему правилу:

  1. В плюсовых клетках добавляем Х.

  2. Из минусовых клеток вычитаем Х.

  3. Все остальные клетки вне цикла остаются без изменения.


Пример 3: См. пример 2. Проверить построенный план на оптимальность методом потенциалов.

Решение: Возьмем таблицу с построенным планом и добавим еще столбец и строку потенциалов.

По заполненным клеткам вычислим потенциалы по правилу hello_html_6d956266.gif:

Для пустых клеток вычислим их оценки hello_html_m79798a92.gif.

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

hello_html_m46834b54.png


Пример 4: Для плана примера 3 построим цикл перерасчета (в предыдущей таблице) и построим второй опорный план: Заполняем клетку_________

hello_html_m46834b54.png

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

F =

Проверим план на оптимальность методом потенциалов.

План - ______________________________________________________________________________

Построим цикл перерасчета таблицы. Заполняем клетку_________

Третий опорный план:

hello_html_m46834b54.png

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

F =

Проверим план на оптимальность методом потенциалов.

План - ________________________________________

Ответ: _________________________________________________________________________

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________


Контрольные вопросы:

  1. Приведите пример транспортной задачи.

  2. В чем суть метода потенциалов?

  3. Что находится изначально: опорный план перевозок или оптимальный план перевозок?


Задачи на закрепление:

На трех базах А1, А2, А3 имеется однородный груз в количестве а1, а2, а3 условных единиц соответственно. Этот груз требуется перевести в четыре пункта потребления В1, В2 , В3 и В4 в количестве b1, b2 , b3 и b4 условных единиц соответственно. Стоимости перевозок единицы груза от поставщиков потребителям указаны в таблице в матрице стоимостей С. Составить такой план перевозки грузов, при котором транспортные расходы будут наименьшими.

1) а1=140, а2=120, а3=170

b1=98, b2 =122, b3=100, b4=110

hello_html_5f1a8301.gif

2)а1=160, а2=140, а3=100

b1=90, b2 =54, b3=176, b4=80

hello_html_m1825711e.gif



Краткое описание документа:

Данный материал содержит план урока, презентацию и два вида опорного конспекта по теме «Транспорная задача». Создавался как план открытого урока в группе по специальности «ЭКОНОМИКА И БУХГАЛТЕРСКИЙ УЧЕТ (ПО ОТРАСЛЯМ)», дисциплина «Математические методы».План урока содержит историческую справку, указана мотивация к изучению темыи подробное изложение самого материала.Презентация создана для работы на интерактивной доске. Содержит весь теоретический материал по теме, а также разбор решения задачи.Материал предназначен для преподавателей, а также может быть полезен ученикам и студентам при изучении указанной темы.

Общая информация

Номер материала: 101069051119

Похожие материалы