Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Решение транспортной задачи с открытой моделью
Решение транспортной задачи рассмотрим для случая, когда:
Пример 28. В трех хранилищах А1, А2, А3 имеется соответственно 70, 80, 50 т. топлива. Требуется спланировать перевозку топлива четырем потребителям В1, В2, В3, В4, спрос которых равен 50, 70, 40 и 40 т. так, чтобы затраты на транспортировку были минимальны. Стоимость перевозки 1 т указана в табл. 36. Таблица 36
Решение. Поскольку запасы топлива в хранилищах больше спроса потребителей, вводим фиктивного потребителя В5, спрос которого:
а затраты на перевозку для фиктивного потребителя сi5 = 0 (
Исходный опорный план получим по методу минимального элемента. Проверяем m + n – 1 = 3 + 5 – 1 = 7 = 7 выполняется. Определяем потенциалы занятых клеток и находим оценки свободных клеток: S11 = 5 – 3 = 2 > 0; S13 = 3 – 2=1 > 0; S14= 6 – 6 = 0; S23 = 5 – 3 = 2 > 0; S25 = 0 – 1 = –1 < 0; S32 = 4 – 1 = 3 > 0; S34 = 5 – 5 = 0; S35 =0 + 1 = 1 > 0; Только одна оценка S25 < 0; поэтому план перевозки можно улучшить за счет этой клетки (2; 5). Выделяем для нее цикл: λ = min (10; 10) = 10. После смещения по циклу 10 т груза получаем новый план перевозок (табл. 38): Таблица 38
Найдем потенциалы занятых клеток, так как их 6, а должно быть 3 + 5 – 1 = 7, то занимаем клетку, например (2; 2). Подсчитываем потенциалы занятых клеток, составив и решив систему.
Находим оценки свободных клеток: S11 = 5 – 3 = 2 > 0; S13 = 3 – 2 = 1 > 0; S14 = 6 – 6 = 0; S15 = 0 +1 = 1 > 0; S23 = 5 – 3 = 2 > 0; S32 = 4 – 1 = 3 > 0; S34 = 5 – 5 = 0; S35 = 0 + 2 = 2 > 0. Так как все Sij ≥ 0, то план оптимальный, но таких планов будет бесчисленное множество, т. к. S14 = S34 = 0, и поэтому, за счет загрузки клеток (1; 4) и (3; 4), можно получить новые планы, однако значение целевой функции при этом меняться не будет.
Итак, получили оптимальный план. Х*= min Z = Z(X*) = 2 · 70 + 4 · 40 + 7 · 40 + 2 · 10 + 1 · 40 = 640 тыс. руб. При этом 10 т. топлива из хранилища А2 остались нераспределенными.
Задания для самостоятельной работы
Задание 1. На три базы А 1, А 2, А 3 поступил однородный груз в количестве а 1 т. на базу А 1, а 2 т. на базу А 2, а 3 т. на базу А 3. Полученный груз требуется перевезти в пять пунктов: в 1 т. в пункт В 1, в 2 т. в пункт В 2, в 3 т. в пункт В 3, в 4 т. в пункт В 4, в 5 т. в пункт В 5. Стоимость перевозок пропорциональна расстоянию и количеству перевозимого груза. Матрица тарифов и значения а 1, а 2, а 3 и в 1, в 2, в 3, в 4, в 5 – известны. Требуется записать модель и спланировать перевозки так, чтобы их общая стоимость была минимальной.
Задание 2. В каждом из заданий приведена таблица, в клетках которой представлены элементы матрицы С = {Cij}, справа от таблицы – значения величин а i (i = 1,4), внизу – значения величин b j (j = 1,5) транспортной задачи. Решить соответствующую транспортную задачу.
7. Элементы сетевого планирования
Основные понятия При планировании и оперативном управлении сложными комплексами работ, объединенных общностью цели, с успехом используются их графические модели – сетевые графики (сети). С математической точки зрения сетевой график – это связанный орграф без петель и контуров. В настоящее время разработаны специальные математические методы сетевого планирования и управления (СПУ). Основными понятиями СПУ являются работа и событие. Под работой понимаются любые действия (трудовые процессы), сопровождающиеся затратами ресурсов или времени и приводящие к определенным результатам. Под событием понимают результат завершения одной или несколько работ. Событие является предпосылкой для выполнения работ, следующих за ним. Поэтому любая работа на сети может быть определенна двумя событиями, между которыми она находится. Событием же может заканчиваться или начинаться сразу несколько работ. Работы на сети изображают произвольной длины направленными отрезками прямых (иногда дугами), а событие – обычно кружками, в которых указывают порядковый номер или шифр события. У каждого отрезка проставляется время выполнения работы, а иногда и другие числовые характеристики (расход ресурса, количество исполнителей и т. д.). Сетевые графики выполняются с соблюдением определенных правил: 1. Они должны иметь только одно исходное событие (исток сети J) – начало работ комплекса; 2. Они должны иметь только одно завершающее событие (сток сети S) – окончание всех работ комплекса; 3. Прежде чем строить сеть, надо составить подробный список работ комплекса. В отношении каждой работы выяснить: а) ее связи с другими работами; б) ее место в комплексе; в) ее конечные результаты (события). После того, как описанный подготовительный этап будет закончен, приступают к построению сети. Пример 29. По данным табл. 39 построить сеть. Таблица 39
Решение: работы а1, а2, а3 не имеют предшествующих, поэтому реализация комплекса начинается с этих работ и изображаем их прямыми, выходящими из одного события 1 (исток J сети) (рис. 18).
Рис. 18 Дуги а1, а2, а3 и так далее располагаются произвольно. Работе а4 предшествует работа а1. Далее надо изобразить работы а5 и а6, им предшествуют одни и те же работы а1 и а2. Во избежание путаницы на сетях не рекомендуется изображать параллельными дугами одновременно выполняемые работы. В подобных случаях вводятся дополнительные события и фиктивные работы (нулевой продолжительности), которые изображаются штриховыми линиями. Их назначение – показать, что данная работа не может быть выполнена ранее какого-либо события или работы. Учитывая это, введем фиктивную работу, соединив событие 2 работы а1 с событием 3 работы а2. После этого изобразим а5 и а6 дугами, выходящими из события 3, причем дуги а3, а5 должны прийти в одно событие (работа а7 начинается после них), такое событие уже есть – это 4, а дуги а4, а6 аналогично идут в событие 5. Так как работа а8 может быть начата только после работ а4, а6 и а7, поэтому работу а7 направим в событие 5. И, наконец, дуги а8 и а9 моделируют заключительные работы комплекса, поэтому сведем их в одно завершающее событие 6 (сток сети S).
Замечание. Правильность нумерации событий (вершин графа) можно проверить алгоритмом Фалкерсона (упорядочить граф). 7.2. Временные параметры сети (рассмотрим на примере) Пример 30. Сеть некоторого комплекса построена и известна продолжительность каждой работы (в днях). Определить за какое минимальное время можно выполнить все работы комплекса? Решение. Рассмотрим все пути от J до S (рис. 19).
Рис. 19 1) L 1: 1 – 2 – 4 – 5 => t (L 1 ) = 2 + 1 + 5 = 8; 2) L 2: 1 – 3 – 4 – 5; => t (L 2 ) = 4 + 3 + 5 = 12; 3) L 3: 1 – 3 – 5 => t (L 3 ) = 4 + 2 = 6. Наиболее продолжительным оказался путь L 2. Его называют критическим. Он и определяет максимальное время выполнения всех работ данного комплекса. Это максимальное время называют критическим сроком и обозначают t КР. Итак t КР = 12. Работы и события, лежащие на критическом пути называются критическими, остальные работы и события сети – некритическими. Если выполнение какой-либо критической работы будет задержано, это вызовет задержку выполнения всего комплекса на тот же срок. Однако, некритические работы допускают некоторое запаздывание их выполнения без нарушения критического срока. Чтобы определить время, на которое можно задержать выполнение некритических работ, введем понятие резерва времени событий и работ.
 – мно-
