Организация снабжения и управление трудовыми ресурсами

В этом разделе будут рассмотрены две модели, исключительно широко использующиеся в деловой практике: транспортная задача и задача о назначениях. Обе они реализуются в виде ЗЛП, но имеют весьма характерные особенности, которые можно эффективно учитывать при решении таких задач средствами MS Excel.

1. Транспортная задача

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

Постановка задачи.

Пусть требуется развести груз, хранящийся на т. складах А],А2,...Ат в количествах ai,a2,...,am соответственно по

п пунктам назначения Вх,В2,...Вп , подавшим заявки на b\,b2,...,bn единиц груза. Пусть запас груза на всех складах равен суммарной заявке, то есть:

т

п

Известно, что стоимость перевозки единицы груза от г-го склада к у-му потребителю равна с Требуется составить такой план перевозок, чтобы все заявки были выполнены, а стоимость всех перевозок была минимальна.

Математическая модель. Пусть х1; — количество груза, перевозимого со склада А, потребителю В ¦ Прямоугольную матрицу, составленную из величин х , будем называть планом перевозок.

• Суммарное количество груза, перевозимое с каждого склада потребителям, должно быть равно запасу на данном складе. То есть:

хи + .х12              =fl,

*21 +*22 +—+*2Л

*»| +хп,2 + - + *™ =а.

• Суммарное количество груза, доставляемое каждому потребителю со складов, должно быть равно заявке данного потребителя:

хи +x2l +              =ЬХ

• Суммарная стоимость всех перевозок должна быть минимальной

М П

В данной модели суммарные поставки равны общему количеству заказов.

Пример 1

Пусть имеются п=4 поставщика и m = 5 потребителей. Издержки перевозки единицы груза от г-го поставщика в /-й пункт назначения, запасы поставщиков и заказы потребителей приведены в таблице.

Требуется оптимизировать план перевозок.

Решение.

Организуем данные в MS Excel так, как показано на рис. 10.18

ш В ячейках 14—17 укажем суммы произведения цены перевозки единицы груза на объем перевозки от г-го поставщика к любому потребителю. В ячейке 18 — сумму этих сумм, являющуюся целевой функцией, которую нужно минимизировать.

• В ячейки 111:114 введем ограничения на количества груза, которые нужно увезти от каждого поставщика. В ячейках B16:F16 = 0 стоят ограничения на количества груза, которые нужно привезти к каждому потребителю.
• Вызовем процедуру Поиск решения и укажем параметры: целевая ячейка 18 ( Минимум), Изменяя ячейки: B11:F14, Ограничения: В11: F 14 gt; 0 (перевозки неотрицательны), 111:114 = 0 (ограничения на количества груза от каждого поставщика), B16:F16 — 0 (ограничения на количества груза для каждого потребителя).

При такой организации данных все перевозки окажутся целыми числами (если целыми являются числа в колонках «Запасы» и строке «Заказы»).

• Проверим, что в полученном решении ровно m -I- п - 1 = 8 ненулевых перевозок.

В итоге мы получим минимальную величину издержек, равную 980 единицам. Если повторить расчет, максимизируя транспортные издержки, то можно оценить отличие наилучшего варианта от наихудшего. Наихудший вариант даст величину издержек, равную 1459, то есть в худшем случае издержки увеличатся по сравнению с оптимальным вариантом на 479 денежных единиц.

2. Несбалансированные транспортные задачи.

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

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

Во втором случае предстоит решать, как распределить дефицит между потребителями. Разумеется, в реальности этот случай сложнее для менеджера, отвечающего за доставку заказов потребителям. Решение проблемы будет, по-видимому, определяться приоритетом каждого из потребителей для поставщика или исходом переговоров. Однако, если предположить, что все потребители имеют одинаковый рейтинг и проблема состоит только в том, чтобы подешевле развезти весь имеющийся на складах поставщика товар, то этот второй случай с точки зрения оптимизации издержек симметричен первому. Рассмотрим оба случая.

Несбалансированность: излишек запасов.

Рассмотрим этот случай сначала на примере решения способом, рассмотренным выше.

Пример 2

Пусть требуется минимизировать затраты на перевозку товаров от 3 предприятий-производителей на торговые склады 5 городов, куда необходимо поставить 180, 80, 200, 160 и 220 единиц товара соответственно. При этом необходимо учесть возможности поставок каждого из производителей при максимальном удовлетворении запросов потребителей и затраты на перевозку единицы товара.

Как видно из таблицы, заводы могут поставить 850 единиц товара, а суммарная потребность составляет 840. Решение.

и Организуем данные задачи, как показано на рис. 10.20 (данные и формулы для других трех складов вводятся аналогично).

Здесь ячейка В20 содержит значение целевой функции, а диапазон C8:G10 - значения, соответствующие перевозкам (первоначально заполним произвольными значениями, например, 1).

Выполняя поиск решения, укажем следующие параметры

Найденное оптимальное решение будет иметь вид (рис. 10.22).

Здесь в таблице перевозок указано, какое количество товара на какой склад должен доставить каждый завод- изготовитель.

Затраты, которые будут иметь место при реализации данного плана, будут равны в общей сложности 3 200р.

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

в таблицу транспортных издержек и в таблицу перевозок добавляется по одному лишнему столбцу (Склад 6). Это можно трактовать так, как если бы появился еще один, фиктивный, потребитель. При этом заказ «фиктивного потребителя» в точности равняется разности между суммой всех запасов и суммой всех заказов

а издержки перевозок грузов к нему от любого поставщика равняются нулю.

Выполнив процедуру Поиск решения, получим результат в виде таблицы перевозок (рис. 10.23), из которой видно, что остаток товара в 10 единиц будет иметь Завод 1. Заметим, что значение целевой функции по-прежнему равно 3 200р.

Рис. 10.23 324

Несбалансированность: дефицит запасов

В случае дефицита запасов, т.е. когда

добавим в таблицу транспортных издержек и в таблицу перевозок по одной лишней строчке. Это можно трактовать так, как если бы появился еще один, фиктивный, поставщик. Потребуем, чтобы запас этого «поставщика» в точности равнялся разности между суммой всех заказов и суммой всех запасов, а издержки перевозок грузов от него к любому поставщику были равны нулю. Добавим в таблицу с примером поставщика Завод 4, поставляющего недостающие 10 единиц товара, и выполним процедуру Поиск решения. Полученное решение показывает, что на Склад 3 будет доставлен товар от фиктивного поставщика, что по сути означает недопоставку в 10 единиц товара на этот склад (рис. 10.24). Значение целевой функции при этом уменьшится до 3 140р.

Запрещенный маршрут.

Еще одно возможное осложнение транспортной задачи — это запрещение определенной перевозки от г-го поставщика у-му потребителю для составляемого плана перевозок (ремонт дороги, неплатеж и пр.). В этом случае, естественно, можно было бы просто ввести ограничение хи = 0 Однако это означает невозможность использования эффективных «транспортных» алгоритмов решения.

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

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

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

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

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

выполнения той или иной операции данным работником) должна быть квадратной.

Кроме того, в задаче о назначениях от каждого поставщика к каждому потребителю поставляется только одна единица «груза» (например, только одного рабочего можно назначить для выполнения данной работы) или ни одной. Поэтому все «запасы» и все «заказы» равны 1.

Понятно, что все переменные решения в задаче о назначениях могут принимать только значения 1 или 0. На первый взгляд, это похоже на задачи целочисленного линейного программирования. Однако в силу особенностей структуры ограничений транспортной задачи явно требовать целочисленность переменных решения (как их равенства только нулю или единице) не требуется. Такие значения получаются при решении автоматически.

Постановка задачи. Требуется назначить п работников для выполнения п типовых операций. Из данных исследований эффективности труда известно, насколько эффективно каждый работник выполняет конкретную операцию (например, сколько времени ему требуется на ее выполнение или сколько стоит его труд). Как распределить работников по операциям, чтобы суммарные затраты рабочего времени были минимальны?

Рассмотрим конкретный пример.

Пример 3

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

Виды работ

Определить, какому рабочему следует поручить выполнение какой операции, чтобы стоимость всей работы в целом была минимальной.

Решение.

