Теория

Математическое программирование занимается изучением экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, … , xn ) при ограничениях gi ( x1, x2, … , xn ) * bi , где gi — функция, описывающая ограничения, * — один из ..

Далее

Задачи размещения связаны с решением проблем наилучшего расположения в определенных регионах таких систем обслуживания, как торговые центры, посты пожарной охраны, фабрики, аэропорты, склады и т. д. Математическая структура задачи размещения определяется конфигурацией области допустимых точек и способом оценки качества размещения. Вследствие этого существует много разнообразных задач размещения, и техническая литература изобилует методами их решения. В ..

Далее

Алгоритм Литтла применяют для поиска решения задачи коммивояжера в виде гамильтонова контура. Данный алгоритм используется для поиска оптимального гамильтонова контура в графе, имеющем N вершин, причем каждая вершина i связана с любой другой вершиной j двунаправленной дугой. Каждой дуге приписан вес Сi,j, причем веса дуг строго положительны (Сi,j≥0). Веса дуг образуют матрицу стоимости. Все элементы ..

Далее

 Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм,. предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи. Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны m вершин, ближайших к вершине ..

Далее

Табличный симплекс-метод Метод искусственного базиса Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Данный метод, имеющий несколько различных форм (модификаций), был разработан в 1947 году Г. Данцигом. Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях. Заметим, что каждое из линейных ..

Далее

Алгоритм Флойда является одним из методов поиска кратчайших путей в графе. В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе. Конечно эта задача может быть решена и многократным применением алгоритма Дейкстры (каждый раз последовательно выбираем ..

Далее

Вспомним, что центром является любая вершина х с наименьшим значением МВВ(х) (макимальное расстояние вершина-вершина), т. е. центр — это любая вершина х, такая, что расстояние от нее до наиболее отдаленной вершины минимально. МВВ(х) =min{МВВ(i)} Центр отыскивается как один из элементов матрицы DN, значение i, j-го элемента которой — di,j есть кратчайшее расстояние от вершины i ..

Далее

Главный центр — это произвольная вершина х с минимальным среди всех вершин значением МВД(х) -максимальное расстояние вершина-дуга, т. е. главным центром является такая вершина х, что расстояние от х до наиболее удаленной точки на дугах графа минимально. МВД(x)=min{МВД(i)} Для накождения главного центра необходимо в матрице D’ выбрать строку с наименьшим максимальным значением ее элемента. Эта ..

Далее

Необходимо найти все кратчайшие пути от вершины №1 для графа, представленого на рисунке Составим матрицу длин кратчайших дуг для данного графа. ∞ 10 18 8 ∞ ∞ 10 ∞ 16 9 21 ∞ ∞ 16 ∞ ∞ 15 ∞ 7 9 ∞ ∞ ∞ 12 ∞ ∞ ∞ ∞ ∞ 23 ∞ ∞ 15 ∞ ..

Далее

Абсолютная медиана — это такая точка на дуге графа, что сумма расстояний от нее до всех вершин графа минимальна. Теорема. В графе всегда существует вершина, являющаяся абсолютной медианой. Доказательство. Рассмотрим функцию, характеризующую расстояния точка — вершина d(f— (r, s), j) для каждой вершины j Вогнутые функции расстояния В графическом представлении эта функция имеет вид кривой, ..

Далее