Экономико-математическая модель транспортной задачи.

Транспортная задача является специальным типом задач линейного программирования.

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

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

.

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

При решении задачи используется свойство, которое состоит в том, что ранг матрицы A задачи (4.24) на единицу меньше числа уравнений r(A) = m + n – 1. С учетом этого число ненулевых переменных Xij > 0 в опорном плане будет не больше (m + n – 1).

Если число ненулевых Хij в опорном плане равно (m + n – 1), то план называется невырожденным, иначе – вырожденным.

Для решения задачи составляется табл.:

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

Алгоритм решения задачи состоит из двух частей: построение начального опорного плана (набора чисел Xij > 0), удовлетворяющих соотношениям и построение оптимального плана.

Построение начального плана перевозок

Есть несколько методов построения начального опорного плана: метод северо-западного угла, метод минимального элемента и другие.

Рассмотрим метод минимального элемента.

1. Выбирают клетку табл. 4.4 с минимальным значением cij, в которую записывают min (ai, bj).

2. Из запаса i-го поставщика и потребностей j-го потребителя вычитают эту величину. Из дальнейших рассмотрений исключают поставщика, запасы которого исчерпаны и потребителя, спрос которого полностью удовлетворен.

3. Повторяют шаг 1 до тех пор, пока все запасы продукции не будут исчерпаны. Метод северо-западного угла отличается от метода минимального элемента тем, что клетки заполняют последовательно по строкам, начиная с элемента Х11.

Построение оптимального плана

Для построения оптимального плана перевозок используется метод потенциалов, который является формой симплекс-алгоритма.

Здесь могут быть два варианта.

Вариант 1. Если опорный план вырожден, то в свободные клетки с минимальными значениями Сij записывают перечеркнутые нули 0, (фиктивные поставки), пока не получат невырожденный план. Число 0 считается очень малой положительной величиной. Дальше задача решается методом потенциалов.

Вариант 2. Опорный план невырожден, поскольку количество ненулевых Хij равно m + n – 1.

1. Для Xij > 0 составляется система уравнений:

ui + vj = cij. (4.26)

Неизвестные ui, vj называются индексами (потенциалами).

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

После решения системы (4.26) для свободных клеток таблицы определяют потенциалы

Sij = Сij – (ui + vj). (4.27)

3. Если все Sij ≥ 0, то полученный план оптимальный. Иначе выбирают клетку с минимальным Sij < 0. Начиная с выбранной клетки матрицы перевозок, стоится замкнутый прямоугольный цикл (цепочка) с вершинами в заполненных клетках (в том числе символом 0).

Выбранной клетке присваивается знак «+», следующей вершине цикла по (или против) часовой стрелке – знак «–», далее «+», «–», и т.д. по циклу.

Данная цепочка знаков обязательно заканчивается знаком «–». Цепочка называется вырожденной, если она состоит из одного элемента.

Среди клеток цикла, отмеченных знаком «–», выбирается клетка с

Наименьшим значением переменной Хij, затем из нагрузки клеток, отмеченных знаком «–», вычитают это значение, а клетки, отмеченных знаком «+», прибавляют это значение. Получают новый опорный план, который проверяют на невырожденность и в случае необходимости выполняют переход к невырожденному по варианту 1.

После этого осуществляется переход к шагу 1.

 

16. ТЗ. Построение исходного базисного плана.

Допустимый план х = (x₁,..., x_n)^T называется базисным планом задачи (4.1), если у него найдется n — m нулевых компонент и при этом остальным компонентам х_j1,..., х_jm будут соответствовать линейно независимые столбцы матрицы А: A_j1, …, A_jm. Набор этих столбцов называется базисом этого базисного плана. Если у базисного плана т положительных компонент, т.е  х_j1> 0,... X_jm > 0, то он называется невырожденным. В противном случае, т.е. если у него положительных компонент меньше, то его называют вырожденным.

< С, х> —> max, Ах = b, х > = О_n,

