ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


4.1. Общая постановка транспортной задачи.

Транспортная задача является одной из важнейших частных задач линейного программирования. Специфические методы ее решения проще общей задачи. Название свое задача получила потому, что впервые была сформулирована и поставлена для решения вопроса о наиболее рациональном планировании перевозок на транспорте. Название это условно, так как с ее помощью можно решать разнообразные задачи из различных отраслей производства и не обязательно связанных с перемещением. Методы решения транспортной задачи широко применяют на автомобильном, железнодорожном и других видах транспорта для планирования перевозок различных грузов. Это объясняется их простотой и экономическим эффектом, который они дают. Планы перевозок, разработанные на основе алгоритма транспортной задачи, как правило, на 12—18% экономичнее планов, составленных без применения математических методов.

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

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

Сформулируем транспортную задачу.

В лесозаготовительном объединении имеются А1, А2, ... ..., Аm лесозаготовительных предприятий {ЛЗП), вырабатывающих технологическую щепу в объеме Q1, Q2, .... Qm тысяч кубометров в год. Технологическая щепа должна быть доставлена потребителям (ЦБК) В1, В2, ….., Вn, имеющим соответственно объемы потребления Y1, Y2. … Yn тысяч ку­бометров в год. Стоимость доставки щепы с каждого ЛЗП каждому потребителю определяется матрицей стоимостей:

(4.1)

Объем выработки щепы всеми ЛЗП равен объему потребления всеми ЦБК:

(4.2)

или

(4.3)

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

(4.4)

или

(4.5)

При этом необходимо, чтобы соблюдались условия:

1. Суммарный объем щепы, вывозимой с каждого ЛЗП потребителям, должен равняться его мощности:

(4.6)

 

или

(4.7)

где i=1,2,……m.

2. Суммарный объем щепы, доставляемой на каждый ЦБК от ЛЗП, должен равняться его потребности:

(4.8)

или

(4.9)

где j=1,2,……n.

3.Объемы доставки щепы не могут быть отрицательными, но могут равняться нулю:

(4.10)

4.Уже известное (4.3)

Математически сформулированная транспортная задача ли­нейного программирования:

m+n+2 уравнений,

mxn+1 неизвестных.

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

Найти минимум функции

(4.11)

При заданных условиях

(4.12)

(4.13)

(4.14)

(4.15)

Функция называется целевой функцией или

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

4.2. Общий алгоритм решения транспортной задачи

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

Алгоритм заключается в том, что сначала, строится какой-либо первоначальный допустимый план, затем проверяется, является ли план оптимальным, если план оптимальный — задача решена, если не оптималь­ный— отыскивается другой, но обязательно улучшенный и вновь проверяется на оптимальность. Шаги 2 и 3 повторяются до тех пор, пока очередной улучшенный план не будет оптимальным.

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

 

4.3. Методы построения начального плана

Существует несколько методов построения начального плана, который иногда называют опорным решением. Наибо­лее распространенные из них: метод северо-западного угла, метод наименьшей стоимости, двойного предпочтения, по приоритету ближайших пунктов, способ Фогеля, способ Ле­бедева— Тихомирова и др. Рассмотрим простейшие из них.

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

Решение удобно выполнять в табличной форме. Для это­го составляется рабочая таблица в которой в строке слева указываются поставщики (А1, А2, ..., Аm) и их мощности, в верхней строке указываются потребители (В1, В2, ..., Вn) и их спрос. В клетках таблицы в верхних левых углах указы­ваются единичные стоимости (С11С12 …….. Сmn), т. е. затраты на доставку единицы продукции от соответствующего поставщика Аi (i=1, 2, .... m) соответствующему потребителю Bj (j=1,2,..:,n).

Рассмотрим конкретный пример решения задачи. Три лесозаготовительных предприятия 1, A2, А3) заготовляют пи­ловочник в объемах соответственно 300, 600 и 500 тыс. м3 в год и поставляют четырем деревообрабатывающим пред­приятиям 1, В2, В3, В4). Годовой объем потребления пило­вочника деревообрабатывающими предприятиями равен 450, 400, 200 и 350 тыс. м3. Стоимость доставки сырья от ЛЗП к деревообрабатывающим предприятиям представлена матри­цей стоимостей, показанной в табл. 4.1. цифрами Сij в левых верхних углах клеток рабочей таблицы.

 

