2 Аналитическое решение

2.1 Постановка задачи

Имеется n различных работ, которые требуется распределить между n различными комплексами АСУ. Известен ожидаемый эффект c_ij от использования i-ого комплекса при выполнении j-ой работы. Требуется так распределить работы между комплексами АСУ (по одной на каждый), чтобы суммарный эффект от выполнения работ был максимальным.

2.2 Составление математической модели

Для каждого i-ого комплекса (i=1,…,n) и для каждой j-ой работы (j=1,…,n) введем переменную которая может принимать всего два значения (0 или 1):

Тогда суммарная эффективность выполнения всех работ выражается функцией:

.

Ограничения задачи:

, (1)

(2)

Уравнения (1) означают, что каждый i-ый комплекс используется ровно один раз.

Уравнения (2) означают, что каждая j-ая работа выполняется ровно один раз.

Таким образом, математическая модель задачи о назначениях является задачей целочисленного линейного программирования вида

(3)

при ограничениях (1), (2) и

, (4)

–целочисленные, . (5)

3 Численное решение

Пусть n = 5 и ожидаемый эффект c_ij от использования i-ого комплекса при выполнении j-ой работы указан в матрице С.

Сначала выполним подготовительный этап алгоритма. Найдём максимальный элемент (max) в каждом столбце и вместо каждого элемента c_ij запишем разность (max - c_ij).

Теперь из всех элементов каждой строки вычитаем минимальный элемент этой строки и помечаем независимые 0 символом «*» по схеме, указанной в алгоритме.

На этап подготовительный этап заканчивается.

Ниже приведено решение данной задачи по алгоритму, описанному в пункте 1.3.

Теперь количество независимых нулей 0* стало равным 5, что совпадает с размерностью n матрицы и поэтому процесс выбора закончен. Искомые элементы матрицы C соответствуют позициям независимых нулей матрицы С₀.

Значение целевой функции получим из матрицы С₀, выбрав значения соответствующие позициям независимых нулей.

L(x) = C₃₁ + C₄₂ + C₁₃ + C₂₄ + C₅₅ = 9 + 12 + 12 + 15 + 2 = 50.

Оптимальное решение данной задачи о назначениях определяется набором

{ x_ij }, i, j = 1, …, 5 cо значениями: х₃₁ + х₄₂ + х₁₃ + х₂₄ + х₅₅ = 1.

Содержательно это означает, что третий комплекс АСУ выполняет первый вид работы, четвёртый комплекс АСУ осуществляет второй вид работ, первый комплекс — третий вид работы, второй комплекс делает четвёртую работу, а пятый — пятую. При таком выборе суммарный эффект от выполнения работ будет максимальным и равным 50.

Заключение

Целью оптимизации было распределение различного вида работ между различными комплексами АСУ, при условии чтобы суммарный эффект от выполнения работ был максимальным.

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

Поставленные задачи выполнены полностью.

Список использованных источников

1 Зыкина А. В. «Методы оптимизации: Конспект лекций» – Омск: Изд-во ОмГТУ, 2007. - 36 с.

2 Зыкина А. В. «Теория принятия решений: Методические указания» – Омск: Изд-во ОмГТУ, 2007. - 32 с.

3