Часть 2. Транспортные задачи и логистика; задачи о назначениях и отборе.

Теоретические замечания.

Представление о том, что такое транспортная задача, у специалиста по исследованию операций и у менеджера отдела логистики очень сильно отличаются. С точки зрения менеджера, транспортные задачи - это любые задачи, связанные оптимизацией перевозок. Именно по этому принципу мы и собрали задачи и кейсы в раздел «Логистика». С точки зрения специалиста по исследованию операций, транспортная задача - это специальный вид задачи линейной оптимизации, для которой, в силу ее формулировки и в виду очень специальных ограничений, существуют исключительно эффективные алгоритмы решения. В этот тип попадают и такие реальные задачи, в которых ничего никуда не перевозится (примерами таких задач являются задачи 1.32, 2.1, 11.6 и 11.7, включенные в настоящий сборник).

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

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

При постановке транспортной задачи необходимо прежде всего задать таблицу транспортных издержек для перевозок единицы груза c (см )от i-го поставщика к у-му потребителю. Эта таблица имеет m строк (по числу поставщиков) и n столбцов (по числу потребителей).

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

D).

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

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

Наконец, чтобы получить целевую функцию (суммарные издержки), необходимо рассмотреть суммы произведений каждой строки таблицы транспортных издержек на соответствующую строку таблицы перевозок и сложить их, суммируя по i от 1 до т. Это и даст двойную сумму, показанную на . При этом номер источника ( поставщика), 1< i <m, номер пункта назначения (потребителя), 1< j <n.

( с и 11 С12 . С > V1n (x11 x12 . x > • X1n (S ^ = С21 С22 . . С2 2 n , D) = Х21 x22 . . x2n , (S,) = S2 V Ст1 Ст2 . . С ) mn у V xm1 xm2 . . x mn У m J

Dj =(D„ A.....Dn) n m X(xv ~Si)=0 X(xv ~Di)=0, i = 1,2,...m, j = 1,2,...n j=1 i=1 m n Min: C=XXxc i=1 j=1

Рис. 64

Если задача сбалансирована и никаких других ограничений, кроме упомянутых выше нет, Поиск решения использует эффективный алгоритм решения для этой задачи, причем, если запасы и заказы выражены целыми числами, то и переменные решения xij получатся целыми, даже если не требовать этого специально. Кроме того, гарантировано, что количество ненулевых перевозок x_ij не будет превышать m+n-1, т.е.количество «игроков» (поставщиков и потребителей) минус 1.

Несбалансированность в транспортной задаче

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

В первом случае,

m n

Z s.>Z D,.

i=1 j=1

нужно добавить в таблицу транспортных издержек и в таблицу перевозок по одному лишнему столбцу.

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

D„„ = Z S,-Z D,,

1=1 j=1

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

Во втором случае, когда

m n

Z ^S,<Z ^D,.

1=1 j=1

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

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

nm

Sf„,=Z Dj-Z Si,

,=1 1=1

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

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

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

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

Подробнее о постановке и методах решения транспортной задачи читайте в учебных пособиях [1,2,7-11].

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

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

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

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

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

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

Подробнее о задаче о назначениях читайте в учебных пособиях [1,2,7-11].

Задачи оптимизации логистики и цепочек поставок.

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

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

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

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

2.П-1. Дорстрой

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

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

	Участок A	Участок B	Участок C	Участок D	Участок E
АБЗ 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

Заказы дорожно-строительных бригад на завтра:

Участок A Участок B Участок C Участок D Участок E Количество машин 79 28 61 77 72

Заводы в состоянии предоставить завтра,

Источник АБЗ 16 АБЗ 17 АБЗ 18 АБЗ 19 АБЗ 20 АБЗ 21 Кол-во машин 65 46 52 29 28 67

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

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

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

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

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

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

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

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

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

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

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

	A	B	C	D	E	F	G
1		Участок A	Участок B	Участок C	Участок 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	^УММПРОИЗВ^: F8;B12:F18)
10
11		Участо к A	Участо к B	Участо к C	Участо к D	Участо к E	Контроль отгрузки
12	АБЗ 16						СУММ^ПЕП)- G2
13	АБЗ 17						СУММ^ВЕВ)- G3
14	АБЗ 18						СУММ^МЕМ)- G4
15	АБЗ 19						СУММ^ИЕИ)- G5
16	АБЗ 20						СУММф^Е^)- G6
17	АБЗ 21						СУММ^ПЕП)- G7
18	АБЗ Х						СУММф^Е^)- G8
19	Контроль выполнен ия заказов	=СУМ М^12: B18)- B9	=СУМ М(02: C18)- C9	=СУМ Мф12: D18)- D9	=СУМ М^12: E18)-E9	=СУМ М^12: F18)-F9

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

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

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

Вызываем надстройку Поиск решения и ставим задачу. Целевая ячейка -G9, цель - минимум издержек. Изменяемые ячейки - таблица перевозок B12:F18. Параметры решения - линейная модель и неотрицательные значения переменных. Ограничения - B19:F19=0 и G12:G18=0. Жмем кнопку Выполнить и получаем, если вы нигде не ошиблись, сообщение, что решение найдено ().

Участок A Участок B Участок C Участок D Участок E Планируется отгрузить АБЗ 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 Участо к A Участо к B Участо к C Участо к D Участо к E Контроль отгрузки АБЗ 16 4 0 61 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 АБЗ Х 30 0 0 0 0 7.0E-11 Контроль выполнен ия заказов -2.6E- 09 6.53E- 11 -2E-09 -2.6E- 09 -2.4E- 09

Рис. 66

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

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

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

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

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

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

Требуемое кол-во 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

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

D.

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

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

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

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

Клиент X Клиент Y Клиент Z Клиент W A B A B A B A B База 1 A 595 480 455 430 B 780 665 640 815 База 2 A 435 530 480 485 B 735 735 680 585 База 3 A 545 465 525 440 B 715 755 815 795

Клиенты заказывают следующие количества товаров A, B.

Клиент X Клиент Y Клиент Z Клиент W A B A B A B A B Заказы, шт. 15 20 22 26 12 22 32 42

На базах же в настоящий момент имеются следующие запасы товара:

	База 1	База 2	База 3
	A	B	A	B	A	B
Запасы, шт.	21	21	33	42	17	57

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A B С 1 D Е 1 F G 1 H і 1 j K L 1 M N O 1 Клиент X Клиент Y Клиент Z Клиент W *** Запасы 2 A B A B A B A B B 3 База 1 A 595 9999 480 9999 455 9999 430 9999 21 4 B 9999 780 9999 665 9999 640 9999 815 21 5 База 2 A 435 9999 530 9999 480 9999 485 9999 33 6 B 9999 735 9999 735 9999 680 9999 585 42 7 База 3 A 545 9999 465 9999 525 9999 440 9999 17 8 B 9999 715 9999 755 9999 815 9999 795 57 9 *** A 10 10 Заказы 15 20 22 26 12 22 32 42 10 =СУММПРОИЗВ 11 (C3:K9;C13:K19) 12 A B A B A B A B B Запасы 13 База 1 A =СУММ(С13:К13)-Ь3 14 B =СУММ(С14:К14)-Ь4 15 База 2 A =СУММ(С15 :K15)-L5 16 B =СУММ(С16:К16)А6 17 База 3 A =СУММ(С17:К17)-Ь7 18 B =СУММ(С18:К18)А8 19 *** A =СУММ(С19:К19)-Ь9 20 =СУ =СУ =СУ =СУ =СУ =СУ =СУ =СУ =СУММ(К13:К19)-К10

Рис. 69

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

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

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

A 1 B С D Е F G H I J K L 10 Заказы 15 20 22 26 12 22 32 42 10 104 760 11 12 A B A B A B A B B Запасы 13 База 1 A 0 0 0 0 0 0 21 0 0 0 14 B 0 0 0 0 0 21 0 0 0 0 15 База 2 A 15 0 0 0 12 0 6 0 0 0 16 B 0 0 0 0 0 0 0 42 0 0 17 База 3 A 0 0 12 0 0 0 5 0 0 0 18 B 0 20 0 26 0 1 0 0 10 0 19 *** A 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, Заменить все.

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

A B С 1 D E 1 F G | H i | j K L 1 Клиент X Клиент Y Клиент Z Клиент W *** Запасы 2 A B A B A B A B B 3 База 1 A 595 -9999 480 -9999 455 -9999 430 -9999 21 4 B -9999 780 -9999 665 -9999 640 -9999 815 21 5 База 2 A 435 -9999 530 -9999 480 -9999 485 -9999 33 6 B -9999 735 -9999 735 -9999 680 -9999 585 42 7 База 3 A 545 -9999 465 -9999 525 -9999 440 -9999 17 8 B -9999 715 -9999 755 -9999 815 -9999 795 57 9 *** A 10 10 Заказы 15 20 22 26 12 22 32 42 10 122 930 11 12 A B A B A B A B B Запасы 13 База 1 A 15 0 6 0 0 0 0 0 0 0 14 B 0 14 0 0 0 0 0 7 0 0 15 База 2 A 0 0 16 0 0 0 17 0 0 0 16 B 0 6 0 26 0 0 0 0 10 0 17 База 3 A 0 0 0 0 12 0 5 0 0 0 18 B 0 0 0 0 0 22 0 35 0 0 19 *** A 0 0 0 0 0 0 10 0 0 0 20 0 0 0 0 0 0 0 0 0

Рис. 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. Определите, сколько имеется лучших, в смысле суммарного индекса, решений.

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

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

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

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

A B C D E F G H I J K L M 1 Аня Маша Катя Лиза Ольга Софья 2 Иван 3 4 9 18 9 6 1 =СУММПРОИЗВ (B2:G2;B11:G11) 3 Михаил 16 8 12 13 20 4 1 =СУММПРОИЗВ(B3:G3;B12:G12) 4 Павел 8 6 13 1 6 9 1 =СУММПРОИЗВ(B4:G4;B13:G13) 5 Николай 16 9 6 8 1 11 1 ^’УМ^^ОтВ^^^М^М) 6 Алексей 8 12 17 5 3 5 1 =СУММПРОИЗВ (B6:G6;B15:G15) 7 Петр 2 9 1 10 5 17 1 =СУММПРОИЗВ (B7:G7;B16:G16) 8 1 1 1 1 1 1 =СУММПРОИЗВ (B2:G7;B 11:G16) 9 10 Аня Маша Катя Лиза Ольга Софья 11 Иван 0 0 0 0 0 0 ^’уммшшп) 12 Михаил 0 0 0 0 0 0 ^УММ^^^П) 13 Павел 0 0 0 0 0 0 ^УММ^^^П) 14 Николай 0 1 0 0 0 0 ^УММ^М^М) 15 Алексей 0 0 0 0 0 0 ^УММ^^^^) 16 Петр 0 0 0 0 0 0 ^умм^^^^) 17 =СУМ =СУМ =СУ =СУМ =СУМ =СУММ^1Ш16)

Рис. 72

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

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

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

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

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

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

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

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

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

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

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

Суммарный индекс совместимости равен 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, то ни одно из них не имеет какого-либо преимущества.

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

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

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

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

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

	A	B	C	D	E	F	G	H	I
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) и снова попробуем решить задачу ().

	A	B	C	D	E	F	G	H	I
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!

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

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

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

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

	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	2E-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 можно предложить следующую таблицу ().

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 Гаапвилл ^УММфП^ 1)-M3 12 Финанста ун -20 13 Исабург -25 14 Нью- Баланс -10 15 Заявки =СУММ B7 1(B1 :B14)- -6 -9 -3 -18 -5 -15

Рис. 77

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

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

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

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

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

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

Конечно, это именно потому, что соответствующие назначения в случае с запретами не будут сделаны! А раз переменные в таблице снизу C14, H12 и J14 останутся равными 0, то на какое бы число мы их не умножали при расчете суммарных затрат, результата они не изменят.

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

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

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

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

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

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

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

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

Конторы Клиенты Не исп. Число сотрудников 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.9E-10, не волнуйтесь. Это число в научной форме записи, есть очень маленькая дробь - 39 деленное на сто миллиардов. Так как программа ищет решение не абсолютно точное, а приближенное, то для нее это число с приемлемой точностью уже не отличается от нуля. Часто можно получить несколько более точный результат, увеличив количество итераций во вкладке Параметры со 100 (по умолчанию) до 10000. Но можно и просто не обращать внимания на эти малые числа. Правильное решение все равно получено.

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

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

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

Заявки 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.1E-08 Финанста ун 0 3 1 0 1 5 0 1 1 1 7 7.6E-10 Исабург 1 6 0 0 0 0 1 0 17 0 0 9.5E-10 Нью- Баланс 0 0 0 1 0 1 8 0 0 0 0 3.8E-10

Рис. 79

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

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

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

Корпорация “Современные железобетонные изделия” имеет в окрестностях и черте города 5 небольших заводов ЖБИ (ЖБИ 1,ЖБИ 2, ... ЖБИ 5). Кроме этого, у корпорации есть 3 охраняемых площадки-склада (Склад A, Склад B, Склад C) для временного хранения изделий, хотя корпорация старается работать на заказ. В настоящий момент в отделе продаж имеется заказ от строительной фирмы на поставку новых ж\б блоков высокой прочности в количестве 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 блоков, реально можно складировать следующим образом: Склад A -150 шт., Склад B -150 шт. и Склад C -205 шт.

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

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

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

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

A B C D E F G H I J 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: I7;B11:I15) 9 10 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 Скл. итого 11 ЖБИ 1 ^умм^ыи)^ 12 ЖБИ 2 =СУММф12:П2) -J4 13 ЖБИ 3 ^УММф^ш) -J5 14 ЖБИ 4 =СУММф 14:I14) -J6 15 ЖБИ 5 =СУММда15:Н5) -J7 16 ^УММфПЯ^)- B8 =СУ =СУ =СУ =СУ

Рис. 80

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

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

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 единиц.

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

A B C D E 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 =СУММПРОИЗВ(B3 :D 7;B11:D15) 9 10 Склад 1 Склад 2 Склад 3 итого 11 ЖБИ 1 СУММ^ШИ)^ 12 ЖБИ 2 СУММф^^П)^ 13 ЖБИ 3 СУММ^И^В)^ 14 ЖБИ 4 СУММ^М^М)^ 15 ЖБИ 5 СУММф^^^)^ 16 =СУММ( B11:B15)- B8 =СУММ( C11:C15)- C8 =СУММ( D11:D15) -D8

Рис. 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 блоков, которые мы ранее запасли на трех складских площадках. Составляем новую таблицу () и ищем решение последней, третьей задачи.

A B C D E F G H 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:H5;B9:H11) 7 8 Кл. 1 Кл. 2 Кл. 3 Кл. 4 Кл. 5 Кл. 6 Кл. 7 9 Склад 1 =СУММ(B9:H9)-I3 10 Склад 2 ^УММфЮЛЮ)- I4 11 Склад 3 ^УММфПЛП)- I5 12 =СУ ММ( B9:B 11)- B6 =СУ ММ( C9:C 11)- C6 =СУ ММ( D9:D 11)- D6 =СУ ММ( E9:E1 1)-E6 =СУ ММ( F9:F1 1)-F6 =СУ ММ( G9:G 11)- G6 =СУ ММ( H9:H 11)- H6

Рис. 84

Полученной решение представлено в таблице . Как мы видим издержки по перевозкам составили 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 единиц.

	A	B	C	D	E	F	G	H	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	=СУММПРОИЗВ( B2:H6;B10:H14)
9		Кл. 1	Кл. 2	Кл. 3	Кл. 4	Кл. 5	Кл. 6	Кл. 7	итого
10	ЖБИ 1								^УММЬЮЛЮ)
11	ЖБИ 2								=СУММ(Б11:Ш1)
12	ЖБИ 3
13	ЖБИ 4
14	ЖБИ 5								^УММЕМЛМ)
15		=СУМ	=СУМ	=СУМ	=СУМ	=СУМ	=СУМ	^УМадЕюлмуш
17		Склад 1	Склад 2	Склад 3			Полные	издержки
18	ЖБИ 1	78	15	42			=I7+E23+I37
19	ЖБИ 2	33	60	60
20	ЖБИ 3	60	9	24
21	ЖБИ 4	51	45	15
22	ЖБИ 5	33	39	12
23		150	150	205	=СУММПРОИЗВ(B18:D22;B26:D30)
25		Склад 1	Склад 2	Склад 3	итого
26	ЖБИ 1				=СУММ^26Ю26)	=E26+I10-I2
27	ЖБИ 2				=СУММБ27: D27)	=E27+I11-I3
28	ЖБИ 3				=СУММ^28Ю28)	=E28+I12-I4
29	ЖБИ 4				=СУММда29Ю29)	=E29+I13-I5
30	ЖБИ 5				=СУММда30Ю30)	=E30+I14-I6
31		=СУМ	=СУМ	=СУММ	I(D26:D3	0)-D23
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	=СУММПРОИЗВ( B34:H36;B40:H42)
39		Кл. 1	Кл. 2	Кл. 3	Кл. 4	Кл. 5	Кл. 6	Кл. 7	итого
40	Склад 1								=СУММ(B40:H40)
41	Склад 2
42	Склад 3								=СУММ(B42:H42)
43		=СУМ	=СУМ	=СУМ	=СУМ	=СУМ	=СУМ	=СУММ(H40:H42)-H37

Рис. 86

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

При объединении задач, выражения для расчета баланса по доставке (строки B15:H15, B30:D30 и B43:H43) останутся теми же самыми. В установках для Поиска решения мы потребуем, чтобы значения выражений в этих ячейках равнялись нулю. А вот формулы для подсчета вывезенных блоков мы подкорректируем. Теперь в них должны содержаться просто суммы для всех блоков, вывезенных с каждого пункта (столбцы I10:I14, E26:E30 и I40:I42). Баланс по перевозкам с заводов клиентам и на склады мы рассчитаем в столбце H26:H30 - все, что произведено на данном заводе, должно быть вывезено, либо клиентам, либо на склады. В ограничениях укажем, что 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

P12	57	53	61	62	59
P13	73	64	46	72	60
P14	70	65	78	45	49

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

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

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

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

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

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

A B C D E F G H I 1 O1 O2 O3 O4 O5 Другие работы Рабочее время 2 P1 67 55 51 63 49 0 ^УММПРОИЗВ^^З^^^) 3 P2 61 77 52 72 66 0 =СУММПРОИЗВ(B3:G3;B19:G19) 4 P3 63 73 72 42 58 0 =СУММПРОИЗВ(B4:G4;B20:G20) 5 P4 52 44 72 50 55 0 ^УММПРОИЗВ^^^^!) 6 P5 53 76 63 45 47 0 =СУММПРОИЗВ(B6:G6;B22:G22) 7 P6 70 55 77 46 67 0 =СУММПРОИЗВ(B7:G7;B23:G23) 8 P7 43 61 75 54 75 0 =СУММПРОИЗВ(B8:G8;B24:G24) 9 P8 69 70 55 47 61 0 =СУММПРОИЗВ(B9:G9;B25:G25) 10 P9 71 56 67 42 45 0 =СУММПР ОИЗВ(B10:G10;B26: G26) 11 P10 68 63 77 61 69 0 =СУММПРОИЗВ(B11:G11;B27:G27) 12 P11 54 59 51 66 56 0 =СУММПР ОИЗВ(B12:G12;B28:G28) 13 P12 57 53 61 62 59 0 =СУММПРОИЗВ(B13:G13;B29:G29) 14 P13 73 64 46 72 60 0 =СУММПРОИЗВ (B14:G14;B30:G30) 15 P14 70 65 78 45 49 0 =СУММПРОИЗВ(B15:G15;B31:G31) 16 =СУММ(Ш:Ш5) 17 O1 O2 O3 O4 O5 Д.р. Раб. дней 18 P1 =СУММ(Б18^18) =H2* 100/60/8 19 P2 =СУММ(Б19^19) =H3* 100/60/8 20 P3 =СУММ(Б20^20) =H4* 100/60/8 21 P4 =СУММ(Б2Ш21) =H5* 100/60/8 22 P5 =СУММ(Б22^22) =H6* 100/60/8 23 P6 =СУММ(Б23^23) =H7* 100/60/8 24 P7 =СУММ(Б24^24) =H8* 100/60/8 25 P8 =СУММ(Б25^25) =H9* 100/60/8 26 P9 =СУММ(Б26^26) =H10*100/60/8 27 P10 =СУММ(Б27^27) =H11*100/60/8 28 P11 =СУММ(Б28^28) =H12*100/60/8 29 P12 =СУММ(Б29^29) =H13*100/60/8 30 P13 =СУММ(Б30^30) =H14*100/60/8 31 P14 =СУММ(Б3Ш31) =H15* 100/60/8 32 =СУМ =СУМ =СУМ =СУМ =СУМ =СУММ^18^31)^33 =МАКС(І2:Л5) 33 1 1 1 1 1 9 34 35 =H16*100/60 <-Всего рабочих часов

Рис. 87

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

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

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

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

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

Итак, целевая ячейка H16, цель - поиск минимума затрат рабочего времени. Переменные задачи B18:G31. Во вкладке Параметры отмечаем, что задача линейная, а переменные неотрицательны. И в списке ограничений вводим условия: B32:G32=0 и H18:H31=1, обычные для задач о назначениях.

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

220 O1 O2 O3 O4 O5 Д. р. Раб. дней P3 0 0 0 1 0 0 1 8.75 P4 0 1 0 0 0 0 1 9.17 P7 1 0 0 0 0 0 1 8.96 P9 0 0 0 0 1 0 1 9.38 P13 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 рабочих дней.

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

Первый способ соответствует логике задачи - раз одна бригада набрана, давайте вычеркнем этих рабочих из списка. Т. е. нам нужно скопировать лист и удалить строки, соответствующие рабочим P3, P4, P7, P9 и P13 из обеих частей таблицы, верхней и нижней. Только не забудьте проверить, что все формулы остались правильными. Кроме этого нужно изменить количество лишних рабочих в ячейке G33 с 9 до 4. После новой оптимизации получим второй план назначений ().

250 O1 O2 O3 O4 O5 Д. р. Раб. дней P1 0 0 1 0 0 0 1 10.63 P5 0 0 0 0 1 0 1 9.79 P11 1 0 0 0 0 0 1 11.25 P12 0 1 0 0 0 0 1 11.04 P14 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 часа.

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

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

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

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

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

A B C D E F G I J 1-я бри гада 2-я бри гада =СУММ(Т2Е6) =СУММ^2: G6) 1 P3 43 P1 54 =C2*C9+E2*E9 =E2+C2-F2 =F2* 100/60/8 =G2* 100/60/8 2 P4 44 P5 53 =C3*C10+E3*E10 =E3+C3-F3 =F3* 100/60/8 =G3* 100/60/8 3 P7 46 P11 51 =C4*C11+E4*E11 =E4+C4-F4 =F4* 100/60/8 =G4* 100/60/8 4 P9 42 P12 45 =C5 *C12+E5 *E 12 =E5+C5-F5 =F5* 100/60/8 =G5* 100/60/8 5 P13 45 P14 47 =C6*C13+E6*E13 =E6+C6-F6 =F6* 100/60/8 =G6* 100/60/8 220 250 =F1-G1 Войдут в первую бригаду 1 P3 P1 = 1-C9 2 P4 P5 = 1-C10 3 P7 P11 = 1-C11 4 P9 P12 = 1-C12 5 P13 P14 = 1-C13

Рис. 90

В области A1:D7 приведены списки бригад, выбранные нами ранее. Указаны времена выполнения операций с 1-ой по 5-ю соответствующими рабочими первой и второй бригады. Введем переменные C9:C13, которые показывают, кто из рабочих старой первой бригады войдет в первую новую бригаду. Так как для каждой операции выбор рабочих делается из двух человек, то если рабочий старой первой бригады выбран в новую первую бригаду, значит рабочий старой второй бригады в нее выбран не будет. Например, если выбрать рабочего P3, то не будет выбран рабочий P1 и наоборот. Поэтому формулы в столбце E9:E13 вычисляют, кто из рабочих старой второй бригады будет выбран в новую первую бригаду. Для этого переменные C9:C13 должны быть двоичными, разумеется.

Если список новой первой бригады в столбцах C9:C13 и E9:E13 составлен, то можно вычислить время выполнения каждой из операций рабочими новой первой бригады. Это сделано в столбце F2:F6. Формула суммы в ячейке F1 в этом случае подсчитает время однократного исполнения всех операций первой бригадой. Аналогичные расчеты для второй бригады проведены в столбце G1:G6.

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

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

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

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

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

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

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

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

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

На самом деле и это не сложно. У нас ведь была одна проблема, что целевая функция могла быть отрицательной. Так давайте потребуем, чтобы поиск минимума велся только среди неотрицательных значений целевой функции! Добавляем ограничение - F7>=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 руб.! И в таких условиях должно работать отделение, обеспечивающее максимальный объем продаж!

Антипов:

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

Кузьмин:

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

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

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

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

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

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

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

Подольск Голицыно Бронницы Лобня Запас Черноголовка 1100 1400 900 900 200 Обнинск 900 800 1300 1300 150 Первомайское 700 500 950 600 150 Дмитров 1550 1220 1750 500 150 Воскресенск 1050 1550 300 1400 150 Заказ 180 250 60 160

Рис. 92

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

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

день.

Черноголовка Подольск Голицыно Бронницы Лобня Запас Черноголовка 0 1100 1400 900 900 270 Обнинск 2000 900 800 1300 1300 150 Заказ 70 180 250 60 160 Дефицит 0 -80 -100 -30 -90 Поставка 70 100 150 30 70

Рис. 93

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

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

A B C D E F G 1 Status Quo: Издержки и заказы 2 Черноголовка Подольск Голицыно Бронницы Лобня Запас 3 Черноголовка 0 1100 1400 900 900 270 4 Обнинск 2000 900 800 1300 1300 150 5 6 Потребность 70 180 250 60 160 720 7 Дефицит 0 -80 -100 -30 -90 8 Заказ 70 100 150 30 70 420 9 10 Status Quo: Реально существу ^ющий план перевозок 11 Черноголовка Подольск Голицыно Бронницы Лобня Запас 12 Черноголовка 70 150 50 270 13 Обнинск 100 30 20 150 14 Заказ 70 100 150 30 70 420 15 Средневзвешенные транспортные издержки 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 150 0 0 150 24 Заказ 70 100 150 30 70 420 25 Средневзвешенные транспортные издержки 26 0 1 100 800 900 900 27 Выигрыш \Проигрыш 0 -200 600 400 114 29 Оптимальные издержки= 320 000

Рис. 94

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

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

> ГО о о 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;C12:F16) 10 11 Брать\Не брать Подольск Голицыно Бронницы Лобня Запас 12 Черноголовка =СУММ(а2^12)- G3*B12 13 Обнинск =СУММ(а3^13)- G4*B13 14 Первомайское =СУММ(а4^14)- G5*B14 15 Дмитров =СУММ(а5^15)- G6*B15 16 Воскресенск =СУММ(а6^16)- G7*B16 17 Заказ =СУММ(С =СУММр- =СУММ^ =СУММ^12^16)^8 18 19 Средневзвешенн ые транспортные издержки 20 =СУММП РОИЗВ^ 12:C16;C3 :C7)/C8 =СУММПР ОИЗВР12 :D16;D3:D 7)/D8 =СУММПР ОИЗВ^12 :E16;E3:E 7)/E8 =СУММПР ОИЗВ^12: F16;F3:F7)/ F8 21 Средневзвешенные транспортные издержки для Status Quo 22 900 1 400 1 300 1 014 23 Выигрыш \Проигрыш =C22-C20 =D22-D20 =E22-E20 =F22-F20

Рис. 95

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

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

соответствующий этому гипотетическому цеху равен 0. При задании ограничений в Поиске решения необходимо, очевидно, потребовать, чтобы ячейки C18:F18 и H12:H16 равнялись нулю. Кроме этого, можно потребовать, чтобы двоичные переменные B12:B13 оставались равными единице. Это означает, что старые места цехов уже выбраны.

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

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

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

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

> го о 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 в стране Y. Компания владеет 5 заводами с различными производственными мощностями, построенными в разное время и поэтому имеющими различные ограничения на качество исходного сырья, а также различные значения себестоимости продукта, в зависимости от качества сырья.

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

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

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

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

Потребность заводов компании в сырье на планируемый период Завод 1 Завод 2 Завод 3 Завод 4 Завод 5 мин. % ИК k%min 5% 5% 5% 7% 7% Объем (млн.тонн) 18 25 30 15 20

Рис. 97

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

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

min

C = (1-H •

max

min

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

Параметры зависимости себестоимости от концентрации ИК в сырье Завод 1 Завод 2 Завод 3 Завод 4 Завод 5 Cmax $/тыс.тонн 20,0 18,0 16,0 22,0 20,0 H 1,5 1,2 1,2 1 1

Рис. 98

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

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

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

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

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

Характеристики возможных поставщиков сырья для заводов НАЦПРОДУКТ Поставщик Индекс ненадеж ности Максимум, млн. тонн Минимум, млн. тонн 0/ % концентрации ИК Цена ($/тонна) 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% суммарной себестоимости продукции компании. В компании утвердилось мнение, что транспортные издержки столь высоки из-за неэффективной работы отдела логистики. В конце концов, о задаче оптимизации транспортных издержек все слышали еще в институте. Это - азы количественных методов управления. Однако никто не слышал, чтобы отдел Феофана Перевозчикова использовал количественные методы оптимизации в своей практической работе. Феофан действительно считал это излишним. Ему казалось, что и без всяких замысловатых оптимизационных методов ясно, от какого поставщика вести сырье каждому заводу. Реальная работа состояла в том, чтобы вовремя и правильно зафрахтовать суда и железнодорожные составы для перевозки и проконтролировать движение грузов. Это отдел логистики делал неплохо. Поэтому критику коллег он считал несправедливой. Однако под давлением этой критики он, в конце концов, взял в штат молодого выпускника факультета вычислительной математики и кибернетики Лучшего Университета страны Y, Макса Сиплексова (сына своего старого приятеля).

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

Цены перевозки 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

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

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

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

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

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

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

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

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

Приложение

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

k _- k

C = (1-H ^mm

) C

i ' max

^k mm

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

Значения k, С _max и H для каждого завода приведены на и .

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

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

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

Помимо этого необходимо ввести 10 двоичных переменных типа «выбрать - не выбирать» для каждого поставщика:

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

x_i = <

[1 - выбрать

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

V>x • V.

г г mm-

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

V- < V_m

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

V > 0, а x_t = 0

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

V -100 • х- < 0

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

• x_i < 0

V - ?_т

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

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

10 5

Z V=Z Vj =108

i=1 j=1

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

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

10

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

i=1

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

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

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

10

ZRIi'I']

RI = і=1

закупок 10

ZV

=1

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

10 5

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

i=1 j=1

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

I RI,-V

I R,-v,

J=1_

10

IV

RI _з

=1

в виде

RI_з

108

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

закупок

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

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

10

с = IV,c,

=1

где С( — стоимость одной тонны сырья у I -го поставщика.

A B C D E F G H І 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 =І8-100*Н8 =C8*H8 9 2 30 1 8.0% 15.80 2 10 3 24 1 5.8% 7.53 Ь 11 4 28 1 5.3% 7.10 8 12 5 20 2 7.8% 14.80 1 13 Ь 32 2 Ь.2% 9.80 Ь 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 Ь 18 ИТОГО Требуется 19 Закупок =СУММ(І8:І17) =СУММ(В4^4) 20 Стоимость Закупок с%ИК>7% =І9+І12+І14 =E4+F4 21 =СУММПРОИЗВ($І$8:$І$ 17;E8:E17) Индекс надежности =СУММПРОИЗ В($І$8:$І$17;F 8:F17)/J19 4

Рис. 101

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

В ячейки J7:J16 введены условия связи между объемом закупок V_f и двоичной переменной Xf (4), а в ячейки K7:K16 - выражения для минимального объема закупок, равного либо 0, либо V_min.

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

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

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% 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_i - 100*x_f < 0) фактически не является связывающим. И без него Поиск решения выбрал объемы закупок, превышающие минимально допустимые. Легко понять, что это отнюдь не всегда будет так. Пусть, например, поставщики требуют, чтобы минимальные объемы закупок составляли не менее 50% от объявленных ими же максимальных допустимых объемов. Решение задачи в этом случае показано на .

Видно, что теперь условие связи V_f - 100*x_f < 0 существенно влияет на решение, ухудшая целевую функцию и меняя оптимальный выбор поставщиков.

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Ь 8 6.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 Ь 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

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

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

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

Переменные решения B11:F16 - объемы перевозок от каждого из выбранных поставщиков к каждому заводу-потребителю. В ячейках G11:G15 -стандартные требования поставщиков: суммарный вывезенный объем от каждого поставщика равен его запасу, а в ячейках B16:F16 - аналогичные требования заводов потребителей: суммарный объем сырья, привезенный от каждого из поставщиков, равен заказу.

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

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

5

2 % ИК _г Vi % ИК — J—1_

® j поставки 5

2 V

г —1

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

5

^ % ИК_І Vi

i=1_

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

A B C 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 ^УММПРОИЗВ^^^ 13:F13) 14 5 =СУММ^14: F14)-G5 ^УММПРОИЗВ^^^ 14:F14) 15 7 =СУММ^15: F15)-G6 ^УММПРОИЗВ^^^ 15:F15) 16 8 =СУММ^16: F16)-G7 ^УММПРОИЗВ^^^ 16:F16) 17 10 =СУММ^17: F17)-G8 ^УММПРОИЗВ^^^ 17:F17) 18 =СУММ(В13:В17)-В9 =СУММ0-І13 :H17) 19 Реальный % ИК =СУММПРОИЗВ(В13:B17;$H$4:$H$8)/B9

Рис. 104

j поставки

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

Видно, что все ограничения на объемы поставок и качество доставленного сырья выполнены. При этом 4-му и 5-му заводу поставки осуществляются не только от поставщиков руды с процентным содержанием ИК выше 7%, но и от тех, где %ИК ниже 7%. Предполагается, что перед переработкой сырье, пришедшее от разных поставщиков, проходит стадию перемешивания так, что концентрация ИК в ней становится равной средневзвешенному значению, которое, как видно, удовлетворяет необходимым требованиям.

> ГО о 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 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 16 8 16.25 0 19.75 0 0 0.000 505.60 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.0611 0.0584 0.0586 0.0700 0.0773

Рис. 105

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиска решения?!

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

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

В качестве переменных решения рассматриваем только объемы поставок, а введенные формулы используем для расчета стоимости закупки (ячейка 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 млн. тонн руды.

в 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% 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

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

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

Обратим внимание, что у нас есть два завода-потребителя, к которым нужно отвести сырье с повышенным содержанием ИК, и два поставщика (№№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. Результирующий план представлен на .

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

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

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

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

> ГО о о E F G H 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 min % ИК 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 Max 20 18 16 22 20 22 k 1.5 1.2 1.2 1 1 ИТОГО 23 Реально 14.00 14.30 12.77 21.69 17.71 1 672.4

Рис. 107

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

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

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

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

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

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

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

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

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

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

min

C = (1 - H •

max '

min

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

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

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

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

	A|B|C|D|E|F| G 1 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	-	=СУММ®15^15)^15
16	2	-	21.8	-	8.2	-	30.0	=СУММ®16^16)^16
17	3	-	3.2	-	6.8	-	10.0	=СУММ (B17:F17)-G17
18	4	-	-	-	-	-	- 0.0	=СУММ®18^18)^18
19	5	-	-	-	-	10.0	10.0	=СУММ^19^19)^19
20	6	-	-	16.0	-	10.0	26.0	=СУММ^20^20)^20
21	7	18.0	-	-	-	-	18.0	=СУММ(B21:F21)-G21
22	8	-	-	14.0	-	-	14.0	=СУММ^22^22)^22
23	9	0.0	-	-	-	-	-	=СУММ®23^23)^23
24	10	-	-	0.0	-	-	0.0	=СУММ^24^24)^24
25	Заказы	18	25	30	15	20	Индекс ненадежности	Реально	Д/Б
26	Ограниче ния	=СУММ( B15:B24) B25	=СУММ( C15:C24)- C25	=СУММ( D15:D24)- D25	=СУММ( E15:E24)- E25	=СУММ( F15:F24)- F25	=СУММПРОИЗВ^ 15^24^3^12)/СУ ММ^25^25)	4
27	min % ИК	5.00%	5.00%	5.00%	7.00%	7.00%
28	Реальный % ИК	=СУММПРОИЗВ(B15:B24;$D$3:$D$12)/ B25	=СУММП РОИЗВ^	=СУММ^29^30^ 31)	Полная себестоимость
29	себестои м.	20	18	16	22	20	=СУММПРОИЗВ^ 15:F24;B34:F43)	Стоимость перевозки
30	K %ИК	1.50	1.20	1.20	1.00	1.00	=СУММПРОИЗВ^ 31:F31;B25:F25)	Стоимость производства
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:G24;E3:E12)	Стоимость закупки
32		Заводы-потребители - цены перевозок			Здрав. смысл	Дельта
33	Поставщи	1	2	3	4	5
34	1	24.2	17.6	25.8	24.2	18.8	=G28	4 449.8	=(H34-G28)/H34
35	2	28.8	9.6	11.8	10.2	15.6	=G29	1 738.8	=(H35-G29)/H35
36	3	15	7.8	21.8	8.2	11	=G30	1 672.4	=(H36-G30)/H36
37	4	23.2	17.4	25.4	19.8	26.2	=G31	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-ти заводам компании (ячейки B15:F24), 10 значений объемов закупок у каждого из 10-ти потенциальных поставщиков (ячейки G15:G24), а также 10 двоичных переменных типа «выбрать данного поставщика или не выбирать» (ячейки G3:G12), назначение которых было подробно рассмотрено в анализе действия 1.

Формулы в ячейках H3:H12, выражающие минимально возможный объем закупок у каждого поставщика, и ячейках I3:I12, выражающие связь между объемами закупок и двоичными переменными «выбрать поставщика или не выбирать», также как и формула для средневзвешенного индекса надежности

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

Формулы в ячейках H15:H24, выражающие требования поставщиков, и в ячейках B26:F26, выражающие требования по заказам заводов-потребителей, также как и формулы для средневзвешенного %ИК в руде, доставленной на каждый завод (ячейки B28:F28), подробно обсуждались при анализе плана перевозок в действии 1.

Целевая функция, равная сумме трех издержек (закупки, перевозки и переработки), введена в ячейке L3. Издержки закупки сырья (ячейка L9) и его перевозки от поставщиков к заводам-потребителям (ячейка L5) рассматривались при анализе действия 1 кейса. Издержка переработки (ячейка L7) определена как сумма произведений объемов сырья, заказанных каждым заводом, на себестоимость переработки сырья каждым заводом, которые зависят от средневзвешенного процентного содержания ИК, доставленного каждому заводу. Последние вычислялись по формуле 1 (ячейки B31:F31).

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

іШ

Поиск решения

Установить целевую ячейку;

Равной: С максимальному значении? С* значению; |о

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

I $G$У.т 12; ІЙ* 1S; $G$24; $6$ 1S:$F$24 Предіолажігь |

Ограничения;

Добавить

В^іпоіыить I

Закрыть

Параметры

|B$26:$F|26«0

$B$2B:fF$23 >= $B$27:fF$27

|G$15:$G|24 <- $B$3:$6$12

$G$15:$G$24 >= $H$3:$H$12

$G$3:$4$12 = лаоичное

$H$1S:$H$24=0

$I$3;$1$12 <= 0

$L$28 <- $M$2S _

Изменить

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

Удалить

Справка

Рис. 109

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

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

A B C D E F G H I 1 Оптимальный интегрированный план в цепочке поставок НАЦ ПРОДУК" 2 Поставщики Max Min % ИК Цена Индекс Брать/ не брать Мин. закупка Связь 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 min % ИК 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 Max себестоим. 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 млн. переменных. Существуют и другие профессиональные оптимизационные инструменты с «мощностями» такого же порядка. Информацию о них можно найти на сайтах

-

-

-

-

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

от нескольких тысяч до сотен тысяч (см., например 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 единиц, которые будут показывать, какие переезды между магазинами выбраны. Если теперь применить функцию =СУММПРОИЗВ( ) к этим двум таблицам, то мы сразу получим общее расстояние, которое проехал грузовик. Таким образом задача линейной целочисленной оптимизации практически составлена ().

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:O3;C18:O18) 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:O18) 19 Мг 1 0 20 Мг 2 0 21 Мг 3 I Іер ;ме ннь іе 0 22 Мг 4 0 30 Мг 12 0 31 0 0 0 0 0 0 0 0 0 0 0 0 =СУММ^18Ю30)

Рис. 111

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

Рис. 112

Т.е. какая-то часть маршрута действительно соответствует выезду из базы, посещению нескольких магазинов и возвращению назад - База-> Магазин №3 -> Магазин №1-> База. Но большая часть предложенного маршрута имеет вид: Мг 2 -> Мг 5-> Мг 2, или Мг 7 -> Мг 11 -> Мг 7 (и ).

		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	5
9	Мг 9	19	24	12	21	37	10	6	36	5	##	6	30	16	5
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, ее легко было бы устранить. В самом деле, при наличии таких маршрутов в полученном решении соответствующие элементы таблицы переменных оказываются симметричными относительно диагонали C18-O30. Например, единица, показывающая наличие перевозки, стоит и в ячейке J29 (переезд из Мг 7 в Мг 11), и в ячейке N25 (переезд из Мг 11 в Мг 7), симметричной ячейке J29 относительно диагонали таблицы переменных.

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

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

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

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 км. Т.е. введенное ограничение действительно привело к изменению маршрута.

Рис. 115

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В ячейках D36:O168 и C169:C180 содержатся переменные задачи. В данном случае единица в ячейке D36 строки D36:O36 показывает, что первым пунктом посещения после отправления с базы является Мг 1. При этом строка D21:O21 просто дублирует строку D36:O36, а в ячейке R21 по формуле =СУММПРОИЗВ ($D$1:$O$1; D21:O21) вычисляется номер посещенного магазина.

	A	B	C	D	E	F	G	H	I	J	K	L	M	N	о	P	Q	R
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 15	9	7	4	1	6	5	16	21	12	7	20		118
17		0	=R21	2	0	0	0	0	0	0	0	0	0	=R33
18
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$1?)21:021)
25	5			0	\0	0	1	0
26	6			0	L-	=СУММф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(D1	09:)	Л20		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	=СУММ (D36: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	=СУММ (D168:0168)
169	1	13	0													=C169
170	2		0													=C170
179	11		1													1
180	12		0													0

Рис. 116

Выбор второго пункта посещения делается в ячейках D37:O48. Единица в ячейке F37 показывает, что вторым пунктом выбран Мг 3 (см. номер магазина по этому же столбцу, в котором стоит 1, в ячейке F35). При этом ссылку на номер предыдущего магазина смотрим по этой же строке в ячейке A37. В столбце

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

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

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

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

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

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

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

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

Solver Parameters

1?

Solve

Hi Cel: ЕчиэІ ю; f" мах (* Mlts By Changing '-.'аг;гз!е Ceils: О value of: 5O$3fi:5O$WS;5C$lfi9:$CSia0 Subject to the Constraints: SC S169; SC 5 ISO - binary Ж $C$L9:SO$19 = 1 — SDS36;50?168 - binary — EP5109:SP$120 = ?0$27:$O$Z7 S?5l2l:SPn32 - SD52S:SOS2S S=5133:SP$144 = SD529:$OS29

&ИЯ |La-ge-Scale LP Soever Charge Delete

Close

Qpbons

Add

variables

=teset All

He's

SP5145:$PSI56 ж $0530:50530 SPS1S7:5PS163 - SDS31:$OS31 S?S169:S??230 - SD?32:?OS32 вРШ:*Р«Э - I S?53?:SP543 = 50521:50521 SPS^;S?S60 = SOS22:SO?22 3PS6 L:$p$72 = ?DS23:SO?23 $P$73:S?S3- - SQS24:*QS2-3 SPSS5:S?S96 - SD52S:50s2S SP^7:?PSll08 = 5DS26:SC526 5QS2l:SQ633 = I

Рис. 117

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

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

Рис. 118

Если теперь запустить поиск решения, то спустя 1-3 минуты, в зависимости от мощности процессора, получим то решение, которое и показано в табличке: минимальная длина маршрута 118 км, порядок пунктов посещения -

База (0) 1 3 2 5 6 10 9 8 12 4 7 11 База (0)

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

Рис. 119

Вопрос b.

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

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

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

Этого можно добиться простым способом. Изменим таблицу расстояний так, чтобы места магазина №2 и базы на карте поездок совпадали. Для этого зададим расстояния от магазина №2 до всех пунктов, такими же, как от базы. А расстояние от базы до самого магазина сделаем нулевым. Изменения, которые нужно внести в таблицу расстояний, показаны на .

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

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

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



Содержание раздела

---