Математические модели решений организационно-экономических задач производства 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Математические модели решений организационно-экономических задач производства



 

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

Изучение сетевых моделей началось в 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 с.)