Рис. 5.20. Результаты расчетов Как видно из рис. 5.20, все ограничения выполнены, мини-

мальные затраты составляют 48570 единиц.

Задача 5.4. Задача о назначениях

В цехе некоторого завода стоит пять станков, а количество ра-

бочих в цехе равно четырем. Рабочий 1 не может работать на станке

3, а рабочий 3 – на станке 4. В соответствии с квалификацией рабо-

чих начальник цеха в баллах оценил эффективность работы каждого из рабочих на каждом из станков (в 10-бальной шкале) (см.

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

Таблица 5.2

Бальные оценки эффективности работы рабочих на станках

160

Решение.

Решим эту задачу в табличном процессоре Gnumeric.

Первый шаг: подготовка исходных данных и ввод функций

(рис. 5.21).

Сначала оформим две таблицы.

«Таблица эффективности» (ячейки A1:F7) содержит исходную табл. 5.2. Отличие – прочерки были заменены нулями (ячейки D4,

E6).

«Таблица назначений» (ячейки A9:F15) в ячейках A12:F15 со-

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

мать только два значения: 1 – если рабочий распределен на работу с данным станком; 0 – если не распределен. Изначально везде ставим нули.

161

Рис. 5.21. Подготовка исходных данных.

«Целевая функция» в ячейке С19 содержит значение эффек-

тивности назначений, численно равное произведению переменных назначений на эффективность соответствующего назначения. Эта ве-

личина задается функцией «Сумма произведений»: «=sumproduct(Лист1!B4:F7;Лист1!B12:F15)»

В строке «Сумма» в ячейках B16:F16 содержатся суммы пере-

менных назначения по столбцам. Так, в ячейке В16 содержится сум-

ма ячеек В12:В15 (количество назначений на первый станок). Эта ве-

личина вычисляется при помощи функции SUM: «=sum(B12:B15)».

В столбце «Сумма» в ячейках F12:F15 содержатся суммы гори-

зонтальных ячеек (общее количество назначений для каждого рабо-

162

чего). Это задается той же функцией. Например: «=sum(B12:F12)» -

сумма ячеек B12:F12, которая находится в ячейке G12.

Строка и столбец «Границы» указывают граничные значения для количества назначений: в строке – количество людей на один станок; в столбце – количество станков на одного человека.

Второй шаг: решение оптимизационной задачи.

Для решения оптимизационных задач в таблицах Gnumeric

имеется программа Solver. Она вызывается через пункты меню «Сер-

вис»==> «Решение». Появляется панель «Solver» (рис. 5.22).

Первая вкладка – «Параметры».

Рис. 5.22. Установка основных параметров.

Встроке «Установить целевую ячейку» устанавливаем адрес нашей целевой функции С19.

Встроке «Равняется» делаем выбор пункта «Макс».

Встроке «Изменяя ячейки» указываем диапазон адресов ячеек переменных назначения B12:F15.

Затем переходим на вкладку «Модель» (рис. 5.23).

163

Рис. 5.23. Установка параметров модели.

Выбираем пункты: «Линейная модель», «Предполагать НЕ от-

рицательность», «Предполагать целочисленность», «Алгоритм: Simplex».

Пункт «Квадратичная модель» НЕ РАБОТАЕТ.

И, наконец, переходим на вкладку «Ограничения» (рис. 5.24) и

вводим ограничения модели.

Рис. 5.24. Ограничения модели.

164

1-е ограничение: переменная назначения D12 (назначение пер-

вого рабочего на третий станок) равна нулю (D4 у нас равна нулю).

2-ограничение: переменная назначения Е14 (назначение третьего рабочего на четвертый станок) равна нулю.

3-е ограничение: оно является множественным, сравнение про-

водится сразу по пяти парам ячеек (каждая верхняя ячейка не больше соответствующей нижней). Смысл: каждому станку назначается не более одного рабочего.

4-е ограничение: также множественное, сравнение проводится по четырем парам (каждая левая ячейка равна соответствующей пра-

вой). Смысл: каждый рабочий назначается на один станок.

Ограничения вводятся последовательно в нижней строке, со-

стоящей из трех окон. Действия аналогичны тому, что мы рассмат-

ривали в предыдущем примере.

После ввода ограничения следует нажать кнопку «Добавить».

Затем очистить нижнюю строчку и ввести следующее ограни-

чение и т.д.

ЗАМЕЧАНИЕ: при вводе ограничений в Solver нельзя исполь-

зовать числа, только ссылки на ячейки!

Окончив ввод ограничений нажмем кнопку «Решить» и поя-

вится информационное сообщение о том, что решение найдено (рис.

5.25).

Рис. 5.25. Информационное сообщение.

165