Тема 6. Транспортная логистика. Транспортная задача Презентация подготовлена преподавателем кафедры «Прикладной математики» Тесёлкиной Е.С.

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

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

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

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

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

Постановка транспортной задачи Некоторый однородный продукт, сосредоточенный у m поставщиков A i в количестве a i (i = 1..m) единиц соответственно, необходимо доставить n потребителям B j в количестве b j ( j = 1..n) единиц. Известна стоимость c ij перевозки единицы груза от i-го поставщика к j-му потребителю. Необходимо составить план перевозок, позволяющий вывести все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.

Обозначим через x ij количество единиц груза, запланированных к перевозке от i-го поставщика к j- му потребителю. Тогда стоимость перевозки составит c ij x ij. Стоимость всего плана перевозок выразится двойной суммой Систему ограничений получаем из следующих условий задачи: а) все грузы должны быть перевезены, т.е. б) все потребности должны быть удовлетворены, т.е.

Математическая модель транспортной задачи имеет следующий вид: (1) (2) (3) X ij 0, i = 1..m, j = 1..n (4)

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е. Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется данное условие, называется закрытой моделью; в противном случае – открытой. Для открытой модели может быть два случая: а) суммарные запасы превышают суммарные потребности, б) суммарные потребности превышают суммарные запасы.

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений. Случай «а»: Случай «б»:

Открытая модель решается приведением к закрытой модели. В случае (а), вводится фиктивный потребитель B n+1, потребность которого. В случае (б), вводится фиктивный поставщик A m+1, запасы которого. Как стоимость перевозки единицы груза до фиктивного потребителя (C in+1, i=1,..,m), так и стоимость перевозки груза от фиктивного поставщика (C m+1j, j=1,..,n) полагаются равными нулю, так как груз в обоих случаях не перевозится.

Замечание. Однако возможна ситуация, когда эти стоимости не равны нулю. Например, если: каждая недопоставленная единица продукции облагается штрафом (транспортные расходы на единицу недопоставленной продукции (C m+1j ) равны штрафу за единицу недополученной продукции). продукция имеется в избытке (можно назначить штраф за хранение невывезенной продукции, приняв его за стоимость (C in+1 ) перевозки к фиктивному потребителю). поставщик (s) должен вывезти всю продукцию (стоимость перевозки к фиктивному потребителю необходимо сделать очень высокой: C sn+1 =M).

ТЗ имеет n+m уравнений с mn неизвестными. Матрицу X=(x ij ) m,n, удовлетворяющую условиям (3.2)-(3.4), называют планом перевозок ТЗ. План X*, при котором целевая функция (3.1) обращается в минимум, называется оптимальным. План ТЗ называется опорным, если из его основных коммуникаций (ij;X ij >0) невозможно составить замкнутый маршрут. Опорный план ТЗ содержит не более m+n-1 положительных перевозок.

Решение Решение описанной выше математической модели можно реализовать с помощью надстройки «Поиск решения» в Excel (см. пример «СР_3_Транспортная задача.xlsx»). Кроме того задача может быть решена методом потенциалов. Выбирайте любой удобный для вас способ.

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

Методы составления первоначального опорного плана: 1. метод северо-западного угла, 2. метод минимального элемента. Метод МЭ является вариантом метода СЗУ, учитывающим специфику матрицы C=(c ij ) m,n. Продемонстрировать на примере оба метода.

Задача 1 Заводы фирмы-производителя стиральных машин расположены в А1, А2 и А3. Основные центры распределения продукции сосредоточены в В1 и В2. Объемы производства указанных трех заводов равняются 1000,1500 и 1200 стиральных машин ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 стиральных машин соответственно. Стоимость перевозки по железной дороге одной стиральной машины на один километр равняется примерно 8 копейкам.

Расстояния в километрах между заводами и центрами распределения приведены в следующей таблице: Расстояния можно перевести в стоимость перевозки одной стиральной машины (переводной коэффициент = 0,08 руб./км). В1В2 А А А

Таблица стоимостей (округленных до рубля ) содержит коэффициенты С ij общей модели: Обозначим количество стиральных машин, перевозимых из исходного пункта i в пункт назначения j, через X ij. Поскольку суммарный объем производства стиральных машин равен суммарному спросу, данная модель является сбалансированной транспортной моделью. В1В2 А А А310268

Задача линейного программирования с ограничениями в виде равенств формулируется следующим образом: минимизировать Z=80X X X X X X 32 при ограничениях X 11 +X 12 = 1000, X 21 +X 22 = 1500, X 31 +X 32 = 1200, X 11 +X 21 +X 31 = 2300, X 12 +X 22 +X 32 = 1400, X ij 0 для всех i,j.

Метод потенциалов решения транспортной задачи Для транспортной задачи (ТЗ), как и для любой другой ЗЛП, существует двойственная к ней задача. Обозначим двойственные переменные для каждого ограничения вида (2) через U i ( i = 1,..,m) и вида (3) – V j ( j = 1,..,n), тогда двойственная задача имеет вид: U i +V j C ij, i = 1..m, j = 1..n Переменные задачи, двойственной к транспортной, U i и V j называют потенциалами поставщика и потребителя соответственно.

Для оптимальности плана X=(X ij ) mn ТЗ, необходимо и достаточно существование чисел (потенциалов) V 1,V 2,…,V n и U 1, U 2, …, U m таких, что 1. U i + V j C ij для i = 1,..,m, j = 1,…,n 2. U i + V j = C ij, для тех i, j, где X ij >0 (5)

Из утверждения следует: для того чтобы опорный план был оптимальным, достаточно выполнения следующих условий: а) для каждой занятой клетки (отличного от нуля элемента матрицы X) сумма потенциалов должна быть равна стоимости перевозки единицы груза U i + V j = C ij (6) б) для каждой незанятой клетки (X ij = 0) сумма потенциалов должна быть меньше или равна стоимости перевозки единицы груза U i + V j C ij (7)

Таким образом, для проверки плана на оптимальность необходимо сначала построить систему потенциалов. Для построения системы потенциалов используем условие 2 из утверждения U i + V j = C j, X ij > 0 Систему потенциалов можно построить только для невырожденного опорного плана. Такой план содержит n+m-1 занятых клеток, поэтому для него можно составить систему из n+m-1 линейно-независимых уравнений вида (6) c неизвестными U i и V j. Уравнений на одно меньше, чем переменных, поэтому система является неопределенной и одному неизвестному придают нулевое значение. После этого остальные потенциалы определяются однозначно.

Проверка выполнения условия оптимальности для незанятых клеток. Просматриваем строки и для каждой незанятой клетки проверяем выполнение условия (7), т.е. суммируем потенциалы тех строк и столбцов, на пересечении которых стоит незанятая клетка. Если для всех незанятых клеток U i + V j C ij, то на основании (5) проверяемый план является оптимальным. Если для некоторых клеток U i + V j > C ij, то план не является оптимальным. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину (U i + V j ) – C ij > 0.

Выбор свободной клетки, в которую необходимо послать перевозку Загрузке подлежит в первую очередь клетка, которой соответствует max((U i + V j )-C ij ). Построение цикла и определение величины перераспределения груза. Отыскиваем цикл и начиная движение от клетки, отмеченной знаком «+», поочередно проставляем знаки «–» и «+». Затем находим 0 = min X ij, где X ij – перевозки, стоящие в вершинах цикла, отмеченной знаком «-».

Величина 0 определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение 0 записываем в незанятую клетку, отмеченную знаком «+», двигаясь по циклу, вычитаем 0 из объемов перевозок, расположенных в клетках, которые отмечены знаком «-», и прибавляем к объемам перевозок, находящимся в клетках, отмеченных знаком «+». Если 0 соответствует несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было m+n-1.

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

