Оптимізація змін робочих з допомогою Пошуку рішень в MS EXCEL

1. Умови завдання (оригінальні)
2. Розбір умови задачі
3. Рішення
4. альтернативне рішення

Вирішимо задачу про оптимізацію змін робочих з допомогою Пошуку рішень MS EXCEL 2010. Як приклад розберемо завдання зі збірки "Методи оптимізації управління та прийняття рішень" автори Зайцев М.Г. і Варюхін С.Є. (2008р.). Завдання 2.43 "Проблема майстра".

Збірник завдань "Методи оптимізації управління та прийняття рішень" досить популярний в якості задачника для Вузів, тому посилання на нього зустрічаються повсюдно в інтернеті. Приємно, що для кожного завдання є відповідь в кінці книги - можна порівняти вийшло рішення з рішенням, яке знайдено авторами за допомогою Пошуку рішення (На рік так 2000-му, я вважаю).

Умови завдання (оригінальні)

Майстер повинен вибрати кілька фрезерувальників з 10 (Р1, Р2..Р10) для виготовлення 8 видів деталей (Д1, Д2, ... Д8) для партії продукції:

так, щоб скоротити загальні витрати робочого часу. Середня кількість деталей, яке кожен робітник може обробити за зміну, дано в таблиці:

а. Визначити оптимальний розподіл робочих за операціями, беручи до уваги, що робочі Р5 і Р9 не можуть виготовляти деталі Д5 і Д2 відповідно.
b. Який найкоротший термін виконання цього замовлення?

Розбір умови задачі

Скажу чесно, але умови задачі не здаються мені чітко сформульованими. Ось мої коментарі:

1) Робочих називають спочатку фрезерувальниками, потім просто робочими. Навіщо?

2) Використовується поняття "операції", тобто мається на увазі якась певна послідовність дій. Тобто можна подумати, що спочатку робиться операція Д1 (виготовлення деталі 1), потім Д2 і т.д. Щоб з'ясувати це, звернемося до відповіді:

Тобто немає ніяких послідовних операцій, є просто 8 типів деталей, які потрібно виготовити. Причому один робочий виготовляє за зміну або довше тільки один вид деталей, потім, якщо є необхідність, то переходить до іншого типу. Поняття "операції" не допомагає студенту зрозуміти умову, а лише його заплутує.

3) У відповіді ціла і дробові частини зміни відокремлені точкою, але як відомо, в Росії роздільником є ​​кома. Крім того, очевидно, що дрібна частина зміни призведе до дробового кількості виготовлених деталей (це як то незрозуміло). Як наслідок, в завданню планується складати 63,111 і 48,888 деталей, щоб виконати замовлення. Що не дуже логічно.

4) У умови використовується "середня кількість деталей, яке кожен робітник може обробити за зміну". Начебто, це завдання планується вирішувати статистичними методами з використанням якоїсь функції розподілу.

5) Навіщо сказано, що "робочі Р5 і Р9 не можуть виготовляти деталі Д5 і Д2"? Просто поставте нуль, ніякого сенсу в цьому умови немає.

Крім нешкідливих неточностей у формулюваннях умови в формулюванні завдання відсутні 2 додаткових обмежень, без яких вищевказаний відповідь не отримати. Розберемося в цьому, вирішивши завдання.

Рішення

Якщо ви не знайомі з Пошуком рішення, то для початку прочитайте статтю Пошук рішення MS EXCEL. знайомство .

Щоб побудувати модель для Пошуку рішення (ПР) в EXCEL потрібно визначити 3 її складових:

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

Створимо в файлі прикладу на аркуші а допоміжну таблицю (завантаження робочих по змінах) і заповнимо її даними з вищевказаного рішення.

Тепер розрахуємо, скільки ж деталей буде виготовлено при такому завантаженні робітників.

Виявляється, в рішенні помилка. При цьому відповіді не буде виконано замовлення - основна умова завдання. Виявляється, деталь Д6 також виготовляє робочий Р4. Після додавання потрібної кількості змін, отримаємо правильну відповідь - тепер замовлення виконано.

Повернемося до таблиці завантаження робочих по змінах і ще раз уважно подивимося на рішення, наведене в задачнику.

Виявляється, кількість змін у кожного робітника становить від 1 до 4 (рівно)! Чому? Тому що, це додаткове обмеження, про яке нічого не сказано в умові завдання. Отримаємо це рішення. Для цього створимо модель.

Будемо мінімізувати загальну кількість змін всіх робітників (див. Формулу в червоній осередку). В якості обмежень вимагатимемо виконання замовлення і завантаження кожного робочого від 1 до 4 змін. Змінними є осередки, які містять кількості змін робочих.

Натиснувши кнопку Знайти рішення отримаємо саме ту відповідь, що він дав в задачнику. Щоб зрозуміти, звідки взялося обмеження про завантаження кожного робочого від 1 до 4 змін, видалимо ці обмеження і знову запустимо Пошук рішення. Ось відповідь:

Як бачимо, загальна кількість змін всіх робітників зменшилася (35,78 проти 37,23). Так навіщо авторам потрібні були ці додаткові обмеження? Справа в тому, що без цих обмежень ми отримаємо тривіальний відповідь, який очевидний і без Пошуку рішення! Порівняйте завантаження робочих з їх продуктивністю:

Максимальна продуктивність виділена кольором і разюче збігається зі знайденим рішенням. Насправді рішення очевидно: щоб скоротити завантаження робочих - візьми найпродуктивніших (за типами деталей) і завантаж їх! Цей факт наводить на думку, що або завдання некоректно сформульовано, або неправильно вирішена. Будемо грішити на рішення.

Перед тим як вирішити задачу іншим способом, відповімо на друге питання завдання: "Який найкоротший термін виконання цього замовлення?" (Див. Файл прикладу, лист б)

Щоб обчислити найкоротший термін виконання замовлення - просто приберемо 2 доп. обмеження щодо кількості змін (від 1 до 4) у вікні Пошуку рішення і змінимо цільову функцію в червоній осередку J31. Тепер будемо мінімізувати максимально тривалий змін робочих (= МАКС (J21: J30)).

При цьому вважаємо, що всі 10 робочих працюють незалежно один від одного (на різних верстатах), тому час виконання замовлення дорівнюватиме максимальній кількості змін у одного з робітників. Отримана відповідь 3,89 збігається з відповіддю в задачнику (менше 4-х днів).

альтернативне рішення

Тепер спробуємо переформулювати умову задачі.

По-перше, припустимо, що кожен робітник за 8-ми годинну зміну зобов'язаний зробити все 8 типів деталей (від Д1 до Д8). Тобто, в 1-а година кожен робочий робить Д1, у 2-а година кожен робочий робить Д2 і т.д. Продуктивність дана в таблиці.

По-друге, замовлення потрібно зробити за 1 зміну.

Питання: яких робочих потрібно взяти, щоб виконати замовлення мінімальною кількістю робочих?

При такому формулюванні завдання ми позбавляємося від нецілих змін і дрібних деталей (кожен робочий працює 1 зміну). Також ми не отримуємо тривіального рішення.

Якщо для виконання замовлення ми беремо робочого, то йому присвоюється значення 1, якщо немає, то 0.

Пошук рішення (як і раніше лінійна задача) знаходить, що достатньо взяти 7 робочих, щоб виконати замовлення. В цьому випадку, правда, замовлення буде кілька перевиконано за деякими типами деталей.

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