Презентация на тему "Транспортная задача"

Презентация: Транспортная задача
Включить эффекты
1 из 66
Ваша оценка презентации
Оцените презентацию по шкале от 1 до 5 баллов
  • 1
  • 2
  • 3
  • 4
  • 5
5.0
1 оценка

Комментарии

Нет комментариев для данной презентации

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


Добавить свой комментарий

Аннотация к презентации

Интересует тема "Транспортная задача"? Лучшая powerpoint презентация на эту тему представлена здесь! Данная презентация состоит из 66 слайдов. Средняя оценка: 5.0 балла из 5. Также представлены другие презентации по математике. Скачивайте бесплатно.

  • Формат
    pptx (powerpoint)
  • Количество слайдов
    66
  • Слова
    математика
  • Конспект
    Отсутствует

Содержание

  • Презентация: Транспортная задача
    Слайд 1

    ТРАНСПОРТНАЯ ЗАДАЧА

    Лекции 10,11

  • Слайд 2

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

  • Слайд 3

    Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А1, А2,…, Аm в nпунктов назначения B1, B2,…,Bn. При этом в качестве критерия оптимальности берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

  • Слайд 4

    Рассмотрим транспортную задачу, в которой в качестве критерия оптимальности берется минимальная стоимость перевозок всегогруза. Обозначим через тарифы или стоимости перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через  – запасы груза в i-м пункте отправления, через  – потребности в грузе j-ым пунктом назначения, через  – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения (перевозки).

  • Слайд 5

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

    Найти при ограничениях

  • Слайд 6

    Первое ограничение означает, что все потребности должны быть удовлетворены , а второе - , что все запасы должны быть перевезены.

  • Слайд 7

    Определение. Всякое неотрицательное решение системы ограничений транспортной задачи, определяемое матрицей размераm×n , называют допустимым решением (или планом) транспортной задачи.

  • Слайд 8

    Определение. План , при котором целевая функция принимает минимальное значение, называется оптимальным.

  • Слайд 9

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

  • Слайд 10

    Транспортная таблица

  • Слайд 11

    Необходимое и достаточное условие разрешимости транспортной задачи

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

  • Слайд 12

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

  • Слайд 13

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

  • Слайд 14

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

  • Слайд 15

    Пример

  • Слайд 16

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

  • Слайд 17

    А целевую функцию составили по матрице С- матрице тарифов перевозок.

  • Слайд 18

    Пример. Задача организации оптимального снабжения .

    Три фермерских хозяйства ежедневно могут доставлять в город соответственно 60, 60 и 50 ц молока для обеспечения пяти торговых точек : Стоимость перевозки 1ц молока и потребности торговых точек в молоке указаны в таблице

  • Слайд 19

    Таблица

  • Слайд 20

    Экономико-математическая модель задачи.

    Переменные : - количество молока , поставляемое i-м фермерским хозяйством в j-ю торговую точку. Целевая функция –суммарные транспортные издержки, которые необходимо минимизировать

  • Слайд 21

    Эта задача является задачей открытого типа, так как запасы молока у фермерских хозяйств (поставщиков) больше потребностей в молоке у торговых точек. В этом случае изменяется вид системы ограничений.

  • Слайд 22

    Функциональные ограничения:

    По поставщикам (их 3) по потребителям (их 5)

  • Слайд 23

    Этапы решения транспортной задачи

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

  • Слайд 24

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

  • Слайд 25

    Определение исходного допустимого решения

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

  • Слайд 26

    2. Метод «наименьшей стоимости» Метод заключается в том, что заполнение клеток таблицы начинают с клетки, имеющей наименьшую стоимость перевозки. Если таких клеток несколько, то следует выбрать любую из них.

  • Слайд 27

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

  • Слайд 28

    Минимальный тариф, равный 1 , находится вклетке . Положим . Запишем это значение в соответствующую клетку и временно исключим из рассмотрения строку . Потребности пункта назначения считаем временно равными 30 ед.

  • Слайд 29

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

  • Слайд 30

    Временно исключим из рассмотрения столбец и будем считать запасы пункта равными 120 ед. После этого рассмотрим оставшуюся часть таблицы с двумя строками и и тремя столбцами , и . В ней минимальный тариф находится в клетке на пересечении строки и столбца и равен 3.

  • Слайд 31

    Заполним описанным выше способом эту клетку и аналогично заполним ( в определенном порядке) клетки, находящиеся на пересечении строки и столбца .

  • Слайд 32

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

  • Слайд 33

    Условие невырожденности плана

    Если число заполненных клеток равно m + n – 1, то план является невырожденным. Если число заполненных клеток меньше этого значения, то план (решение) называется вырожденным. В случае вырожденности плана условно считают одну (или несколько) из пустых клеток занятой, записывая в нее нулевую перевозку так, чтобы число занятых клеток стало равным m + n – 1.

  • Слайд 34

    В нашей задаче число заполненных клеток равно m + n – 1=3 + 4 – 1 = 6, а пустых клеток – m × n – (m + n – 1), где m – количество пунктов отправления, n – количество пунктов назначения, что в нашем случае 3 × 4 – 6 = 6. Значит, найденный план является невырожденным.

  • Слайд 35

    Метод потенциалов проверки решения на оптимальность

    Предположим, что каждый пункт отправленияAi вносит за перевозку единицы груза какую-то сумму , а каждый пункт назначения вносит сумму . Эти платежи передаются некоторому третьему лицу, например, перевозчику. Величины и свяжем равенствами , где  – тарифы для базисных клеток.

  • Слайд 36

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

  • Слайд 37

    Обозначим через , где назовем псевдостоимостями или косвенными стоимостями (тарифами). Псевдостоимости находятся для всех свободных клеток. Платежи и не обязательно должны быть положительны, поскольку не исключено, что «перевозчик» сам платит тому или иному пункту какую-то премию за перевозку.

  • Слайд 38

    Теорема «о платежах».

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

  • Слайд 39

    Теорема оптимальности.

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

  • Слайд 40

    Пример

    Найти опорное решение методом минимальной стоимости и проверить оптимальность решения методом потенциалов.

  • Слайд 41
  • Слайд 42
  • Слайд 43

    Находим потенциалы базисных клеток

  • Слайд 44

    Положим и решим систему. Получим Найдем псевдостоимости пустых клеток План перевозок оптимален

  • Слайд 45

    Пример 2.

    На складах имеются запасы продукции 90, 400 и 110 тонн соответственно. Потребители должны получить эту продукцию в количествах 140, 300 и 160 тонн соответственно. Найти такой план закрепления поставщиков к потребителям, при котором суммы затрат на перевозки минимальны.

  • Слайд 46

    Расходы на перевозки 1 т продукции заданы матрицей (у.е.) Сумма потребностей и сумма запасов равны 140+300+160=90+400+110=600. Модель закрытая.

  • Слайд 47
  • Слайд 48

    План

  • Слайд 49

    2)Проверим план на оптимальность методом потенциалов. В таблице занято клеток Для них найдем потенциалы.

  • Слайд 50

    Положим Решим систему:

  • Слайд 51

    Внесем в таблицу потенциалы занятых клеток

  • Слайд 52

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

  • Слайд 53

    3)Переход к другому решению. Перераспределим грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а занятая- свободной. Для свободной клетки с отрицательной оценкой строится цикл(цепь, многоугольник), все вершины которого, кроме одной находятся в занятых клетках. Углы прямые, число вершин четное

  • Слайд 54

    Около свободной клетки цикла ставится (+), а затем поочередно(-) , (+).У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+) и отнимают от грузов у вершин со знаком (-). В результате перемещения получают новый опорный план. Это решение проверяют на оптимальность и т. д. до тех пор ,пока не получится оптимальное решение.

  • Слайд 55
  • Слайд 56
  • Слайд 57
  • Слайд 58

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

  • Слайд 59

    Потенциалы заполненных клеток

  • Слайд 60

    Оценки свободных клеток План не оптимален, т.к. оценка клетки (21) отрицательна.

  • Слайд 61
  • Слайд 62
  • Слайд 63

    Новый план Снова проверяем его на оптимальность. Для занятых клеток Находим

  • Слайд 64

    Для свободных клеток псевдостоимости равны

  • Слайд 65

    Оценки свободных клеток

  • Слайд 66

    Все оценки положительны, поэтому план оптимален. Ответ: . При этом По сравнению с первоначальным планом расходы уменьшились на величину 1610-1280=330у.е.

Посмотреть все слайды

Сообщить об ошибке