Реализация транспортной задачи в матричной постановке. Вариант № 8

Цели  задания:

1. понимать смысл, различать, осознанно использовать следующие понятия: транспортная задача (ТЗ) в матричной постановке; открытая и закрытая модели ТЗ; транспортная таблица, допустимый, опорный, оптимальный планы ТЗ; поставки, перераспределение поставок, потен­циалы строк и столбцов транспортной таблицы как двойственные оцен­ки; характеристики клеток транспортной таблицы, цикл пересчета; альтернативные решения ТЗ;

2. получить навыки, уметь: строить математическую модель ТЗ; переходить от открытой модели ТЗ к закрытой; использовать различ­ные методы для построения опорных планов ТЗ; решать ТЗ методом потенциалов; анализировать полученное решение и находить альтерна­тивные варианты; интерпретировать полученное решение в терминах

поставленной задачи.

   Условие задачи: транспортная фирма обслуживает n поставщиков однородного груза и m потребителей этого груза. В течение дня из каждого пункта пос­тавки фирма должна вывезти соответственно a₁, А₂,,.. , А_n тонн гру­за, а в каждый пункт потребления доставить соответственно В_i, В₂,..., В_m тонн. Себестоимость перевозки 1 тонны груза от i-го поставщика j-му потребителю составляет С_ij тыс. руб.

     Найти такой план перевозки грузов, при котором издержки транс­портной фирмы будут минимальными.

 Задание:записать математическую модель задачи. Построить опорные планы методом северо-западного угла, методом минимального элемента и ме­тодом Фогеля. Сравнить результаты. Опираясь на любой из полученных планов, решить задачу методом потенциалов. Решить задачу на ПЭВМ с помощью ПЭР и сравнить результаты с полученными ручным способом.

            Исходные данные для 8 варианта:        n=3,m=5;A₁=400,A₂=265,A₃=515;                 B₁=220,B₂=230,B₃=250,B₄=220,B₅=310;

Чтобы решить данную задачу необходимо и достаточно, чтобы суммарная мощность всех поставщиков равнялась суммарной мощности всех потребителей, т.е. , а т.к. у нас < , то есть запасов товара на складе меньше, чем потребности покупателей, то необходимо ввести дополнительного (фиктивного) поставщика А₅ = .

 Построим начальный опорный план (НОП) задачи 3 способами: методом северо-западного угла, методом Фогеля и методом минимального элемента. После каждой заполненной таблицы будем поверять условие ее невырожденности: ЧЗК = m + n –1. Если оно не выполняется, выбираем любую свободную клетку и заносим в нее 0, считая занятой, так, чтобы не образовалось цикла из занятых клеток.

1.  НОП, построенный методом северо-западного угла.

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

                                                   X =  

Z = 220*15 + 180*17 + 50*11 + 215*13 + 35*16 + 220*18 + 260*17 + 50*0 = 18645 тыс.руб.

2.  НОП, построенный методом Фогеля.

     Чтобы построить начальную таблицу методом Фогеля, необходимо сначала найти разность между двумя наименьшими тарифами для каждой строки и столбца (соответственно: Δ и Δ) После чего из полученных результатов находим наибольшее значение [в нашем случае -  это число 13] и начинаем заполнение таблицы именно с этой строки\столбца [у нас - столбец В₃]. В найденной строке/столбце находим наименьший тариф и заполняем данную клетку [А₄В₃]. Затем аналогичным способом  заполняем следующие клетки, при условии, что если потребности покупателя удовлетворены полностью или запасы на складе полностью использованы,  мы больше не учитываем соответствующий столбец/строку при расчете Δ. Полученная таблица выглядит следующим образом: