X Международная студенческая научная конференция Студенческий научный форум - 2018

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

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

Во время решения некоторых математических задач приходится назначать исполнителей (людей, механизмы и т.п.) для выполнения некоторых однотипных работ. При этом дополнительно известны значения сij - эффективность (неэффективность) выполнения i-м исполнителем j-ой работы. Требуется распределить исполнителей по работам таким образом, чтобы максимизировать (минимизировать) суммарный критерий эффективности (неэффективности) выполнения всех работ.

Данная задача носит название «задача о назначениях» и является частным случаем более общей транспортной задачи. Если число исполнителей равно числу выполняемых работ, то такая задача является сбалансированной, в противном случае - не сбалансированной. В случае сбалансированной задачи о назначениях выполняются два условия: каждый исполнитель выполняет только одну работу и каждая работа выполняется только одним исполнителем.

1. Сбалансированная и несбалансированная задача о назначениях и ее решение в среде ЭТ MSExcel и математического пакета MathCad

1.1. Сбалансированная задача о назначениях

Задача о назначениях может быть сформулирована различными способами. Решить задачу о назначении − распределить исполнителей (людей или механизмы) по имеющимся работам так, чтобы обеспечить выполнение всех работ с минимальными суммарными затратами. При этом, если количество исполнителей равно количеству выполняемых работ, то задача о назначениях является сбалансированной. Задача о назначениях является частным случаем транспортной задачи.

Пусть управление механизации имеет n подъемных кранов, с помощью которых требуется возвести n объектов. Известна себестоимость c_ij строительства каждым краном отдельного объекта. Требуется так распределить подъемные краны по объектам, чтобы обеспечить возведение всех объектов с минимальными суммарными затратами.

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

Таблица 2. Исходные данные к сбалансированной задаче о назначениях

Обьект Оj Кран Кi	О1	О2	…	Оn
K1	C11	C12	…	C1n
K2	C21	C22	…	C2n
…	…	…	…	…
Kn	Cn1	Cn2	…	Cnm

Для решения сформулированной задачи составим ее математическую модель.

1.2 Математическая модель задачи

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

1. Определим неизвестные и их количество.

Введем переменные x_ij, которые равны 1, если i-й кран работает нa j-м объекте, и 0, если он не работает там. Так как областью допустимых изменений каждой переменной x_ij является не множество неотрицательных чисел, а конечное множество (0,1), то мы имеем дискретную задачу оптимизации. Таким образом, бинарные (двоичные) элементы x_ij образуют матрицу назначений X_nхn.

2. Запишем целевую функцию – суммарные затраты на возведение всех объектов

(1)

3. Сформулируем ограничения рассматриваемой задачи:

3.1. Каждый кран может работать только на одном объекте. Т. е. каждая строка матрицы назначений Х содержит только один элемент, равный 1, а все остальные равны 0. Таким образом, сумма элементов каждой строки матрицы Х равна единице. Это ограничение можно записать в виде:

(2)

3.2. Каждый объект может возводиться только одним краном. Т. е. каждый столбец матрицы назначений Х содержит только один элемент, равный 1, а все остальные равны 0. Это ограничение можно записать:

(3)

3.3. Бинарность переменных x_ij. Поскольку переменные x_ij принимают значения или 1 или 0, то ограничение запишем в виде:

x_ij − бинарные (двоичные). (4)

Совокупность целевой функции (1) и ограничений (2− 4) образует математическую модель типичной экстремальной комбинаторной задачи о назначении. Решение такой задачи представляет собой некоторую перестановку чисел, а количество перестановок с ростом n резко возрастает и равно N = n!. Для задачи, приведенной ниже, N = 3! =1 · 2 · 3 = 6, а для n = 7 число перестановок составляет 5040. Задача относится к классу задач линейного программирования, так как ограничения и целевая функция имеют линейный вид, т. е. искомые переменные x_ij находятся в первой степени.

Более подробно разберем сбалансированную задачу о назначениях на следующем примере:

Требуется:

1. Выполнить математическую постановку задачи линейного программирования (ЗЛП);

2. Решить ЗЛП в среде электронных таблиц MS Excel и пакета Mathcad.

Пусть управление механизации имеет 3 подъемных крана и управлению требуется возвести 3 объекта. Известна себестоимость (тыс. руб.) возведения каждым краном отдельного объекта. Исходная информация представлена в таблице.

Таблица 3 – Данные для сбалансированной задачи о назначениях

Объект Оj Кран Кi	О1	О2	О3
K1	C11	C12	C13
K2	C21	C22	C23
K3	C31	C32	C33

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

1.3Решение в среде ЭТ MSExcel

Для решения задачи с помощью надстройки «Поиск решения» в среде ЭТ MS Excel необходимо:

1. создать таблицу для ввода условий задачи и ввести исходные данные.

2. Запишем матрицу затрат на выполнение работ С_3х3.

3. Составим матрицу назначений Х_3х3 с пока нулевыми значениями элементов x_ij.

4. Дополните матрицу перевозок столбцом справа и строкой снизу, в которые запишите суммы элементов соответствующих строк и столбцов.

5. Дополним матрицу перевозок столбцом справа и строкой снизу, в которые запишем суммы элементов соответствующих строк и столбцов.

Рисунок 8 – MS Excel-документ решения сбалансированной задачи о назначениях

6. Записать целевую функцию F(X), используя встроенную функцию MS Excel – СУММПРОИЗВ().

7. Вызвать диалоговое окно надстройки «Поиск решения» и выполнить необходимые установки.

Рисунок 9 – MS Excel-документ настройки поиск решения для сбалансированной задачи о назначениях

