Приемы решения задач

С шести асфальтобетонных заводов должен вывозиться асфальт для строительства 5 участков автодорог области. Транспортные издержки при перевозках, разумеется, в общем различны (см.

Транспортные издержки

чего, очевидно, недостаточно.

Менеджер подрядной организации хочет минимизировать транспортные расходы для данных условий.

a. Каковы наименьшие транспортные издержки?

b. Сколько машин и на какие участки будет недопоставлено?

c. После составления плана менеджер получил указание, по причинам неэкономического характера, план поставок асфальта для участка А необходимо выполнить полностью. Каковы транспортные издержки нового плана? Сколько машин и на какие участки будет недопоставлено в этом случае?

ё. При утверждении нового плана у руководства, выяснилось, что из-за аварийного состояния моста перевозка асфальта с АБЗ 21 на участок Е по прямому маршруту невозможна. Объездной маршрут увеличивает стоимость рейса на 300 рублей. Насколько при этом возрастут транспортные расходы? Что выгоднее, оставить почти утвержденный план, несмотря на увеличении издержек, или составить новый план с учетом сложившейся ситуации?

е. Есть ли у задачи альтернативные решения?

Решение задачи.

В данном случае перед нами простая транспортная задача. Правда, дополнительные вопросы могут оказаться не такими уж простыми, но, в любом случае, задачу следует сначала решить в основной постановке.

Как обычно, сначала проверяем, сбалансирована ли задача, так как дисбаланс сразу нужно будет учесть при правильной организации данных на листе Excel. Общее количество машин асфальта, которые можно вывезти с заводов - 287 штук. Общий заказ дорожно-строительных бригад - 317 машин. Действительно, как и сказано в тексте задачи имеется дисбаланс заказов и запасов. Размер дисбаланса - 30 машин.

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

В данном случае фиктивный поставщик асфальта носит гордое имя АБЗ X.

Так как стоимость перевозок от отдельных поставщиков нас не интересует, мы рассчитываем сразу суммарную стоимость перевозок, перемножая таблицу перевозок Б12:Б18 на таблицу цен Б2:Б8 с помощью функции =СУММПРОИЗВ( ). Суммарная стоимость всех перевозок и есть целевая функция задачи (ячейка 09).

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

Вызываем надстройку Поиск решения и ставим задачу. Целевая ячейка - 09, цель - минимум издержек. Изменяемые ячейки - таблица перевозок Б12:Б18. Параметры решения - линейная модель и неотрицательные значения переменных. Ограничения - Б19:Б19=0 и 012:018=0. Жмем кнопку Выполнить и получаем, если вы нигде не ошиблись, сообщение, что решение найдено (Рис. 66).

Напоминаем, что числа вида 2.1Е-09 - это малые десятичные дроби в

научной форме записи. Надстройка Поиск решения, при заданной точности решения, не отличает их от нуля. Не будем придираться и мы, так как в остальном решение нас устраивает. План составлен, общие издержки - 251 950 руб. - минимальные из всех возможных при выполнении заказов бригад.

Как мы можем видеть, не повезло только бригаде, работающей на участке А. Все недопоставленные машины пришлись на их долю (перевозки от поставщика АБЗ Х).

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

До сих пор мы не задавали в ценах перевозок от фиктивного поставщика разных цен. Но делали мы это именно потому, что хотели поставить всех клиентов в равные условия, по отношению к такому фиктивному поставщику. А что, если условия не равные? В таком случае мы можем поставить в качестве цены перевозки от АБЗ Х на участок А какое-нибудь большое число, которое фактически запретит данную перевозку для Поиска решения.

Ставим цену 10 тыс. за машину и вновь ищем решение (Рис. 67).

Теперь вся недопоставка пришлась на долю участка С. Общая цена вопроса

10.5 тыс. рублей - именно на столько возросли издержки перевозок после волевого решения выполнить план поставок на участок А.

Для ответа на вопрос d сначала изменим цену перевозки от АБЗ 21 на участок Е на 300 рублей и позволим Excel пересчитать текущие издержки. Получаем общие издержки в 282 550 рублей, что выше, чем в последнем плане перевозок на 20 100 руб. Это не удивительно, так как в соответствии с планом перевозок мы везли по этому маршруту 67 машин асфальта.

Попробуем оптимизировать план перевозок, для этого еще раз запустим Поиск решения.

Как вы видите (Рис.

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

2. П-2. Поставки двух видов продуктов

Менеджер отдела логистики составляет план перевозок продукции фирмы с 3 ее складских комплексов База 1, ... База 3 к четырем клиентам: X, У, Z и Ж. Речь идет о перевозках двух видов продукции: А и В.

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

a. Составьте план перевозок, минимизирующий транспортные издержки. Если спрос по отдельным позициям удовлетворить невозможно, руководствуйтесь минимумом издержек для себя.

b. Каков наихудший план перевозок?

Решение задачи.

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

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

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

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

Теперь задача оказывается не сбалансированной по обоим продуктам: продукта А имеется в запасах 71 ед., а заказано клиентами 81 ед., продукта В в запасах 120 ед., а заказано клиентами 110 ед. Так что задачу придется балансировать искусственно.

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

В данной задаче в качестве целевой функции разумно выбрать полные издержки по перевозкам. Подсчитаем их по формуле

=СУММПРОИЗВ(С3:К9;С13:К19), где таблица С3:К9 содержит цены перевозок, а таблица переменных С13:К19 - количества грузов, перевозимые по каждому из допустимых маршрутов. Целью оптимизации, разумеется, выбираем поиск минимума.

В строке С20:К20 подсчитываем баланс выполнения заказов, а в столбце Ь13:Ь19 - баланс вывоза запасов.

В принципе, можно было бы ставить задачу Поиску решения, но давайте еще раз посмотрим таблицу цен перевозок. В исходной таблице цен пустые ячейки означали отсутствие соответствующей перевозки. Например, пустая ячейка Б3 показывает, что никакой перевозки, способной при отгрузке получить 1 единицу продукта А с базы 1, а доставить 1 единицу продукта В клиенту Х не существует. Однако для надстройки Поиск решения пустая ячейка означает нулевую цену и такие перевозки будут запланированы. Поэтому нам следует запретить все подобные перевозки.

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

При этом цены фиктивных перевозок должны остаться равными 0.

Теперь можно искать решение.

В полученном решении (Рис. 70) недостающие 10 единиц продукта А будут недопоставлены клиенту У, а излишек продукта В целиком останется на базе 3.

Минимальная общая стоимость перевозок составит 104 760 рублей.

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

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

Проще всего это сделать через меню Правка\Заменить... -gt; Найти: 10000, Заменить на: -10000, Заменить все.

После замены запускаем Поиск решения вновь и меняем цель поиска на максимум.

В полученном решении (Рис. 71) суммарная стоимость перевозок

возрастает до 122930 рублей. Таким образом, наихудший план отличается от лучшего меньше чем на 20%, что дает определенную свободу выбора среди возможных планов перевозок.

2. П-3. Компью-Нет

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

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

b. Каков наихудший индекс совместимости у отобранных пар?

c. Определите, сколько имеется лучших, в смысле суммарного индекса, решений.

ё. Можно ли так подобрать пары, чтобы ни один индекс совместимости не превышал 6?

Решение задачи.

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

Сначала скопируем таблицу данных и вставим ее чуть ниже по странице. Выделим в ней область данных и сотрем их - в освобожденных ячейках, в данном случае В11:016, будут располагаться переменные задачи (Рис. 72)

Так как эта задача - задача о назначениях, то переменные должны в итоге принять какое-либо из двух возможных значений: 0 или 1. Значение переменной 1 в ячейке С14, к примеру, означает, что будет создана команда из программиста Николая и специалиста по маркетингу Маши. И напротив, если в ячейке, находящейся на пересечении некоторого столбца и некоей строки, содержится 0, значит, данная команда не будет создана. При этом, если найти суммы переменных по столбцам или строкам, как это сделано в представленной таблице, то все они в правильном решении должны оказаться равными 1. Это будет означать, что каждый из программистов назначен только в одну команду, как и каждый из специалистов по маркетингу.

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

Далее, для построения целевой функции, нужно рассчитать суммарный индекс совместимости команд. Его можно вычислить используя всего одну хорошо известную нам формулу =СУММПРОИЗВ( ), если применить ее не для двух строк или столбцов, а для двух таблиц. Разумеется размер таблиц так же должен совпадать.

Итак, запишем в ячейку I8 формулу: =СУММПРОИЗВ(Б2:07;Б11:016). Если в нижней таблице - таблице переменных B11:G16 - будут содержаться только нули и шесть единиц, формирующих пары, результатом выполнения функции станет сумма индексов совместимости для всех шести пар. При показанном в таблице (Рис. 72) состоянии переменных результатом вычисления функции будет число 9, на которое умножится единственная единица, соответствующая паре Маша-Николай.

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

Если записать в ячейке I2 формулу =СУММПРОИЗВ(В2^2;В11^11), то мы сможем вычислить индекс пары, которую техник-программист Иван составит с кем-либо из специалистов по маркетингу. Протягивая формулу вниз, на ячейки I3:I7, мы получим такие индексы для всех остальных пар, так как в каждую пару обязательно входит один из техников-программистов.

Безусловно, можно было бы вычислять индексы и для пар, составляемых специалистами по маркетингу с кем-либо из программистов. Для этого в строке Б9 нужно было ввести формулу =СУММПРОИЗВ(В11:В16;В2:В7), и протянуть ее вправо. Результат, в смысле составляемых пар, в обоих случаях один и тот же.

Теперь все готово для решения задачи. Вызываем Поиск решения и указываем целевую ячейку - I8. Так как чем меньше индекс, тем лучше, в качестве цели указываем поиск минимума. Переменные задачи В11^16. В параметрах обязательно указываем, что подразумевается линейная модель и что переменные неотрицательны. Ограничений в задаче о назначениях, как и в транспортных задачах, должно быть всего 2 (групповых). Ограничение H11:H16=H2:H7 требует, чтобы каждый из техников-программистов был назначен только один раз (столбец H2:H7 содержит только единицы), а ограничение В17^17=В8^8 требует того же для специалистов по маркетингу.

Замечание: В ограничениях можно было бы написать и H11:H16=1 и В17^17=1, однако это было бы не в духе идеологии Excel. Первый способ является более гибким для модификации и исследования исходной задачи. В прочих задачах вы в этом убедитесь. Кроме этого, в такой форме записи ограничений задача о назначениях полностью совпадает с транспортной, что позволяет использовать для решения нескольких разных задач один и тот же однажды сделанный шаблон.

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

Результатом решения будет следующая таблица (Рис. 73).

Суммарный индекс совместимости равен 19. Таблица переменных дает распределение по парам: Иван-Аня, Михаил-Маша, Павел-Лиза, Николай-Ольга,

Рис. 73

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

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

К сожалению, надстройка Поиск решения не имеет какого-либо механизма, позволяющего получить все такие решения. Можно, однако, получив одно решение, запустить Поиск решения еще раз, не обнуляя переменные. В случае, если есть и другие решения, новое решение будет получено. Несколько раз запуская Поиск решения и сохраняя полученный результат вы можете получить набор вариантов разбиения, имеющих различные индексы пар, но одинаковый суммарный индекс.

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

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

Чтобы вернуться к исходному решению следует стереть все переменные и повторить расчет.

Итак, имеется 2 решения задачи с суммарным индексом совместимости 19. Так как в обоих решениях самый плохой индекс 8, то ни одно из них не имеет какого-либо преимущества.

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

Как мы увидели при поиске оптимального решения, во всех альтернативных планах решения лучше, чем с максимальным индексом 8, нет. Но значит ли это, что вообще плана с индексами не хуже 6 не существует? Разумеется, нет.

Вполне могут существовать множество планов с индексами не хуже 6, но зато с суммарным индексом выше 19! Поиск решения, естественно, игнорирует эти планы, потому что ищет план с наименьшим суммарным индексом. Но мы готовы пойти на ухудшение суммарного индекса, если максимальный из индексов команд будет меньше 8.

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

Попробуем потребовать, чтобы ни один индекс совместимости команд не превышал 6: 12:17lt;=6. Добавляем это ограничение в список Поиска решения и запускаем на выполнение.

Первое, на что следует обратить внимание, это факт, что требуемое решение найдено. Теперь рассмотрим полученное решение внимательней (Рис. 74.).___________________________________________

Рис. 74.

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

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

В задачах линейной оптимизации для «борьбы» с нецелыми решениями мы использовали целые или двоичные ограничения на переменные. Поступим здесь так же, добавим условие, что все переменные - двоичные (0 или 1) и снова попробуем решить задачу (Рис. 75).

Рис. 75

В данном случае решение так же найдено и теперь удовлетворяет всем нашим ожиданиям. Да, максимальный коэффициент 6. Да, все назначения либо 0, либо 1. И, наконец, суммарный индекс выше, чем в оптимальном решении, полученном нами ранее.

Задача решена. Но давайте проделаем еще небольшое исследование.

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

По той же таблице можно проанализировать, действительно ли такое решение возможно. Однако, во-первых, быстрее изменить ограничение в Поиске решения и получить ответ автоматически, а во-вторых, все равно для большой таблицы такой анализ «вручную» невозможен. Поэтому изменим ограничение І2:І7lt;=6 на 12:17lt;=4 и снова поищем решение.

Увы, Поиск решения сообщает, что решение не найдено. Это означает, что нельзя назначить 6 пар так, чтобы коэффициенты были не хуже 4. А если не хуже 5?

Проверяем и убеждаемся, что такого решения тоже не существует. Придется остановиться на коэффициентах не хуже 6.

Обратите внимание, что если после получения резюме Поиска решения о том, что решение не найдено, нажать кнопку ОК, на листе с задачей сохранится НЕ решение, а просто итог поиска. Состояние задачи, на котором надстройка пришла к заключению, что решения не существует. Например такой (Рис. 76).

Рис. 76

Зачастую такой результат может подсказать, какое условие не удается выполнить. В таком случае Поиск решения останавливается в состоянии, когда удовлетворены все условия, кроме одного, и это можно увидеть.

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

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

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

2. П-4. Распределение аудиторов по фирмам

Менеджер - координатор аудиторской фирмы должен распределить аудиторов для работы на следующий месяц. Аудиторы различаются по квалификации и опыту работы. Прежде чем приступить к аудиту конкретной фирмы они должны затратить определенное время на подготовку и консультации. В данный момент имеются заявки от 10 клиентов. Менеджер - координатор, учитывая опыт работ аудиторов каждой конторы, оценил время, необходимое «среднему» аудитора каждой конторы для подготовки к аудиту конкретного клиента. Результаты представлены в таблице.

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

b. Найдите оптимальное распределение аудиторов в случае, если назначение клиенту аудиторов только из одной конторы нежелательно.

Решение задачи.

В данном случае мы имеем дело с транспортной задачей, так как аудиторы из одной конторы могут быть назначены разным клиентам одновременно, т.е. мы не ищем только соответствия контора - клиент. Следовательно, в задаче требуется найти, сколько аудиторов из Гаапвила будет назначено 1-му, 2-му. 3-ему, ... 10-му клиентам, сколько аудиторов из Финанстауна будет назначено 1-му, 2-му. 3-ему, ... 10-му клиентам и т.д. для остальных контор. В соответствии с этим в задаче должно быть не менее чем 40 переменных (4 конторы х 10 клиентов). Однако прежде чем строить задачу необходимо убедиться, что задача сбалансирована.

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

В качестве примера организации данных на листе Excel можно предложить следующую таблицу (Рис. 77).

Обратите внимание на изменение исходной таблицы временных затрат на подготовку к аудиту.

Во-первых, временные затраты для добавочного фиктивного клиента не заданы вообще. Правильно ли это? На самом деле, так как в Excel пустые ячейки при вычислениях полагаются содержащими 0, временные затраты заданы и равны 0. Можно ли задать какое-либо другое значение в этих ячейках? Вообще-то можно, результаты минимизации при этом не изменятся. Однако какое число вы могли бы подставить вместо нулей? Видимо, любое произвольное число. Но, так как часть аудиторов будет неизбежно назначена этому фиктивному клиенту, заданное вами произвольное число войдет в целевую функцию, являющуюся суммарными временными затратами всех аудиторов! Таким образом целевая функция будет показывать не реальные временные затраты, а некий индекс. Его, разумеется, можно пересчитать к реальным временным затратам, вычтя из него 15 умноженное на заданное вами произвольное число. А это, в свою очередь, эквивалентно тому, что вы сразу зададите в качестве временных затрат для фиктивного клиента нулевые значения.

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

Во-вторых, в пустых ячейках проставлено число 99. Эти изменения связаны с необходимостью запретить назначения аудиторов из Финанстауна седьмому клиенту и аудиторов из Нью-Баланс - второму и девятому клиентам. Здесь уместно напомнить, что в транспортной задаче не должно быть лишних ограничений. По существу их всего два - все заказы должны быть в точности исполнены и все аудиторы должны быть распределены по клиентам. Поэтому писать в ограничениях Поиска решения что-то вроде переменная С 14=0 не следует. Нужно просто задать в таблице такое произвольное значение времени подготовки, чтобы Поиск решения сам отказался от нежелательных для вас назначений. Так как мы будем искать минимум временных затрат, то следует, очевидно, записать в пустых ячейках какие-либо числа, гораздо большие самого большого числа в таблице. Мы уже находили это число (26), следовательно, можно эффективно запретить назначения, записав в пустые ячейки 100, или 1000, или 10000 и т.д. Мы проставили число 99 исключительно с целью уменьшить ширину таблицы для данной книги.

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

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

Конечно, это именно потому, что соответствующие назначения в случае с запретами не будут сделаны! А раз переменные в таблице снизу С14, Н12 и Л4 останутся равными 0, то на какое бы число мы их не умножали при расчете суммарных затрат, результата они не изменят.

В-третьих, в строку заказов В7:К7 мы добавили число 15 в ячейке Ь7 - фиктивный заказ добавленного клиента.

С учетом этих изменений количество переменных достигло 44 (В11:Ь14).

Чтобы рассчитать реальные издержки времени на подготовку для всех контор в сумме запишем в ячейку М7 формулу =СУММПРОИЗВ(В3:Ь6;В11:Ь14). Это и будет целевая функция задачи.

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

Если записать в ячейку В15 формулу =СУММ(В11:В14)-В7, то мы подсчитаем разницу между заказом первого клиента (В7) и числом назначенных ему аудиторов. Эта разница, в случае правильного решения задачи, должна быть равной нулю. Протянем формулу вправо, на оставшихся 10 клиентов (включая фиктивного). Аналогичную формулу используем для контроля использования аудиторов контор. Запишем в ячейку М11 формулу =СУММ(В11:Ь11)-М3 и протянем ее вниз. В постановке задачи для Поиска решения мы должны будем потребовать, чтобы ячейки В15:Ь15=0 и М11:М14=0.

Почему в данном случае мы предлагаем сравнивать разницу между заказом и назначением с нулем, а не просто сравнивать заказы и назначения? Конечно, не потому, что имеется какая-либо разница в результате решения. Эти изменения связаны с тем, что для контроля правильности решения, которое будет получено, неплохо будет и визуально проверить результаты. А в этом случае значительно проще сравнивать все получаемые числа с нулем, чем друг с другом. Если мы ожидаем, что при правильном решении получатся нули, то сможем сразу увидеть, если это будет не так. В предыдущей задаче суммы заказов мы и так сравнивали практически с одним и тем же числом - единицей, так что там не имело смысла усложнять формулы.

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

После запуска Поиска решения на выполнение получаем следующее решение (Рис. 78).

Как мы видим общие затраты составили 950 рабочих часов. При этом фиктивному заказчику назначены 3 аудитора из конторы Гаапвил и 12 аудиторов из конторы Финанстаун - в реальности эти аудиторы не будут заняты в предстоящий период.

Как мы можем убедиться, запрещения назначений, сделанные нами, так же сработали правильно. При этом аудиторы Гаапвила назначены шести клиентам (1­му - 4, 3-му - 2, 4-му -11, 5-му - 7, 8-му -3 и 10-му - 5), а аудиторы Финанстауна, Исабурга и Нью-Баланса - двум клиентам каждый.

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

Замечание: если вы при расчете получили в некоторых ячейках своей таблицы вместо нулей числа вроде 3.9Е-10, не волнуйтесь. Это число в научной форме записи, есть очень маленькая дробь - 39 деленное на сто миллиардов. Так как программа ищет решение не абсолютно точное, а приближенное, то для нее это число с приемлемой точностью уже не отличается от нуля. Часто можно получить несколько более точный результат, увеличив количество итераций во вкладке Параметры со 100 (по умолчанию) до 10000. Но можно и просто не обращать внимания на эти малые числа. Правильное решение все равно получено.

Следующий вопрос задачи, который на первый взгляд выглядит так невинно, перемещает нас из области транспортных задач в область задач линейного программирования, так как ответ на него нельзя получить без увеличения числа ограничений. Но в рамках обычной задачи линейного программирования решение оказывается несложным. В сущности, ведь чего нам нужно добиться? Чтобы ни одна из переменных, относящихся к назначениям аудиторов для любого клиента не была равна сумме назначений для этого клиента. В этом случае хотя бы один аудитор среди назначенных клиенту будет из «второй» конторы.

Давайте дублируем лист с таблицей (щелкнуть по ярлыку правой кнопкой мыши, выбрать Переместить/Скопировать, отметить создавать копию, ОК) и изменим формулы в строке В15:Ь15. Запишем в ячейку В15 формулу =СУММ(В11:В14) и протянем ее вправо. Затем в ячейке В17 запишем формулу для разницы между переменной и заказом в целом =В11-В$15. Эту формулу нужно растянуть так, чтобы охватить все переменные, то есть на область В17:К20. Фиктивного клиента мы здесь пропускаем, так как на него ограничение не распространяется - можно отставить аудиторов только одной фирмы. После этого возвращаемся в Поиск решения и меняем введенное ранее условие В15:Ь15=0 на В15:Ь15= В7:Ь7. Мы снова вернулись к обычному виду этого ограничения для того, чтобы не считать еще раз суммы назначений аудиторов для клиентов.

Теперь добавим новое ограничение, позволяющее назначить каждому клиенту аудиторов не менее чем из двух контор. Судя по всему такое решение существует, какой-нибудь пример подобного решения можно найти и вручную. Однако оптимальное решение найдет нам Поиск решения, после того, как мы потребуем, чтобы все числа в таблице В17:К20 были меньше или равны -1 (ноль соответствует нежелательному назначению всех аудиторов из одной конторы). Приведем часть полученной таблицы, относящуюся к решению (Рис. 79).

Как мы видим, общее количество часов, затраченных на подготовку, выросло до 982. При этом во всех случаях аудиторы назначаются из двух контор. Несколько изменились и количества не назначенных аудиторов - теперь из Гаапвила не использованы 8 аудиторов, а из Финанстауна только 7.

Постойте, а почему же, если задача решалась симплекс-методом, а не транспортным алгоритмом переменные остались целыми? В данном случае это просто случайность - оптимальное решение оказывается целым и никакое решение не в целых числах не лучше полученного. А в общем случае могли получиться и дробные назначения: полтора аудитора одному клиенту, а 0.5 другому.

2.П-5. Заводы ЖБИ

Корпорация “Современные железобетонные изделия” имеет в

окрестностях и черте города 5 небольших заводов ЖБИ (ЖБИ 1,ЖБИ 2, ... ЖБИ 5). Кроме этого, у корпорации есть 3 охраняемых площадки-склада (Склад А, Склад В, Склад С) для временного хранения изделий, хотя корпорация старается работать на заказ. В настоящий момент в отделе продаж имеется заказ от строительной фирмы на поставку новых ж\б блоков высокой прочности в количестве 1050 шт. Учитывая прочие заказы заводы могут за обусловленный срок поставить следующее количество блоков:

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

Строительная компания заказывает поставку блоков в два этапа: через 2 недели 545 блоков и еще через две недели 505 блоков. Заказы для отдельных клиентов даны в таблице.

Но корпорации выгодней выполнить весь заказ в течение 3-4 дней, а затем переналадить оборудование на изготовление другого изделия из пакета заказов. В этом случае приходится часть изделий отправлять клиентам немедленно после набора необходимой прочности, а остальные складировать на собственных площадках. Стоимости перевозок на склады корпорации так же даны в таблице.

Разумеется, в этом случае в обусловленные заказом сроки 505 складированных блоков должны будут доставлены клиентам прямо со складов. Стоимости перевозок блоков со складов к клиентам даны в следующей таблице.

a. Составьте план перевозок заводы-клиенты, заводы-склады и склады- клиенты так, чтобы издержки корпорации были минимальны. Учтите, что изготовленные заранее 505 блоков, реально можно складировать следующим образом: Склад А -150 шт., Склад В -150 шт. и Склад С -205 шт.

b. Определите, как изменились бы издержки, если оптимизировать задачу по частям: сначала перевозки заводы-клиенты, затем заводы-склады и склады- клиенты.

Решение задачи.

В этой, довольно объемной задаче, при решении явно следует поменять местами вопросы а и Ь. Ведь каждая отдельная задача в вопросе Ь не должна вызвать у нас проблем - это все знакомые нам задачи. А уж после того, как мы решим задачу наиболее очевидным способом, можно будет перейти к тотальной оптимизации.

Давайте начнем с перевозок заводы-клиенты. Как следует из условия задачи заводы представят к перевозке 1050 блоков, из которых к клиентам можно будет перевезти 545 блоков, а остальные придется везти на склады. Для нас это означает, что первая из отдельных задач не сбалансирована. Для того, чтобы сбалансировать задачу придется добавить фиктивного клиента, который и «закажет» лишние 505 блоков. В этом случае задачу можно построить следующим образом (Рис. 80).

Целевая функция здесь - полные издержки перевозки. Выражения для задания ограничений в Поиске решения записываются как обычно (строка В16:116 и столбец Л1:Л5). Разумеется, перевозку блоков к фиктивному клиенту мы, как обычно, оставляем бесплатной. Соответствующие издержки будут учтены при решении задачи о перевозке на склады.

Поиск решения выдает следующий оптимальный план перевозок (Рис. 81).

Как мы видим, на склады отправится вся продукция завода ЖБИ 1 и часть продукции заводов ЖБИ 3 и ЖБИ 4. Стоимость этой фазы перевозок 15555 единиц.

Следующая часть перевозок - перевозки с заводов на склады. В предыдущей части мы выяснили, сколько блоков должно быть вывезено на склады с каждого из заводов. Емкость складов и цены перевозки нам известны из условия задачи. Составим соответствующую таблицу (Рис. 82).

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

Поиск решения дает следующий результат для этой части перевозок (Рис.

Общая стоимость перевозок составила 17790 единиц.

И последняя часть задачи - перевозки с трех складов к клиентам, которые происходят через две недели. Задача и здесь сбалансирована, второй заказ в сумме составляет 505 блоков, которые мы ранее запасли на трех складских площадках. Составляем новую таблицу (Рис. 84) и ищем решение последней, третьей задачи.

Полученной решение представлено в таблице Рис. 85. Как мы видим издержки по перевозкам составили 15210 единиц.

Суммируя все три результата мы можем сказать, что минимальные издержки при оптимизации перевозок по частям составят 48555 единиц.

Рис. 86

Теперь решим эту задачу сразу для всех трех частей перевозок. Для этого объединим все задачи на одном листе и свяжем их друг с другом (Рис. 86). Так как в целом задача сбалансирована, можно убрать фиктивного получателя из первой задачи.

При объединении задач, выражения для расчета баланса по доставке (строки В15:Н15, В30:Б30 и В43:Н43) останутся теми же самыми. В установках для Поиска решения мы потребуем, чтобы значения выражений в этих ячейках равнялись нулю. А вот формулы для подсчета вывезенных блоков мы подкорректируем. Теперь в них должны содержаться просто суммы для всех блоков, вывезенных с каждого пункта (столбцы 110:114, Е26:Е30 и 140:142). Баланс по перевозкам с заводов клиентам и на склады мы рассчитаем в столбце Н26:Н30 - все, что произведено на данном заводе, должно быть вывезено, либо клиентам,

либо на склады. В ограничениях укажем, что H26:H30=0. Для перевозок со складов к клиентам потребуем просто, чтобы I40:I42 равнялись I34:I36.

В ячейках I7, E23 и I37 мы по прежнему считаем стоимости перевозок в отдельных частях. Но в качестве целевой функции мы выберем сумму этих трех величин (ячейка G18).

Так как мы собираемся выбирать оптимальные перевозки среди всех маршрутов на всех участках, то переменными задачи будут все три прежние таблицы переменных: B10:H14, B26:D30 и B40:H42. Напомним, что для указания в качестве переменных разрозненных ячеек или диапазонов ячеек нужно при выделении удерживать нажатой клавишу Ctrl.

Итак, задача для Поиска решения поставлена. Проверьте, что у вас указаны все пять групповых ограничений и в Параметрах отмечено, что задача линейная, а переменные неотрицательны. Если все сделано верно, Поиск решения сможет найти оптимальное решение.

Чтобы не вставлять в книгу еще одну громоздкую таблицу, мы его целиком приводить не будем. Отметим только результаты минимизации в отношении стоимости перевозок. В отличие от оптимизации по частям стоимость перевозок составила 47025 единиц. Сокращение издержек произошло за счет лучшего плана перевозок с заводов.

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

2.П-6. Две бригады

Для выполнения срочного заказа мастер должен набрать из 14 рабочих (Р1, Р2...Р14) бригаду в 5 человек.

Среднее время, которое каждый из 14 рабочих тратит на ту или иную операцию (О1, О2,...О5), требующуюся для выполнения заказа, дано в таблице. Размер заказа равен 100 единицам, так что в реальности каждая операция будет выполнена 100 раз.

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

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

Что следует сделать, чтобы набрать две как можно более равные по силам бригады? Представьте списки новых бригад.

Решение задачи.

Так как каждый рабочий должен быть назначен только на одну операцию, то мы имеем дело с задачей о назначениях. В этой ситуации мы сразу можем определить, что задача не сбалансирована, так как операций 5, а рабочих 14. В условиях нехватки операций для назначения остальных рабочих мы можем сбалансировать задачу, введя фиктивные дополнительные операции. Чтобы сэкономить переменные задачи введем только одну фиктивную операцию и назовем ее «Другие работы». На эту операцию назначим 9 рабочих (14-5) оставшихся в стороне от заказа.

Для решения задачи построим обычную таблицу, которая для всех транспортных задач и задач о назначениях выглядит практически одинаково (Рис. 87).

Рис. 87

В задаче имеется 84 переменных (14*6), отвечающих всем возможным назначениям. Время выполнения фиктивной операции задаем равным нулю.

В ячейках Н2:Н15 рассчитываем время выполнения одной назначенной операции каждым рабочим и в ячейке Н16 суммируем все это рабочее время. Таким образом в ячейке Н16 содержится целевая функция задачи.

Для ответов на вопросы задачи нам нужно также подсчитать требующееся рабочее время с учетом того, что все операции нужно выполнить 100 раз. В ячейке А35 запишем формулу для полного рабочего времени в часах =Н16*100/60. А в ячейках 118:131 подсчитаем, сколько смен должен проработать каждый рабочий.

Разумеется, может оказаться, что количество смен получится различным. В этих условиях длительность выполнения заказа определится максимальным из этих времен. Для определения максимального времени используем функцию =МАКС(12:Л5).

Чтобы поставить задачу Поиску решения нужно еще сделать расчеты количеств назначений для рабочих и операций. Для контроля числа назначенных на каждую операцию рабочих введем в ячейку 032 формулу =СУММ(018:031)- 033, которую затем протянем влево. «Заказанное» количество рабочих указано в строке В33:033. Для контроля числа назначений для каждого из рабочих, введем в ячейку Н18 формулу =СУММ(В18:018), которую следует затем протянуть вниз. Теперь можно ставить задачу Поиску решения.

Итак, целевая ячейка Н16, цель - поиск минимума затрат рабочего времени. Переменные задачи В18:031. Во вкладке Параметры отмечаем, что задача линейная, а переменные неотрицательны. И в списке ограничений вводим условия: В32:032=0 и Н18:Н31=1, обычные для задач о назначениях.

В результате оптимизации получаем следующий план назначений (Рис. 88)

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

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

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

Для набора двух бригад вместо одной можно действовать двумя способами.

Первый способ соответствует логике задачи - раз одна бригада набрана, давайте вычеркнем этих рабочих из списка. Т. е. нам нужно скопировать лист и удалить строки, соответствующие рабочим Р3, Р4, Р7, Р9 и Р13 из обеих частей таблицы, верхней и нижней. Только не забудьте проверить, что все формулы остались правильными. Кроме этого нужно изменить количество лишних рабочих в ячейке 033 с 9 до 4. После новой оптимизации получим второй план назначений (Рис. 89).

В таблице снова оставлены только назначенные во вторую бригаду рабочие.

Как вы можете видеть, теперь максимальная длительность работ составила бы чуть больше 11 дней, а трудозатраты увеличились до 417 часов. Левые колонки в таблицах 2.7 и 2.8 содержат списки двух составленных бригад.

Если заказ действительно будет удвоен, то реальный срок выполнения составит 12 дней, вместо 10, а трудозатраты возрастут до 783.4 часа.

Второй способ решения можно получить, если воспользоваться простыми соображениями. Что в реальности получится после набора второй бригады? Очевидно, на каждую операцию будет назначено по два человека, а не по одному. А так как первая бригада - лучшая, то рабочие первой бригады обязательно будут при этом выбраны. Поэтому, если в строке заказов В33:О33 вместо единиц проставить двойки, а вместо 9 оставить 4, то мы отберем лучших 10 человек, среди которых будут 5 рабочих первой бригады, а остальные 5 составят вторую бригаду.

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

Вопрос о равных бригадах оказывается более сложным. Фактически он соответствует решению дополнительной задачи линейного программирования. Мы предлагаем воспользоваться уже полученными списками бригад и оставляем на долю читателя попытку решить задачу о равных бригадах с нуля и в одной задаче.

Так как мы отобрали лучших рабочих, очевидно, было бы разумно составлять две равные бригады именно из них. Конечно, может быть из всех рабочих можно выбрать две совершенно равные бригады. Но при этом, время исполнения заказа и использованное рабочее время в целом могут сильно увеличиться, что нежелательно по смыслу задачи.

Поэтому наша задача состоит в разбиении 10 выбранных рабочих на две бригады. В таблице 2.9 показан пример организации данных для решения задачи.

В области Л1:Б7 приведены списки бригад, выбранные нами ранее. Указаны времена выполнения операций с 1-ой по 5-ю соответствующими рабочими первой и второй бригады. Введем переменные С9:С13, которые показывают, кто из рабочих старой первой бригады войдет в первую новую бригаду. Так как для каждой операции выбор рабочих делается из двух человек, то если рабочий старой первой бригады выбран в новую первую бригаду, значит рабочий старой второй бригады в нее выбран не будет. Например, если выбрать рабочего Р3, то не будет выбран рабочий Р1 и наоборот. Поэтому формулы в столбце Е9:Е13 вычисляют, кто из рабочих старой второй бригады будет выбран в новую первую бригаду. Для этого переменные С9:С13 должны быть двоичными, разумеется.

Если список новой первой бригады в столбцах С9:С13 и Е9:Е13 составлен, то можно вычислить время выполнения каждой из операций рабочими новой первой бригады. Это сделано в столбце Е2Е6. Формула суммы в ячейке Б1 в этом случае подсчитает время однократного исполнения всех операций первой бригадой. Аналогичные расчеты для второй бригады проведены в столбце 01:06.

Теперь вся проблема в определении целевой функции.

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

Так как мы хотим добиться наименьшей разницы во времени выполнения заказа двумя бригадами, подсчитаем в ячейке Б7 эту самую разницу: =Б1-01. Можно ли выбрать полученное выражение в качестве целевой функции? Давайте попробуем. Надо только решить, какую выбрать цель.

Можем ли мы потребовать, чтобы Б7 была минимально возможной? Очевидно, нет. Ведь если значение ячейки Б1 будет меньше, чем значение ячейки 01, то целевая функция станет отрицательной. А наименьшее значение целевой функции будет достигнуто при наибольшей разнице во временах выполнения. Причем, такое решение у нас уже есть, если хорошенько подумать.

Можно попросить, чтобы значение целевой ячейки равнялось заданному числу (третий выбор цели оптимизации). Что тут плохо, так это то, что мы не знаем, какое число выбрать. Если выбрать 0, то есть ли вообще такое решение? Попробуем.

Итак: цель - равенство 0, переменные С9:С13, ограничение - переменные = двоичные, параметры - линейная задача. Запускаем поиск, получаем ответ, что поиск не может найти подходящего решения. Значит придется пробовать несколько разных значений до тех пор, пока мы не набредем на нужное значение.

Пробовать в качестве цели нечетные числа, и в частности единицу, очевидно не стоит, так как сумма двух времен четное число (220+250=470), а разница между временами бригад в этом случае может быть только четной.

Новая цель - целевая функция равна 2. Запускаем поиск - оп, решение найдено! Времена выполнения 236 и 234 минуты для первой и второй бригады соответственно. Не так уж много и работы понадобилось. Что еще хорошо в этом подходе, что можно подбирать любую разницу по заданному значению, а не только минимальную. Иногда это оказывается очень полезным. Например, в случае, если вы хотите получить несколько решений, близких к оптимальному решению.

Но, все таки, что там насчет первого способа? Чтобы сразу искать нужное решение?

На самом деле и это не сложно. У нас ведь была одна проблема, что целевая функция могла быть отрицательной. Так давайте потребуем, чтобы поиск минимума велся только среди неотрицательных значений целевой функции! Добавляем ограничение - Б7gt;=0, и спокойно ищем минимум целевой функции. Приведем и полученное решение, то же самое, что и при поиске заданной

В одну бригаду войдут рабочие Р1, Р4, Р9, Р11, Р13, а в другую - Р3, Р5, Р7, Р9, Р14. Следует заметить, что наши попытки выровнять бригады привели к тому, что время выполнения заказа увеличилось до 11 суток.

2.П-7. Отделочный камень для коттеджей (Кейс)

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

Николай тесно контактировал с группой химиков-синтетиков, которые, руководствуясь результатами его структурных исследований, по его просьбе синтезировали все новые и новые ряды полимерных материалов этого типа. Однажды в результате такого синтеза появились «уроды», твердые как камни, которые не демонстрировали никаких высокоэластических или жидкокристаллических свойств, сколько их не нагревай и не растягивай. Сначала Николай хотел их просто выбросить, но для порядка решил все же зарегистрировать их структурные и прочностные характеристики. Обточив образец для того, чтобы поставить его в рентгеновский аппарат, наш химик поразился красотой рисунка полимерного камня. Он напоминал хорошо обработанный природный гранит...

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

- Может у них хоть прочность высокая? - спросил один из сотрудников.

Прочность у материалов была повыше, чем у природного гранита, но до

высокоориентированных полимерных рекордсменов было очень далеко.

- Так зачем они тогда нужны?

- Ну, может как отделочный материал, их легко синтезировать разных цветов и с разными рисунками. - смущенно ответил Кузьмин, и забросил своих «уродов» в дальний угол лабораторного шкафа.

А на дворе был 1991 год. Еще через год научным сотрудникам стало недосуг удовлетворять собственное любопытство за государственный счет. Зарплаты не хватало, чтобы купить пару обуви детям. Нужно было думать, как кормить семью. И Николай вспомнил про тупиковую ветвь своих исследований. Он показал образцы искусственных камней своему школьному приятелю, инженеру-строителю, который в это время начал строить особняки для новых русских. Тот сказал, что если можно синтезировать их в больших объемах, то они вполне могут рассматриваться как недорогой, прочный и красивый отделочный материал.

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

Дальше - больше. Камни продавались хорошо, и через три года у Кузьмина было 5 оптовых магазинов - складов («отделений компании», как он говорил) в Подмосковье:

в Черноголовке, где впервые реализовалась идея; недалеко от Голицыно для обслуживания лидеров дачного строительства по западному направлению (Минское, Киевское, Рублевского и Ново-рижского шоссе);

под Подольском для обслуживания Калужского направления; в Лобне для обслуживания перспективного «президентского» направления, в Бронницах, чтобы не осталось «неохваченным» ни одно из дачных направлений Подмосковья.

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

Большая часть продукции изготавливалась в Черноголовке, там же где находился первый (сейчас уже совсем не самый доходный магазин). Цех мог производить 270 тонн искусственных камней, но такая производственная мощность очень скоро стала совершенно недостаточна. Все 5 отделений компании жаловались на нехватку товара при все возрастающем спросе клиентов.

Поскольку Подольск находился дальше от Черноголовки, чем другие отделения компании (и продавал существенно меньше, чем Голицынское отделение), Николай всегда отправлял продукцию в Подольск в последнюю очередь, по остаточному принципу. Это приводило в ярость менеджера Подольского отделения, Евгения Антипова, и после горячих дискуссий было решено открыть новое производство в Обнинске. Организовать цех поближе к Москве тогда уже было очень трудно и дорого. Цех в Обнинске мог производить 150 тонн продукции ежемесячно.

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

Каждый цех должен иметь такую же производственную мощность, что и цех в Обнинске. Под цех с мощностью, превышающей 150 тонн искусственного камня в месяц, по новым требованиям подмосковных властей нужна намного большая территория (а земля в Подмосковье сейчас безумно дорогая), он должен быть расположен далеко от жилых объектов, а значит, не будет никаких подъездных путей. Николай провел интенсивный поиск и отобрал 3 приемлемых места для постройки двух цехов: на окраине Воскресенска, недалеко от Дмитрова и в маленьком местечке Первомайское на полпути в Волоколамск. При окончательном выборе двух мест для постройки из этих трех кандидатов нужно принять во внимание транспортные издержки и потребности в товаре

существующих отделений компании.

Черноголовским отделением занимается сам Николай Кузьмин.

Потребность отделения составляет 70 тонн в месяц, которые полностью

удовлетворяются цехом в Черноголовке - ведь возить продукцию никуда не надо. Грех было бы не удовлетворять потребности клиентов.

Голицынское отделение (его возглавляет Рустем Сабиров) было вторым отделением, основанным Николаем и до сих пор оно остается самым доходным. По оценкам Рустема спрос составляет 250 тонн в месяц. Цех в Черноголовке традиционно поставляет 150 тонн продукции каждый месяц. Транспортные

издержки в расчете на одну тонну, перевезенную из Черноголовки в Голицыно, составляют 1400 руб. Хотя издержки по перевозке одной тонны груза из Обнинска в Голицыно были бы всего 800 руб., Рустем понимал, что ему не дождаться товара из Обнинска, поскольку на него «наложил лапу» напористый Евгений Антипов из Подольского отделения (ведь для него собственно этот второй цех и был построен). Поэтому он всегда просил Николая доставить еще хотя бы 50 тонн из Черноголовки (правда, безрезультатно).

Два дополнительных цеха, конечно, смогут удовлетворить потребность Рустема в дополнительных 100 тоннах продукции, которые ему необходимы. Разумеется, транспортные расходы будут существенно варьировать в зависимости от того, какие места будут для них выбраны. Это будет 500 руб. на тонну при транспортировке из Первомайского, 1220 руб. - из Дмитрова и 1550 руб.- из Воскресенска.

Елена Матухина, менеджер отделения в Лобне, была особенно расстроена из-за недостаточного размера поставок для ее магазина. У нее спрос составлял 160 тонн в месяц, а получала она только 70 тонн: 50 тонн из цеха в Черноголовке и 20 тонн из Обнинска. Она никак не могла понять, почему Николай не поставлял ей все 160 тонн из Черноголовки. Ведь транспортные издержки в расчете на 1 тонну оттуда составляли всего 900 руб., в то время как привести 1 тонну из Обнинска стоит 1300 руб., и еще за это на нее непрерывно «наезжает» Антипов. Елена надеялась, что Николай выберет Дмитров для одного из новых цехов. Тогда она смогла быть получить все недостающие ей 90 тонн с транспортной издержкой всего 500 руб. за 1 тонну. Если не Дмитров, то подошло бы и Первомайское, хотя транспортные издержки в этом случае возросли бы до 600 руб. за тонну. Поскольку транспортные издержки из Воскресенска в Лобню составили бы 1400 руб. за тонну, Елена подсчитала, что это делает для нее невозможным поставки оттуда.

Отделение в Подольске, возглавляемое Евгением Антиповым, получает 100 тонн искусственного камня в месяц из Обнинска. Спрос составлял 180 тонн. Евгению удалось отстоять поставки из нового цеха в Обнинске (который и был построен в результате его постоянного давления). Транспортные издержки из Обнинска в Подольск составляли 900 руб., в то время как транспортировка камня из Черноголовки в Подольск обходилась бы в 1100 руб. за тонну. Однако добиться, чтобы вся продукция из Обнинска шла только ему, Евгению не удалось. Вмешалась Матухина, тихой сапой, оттяпавшая себе 20 тонн в месяц, и 30 тонн пришлось согласиться отдать новому отделению в Бронницах. Евгений надеялся, что Дмитров не будет выбран в качестве места дислокации новых производственных цехов, поскольку при поставке товара из Дмитрова в Подольск транспортные издержки составили бы 1550 руб. за тонну. Поставки из Первомайского и Воскресенска составили бы соответственно 700 руб. и 1050 руб. за тонну, что его вполне устраивало.

Отделение в Бронницах получало только половину от своей ежемесячной потребности. 30 тонн искусственного камня приходили в Бронницы из Обнинска. Транспортные издержки при этом составляли 1300 руб. за тонну. Из Черноголовки транспортные издержки составили бы 900 руб., но Владимир Копцев, менеджер отделения в Бронницах понимал, что при этом Кузьмину пришлось бы уменьшить поставки Голицынскому отделению, на что он никогда бы не пошел. Поэтому Копцев возлагал большие надежды на запуск новых цехов. Особенно заинтересован он был в запуске цеха в Воскресенске, поскольку при этом транспортные издержки для него составили бы всего 300 руб. за тонну. Он мог бы получить весь требующийся ему товар (60 тонн) из Воскресенска. Правда, даже, если Воскресенск и не будет выбран, Первомайское то же терпимо, хотя и гораздо хуже. Транспортные издержки при поставках из Первомайского в Бронницы составят 950 руб. за тонну. А вот Дмитров для него совсем неприемлем

- 1750 руб. за тонну.

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

- минимизировать транспортные издержки. Совещание произошло в Черноголовке. Присутствовали все, кроме Елены Матухиной.

Протокол совещания

Кузьмин:

Благодарю всех за то, что собрались. Как вы знаете, я решил открыть два новых производственных цеха в Первомайском, Дмитрове или в Воскресенске. Два цеха, конечно, изменят существующую практику поставок, и я искренне надеюсь, что они позволят поставлять столько искусственного камня, сколько вам требуется. Я знаю, что вы могли бы продавать больше нашей продукции, и я прошу прощенья за то, что такая ситуация продолжалась так долго.

Копцев:

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

Сабиров:

Володя, я уверен, что Сергей сможет справиться с этой работой, и я знаю, как трудно сейчас найти приличную работу инженеру-технологу (ведь он у тебя работает на Воскресенском химическом комбинате, не правда ли?). Тем не менее, нам следует рассматривать полные издержки, связанные с транспортировкой продукции во все наши отделения, а не персоналии. Я думаю, что новые цеха должны быть открыты в Первомайском и Дмитрове. Мое отделение находится гораздо дальше от производственных цехов (действующих и потенциального в Воскресенске), чем все остальные отделения нашей компании, и выбор Первомайского и Дмитрова мог бы существенного уменьшить мои транспортные издержки.

Копцев:

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

Сабиров:

Выигрыш в 100 руб. на тонну никак не компенсирует возрастание моих транспортных издержек. У меня и так они самые большие - 1400 руб. за тонну, а если выбрать Воскресенск они составят 1550 руб.! И в таких условиях должно работать отделение, обеспечивающее максимальный объем продаж!

Антипов:

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

Кузьмин:

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

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

Анализ кейса.

С технической точки зрения анализ кейса не вызывает никаких трудностей. Необходимо выбрать два из трех потенциальных мест для строительства цехов, на основе минимизации издержек транспортных перевозок камней от четырех цехов, где производятся искусственные камни (два имеющихся цеха - в Черноголовке и Обнинске, и два новых) к четырем магазинам складам (в Подольске, Голицыно, Лобне и Бронницах). Магазин в Черноголовке можно из количественной модели исключить, т.к. очевидно, что он должен снабжаться цехом, расположенным в Черноголовке, поскольку транспортные издержки при этом нулевые.

Это можно сделать, либо решив последовательно 3 транспортные задачи (для трех возможных сочетаний двух новых цехов: Первомайское - Воскресенск, Дмитров - Первомайское и Дмитров - Воскресенск), либо совместив задачу выбора двух поставщиков из трех возможных с минимизаций издержек транспортных перевозок от них. Мы реализуем второй путь.

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

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

Потребность магазина в Черноголовке составляет 70 тонн в год и удовлетворяется цехом в Черноголовке, который производит 270 тонн искусственных камней в год. Таким образом, на четыре оставшихся магазина приходится 200 тонн камней из Черноголовки, что и отражено в таблице (в колонке Запас). Цены перевозок 1 тонны камней из Воскресенска в каждый из четырех магазинов уменьшены на 100 руб., по сравнению с данными, обсуждавшимися в тексте. Тем самым учтено, что себестоимость сырья, в случае строительства цеха в Воскресенске, будет на 100 руб. меньше на каждую тонну произведенных камней.

В следующей таблице (Рис. 93) представлена ситуация на сегодняшний

Оставим в стороне вопрос о том, почему разные отделения компании имеют различные отношения величины дефицита к реальной потребности. В принципе, мы могли бы перераспределить имеющийся дефицит в 300 тонн в год (сумма заказов от всех отделений - 720 тонн, а производственные мощности двух имеющихся цехов - 420 тонн) исходя из минимума транспортных издержек. Однако, по-видимому, транспортные издержки не являются основным фактором в распределении ограниченных ресурсов компании по ее отделениям. Здесь важную роль могут иметь упущенные возможности от неудовлетворенного спроса, цены и ассортимент продукции каждого отделения. Нет уверенности, что при решении вопроса о величине поставок все эти факторы принимались во внимание Кузьминым (скорее, наоборот, решающим фактором было давление менеджеров - руководителей отделений). Однако, поскольку объективная информация на этот счет в кейсе отсутствует, примем величины поставок в каждое отделение как данность и проверим, правильно ли определены поставщики для каждого отделения с точки зрения минимизации полных издержек транспортных перевозок. Просто решим сбалансированную транспортную задачу с двумя поставщиками и четырьмя заказчиками.

Видно, что сложившаяся практика поставок обусловливает транспортные издержки почти на 30% выше, чем оптимальные. Анализ средневзвешенных транспортных издержек каждого магазина показывает, что при переходе от сложившейся практики поставок к оптимальной, выиграли бы все менеджеры- руководители отделений, кроме «напористого» Евгения Антипова. Понятно, что именно давление этого менеджера и, возможно, стремление Кузьмина продавать как можно больше (и в первую очередь) на западном направлении сформировало нынешнюю неэффективную систему поставок.

Перейдем теперь к решению задачи об оптимальном выборе местоположения для новых цехов. На Рис. 95 представлена организация данных на листе MS Excel для использования Поиска решения.

Переменными решения являются 20 объемов перевозок от каждого поставщика (два старых цеха и 3 потенциальных новых) в каждое отделение компании - ячейки С12:Б16, а также пять двоичных переменных (0/1) в ячейках Б12:Б16, отвечающие на вопрос «Выбирать или не выбирать» потенциальное местоположение для строительства нового цеха. Целевая функция - суммарные издержки транспортных перевозок введена в ячейке 13.

Ограничения в ячейках С17:Б17 - обычное для транспортной задачи требование удовлетворения заказа данного потребителя - отделения компании. Аналогично, в ячейках Н12:Н16 введено ограничение, обусловленное производственными мощностями цехов в Черноголовке и Обнинске. Обратите внимание, что величина производственной мощности множится на двоичную переменную «Выбирать или не выбирать» данное место для строительства цеха. Очевидно, если эта переменная равна 0 («не выбирать»), то запас,

соответствующий этому гипотетическому цеху равен 0. При задании ограничений в Поиске решения необходимо, очевидно, потребовать, чтобы ячейки С18:Б18 и Н12:Н16 равнялись нулю. Кроме этого, можно потребовать, чтобы двоичные переменные Б12:Б13 оставались равными единице. Это означает, что старые места цехов уже выбраны.

Решение показано на Рис. 96.

Здесь мы позволим себе небольшое отступление.

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

Видно, что модель рекомендует выбрать Дмитров и Первомайское в качестве мест для строительства новых цехов. При этом суммарные транспортные издержки составят 481000 руб. в год. В случае выбора пар Дмитров -Воскресенск или Первомайское -Воскресенск издержки соответственно 555500 руб. и 500500 руб. (проверьте это непосредственным решением транспортной задачи для данных вариантов).__________________________________________________

Интересно оценить, как изменились средневзвешенные транспортные издержки за 1 тонну для каждого из отделений компании. Видно, что опять выиграли все, кроме Антипова. При этом вариации транспортных издержек для различных отделений компании очень велики: максимальные и минимальные значения отличаются почти в два раза. Это, очевидно, несправедливо, и, несомненно, вызовет трения в компании. Для их преодоления можно рекомендовать создать общий фонд для оплаты транспортных издержек, как фиксированный процент с выручки от продаж каждого отделения, или как-то иначе изменить систему выплат и компенсаций менеджеров-руководителей. В любом случае необходимо прекратить «перетягивание одеяла» между руководителями различных отделений компании - это неизбежно оборачивается убытками для компании в целом.

2.П-8. Цепочка поставок компании «НАЦПРОДУКТ» (Кейс)

Действие 1-е: Постановка задач оптимизации.

Металлургическая компания НАЦПРОДУКТ является одним из крупнейших производителей ценного продукта X в стране У. Компания владеет 5 заводами с различными производственными мощностями, построенными в разное время и поэтому имеющими различные ограничения на качество исходного сырья, а также различные значения себестоимости продукта, в зависимости от качества сырья.

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

Рынок испытывает высокую потребность в ценном продукте Х, но страна У небогата сырьем для производства этого продукта. Сырье - руда с различным процентным содержанием искомого компонента (ИК), добывается в весьма удаленных районах мира.

В результате, доля транспортных издержек компании НАЦПРОДУКТ составляет свыше 30% в себестоимости продукта Х.

Цепочка поставок компании НАЦПРОДУКТ построена просто и логично.

В зависимости от спроса на различные вариации продукта Х на внутреннем и внешнем рынке и в зависимости от контрактов, заключенных отделом сбыта компании, определяется производственный план и потребность в сырье для каждого завода. Технологические особенности каждого завода определяют минимальное содержание ИК в руде для каждого завода. Если среднее содержание ИК в руде ниже этого минимального, сырье непригодно для производства продукта на этом заводе. Минимальное содержание ИК и потребность в сырье на планируемый период для каждого завода приведены в таблице (Рис. 97).

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

к - к

C = (1-H • ^) C тах

к #9632;

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

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

Закупки сырья являются ключевой, жизненно важной функцией для компании НАЦПРОДУКТ. Это - внешнеэкономическая деятельность, ей присуще множество тонкостей и подводных камней, связанных с международным торговым правом, таможенным регулированием и налоговым законодательством. Поэтому в отделе закупок работают очень опытные люди с юридическим и экономическим образованием. Руководитель отдела, Боб Безукоризненный, двадцать лет назад окончил Престижный Университет по специальности «Внешнеэкономическая деятельность» и имеет большой практический опыт работы в этой сфере. При составлении плана закупок, он придает особое значение выбору надежных поставщиков. Ведь срыв сроков поставок или отклонения от необходимого качества сырья грозят остановкой производства и многомиллионными убытками.

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

Практически компания НАЦПРОДУКТ может закупать сырье у десяти различных поставщиков в разных странах мира. Индексы ненадежности каждого поставщика, максимальные и минимальные объемы поставок, которые поставщик готов предоставить компании НАЦПРОДУКТ на планируемый период, цены сырья и среднее значение концентрации ИК для каждого поставщика представлены на Рис. 99.

Боб Безукоризненный считает, что индекс ненадежности поставок не должен превышать 4 для обеспечения бесперебойной работы компании. Это не значит, что поставщиков с индексом ненадежности выше 4 совсем нельзя включать в план. Но уж если их необходимо использовать, то весовая доля их поставок должна быть не слишком велика. Зато большая весовая доля надежных поставщиков улучшает качество закупки и компенсирует наличие небольшой доли ненадежных поставщиков.

Разумеется, следует стремиться закупить сырье по возможно низким ценам, удовлетворив при этом требованиям надежности поставок, ограничениям, выдвигаемым поставщиками по объему поставок, и требуемой заводами минимальной концентрации ИК.

После того, как поставщики выбраны, и объемы поставок каждого из них определены, наступает очередь отдела логистики. Эта работа в компании традиционно рассматривается как сугубо техническая. Руководители смежных отделов не любят, когда директор по логистике Феофан Перевозчиков выступает с какими-либо замечаниями по работе отдела закупок или, тем более, производственного отдела. Как любит говорить Боб Безукоризненный: «Ваше дело привести сырье, которое мы обеспечили нашими договорами с поставщиками, остальное вас не касается».

Опыт показывает, что транспортные издержки составляют около 30% суммарной себестоимости продукции компании. В компании утвердилось мнение, что транспортные издержки столь высоки из-за неэффективной работы отдела логистики. В конце концов, о задаче оптимизации транспортных издержек все слышали еще в институте. Это - азы количественных методов управления. Однако никто не слышал, чтобы отдел Феофана Перевозчикова использовал количественные методы оптимизации в своей практической работе. Феофан действительно считал это излишним. Ему казалось, что и без всяких замысловатых оптимизационных методов ясно, от какого поставщика вести сырье каждому заводу. Реальная работа состояла в том, чтобы вовремя и правильно зафрахтовать суда и железнодорожные составы для перевозки и проконтролировать движение грузов. Это отдел логистики делал неплохо. Поэтому критику коллег он считал несправедливой. Однако под давлением этой критики он, в конце концов, взял в штат молодого выпускника факультета вычислительной математики и кибернетики Лучшего Университета страны У, Макса Сиплексова (сына своего старого приятеля).

Макс хорошо учился в университете, но после окончания не захотел идти в аспирантуру, предпочитая попробовать себя на практической работе, поэтому предложение от Компании НАЦПРОДУКТ принял с энтузиазмом.

Феофан поручил Максу, для начала, две задачи. Первая задача (ради которой, собственно, по настоянию «общественности», и был взят молодой специалист-«оптимизатор») - это минимизация издержек транспортных перевозок от поставщиков, выбранных отделом закупок, к заводам компании. В глубине души, Феофан был уверен, что ничего нового эта задача для отдела логистики не даст. После того как отдел Боба определил поставщиков, вариантов перевозок было не так уж много, они сильно различались по цене и неоднократно были тщательно проанализированы его сотрудниками. Что тут делать компьютерным методам? Тем не менее, он предоставил Максу таблицу цен перевозок от каждого из 10 возможных поставщиков к каждому из заводов (Рис. 100).

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

Перед тем как идти к Бобу, Феофан зашел к Зам. генерального директора компании по управлению операциями Алексу Заверховному и убедил его, что было бы нерационально использовать нового перспективного сотрудника - Макса Симплексова, только для узких целей отдела логистики. Почему бы не поручить ему оптимизацию и на других участках работы компании? Заверховный предложение одобрил. Действительно, хорошее начинание надо внедрять повсеместно, особенно если это не требует дополнительных затрат.

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

Итак, молодой сотрудник Макс Симплексов получил две задачи для решения.

— Первая задача состоит в том, чтобы полностью обеспечить заводы сырьем требуемого качества и добиться минимальной стоимости закупок сырья при обеспечении высокой надежности поставок.

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

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

Приложение

Эмпирическая зависимость себестоимости переработки продукции от процентного содержания извлекаемого компонента в руде для заводов компании НАЦПРОДУКТ

к - к

C = (1-H • —) C тах

к тш

где С - себестоимость продукции, С max - максимальная себестоимость (при минимально допустимой концентрации ИК), H - коэффициент, выражающий скорость снижения себестоимости при росте содержания ИК в руде.

Значения к , С max и H для каждого завода приведены на Рис. 97 и Рис. 98.