8.3. Усложненные задачи транспортного типа

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

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

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

Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту AtBj можно Провести не более q единиц груза, то Bj столбец матрицы разбивается на два столбца — її] и її'у В первом столбце спрос принимается равным разности между действительным спросом bj и ограничением q: b'j = bj — q, во втором — равным ограничению q, т.

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

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

Необходимо максимизировать целевую функцию задачи транспортного типа. В этой ситуации при составлении опорного плана в первую очередь стараются заполнить клетки с наиболее высокими значениями показателей с у. Выбор клетки, подлежащей заполнению при переходе от одного допустимого плана к другому, должен производиться не по минимальной отрицательной разнице [су — (а,- + Ру)], а по максимальной положительной разнице [су — — (а, + Ру)]. Оптимальным будет план, которому в последней таблице сопутствуют свободные клетки с неположительными элементами: все разности [с у — (а,- + Ру)] < 0.

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

Рассмотрим примеры задач транспортного типа.

Пример 8.1. Одно фермерское хозяйство (Ах) имеет продовольственное зерно двух видов: 3 тыс. т — III класса и 4 тыс. т — IV класса. Второе фермерское хозяйство (А2) также имеет зерно двух классов: 5 тыс. т — III класса и 2 тыс. т — IV класса. Зерно должно быть вывезено на два элеватора: на первый элеватор (2?j) необходимо поставить 2 тыс. т пшеницы III класса, 3 тыс. т пшеницы IV класса и остальные 2 тыс. т пшеницы любого класса.

Аналогично второй элеватор (В2) должен получить 8,25 тыс. т, из них пшеницы — 1 тыс. т III класса и 1,5 тыс. т IV класса.

Стоимость перевозки в д. е. 1 т зерна составляет: из пункта Ах в пункты Вх и В2 — 1 и 1,5 соответственно; из пункта А2 в пункты Вх и В2 — 2 и 1 д. е. соответственно.

Составить оптимальный план перевозок.

Каждого поставщика условно разбиваем на две части согласно двум видам зерна {А3 и А4; А2 и А4), аналогично потребителей разбиваем на три части (пшеница III класса, IV класса и любой класс): Вj3, В4 и ВД а также В2 , В4 и В2. Потребности превышают запасы, поэтому вводим фиктивного поставщика А3. Часть клеток в таблице запираем большими числами М; например, в клетке (1; 2) стоит большое число. Это значит, что поставщик/^3 не может удовлетворить потребителя В 4 пшеницей IV класса за счет имеющейся пшеницы III класса.

С учетом сделанных замечаний составим первую таблицу (табл. 8.6).

Таблица 8.6

Исходные данные Потребители Запас, тыс. т Поставщики Вх в2 Вхг ВхА Вх* B"i Вг4 в2° At3 і м і 1,5 м 1,5 3 Ai А,4 м 1 і М 1,5 1,5 4 а23 2 м 2 1 М 1 5 а2 а24 М 2 2 М 1 1 2 Ау 0 0 0 0 0 0 1,25 Спрос, тыс. т 2 3 2 1 1,5 5,75 15,25

Перевозки от фиктивного поставщика не производятся, поэтому с51 = с52 = с5з = с54 = с55 = с56 = 0.

Анализ решения.

Первый поставщик поставит на первый элеватор (i^) пшеницу III класса (х22 = 2); пшеницу IV класса (х22 = 3), а также пше-ницу любого класса (III или IV) (л:13 = 1; х23 = 1).

Второй поставщик (Л2) поставит на второй элеватор (В2) пшеницу III класса (х31 = 1), пшеницу IV класса (л:45 = 1,5) и частично Потребители Запас, тыс. т Поставщики я. В2 я,3 в2ъ В2 В2» А3 2 м Iі 1,5 м 1,5 3 А, А,4 м 3 ' Iі М 1,5 1,5 4 А2} 2 м 2 і 1 М 1

4 5 Аг А24 М 2 2 М 1.51 і

0,5 2 Лг 0 0 0 0 0 0

1,25 1,25 Спрос, тыс. т 2 3 2 1 1,5 5,75 15,25

любую пшеницу (х36 = 4; х46 = 0,5). Потребность элеватора в любой пшенице не удовлетворена на 1,25 тыс. т (х56 = 1,25). Минимальные затраты на перевозку составили: Zmin = 14 д. е.

Пример 8.2. Модель производства с запасами.

Фирма переводит свой головной завод на производство определенного вида изделий, которые будут выпускаться в течение четырех месяцев. Величины спроса в течение этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет:

запасов изделий, произведенных в прошлом месяце, сохраняющихся для реализации в будущем;

производства изделий в течение текущего месяца;

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

Затраты на одно изделие в каждом месяце составляют 4 д. е. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 д. е. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом в размере 2 д. е. в месяц.

Объем производства изделий меняется от месяца к месяцу в зависимости от выпуска других изделий. В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно.

Требуется составить план, имеющий минимальную стоимость производства и хранения изделий.

Решение

Задачу можно сформулировать как транспортную.

Таблица 8.8 Транспортная система Производственная система 1. Исходный пункт /

Пункт назначения j

Предложение в пункте і

Спрос в пункте у

Стоимость перевозки из / и У 1. Период производства /

Период потребления j

Объем производства за период /

Реализация за периоду

Стоимость производства и хранения за период / и у

Перед нами структура транспортной модели. Для рассматриваемой задачи стоимость «перевозки» изделия из периода і в период у выражается как:

стоимость производства в /-и период, і = у;

СУ =

стоимость производства в /-й период плюс стоимость задержки от і до у, і < j;

стоимость производства в /-й период плюс штраф за нарушение срока, і > у.

Из определения Су следует, что затраты в период і при реализации продукции в тот же период / (/ = у) оцениваются только стоимостью производства. Если в период і производится продукция, которая будет потребляться позже (/ < У), то имеют место дополнительные издержки, связанные с хранением. Аналогично производство в /-й период в счет невыполненных заказов і > у влечет за собой дополнительные расходы в виде штрафа. Например,

сп = 4 д. е.;

с24 = 4 + (0,5 + 0,5) = 5 д. е.;

с41 = 4 + (2 + 2 + 2) = 10 д. е.

Исходная транспортная таблица выглядит следующим образом (табл. 8.9).

Исходные данные Период Период Объем производства 1 2 3 4 1 4 4,5 5 5,5 50 2 6 4 4,5 5 180 J 8 6 4 4,5 280 4 10 8 6 4 270 Спрос 100 200 180 300

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

Пример 8.3. Имеются три сорта бумаги в количестве 10, 8 и 5 т, которую можно использовать на издание четырех книг тиражом 8000, 6000, 10 000, 15 000 экземпляров. Расход бумаги на одну книгу составляет: 0,6; 0,4; 0,8; 0,5 кг, а себестоимость тиража книги при использовании /-го сорта бумаги задается следующей матрицей (д.

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

Решение

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

Потребности в бумаге легко определить, зная тираж и расход на одну книгу (т):

8000 • 0,6 = 4,8;

15 000 • 0,4 = 6;

6000 • 0,8 = 4,8;

10 000 • 0,5 = 5.

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

Согласно изложенному составим первую таблицу (табл. 8.10).

Таблица 8.10

Исходные данные Поставщики Потребители Запасы, т Вх В2 Вз Вл Вз 40 20 80 50 0 10 а2 30 30 60 40 0 8 Аз 50 30 40 40 0 5 Потреб-ность, т 4,8 4,8 6 5 2,4 23

Используя метод потенциалов, получим оптимальное решение (табл. 8.11).

Таблица 8.11

Оптимальное решение Поставщики Потребители Запасы, т Вх В2 *3 в. в; Ах 40 20

4,8 80 50

2,8 0

2,4 10 А2 30

4,8 30 60

1 40

2,2 0 8 Аз 50 30 5 40 40 0 5 Потреб-ность, т 4,8 4,8 6 5 2,4 23

Анализ решения.

Бумаги 1-го сорта в количестве 4,8 т затрачено на издание второй книги; 2,8 т — на издание четвертой книги; 2,4 т — не использовано. Бумаги 2-го сорта затрачено: на первую книгу — 4,8 т; на издание третьей книги - 1,0 т; на издание четвертой книги - 2,2 т; бумага 3-го сорта использована на издание третьей книги в количестве 5 т.