Решить задачу

[web developer]

Дискретная оптимизация
Цель: Решить задачу динамического программирования. Задача замены оборудования. Автоматизировать решение задачи на одном из языков программирования

Краткая информация о теории графов. Теория графов – это одна из наиболее бурно развивающихся отраслей математики. Сложно назвать совре-менную область исследований человека, где используемый математический ап-парат обходился бы без графов. В виде графов можно, например, интерпрети-ровать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей.
Графы используются при проектировании электронных схем и схем управления, при исследовании автоматов, логических цепей, блок - схем про-грамм, в химии, биологии, в теории расписания, теории управления и дискрет-ной оптимизации.
Определение графа. Рассмотрим конечное множество , и множество всех его 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