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

Строительной фирме «Спецмонтаж» необходимо выполнить бетонные работы на 4 строящихся объектах. В фирме имеются 4 бригады бетонщиков, которые могут выполнить эту работу. Сроки выполнения работ каждой бригадой в рабочих днях приведены в следующей таблице 3.

Таблица 3

Бригада	Объект
	О1	О2	О3	О4
Б1	30	40	50	60
Б2	36	41	52	58
Б3	28	44	49	57
Б4	35	39	49	63

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

Составим математическую модель этой задачи. Определим 16 двоичных переменных х_ij (i и j изменяются от 1 до 4), которые будут равны 1, если бригада i назначается на объект j, и 0, если бригада i не назначается на объект j.

Если принять за стоимости назначений c_ij сроки выполнения работ каждой бригадой, которые приведены в таблице, то целевую функцию можно записать так:

z = 30x₁₁ + 40x₁₂ + 50x₁₃ + 60x₁₄ + 36x₂₁ + 41x₂₂ + 52x₂₃ + 58x₂₄ + 28x₃₁ + 44x₃₂ + 49x₃₃ + 57x₃₄ + 35x₄₁ + 39x₄₂ + 49x₄₃ + 63x₄₄.

Далее запишем 8 простых ограничений в виде равенств, поскольку эта задача сбалансированная:

x₁₁ + x₁₂ + x₁₃ + x₁₄ = 1,

x₂₁ + x₂₂ + x₂₃ + x₂₄ = 1,

x₃₁ + x₃₂ + x₃₃ + x₃₄ = 1,

x₄₁ + x₄₂ + x₄₃ + x₄₄ = 1,

x₁₁ + x₂₁ + x₃₁ + x₄₁ = 1,

x₁₂ + x₂₂ + x₃₂ + x₄₂ = 1,

x₁₃ + x₂₃ + x₃₃ + x₄₃ = 1,

x₁₄ + x₂₄ + x₃₄ + x₄₄ = 1.

На основе записанной математической модели создаем на рабочем листе Excel табличную модель, показанную на рис. 6. Значение целевой функции в ячейке F20 вычисляется по формуле, которая показана на рис.6 в строке формул. В диапазонах F14 : F17 и В18 : Е18 по – прежнему вычисляются суммы значений переменных соответственно по строкам и столбцам матрицы решения. Далее следует воспользоваться командой меню Сервис  Поиск решения. В одноименном диалоговом окне (рис. 8) задаем адрес целевой ячейки F20, устанавливаем переключатель минимальному значению, указываем адрес диапазона изменяемых ячеек В14 : Е17, задаем ограничения. Как задавать ограничения двоичности, налагаемые на переменные решения, показано на рис. 7. В диалоговом окне Параметры поиска решения устанавливаем флажки Линейная модель и Автоматическое масштабирование. В диалоговом окне Поиск решения щелкаем по кнопке Выполнить и получаем решение, показанное на рис. 9.

Рис. 6

Рис. 7

Рис. 8

Рис. 9

Найденное решение (рис. 9) показывает, что первую бригаду надо отправить на 3 объект (число 1 в ячейке D14), вторую бригаду  на 4 объект (число 1 в ячейке Е15), третью бригаду  на первый объект и четвертую  на второй объект. Общая продолжительность всех работ составит 175 рабочих дней (значение целевой функции в ячейке).

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

Предположим, что в фирме «Спецстрой» имеется пять бригад бетонщиков, которые могут выполнить работы на четырех объектах. таблице 3 сроков выполнения работ приведена ниже.

Таблица 4

Бригада	Объект
	О1	О2	О3	О4
Б1	30	40	50	60
Б2	36	41	52	58
Б3	28	44	49	57
Б4	35	39	49	63
Б5	29	40	48	59

Поскольку в данном случае количество бригад больше количества объектов, имеем несбалансированную задачу о назначениях. Целевую функцию следует записать так:

z = 30x₁₁ + 40x₁₂ + 50x₁₃ + 60x₁₄ + 36x₂₁ + 41x₂₂ + 52x₂₃ + 58x₂₄ + 28x₃₁ + 44x₃₂ + 49x₃₃ + 57x₃₄ + 35x₄₁ + 39x₄₂ + 49x₄₃ + 63x₄₄ + 29x₅₁ + 40x₅₂ + 48x₅₃ + 59x₅₄.

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

x₁₁ + x₂₁ + x₃₁ + x₄₁ + x₅₁ = 1,

x₁₂ + x₂₂ + x₃₂ + x₄₂ + x₅₂ = 1,

x₁₃ + x₂₃ + x₃₃ + x₄₃ + x₅₃ = 1,

x₁₄ + x₂₄ + x₃₄ + x₄₄ + x₅₄ = 1.

и пять ограничений в виде неравенств (суммы переменных по строкам матрицы решений)

x₁₁ + x₁₂ + x₁₃ + x₁₄ ≤ 1,

x₂₁ + x₂₂ + x₂₃ + x₂₄ ≤ 1,

x₃₁ + x₃₂ + x₃₃ + x₃₄ ≤ 1,

x₄₁ + x₄₂ + x₄₃ + x₄₄ ≤ 1,

x₅₁ + x₅₂ + x₅₃ + x₅₄ ≤ 1.

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

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

Найденное решение (рис. 11) показывает, что первая бригада остается безработной, вторую бригаду надо отправить на 4 объект (число 1 в ячейке Е16), третью бригаду  на 1 объект (число 1 в ячейке В17), четвертую  на 2 объект и пятую  на третий объект. Общая продолжительность всех работ составит 173 рабочих дня (значение целевой функции в ячейке F22), что меньше на 2 дня решения сбалансированной задачи.

При выполнении задачи 6 обратите внимание, что в табл. 6 задания 0 – 4 и 7 – 9 относятся к транспортной задаче, а задания 5 и 6 – к задаче о назначениях.

Рис. 10

Рис. 11