1. Организуем данные, как показано на рис. 10.24.
2. Выделим целевую ячейку F19 и вызовем процедуру Поиск решения.
3. Укажем параметры, как показано на рис. 10.25.

4. Выполним процедуру и получим результат, представленный на рис. 10.26.

При этом в таблице занятости появятся 1 на пересечении строк и столбцов, соответствующих назначений. Как видно из рисунка, работник а5 не получил никакого назначения.[55]

В заключение раздела еще раз отметим, что транспортная задача обязательно должна обладать свойством сбалансированности: сумма запасов производителей должна быть равна сумме заказов потребителей. Если это условие в реальности не выполняется, необходимо сбалансировать задачу, а именно:

т если сумма запасов превышает сумму заказов, в таблицы издержек и перевозок нужно ввести лишнюю строку «фиктивного потребителя», который «заказывает» весь реальный избыток запасов поставщиков. При этом транспортные издержки при перевоз

ке запаса от любого реального поставщика к «фиктивному потребителю» должны быть равны нулю. Перевозки, «доставленные» к «фиктивному потребителю» от каждого поставщика, означают, что эти запасы реально остались на складах поставщиков;

• если сумма заказов превышает сумму запасов, в таблицы издержек и перевозок нужно ввести лишний столбец «фиктивного поставщика», который «предлагает» покрыть весь дефицит запасов реальных поставщиков. При этом транспортные издержки при перевозке запаса от «фиктивного поставщика» к любому реальному потребителю должны быть равны нулю. Перевозки, «доставленные» от «фиктивного поставщика» каждому реальному потребителю, означают величину недопоставленного запаса этому потребителю.

При решении транспортной задачи с помощью процедуры MS-Excel Поиск решения она автоматически выберет специальные эффективные алгоритмы решения и обеспечит целочисленность решения (без специального требования целочисленности), если организация данных и введенные ограничения соответствуют транспортной задаче.

Задача о назначениях представляет собой частный случай транспортной задачи с числом строк (поставщиков), равным числу столбцов (потребителей). Каждый «поставщик» (это может быть рабочий) предлагает самого себя одному из «потребителей» (это может быть операция, станок или напарник). Поэтому все «запасы» и «заказы» в задаче о назначениях равны 1.

Вопросы для самопроверки

1. Перечислите особенности транспортных задач, позволяющие выделить эти задачи в отдельный класс ЛПЗ и использовать специальные эффективные методы для их решения.

2. Что означает условие сбалансированности транспортной задачи? Почему его соблюдение столь необходимо?
3. Как сбалансировать транспортную задачу, если запасы постав

щиков превосходят заказы потребителей? Как узнать, какое количество запасов останется невывезенным у каждого поставщика?

4. Как сбалансировать транспортную задачу, если заказы потре

бителей превосходят запасы поставщиков? Как узнать, какое количество запасов недополучит каждый потребитель?

5. Каким образом можно добиться, чтобы в оптимальном пла

не перевозка от конкретного поставщика к конкретному потребителю была запрещена (если этого требуют обстоятельства)? Почему не стоит вводить в качестве дополнительного ограничения требование равенства нулю соответствующей переменной решения X = О?

6. Нужно ли вводить условие целочисленности при решении транспортной задачи, если все запасы и заказы целые? Объясните почему?
7. Объясните, что общего и в чем различия транспортной задачи и задачи о назначениях.?

Упражнения

1. Пусть имеются 4 поставщика и 5 потребителей. Издержки перевозки единицы груза от і-го поставщика в j-й пункт назначения, запасы поставщиков и заказы потребителей даны в таблице. Оптимизировать план перевозок.

2. Расстановка рабочих по операциям.

Мастер должен расставить 4 рабочих для выполнения 4 типовых операций. Из данных хронометрирования известно, сколько минут в среднем тратит каждый из рабочих на выполнение каждой операции. Эти данные представлены в таблице.

Как распределить рабочих по операциям, чтобы суммарные затраты рабочего времени были бы минимальны?

Замечание. Отметим, что в данном разделе рассмотрена лишь незначительная часть задач оптимизации. В частности, в терминах задач математического программирования могут быть сформулированы также задачи о ведении портфеля ценных бумаг, управлении капиталом, формировании графика занятости, управления запасами и другие.