All posts by admin

На современном этапе развития общества происходит постоянное усложнение и развитие техники, технологического производства, увеличение масштабов и темпов производства, планирование и управление. Возникающие при этом задачи требуют новых современных методов решения. Они имеют большую размерность и могут быть решены в реальных условиях только с применением ЭВМ. Изучением этих методов и задач занимаются:

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

-Постановка задачи: сначала формулируется заказчиком и записывается словесно. Эта постановка не является окончательной. Операционная группа проводит обследование и в результате постановка задачи корректируется.

Любые операционные системы обязательно содержат: 1. Лицо, которое стремится к достижению определенной цели 2. Должно существовать некоторое множество достиг. цели. 3. Существовать некоторая обстановка во время которой проводятся операции 4. Известны исходы решения 5. Существуют правила выбора решения

1.При решении различных производственных, экономических, социальных и других задач часто приходиться учитывать несколько критериев эффективности. Например, при проектировании прибора необходимо как правило учитывать 2 условия – чтобы прибор был надёжен и стоимость минимальна. Ясно что эти 2 критерия противоречивы. Прибор построенный с учётом максимальной надёжности будет дорогим и наоборот.

Рассмотрим мат. Модель линейной многокритериальной задачи. В методе свёртывания критериев задаются некоторые числа так называемые веса учитывающие степень важности некоторого критерия и затем строится обобщённый критерий и затем строим обобщённый критерий Z и решаем задачу в которой для этого критерия Z будем искать max при (1) и (2).

1.Задача оптимального плана производства и двойственная к ней – задача нахождения оптимальных оценок ресурсов. Запишем мат. Модель задачи оптимального плана производства. З.1)

В своей практической деятельности человек часто встречается с задачами, в которых переменные по своему физическому или экономическому смыслу могут принимать только целочисленные значения. Например, в задачах о выпуске неделимой продукции, которая не может выражаться дробными числами. В мат. моделях таких задач необходимо вводить дополнительные условия, требования цело численности переменных. Если все остальные ограничения и целевая Читать далее

Для решения ЗЛЦП существует 3 группы методов: 1) Методы отсечения или отсекающих плоскостей 2) Комбинаторные методы 3) Эвристические методы

Рассмотрим математическую модель ЗЛЦП с неделимостями. Для функции (1) (найти max) при условии

Иерархической является система, элементы которой распределены по уровням так, что подсистема более высокого уровня доминирует определенным образом над подсистемами более низкого уровня. Например, система управления промышленностью построена по иерархическому принципу.

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

Коммивояжер (К) должен обойти N городов и вернуться в исходный город. Пронумеруем эти города 1,2….N. Известна матрица расстояний L=(lij)NN так как К из города i переходит в другой город j, то lij не существует. Если из города i нельзя переход в j то расстояние lij=?. В общем случае lij? lji. Будем предполагать что К находится Читать далее

Множество точек на плоскости, соединенных отрезками, будем называть графом. Точки на плоскости называют вершинами графа и их будем обозначать кружком на плоскости. Отрезки линий, соединяющих вершины, будем называть ребрами, если на отрезке не указано направление (т.н. неорентированый отрезок), и дугами, если на отрезке указано направление (ориентированный отрезок). Если в графе отрезки не ориентированны (ребра), то Читать далее

Для любой сети G=(J, U) с одним источником S и одним стоком t величина максимального потока из S в t равна пропускной способности минимального разреза, отделяющего S от t. Дугу, входящею в некоторую цепь в сети, будем наз. прямой, если ее направление совпадает с направлением обхода вершин, и обратной – в противном случае. Дуга (i, Читать далее

Рассмотрим сеть G=(J, U) с одним источником S и одним стоком t и для всех дуг сети (i, j) заданы их пропускные способности Cij. Найти величину максимального потока в сети, который можно направить из источника в сток и минимальный разрез в сети. Метод Форда – Фалкерсона называют еще и методом пометок. Рассмотрим его по шагам.

Пусть из города S в город T необходимо доставить некоторый груз за кротчайшее время. Города S и T связаны между собой сетью дорог, проходящих через перевалочные пункты. Изобразим город S и T и перевалочные пункты в виде вершин некоторого графа. И каждую пару вершин i и j связываем дугой, если между ними существует прямая связь, Читать далее

Рассмотрим сеть G=(J,U) с одним источником S и одним стоком T. В сети n вершин. В вершину S не входит ни одна дуга, а из вершины T не выходит ни одна дуга. Пронумеровать в такой сети вершины правильно необходимо, чтобы в сети не было контуров. Рангом вершины i назовем max число дуг в пути, которое Читать далее

Рассмотрим ориентированную сеть G=(I,U) без контуров, с одним источником s и стоком t. Числа на дугах lij означают их длину. найдем следующим образом: источнику т.е. вершине 1 присваиваем метку Е1=0, число 0 означает, что это кратчайший путь до источника. Вершине 2 присваиваем метку Е2=Е1+l12 . Далее последовательно будем присваивать метки вершинам 3,4,…,n по правилу: Еj=min(Ei+lij), Читать далее

Рассмотрим задачу: имеется n городов A1, … ,An, которые необходимо связать между собой сетью шоссейных или железных дорог. Для каждой пары городов AiAj известна стоимость Cij соответствующей магистрали (Сij можно рассматривать как расстояние между городами Ai и Aj). Задача состоит в том, чтобы построить самую дешевую из сетей дорог, которые связывает все эти города. Вместо Читать далее

В различных сферах произв., научной и общественной деятельности часто приходится решать задачи рационального планирования большого комплекса работ. Такие задачи возникают при разработке проектов строительства крупных промышленых комплексов, при планировании и подготовке к запуску космической ракеты, при решении крупной исследовательской проблемы, например по созданию комплекса вычислительной техники, при организации и проведении научных симпозиумов, спортивных соревнований и Читать далее

Это схематическое изображение планируемого процесса, проекта или разработки, отражающее технологическую взаимосвязь и последовательность выполняемых работ. С математической точки зрения сетевой график – это ориентированный граф без контуров. Вершины графа это события, а дуги – работы. Работы бывают трех типов: действительные, фиктивные и ожидания.

1. Пусть имеется следующий фрагмент сетевого графика и известно, что работы U2 и U3 можно начинать до полного окончания работы U1 , т. е. для начала выполнения работ U2 и U3 необх. лишь частичное выполнение работы U1 , а для начала выполнения работы U4 необходимо полное выполнение работы U1 . В этом случае работу U1 Читать далее

Т.к. для событий сетевого графика можно найти их ранее и позднее сроки свершения, то очевидно, что начало и окончание работ тоже могут изменятся в определенных пределах. Действительно для каждой i,j можно найти ее решение TijРН и ее позднее TijПН начало. И ее ранее и позднее окончание (TijРО TijПО). Очевидно, что ранее начало ij равно раннему Читать далее