Таблица 4.1.

Исходные данные для решения транспортной задачи линейного программирования (рабочая таблица).

Поставщики и их мощности, тыс.куб. м. Потребители и их спрос, тыс.куб.м.
В1 В2 В3 В4
А1
А2
А3

Согласно методу северо-западного угла распределение поставок от поставщиков к потребителям начинается с клет­ки А1B1 Сравниваем мощность первого поставщика А1 (300) с потребностью потребителя B1 (450). Меньшую величину (300) помещаем в клетку А1B1 и вычитаем ее из обеих срав­ниваемых величин. В итоге в остатке первой строки простав­ляется 0, а в итоге первого столбца остаток 450—300=150 (табл.4.2.). Первую строку из дальнейшего рассмотрения исключаем. Поскольку остаток оказался в первом столбце, следующую поставку назначаем в соседнюю клетку А2B1. Сравнивая итоги второй строки (600) и первого столбца (остаток 150), устанавливаем величину поставки, равную 150. Вычтя эту поставку из сравниваемых величин, в итоге первого столбца проставляем 0, а в итоге второй строки за­писываем разницу 600—150 = 450. На третьей итерации, срав­нивая потребность потребителя второго столбца B2=400 и остаток мощности второго поставщика А2 = 450, меньшее зна­чение записываем в клетку А2B2. В остатке второго столбца остается 400—400 = 0, а второй строки 450—400 = 50, что и записываем в остаток по строке в результате третьей итера­ции. Продолжая этот процесс, распределяем поставки по всей таблице. Итог распределения поставок приведен в табл. 4.2.

Таблица 4.2.

Построение опорного плана методом северо-западного угла.

Поставщики и их мощности, тыс.куб. м. Потребители и их спрос, тыс.куб.м. Остатки по строкам итерации
В1 В2 В3 В4
А1              
А2        
А3          
Остатки по столбцам Итерации        
     
     
     
     
     

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

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

Рассмотрим еще один способ составления начального плана - способ минимального элемента.

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

Сущность его заключается в следующем.

В матрице стоимостей отыскивается клетка с минималь­ным значением Cij и в эту клетку записывается поставка Xij =min (ai bj). Если матрица содержит несколько одинако­вых минимальных значений Cij, то выбирают любое одно.

После этого вычеркивается строка или столбец. Если ai> bj, вычеркивают столбец, при ai < bj вычеркивают стро­ку.

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

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

Рабочая таблица имеет форму, приведенную в табл. 4.3.

 

 

Таблица 4.3.

Построение опорного плана по методу минимального элемента.

Поставщики и их мощности, тыс.куб. м. Потребители и их спрос, тыс.куб.м. Нераспределенные мощности на шагах
В1 В2 В3 В4
А1        
А2          
А3  
Неудовлетворенный спрос на шагах            
           
             
             
               
               
                         

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

Шаг 1. Находим минимальное значение стоимости Cij. В нашем случае это будет C21 = 4. В эту клетку таблицы за­писываем возможную поставку, т. е. минимальную из А2 и В1, Сравнивая А2 = 600 и В1 = 450, записываем в клетку Х21 поставку 450. Вычисляем нераспределенные мощности по­ставщиков и неудовлетворенный спрос потребителей.

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

Потребитель В2 неудовлетворен, его спрос остался рав­ным 400, что и записываем во вспомогательной части табли­цы.

Потребитель В3 — неудовлетворен, спрос остался — 200.

Потребитель В4 — неудовлетворен, спрос —350.

Поставщик А1 — мощность его не распределена, остаток нераспределенной мощности, равный 300, записываем во вспомогательной части таблицы справа.

Поставщик А2 — часть мощности распределена потреби­телю В1 но осталась нераспределенной мощность 600—450 = = 150, что и записываем во вспомогательную часть таблицы, как нераспределенную мощность на первом шаге.

Поставщик А3 — мощность его не распределена и запи­сываем результат нераспределенной мощности 500.

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

Шаг 2. Находим минимальное значение стоимости Cij без вычеркнутого столбца В1 это значение С33 =5. Записы­ваем в эту клетку возможную поставку-минимум из А3 = 500 и В3=200, min=200, записываем нераспределенные мощно­сти и неудовлетворенный спрос на этом шаге и их сумму, равную 750, и вычеркиваем из дальнейшего рассмотрения столбец у которого спрос удовлетворен.

Шаг 3. Минимальный элемент А2В2 = 7. В эту клетку записываем минимальное значение из нераспределенной мощ­ности А2=150 и спроса В2=400, min=150. В результате третьего шага мощность поставщика А2 исчерпана, а сумма нераспределенных мощностей и неудовлетворенного спроса осталась равной 600. Продолжая аналогично, доводим рас­пределение до конца,

Шаг 4. Минимальное Cij из оставшихся имеют клетки А1В2 и А3В2 — выбираем А3В2. Записываем сюда поставку 250 как минимум из значений остатка потребителя В2 и по­ставщика А3 и так далее.

Результат распределения по методу минимального элемента показан в табл. 4.3.

Вычисляем значение целевой функции полученного начального решения:

R= 10* 300 + 4 *450 + 7 *150 + 8 *250 + 5*200+ 12*50 = 9450 тыс. руб.

Видим, что это решение более целесообразное, чем полученное методом северо-западного угла. Но это не значит, что полученное решение оптимальное.

 

4.5. Проверка решения на оптимальность

Перейдем ко второму этапу решения задачи — проверке полученного решения на оптимальность.

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

Условимся называть клетки, заполненные поставками — базисными, клетки, где нет поставки — свободными.

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

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

Для того, чтобы не нарушался баланс поставщика А1 не­обходимо уменьшить поставку от этого поставщика потре­бителю В4 на единицу, но чтобы не нарушилась поставка по­требителю В4, необходимо увеличить ему поставку от по­ставщика А3 на единицу. В свою очередь, чтобы не нарушил­ся баланс поставщика А3 необходимо уменьшить от него по­ставку потребителю В2, а потребителю В2 увеличить постав­ку от поставщика А2. Теперь, чтобы не нарушался баланс поставщика А2, необходимо уменьшить от него поставку потре­бителю В1.

Результат этих перестановок можно изобразить схемой, приведенной на рис. 2. В результате выполненных переста­новок мы опять получили допустимое решение. Если выпол­нить эти перестановки в начальном решении, то произойдет изменение стоимости перевозок. Определим, к чему это приведет. Стоимость поставки потребите­лю В1 от поставщика A1 т. е. cтоимость поставки A1В1 увели­чится на C11 = 6*1 = + 6.

 

 

 

Рис. 4.1. Перераспределение единичных поставок для клетки A1В1

 

Стоимость поставки A1В4 уменьшится на величину С14 *1= -10*1 = -10.

В целом, изме­нения, которые произойдут при рассмотренной перестановке по­ставок, можно записать следую­щим образом:

ΔR= +С11 *1- С14 *1 +С34 *1- С32 *1+ С22 *1- С21 *1=+ 6-10+12-8+7-4=+3

То есть при попытке дать поставку в клетку A1В1 в целом произойдет увеличение стоимости перевозок, увеличение зна­чения функции цели.

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

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

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

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

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

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

 

 

Клетка A1В1 Клетка A1В2

∑С11 =+6-10+12-8+7-4=+3 ∑С12 =+8-10+12-8=+2

 

Клетка A1В3 Клетка A2В3

       
   

 


∑С13 =+7-10+12-5=+4 ∑С23 =+6-5+8-7=+2

 

 

Клетка A2В4 Клетка A3В1

       
   

 


∑С24 =+8-12+8-7=-3 ∑С31 =+9-8+7-4=+4

 

Рис. 4.2. Цепи свободных клеток и их характеристики.

 

 

4.6. Переход от неоптимального решения к лучшему.

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

Величина функции цели равна:

R = 10*300 + 4*450 +7*100 +8*50 + 8*300 +5*200 = 9300 тыс. руб.

Это решение лучше начального на 150 тыс. руб. Это мож­но было установить, умножив характеристику цепи на по­ставку, внесенную в перспективную клетку -3*50 = -150 тыс. руб.

 

 

Таблица 4.4.



Дата добавления: 2021-07-22; просмотров: 340;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.035 сек.