Линейная и векторная алгебра Кратные интегралы Математическая статистика Математический анализ

Задача заключается в выборе такого распределения ресурсов по объектам, при котором минимизируется стоимость назначений. Предполагается, что каждый ресурс назначается ровно один раз и каждому объекту приписывается ровно один ресурс.

Возможные применения задачи о назначениях представлены в табл. 26.1.

Матрица стоимостей С имеет вид

где cij — затраты, связанные с назначением i-го ресурса на j-й объект, i = j = , где п — число объектов или ресурсов. Вычисление интегралов Кривая L задана параметрически

Обозначим:

Таким образом, решение задачи может быть записано в виде Х = (xij).

Допустимое решение называется назначением. Оно строится путем выбора ровно одного элемента в каждой строке матрицы X = (xij) и ровно одного элемента в каждом столбце этой матрицы.

Элементы cij матрицы С, соответствующие элементам xij = 1 матрицы X, будем отмечать кружками:

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

при ограничениях:

Алгоритм решения задачи

Задача о назначениях является частным случаем транспортной задачи, в которой ai = bj = 1. Поэтому ее можно решать алгоритмами транспортной задачи. Рассмотрим другой метод, который является более эффективным, учитывающим специфику математической модели. Этот метод называется венгерским алгоритмом. Он состоит из следующих шагов:

1) преобразования строк и столбцов матрицы;

2) определение назначения;

3) модификация преобразованной матрицы.

1-й шаг. Цель данного шага — получение максимально возможного числа нулевых элементов в матрице С. Для этого из всех элементов каждой строки вычитаем минимальный элемент соответствующей строки, а из всех элементов каждого столбца вычитаем минимальный элемент соответствующего столбца.

2-й шаг. Если после выполнения 1-го шага в каждой строке и каждом столбце матрицы С можно выбрать по одному нулевому элементу, то полученное решение будет оптимальным назначением.

3-й шаг. Если допустимое решение, состоящее из нулей, не найдено, то проводим минимальное число прямых через некоторые столбцы и строки так, чтобы все нули оказались вычеркнутыми. Выбираем наименьший невычеркнутый элемент. Этот элемент вычитаем из каждого невычеркнутого элемента и прибавляем к каждому элементу, стоящему на пересечении проведенных прямых.

Если после проведения 3-го шага оптимальное решение не достигнуто, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено допустимое решение.

Пример.

Распределить ресурсы по объектам.

Решение. 1-й шаг. Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим

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

3-й шаг. Вычеркиваем столбец 1, строку 3, строку 2 (или столбец 2). Значение минимального невычеркнутого элемента равно 2:

Вычитаем его из всех невычеркнутых элементов и, складывая его со всеми элементами, расположенными на пересечении двух линий, получим

Ответ. Первый ресурс направляем на 3-й объект, второй — на 2-й объект, четвертый — на 1-й объект, третий ресурс — на 4-й объект. Стоимость назначения: 9 + 4 + 11 + 4 = 28.

Примечания. 1. Если исходная матрица не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2. Если какой-либо ресурс не может быть назначен на какой-то объект, то соответствующая стоимость полагается равной достаточно большому числу М.

3. Если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на (—1) и сложить их с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем задачу следует решать как задачу минимизации.

4. Если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк или столбцов (квадратной матрицы), то существует назначение нулевой стоимости.

 

Планирование загрузки оборудования с учетом максимальной производительности станков

Рассмотрим следующую задачу.

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

Определить, какую операцию и за каким станком следует закрепить, чтобы суммарная производительность была максимальной при условии, что за каждым станком закреплена только одна операция.

Решение. Так как в задаче требуется определить max, a алгоритм метода дан для задач на min, умножим матрицу С на (—1). Сложим полученную матрицу, имеющую отрицательные коэффициенты, с положительным числом, например с числом 10. Получим

Минимальные элементы в строчках есть 3, 4, 4, 6, 4. Вычтем их из соответствующих элементов матрицы, получим

Так как назначение не получено, вычеркиваем строку 2, столбцы 2, 4, 5:

Минимальный элемент равен 1. Вычитаем его из всех невычеркнутых элементов и складываем со всеми элементами, расположенными на пересечении двух линий. Получаем

Оптимальное решение, соответствующее последней матрице, равно

Суммарная производительность: 6 + 6 + 3 + 6 + 7= 28.

Таким образом, на первом станке надо делать 5-ю операцию, на втором — 1-ю операцию, на третьем — 4-ю операцию, на четвертом — 3-ю операцию, на пятом станке — 2-ю операцию. Суммарная производительность: 28 деталей в единицу времени.

Выбор инвестиционных проектов в условиях ограниченности финансовых ресурсов

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

Например, у предприятия для выполнения некоторых программ имеется пять инвестиционных проектов, чистая приведенная стоимость которых указана в табл. 26.2. Однако предприятие не может финансировать все проекты: суммы денег, выделенные на текущий год и последующие два, меньше необходимых для инвестирования в полном объеме. При этом оставшиеся денежные средства не могут быть перенесены на следующие годы, также не предусмотрено более одного финансирования одного и того же проекта. Требуется распределить выделенные средства в инвестиционные проекты оптимальным способом.

Решение. Обозначим черех xj долю вложения в j-й проект, где j = . Тогда чистая приведенная стоимость инвестиций в 1-й проект составит 40x1; во 2-й проект — 60x2 и т.д. При этом необходимо учитывать, что инвестиции не должны превышать 54, 62 и 70 ден. ед. в первый, второй и третий годы соответственно. Требуется выбрать один или группу проектов с наибольшей совокупной чистой приведенной стоимостью.

Математическая модель этой экономической задачи имеет вид

при ограничениях:

причем xj = 0 или 1, j =  (проект либо финансируется, либо нет).

Решая задачу на компьютере, получаем х1 = х2 = х4 = x5 = 1, x3 = 0. Иными словами, необходимо производить финансирование 1, 2, 4 и 5-го проектов. При этом потребуются денежные средства в объеме 177 ден. ед. в течение трех лет (при выделяемом предприятием объеме 186 ден. ед.), а сумма чистой приведенной пои мести проектов будет максимальной и составит 205 ден. ед.

Математическая модель может быть составлена для произвольного конечного числа программ при предполагаемом финансировании в течение любого количества лет.

УПРАЖНЕНИЯ

26.1. Фирма имеет три механизма A1, А2, А3, каждый из которых может быть использован на каждом из трех видов работ B1, B2, B3 с производительностью, заданной матрицей (в условных единицах)

Распределить механизмы по одному на каждую из работ так, чтобы суммарная производительность всех механизмов была максимальной.

26.2. Пять человек должны выполнить четыре работы, причем каждый из работников с разной производительностью может выполнить любую из этих работ. Предусматривается, что каждый работник в состоянии сделать только одну работу.

Производительности работников при выполнении работ заданы матрицей

Распределить людей на работу так, чтобы выполнить ее с максимальной производительностью.

26.3. Фирма, имеющая четыре склада, получила четыре заказа, которые необходимо доставить различным потребителям. Складские помещения каждой базы имеют вполне достаточное количество товара, чтобы выполнить любой один из этих заказов.

Расстояния между каждой базой и каждым потребителем приведены в матрице

Как следует распределить заказы по базам, чтобы общая дальность транспортировки была минимальной?

26.4. Фирма объединяет три предприятия, каждое из которых производит 3 вида изделий.

Себестоимости каждого изделия в усл. ед. при изготовлении на каждом предприятии указаны в матрице

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

26.5. Компания разрабатывает план выпуска трех новых видов продукции. Она уже владеет пятью предприятиями, и теперь на трех из них должны производиться новые виды продукции — по одному виду на одно предприятие.

Даны издержки производства единицы продукции, усл. ед.:

Издержки сбыта единицы продукции, усл. ед.:

Плановый объем годового производства, который позволил бы удовлетворить спрос, и себестоимость единицы продукции каждого вида приведены в табл. 26.3.

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


На главную