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

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

Транспортные издержки Участок А Участок В Участок С Участок Б Участок Е АБЗ 16 1200 1250 850 900 1350 АБЗ 17 1250 950 1250 850 700 АБЗ 18 1400 1000 1200 1050 850 АБЗ 19 1350 850 800 750 1200 АБЗ 20 1300 650 1300 1050 1300 АБЗ 21 1500 850 1000 1250 700

Заказы дорожно-строительных бригад на завтра: Участок А Участок В Участок С Участок Б Участок Е Количество машин 79 28 61 77 72

Заводы в состоянии предоставить завтра, Источник АБЗ 16 АБЗ 17 АБЗ 18 АБЗ 19 АБЗ 20 АБЗ 21 Кол-во машин 65 46 52 29 28 67 чего, очевидно, недостаточно.

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

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

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

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

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

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

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

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

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

Для того, чтобы сбалансировать задачу нужно добавить недостающего поставщика асфальта мощностью в 30 машин в день. Учтем это при построении таблицы (Рис. 65). A B C D E F G 1 Участок A Участок B Участок С Участок D Участок E Планируется

отгрузить 2 АБЗ 16 1200 1250 850 900 1350 65 3 АБЗ 17 1250 950 1250 850 700 46 4 АБЗ 18 1400 1000 1200 1050 850 52 5 АБЗ 19 1350 850 800 750 1200 29 6 АБЗ 20 1300 650 1300 1050 1300 28 7 АБЗ 21 1500 850 1000 1250 700 67 8 АБЗ Х 0 0 0 0 0 30 9 Требуемо е кол-во 79 28 61 77 72 =СУММПРОИЗВ(В2:

F8;B12:F18) 10 11 Участо к A Участо к В Участо к С Участо к D Участо к Е Контроль отгрузки 12 АБЗ 16 =СУММ(В12^12)-

G2 13 АБЗ 17 =СУММ(В13^13)-

G3 14 АБЗ 18 =СУММ(В14^14)-

G4 15 АБЗ 19 =СУММ(В15^15)-

G5 16 АБЗ 20 =СУММ(В16^16)-

G6 17 АБЗ 21 =СУММ(В17^17)-

G7 18 АБЗ Х =СУММ(В18^18)-

G8 19 Контроль выполнен ия заказов =СУМ

М(В12:

В18)-

В9 =СУМ

М(С12:

С18)-

С9 =СУМ

Мф12:

D18)-

D9 =СУМ

М(Е12:

Е18)-Е9 =СУМ

М^12:

F18)-F9 В данном случае фиктивный поставщик асфальта носит гордое имя АБЗ X. Как обычно, мы считаем все перевозки от фиктивного поставщика бесплатными.

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

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

Вызываем надстройку Поиск решения и ставим задачу.

отгрузить АБЗ 16 1200 1250 850 900 1350 65 АБЗ 17 1250 950 1250 850 700 46 АБЗ 18 1400 1000 1200 1050 850 52 АБЗ 19 1350 850 800 750 1200 29 АБЗ 20 1300 650 1300 1050 1300 28 АБЗ 21 1500 850 1000 1250 700 67 АБЗ Х 30 Требуемое

кол-во 79 28 61 77 72 251 950 Участо к А Участо к В Участо к С Участо к Б Участо к Е Контроль отгрузки АБЗ 16 4 0 61 0 0 -2.2Е-09 АБЗ 17 0 0 0 46 0 -1.5Е-09 АБЗ 18 45 0 0 2 5 -1.7Е-09 АБЗ 19 0 0 0 29 0 6.8Е-11 АБЗ 20 0 28 0 0 0 -2.0Е-09 АБЗ 21 0 2.1Е-09 0 0 67 -2.2Е-09 АБЗ Х 30 0 0 0 0 7.0Е-11 Контроль выполнен ия заказов -2.6Е-

09 6.53Е-

11 -2Е-09 -2.6Е-

09 -2.4Е-

09 Рис. 66

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

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

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

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

кол-во 79 28 61 77 72 262 450 Участок A Участок B Участок C Участок D Участок E Контроль отгрузки АБЗ 16 34 0 31 0 0 -2.2E-09 АБЗ 17 0 0 0 46 0 -1.5E-09 АБЗ 18 45 0 0 2 5 -1.7E-09 АБЗ 19 0 0 0 29 0 6.8E-11 АБЗ 20 0 28 0 0 0 -2.0E-09 АБЗ 21 0 2.1E-09 0 0 67 -2.2E-09 АБЗ Х 0 0 30 0 0 7.0E-11 Рис. 67

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

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

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

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

кол-во 79 28 61 77 72 271 450 Участок A Участок B Участок C Участок D Участок E Контроль отгрузки АБЗ 16 65 0 0 0 0 0.0E+00 АБЗ 17 0 0 0 18 28 0.0E+00 АБЗ 18 8 0 0 0 44 0.0E+00 АБЗ 19 0 0 0 29 0 0.0E+00 АБЗ 20 6 22 0 0 0 0.0E+00 АБЗ 21 0 6 61 0 0 0.0E+00 АБЗ Х 0 0 0 30 0 0.0E+00 Как вы видите (Рис. 68), нам удалось отыграть у жестокой судьбы 11 100 рублей на составлении нового плана перевозок. В этом плане не повезло участку Б.

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

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

Менеджер отдела логистики составляет план перевозок продукции фирмы с 3 ее складских комплексов База 1, ...

Стоимость перевозок для каждого вида продукции, исходя из расстояний и других обстоятельств, даны в таблице. Клиент X Клиент У Клиент Ъ Клиент W А В А В А В А В База 1 А 595 480 455 430 В 780 665 640 815 База 2 А 435 530 480 485 В 735 735 680 585 База 3 А 545 465 525 440 В 715 755 815 795 Клиенты заказывают следующие количества товаров А, В.

Клиент X Клиент У Клиент Ъ Клиент W А В А В А В А В Заказы, шт. 15 20 22 26 12 22 32 42 На базах же в настоящий момент имеются следующие запасы товара:

База 1 База 2 База 3 А В А В А В Запасы, шт. 21 21 33 42 17 57 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 единицу продукта В клиенту Х не существует. Однако для надстройки Поиск решения пустая ячейка означает нулевую цену и такие перевозки будут запланированы. Поэтому нам следует запретить все подобные перевозки.

Как и в обычных задачах запретить перевозку по маршруту можно, поставив высокую цену перевозки. Давайте добавим в таблицу цен произвольное число, много большее любой из имеющихся цен, в каждую из оставшихся пустыми ячеек. A B С | D Е I F С | H I I J к ъ | м N О 1 Клиент X Клиент У Клиент Ъ Клиент W *** Запасы 2 А В А В А В А В В 3 База

1 А 595 9999 480 9999 455 9999 430 9999 21 4 В 9999 780 9999 665 9999 640 9999 815 21 5 База

2 А 435 9999 530 9999 480 9999 485 9999 33 6 В 9999 735 9999 735 9999 680 9999 585 42 7 База

3 А 545 9999 465 9999 525 9999 440 9999 17 8 В 9999 715 9999 755 9999 815 9999 795 57 9 *** А 10 10 Заказы 15 20 22 26 12 22 32 42 10 =СУММПРОИЗВ 11 (С3:К9;С13:К19) 12 А В А В А В А В В Запасы 13 База

1 А =СУММ(С13:К13)-Ь3 14 В =СУММ(С14:К14)-Ь4 15 База

2 А =СУММ(С15:К15)-Ь5 16 В =СУММ(С16:К16)-Ь6 17 База

3 А =СУММ(С17:К17)-Ь7 18 В =СУММ(С18:К18)-Ь8 19 *** А =СУММ(С19:К19)-Ь9 20 =СУ =СУ =СУ =СУ =СУ =СУ =СУ =СУ =СУММ(К13:К19)-К10 Рис. 69

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

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

В полученном решении (Рис. 70) недостающие 10 единиц продукта А будут недопоставлены клиенту У, а излишек продукта В целиком останется на базе 3. А | В С D Е Е С н I J к ъ 10 Заказы 15 20 22 26 12 22 32 42 10 104 760 11 12 А В А В А В А В В Запасы 13 База

1 А 0 0 0 0 0 0 21 0 0 0 14 В 0 0 0 0 0 21 0 0 0 0 15 База

2 А 15 0 0 0 12 0 6 0 0 0 16 В 0 0 0 0 0 0 0 42 0 0 17 База

3 А 0 0 12 0 0 0 5 0 0 0 18 В 0 20 0 26 0 1 0 0 10 0 19 *** А 0 0 10 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 Рис. 70

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

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

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

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

После замены запускаем Поиск решения вновь и меняем цель поиска на максимум. А В С | Б Е | Е с | н і | а K L 1 Клиент X Клиент У Клиент Ъ Клиент W *** Запасы 2 А В А В А В А В В 3 База

1 А 595 -9999 480 -9999 455 -9999 430 -9999 21 4 В -9999 780 -9999 665 -9999 640 -9999 815 21 5 База

2 А 435 -9999 530 -9999 480 -9999 485 -9999 33 6 В -9999 735 -9999 735 -9999 680 -9999 585 42 7 База

3 А 545 -9999 465 -9999 525 -9999 440 -9999 17 8 В -9999 715 -9999 755 -9999 815 -9999 795 57 9 *** А 10 10 Заказы 15 20 22 26 12 22 32 42 10 122 930 11 12 А В А В А В А В В Запасы 13 База

1 А 15 0 6 0 0 0 0 0 0 0 14 В 0 14 0 0 0 0 0 7 0 0 15 База

2 А 0 0 16 0 0 0 17 0 0 0 16 В 0 6 0 26 0 0 0 0 10 0 17 База

3 А 0 0 0 0 12 0 5 0 0 0 18 В 0 0 0 0 0 22 0 35 0 0 19 *** А 0 0 0 0 0 0 10 0 0 0 20 0 0 0 0 0 0 0 0 0 Рис. 71

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

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

дружеских отношений

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

, и для каждой потенциальной пары приведен в таблице. Аня Маша Катя Лиза Ольга Софья Иван 3 4 9 18 9 6 Михаил 16 8 12 13 20 4 Павел 8 6 13 1 6 9 Николай 16 9 6 8 1 11 Алексей 8 12 17 5 3 5 Петр 2 9 1 10 5 17 a. Определите такое распределение по парам, которое обращает в минимум суммарный индекс совместимости. b.

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

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

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

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

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

Сначала скопируем таблицу данных и вставим ее чуть ниже по странице. Выделим в ней область данных и сотрем их - в освобожденных ячейках, в данном случае В11:016, будут располагаться переменные задачи (Рис. 72) A B C D E F G H I а | K L м 1 Аня Маша Катя Лиза Ольга Софья 2 Иван 3 4 9 18 9 6 1 =СУММПРОИЗВ(В2:02;В11:в11) 3 Михаил 16 8 12 13 20 4 1 =СУММПРОИЗВ(В3:в3;В12:в12) 4 Павел 8 6 13 1 6 9 1 =СУММПРОИЗВ(В4:в4;В13:в13) 5 Николай 16 9 6 8 1 11 1 =СУММПРОИЗВ(В5:05;В14:в14) 6 Алексей 8 12 17 5 3 5 1 =СУММПРОИЗВ (В6: в6;В15:в15) 7 Петр 2 9 1 10 5 17 1 =СУММПРОИЗВ (В7:в7;В16:в16) 8 1 1 1 1 1 1 =СУММПРОИЗВ(В2:в7;В 11:016) 9 10 Аня Маша Катя Лиза Ольга Софья 11 Иван 0 0 0 0 0 0 =СУММ(В11:011) 12 Михаил 0 0 0 0 0 0 =СУММ(В12:в12) 13 Павел 0 0 0 0 0 0 =СУММ(В13:в13) 14 Николай 0 1 0 0 0 0 =СУММ(В14:в14) 15 Алексей 0 0 0 0 0 0 =СУММ(В15:в15) 16 Петр 0 0 0 0 0 0 =СУММ(В16:в16) 17 =СУМ =СУМ =СУГ =СУМ =СУМ =СУММ(011:016) Рис. 72

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

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

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

Итак, запишем в ячейку I8 формулу: =СУММПР0ИЗВ(Б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. Таблица переменных дает распределение по парам: Иван-Аня, Михаил-Маша, Павел-Лиза, Николай-Ольга, A B C D E F G H I 1 Аня Маша Катя Лиза Ольга Софья 2 Иван 3 4 9 18 9 6 1 3 3 Михаил 16 8 12 13 20 4 1 8 4 Павел 8 6 13 1 6 9 1 1 5 Николай 16 9 6 8 1 11 1 1 6 Алексей 8 12 17 5 3 5 1 5 7 Петр 2 9 1 10 5 17 1 1 8 1 1 1 1 1 1 19 9 10 Аня Маша Катя Лиза Ольга Софья 11 Иван 1 0 0 0 0 0 1 12 Михаил 0 1 0 0 0 0 1 13 Павел 0 0 0 1 0 0 1 14 Николай 0 0 0 0 1 0 1 15 Алексей 0 0 0 0 0 1 1 16 Петр 0 0 1 0 0 0 1 17 1 1 1 1 1 1 Рис. 73

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

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

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

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

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

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

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

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

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

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

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

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

Первое, на что следует обратить внимание, это факт, что требуемое решение найдено. Теперь рассмотрим полученное решение внимательней (Рис. 74.). А в с Б Е Е о н і 1 Аня Маша Катя Лиза Ольга Софья 2 Иван 3 4 9 18 9 6 1 3.5 3 Михаил 16 8 12 13 20 4 1 6 4 Павел 8 6 13 1 6 9 1 1 5 Николай 16 9 6 8 1 11 1 1.5 6 Алексей 8 12 17 5 3 5 1 6 7 Петр 2 9 1 10 5 17 1 1.1 8 1 1 1 1 1 1 19.1 9 10 Аня Маша Катя Лиза Ольга Софья 11 Иван 0.5 0.5 0 0 0 0 1 12 Михаил 0 0.5 0 0 0 0.5 1 13 Павел 0 0 0 1 0 0 1 14 Николай 0 0 0.1 0 0.9 0 1 15 Алексей 0.4 0 0 0 0.1 0.5 1 16 Петр 0.1 0 0.9 0 0 0 1 17 1 1 1 1 1 1 Рис. 74.

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

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

В задачах линейной оптимизации для «борьбы» с нецелыми решениями мы использовали целые или двоичные ограничения на переменные. Поступим здесь так же, добавим условие, что все переменные - двоичные (0 или 1) и снова попробуем решить задачу (Рис. 75). А в с Б Е Е о н і 1 Аня Маша Катя Лиза Ольга Софья 2 Иван 3 4 9 18 9 6 1 4 3 Михаил 16 8 12 13 20 4 1 4 4 Павел 8 6 13 1 6 9 1 1 5 Николай 16 9 6 8 1 11 1 6 6 Алексей 8 12 17 5 3 5 1 3 7 Петр 2 9 1 10 5 17 1 2 8 1 1 1 1 1 1 20 9 10 Аня Маша Катя Лиза Ольга Софья 11 Иван 0 1 0 0 0 0 1 12 Михаил 0 0 0 0 0 1 1 13 Павел 0 0 0 1 0 0 1 14 Николай 0 0 1 0 0 0 1 15 Алексей 0 0 0 0 1 0 1 16 Петр 1 0 0 0 0 0 1 17 1 1 1 1 1 1 Рис. 75

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

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

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

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

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

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

Обратите внимание, что если после получения резюме Поиска решения о том, что решение не найдено, нажать кнопку ОК, на листе с задачей сохранится НЕ решение, а просто итог поиска. Состояние задачи, на котором надстройка пришла к заключению, что решения не существует. Например такой (Рис. 76). A B C D E F G H I 1 Аня Маша Катя Лиза Ольга Софья 2 Иван 3 4 9 18 9 6 1 3.75 3 Михаил 16 8 12 13 20 4 1 5 4 Павел 8 6 13 1 6 9 1 1 5 Николай 16 9 6 8 1 11 1 3.25 6 Алексей 8 12 17 5 3 5 1 5 7 Петр 2 9 1 10 5 17 1 1.45 8 1 1 1 1 1 1 19.45 9 10 Аня Маша Катя Лиза Ольга Софья 11 Иван 0.25 0.75 0 0 0 0 1 12 Михаил 0 0.25 0 0 0 0.75 1 13 Павел 0 2Е-15 0 1 0 0 1 14 Николай 0 0 0.45 0 0.55 0 1 15 Алексей 0.3 0 0 0 0.45 0.25 1 16 Петр 0.45 0 0.55 0 0 0 1 17 1 1 1 1 1 1 Рис. 76

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

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

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

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

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

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

сотруд

ников 1 2 3 4 5 6 7 8 9 10 Гаапвилл 8 21 15 13 9 17 18 7 26 9 35 Финанстаун 14 18 17 19 12 6 15 24 13 20 Исабург 9 15 18 16 16 15 11 13 21 19 25 Нью-Баланс 11 14 7 23 9 6 18 7 10 Заявки 4 9 2 12 7 6 9 3 18 5 a. Распределите аудиторов так, чтобы суммарные временные затраты на подготовку были бы минимальны. Пропуски в некоторых клетках таблицы означают, что аудиторы данной конторы не имеют опыт аудита в отрасли, к которой относится данный клиент, и не должны к нему посылаться. b.

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

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

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

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

В качестве примера организации данных на листе Excel можно предложить следующую таблицу (Рис. 77). A B C D E F G H I J K L M 1 Конторы Клиенты Не

исп Число

сотрудников 2 1 2 3 4 5 6 7 8 9 10 3 Гаапвилл 8 21 15 13 9 17 18 7 26 9 35 4 Финанста

Ун 14 18 17 19 12 6 99 15 24 13 20 5 Исабург 9 15 18 16 16 15 11 13 21 19 25 6 Нью-

Баланс 11 99 14 7 23 9 6 18 99 7 10 7 Заявки 4 9 2 12 7 6 9 3 18 5 15 =СУММПРОИЗ

В(

B3:L6;B11:L14) 8 9 Конторы Клиенты Не

исп Число

сотрудников 10 1 2 3 4 5 6 7 8 9 10 11 Гаапвилл =CyMM(B11:L1

1)-M3 12 Финанста

Ун -20 13 Исабург -25 14 Нью-

Баланс -10 15 Заявки =СУММ

B7 [(B1 :B14)- -6 -9 -3 -18 -5 -15 Рис. 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). Конторы Клиенты Не

исп. Число

сотрудников 1 2 3 4 5 6 7 8 9 10 Г аапвилл 8 21 15 13 9 17 18 7 26 9 35 Финанста

ун 14 18 17 19 12 6 99 15 24 13 20 Исабург 9 15 18 16 16 15 11 13 21 19 25 Нью-

Баланс 11 99 14 7 23 9 6 18 99 7 10 Заявки 4 9 2 12 7 6 9 3 18 5 15 950 Конторы Клиенты Не

исп. Число

сотрудников 1 2 3 4 5 6 7 8 9 10 Г аапвилл 4 0 2 11 7 0 0 3 0 5 3 0 Финанста

ун 0 2 0 0 0 6 0 0 0 0 12 0 Исабург 0 7 0 0 0 0 0 0 18 0 0 0 Нью-

Баланс 0 0 0 1 0 0 9 0 0 0 0 0 Заявки 0 0 0 0 0 0 0 0 0 0 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). Заявки 4 9 2 12 7 6 9 3 18 5 15 982 Конторы Клиенты Не

исп. Число

сотрудников 1 2 3 4 5 6 7 8 9 10 Г аапвилл 3 0 1 11 6 0 0 2 0 4 8 -1.1Е-08 Финанста

ун 0 3 1 0 1 5 0 1 1 1 7 7.6Е-10 Исабург 1 6 0 0 0 0 1 0 17 0 0 9.5Е-10 Нью-

Баланс 0 0 0 1 0 1 8 0 0 0 0 3.8Е-10 Рис. 79

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

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

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

Корпорация “Современные железобетонные изделия” имеет в окрестностях и черте города 5 небольших заводов ЖБИ (ЖБИ 1,ЖБИ 2, ... ЖБИ 5). Кроме этого, у корпорации есть 3 охраняемых площадки-склада (Склад А, Склад В, Склад С) для временного хранения изделий, хотя корпорация старается работать на заказ. В настоящий момент в отделе продаж имеется заказ от строительной фирмы на поставку новых ж\б блоков высокой прочности в количестве 1050 шт. Учитывая прочие заказы заводы могут за обусловленный срок поставить следующее количество блоков: ЖБИ 1 ЖБИ 2 ЖБИ 3 ЖБИ 4 ЖБИ 5 290 165 235 255 105 Корпорация имеет транспортный отдел, который помогает зарабатывать дополнительные деньги (стоимость перевозки для близко расположенных заказчиков включена в стоимость изделий), поэтому заказанные блоки должны быть доставлены на площадки семи клиентов строительной компании. Стоимости перевозок с заводов на склады и с заводов клиентам даны в таблицах. Перевозки заводы - клиентам: Ед. Клиент Клиент Клиент Клиент Клиент Клиент Клиент 1 2 3 4 5 6 7 ЖБИ 1 84 36 42 81 63 60 66 ЖБИ 2 63 48 33 24 33 21 33 ЖБИ 3 63 18 33 66 45 45 51 ЖБИ 4 39 33 57 63 42 51 45 ЖБИ 5 30 21 42 42 24 33 24 Строительная компания заказывает поставку блоков в два этапа: через 2 недели 545 блоков и еще через две недели 505 блоков. Заказы для отдельных клиентов даны в таблице. штук Клиент 1 Клиент 2 Клиент 3 Клиент 4 Клиент 5 Клиент 6 Клиент 7 1-ый

Заказ 90 65 45 75 95 100 75 2-ой

Заказ 55 45 70 75 40 35 185 Но корпорации выгодней выполнить весь заказ в течение 3-4 дней, а затем переналадить оборудование на изготовление другого изделия из пакета заказов. В этом случае приходится часть изделий отправлять клиентам немедленно после набора необходимой прочности, а остальные складировать на собственных площадках. Стоимости перевозок на склады корпорации так же даны в таблице. Перевозки заводы - склады ед Склад 1 Склад 2 Склад 3 ЖБИ 1 78 15 42 ЖБИ 2 33 60 60 ЖБИ 3 60 9 24 ЖБИ 4 51 45 15 ЖБИ 5 33 39 12 Разумеется, в этом случае в обусловленные заказом сроки 505 складированных блоков должны будут доставлены клиентам прямо со складов. Стоимости перевозок блоков со складов к клиентам даны в следующей таблице. Клиент 1 Клиент 2 Клиент 3 Клиент 4 Клиент 5 Клиент 6 Клиент 7 Склад 1 27 57 63 21 30 39 24 Склад 2 69 21 27 66 48 45 51 Склад 3 42 18 42 54 33 39 36 a. Составьте план перевозок заводы-клиенты, заводы-склады и склады- клиенты так, чтобы издержки корпорации были минимальны. Учтите, что изготовленные заранее 505 блоков, реально можно складировать следующим образом: Склад А -150 шт., Склад В -150 шт. и Склад С -205 шт. b.

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

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

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

Давайте начнем с перевозок заводы-клиенты. Как следует из условия задачи заводы представят к перевозке 1050 блоков, из которых к клиентам можно будет перевезти 545 блоков, а остальные придется везти на склады. Для нас это означает, что первая из отдельных задач не сбалансирована. Для того, чтобы сбалансировать задачу придется добавить фиктивного клиента, который и «закажет» лишние 505 блоков. В этом случае задачу можно построить следующим образом (Рис. 80). А В С В Е Б о н I I 1 Оптимизация перевозок по частям: заводы-клиенты 2 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 Скл. Объем производства 3 ЖБИ 1 84 36 42 81 63 60 66 290 4 ЖБИ 2 63 48 33 24 33 21 33 165 5 ЖБИ 3 63 18 33 66 45 45 51 235 6 ЖБИ 4 39 33 57 63 42 51 45 255 7 ЖБИ 5 30 21 42 42 24 33 24 105 8 1-ый

Заказ 90 65 45 75 95 100 75 505 =СУММПРОИЗВ(В3:

17;В11:115) 9 10 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 Скл. итого 11 ЖБИ 1 =СУММ(В 11:111)13 12 ЖБИ 2 =СУММ(В 12:112) -14 13 ЖБИ 3 =СУММ(В13:113) -15 14 ЖБИ 4 =СУММ(В 14:114) -16 15 ЖБИ 5 =СУММ(В15:115) -17 16 =СУММ(В11:В15)-

В8 =СУ =СУ =СУ =СУ Рис. 80

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

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

Заказ 90 65 45 75 95 100 75 505 15 555 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 Скл. итого ЖБИ 1 0 0 0 0 0 0 0 290 290 ЖБИ 2 0 0 0 75 0 90 0 0 165 ЖБИ 3 0 65 45 0 0 10 0 115 235 ЖБИ 4 90 0 0 0 65 0 0 100 255 ЖБИ 5 0 0 0 0 30 0 75 0 105 0 0 0 0 0 0 0 0 Рис. 81

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

Следующая часть перевозок - перевозки с заводов на склады. В предыдущей части мы выяснили, сколько блоков должно быть вывезено на склады с каждого из заводов. Емкость складов и цены перевозки нам известны из условия задачи. Составим соответствующую таблицу (Рис. 82). А В С В Е 1 Оптимизация перевозок по частям: заводы-склады 2 Склад 1 Склад 2 Склад 3 3 ЖБИ 1 78 15 42 290 4 ЖБИ 2 33 60 60 0 5 ЖБИ 3 60 9 24 115 6 ЖБИ 4 51 45 15 100 7 ЖБИ 5 33 39 12 0 8 150 150 205 =СУММПРОИЗВ(В3 :Э 7;В11:Э15) 9 10 Склад 1 Склад 2 Склад 3 итого 11 ЖБИ 1 =СУММ(В11:Э11)-Е3 12 ЖБИ 2 =СУММ(В12:Э12)-Е4 13 ЖБИ 3 =СУММ(В13:Э13)-Е5 14 ЖБИ 4 =СУММ(В14:Э14)-Е6 15 ЖБИ 5 =СУММ(В15:Э15)-Е7 16 =СУММ(

В11:В15)-

В8 =СУММ( С11:С 15)- С8 =СУММ(

В11:В15)

-Э8 Рис. 82

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