8. Сохраним полученное решение.

1.4 Решение с помощью пакета MathCad

Для решения задачи в среде пакета MathСad:

1. Зададим исходные данные.

2. Определим вектор-столбцы переменных Х и затрат С.

3. Определим целевую функцию – минимальные затраты.

4. Вызовем блок решения, занесем в него ограничения.

5. Найдем оптимальное решение с помощью функции Minimize.

Рисунок 10 – MathCad-документ решения сбалансированной задачи о назначениях

2.1 Несбалансированная задача о назначениях

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

Таблица 4 – Исходные данные для несбалансированной задачи о назначениях

Работы Pj Исполнители Иi	P1	P2	…	Pm
И1	С11	С12	…	С1n
И2	C21	C22	…	C2n
…	…	…	…	…
Иn	Cn1	Cn2	…	Cnm

При этом возможны два случая:

а) число исполнителей n больше числа выполняемых работ m (n > m),

б) число исполнителей n меньше числа выполняемых работ m (n < m).

В обоих случаях для решения несбалансированной задачи ее сводят к сбалансированной, путем введения фиктивных работ или фиктивных исполнителей с нулевыми значениями с_ij – эффективности (неэффективности) выполнения i-м исполнителем j-й работы.

В первом случае, когда n > m, вводится k = n – m фиктивных работ P_m+1, P_m+2, …, P_m+k. Во втором случае (n < m) – рассматриваются k = m – n фиктивных исполнителя И_n+1,И_n+2, …, И_n+k.

Решим задачу о назначениях, когда 6 исполнителей претендуют на выполнение 4 работ. Таблица себестоимостей (тыс. руб.) выполнения претендентами каждой из четырех работ представлена ниже.

Таблица 5 – Исходные данные для несбалансированной задачи о назначениях

Работы Pj Исполнители Иi	P1	P2	P3	P4
И1	75	30	10	25
И2	20	35	40	50
И3	15	55	70	65
И4	25	30	20	100
И5	30	40	55	60
И6	70	80	25	30

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

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

2.2 Решение задачи в среде ЭТ MSExcel

Для решения задачи с помощью

надстройки «Поиск решения» в среде ЭТ MS Excel необходимо:

1. Создадим таблицу для ввода условий задачи и введите исходные данные − матрицу себестоимостей С_6х4.

3. Сформируем матрицу себестоимостей С_6х6 сбалансированной задачи о назначениях.

4. Составим матрицу перевозок Х6х6 с нулевыми значениями x_ij.

5. Дополним матрицу перевозок столбцом справа и строкой снизу, в которые запишем суммы элементов соответствующих строк и столбцов.

6. Запишите целевую функцию F(X), используя встроенную функцию MS Excel СУММПРОИЗВ()

Рисунок 11 – MS Excel-документ исходных данных несбалансированной задачи о назначениях

7. Вызовем диалоговое окно надстройки «Поиск решения», и выполним необходимые установки.

Рисунок 12 – MS Excel-документ, надстройка поиск решения для несбалансированной задачи о назначениях

8. Сохраним полученное решение.

Рисунок 13 – MS Excel-документ решения несбалансированной задачи о назначениях

2.3 Решение с помощью пакета MathCad

Для решения задачи в среде пакета MathСad:

1. Зададим исходные данные, сведем несбалансированную задачу к сбалансированной

2. Определим вектор-столбцы переменных Х и затрат С.

3. Определим целевую функцию – минимальные затраты.

4. Вызовем блок решения, занесем в него ограничения.

5. Найдем оптимальное решение с помощью функции Minimize.

Рисунок 14 – MathCad-документ решения несбалансированной задачи о назначениях

Рисунок 15 – MathCad-документ решения несбалансированной задачи о назначениях

Решив эту задачу в среде ЭТ MS Excel и в математическом пакете Mathcad, мы получили одинаковые решения: минимальное значение целевой функция равна 85 т.руб.

ЗАКЛЮЧЕНИЕ

Данная работа показывает широкие возможности работы с пакетами ЭТ MS Excel и MathCad. Результатом данного исследования является решение сбалансированной и несбалансированной задачи о назначениях.

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

СПИСОК ЛИТЕРАТУРЫ

1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. – М.: Наука, 1986. – 321 с.

2. Математические методы и модели исследования операций: Учебник для студентов вузов/ под ред. В.А. Колемаева.–М.:ЮНИТИ-ДАНА, 209. – 592 с.

3. Супрун А.Н., Найденко В.В. Вычислительная математика для инженеров – экологов. – М.: АСВ, 1996. – 391с.

4. Леоненков А.В. Решение задач оптимизации в среде MS Excel СПб.: БХВ – Петербург, 2005. – 704 с.

5. И. Спира. Microsoft Excel и Word 2013. Учится некогда не поздно. Издательство: Питер, 2014. – 250 с.

6. Аверьянова С.Ю., Растеряев Н.В. Содержательные задачи линейного программирования и их решение с помощью ЭТ MS EXCEL и пакета MATHCAD: учебное пособие/Южный федеральный университет. –Ростов-на-Дону: Издательство ЮФУ, 2014. – 132 с.

7. Бородакий Ю.В. Линейное программирование в современных задачах оптимизации / Ю.В. Бородакий. – М.: МИФИ, 2008. – 564с.

8. Киселева Э.В. Математическое программирование (линейное программирование) / Э.В. Киселева, С.И. Соловьева. – Новосибирск: НГАСУ, 2002. – 256с.

9. Кремер Н.Ш. Исследование операций в экономике/ Н.Ш. Кремер. — М.:Юнити,2000. — 400 с.

Код для цитирования: Скопировать