Определение оптимального плана ТЗ, имеющих некоторые усложнения в их постановке 1. При некоторых реальных условиях перевозки груза из определенного пункта A i в пункт назначения B j не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта A i в пункт B j является сколь угодно большой величиной М и при этом условии известными методами находят решение ТЗ. Такой подход к нахождению решения ТЗ называется запрещением перевозок.

2. В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из A i в B j требуется обязательно перевезти α ij единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки A i и столбца B j, записывают указанное число α ij и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки М. Для полученной таким образом новой ТЗ находят оптимальный план, который определяет оптимальный план исходной задачи.

3. Иногда требуется найти решение ТЗ, при котором из A i в B j должно быть перевезено не менее заданного количества груза α ij. Для определения оптимального плана такой задачи считают, что запасы A i и потребности B j меньше фактических на α ij единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи. Примечание: При целых a i (i = 1,..., m) и b j (j = 1,..., n), в силу специфики ограничений ТЗ, любое базисное допустимое решение является целочисленным.

Задача 2. ТЗ с запрещением перевозки

ТЗ с запрещением перевозки В приведенном примере запрещено перевозить груз от 1 поставщика к 3 потребителю и от 3 поставщика ко 2 потребителю. Чтобы отразить это условие, необходимо в матрице С (затраты на транспортировку 1 ед. груза) проставить максимально большое число в ячейках, соответствующих запрещенным маршрутам.

Задача 3. Многопродуктовая ТЗ с независимыми и взаимозаменяемыми поставками Фирма, имеющая три завода (А1, А2, А3), производит стиральные машины четырех моделей М1, М2, М3, М4. Основные центры распределения продукции расположены в двух пунктах (оптовых базах) В1, В2. Объемы выпуска разных заводов и величины спроса в центрах распределения для каждой модели машины приведены в таблице.

Модель М1М2М3М4Всего Завод AI AII AIII Центр распределе ния BI BII

Стоимость перевозки одной стиральной машины приведена в следующей таблице(матрица С = (С ij ) ): BIBII AI80215 AII AIII10268

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

Полная транспортная таблица Зав оды Мод ели Центры распределения Объе м пр-ва BIBII M1M2M3M4M1M2M3M4 АIАI M3 M4 AIIM1 M2 M4 AIIIM1 M2 Спрос

Заметим, что некоторые маршруты будут недопустимы, поскольку в данной постановке задачи стиральные машины различных моделей не могут заменить друг друга. Например, нельзя осуществлять перевозки из пункта производства стиральных машин марки М1 в пункт доставки стиральных машин модели М4. В табл. запрещенным маршрутам соответствует очень высокая стоимость перевозки М (C ij = M).

Зав оды Моде ли Центры распределения Объе м пр-ва BIBII M1M2M3M4M1M2M3M4 АIАIM3MM80MMM215M700 M4MMM80MMM AIIM1100MMM108MMM500 M2M100MMM108MM600 M4MMM100MMM AIIIM1102MMM68MMM800 M2M102MMM68MM400 Спрос

Можно заметить, что на самом деле задачу не обязательно описывать одной моделью. В силу независимости поставок можно было бы представить задачу по каждой модели машин в виде отдельной таблицы перевозок, но только существенно меньшего размера. Таблицу можно разбить следующим образом: а) модель М1 Заводы Центры распределения Объем производства BIBII AII AIII Спрос

б) модель M2 в) модель М3 Заводы Центры распределения Объем производства BIBII AII AIII Спрос 500 Заводы Центры распределения Объем производства BIBII AI Спрос

г) модель M4 Рассмотрение этих четырех транспортных моделей дает решение, совпадающее с оптимальным решением задачи, соответствующей общей транспортной таблице. С вычислительной точки зрения небольшие подзадачи решить существенно эффективнее, чем одну сложную задачу, представленную в общей ТТ. Заводы Центры распределения Объем производства BIBII AI AII Спрос

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