Поиск решения дает следующий результат для этой части перевозок (Рис. 150 150 205 17 790 Склад 1 Склад 2 Склад 3 итого ЖБИ 1 35 150 105 0 ЖБИ 2 0 0 0 0 ЖБИ 3 115 0 0 0 ЖБИ 4 0 0 100 0 ЖБИ 5 0 0 0 0 0 0 0 Рис. 83

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

И последняя часть задачи - перевозки с трех складов к клиентам, которые происходят через две недели. Задача и здесь сбалансирована, второй заказ в сумме составляет 505 блоков, которые мы ранее запасли на трех складских площадках. Составляем новую таблицу (Рис. 84) и ищем решение последней, третьей задачи. А В С В Е Б О Н I 1 Оптимизация перевозок по частям: склады-клиенты 2 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 Запасы 3 Склад 1 27 57 63 21 30 39 24 150 4 Склад 2 69 21 27 66 48 45 51 150 5 Склад 3 42 18 42 54 33 39 36 205 6 2-ой

Заказ 55 45 70 75 40 35 185 =СУММПРОИЗВ(В

3:Н5;В9:Н11) 7 8 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 9 Склад 1 =СУММ(В9:Н9)-13 10 Склад 2 =СУММ(В10:Н10)-

14 11 Склад 3 =СУММ(В 11:Н11)- 15 12 =СУ

ММ(

В9:В

11)-

В6 =СУ

ММ(

С9:С

11)-

С6 =СУ

ММ(

В9:Э

11)-

Э6 =СУ

ММ(

Е9:Е1

1)-Е6 =СУ

ММ(

Р9:Б1

1)-Б6 =СУ

ММ(

О9:О

11)-

О6 =СУ

ММ(

Н9:Н

11)-

Н6 Рис. 84

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

Заказ 55 45 70 75 40 35 185 15 210 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 Склад 1 55 0 0 75 0 0 20 0 Склад 2 0 45 70 0 0 35 0 0 Склад 3 0 0 0 0 40 0 165 0 0 0 0 0 0 0 0 Рис. 85

Суммируя все три результата мы можем сказать, что минимальные издержки при оптимизации перевозок по частям составят 48555 единиц. А В С Б Е Е О Н I 1 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 Объем произв. 2 ЖБИ 1 84 36 42 81 63 60 66 290 3 ЖБИ 2 63 48 33 24 33 21 33 165 4 ЖБИ 3 63 18 33 66 45 45 51 235 5 ЖБИ 4 39 33 57 63 42 51 45 255 6 ЖБИ 5 30 21 42 42 24 33 24 105 7 1-ый

Заказ 90 65 45 75 95 100 75 =СУММПРОИЗВ(

В2:Н6;В10:Н14) 9 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 итого 10 ЖБИ 1 =СУММ(В10:Н10) 11 ЖБИ 2 =СУММ(В11:Н11) 12 ЖБИ 3 =СУММ(В12:Н12) 13 ЖБИ 4 =СУММ(В13:Н13) 14 ЖБИ 5 =СУММ(В14:Н14) 15 =СУМ =СУМ =СУМ =СУМ =СУМ =СУМ =СУММ(Н10:Н14)-Н7 17 Склад 1 Склад 2 Склад 3 Полные издержки 18 ЖБИ 1 78 15 42 =17+Е23+137 19 ЖБИ 2 33 60 60 20 ЖБИ 3 60 9 24 21 ЖБИ 4 51 45 15 22 ЖБИ 5 33 39 12 23 150 150 205 =СУММПР0ИЗВ(В18:В22;В26:В30) 25 Склад 1 Склад 2 Склад 3 итого 26 ЖБИ 1 =СУММ(В26:Б26) =Е26+110-12 27 ЖБИ 2 =СУММ(В27:Б27) =Е2 7+111-13 28 ЖБИ 3 =СУММ(В28:Б28) =Е2 8+112-14 29 ЖБИ 4 =СУММ(В29:Б29) =Е2 9+113-15 30 ЖБИ 5 =СУММ(В30:Б30) =Е3 0+114-16 31 =СУМ =СУМ =СУММ 1(Б26:Б3 0)-Б23 33 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 Запасы 34 Склад 1 27 57 63 21 30 39 24 150 35 Склад 2 69 21 27 66 48 45 51 150 36 Склад 3 42 18 42 54 33 39 36 205 37 2-ой

Заказ 55 45 70 75 40 35 185 =СУММПРОИЗВ(

В34:Н36;В40:Н42) 39 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 итого 40 Склад 1 =СУММ(В40:Н40) 41 Склад 2 =СУММ(В41:Н41) 42 Склад 3 =СУММ(В42:Н42) 43 =СУМ =СУМ =СУМ =СУМ =СУМ =СУМ =СУММ(Н40:Н42)-Н37 Рис. 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 раз. Время, минут O1 O2 O3 O4 O5 P1 67 55 51 63 49 P2 61 77 52 72 66 P3 63 73 72 42 58 P4 52 44 72 50 55 P5 53 76 63 45 47 P6 70 55 77 46 67 P7 43 61 75 54 75 P8 69 70 55 47 61 P9 71 56 67 42 45 P10 68 63 77 61 69 P11 54 59 51 66 56 Р12 57 53 61 62 59 Р13 73 64 46 72 60 Р14 70 65 78 45 49 Определите оптимальное распределение рабочих по операциям. Рассчитайте количество рабочего времени, требующегося на выполнение заказа. Можно ли при этом выполнить заказ за 10 рабочих дней? (Считайте, что рабочая смена равна 8 часам.)

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

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

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

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

Для решения задачи построим обычную таблицу, которая для всех транспортных задач и задач о назначениях выглядит практически одинаково (Рис. 87). А В с Б Е Г а Н I 1 01 02 03 04 05 Другие

работы Рабочее время 2 Р1 67 55 51 63 49 0 =СУММПРОИЗВ(В2:а2;В18:а18) 3 Р2 61 77 52 72 66 0 =СУММПРОИЗВ(В3:а3;В19:а19) 4 Р3 63 73 72 42 58 0 =СУММПР0ИЗВ(В4:а4;В20:а20) 5 Р4 52 44 72 50 55 0 =СУММПР0ИЗВ(В5:а5;В21:а21) 6 Р5 53 76 63 45 47 0 =СУММПР0ИЗВ(В6:а6;В22:а22) 7 Р6 70 55 77 46 67 0 =СУММПР0ИЗВ(В7:а7;В23:а23) 8 Р7 43 61 75 54 75 0 =СУММПР0ИЗВ(В8:а8;В24:а24) 9 Р8 69 70 55 47 61 0 =СУММПР0ИЗВ(В9:а9;В25:а25) 10 Р9 71 56 67 42 45 0 =СУММПР 0ИЗВ (В10:а 10;В26: а26) 11 Р10 68 63 77 61 69 0 =СУММПР0ИЗВ(В11:а11;В27:а27) 12 Р11 54 59 51 66 56 0 =СУММПР0ИЗВ(В12:а12;В28:а28) 13 Р12 57 53 61 62 59 0 =СУММПР0ИЗВ(В13:а13;В29:а29) 14 Р13 73 64 46 72 60 0 =СУММПР0ИЗВ(В14:а14;В30:а30) 15 Р14 70 65 78 45 49 0 =СУММПР0ИЗВ(В15:а15;В31:а31) 16 =СУММ(Н2:Н15) 17 01 02 03 04 05 Д.р. Раб. дней 18 Р1 =СУММ(В18:а18) =Н2* 100/60/8 19 Р2 =СУММ(В19:а19) =Н3* 100/60/8 20 Р3 =СУММ(В20:а20) =Н4* 100/60/8 21 Р4 =СУММ(В21:а21) =Н5* 100/60/8 22 Р5 =СУММ(В22:а22) =Н6* 100/60/8 23 Р6 =СУММ(В23:а23) =Н7* 100/60/8 24 Р7 =СУММ(В24:а24) =Н8* 100/60/8 25 Р8 =СУММ(В25:а25) =Н9* 100/60/8 26 Р9 =СУММ(В26:а26) =Н10*100/60/8 27 Р10 =СУММ(В27:а27) =Н 11*100/60/8 28 Р11 =СУММ(В28:а28) =Н12*100/60/8 29 Р12 =СУММ(В29:а29) =Н13*100/60/8 30 Р13 =СУММ(В30:а30) =Н14*100/60/8 31 Р14 =СУММ(В31:а31) =Н15* 100/60/8 32 =СУМ =СУМ =СУМ =СУМ =СУМ =СУММ(а18:а31)-а33 =МАКС(12:Л5) 33 1 1 1 1 1 9 34 35 =Н16*100/60 <-Всего рабочих часов Рис. 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) 220 01 02 03 04 05 Д. р. Раб. дней Р3 0 0 0 1 0 0 1 8.75 Р4 0 1 0 0 0 0 1 9.17 Р7 1 0 0 0 0 0 1 8.96 Р9 0 0 0 0 1 0 1 9.38 Р13 0 0 1 0 0 0 1 9.58 0 0 0 0 0 0 9.58 1 1 1 1 1 9 366.7 <-Всего рабочих часов Рис. 88

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

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

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

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

Первый способ соответствует логике задачи - раз одна бригада набрана, давайте вычеркнем этих рабочих из списка. Т. е. нам нужно скопировать лист и удалить строки, соответствующие рабочим Р3, Р4, Р7, Р9 и Р13 из обеих частей таблицы, верхней и нижней. Только не забудьте проверить, что все формулы остались правильными. Кроме этого нужно изменить количество лишних рабочих в ячейке 033 с 9 до 4. После новой оптимизации получим второй план назначений (Рис. 89). 250 01 02 03 04 05 Д. р. Раб. дней Р1 0 0 1 0 0 0 1 10.63 Р5 0 0 0 0 1 0 1 9.79 Р11 1 0 0 0 0 0 1 11.25 Р12 0 1 0 0 0 0 1 11.04 Р14 0 0 0 1 0 0 1 9.38 0 0 0 0 0 0 11.25 1 1 1 1 1 4 416.7 <-Всего рабочих часов Рис. 89

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

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

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

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

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

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

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

Поэтому наша задача состоит в разбиении 10 выбранных рабочих на две бригады. В таблице 2.9 показан пример организации данных для решения задачи. А В С Э Е Р О I 1-я

бри

гада 2-я

бри

гада =СУММ(Р2:Р6) =СУММ(02:

06) 1 Р3 43 Р1 54 =С2*С9+Е2*Е9 =Е2+С2-Р2 =Р2* 100/60/8 =02*100/60/8 2 Р4 44 Р5 53 =С3*С10+Е3*Е10 =Е3+С3-Р3 =Р3* 100/60/8 =03*100/60/8 3 Р7 46 Р11 51 =С4*С11+Е4*Е11 =Е4+С4-Р4 =Р4* 100/60/8 =04*100/60/8 4 Р9 42 Р12 45 =С5 *С12+Е5 *Е 12 =Е5+С5-Р5 =Р5* 100/60/8 =05*100/60/8 5 Р13 45 Р14 47 =С6*С13+Е6*Е13 =Е6+С6-Р6 =Р6* 100/60/8 =06*100/60/8 220 250 =Р1-01 Войдут в первую бригаду 1 Р3 Р1 = 1-С9 2 Р4 Р5 = 1-С10 3 Р7 Р11 = 1-С11 4 Р9 Р12 = 1 -С 12 5 Р13 Р14 = 1 -С 13 Рис. 90

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

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

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

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

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

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

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

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

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

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

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

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

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

бри

гада 2-я

бри

гада 236 234 Время работы рабочих 1-ой бр. Время работы рабочих 2-ой бр. 1 P3 43 P1 54 54 43 11.3 9.0 2 P4 44 P5 53 44 53 9.2 11.0 3 P7 46 P11 51 51 46 10.6 9.6 4 P9 42 P12 45 42 45 8.8 9.4 5 P13 45 P14 47 45 47 9.4 9.8 220 250 2 Войдут в первую бригаду 1 P3 0 P1 1 Вторая 2 P4 1 P5 0 бригада - 3 P7 0 P11 1 остальны

е 4 P9 1 P12 0 рабочие 5 P13 1 P14 0 Рис. 91

В одну бригаду войдут рабочие P1, P4, P9, P11, P13, а в другую - P3, P5, P7, P9, P14. Следует заметить, что наши попытки выровнять бригады привели к тому, что время выполнения заказа увеличилось до 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 транспортные задачи (для трех возможных сочетаний двух новых цехов: Первомайское - Воскресенск, Дмитров - Первомайское и Дмитров - Воскресенск), либо совместив задачу выбора двух поставщиков из трех возможных с минимизаций издержек транспортных перевозок от них. Мы реализуем второй путь.

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

Начнем с анализа статус-кво. Насколько сложившаяся практика поставок выгодна для компании в целом? В тексте кейса можно найти информацию о ценах и объемах перевозок, а также о величинах оцениваемого дефицита поставок. Все необходимые для дальнейшего анализа данные собраны в таблице. Подольск Голицыно Бронницы Лобня Запас Черноголовка 1100 1400 900 900 200 Обнинск 900 B00 1300 1300 150 Первомайское 700 500 950 600 150 Дмитров 1550 1220 1750 500 150 Воскресенск 1050 1550 300 1400 150 Заказ 1B0 250 60 160 Рис. 92

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

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

день. Черноголовка Подольск Голицыно Бронницы Лобня Запас Черноголовка O 1100 1400 900 900 270 Обнинск 2000 900 B00 1300 1300 150 Заказ 70 1B0 250 60 160 Дефицит O -B0 -100 -З0 -90 Поставка 7O 100 150 З0 70 Рис. 93

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

На Рис. 94 приведены планы поставок как есть и как должно быть из соображений минимума издержек (нижняя таблица), а также соответствующие издержки. A B C D E F G 1 Status Quo: Издержки и заказы 2 Черноголовка Подольск Голицыно Бронницы Лобня Запас 3 Черноголовка 0 1100 1400 900 900 270 4 Обнинск 2000 900 800 1300 1300 100 О 6 Потребность 70 180 200 60 160 720 7 Дефицит 0 -80 -100 -30 -90 8 Заказ 70 100 100 30 70 420 9 10 Status Quo: Реально существу /ющий план перевозок 11 Черноголовка Подольск Голицыно Бронницы Лобня Запас 12 Черноголовка 70 100 00 270 13 Обнинск 100 30 20 100 14 Заказ 70 100 100 30 70 420 10 Средневзвешенные транспортные издержки 16 0 900 1 400 1 300 1 014 18 Издержки Status Quo= 410 000 19 20 Оптимум для Status Quo. 21 Черноголовка Подольск Голицыно Бронницы Лобня Запас 22 Черноголовка 70 100 0 30 70 270 23 Обнинск 0 0 100 0 0 100 24 Заказ 70 100 100 30 70 420 20 Средневзвешенные транспортные издержки 26 0 1 100 800 900 900 27 Выигрыш

\Проигрыш 0 -200 600 400 114 29 Оптимальные издержки= 320 000 Рис. 94

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

Перейдем теперь к решению задачи об оптимальном выборе местоположения для новых цехов. На Рис. 95 представлена организация данных на листе MS Excel для использования Поиска решения. А | B | С | D E F G 1 Выбор положения цехов и объемов поставок 2 Подольск Голицыно Бронницы Лобня Запас 3 Черноголовка 1100 1400 900 900 200 4 Обнинск 900 800 1300 1300 150 5 Первомайское 700 500 950 600 1 50 6 Дмитров 1550 1220 1750 500 150 7 Воскресенск 1050 1550 300 1400 150 8 Заказ 180 250 60 160 9 Полные издержки = =СУММПРОИЗВ(С3:

F7;d2:F16) 10 11 Брать\Не брать Подольск Голицыно Бронницы Лобня Запас 12 Черноголовка =СУММ(С12^12)-

G3*B12 13 Обнинск =СУММ(С13^13)-

G4*B13 14 Первомайское =СУММ(С14^14)-

G5*B14 15 Дмитров =СУММ(С15^15)-

G6*B15 16 Воскресенск =СУММ(С16^16)-

G7*B16 17 Заказ =СУММ(С =СУММ(Р- =СУММ(Е =СУММ^12^16)^8 18 19 Средневзвешенн ые транспортные издержки 20 =СУММП

РОИЗВ(С

12:С16;С3

:С7)/С8 =СУММПР

ОИЗВ(й12

:D16;D3:D

7)/D8 =СУММПР

ОИЗВ(Е12

:Е16;Е3:Е

7)/E8 =СУММПР

ОИЗВ^12:

F16;F3:F7)/

F8 21 Средневзвешенные транспортные издержки для Status Quo 22 900 1 400 1 300 1 014 23 Выигрыш

\Проигрыш =С22-С20 =D22-D20 =Е22-Е20 =F22-F20 Рис. 95

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

Ограничения в ячейках C17:F17 - обычное для транспортной задачи требование удовлетворения заказа данного потребителя - отделения компании. Аналогично, в ячейках H12:H16 введено ограничение, обусловленное производственными мощностями цехов в Черноголовке и Обнинске. Обратите внимание, что величина производственной мощности множится на двоичную переменную «Выбирать или не выбирать» данное место для строительства цеха. Очевидно, если эта переменная равна 0 («не выбирать»), то запас, соответствующий этому гипотетическому цеху равен 0. При задании ограничений в Поиске решения необходимо, очевидно, потребовать, чтобы ячейки C18:F18 и H12:H16 равнялись нулю. Кроме этого, можно потребовать, чтобы двоичные переменные B12:B13 оставались равными единице. Это означает, что старые места цехов уже выбраны.

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

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

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

Видно, что модель рекомендует выбрать Дмитров и Первомайское в качестве мест для строительства новых цехов. При этом суммарные транспортные издержки составят 481000 руб. в год. В случае выбора пар Дмитров -Воскресенск или Первомайское -Воскресенск издержки соответственно 555500 руб. и 500500 руб. (проверьте это непосредственным решением транспортной задачи для данных вариантов). A B C D E F G 1 Выбор положения цехов и объемов поставок 2 Подольск Голицыно Бронницы Лобня Запас 3 Черноголовка 1100 1400 900 900 200 4 Обнинск 900 800 1300 1300 150 5 Первомайское 700 500 950 600 150 6 Дмитров 1550 1220 1750 500 150 7 Воскресенск 1050 1550 300 1400 150 8 Заказ 180 250 60 160 9 Полные издержки= 481 000 10 11 Брать\Не брать Подольск Голицыно Бронницы Лобня Запас 12 Черноголовка 1 130 0 60 10 0 13 Обнинск 1 50 100 0 0 0 14 Первомайское 1 0 150 0 0 0 15 Дмитров 1 0 0 0 150 0 16 Воскресенск 0 0 0 0 0 0 17 Заказ 0 0 0 0 18 19 Средневзвешенные транспортные издержки 20 1 044 620 900 525 21 Средневзвешенные транспортные издержки для Status Quo 22 900 1 400 1 300 1 014 23 Выигрыш

\Проигрыш -144 780 400 489 Рис. 96

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

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

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

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

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

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

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

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

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

k%min 5% 5% 5% 7% 7% Объем

(млн.тонн) 18 25 30 15 20 Рис. 97

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

k - k

C = (1-H • —) C max k ?

с параметрами, специфическими для каждого завода, представленными в следующей таблице (Рис. 98). Параметры зависимости себестоимости от концентрации ИК в сырье Завод 1 Завод 2 Завод 3 Завод 4 Завод 5 Стах

$/тыс.тонн 20,0 18,0 16,0 22,0 20,0 н 1,5 1,2 1,2 1 1 Рис. 98

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

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

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

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

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

ненадеж

ности Максимум,

млн.

тонн Минимум,

млн.

тонн %

концентрации

ИК Цена

($/тонна) 1 4 16 1 6,00% 11,25 2 2 20 1 8,00% 23,7 3 6 24 1 5,80% 11,3 4 8 28 1 5,30% 10,65 5 1 30 2 7,80% 22,2 6 6 32 2 6,20% 14,7 7 5 34 2 7,10% 17,3 8 4 36 2 6,00% 12,55 9 9 38 3 5,90% 10,8 10 6 40 3 5,60% 10,6 Рис. 99

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

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

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

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

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

Феофан поручил Максу, для начала, две задачи. Первая задача (ради которой, собственно, по настоянию «общественности», и был взят молодой специалист-«оптимизатор») - это минимизация издержек транспортных перевозок от поставщиков, выбранных отделом закупок, к заводам компании. В глубине души, Феофан был уверен, что ничего нового эта задача для отдела логистики не даст. После того как отдел Боба определил поставщиков, вариантов перевозок было не так уж много, они сильно различались по цене и неоднократно были тщательно проанализированы его сотрудниками. Что тут делать компьютерным методам? Тем не менее, он предоставил Максу таблицу цен перевозок от каждого из 10 возможных поставщиков к каждому из заводов (Рис. 100). Цены перевозки 1 тонны сырья от каждого из 10 мировых поставщиков к каждому заводу компании Заводы-потребители Поставщики 1 2 3 4 5 1 24,2 17,6 25,8 24,2 18,8 2 28,8 9,6 11,8 10,2 15,6 3 15,0 7,8 21,8 8,2 11,0 4 23,2 17,4 25,4 19,8 26,2 5 23,6 20,2 22,6 20,4 14,6 6 14,2 8,2 9,4 15,8 8,4 7 12,0 16,2 19,2 18,2 19,0 8 15,8 19,0 12,6 24,0 21,2 9 11,4 20,2 16,6 25,4 22,2 10 21,4 20,2 16,6 25,4 22,2 Рис. 100

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

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

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

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

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

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

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

Приложение

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

к - к

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

к тш

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

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

Анализ действия 1 кейса.

Определение оптимального плана закупок

В задаче определения оптимального плана закупок переменными решения, очевидно являются объемы закупок у каждого i-го поставщика V . Поскольку поставщиков 10, i меняется от 1до 10.

Помимо этого необходимо ввести 10 двоичных переменных типа «выбрать -

не выбирать» для каждого поставщика:

(0 - не выбирать

xi = i

[1 - выбрать

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

V > х. • V.

I г mini

Аналогичное ограничение на величину поставок от каждого поставщика сверху запишется в виде: V

< V

г maxi

Как было рассмотрено в кейсе «На кондитерской фабрике» (действие 3), необходимо обеспечить связь между парой переменных хi о- Vi , которая исключала бы ситуацию, когда V

> 0, а xt = 0

Действительно, если мы не выбрали данного поставщика, т.е. х, = 0 , то обязательно должно быть V, = 0, т.е. никаких закупок у данного поставщика не делается. Эта связь задается условием: V

-100 • X,. < 0

Число 100 здесь - это большое число, превышающее максимальный объем, который каждый поставщик способен продать. Последнее условие можно было бы записать в виде V

- V • X. < 0

, max, , —

В этом случае это условие включило бы и ограничение V, < Vmax и условие связи V, - 100*х, < 0 , вынуждающее алгоритм положить V, = 0 , если х, = 0 .

Два других очевидных ограничения - это ограничение на суммарный объем закупок

10 5

Z V.=Z Vj =108

,=1 j=1

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

потребности 5-ти заводов компании - 108 млн. тонн, и

10

ZV (%ИК, > 7%) > 35

,=1

состоящее в том, что суммарный объем закупок сырья с высоким (более 7%) содержанием искомого компонента в руде должен покрывать потребности 2х заводов компании, и следовательно, такое сырье должно быть закуплено в объеме, не меньшем, чем 35 млн. тонн.

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

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

10

Z Rii-V

RI = J=1

закупок 10

Z V

,=1

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

10 5

никакой необходимости, т.к. согласно условию V=108 , суммарный

i=l ]=1

объем закупок должен точно равняться 108 млн. тонн. Учитывая это обстоятельство, можно переписать выражение S Щ-V

RI _ _i_1

закупок 10

S V

i_1

в виде

S Щ-V RI-

108

закупок

и потребовать, чтобы этот индекс в оптимальном плане не превышал 4:

RI < 4

закупок

Наконец выражение для целевой функции - суммарной стоимости закупок,

которая должна быть минимальна, запишется в виде:

10

с =

2_1

где Ci — стоимость одной тонны сырья у i -го поставщика. A в C D E F G H I J K 1 План закупок. Выбор поставщиков. Оптимизация 2 3 Завод 1 2 3 4 5 4 Кол-во 18 25 30 15 20 5 min % ИК 5% 5% 5% 7% 7% Ь 7 Постав

щик Max Min % ИК Цена Индекс

надеж

ности Брать/не

брать Объем закупок Условие

связи Мин.

объем 8 1 1Ь 1 Ь.0% 7.50 4 =I8-100*H8 =C8*H8 9 2 30 1 8.0% 15.80 2 10 3 24 1 5.8% 7.53 6 11 4 28 1 5.3% 7.10 8 12 5 20 2 7.8% 14.80 1 13 6 32 2 Ь.2% 9.80 6 14 7 34 2 7.1% 11.53 5 15 8 3Ь 2 Ь.0% 8.37 4 1Ь 9 38 3 5.9% 7.20 9 17 10 40 3 5.Ь% 7.07 6 18 ИТОГО Требуется 19 Закупок =СУММ(18:117) =СУММ(В4^4) 20 Стоимость Закупок

с%ИК>7% =I9+I12+I14 =E4+F4 21 =СУММПРОИЗВ($1$8:$1$

17;E8:E17) Индекс

надежности =СУММПРОИЗ

В($!$8:$!$17^

8:F17)/J19 4 Рис. 101

На Рис. 101 приведена организация данных на листе MS Excel для использования Поиска решений. В ячейках A1:F3 введены данные, касающиеся требования к поставкам сырья 5-ти заводов компании, а в ячейках A4:F16 - данные о потенциальных поставщиках компании, включая возможные максимальный и минимальный объем закупок, %ИК в руде, цену одной тонны руды и индекс надежности, приписанный поставщику экспертами отдела закупок компании НАЦПРОДУКТ. Двоичные переменными решения располагаются в ячейках Н7:Н16 («выбрать поставщика или не выбирать») и переменные объемы закупок - в ячейках 17:116. Целевая функция введена в ячейку Ь7.

В ячейки 17:116 введены условия связи между объемом закупок V] и двоичной переменной Х( (4), а в ячейки К7:К16 - выражения для минимального объема закупок, равного либо 0, либо Vmin.

Наконец, в ячейках 118:121 введены левые части ограничений на суммарный объем закупок, на объем закупок руды с высоким процентным содержанием ИК (%ИК>7%), а также выражение для средневзвешенного индекса надежности поставщиков. В ячейках Л8:121 - соответственно правые части ограничений (6), (7), (9).

Оптимальный план поставок, полученный с использованием Поиска решений, представлен на Рис. 102. A в C D E F G H I Л К 1 План закупок. Выбор поставщиков. Оптимизация 2 3 Завод 1 2 3 4 5 4 Кол-во 18 25 30 15 20 5 min % ИК 5% 5% 5% 7% 7% b 7 Постав

щик Max Min % ИК Цена Индекс

надеж

ности Брать/не

брать Объем закупок Условие

связи Мин.

объем 8 1 1b 1 b.0% 7.50 4 1 16.00 -84 1.00 9 2 30 1 8.0% 15.80 2 0 0.00 0 0.00 10 3 24 1 5.8% 7.53 6 0 0.00 0 0.00 11 4 28 1 5.3% 7.10 8 0 0.00 0 0.00 12 5 20 2 7.8% 14.80 1 1 19.25 -81 2.00 13 b 32 2 b.2% 9.80 6 0 0.00 0 0.00 14 7 34 2 7.1% 11.53 5 1 15.75 -84 2.00 15 8 3b 2 b.0% 8.37 4 1 36.00 -64 2.00 1b 9 38 3 5.9% 7.20 9 0 0.00 0 0.00 17 10 40 3 5.b% 7.07 6 1 21.00 -79 3.00 18 ИТОГО Т ребуется 19 Закупок 108.00 108 20 Стоимость Закупок с%ИК>7% 35.00 35 21 1036.15 Индекс надежности 4.00 4 Рис. 102

Видно, что следует выбрать поставщиков №1, 5, 7, 8 и 10. При этом все ограничения по объему поставок, качество сырья и надежности поставок выполнены.

В полученном решении условие связи между двоичными переменными и объема закупок (V - 100*хг- < 0) фактически не является связывающим. И без него Поиск решения выбрал объемы закупок, превышающие минимально допустимые. Легко понять, что это отнюдь не всегда будет так. Пусть, например, поставщики требуют, чтобы минимальные объемы закупок составляли не менее 50% от объявленных ими же максимальных допустимых объемов. Решение задачи в этом случае показано на Рис. 103.

Видно, что теперь условие связи V - 100*хг- < 0 существенно влияет на решение, ухудшая целевую функцию и меняя оптимальный выбор поставщиков. A в C D E F G H I Л К 1 План закупок. Выбор поставщиков. Оптимизация 2 3 Завод 1 2 3 4 5 4 Кол-во 18 25 30 15 20 5 min % ИК 5% 5% 5% 7% 7% Ь 7 Постав

щик Max Min % ИК Цена Индекс

надеж

ности Брать/не

брать Объем закупок Условие

связи Мин.

объем 8 1 1Ь 8 Ь.0% 7.50 4 1 15.00 -85 8.00 9 2 30 15 8.0% 15.80 2 1 15.00 -85 15.00 10 3 24 12 5.8% 7.53 6 0 0.00 0 0.00 11 4 28 14 5.3% 7.10 8 0 0.00 0 0.00 12 5 20 10 7.8% 14.80 1 1 20.00 -80 10.00 13 6 32 1Ь Ь.2% 9.80 6 0 0.00 0 0.00 14 7 34 17 7.1% 11.53 5 0 0.00 0 0.00 15 8 3Ь 18 Ь.0% 8.37 4 1 18.00 -82 18.00 1Ь 9 38 19 5.9% 7.20 9 0 0.00 0 0.00 17 10 40 20 5.Ь% 7.07 6 1 40.00 -60 20.00 18 ИТОГО Требуется 19 Закупок 108.00 108 20 Стоимость Закупок с%ИК>7% 35.00 35 21 1078.77 Индекс надежности 3.91 4 Рис. 103

Определение оптимального плана перевозок

Это задача практически мало отличается от обычной сбалансированной транспортной задачи. На Рис. 104 показана организация данных для Поиска решения М8-Бхее1.

После выбора поставщиков на предыдущем шага анализа кейса, в таблице цен транспортных перевозок от каждого из потенциальных поставщиков к каждому из 5-ти заводов компании, осталось всего 5 строк, а именно строки № 1,5,7,8,10 - т.е. строки с номерами выбранных поставщиков.

Переменные решения БИЛ6 - объемы перевозок от каждого из выбранных поставщиков к каждому заводу-потребителю. В ячейках 011:015 - стандартные требования поставщиков: суммарный вывезенный объем от каждого поставщика равен его запасу, а в ячейках Б16:Б16 - аналогичные требования заводов потребителей: суммарный объем сырья, привезенный от каждого из поставщиков, равен заказу.

Единственное отличие данной задачи от транспортной - это требования каждого поставщика к качеству сырья: средневзвешенное процентное содержание ИК в доставленной руде не должно быть меньше минимально допустимого. Для заводов 1-3 это 5%, а для заводов 4-5, это 7%. Эти требования выражены ограничениями, введенными в ячейках Б17:Б17.

При этом снова, как и на предыдущем шаге анализа, выражение для средневзвешенного процентного содержания ИК в руде, доставленной ]-ому заводу потребителю

i=1

2 % ИК г Vi

% ИК

] поставки

г =1

где V/ - объем сырья привезенный от /-го поставщика, заменен на

Е % Щ. Vi % ИК = —

j поставки т г

Vj

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

Целевая функция, равная сумме сумм произведений цен на объемы перевозок введена в ячейку Н17. A B с D E F G H I 1 Оптимальный план перевозок 3 Поставщик 1 2 3 4 5 Объем закупо % ИК Цена 4 1 24.2 17.6 25.8 24.2 18.8 16.00 0.060 7.50 5 5 23.6 20.2 22.6 20.4 14.6 19.25 0.078 14.80 6 7 12 16.2 19.2 18.2 19 15.75 0.071 11.53 7 8 15.8 19 12.6 24 21.2 36.00 0.060 8.37 8 10 21.4 20.2 16.6 25.4 22.2 21.00 0.056 7.07 9 Заказы 18 25 30 15 20 10 min % ИК 0.05 0.05 0.05 0.07 0.07 II 12 Поставщик 1 2 3 4 5 Издержки 13 1 =СУММ(В13:

F13)-G4 =СУММПРОИЗВ(В4^4;В

13:F13) 14 5 =СУММ(В14:

F14)-G5 =СУММПРОИЗВ(В5^5;В

14:F14) 15 7 =СУММ(В15:

F15)-G6 =СУММПРОИЗВ(В6^6;В

15:F15) 16 8 =СУММ(В16:

F16)-G7 =СУММПРОИЗВ(B7:F7;B

16:F16) 17 10 =СУММ(В17:

F17)-G8 =СУММПРОИЗВ(B8:F8;B

17:F17) 18 =СУММ(В13:В17)-В9 =СУММ(Н13 :Н17) 19 Реальный % ИК =СУММПРОИЗВ(В13:B17;$H$4:$H$8)/B9 Рис. 104

Решение задачи приведено на Рис. 105.

Видно, что все ограничения на объемы поставок и качество доставленного сырья выполнены. При этом 4-му и 5-му заводу поставки осуществляются не только от поставщиков руды с процентным содержанием ИК выше 7%, но и от тех, где %ИК ниже 7%. Предполагается, что перед переработкой сырье, пришедшее от разных поставщиков, проходит стадию перемешивания так, что концентрация ИК в ней становится равной средневзвешенному значению, которое, как видно, удовлетворяет необходимым требованиям. А | В | С | Э E F G H I 1 Оптимальный план перевозок 3 Поставщик 1 2 3 4 5 Объем закупок % ИК Цена 4 1 24.2 17.b 25.8 24.2 18.8 1b.00 0.0b0 7.50 5 5 23.b 20.2 22.b 20.4 14.b 19.25 0.078 14.80 b 7 12 1b.2 19.2 18.2 19 15.75 0.071 11.53 7 8 15.8 19 12.b 24 21.2 3b.00 0.0b0 8.37 8 10 21.4 20.2 1b.b 25.4 22.2 21.00 0.05b 7.07 9 Заказы 18 25 30 15 20 10 min % ИК 0.05 0.05 0.05 0.07 0.07 11 12 Поставщик 1 2 3 4 5 Издержки 13 1 0 15.25 0 0 0.75 0.000 282.50 14 5 0 0 0 0 19.25 0.000 281.05 15 7 1.75 0 0 14 0 0.000 275.80 1b 8 1b.25 0 19.75 0 0 0.000 505.b0 17 10 0 9.75 10.25 1 0 0.000 392.50 18 0.000 0.000 0.000 0.000 0.000 1 737 19 Реальный % ИК 0.0b11 0.0584 0.058b 0.0700 0.0773 Рис. 105

Действие 2-е: Оптимизация и здравый смысл.

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

Разумеется, опытные Боб и Феофан предоставили юноше информацию, которая они использовали для составления планов прошлого периода. Так что теперь можно было сравнить результаты «высоко научных методов» и здравого смысла профессионалов со стажем.

Боб был снисходителен и благодушен. Он все время похлопывал Макса по плечу и хвалил: -

Молодец, ты же выбрал именно тех самых поставщиков, что и мы! Правда, объем закупок у нас немного другой..., гм... и цена закупки у тебя получилась немного меньше., но это, брат, мелочи! Разница-то. гм, ведь это чуть больше, чем твоя зарплата за год, ха-ха, шучу, конечно! Зато у нас надежность поставщиков выше. А это в нашем деле важнее, чем какие-то 0,2% себестоимости закупок. -

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

Макс согласился. -

А после этого, план закупок определяется просто на основе здравого смысла. Хочешь, покажу как?

Боб показал. Макс стоял, словно в воду опущенный. Боб успокаивал: -

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

И Макс пошел к Феофану.

Феофану результаты Макса не понравились совсем. Сначала он вообще не понял, как можно везти на завод, у которого минимально допустимая концентрация ИК в руде 7%, сырье с процентным содержанием ИК равным 6%. Макс объяснил, что перед переработкой сырье, пришедшее от разных поставщиков, проходит стадию перемешивания. При этом концентрация ИК становится равной средневзвешенному значению. (Он узнал это, поговорив с менеджером из производственного отдела). После этого Феофан смягчился, однако мнения о полезности расчета не изменил: -

Ну что это меняет? Посмотри, в твоем варианте транспортные издержки всего на 0,1% меньше, чем у меня. Я же тебе говорил, что если поставщики заданы, то маршруты перевозок сырья на заводы определяются элементарно. Показать?

Макс расстроился окончательно, но Феофан не унимался: -

И это все, что может твоя оптимизация? Почему вы - он имел в виду и Макса и Боба - все время выбираете тех поставщиков, от которых дорого вести?

Анализ действия 2 кейса.

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

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

Используем организацию данных на листе MS Excel, близкую к представленной на Рис. 101).

В качестве переменных решения рассматриваем только объемы поставок, а введенные формулы используем для расчета стоимости закупки (ячейка A21), общего объема поставок и объема поставок руды с высоким содержанием ИК (I19,I20). Формула для средневзвешенного индекса надежности выбранных поставщиков введена в ячейку I21.

Попробуем заполнять таблицу, руководствуясь здравым смыслом. Наши ориентиры: -

выбирать надежных поставщиков, -

при этом стараться минимизировать цену закупки, -

закупить ровно 108 млн. тонн руды, -

при это не менее 35 млн. тонн должна быть руда с %ИК>7%.

Руководствуясь этими ориентирами разумно начать закупку у самого надежного поставщика № 5. У него индекс надежности 1, и руда качественная - %ИК=7,8%. Закупим у него максимум того, что он готов продать - 20 млн.тонн.

На следующем шаге вспомним, что нам надо закупить 35 млн. тонн руды с %ИК выше 7%. Здесь у нас всего 2 альтернативы: купить у поставщика №2 или №7. У поставщика №2 хороший индекс надежности (2), но слишком высокая цена. У поставщика №7 индекс надежности ниже «критического» уровня 4, однако если добавить его поставки к поставкам высоконадежного поставщика №5, средневзвешенный индекс надежности не выйдет за критический предел. Вместе с тем, его цена на треть меньше, чем цена поставщика №2.

Итак, купим у поставщика №7 недостающие нам 15 млн. тонн с %ИК=7,1%. Тогда мы удовлетворим требованию закупки 35 млн. тонн сырья с %ИК>7%. При этом наш индекс надежности будет равен 2,71.

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

минимум 4. Естественно, поэтому обратиться именно к поставщикам с этим индексам. Это поставщики №№ 1, 8. Более дешевый поставщик №1. Закупим у него максиму того, что он может продать - 16 млн. тонн. Далее, мы вынуждены обратиться к поставщику №8 и сделать у него также максимальную закупку - 36 млн. тонн. При этом наш средневзвешенный индекс надежности закупок будет 3,48, а суммарный объем закупок - 87 млн.тонн. Необходимо закупить еще 21 млн. тонн руды. Для этой закупки придется использовать поставщиков с индексом надежности 6 (лучше не осталось). Это поставщики №№ 1,6.10. Наиболее дешевый из них - поставщик №10. У него мы и закупим недостающие нам 21 млн. тонн руды.

