Файл: Коробов Г.Ю. Совершенствование снабжения с применением ЭВМ.pdf

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

2. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ

Одним из распространенных методов линейного про­ граммирования, применяемых для решения транспортных задач, является так называемый распределительный ме­ тод. Сущность и порядок расчетов этим методом рассмот­ рим на числовом примере.

В качестве условия задачи и исходных данных при­ мем, что имеется три поставщика Р\, Р% Р% с ресурсами соответственно 40, 110 и 30 единиц, а также четыре по­ требителя с потребностью (фондом) у первого 30, у вто­ рого 60, третьего 40 и у четвертого 50 единиц материала. Затраты на перевозку единицы материала даны в табл. 37.

Неизвестной величиной здесь является количество ма­ териалов, отправляемых поставщиками различным по­ требителям. Задача состоит в таком прикреплении потре­

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

пт

Для удобства выполнения расчета этим методом за­ несем исходные данные в специальную таблицу (табл. 38).

Решение задачи начинается с построения исходного варианта перевозки путем заполнения левого верхнего угла и кончается заполнением правого нижнего угла. Этот специфический прием для составления исходного вариан­ та прикрепления потребителей к поставщикам в литера­ туре получил название «метода северо-западного угла». При построении исходного варианта прикрепления потре­ бителей к поставщикам во внимание принимаются только

242

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

При этом распределение материалов из ресурса по­ ставщика по потребителям, как это видно из табл. 38, осуществляется ступенчатым образом, так чтобы число заполненных квадратов было на единицу меньше суммы числа поставщиков и числа потребителей. Если обозна­ чить количество поставщиков п, а количество потребите­ лей т, то число занятых квадратов таблицы должно быть п + т—1. В нашем примере это число должно быть равно

удовлетворены, мы получим исходный вариант прикреп­

мере равны ЗОХ 1 + 10X4 + 50x5 + 40X2 + 20x1 + 30x3 = = 510 единиц.

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

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

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

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

244

Т а б л и ц а 39

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

Обозначив поставщиков в нашем примере Pi, Рг и Р3, а потребителей 1, 2, 3 и 4, определим алгебраические

Как видно из приведенных данных, два свободных квадрата (Рз—2 и Р3 —3) из шести рассмотренных имеют отрицательные значения. Это говорит о том, что имеется возможность оптимизации исходного плана прикрепления потребителей к поставщикам. Оптимизация может быть достигнута за счет одного из свободных квадратов с

245