Задача 4 Решить задачу 3 при дополнительном условии: пусть некоторую часть спроса на одну из моделей можно удовлетворить за счет другой в соответствии со следующими данными: Центр распределения Заменяемая часть спроса в % Взаимозаменяем ые марки BI10 20 M1,M2 M3,M4 BII10 5 M1,M3 M2,M4

Указание Добавьте четыре новых пункта назначения, соответствующие новым комбинациям (M1, M2), (M3, M4), (M1, M3) и (M2, M4). Величины спроса в новых пунктах назначения определяются из данных о процентном соотношении заменяемых моделей. Будете решать задачу на семинаре!!!

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

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

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

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

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

Стоимости в расчете на единицу груза оцениваются на основании данных о маршрутах, соединяющих исходные пункты с пунктами назначения в модели с промежуточными пунктами. Коэффициенты стоимости перевозки между первоначально заданными исходными пунктами и пунктами назначения остаются такими же, как в примере 1. Стоимость перевозки из некоторого пункта в него же ( скажем, из А1 в А1) равна нулю. Стоимость перевозки может меняться в зависимости от направления движения (например, маршрут А1-А2 может отличаться по стоимости от маршрута А2-А1, если используются различные режимы перевозок ).

Транспортная таблица для рассмотренной задачи А1А2А3В1В2 А А А В В

Оптимальное решение рассмотренной задачи А1А2А3В1В2 А А А В В

Решение

Помимо рассмотренной выше возможны другие ситуации, при которых имеет место транзитная перевозка продукции. Например, конечные пункты назначения, куда поступают стиральные машины, могут представлять отдельных продавцов, а не крупные центры распределения. Предположим, что имеется лишь пять продавцов, которые получают свои заказы из центров распределения в В1 и В2. При этом спрос пяти продавцов, составляет 800, 500, 750, 1000 и 650 стиральных машин. Предположим, что продавец может получать товар из любого центра распределения. В данном случае промежуточными пунктами могут быть только центры распределения.

Модель с промежуточными пунктами B1B2M1M2M3M4M5 A1A180215MMMMM1000 A2A MMMMM1500 A3A310268MMMMM1200 B10M B2M

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

MMMMM MMMMM MMMMM

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

Оптимальное распределение оборудования Оборудование m различных видов нужно распределить между n рабочими участками. Производительность единицы оборудования i-го вида на j-м рабочем участке равна равна p ij; ; i = 1,…, m; j = 1,…, n. Потребность j-го участка в оборудовании составляет b j, j = 1,…,n. Запас оборудования i-го вида равен a i, i = 1,…, m. Найти распределение оборудования по рабочим участкам, при котором суммарная производительность максимальна. Данная задача относится к классу ТЗ при условии, что производительность линейно зависит от количества используемого оборудования. Поставщиками в задаче являются различные виды оборудования, потребителями – рабочие участки.

Обозначим через x ij число единиц оборудования i-го вида, выделенное на j-й рабочий участок, i = 1,…, m; j = 1,…, n. Математическая модель задачи имеет следующий вид: P =,, i = 1,…, m;, j = 1,…, n; ; x ij 0, i = 1,…,m; j = 1,…, n.

Формирование оптимального штата фирмы Фирма набирает штат сотрудников. Она располагает n группами различных должностей по b j вакантных единиц в каждой группе, j = 1,…, n. Кандидаты для занятия должностей проходят тестирование, по результатам которого их разделяют на m групп по а i кандидатов в каждой группе, i = 1,…, m. Для каждого кандидата из i-ой группы требуются определенные затраты с ij на обучение для занятия j-ой должности, i = 1,…, m; j = 1,…, n: с ij = 0, т.е. кандидат полностью соответствует должности, c ij =, т.е. кандидат вообще не может занять данную должность. Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение.

