Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Математические модели решений организационно-экономических задач производства
В области машиностроения наиболее часто встречающимся приложением алгоритмов и теоретических методов, рассматриваемых теорией графов, является решение задач о потоках в сетях (сетевые модели). Изучение сетевых моделей началось в 40-х годах XX в. в связи с транспортными задачами, т.е. задачами о прикреплении поставщиков к потребителям, минимизирующем суммарные расходы по перевозке. Разновидностью таких задач являются часто встречающиеся на практике задачи максимизации потока некоего продукта между двумя заданными узлами сети при условии, что поток вдоль каждой дуга ограничен. В этом разделе формулируются основные принципы и излагается метод решения указанного класса сетевых задач.
Решение задачи о максимальном потоке Задача максимального потока формулируется следующим образом. Пусть каждой дуге () сети G = (N, А) поставлено в соответствие некоторое неотрицательное вещественное число , называемое пропускной способностью дуги. Выделим на сети два узла: и ,которые назовем источником и стоком соответственно. Тогда потоком величины F из в называется функция х, отображающая А на множество неотрицательных вещественных чисел и удовлетворяющая условиям где А i * - множество дуг с начальным узлом , а Ai - - множество дуг с конечным узлом Величина , называется потоком по дуге (). Суммарный поток из каждого промежуточного узла равен 0, а суммарный поток в сток равен F. Из уравнения следует, что поток по каждой дуге не превышает ее пропускной способности. Максимальным потоком из в назовем такую функцию х,удовлетворяющую представленным уравнениям, для которой величина F максимальна. Пример потока в сети дан на рис., на котором первое число, поставленное в соответствие каждой дуге – ее пропускная способность, а второе – поток по дуге.
Рис 5.2 Поток в сети (величиной F = 5)
Физически поток можно представить как количество условного «груза», перевозимого из вершины с номером i в вершину с номером j, а суммарный поток F – как количество груза, перевозимого из источника в сток. Транспортная задача Рассматривается случай нескольких истоков и стоков с ограничением на их мощности. Пусть имеется т сталепрокатных заводов х 1, х 2, …, хт, и каждый из заводов х i может производить с (х j) тонн проката в неделю. Стоимость перевозки одной тонны из х i в yj равна .
Сколько проката надо производить на каждом заводе и куда его направлять, чтобы с минимальными расходами удовлетворить потребности всех металлообрабатывающих предприятий? В терминах сетевой модели проблема может быть сформулирована как задача нахождения максимального потока минимальной стоимости в сети, где первые числа указывают пропускную способность, а вторые – стоимость каждой дуги.
Вопросы для самопроверки 1. Как изображается граф? 2. Что определяют понятия: ребро, дуга, путь? 3. Как изображается вершина графа, ребро графа? 4. Как называются графы, отличающиеся только номерами вершин и ребер? 5. Какой граф называется мультиграфом? 6. Какой маршрут в графе называют циклом? 7. Какой маршрут в графе называют цепью? 8. Как называют вершины графа, которые не принадлежат ни одному ребру? 9. Как называют связной граф без циклов? 10. Изобразите полный граф и псевдограф.
|
|||||
Последнее изменение этой страницы: 2021-01-14; просмотров: 80; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.97.189 (0.005 с.) |