|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
24.11.2022, 16:55 | #1 |
Пользователь
Регистрация: 04.06.2022
Сообщений: 62
|
Решить задачу
Дискретная оптимизация
Цель: Решить задачу динамического программирования. Задача замены оборудования. Автоматизировать решение задачи на одном из языков программирования Краткая информация о теории графов. Теория графов – это одна из наиболее бурно развивающихся отраслей математики. Сложно назвать совре-менную область исследований человека, где используемый математический ап-парат обходился бы без графов. В виде графов можно, например, интерпрети-ровать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей. Графы используются при проектировании электронных схем и схем управления, при исследовании автоматов, логических цепей, блок - схем про-грамм, в химии, биологии, в теории расписания, теории управления и дискрет-ной оптимизации. Определение графа. Рассмотрим конечное множество , и множество всех его 2-х элементных подмножеств . Для произвольных подмножеств называем термином «граф» (неориентированный граф) всякую пару . Элементы называются вершинами, элементы - ребра¬ми. Число называется порядком или размерностью графа (мощность графа). В графе две вершины смежные, если они соединены ребром (дугой). Два ребра и называются смежными, если они име-ют общую вершину . Вершина , и ребро е называются инцидентными, если , является концом ребра е, т.е. . Таким образом, смежность есть отношение между однородными элемен-тами графа, а инцидентность - между разнородными элементами. Графическое изображение графа , где и на рисунке 1. Рисунок - 1 Граф называется полным, если любые две его вершины смежны, т.е. . Полный граф порядка п обозначается символом число ребер в полном графе . Граф называется пустым, если в нем нет ребер, т.е. . Если в графе ребро имеет направление, то такой граф называется ориентированным, иначе неориентированным. В ориентиро-ванном графе ребра называют дугами, а в неориентированном графе линии со-единяющие вершины графа называют ребрами. Матрицы можно ассоциировать с графом. Так, матрица смежности графа определяется согласно правила (см. рис.2): Рисунок - 2 Например: Матрица инцидентности графа определяет-ся согласно правила: Рисунок - 3 Путь – это последовательность дуг (в орграфе), такая, что конец одной дуги является началом другой дуги. Простой путь – путь, в котором ни одна дуга не встречается дважды. Длиной пути называется число дуг пути или сумма длин его дуг, если последние заданы. Задача о замене оборудования (ЗО) состоит в определении оптималь-ных сроков замены старого оборудования: станков, машин, производственных зданий и т.п. Термин «старое» или «старение» оборудования включает его фи-зический и моральный износ. По причине старения растут производственные затраты, затраты на ремонт и обслуживание, снижаются производительность труда и ликвидная стоимость. В задачах ЗО критерием оптимальности являют-ся либо прибыль от эксплуатации оборудования, либо суммарные затраты на замену (т.е. покупку-продажу) и эксплуатацию в течение планируемого перио-да. Значение этих критериев зависит от основного параметра, которым в зада-чах ЗО является возраст оборудования. Для представления математической модели задачи ЗО вводятся следую-щие обозначения: -протяженность планового периода, единицей измерения которого яв-ляется единичный отрезок (год, полугодие и т.д.); - индекс, которым занумерованы начала этих отрезков, ; решение о замене, т.е. продаже старого и покупка нового автомобиля принимается в календарные моменты , ; - ограничение сверху на срок эксплуатации автомобиля, т.е. если ав-томобиль куплен в момент , то он заменяется на новый не позже, чем в мо-мент времени ; - стоимость нового автомобиля в начале i-го года, точнее, в начале i-го единичного отрезка времени; - эксплуатационные расходы в течение k-го года; - ликвидационная стоимость автомобиля в начале j-го года при условии, что он куплен в начале i-го года, например, может вычисляться по формуле - суммарные затраты на покупку, содержание и ликвидацию авто-мобиля в случае, если он покупается в начале года i и ликвидируется в начале года ; все эти суммарные затраты вычисляются по формуле Задача о ЗА состоит в том, чтобы указать такие лет замены автомобиля, для которых суммарные за лет за-траты были бы минимальными. При этом учиты-вается условие: автомобиль может находиться в эксплуатации не более лет, т.е. для всякой пары индексов вида должно выполняться неравенство , , , . 1. При Т=8, =4 заданных вариантов значений параметров Рi, mk и Sij вычис-лить суммарные затраты С(i,j) для всех пар i, j таких, что и . 2. Построить 9-ти вершинный орграф , приписав его дугам со-ответственно веса С(i,j). 3. Применив алгоритм Дейкстры, найти оптимальный план покупок и замены автомобиля (затраты берутся в $США). Таблица значений Рi- стоимость нового автомобиля (в тыс.$США). ГОДЫ вариант 8 8 580 616 677 740 854 900 992 1090 |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Помогите решить задачу на с#,уже час ломаю голову,не могу решить. | KeyJW | Помощь студентам | 1 | 09.11.2022 22:15 |
Помогите решить задачу,пожалуйста!!!вторую часть не могу решить. | Родион Афанасьев | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 03.03.2018 19:44 |
решить задачу | Рон99 | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 01.11.2011 21:23 |
Как решить задачу? | Annneet | Общие вопросы C/C++ | 1 | 18.10.2011 19:19 |
Как решить задачу? | BETONOMESHALKA | Общие вопросы Delphi | 8 | 04.11.2007 00:19 |