Результирующий план представлен на Рис. 106. Видно, что этот план всего на 0,2% хуже (по величине целевой функции - суммарной стоимости закупок), чем план, полученный Максом с использованием формальной модели и инструмента оптимизации Поиск решения. а |б|с|о|е| р |о| н I I 1 План закупок. Выбор поставщиков. Здравый смысл Боба. 2 3 Завод 1 2 3 4 5 4 Кол-во 18 25 30 15 20 5 min % ИК 5% 5% 5% 7% 7% 6 7 Постав

щик Max Min % ИК Цена Индекс

надеж

ности Брать/не

брать Объем закупок 8 1 16 1 6.0% 7.50 4 1 16.00 9 2 30 1 8.0% 15.80 2 10 3 24 1 5.8% 7.53 6 11 4 28 1 5.3% 7.10 8 12 5 20 2 7.8% 14.80 1 1 20.00 13 6 32 2 6.2% 9.80 6 14 7 34 2 7.1% 11.53 5 1 15.00 15 8 36 2 6.0% 8.37 4 1 36.00 16 9 38 3 5.9% 7.20 9 17 10 40 3 5.6% 7.07 6 1 21.00 18 ИТОГО 19 Закупок 108.00 20 Стоимость Закупок с%ИК>7% 35.00 21 1038.60 Индекс надежности 3.97 Рис. 106

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

Обратим внимание, что у нас есть два завода-потребителя, к которым нужно отвести сырье с повышенным содержанием ИК, и два поставщика (№№5,7). У которых такое сырье есть. Таким образом, сначала решим транспортную задачу 2x2. Очевидно, что нужно отвести 20 млн. от поставщика №5 на завод №5, а не на завод №4, поскольку цена перевозки от поставщика №5 на завод №5 меньше, чем цена перевозки от него на завод №4. В то же время от поставщика №7 нужно 15млн. отвести на завод №4, так как эта цена ниже, чем цена перевозки от него на 5-ый завод. Таким образом, с перевозкой сырья с высоким содержанием ИК мы закончили.

Далее нужно сырье от поставщиков №№1,8,10 на заводы №№1-3. Это - транспортная задача 3x3. начнем с завода №1. Для него минимальная цена перевозки будет от поставщика №8. Привезем от этого поставщика требуемые заводом №1 18 млн. тонн. Оставшиеся у этого поставщика 18млн. тонн отвезем на завод №3 по минимальной возможной цене. Завод №3 требовал 30 млн. тонн. Недостающие ему 12 млн. тонн привезем от поставщика №10 по наименьшей возможной для этого поставщика цене. Оставшиеся у поставщика №10 9 млн. тонн отвезем на завод №2. И, наконец, доставим 16 млн. тонн от поставщика №1 на завод №2. Результирующий план представлен на Рис. 107.

Воспроизведенная логика выглядит очень ясной и естественной. Даже если Феофан и не с первого раза определил этот план, не вызывает сомнений, что методом проб и ошибок к этому почти оптимальному результату можно прийти очень легко. Видно, что суммарные транспортные издержки лишь на 0,1% выше, чем в оптимальном решении (принимающем во внимание, что из-за перемешивания сырья с разным содержанием ИК на заводы №4, №5 можно вести сырье не только от поставщиков №5, №7).

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

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

С другой стороны, Феофан и его отдел логистики отвечает за транспортные издержки, но не может выбирать от каких поставщиков вести сырье. Ведь не этот отдел заключает с ними договора о поставках! После же того, как поставщики определены, действительно, существуют очень немного разумных вариантов перевозок, и серьезной необходимости в компьютерных методах и, правда, нет. А | В | С | 0 Е Р 0 Н I 1 Оптимальный план перевозок 2 3 Поставщик 1 2 3 4 5 Объем закупок % ИК Цена 4 1 24.2 17.6 25.8 24.2 18.8 16.00 0.060 7.50 5 5 23.6 20.2 22.6 20.4 14.6 19.25 0.078 14.80 6 7 12 16.2 19.2 18.2 19 15.75 0.071 11.53 7 8 15.8 19 12.6 24 21.2 36.00 0.060 8.37 8 10 21.4 20.2 16.6 25.4 22.2 21.00 0.056 7.07 9 Заказы 18 25 30 15 20 10 т1п % ИК 0.05 0.05 0.05 0.07 0.07 11 12 Поставщик 1 2 3 4 5 Издержки 13 1 16 0.000 281.60 14 5 20 0.750 292.00 15 7 15 -0.750 273.00 16 8 18 18 0.000 511.20 17 10 9 12 0.000 381.00 18 0.000 0.000 0.000 0.000 0.000 1 739 19 Реальный % ИК 0.0600 0.0586 0.0584 0.0710 0.0780 20 Издержки переработки 21 Мах 20 18 16 22 20 22 к 1.5 1.2 1.2 1 1 ИТОГО 23 Реально 14.00 14.30 12.77 21.69 17.71 1 672.4 Рис. 107

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

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

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

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

Действие 3-е:

Интегрированный план для цепочки поставок Уходя домой, Макс думал, что и в сфере логистики, как говорил Боб, «развернуться» ему не удалось. Зря, наверное, он не пошел в аспирантуру.. Во всяком случае, в этой компании перспектив для оптимизации не видно. -

Хотя..., может попробовать по-другому...?- Тут он вспомнил последнюю фразу Феофана, и светлая мысль пришла ему в голову.

Как вы полагаете, какая?

Анализ действия 3 кейса.

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

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

k - k

C = (1 - H • —^) Cmax.

k mm

Просуммировав три функции издержек (закупок, перевозки и переработки), мы получим себестоимость производства металла Х в компании НАЦПРОДУКТ, которую сформировалась на основе «здравого смысла» -

ТС = 1038,6 + 1738,8 + 1642,7 = $ 4449,8 млн.

Ее и предстоит улучшить в интегрированном плане для цепочки поставок.

Организация данных для оптимизации интегрированного плана цепочки поставок представлена на Рис. 108. A|B|C|D|E|F| G | H I 1 Оптимальный интегрированный план в цепочке поставок НАЦПРОДУКТ. 2 Поставщи

ки Max Min % ИК ГО

І

ф Индекс Брать/ не брать Мин. закупка Связь 3 1 16 1 0.060 7.5 4 0 =G3*C3 =G15-100*G3 4 2 30 1 0.080 15.8 2 1 =G4*C4 =G16-100*G4 5 3 24 1 0.058 7.53 6 1 =G5*C5 =G17-100*G5 6 4 28 1 0.053 7.1 8 0 =G6*C6 =G18-100*G6 7 5 20 2 0.078 14.8 1 1 =G7*C7 =G19-100*G7 8 6 32 2 0.062 9.8 6 1 =G8*C8 =G20-100*G8 9 7 34 2 0.071 11.53 5 1 =G9*C9 =G21-100*G9 10 8 36 2 0.060 8.37 4 1 =G10*C10 =G22-100*G10 11 9 38 3 0.059 7.2 9 0 =G11*C11 =G23-100*G11 12 10 40 3 0.056 7.07 6 0 =G12*C12 =G24-100*G12 13 Заводы-потребители - объемы 14 Поставщи

ки 1 2 3 4 5 Объемы поставок Огранич 15 1 - - - - 0.0 - =СУММ(B15:F15)-G15 16 2 - 21.8 - 8.2 - 30.0 =СУММ(B16:F16)-G16 17 3 - 3.2 - 6.8 - 10.0 =СУММ (B17:F17)-G17 18 4 - - - - - - 0.0 =СУММ(B18:F18)-G18 19 5 - - - - 10.0 10.0 =СУММ(B19:F19)-G19 20 6 - - 16.0 - 10.0 26.0 ^yMM(B20:F20)-G20 21 7 18.0 - - - - 18.0 =СУMM(B21:F21)-G21 22 8 - - 14.0 - - 14.0 =СУMM(B22:F22)-G22 23 9 0.0 - - - - - =СУMM(B23:F23)-G23 24 10 - - 0.0 - - 0.0 =СУMM(B24:F24)-G24 25 Заказы 18 25 30 15 20 Индекс ненадежности Реально Д/Б 26 Ограниче

ния =СУММ(

B15:B24)

B25 =СУММ(

C15:C24)

C25 О О и

21

:У

D М2 М :E У 55 С 12 =EE М2 М :F У 5:5 С 12 =FF =СУММПРОИЗВ^

15:G24;F3:F12)/СУ

MM(B25:F25) 4 27 min % ИК 5.00% 5.00% 5.00% 7.00% 7.00% 28 Реальный % ИК =СУММПРОИЗВ(В15:В24ДО$3ДО$12)/

B25 =СУММП

РОИЗВ^ =СУММ(329;Э30;Э

31) Полная себестоимость 29 себестои

м. 20 18 16 22 20 =СУММПРОИЗВ(В

15:Р24;Б34:Р43) Стоимость перевозки 30 K %ИК 1.50 1.20 1.20 1.00 1.00 =СУММПРОИЗВ(В

31:Р31;В25:Р25) Стоимость производства 31 Себесто

имость =B29*(1-

B30*(B28

B27)/B27

) =C29*(1-

C30*(C28

C27)/C27

) =D29*(1-

D30*(D28

D27)/D27

) =E29*(1-

E30*(E28

E27)/E27

) =F29*(1-

F30*(F28-

F27)/F27) =СУММПРОИЗВ(Э

15:Э24;Е3:Е12) Стоимость закупки 32 Заводы-потребители - цены перевозок Здрав. смысл Дельта 33 Поставщи 1 2 3 4 5 34 1 24.2 17.6 25.8 24.2 18.8 =Э28 4 449.8 =(H34-G28)/H34 35 2 28.8 9.6 11.8 10.2 15.6 =Э29 1 738.8 =(H35-G29)/H35 36 3 15 7.8 21.8 8.2 11 =Э30 1 672.4 =(H36-G30)/H36 37 4 23.2 17.4 25.4 19.8 26.2 =Э31 1 038.6 =(H37-G31)/H37 38 5 23.6 20.2 22.6 20.4 14.6 39 6 14.2 8.2 9.4 15.8 8.4 40 7 12 16.2 19.2 18.2 19 41 8 15.8 19 12.6 24 21.2 42 9 11.4 20.2 16.6 25.4 22.2 43 10 21.4 20.2 16.6 25.4 22.2 Рис. 108

В качестве переменных решения выступают 50 значений объемов перевозок от 10 потенциальных поставщиков к 5-ти заводам компании (ячейки В15:Б24), 10 значений объемов закупок у каждого из 10-ти потенциальных поставщиков (ячейки 015:024), а также 10 двоичных переменных типа «выбрать данного поставщика или не выбирать» (ячейки 03:012), назначение которых было подробно рассмотрено в анализе действия 1.

Формулы в ячейках Н3:Н12, выражающие минимально возможный объем закупок у каждого поставщика, и ячейках 13:112, выражающие связь между объемами закупок и двоичными переменными «выбрать поставщика или не выбирать», также как и формула для средневзвешенного индекса надежности

поставок (ячейка Н26), подробно рассматривались при анализе плана закупок в действии 1.

Формулы в ячейках Н15:Н24, выражающие требования поставщиков, и в ячейках Б26:Б26, выражающие требования по заказам заводов-потребителей, также как и формулы для средневзвешенного %ИК в руде, доставленной на каждый завод (ячейки Б28:Б28), подробно обсуждались при анализе плана перевозок в действии 1.

Целевая функция, равная сумме трех издержек (закупки, перевозки и переработки), введена в ячейке Ь3. Издержки закупки сырья (ячейка Ь9) и его перевозки от поставщиков к заводам-потребителям (ячейка Ь5) рассматривались при анализе действия 1 кейса. Издержка переработки (ячейка Ь7) определена как сумма произведений объемов сырья, заказанных каждым заводом, на себестоимость переработки сырья каждым заводом, которые зависят от средневзвешенного процентного содержания ИК, доставленного каждому заводу. Последние вычислялись по формуле 1 (ячейки Б31:Б31).

1Ш

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

Поиск решения Закрыть

Є^іпоіиить

Установить целевую ячейку; |13Ц Равной: ' максимальному значению

* мннммальнону значению Изменяя ячейки: Параметры

| $ <3$3:|Є$ 12; 13: $Є$Ї4; $ в$ 15:$Р$24 V Предіолоиаїть | Ограничения: Добавить

Изменить

Восстановить

Удалить

Справка

№б:$Р|26-0

|В|28:|Р|23 >= $В$27:ІР$27 М 15:^24 <- $В$3:|Є|12 $й$15:$й$24 >= $Н$ЗІН$12 Ій$3:^12 = леоичное $Н|15:$Н|24=0 <= О

Іііге <=

Рис. 109

Оптимальное решение для интегрированного плана цепочки поставок представлено на Рис. 110.

Видно, что суммарные издержки по закупке, перевозке и переработке руды, уменьшились по сравнению с планированием по «здравому смыслу» почти на 15%, что при огромных оборотах компании НАД!ПРОДУКТ выражается весьма значительной суммой, превышающей $700 млн. При этом издержки перевозки сократились на 34%, а издержки переработки - на 18%, за счет возрастания издержек закупки на 23%. Выбраны другие поставщики, закуплено сырье с более высоким содержанием ИК. При этом высококачественное сырье доставлено не только на заводы №№4,5, но и на заводы №№1,2, что существенно снизило стоимость переработки. Разумеется, при выборе поставщиков должным образом учтены транспортные издержки. А В С 0 Е ? С Н I 1 Оптимальный интегрированный план в цепочке поставок НАЦ ПРОДУК 2 Поставщики Мах Міп % ИК Цена Индекс Брать/ не брать Мин.

