Нетрадиционные транспортные модели

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

Пример 2.13. (задача о распределении оборудования). Пусть на предприятии имеется m видов станков, максимальное время работы которых соответственно равно () часов. Каждый из станков может выполнять n видов операций. Суммарное время выполнения каждой операции соответственно равно b_j (). Известна производительность c_ij i -го станка при выполнении j -й операции. Определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей.

Для составления математической модели обозначим через x_ij (; ) время, которое i -й станок должен работать на j -й операции. Тогда количество деталей, обработанных на i -м станке, равно _. Количество деталей, обработанных на всех станках, равно . Так как максимальное время работы i-го станка ограничено значением , то получаем если максимальное время работы станков используется полностью, или если это время используется не полностью. Так как время, отведенное на j -ю операцию, равно b_j, то Таким образом, если максимальное время работы используется полностью, мы получаем следующую математическую модель задачи:

максимизировать целевую функцию

при ограничениях

,

,

.

Эта задача отличается от математической модели транспортной задачи (2.9) – (2.12) только тем, что она является задачей максимизации, а не минимизации. Однако это отличие, как известно, не является существенным: достаточно умножить целевую функцию
на – 1, т. е. считать все значения c_ij отрицательными, и задача максимизации будет сведена к задаче минимизации. Таким образом, эта задача может быть решена методом потенциалов. Если же максимальное время работы используется не полностью, то мы получаем открытую транспортную модель, которая сводится к закрытой путем введения фиктивной (n+1)-й операции (простой), которой соответствуют производительности, равные нулю.

Пример 2.14. (формирование штатного расписания). Пусть имеются специалисты m профилей в количествах (), которые могут выполнять n видов работ. Потребности в специалистах для каждого вида работ равны соответственно b_j (). Матрица C=(c_ij) характеризует эффективность использования специалиста на данной работе (производительность труда). Требуется распределить работы между специалистами так, чтобы производительность труда была максимальной.

Если ввести матрицу X=(x_ij), где x_ij – количество специалистов i -го профиля, выполняющих работу j -го вида, то математическая модель этой задачи, как легко видеть, совпадет с предыдущей.

Пример 2.15. Спрос на некоторый скоропортящийся продукт в следующие 4 месяца составляет 400, 300, 420 и 380 тонн соответственно. Предложение этого товара в те же месяцы составляет 500, 600, 200 и 300 тонн. Отпускная цена на этот товар колеблется от месяца к месяцу и равна соответственно 100, 140, 120 и 150 долл. за тонну. Поскольку товар скоропортящийся, он должен быть реализован в течение трех месяцев (включая текущий). Стоимость хранения в течение месяца тонны товара равна 3 долл. Природа товара такова, что невозможна задержка с выполнением заказа. Найти оптимальный план закупки товара.

Обозначим x_ij – количество продукта, закупленного в i -м месяце для потребления в j -м месяце (). Очевидно, x_ij =0 при i> j (продукт не может быть потреблен раньше, чем куплен). Кроме того, согласно условию, x₁₄ =0, т. к. продукт должен быть реализован в течение трех месяцев. Пусть c_ij – затраты на покупку и хранение 1 тонны продукта при покупке в i -м месяце и потреблении в j -м. Тогда c₁₁=100, c₂₂=140, c₃₃=120, c₄₄=150, c₁₂=143, c₁₃=126, c₂₃=123, c₂₄=156, c₃₄=153. Учитывая, что закупки товара в каждом месяце не должны превышать предложения, а потребление в каждом месяце равно спросу, получаем следующую математическую модель:

минимизировать целевую функцию при ограничениях

Эта модель совпадает с открытой транспортной моделью при дополнительных ограничениях: x_ij =0 при i> j, x₁₄ =0. Если положить c_ij =M при i> j, x₁₄ =M, где M – очень большое число, то эти ограничения можно опустить (они будут выполняться автоматически). Остается свести открытую модель к закрытой введением переменных x_i5, полагая значения c_i5=0. Решение задачи теперь может быть найдено методом потенциалов и имеет вид: x ₁₁ = 400, x ₁₅ = 100, x ₂₂ = 300, x ₂₃ = 220, x ₂₄ = 80, x ₃₃ = 20, x ₄₄ = 300. Значения остальных переменных равны 0. Таким образом, в первый месяц следует закупить 400 тонн продукта, во второй – 600 тонн, из которых 220 тонн предназначены для покрытия спроса третьего месяца и 80 тонн – на покрытие спроса 4-го. В третий месяц следует закупить 200 тонн продукта и в 4-й – 300 тонн. Общая стоимость закупки будет равна 190 540 долл.