x ij 0, i = 1,…, m; j = 1,…, n.

Задача календарного планирования производства Рассмотрим задачу календарного планирования производства на N последовательных этапах. Спрос изменяется во времени, но детерминирован (определен). Его можно удовлетворить либо путем изменения уровня запаса при постоянном объеме производства, либо за счет изменения объема производства при постоянном уровне запаса, либо путем изменения и уровня запаса, и выпуска.

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

Введем следующие обозначения для этапа i; i = 1,2,..., N: c i – производственные затраты на единицу продукции при обычном режиме работы; d i – производственные затраты на единицу продукции при работе в сверхурочное время (d i > c i ); h i – затраты на хранение единицы продукции, переходящей из этапа i в этап i + 1; p i – потери от дефицита на единицу продукции, требуемой на этапе i, но поставляемой на этапе i + 1; a ri – производственная мощность (в единицах продукции) при обычном режиме работы; a ti – производственная мощность (в единицах продукции) при работе в сверхурочное время; b i – спрос (в единицах продукции).

Модель без дефицита В соответствии с терминологией транспортной модели поставщики представлены обычным и сверхурочным производством для различных этапов. Потребители задаются спросом соответствующих этапов. Затраты на «транспортировку» единицы продукции от любого поставщика к любому потребителю представляются суммой соответствующих производственных затрат и затрат на хранение единицы продукции.

Матрица полных затрат для эквивалентной транспортной задачи приведена в следующей таблице: спрос на этапе j избыток N R1R1 C1C1 C 1 + h 1 C 1 + h 1 + h 2 C 1 + h 1 + …+ h N–1 0a R1 T1T1 d1d1 d 1 + h 1 d 1 + h 1 + h 2 d 1 + h 1 + …+ h N–1 0a T1 R2R2 C2C2 C 2 + h 2 C 2 + h 2 + …+ h N–1 0a R2 T2T2 d2d2 d 2 + h 2 d 2 + h 2 + …+ h N–1 0a T2... RN CNCN 0a RN TN dNdN 0a TN b1b1 b2b2 b3b3...bNbN S

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

Так как задолженность в модели не допускается, то для каждого этапа k в нее необходимо включить ограничение, состоящее в том, что накопленный спрос не должен превышать соответствующий общий объем произведенной продукции, т.е., k = 1, 2,..., N.

Так как спрос на этапе i должен быть удовлетворен прежде, чем спрос на этапах i + 1, i + 2,..., N, и поскольку на функцию производственных затрат наложены специальные требования, нет необходимости применять общий алгоритм решения транспортной задачи. Сначала путем последовательного назначения максимально возможных поставок по наиболее дешевым элементам первого столбца удовлетворяется спрос на этапе 1.

Затем корректируются значения a i, которые после этого определяют оставшиеся мощности для различных этапов. Далее рассматривается этап 2, и его спрос удовлетворяется наиболее дешевыми поставками в пределах новых ограничений на производственные мощности. Процесс продолжается до тех пор, пока не будет удовлетворен спрос этапа N.

Модель с дефицитом Рассмотрим обобщение описанной выше модели при условии, что допускается дефицит. Предполагается, что задолженный спрос должен быть удовлетворен к концу N-этапного горизонта планирования. Таблицу 1 можно легко модифицировать, чтобы учесть влияние задолженности, введя соответствующие удельные издержки в заблокированные маршруты.

Так, например, если p i – удельные потери от дефицита (т.е. на единицу продукции) в случае, когда продукция требуется на этапе i, а поставляется на этапе i + 1, то удельные расходы, соответствующие ячейкам (R N,1 ) и (T N,1 ), составляют: {c N + p 1 + p 2 + …+ p N–1 } и {d N + p 1 + p 2 + …+ p N–1 } соответственно. Заметим, что в общем случае описанный выше алгоритм может не привести к оптимальному решению.