закупка Связь 3 1 16 1 0.060 7.5 4 0 0 0.0 4 2 30 1 0.080 15.8 2 1 1 -70.0 5 3 24 1 0.058 7.53 6 1 1 -90.0 6 4 28 1 0.053 7.1 8 0 0 0.0 7 5 20 2 0.078 14.8 1 1 2 -90.0 8 6 32 2 0.062 9.8 6 1 2 -74.0 9 7 34 2 0.071 11.53 5 1 2 -82.0 10 8 36 2 0.060 8.37 4 1 2 -86.0 11 9 38 3 0.059 7.2 9 0 0 0.0 12 10 40 3 0.056 7.07 6 0 0 0.0 13 Заводы-потребители - объемы 14 Поставщики 1 2 3 4 5 Объемы

поставок Огранич 15 1 - - - - 0.0 - 0.00 16 2 - 21.8 - 8.2 - 30.0 0.00 17 3 - 3.2 - 6.8 - 10.0 0.00 18 4 - - - - - - 0.0 0.00 19 5 - - - - 10.0 10.0 0.00 20 6 - - 16.0 - 10.0 26.0 0.00 21 7 18.0 - - - - 18.0 0.00 22 8 - - 14.0 - - 14.0 0.00 23 9 0.0 - - - - - 0.00 24 10 - - 0.0 - - 0.0 0.00 25 Заказы 18 25 30 15 20 Индекс ненадеж ности Реально Д/Б 26 Ограниче-ния 0.00 0 0 0 0 4 4 27 т1п % ИК 5.00% 5.00% 5.00% 7.00% 7.00% 28 Реальный % ИК 7.10% 7.72% 6.11% 7.00% 7.00% 3 795.2 Полная

себестоимость 29 Мах

себестоим. 20 18 16 22 20 1 146.4 Стоимость

перевозки 30 К %ИК 1.50 1.20 1.20 1.00 1.00 1 372.0 Стоимость

производства 31 Себесто

имость 7.40 6.25 11.75 22.00 20.00 1 276.8 Стоимость закупки 32 Заводы-потребители - цены перевозок Здрав.

смысл Дельта 33 Поставщики 1 2 3 4 5 34 1 24.2 17.6 25.8 24.2 18.8 3 795.2 4 449.8 15% 35 2 28.8 9.6 11.8 10.2 15.6 1 146.4 1 738.8 34% 36 3 15 7.8 21.8 8.2 11 1 372.0 1 672.4 18% 37 4 23.2 17.4 25.4 19.8 26.2 1 276.8 1 038.6 -23% 38 5 23.6 20.2 22.6 20.4 14.6 39 6 14.2 8.2 9.4 15.8 8.4 40 7 12 16.2 19.2 18.2 19 41 8 15.8 19 12.6 24 21.2 42 9 11.4 20.2 16.6 25.4 22.2 43 10 21.4 20.2 16.6 25.4 22.2 Рис. 110

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

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

сравнению с ситуацией, которая могла бы иметь место в реальности. Во-первых, мы рассматривали величины валовых годовых закупок и перевозок. В реальности, необходимо было бы составить многопериодный план закупки и поставки сырья, скажем, на каждую неделю, для каждого поставщика и потребителя на год. Во- вторых, мы рассматривали некоторую интегральную, средневзвешенную характеристику надежности поставок в целом. В реальности, следовало бы позаботиться об обеспечении надежности поставок на каждый завод, в каждый планируемый период. При этом, помимо качественной экспертной оценки надежности поставщика, полезно было бы использовать количественные характеристики надежности, например, величины вариации времени поставки и качества сырья. Это потребовало бы расчета и создания резервных запасов сырья на каждом заводе (см. [2-6] и задачи раздела 2.1 настоящего сборника). В-третьих, учитывая огромный объем поставок сырья, при его перевозке наверняка бы возникли проблемы, связанные с ограничениями мощностей транспортных средств и учетом условно-постоянных издержек при их использовании и т. д. и т. п. Все это, без сомнений, резко увеличило бы количество переменных в оптимизационной модели. Естественно возникает вопрос, возможно ли получить интегральный план цепочки поставок, подобный рассмотренному в настоящем примере, для реальной компании тех же масштабов, что и НАЦПРОДУКТ?

Прежде всего, отметим, что современные оптимизационные инструменты позволяют решать задачи с количеством переменных до 1 млн. на обычном переносном компьютере. Используемый для решения задач в этом сборнике Поиск решения, созданный компанией Frontline systems в 1991г., и называемый Standard Solver, способен справиться с задачами, в которых не более 200 переменных. Современный общедоступный продукт этой компании Premium Solver позволяет рассматривать задачи с количеством переменных решения до 2000. Эта же компания предлагает специальные Solver’ы, с «мощностью» до 1 млн. переменных. Существуют и другие профессиональные оптимизационные инструменты с «мощностями» такого же порядка. Информацию о них можно найти на сайтах -

www.solver.com -

www.maximalsoftware.com -

www.cplex.com -

www.ilog.com

В специальной литературе имеются сведения о внедрении в управленческую практику оптимизационных моделей с количеством переменных

от нескольких тысяч до сотен тысяч (см., например Interfaces ,

конференция INFORMS 2004 ). При этом,

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

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

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

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

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

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

П-9. Фирма «Хороший хозяин»

Фирма «Хороший хозяин» имеет сеть из 12 магазинов бытовых инструментов и оборудования в крупном городе. Все магазины снабжаются одним складом. Доставка осуществляется одной автомашиной, принадлежащей фирме, и проводится раз в два дня. При этом на складе формируется груз, который всегда можно развезти за одну ездку. Автомашина забирает его со склада и развозит по магазинам, объезжая их по очереди.

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

км Б 1 2 3 4 5 6 7 8 9 10 11 12 База 5 8 6 35 9 13 27 23 19 14 20 20 Маг. № 1 5 13 5 37 14 18 28 28 24 19 21 25 Маг. № 2 8 13 9 39 7 8 33 17 12 9 26 20 Маг. № 3 6 5 9 40 13 16 32 26 21 17 25 26 Маг. № 4 35 37 39 40 32 34 12 37 37 33 17 21 Маг. № 5 9 14 7 13 32 4 28 15 10 5 22 14 Маг. № 6 13 18 8 16 34 4 31 10 6 1 25 14 Маг. № 7 27 28 33 32 12 28 31 37 36 30 7 22 Маг. № 8 23 28 17 26 37 15 10 37 5 9 33 16 Маг. № 9 19 24 12 21 37 10 6 36 5 6 30 16 Маг. № 10 14 19 9 17 33 5 1 30 9 6 25 12 Маг. № 11 20 21 26 25 17 22 25 7 33 30 25 18 Маг. № 12 20 25 20 26 21 14 14 22 16 16 12 18 a. Сформулируйте задачу линейной оптимизации, которая позволяет найти самый короткий по общей протяженности маршрут для автомашины, позволяющий объехать все 12 магазинов. Никаких ограничений на порядок объезда магазинов нет. Машина должна выехать со склада и на него же вернуться. b.

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

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

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

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

Для начала смело заверим читателя, что сформулировать такую задачу можно! Такая уверенность сильно помогает при решении.

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

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

Вместо этого можно попробовать просто составить табличку 13х13 переменных, соответствующую таблице расстояний (база и 12 магазинов) и расставить в этой табличке 13 единиц, которые будут показывать, какие переезды между магазинами выбраны. Если теперь применить функцию =СУММПРОИЗВ( ) к этим двум таблицам, то мы сразу получим общее расстояние, которое проехал грузовик. Таким образом задача линейной целочисленной оптимизации практически составлена (Рис. 111). A B C D E F G H I J K L M N O P 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12 3 0 База ## 5 8 6 35 9 13 27 23 19 14 20 20 =СУММПРОИЗВ(

C3:03;C18:018) 4 1 Мг 1 5 ## 13 5 37 14 18 28 28 24 19 21 25 0 5 2 Мг 2 8 13 ## 9 39 7 8 33 17 12 9 26 20 0 6 3 Мг 3 6 5 9 ## 40 13 16 32 26 21 17 25 26 0 7 4 Мг 4 35 37 39 40 ## 32 34 12 37 37 33 17 21 0 15 12 Мг 12 20 25 20 26 21 14 14 22 16 16 12 18 ## 0 16 0 17 0 1 2 3 4 5 6 7 8 9 10 11 12 18 База =СУММ(С 18:018) 19 Мг 1 0 20 Мг 2 0 21 Мг 3 I 1ер ;ме ннь [Є 0 22 Мг 4 0 30 Мг 12 0 31 0 0 0 0 0 0 0 0 0 0 0 0 =СУММ(018:030) Рис. 111

Однако здесь нас также поджидает глубокое разочарование. Дело в том, что чаще всего предлагаемый Поиском решения маршрут не является кольцевым. / Vi / № г 11 * Мг 12 Бс ю S * Мг 5 1 Mr 1 Мг 6

1 1 \ Мг 2 т/мг з 1 О 5 10 15 20 25 30 35

Рис. 112

Т.е. какая-то часть маршрута действительно соответствует выезду из базы, посещению нескольких магазинов и возвращению назад - База-> Магазин №3 -> Магазин №1-> База. Но большая часть предложенного маршрута имеет вид: Мг 2 -> Мг 5-> Мг 2, или Мг 7 -> Мг 11 -> Мг 7 (Рис. 113 и Рис. 112). 0 1 2 3 4 5 6 7 8 9 10 11 12 0 База ## 5 8 6 35 9 13 27 23 19 14 20 20 5 1 Мг 1 5 ## 13 5 37 14 18 28 28 24 19 21 25 5 2 Мг 2 8 13 ## 9 39 7 8 33 17 12 9 26 20 7 3 Мг 3 6 5 9 ## 40 13 16 32 26 21 17 25 26 6 4 Мг 4 35 37 39 40 ## 32 34 12 37 37 33 17 21 21 5 Мг 5 9 14 7 13 32 ## 4 28 15 10 5 22 14 7 6 Мг 6 13 18 8 16 34 4 ## 31 10 6 1 25 14 1 7 Мг 7 27 28 33 32 12 28 31 ## 37 36 30 7 22 7 8 Мг 8 23 28 17 26 37 15 10 37 ## 5 9 33 16 9 Мг 9 19 24 12 21 37 10 6 36 5 ## 6 30 16 10 Мг 10 14 19 9 17 33 5 1 30 9 6 ## 25 12 1 11 Мг 11 20 21 26 25 17 22 25 7 33 30 25 ## 18 7 12 Мг 12 20 25 20 26 21 14 14 22 16 16 12 18 ## 21 98 0 1 2 3 4 5 6 7 8 9 10 11 12 База 0 1 0 0 0 0 0 0 0 0 0 0 0 1 Мг 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 Мг 2 0 0 0 0 0 1 0 0 0 0 0 0 0 1 Мг 3 1 0 0 0 0 0 0 0 0 0 0 0 0 1 Мг 4 0 0 0 0 0 0 0 0 0 0 0 0 1 1 Мг 5 0 0 1 0 0 0 0 0 0 0 0 0 0 1 Мг 6 0 0 0 0 0 0 0 0 0 0 1 0 0 1 Мг 7 0 0 0 0 0 0 0 0 0 0 0 1 0 1 Мг 8 0 0 0 0 0 0 0 0 0 1 0 0 0 1 Мг 9 0 0 0 0 0 0 0 0 1 0 0 0 0 1 Мг 10 0 0 0 0 0 0 1 0 0 0 0 0 0 1 Мг 11 0 0 0 0 0 0 0 1 0 0 0 0 0 1 Мг 12 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Рис. 113

Разумеется, это вовсе не решение исходной задачи.

Если бы проблема была бы только в маршрутах вида Мг 7 -> Мг 11 -> Мг 7, ее легко было бы устранить. В самом деле, при наличии таких маршрутов в полученном решении соответствующие элементы таблицы переменных оказываются симметричными относительно диагонали С18-030. Например, единица, показывающая наличие перевозки, стоит и в ячейке 129 (переезд из Мг 7 в Мг 11), и в ячейке N25 (переезд из Мг 11 в Мг 7), симметричной ячейке 129 относительно диагонали таблицы переменных.

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

Это, правда, не делается простым протягиванием. А в задании для «Поиска решения» добавим условие, что все эти суммы меньше или равны 1. Это исключит возвратные маршруты.

