Математическая модель транспортной задачи
ОДп.02.
Информатика и ИКТ
Автомеханик
УРОК № 69
Группа: 2
Дата: 24.12.2021 г.
Преподаватель: Л.Н.Иванова
Тема урока: ТРАНСПОРТНАЯ ЗАДАЧА. ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ. ТЕОРИЯ ИГР. ПРИМЕР МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ДЛЯ ЭКОЛОГИЧЕСКОЙ СИСТЕМЫ
Цель: изучить понятие транспортной задачи и методы ее решения, задачи теории расписаний. Теория игр. Пример математического моделирования для экологической системы
На прошлом занятии мы рассмотрели общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые в силу своей структуры допускают решения более простыми методами. Сегодня мы остановимся на одной из них – так называемой, транспортной задаче.
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью.
Мы рассмотрим классическую транспортную задачу – это задача об оптимальном плане перевозок продукта (-ов) из пунктов отправления в пункты потребления, встречается чаще всего в практических приложениях линейного программирования.
Где могут пригодиться вам полученные сегодня знания?
На каждом предприятии есть отдел логистики. Его работа заключается в организации рационального процесса продвижения товаров от производителей к потребителям, создания инфраструктуры товародвижения.
Логистов иначе называют «транспортными богами».
|
|
|
Сегодня на уроке нам необходимо разобрать транспортную задачу, научиться строить математическую модель этой задачи и решать ее.
Как всегда, изучение теоретического материала будем сопровождать примерами для лучшего понимания темы.
Но прежде, чем перейти к самой задаче, обратимся к истории:
Проблема транспортной задачи была впервые формализована французским математиком Гаспаром Монжем в 1781 году, который выполнил работу о наиболее экономном способе перемещения масс для строительства военных укреплений.
А основное продвижение было сделано советским математиком и экономистом Леонидом Канторовичем.
В 1939 году к 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”.
|
|
|
Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.
В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за “вклад в разработку теории и оптимального использования ресурсов в экономике”.
ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ
Однородный груз, имеющийся в 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).
Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются, а суммарные транспортные расходы минимальны.
|
|
|
Замечание:
Задача в данной формулировке, когда выполняется равенство
называется закрытой.
Чтобы мы могли решать данную задачу нам необходимо записать ее математическую модель.
Математическая модель транспортной задачи
Наша задача найти значения х, которые удовлетворяют системе ограничений и целевой функции.
При этом нам понадобятся несколько определений:
Определение: Построенный план называется опорным, если в нем отличны от нуля m+n-1 базисных перевозок, а остальные перевозки равны 0.
Определение: Опорный план называется оптимальным, если он приводит к минимальной суммарной стоимости перевозок.
Дата добавления: 2022-01-22; просмотров: 17; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!