книги из ГПНТБ / Коробов Г.Ю. Совершенствование снабжения с применением ЭВМ

при условиях

т

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

пт

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

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

240

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

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

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

Р3 — 2 и равно —6. Вычисление сводится к тому, что эта

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

Расчет на примере контура квадрата Р$—2 приведен в табл. 40.

Из таблицы видно, что наименьшей величиной из всех квадратов с отрицательными вершинами является число 30 в квадрате Р3 —4. Согласно описанному выше пра­ вилу, оно прибавляется к числу 20 с положительным значением в квадрате Рг—4 и вычитается из числа 50 с отрицательным значением в квадрате Р^—2. В резуль­ тате мы получаем новое прикрепление потребителей к по­ ставщикам (числа обведены кружками), по которому в сравнении с исходным вариантом прикрепления суммар­ ные затраты на транспортировку уменьшились на 180 единиц (30X1 + 10X4 + 20X5 + 40X2 + 50X1+30X1 = = 330; 510—330=180 единиц). Новый план прикрепления представлен в табл. 41.

246

Т а б л и ц а 41

/=1

Полученные результаты подвергаются анализу с тем, чтобы выявить возможность дальнейшей оптимизации плана прикрепления потребителей к поставщикам и до­ полнительного снижения транспортных расходов. Для этого по каждому свободному квадрату вновь очерчива­ ются контуры и по описанной методике с применением «метода северо-западного утла» рассчитываются алгебра­ ические суммы чисел, расположенных в верхних правых углах квадратов каждого контура. Применительно к вновь полученному варианту прикрепления, который отражен в табл. 41, строятся контуры свободных квадра­ тов. Контуром квадрата Р2— 1 явится прямоугольник с вершинами квадратов Р 2 — 1 , Pi—2, Р\—2 и Р\—1. Тогда алгебраические суммы чисел определяются следующим образом:

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

Весьма распространенным методом решения транс­ портных задач линейного программирования по при-

247

креплению потребителей к поставщикам является метод Лурье — Брудно, преимущества которого состоят в воз­ можности легко понять его экономическое содержание. Этот метод принято также называть методом дифферен­ циальных рент, или методом вычеркивающей нумерации. Прикрепление потребителей к поставщикам этим методом начинается с наиболее выгодных расстояний перевозки, т. е. способом предпочтительного прикрепления, и только после этого, по мере необходимости, в план прикрепления последовательно включаются перевозки на большие рас­ стояния. Тем самым, исходя из имеющихся ресурсов по­ ставщиков и фондов потребителей, обеспечивается полу­ чение оптимального плана прикрепления. Он считается составленным тогда, когда все резервы поставщиков оказываются распределенными.

Этот метод весьма прост и обладает рядом других преимуществ. Он отличается, в частности, относительно небольшим количеством вычислений на каждой итера­ ции; удобен для расчетов на ЭВМ по матрицам больших размеров; не имеет «вырождений», т. е. случаев, когда за­ дача не может быть решена при некоторых условиях, не предусмотренных общим алгоритмом; всегда позволяет оценивать, насколько полученное прикрепление на любой итерации отличается от оптимального.

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

160 единиц). Для выполнения вычислений заносим исход­ ные данные в таблицу-матрицу (табл. 42).

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

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

248

щиком является поставщик А\ (2). Эти кратчайшие рас­ стояния отмечаются кружками. В случае, если в какомлибо столбце окажется несколько одинаковых наимень­ ших расстояний, то кружком отмечается одно любое из них.

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

После этого по каждому поставщику (строке табли­ цы) определяется разность между его ресурсами и наме­ ченным первоначальным вариантом плана объемом поставок материалов всем потребителям или так называе­ мая избыточность ( + ) или недостаточность (—) постав­ щика. Анализ матрицы показывает, что по первоначаль­ ному плану распределения исчерпаны не все ресурсы

243