После этого запустим надстройку Поиск решения на выполнение и опять проанализируем полученное решение (в таблице на Рис. 114 приведено только 109 0 1 2 3 4 5 6 7 8 9 10 11 12 База 0 0 0 1 0 0 0 0 0 0 0 0 0 1 Кл 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 Кл 2 0 0 0 0 0 0 0 0 0 1 0 0 0 1 Кл 3 0 1 0 0 0 0 0 0 0 0 0 0 0 1 Кл 4 0 0 0 0 0 0 0 0 0 0 0 1 0 1 Кл 5 0 0 1 0 0 0 0 0 0 0 0 0 0 1 Кл 6 0 0 0 0 0 1 0 0 0 0 0 0 0 1 Кл 7 0 0 0 0 1 0 0 0 0 0 0 0 0 1 Кл 8 0 0 0 0 0 0 0 0 0 0 0 0 1 1 Кл 9 0 0 0 0 0 0 0 0 1 0 0 0 0 1 Кл 10 0 0 0 0 0 0 1 0 0 0 0 0 0 1 Кл 11 0 0 0 0 0 0 0 1 0 0 0 0 0 1 Кл 12 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Рис. 114

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

Анализ полученного решения (Рис. 114 и Рис. 115) показывает, что и на этот раз решение не может нас устроить. Получилось три цикла, вместо одного.

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

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

Придется пойти сложным путем, в частности оказывается, что при этом необходимо использование более продвинутой модели надстройки Поиск решения под названием Large-Scale LP Solver. Эту продвинутую надстройку можно найти на сайте компании-создателя этого инструмента FrontLine System www.solver.com. Надстройку можно скачать бесплатно и пользоваться ею в течение двухнедельного пробного срока.

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

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

В первый магазин маршрута объезда автомобиль должен прибыть с базы.

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

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

Таким образом на первом шаге мы выбираем 1 из 12 магазинов, в который поедем с базы (склада), т.е. имеем 12 переменных.

На втором шаге выбираем второй пункт маршрута. Так как мы поедем из выбранного на первом шаге магазина (1 из 12) в другой магазин (вообще говоря тоже 1 из 12, так как заранее неизвестно, какой магазин посещен первым), но не на базу, то для выбора второго пункта посещения необходимо выбрать одно направление поездки из 144 (=12*12) возможных. При этом после выбора нужно будет проверить, что выбор «откуда» прибыл, совпадает с выбором «куда» прибыл, сделанным на предыдущем шаге.

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

На последнем тринадцатом шаге мы должны вернуться на базу. Для этого нужно выбрать пункт «откуда» автомобиль туда вернется. Это необходимо для вычисления длины маршрута возвращения. Это добавит к задаче еще 12 переменных. Итого получаем 12 + 11* 12*12 + 12 = 1608 переменных.

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

В новой таблице (Рис. 116) приведен пример организации данных для нашей задачи.

В ячейках Б36:0168 и С169:С180 содержатся переменные задачи. В данном случае единица в ячейке Б36 строки Б36:036 показывает, что первым пунктом посещения после отправления с базы является Мг 1. При этом строка Б21:021 просто дублирует строку Б36:036, а в ячейке Я21 по формуле =СУММПРОИЗВ ($Б$1:$0$1; Б21:021) вычисляется номер посещенного магазина. А В С Б Е Б О Н I 1 к ь м N о Р К 1 0 1 2 3 4 5 6 7 8 9 10 11 12 2 0 База ## 5 8 6 35 9 13 27 23 19 14 20 20 3 1 Мг 1 5 ## 13 5 37 14 18 28 28 24 19 21 25 4 2 Мг 2 8 13 ## 9 39 7 8 33 17 12 9 26 20 Таблица 5 3 Мг 3 6 5 9 ## 40 13 16 32 26 21 17 25 26 взаимных 6 4 Мг 4 35 37 39 40 ## 32 34 12 37 37 33 17 21 расстояний, км. 7 5 Мг 5 9 14 7 13 32 ## 4 28 15 10 5 22 14 8 6 Мг 6 13 18 8 16 34 4 ## 31 10 6 1 25 14 9 7 Мг 7 27 28 33 32 12 28 31 ## 37 36 30 7 22 10 8 Мг 8 23 28 17 26 37 15 10 37 ## 5 9 33 16 11 9 Мг 9 19 24 12 21 37 10 6 36 5 ## 6 30 16 12 10 Мг 10 14 19 9 17 33 5 1 30 9 6 ## 25 12 13 11 Мг 11 20 21 26 25 17 22 25 7 33 30 25 ## 18 14 12 Мг 12 20 25 20 26 21 14 14 22 16 16 12 18 ## 15 Расстояния между пунктами маршрута, км Всего км. 16 5

5 9 7 4 1 6 5 16 21 12 7 20 118 17 0 =И21 2 0 0 0 0 0 0 0 0 0 =К33 18 1 19 1 1 1 1 1 1 1 1 1 1 1 1 =СУММ(036:0180) 20 21 1 1 0 0 0 0 0 0 0 0 0 0 0 V 1 1 22 2 0 1 0 0 0 0 0 0 0 0 0 1 3 X 23 3 0\ 1 0 0 0 0 =СУММ(Б36:036) / 1 1 ,2/ 24 4 0 \ 0 0 1 / 0 =СУММПРОИЗВ($Б$0:$0$1 ;Б21:021) 25 5 0 \° 0 1 0 26 6 0 0 =СУММ(Б36:Б48) ) 0 1 0 0 1 1 0 27 7 0 0 ) 1 0 0 0 1 1 0 28 8 0 - ?0 0 0 0 0 1 1 0 29 9 0 0 С У ММ 1(Б1 09:Б ->120 0 0 0 1 1 1 0 30 10 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 31 11 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 32 12 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 33 13 1 1 1 0 34 35 0 1 2 3 4 5 6 7 8 9 10 11 12 36 0 1 1 0 0 0 0 0 0 0 0 0 0 0 =СУММ

(Б36:036) 37 1 2 0 0 1 0 0 0 0 0 0 0 0 0 1 38 2 0 0 0 0 0 0 0 0 0 0 0 0 0 39 3 0 0 0 0 0 0 0 0 0 0 0 0 0 48 12 0 0 0 0 0 0 0 0 0 0 0 0 0 49 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 157 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 163 7 0 0 0 0 0 0 0 0 0 0 1 0 1 168 12 0 0 0 0 0 0 0 0 0 0 0 0 =СУММ

(Б168:0168) 169 1 13 0 =С169 170 2 0 =С170 179 11 1 1 180 12 0 0 Рис. 116

Выбор второго пункта посещения делается в ячейках 037:048. Единица в ячейке Б37 показывает, что вторым пунктом выбран Мг 3 (см. номер магазина по этому же столбцу, в котором стоит 1, в ячейке Б35). При этом ссылку на номер предыдущего магазина смотрим по этой же строке в ячейке А37. В столбце

P36:P168 считаются суммы по строкам переменных. Эти суммы позволяют с одной стороны задать ограничение на выбор только одного пункта назначения на каждом шаге, а с другой стороны формируют очень нужные нам данные. В самом деле, так как номер строки в соответствии с нумерацией в столбце А показывает, из какого пункта прибыл автомобиль, то столбец P37:P48 должен совпадать со строкой D21:O21. Как вы видите, так оно и есть. Но главное, что этого можно потребовать при поиске решения (в данной, более продвинутой, версии Поиска решения можно сравнивать строки и столбцы)!

В строке D22:O22 вычисляются суммы по столбцам от D37:D48 до 037:048, также подытоживающие результаты выбора на втором шаге, для использования их на шаге третьем. Т.е. в строке D22:022 показано, какой магазин был выбран на втором шаге. Непосредственно для лучшего представления результатов в ячейке R22 по той же формуле =СУММПРОИЗВ ($D$1:$O$1; D22:O22) вычисляется номер посещенного магазина.

Выбор третьего пункта посещения делается в ячейках D49:060. Снова суммы в столбце P49:P60 должны совпадать со значениями в строке D22:022, показывающей второй пункт посещения.

В общем эта процедура построения таблицы продолжается до выбора 13 пункта без изменений. Как уже отмечалось выше на тринадцатом шаге нужно вернуться в базу, поэтому пункт назначения определен. Для «выбора» предыдущего пункта используем 12 переменных: C169:C180. Собственно говоря, прочие соотношения остаются теми же, только в некоторых местах надобность в суммировании отсутствует, т.к. в сумме имеется только одно слагаемое. Значения ячеек в столбце P169:P180 должны совпасть со значениями в строке D32:032, что также нужно будет задать в списке ограничений Large-Scale LP Solver’а. Для того, чтобы каждый магазин был выбран в качестве пункта назначения только 1 раз, используются результаты расчетов в ячейках C 19:019. Очевидно следует потребовать, чтобы суммы всех переменных по столбцам равнялись 1, что соответствует выбору каждого магазина один и только один раз.

Чтобы выбрать каждый магазин только 1 раз в качестве предыдущего пункта посещения используем результаты суммирования в столбце Q21:Q33. В каждой из этих ячеек найдены суммы ячеек соответствующие выбору: Мг 1 на шагах 2, 3, 4...12, Мг 2 на шагах 2, 3, 4...12 и т.д. до Мг 12. Если потребовать, чтобы Q21:Q33 = 1, каждый магазин выступит в качестве предыдущего пункта посещения один и только один раз.

Ну и наконец, самое главное - расчет расстояний. Собственно говоря, мы ведь и вводили такое большое количество переменных именно для того, чтобы в каждом пункте легко вычислять, откуда приехали. Поэтому отдельные таблицы переменных для каждого из пунктов посещения дают при умножении на нужную часть таблицы расстояний C2:014 расстояние очередной поездки. Например в C16 по формуле =СУММПР0ИЗВ($C$2:$0$2;$C36:$036) вычислено расстояние от базы до первого пункта посещения. В ячейках D16:016 по другой формуле вида =СУММПР0ИЗВ($C$3:$0$14;$C37:$048) вычислено расстояние от первого пункта посещения до второго, от второго до третьего и т. д.

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

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

SP5KE:SP$?Sq = SDS30:SOS30 SPSlS7:SPSlflS - 5DS31:SOS31 S??l6S;S???S0 - SD?32:'OS32 РЗДРвЭ - l

5^S3?:5PS43 = ?DslUEQ?ll SPS*?;??SW = SO?’::?O?22 SPS6l:5PS72 - ?DS23:SO?23 P*7^S??$- - ?>324:10524 SPS5S:S?S96 • SOS2S:SO?2S SPS97;?PS108 - SDS2?:SG?25 SQS2l:SQS33 = I

Рис. 117

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

Так же желательно установить большую точность при поиске решения на вкладке Options (Рис. 118)

17 [Assume Non-Negative Crash Artificial Variables Show Iteration Results Bypass Solver Reports

Scaling c~' None Row Only (* Row StCol

Max lime: Iterations: Coeff Toi: Solution Toi: Pivot Toi: Reduced Toi:

Large-Scale LP Solver Options [Т т 1000 seconds OK 1000 Cancel 0.00000001 Integer Options... 0.00001 Load Model... 0.000001 Save Model... 0.0001 Help

Если теперь запустить поиск решения, то спустя 1-3 минуты, в зависимости от мощности процессора, получим то решение, которое и показано в табличке: минимальная длина маршрута 118 км, порядок пунктов посещения - База (0) 1 3 2 5 6 10 9 8 12 4 7 11 База (0) Как вы можете убедиться, это решение отличается от предыдущих вариантов большей длиной. На Рис. 119 приведено изображение оптимального маршрута поездки автомобиля по магазинам.

U0

: 5 10 15 2С 25 30 35

Рис. 119

45 4:

35 30 25 20

Вопрос b.

Разумеется, чтобы ответить на этот вопрос можно было бы перестроить задачу, выбросив из всех расчетов магазин №2. Это заодно уменьшило бы число переменных.

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

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

Этого можно добиться простым способом. Изменим таблицу расстояний так, чтобы места магазина №2 и базы на карте поездок совпадали. Для этого зададим расстояния от магазина №2 до всех пунктов, такими же, как от базы. А расстояние от базы до самого магазина сделаем нулевым. Изменения, которые нужно внести в таблицу расстояний, показаны на Рис. 120. A B C D E F G H I J K L M N O P Q R 1 0 1 2 3 4 5 6 7 8 9 10 11 12 2 0 База ## 5 0 6 35 9 13 27 23 19 14 20 20 3 1 Мг 1 5 ## 5 5 37 14 18 28 28 24 19 21 25 4 2 Мг 2 0 5 ## 6 35 9 13 27 23 19 14 20 20 Таблица 5 3 Мг 3 6 5 6 ## 40 13 16 32 26 21 17 25 26 взаимных 6 4 Мг 4 35 37 35 40 ## 32 34 12 37 37 33 17 20 расстояний, км. 7 5 Мг 5 9 14 9 13 32 ## 4 28 15 10 5 22 14 8 6 Мг 6 13 18 13 16 34 4 ## 31 10 6 1 25 14 9 7 Мг 7 27 28 27 32 12 28 31 ## 37 36 30 7 22 10 8 Мг 8 23 28 23 26 37 15 10 37 ## 5 9 33 16 11 9 Мг 9 19 24 19 21 37 10 6 36 5 ## 6 30 16 12 10 Мг 10 14 19 14 17 33 5 1 30 9 6 ## 25 12 13 11 Мг 11 20 21 20 25 17 22 25 7 33 30 25 ## 18 14 12 Мг 12 20 25 20 26 21 14 14 22 16 16 12 18 ## Рис. 120

Так как маршрут начинается с базы и заканчивается базой, то в оптимальном маршруте магазин №2 окажется либо первым, после выезда, либо последним из посещенных. Чтобы упростить выбор маршрута для Large-Scale LP Solver’а, можно добавить в список ограничений одно простое условие: R21 = 2. Таким образом мы потребуем, чтобы фиктивный заезд в магазин №2 был сделан сразу после выезда с ^ базы. При этом маршрут будет следующим:

База (0)

Общая длина такого минимального маршрута составит 112 км.

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

3

База

(0)

1

11

7

4

12

8

9

10

6

5