где х = (x₁,..., x_n) ^T принадл. Rⁿ.c = (с1,..., с_n) ^T принадл. Rⁿ_, , b = (b₁,..., b_m) принадл. R^m. Матрица А размерности m на n.

Метод северо-западного угла. Назначение перевозок х_ij начинаем с верхней левой клетки (северо-западного угла) таблицы. Положим х₁₁ — min (а1, b1). Если a1> b1 то Х11= b1 вычеркиваем из матрицы столбец j = 1, так как спрос первого потребителя полностью удовлетворен. Если a1< b1 то х11 = а1, вычеркиваем строку i=1, так как в этом случае полностью исчерпаны запасы первого поставщика. Если а1 = b1 то вычеркиваем и строку i = 1, и столбец j=1 одновременно. Вычеркнув ряд, соответствующий min (a1, b1) скорректируем запасы и потребности первого поставщика и первого потребителя на величину x11. С оставшейся матрицей поступим аналогично предыдущему. Продолжая действовать по этой схеме, исчерпаемзапасы поставщиков и удовлетворим запросы потребителей. На последнем шаге процесса получится матрица 1 х 1, в которой одновременно вычеркиваем и строку, и столбец. Метод северо-западного угла не учитывает матрицу тарифов, поэтому начальный план может оказаться далеким от оптимального. Более близким к оптимальному обычно является план, построенный методом минимальной стоимости.

Метод минимальной стоимости. Находим min c_ij =с_i0j0. Аналогично предыдущему способу, если а _i0> b_i0. то x_i0j0=b_j0, вычеркиваем столбец j0, запасы поставщика i0 корректируем, т. е. считаем равными a_i0 - x_i0j0 если я а _i0< b_i0, то x_i0j0=a_i0, вычеркиваем строку i0, запасы потребителя j0 считаем равными b_j0- x_i0j0 , если же а i0 = b jo, то x_i0j0=аi0 =bj0., вычеркиваем и строку i=i_{0 и} столбец j=j₀ одновременно. Вычеркнув один из рядов матрицы и скорректировав запасы либо поставщика, либо потребности получателя на величину x_i0j0 оставшейся матрицей меньшего размера поступаем аналогично предыдущему. На последнем шаге в матрице 1 х 1 одновременно убираем и строку, и столбец. Построенный начальный план перевозок должен быть базисным, т. е. число назначенных перевозок Хij должно быть равно m + n -1. Если это условие не выполняется, а условие общего баланса выполнено, то построенный начальный план — вырожденный. Для построения базисного плана в исходный план вводят нулевые перевозки так, чтобы не образовывался замкнутый контур из назначенных перевозок. Заполнение клеток нулем не влияет на экономическую оценку решения, но оно необходимо для получения начального базисного плана и для поиска оптимального решения.

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

Рисунок 2.1 - Примеры форм замкнутых контуров

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

 

17. ТЗ. Метод потенциалов.

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

По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:

Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

Рассмотрим подробнее процесс определения потенциалов текущего плана транспортной задачи. Потенциал первого пункта потребления принимаем равным нулю

Теперь, зная его, мы можем определить потенциалы для всех пунктов производства, связанных с первым пунктом ненулевыми перевозками.

Для свободных клеток транспортной таблицы вычисляются величины

называемые разностями потенциалов. В таблице они выписаны для всех небазисных клеток под ценами.

Разность потенциалов можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j.

Процесс «улучшения» плана состоит в определении вводимой и выводимой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

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

В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины: нечетные — знаком «+», а четные знаком «—». Знаком «+» отмечаются те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком «—» — те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком «—», выбирается клетка с наименьшим значением.

Она и становится кандидатом на вывод, т. к. уменьшение объема перевозок на большую величину может привести к отрицательным значениям x_{i, j} в других «минусовых» клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком «+», добавляется объем q, а из объемов клеток, помеченных знаком «—», он вычитается. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описанные выше действия повторяются.

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

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

 

 

Модели управления запасами. Основные понятия

Запас — все то, на что имеется спрос и что временно исключено из потреб­ления. Запасы подразделяются на:

1. запасы средств производства, предназначенные для производ­ственного потребления (сбытовые, производственные, государственные резервы и незавершенное производство),

2.  запасы предметов потребления, предназначенные для использования в непроизвод­ственной социально-экономической сфере и удовлетворения потребностей людей (товарные, запасы предметов коллективного и индивидуального потребления и государственные резервы).

Основные причины создания запасов:

- необходимость обеспечения бесперебойного снабжения производственного процесса,

- периодичность производства различных видов продукции поставщиками,

- транспортировка большинства видов продукции партиями от поставщика к потре­бителю,

- несовпадение ритма производства с ритмом потребления.

Причины, побуждающие предприятия к уменьшению запасов:

- плата за физическое хранение запасов,

- отвлечение денежных средств, вложенных в них потери от естественной убыли,

- моральный износ.

Предмет теории управления запасами — это отыскание такой организации поставок или производства, при которой суммарные затраты на функционирование системы минимальны. Ор­ганизация поставок — определение объемов поставок и периодичность заказов.

Существует 4 основных вида затрат, которые могут оказать влияние на выбор решения по управлению запасами:

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

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

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

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

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

1. де­терминированным

a. статический (посто­янный во времени)

b. динамический (изменяющийся во времени);

2. случайным

a. стационарный (с постоянной во времени плотностью вероятности)

b. нестационарный.

Детерминированный спрос точно известен заранее, в отличие от вероятностного спроса. При статическом типе спроса интенсивность потребления ресурса остается неизменной во времени, при динамическом типе спроса интенсивность потребления изменяется в зависимости от времени. При стационарном типе спроса его функция плотности вероятности неизменна во времени, а при нестационарном - функция плотности вероятности спроса изменяется во времени.

Те­кущие за­пасы - часть сред­не­го за­паса, под­ле­жащая ре­гуляр­но­му до­пол­не­нию.
Стра­ховые за­пасы - часть сред­них за­пасов, слу­жащая за­щитой от не­оп­ре­делен­ности.
За­пасы в пу­ти - за­пасы, ко­торые на­ходят­ся в пу­ти или ждут транс­пор­ти­ров­ки.
Точ­ка за­каза - объ­ем за­каза, по дос­ти­жении ко­торо­го мы осу­щест­вля­ем за­каз:
Ви­ды конт­ро­ля за сос­то­янием за­пасов:
• неп­ре­рыв­ный (в каж­дый мо­мент вре­мени мы мо­жем точ­но оп­ре­делить объ­ем за­пасов на скла­дах) - вле­чет за со­бой до­пол­ни­тель­ные из­держ­ки, свя­зан­ные с пос­то­ян­ным конт­ро­лем за за­па­са­ми;
• пе­ри­оди­чес­кий (пе­ри­оди­чес­ки про­из­во­дит­ся ин­вента­риза­ция и вы-f вля­ет­ся ре­аль­ное сос­то­яние за­пасов) - ме­нее зат­ратный, но мо­жет при­вес­ти к де­фици­ту в слу­чае, ес­ли за­пасы за­кон­чи­лись до ин­вен­та­ри­за­ции;
• сме­шан­ный (за на­ибо­лее важ­ны­ми за­паса­ми ус­та­нов­лен неп­ре­рыв­ный конт­роль, за ме­нее важ­ны­ми - пе­ри­оди­чес­кий) - поз­во­ля­ет отс­ле­живать кри­тичес­кие за­пасы (нап­ри­мер, до­рогос­то­ящие комп­лек­ту­ющие, участ­ву­ющие в про­из­водс­тве) и пе­ри­оди­чес­ки конт­ро­лиро­вать ме­нее важ­ные за­па­сы (нап­ри­мер, за­па­сы кан­це­лярс­ких то­ва­ров).

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: