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

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

Речь идет о перевозках двух видов продукции: A и B.

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

 

		Клиент X	Клиент Y	Клиент Z	Клиент W
		A	B	A	B	A	B	A	B
База 1	A
B
База 2	A
B
База 3	A
B

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

	Клиент X	Клиент Y	Клиент Z	Клиент W
	A	B	A	B	A	B	A	B
Заказы, шт.

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

	База 1	База 2	База 3
	A	B	A	B	A	B
Запасы, шт.

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

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

Задачи о назначениях. Теоретические основы

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

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

Переменные x_ij в задаче о назначениях принимают два значения: , если i-ый претендент (Pi) не принимается на j-ую вакансию (Vj), , если i-ый претендент (P_i) принимается на j-ую вакансию (Vj). Все переменные задачи неотрицательные и целые числа. Кроме того, так как каждый претендент может занять только одну вакансию и все вакансии должны быть заняты, должны удовлетворяться следующие ограничения:

Если обозначить через c_ij количественную меру эффективности назначения i-ого претендента на j-ую вакансию, целевая функция задачи о назначения будет выглядеть следующим образом

Итак, формализованное описание задачи о назначениях совпадает с описанием транспортной задачи.

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

Пример 2.2 Персонал фирмы «Компью-Нет»

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

 

	Аня	Маша	Катя	Лиза	Ольга	Софья
Иван
Михаил
Павел
Николай
Алексей
Петр

 

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

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

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

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

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

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

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

Рис.6. Организация данных при решении задачи о назначения примера 2.2.

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

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

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

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

Во втором вопросе поставлена задача вычисления индекса совместимости для каждой пары. Поэтому, в блок ячеек (I2:I7) введены формулы сумм произведений соответствующих строк таблицы (cij) и (xij).

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

 

Рис.7. Установка опций Поиска решений задачи в примере 2.2 по пункту 1.

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

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

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

Рис.8. Результат решения задачи примера 2.2 по пункту 1.

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

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

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

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

Рис.9. Результат решения задачи примера 2.2 по пункту 1 при повторном запуске средства «Поиск решений».

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

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

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

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

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

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

Здесь уместно напомнить, что в задаче оптимизации можно поставить только одну цель. В случае же, если нужно достичь нескольких целей приходится создавать некий синтетический показатель. Либо, кроме главной цели, задавать дополнительные ограничения, направленные на получение не слишком плохого результата по другим вашим требованиям. В данной задаче мы были заинтересованы, чтобы индексы всех пар были минимальными. Так как поставить такую задачу нельзя, использовали синтетический показатель – суммарный индекс. Однако полученное решение нас не устраивает, поэтому остается только один путь – добавить новые ограничения. Если потребовать, чтобы ни один индекс совместимости команд не превышал 6 (I2:I7<=6), а переменные x_ij – двоичные (Рис.10), то получим результат на Рис.11.

Рис.10. Установка дополнительных ограничений при решении задачи 2.2 по пункту 4.

 

Рис.11. Результат решения задачи примера 2.2 по пункту 4.

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

 

Задача для самостоятельного решения