жество работ, входящих в j -событие. Тогда имеем tp (1) = 0, tp (5) = t КР = 12 (и вообще tp (J) = 0, а tp (S) = t КР). Тогда tp (2) = 2 или tp (2) = 0 + 2 = tp (1) + t (1, 2), где t (1, 2) – время выполнения работы (1 – 2). Аналогично tp (3) = 0 + 4 = tp (1) + t (1,3). Для события 4: по работе (2 – 4) имеем tp (2) + t (2, 4) = 2 + 1 + 3, а по работе (3 – 4) => tp (3) + t (3, 4) = 4 + 3 = 7, так как к моменту tp (4) должны закончиться все предшествующие работы, тогда tp (4) = max (tp (2) + t (2, 4); tp (3) + t (3, 4)) = max (3; 7) = 7. i = 2, 3 Итак, если событием j заканчивается одна работа (i, j), то tp (j) равно сумме tp (i) – раннего срока свершения ее начального события и tp (i, j) – продолжительность этой работы. Если же событием j заканчивается несколько работ, то по каждой работе находится свой ранний срок, а искомый tp (j) будет максимальной из них. Поздним сроком t п (i) свершения события i назовем самый поздний момент времени, после которого останется ровно столько времени, сколько необходимо для завершения всех работ, следующих за этим событием.
 – множество работ,
выходящих из i -события, t п (j) – поздний срок свершения конечного события (i, j). Поздний срок t п (J) = 0, t п (S) = tp (S) = t КР. В нашем примере t п (5) = 12.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Последнее изменение этой страницы: 2020-11-11; просмотров: 236; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.142.96.146 (0.102 с.) |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
.
).
