Методы оптимизации управления для менеджеров - Зайцев М.Г.. Методы оптимизации управления для менеджеров компьютерноориентированный подход
 Скачать 7.64 Mb.
|
|
Несбалансированность: дефицит запасов В случае дефицита запасов, т.е. когда добавим в таблицу транспортных издержек и в таблицу перевозок по одной лишней строчке. Это можно трактовать так, как если бы появился еще один, фиктивный, поставщик. Потребуем, чтобы запас этого "поставщика" в точности равнялся разности между суммой всех заказов и суммой всех запасов а издержки перевозок грузов от него к любому поставщику были равны нулю. Пусть в нашей задаче о перевозке песка производительность второго карьера не 200, а 150 грузовиков в день. Тогда заводы будут испытывать дефицит: потребность заводов - 300 грузовиков с песком в день, а карьеры могут добывать 250. Как распределить этот дефицит между заводами? Сколько грузовиков с песком не получит каждый завод, если поставщик (владелец обоих карьеров) интересуется только минимизацией транспортных издержек? Сбалансируем задачу добавлением фиктивного карьера-поставщика с нулевыми ценами перевозок и с запасом, равным 50 (разница между заказами от заводов (80 + 90 + 130) и запасами реальных карьеров (100 + 150)). Тогда переменныеХ 31 ,Х 32 иХ 33 покажут, сколько грузовиков песка не получат соответственно 1, 2 и 3-й заводы. Заметим, что несбалансированные транспортные задачи можно, конечно, решать, и просто заменив в соответствующих ограничениях знаки равенства на знаки нестрогих неравенств. Однако при этом надо иметь в виду, что для решения такой задачи MS-Excel будет применять общие методы решения ЛП-задач, а не специфические "транспортные" алгоритмы. В результате эффективность решения может быть значительно ниже. Возможно, для небольших задач, которые можно решить с помощью MS-Excel на современных персональных компьютерах (а надстройка "Поиск решения" MS-Excel допускает задачи, в которых не более 200 переменных решения), различие применяемых алгоритмов и не будет очень заметно. Однако для серьезных транспортных задач применение эффективных "транспортных" алгоритмов может быть очень существенно. Запрещенный маршрут Еще одно возможное осложнение транспортной задачи - это запрещение определенной перевозки от i-го поставщика к j- му потребителю для составляемого плана перевозок (ремонт дороги, неплатеж и пр.). В этом случае, естественно, можно просто ввести ограничение X ij =0. Однако вновь это означает невозможность использования эффективных "транспортных" алгоритмов решения. Чтобы сохранить форму транспортной задачи и учесть этот запрет, достаточно в таблице транспортных издержек заменить c ij на очень большое число (в случае нашего примера с песчаными карьерами подойдет что-то вроде 100). Это фактически будет означать, что оптимизационный алгоритм наверняка положит соответствующее значение перевозки X ij равным нулю, поскольку перевозка по этому маршруту просто крайне невыгодна. 5.3. Задача о назначениях С математической точки зрения задача о назначениях - это частный случай транспортной задачи, в которой число поставщиков (например, число рабочих, или, иначе, поставщиков рабочей силы) в точности равно числу потребителей ("работ", различных технологических операций). Поэтому таблица "транспортных издержек" (аналогом которых может выступать любая мера эффективности выполнения той или иной операции данным работником) должна быть квадратной. Кроме того, в задаче о назначениях от каждого поставщика к каждому потребителю поставляется только одна единица "груза" (например, только одного рабочего можно назначить для выполнения данной работы) или ни одной. Поэтому все "запасы" и все "заказы" равны 1. Понятно, что все переменные решения в задаче о назначениях могут принимать только значения 1 или 0. На первый взгляд это похоже на задачи целочисленного линейного программирования, рассмотренные в предыдущем разделе. Однако в силу упомянутых выше особенностей структуры ограничений транспортной задачи явно требовать целочисленности переменных решения (как их равенства только нулю или единице) не требуется. Такие значения получаются при решении автоматически. При этом, разумеется, "транспортные" алгоритмы решения гораздо более эффективны, чем алгоритмы решения задач целочисленного линейного программирования. Постановка задачи: Расстановка рабочих по операциям Мастер должен расставить 4 рабочих для выполнения 4 типовых операций. Из данных хронометрирования известно, сколько минут в среднем тратит каждый из рабочих на выполнение каждой операции. Эти данные представлены в таблице. Работы Работники A B C D 1 15 20 18 24 2 12 17 16 15 3 14 15 19 15 4 11 14 12 3 Как распределить рабочих по операциям, чтобы суммарные затраты рабочего времени были бы минимальны? Как и при решении транспортной задачи, составим таблицу переменных решения, которых в этой задаче будет, очевидно, 16. Каждая переменная решения может принять только два значения - 1 или 0, что будет означать соответственно, что данный рабочий назначен или не назначен на данную операцию. Понятно при этом, что в каждой строчке и в каждом столбце может быть только одна переменная решения, равная единице, а остальные должны быть равны нулю. Очевидно, что целевая функция представляет собой, как и в случае транспортной задачи, двойную сумму произведений переменных решения X ij на время выполнения каждой операции, которую мы обозначим, как и в транспортной задаче, c ij . Ограничения обусловлены основным требованием задачи о том, что каждый рабочий должен быть назначен на одну, и только одну, операцию и каждая операция должна быть назначена одному, и только одному, рабочему. Поэтому Иными словами, мы требуем, чтобы сумма всех переменных в любой строке составляла единицу и сумма всех переменных в любом столбце также была бы равна единице. Ясно, что, поскольку все переменные предполагаются неотрицательными, единственная возможность удовлетворить этим равенствам - это положить одну из переменных в каждой строчке и в каждом столбике равной 1, а все остальные - равными нулю. Никаких дополнительных условий целочисленности не требуется. Таблица 15 Назначения Работы Работники A B C D Запасы 1 X 11 X 12 X 13 X 14 1 2 X 21 X 22 X 23 X 24 1 3 X 31 X 32 X 33 X 34 1 4 X 41 X 42 X 43 X 44 1 Заказ 1 1 1 1 Понятно, что организация данных для решения задачи с помощью MS-Excel полностью аналогична транспортной задаче. Для практического решения задачи о назначениях рассмотрим более сложный пример. Пример для решения с помощью MS-Excel : Построение команд Фирма, занимающаяся продажей оборудования для компьютерных сетей, имеет 10 специалистов по маркетингу и 10 техников-программистов, которых необходимо объединить в пары (техник - менеджер по маркетингу) - команды по продаже оборудования, соответствующего нуждам конкретного клиента. Менеджер по работе с персоналом провел среди них тест Майера-Бриггса и определил индекс взаимной несовместимости между i-м техником и j-м маркетологом. Индекс варьирует от 20 (выраженная враждебность) до 1 (дружеские отношения). Результаты представлены в таблице индексов несовместимости. Составить команды так, чтобы суммарный индекс был минимальным. Решение 1. Организуйте данные так, как показано на рис. 23 "Построение команд". Отличие от транспортной задачи только в том, что все "Запасы" и "Заказы" равны единице. Сделав первую таблицу, скопируйте ее на новое место, обнулите все значения переменных решения и добавьте строчки ограничений (из единиц). Формулы для левых частей ограничений такие же, как и в предыдущей задаче. 2. Целевая функция вычисляется как сумма сумм произведений строки с индексами несовместимости и строки переменных решения. При этом нетрудно понять, что каждая такая сумма произведений есть фактически индекс образованной команды. Действительно, в строке переменных все числа равны нулю, кроме одного, которое стоит на пересечении строки с именем маркетолога и столбца с именем техника (см. рис. 24). Это число равно 1, и оно указывает на то, что команда сформирована именно из этих j двух участников. Именно эта единица, будучи умножена на индекс несовместимости участников этой команды, дает значение ЭССЙ суммы произведений, поскольку остальные произведения в этой сумме - нули. 3. Вызовите "Поиск решения". В отличие от предыдущей задачи все переменные окажутся равными 0 или 1. Однако не следует требовать явно, чтобы они были целыми и меньшими или равными 1! Анализ решения. Расчеты типа "что, если..." Альтернативные решения Решение задачи показано на рис. 24. Интересно отметить, что оно, как говорят математики, "вырождено". Это значит, что различным наборам переменных решения отвечает одно и то же оптимальное значение целевой функции. Цифры над суммарным индексом, как отмечалось выше, дают индексы сформированных команд. На рис. 24 показаны три различных набора этих индексов (соответствующих, конечно, трем различным наборам переменных решения, из которых на рис. 24 показан только последний). Получить эти различные решения можно просто, повторно запуская "Поиск решения" после нахождения очередного оптимального решения (не обнуляя переменные решения). Особенности алгоритма, используемого MS-Excel, позволяют последовательно получить 3 альтернативных решения без специальных усилий. Эти решения, разумеется, совершенно одинаковы с точки зрения поставленной нами оптимизационной задачи. Однако очевидно, что менеджер предпочтет решение, показанное в последнем столбце Действительно, при одинаковом суммарном индексе составленных команд - 38 (или среднем индексе 3,8) в этом решении нет совсем уж плохих команд. Наихудший индекс - 11 (что можно трактовать как почти нейтральные отношения), в то время как для решений, показанных в первых двух столбцах, есть команды с индексами 13 и 19. Заметим, что, как уже отмечалось ранее, наличие альтернативных решений полезно для менеджера, поскольку дает возможность выбрать из них наилучшее решение с точки зрения факторов, оставшихся неформализованными. В данном случае неформализованным осталось требование о том, что каждая из команд должна иметь индекс не хуже некоторого заданного числа. На первый! взгляд нетрудно явно ввести это требование в решение. Явное ограничение индекса команды Действительно, просто потребуем, чтобы все числа в ячейках М4-М13 (т.е. индексы образованных команд) были не больше 11. К сожалению, нельзя ограничить их меньшим числом, так как, присмотревшись к индексам несовместимости участников, нетрудно заметить, что уникальный техник "Миша" имеет минимальное значение этого индекса, как раз равное 11, и может более или менее уживаться только с маркетологом "Дашей". Таким образом, либо "Мишу" надо уволить, либо согласиться с тем, что наихудшая команда не может иметь индекс меньше 11. Остановимся пока на втором варианте. Решение модифицированной задачи показано на рис. 25видно, что в нем что-то "катастрофически не так". Переменные решения оказались не целыми. Ни о каком "спаривании" участников в команды не может быть и речи! Почему так получилось? Дело в том, что введенное дополнительное ограничение превратило нашу задачу о назначениях (по существу транспортную задачу) в обычную задачу линейного программирования. Для такой задачи специализированные "транспортные" методы решения неприменимы. А как указывалось раньше, только они обеспечивают целочисленные решения без введения явных требований целочисленности. Получившуюся общую ЛП-задачу MS-Excel решают с помощью обычного симплекс-метода, а он отнюдь не гарантирует целочисленности переменных решения. Можно возразить, что целочисленное решение этой ЛП-задачи при добавленном ограничении на индексы команды существует. Соответствующие ему индексы команд изображены на рис. 24 в крайнем справа из трех приведенных столбцов с индексами составленных команд. Почему же "Поиск решения" его не показал? Ответ заключается в том, что сформулированная ЛП-задача гоже вырожденная, т.е. несколько наборов переменных решения соответствует одному и тому же значению целевой функции. Симплекс-метод сводится к одному из решений в зависимости от того, из какой угловой точки области допустимых планов начать процесс поиска. Стандартно этот процесс начинается из начала координат (т.е. все переменные решения первоначально предполагаются равными нулю). В данном случае симплекс-метод выбрал не то решение, которого бы нам хотелось. Надо заметить, что, для того чтобы получить все оптимальные решения, необходимы специальные усилия, доступные только специалисту. Условие целочисленности Можно, разумеется, явно потребовать, чтобы все переменные решения были целыми. Введем дополнительное ограничение В17:К26- целое. В этом случае процесс решения занимает несколько большее время. "Поиск решения" должен использовать алгоритм целочисленного программирования. Решение находится только после продолжения поиска за установленным по умолчанию пределом допустимых итераций. В середине решения программа выбрасывает окно с вопросом "Достигнуто максимальное число итераций. Продолжить?". Нужно ответить "да". Правда, решение этой гораздо более сложной, чем исходная, задачи тоже занимает всего несколько секунд. Все же заметно, что время решения существенно больше, а само решение то же самое, что было получено в результате решения задачи о назначениях простыми "транспортными" методами (рис. 26). Слишком жесткие требования к максимальному индексу команд Интересно повторить решение ЛП-задачи с ограничением на индексы команд, а также решение этой задачи с явным условием целочисленности переменных решения, если потребовать, чтобы индекс каждой команды был не больше 9 (или еще меньше). Решая ЛП-задачу, "Поиск решения", не колеблясь, выдаст "оптимальный вариант" с дробными переменными решения, спарив 20% "Даши" с "Мишей", а 80% - с "Инной". В случае же явного указания целочисленности переменных "Поиск решения" будет решать задачу минут 10, прежде чем ответит, что решения нет. Мораль Введение в транспортную задачу или в задачу о назначениях не свойственных им дополнительных ограничений приводит к тому, что эффективные "транспортные" методы решения таких задач (метод "северо-западного угла", циклические перестановки м т.п.) перестают быть применимыми. В этом случае задача будет решаться с помощью общих алгоритмов решения ЛП-задач (например, симплекс-методом). Помимо того что эти методы менее эффективны, они не могут гарантировать целочисленного решения, которое обычно предполагается в транспортной задаче и абсолютно необходимо в задаче о назначениях. Прямое требование целочисленности переводит проблему в разряд моделей целочисленного линейного программирования, которые являются гораздо более трудными для решения и анализа. Рассмотренный пример позволяет сделать рекомендацию более общего характера. Не стоит беспредельно усложнять модель, пытаясь формализовать все новые и новые факторы, важные для принятия практического управленческого решения. Лучше в наиболее простой (но реалистичной) модели попытаться получить не одно, а множество альтернативных оптимальных (или близких к оптимальному, "хороших") решений и выбрать среди них такое, которое бы наилучшим образом удовлетворяло всем оставшимся неформализованными факторам. Заключение к разделу 5 Постановка транспортной задачи предусматривает задание двух таблиц: таблицы транспортных издержек для перевозок единицы груза c jj и таблицы объемов перевозок X ij от i-го поставщика к j-му потребителю. Эти таблицы имеют mстрок (по числу поставщиков) и nстолбцов (по числу потребителей). Необходимо также задать запасы поставщиков, готовые к вывозу (столбец S i ) и величины заказов потребителей (строка D j ). Транспортная задача обязательно должна обладать свойством сбалансированности: сумма запасов производителей должна быть равна сумме заказов потребителей. Если это условие в реальности не выполняется, необходимо сбалансировать задачу, а именно: • если сумма запасов превышает сумму заказов, в таблицы издержек и перевозок нужно ввести лишнюю строку "фиктивного потребителя", который "заказывает" весь реальный избыток запасов поставщиков. При этом транспортные издержки при перевозке запаса от любого реального поставщика к "фиктивному потребителю" должны быть равны нулю. Перевозки, "доставленные" к "фиктивному потребителю" от каждого поставщика, означают, что эти запасы реально остались на складах поставщиков; • если сумма заказов превышает сумму запасов, в таблицы издержек и перевозок нужно ввести лишний столбец "фиктивного поставщика", который "предлагает" покрыть весь дефицит запасов реальных поставщиков. При этом транспортные издержки при перевозке запаса от "фиктивного поставщика" к любому реальному потребителю должны быть равны нулю. Перевозки, "доставленные" от "фиктивного поставщика" каждому реальному потребителю, означают величину непоставленного запаса этому потребителю. Сбалансированность и специальная структура ограничений транспортной задачи обусловливают важное свойство оптимального плана перевозок: его следует искать только среди множества опорных планов. Опорным называется такой план, в котором количество ненулевых перевозок равно сумме количеств поставщиков и потребителей минус единица. В связи с этим алгоритм решения транспортной задачи разбивается на две стадии: • запись какого-нибудь опорного плана; • переход от одного опорного плана к другому, с меньшими суммарными затратами.И для той и для другой стадии разработаны алгоритмы, гораздо более эффективные, чем обычный симплекс-метод. Важной особенностью этих алгоритмов является целочисленность оптимального плана перевозок (при условии, что запасы и заказы - целые). При решении транспортной задачи с помощью MS-Excei "Поиск решения" автоматически выберет специальные эффективные алгоритмы решения и обеспечит целочисленность решения (без специального требования целочисленности!), если организация данных и введенные ограничения соответствуют транспортной задаче. Задача о назначениях представляет собой частный случай транспортной задачи с числом строк (поставщиков), равным числу столбцов (потребителей). Каждый "поставщик" (это может быть рабочий) предлагает самого себя одному из "потребителей" (это может быть операция, станок или напарник). Поэтому все "запасы" и "заказы" в задаче о назначениях равны 1. |