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

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

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

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

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

3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту A_iB_j можно провести не более q единиц груза, то B_j -й столбец матрицы разбивается на два столбца - и . В первом столбце спрос принимается равным разности между действительным спросом и ограничением q: , во втором – равным ограничению q, т.е. . Затраты c_ij в обоих столбцах одинаковы и равны данным, но в первом столбце , в клетке, соответствующей ограничению i, вместо истинного тарифа c_ij ставится искусственно завышенный тариф M (клетка блокируется). Затем задача решается обычным способом.

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

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

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

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

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

Пример 1. Одно фермерское хозяйство (A ₁) имеет продовольственное зерно двух видов: 3 тыс. тонн – III класса и 4 тыс. тонн - IV класса. Второе фермерское хозяйство (A ₂) также имеет зерно двух видов: 5 тыс. тонн – III класса и 2 тыс. тонн - IV класса. Зерно должно быть вывезено на два элеватора: на первый элеватор (B ₁) необходимо поставить 2 тыс. тонн пшеницы III класса, 3 тыс. тонн пшеницы IV класса и остальные 2 тыс. тонн пшеницы любого класса.

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

Стоимость перевозки в д.е. 1 тонны зерна составляет: из пункта A ₁ в пункты B ₁ и B ₂ - 1 и 1,5 соответственно; из пункта A ₂ в пункты B ₁ и B ₂ - 2 и 1 д.е. соответственно.

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

Решение

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

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

Таблица 7.6

Исходные данные

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

Таблица 7.7

Оптимальное решение

Анализ решения. Первый поставщик поставит на первый элеватор (B ₁) пшеницу III класса (x ₁₂ = 2); пшеницу IV класса (x ₂₂ = 3), а также пшеницу любого класса (III или IV) (x ₁₃ = 1; x ₂₃ = 1).

Второй поставщик (A ₂) поставит на второй элеватор (B ₂) пшеницу III класса (x ₃₁ = 1), пшеницу IV класса (x ₄₅ = 1,5) и частично любую пшеницу (x ₃₆ = 4; x ₄₆ = 0,5). Потребность элеватора в любой пшенице не удовлетворена на 1,25 тыс. тонн (x ₅₆ = 1,25). Минимальные затраты на перевозку составили: Z _min = 14 д.е.

 

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

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

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

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

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

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

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

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

Решение

Задачу можно сформулировать как транспортную. Эквивалентность между элементами производственной и транспортной систем устанавливается следующим образом:

Транспортная система	Производственная система
1. Исходный пункт i	1. Период производства i
2. Пункт назначения j	2. Период потребления j
3. Предложение в пункте i	3. Объем производства за период i
4. Спрос в пункте j	4. Реализация за период j
5. Стоимость перевозки из i в j	5. Стоимость производства и хранения за период i и j

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

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

c ₁₁ = 4 д.е.

c ₂₄ = 4 + (0,5 + 0,5) = 5 д.е.

c ₄₁ = 4 + (2 + 2 + 2) = 10 д.е.

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

Таблица 7.8

Оптимальное решение

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

.

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

Решение

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

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

8000 * 0,6 = 4,8 т

15000 * 0,4 = 6 т

8000 * 0,6 = 4,8 т

10000 * 0,5 = 5 т

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

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

Таблица 7.9

Исходные данные

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

Таблица 7.10

Оптимальное решение

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

 

Решение транспортной задачи с применением MATLAB

 

clc;

f=[70 50 15 80 70 80 90 40 60 85 50 10 90 11 25];

Aeq=[1 1 1 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 1 1 1 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1

1 0 0 0 0 1 0 0 0 0 1 0 0 0 0

0 1 0 0 0 0 1 0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 1 0 0 0 0 1 0 0

0 0 0 1 0 0 0 0 1 0 0 0 0 1 0

0 0 0 0 1 0 0 0 0 1 0 0 0 0 1];

beq=[300;150;250;170;110;100;120;200];

lb=[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];

X=linprog(f,[],[],Aeq,beq,lb,[]);

disp(X);

fopt=f*X;

disp(fopt);