Рассмотрим пример решения задачи на ЭВМ.
Пример 10.1.
Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:
Рабочие | Станки | |||
С1 | С2 | С3 | С4 | |
P1 | 2,3 | 1,9 | 2,2 | 2,7 |
P2 | 1,8 | 2,2 | 2,0 | 1,8 |
P3 | 2,5 | 2,0 | 2,2 | 3,0 |
P4 | 2,0 | 2,4 | 2,4 | 2,8 |
Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент?
Решение. Обозначим за xij; i = 1,2,3,4; j = 1,2,3,4 ij - переменные, которые принимают значения 1, если i -й рабочий работает на j -м станке. Если данное условие не выполняется, то xij = 0. Целевая функция есть:
Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть
Кроме этого, каждый станок обслуживает только один рабочий:
|
|
Кроме того, все переменные должны быть целыми и неотрицательными: xij≥0, xij – целые.
Открываем электронную таблицу MS Excel. Вводим в диапазон В3-Е6 проценты по браку, ячейки G3-J6 выделяем под переменные и вводим в них произвольные числа, например единицы, задаем подписи как показано на рисунке.
Целевая функция равна сумме произведений данных из диапазона В3-Е6 умноженных на переменные из диапазона G3-J6, и все делить на 4. Для ее вычисления ставим курсор в ячейку В7, вызываем мастер функций кнопкой fx и выбираем функцию СУММПРОИЗВ из категории «Статистические». В полях «Массив 1» обводим ячейки В3-Е6, делая на них ссылку, а в «Массив 2» обводим G3-J6, нажимаем «ОК». Вводим левые части ограничений. Ставим курсор в В8 и вводим туда функцию «=G3+G4+G5+G6». Автозаполняем на В8, С8, D8 и Е8. Ставим курсор на F8 и вводим формулу: «=G3+H3+I3+J3» и автозаполняем ее на F9, F10, F11.
Вызываем надстройку ПОИСК РЕШЕНИЯ. Если Вы работаете в «EXCEL 2003» или ранней версии, то заходим в меню СЕРВИС, выбираем НАДСТРОЙКИ и проверяем наличие флажка напротив «Поиск решения», «ОК», заходим вновь в меню СЕРВИС, выбираем ПОИСК РЕШЕНИЯ.
Если Вы работаете в «EXCEL 2007» или более поздней версии, то нажимаем левой кнопкой мыши по круглой кнопке “Office” в верхнем левом углу экрана, внизу выбираем «Параметры Excel», слева выбираем НАДСТРОЙКИ, нажимаем кнопку «Перейти» внизу окна и в открывшемся окне проверяем наличие флажка напротив «Поиск решения», «ОК». В меню ДАННЫЕ выбираем ПОИСК РЕШЕНИЯ. В окне ПОИСК РЕШЕНИЯ в поле «Установить целевую ячейку» даем ссылку на В7. Ставим точку на переключателе «Минимальному значению». В поле «Изменяя ячейки» даем ссылку на G3-J6. Нажимаем «Добавить» и вызываем окно добавление ограничения. Вводим 4 ограничения, как показано на рисунке
|
|
Нажимаем «Выполнить».
Получаем результат, таблица переменных состоит из единиц и нулей, по единицам определяем, что 1-й рабочий должен работать на втором станке, второй на четвертом, третий на третьем, четвертый на первом. Суммарный процент брака (целевая функция) будет равен 7,9.