Транспортная задача в сетевой постановке

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

    Стоимость перевозки в д.е. 1 тонны зерна  составляет: из пункта A1  в пункты B1   и B2  - 1 и 1,5 соответственно; из пункта A2  в пункты B1  и B2  - 2 и 1 д.е. соответственно. 

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

    Решение 

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

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

    Таблица 3.6 

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

    

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

    Таблица 3.7 

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

      
 

    Анализ  решения. Первый поставщик поставит на первый элеватор (B1) пшеницу III класса ( x12 = 2); пшеницу IV класса (x22 = 3), а также пшеницу любого класса (III или IV) (x13 = 1 ; x23 = 1). 

    Второй  поставщик (A2) поставит на второй элеватор (B2) пшеницу III класса (x31 = 1), пшеницу IV класса (x45 = 1,5) и частично любую пшеницу (x36 = 4; x46 = 0,5). Потребность элеватора в любой пшенице не удовлетворена на 1,25 тыс. тонн (x56 = 1,25). Минимальные затраты на перевозку составили: Zmin = 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 выражается  как: 

    

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

    c11  = 4 д.е. 

    c24  = 4 + (0,5 + 0,5) = 5 д.е. 

    c41  = 4 + (2 + 2 + 2) = 10 д.е. 

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

    Таблица 3.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 т, поэтому необходимо в таблицу ввести фиктивный тираж B5   с нулевыми затратами. В  связи с тем, что мы составляем модель относительно бумаги, а матрица cij   характеризует себестоимость печатания книги, необходимо исходную матрицу преобразовать относительно единицы бумаги (каждый столбец матрицы cij   разделим на количество бумаги, приходящейся на одну книгу). 

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

    Таблица 3.9 

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

    

 

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

    Таблица 3.10 

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

      

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

     1.3.Метод Фогеля.

 

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

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

2.Транспортная задача в сетевой постановке. 

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

    

 

      Ограничения задачи:  

     

    

 

      Естественное ограничение -- условие  неотрицательности  

    

 

      Задача линейного программирования (1)-(3) называется транспортной задачей  в сетевой постановке. Обозначим через  матрицу инцидентности графа. Тогда в матричной форме задача записывается так:  

    

 

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

    2.1  Доставка груза в кратчайший срок. 

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

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

    Любым способом строим один из опорных планов.

    Определяем  наибольший элемент /' из всех ty, соответствующих занятым клеткам, и все клетки с элементами t_tj > t' (это могут быть лишь свободные клетки) вычеркиваются.

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

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

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

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

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