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

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

Р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