Предмет и задачи исследования операций

↑

Стр 1 из 28Следующая ⇒

1. Предмет и задачи исследования операций

Мат. Программирование представляет собой класс методов предназначенных для отыскания экстремума заданной функции при определённых ограничениях.

В общем виде задача мат. программирования записывается следующим образом: определить такие значения переменных X=(x₁,x_{2, …,} x_n), которые доставляют экстремальные значения ф-и z=f(x₁,x_{2, …,} x_n)->max (min) (1) и удв. ограничениям g_i=(x₁,x_{2, …,} x_n)<= b_i (2).

X – представляет собой различные варианты решений из которых нужно выбрать наилучшее.

(1) – целевая функция.

Возможные решения X также называются планами.

Набор переменных X удв. всем соотношения системы (2) назыв. допустимым планом.

Допустимое решение X^* называется ОП если оно доставляет экстремум целевой ф-и.

В зависимости от ф-и f, g_i выделяют:

1) Задачи лин. программирования если все ф-и f и g_i явл. линейными ф-ми.

2) если хотя бы одна из ф-й f или g_i явл. не линейной то задача (1), (2) называется задачей нелинейного программирования.

3) если на переменную x_i наложено условие дискретности то задача дискретного программирования.

Типичные классы задач:

1) Задача распределения ресурса.

2) Задача управления.

3) Ремонт и замена оборудования

4) Задача массового обслуживания

5) Теория расписаний

6) Задача сетевого планирования и т.д.

2.  Задача о назнач. Венгерский метод (пост. задачи, мат. мод, идея и алгоритм

Постановка задачи: пусть имеется п видов работ и п исполнителей, каждый из которых может выполнить любую из этих работ; c_ij— эф­фективность выполнения i-ой работы j-ым исполнителем, i,j = 1,n. Из параметров c_ij можно составить (п  п) матрицу стоимостей (эффективностей) С. Найти такую расстановку исполнителей, чтобы суммарный эффект их труда был наибольшим.

Математическая модель задачи: введем переменные

Получаем задачу:

          (1),    (2),

Ограничения (1) означают, что на каждую работу должен быть на­значен только один исполнитель. Ограничения (2) означают, что каждый исполнитель выполняет только одну работу.

Определение. Система нулевых элементов матрицы, обладающая тем свойством, что никакая пара из них не лежит в одной строке или в одном столбце, называется системой независимых нулей (СНИ).

Идея метода.

Венгерский метод состоит в преобразовании исходной задачи с матрицей С в эквивалентную ей задачу минимизации с матрицей С". Если в матрице С" имеется система из п независимых нулей, то решением задачи будет матрица X, у которой на местах, соответствующим независимым нулям, стоят 1, а остальные элементы являются нулевыми. Таким образом алгоритм направлен на построение СНН путем эквивалентных , преобразований матрицы С".

Алгоритм метода.

0. Преобразуем матрицу С в матрицу С" следующим образом:

a)  ;

b) 

Приходим к задаче:

1. Строим систему независимых нулей, помечая их *. Пусть число таких элементов равно k. Если k=n, то пишем ответ — матрицу X и L(X). Если , то помечаем столбцы, содержащие 0* сверху знаком «+». Все элементы в этих столбцах назовем выделенными элементами (ВЭ) (аналогично, так назовем элементы и в строках со знаком «+»).

2. Среди невыделенных элементов ищутся нулевые. Если они есть, то помечаем один из них 0' и переходим на 3. Если нет, то — 5.

3. Если в строке, содержащей только что найденный (У нет 0*, то — переход на 4. Иначе с соответствующего столбца снимается знак выде­ления и выделяется строка, содержащая 0' и осуществляется переход на 2.

4. Начиная с только что найденного 0' строится цепочка нулевых элементов матрицы по следующему правилу: исходный 0'; 0*, лежащий в одном столбце с этим 0'; 0', лежащий в строке с только что пройденным 0* и т.д. Заканчивается цепочка 0'. После построения цепочки штрихи у нулевых элементов этой цепочки заменяются на *, старые * в цепочке уничтожаются. Убираются знаки выделения строк и столбцов. * не входящие в цепочку переписываются. Далее переход на 1.

5. Ищем минимальный ненулевой неВЭ и обозначаем h. Затем, прибавляем h к элементам, которые стоят на пересечении выделенных строк и выделенных столбцов; отнимаем h от элементов, которые стоят на пересечении невыделенных строк и не выделенных столбцов; остальные элементы переписываем без изменений. Возвращаемся к 2.

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии