Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






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

ТРАНСПОРТНАЯ ЛОГИСТИКА

Транспорт является одним из важнейших звеньев материального потока. Транспортные расходы, при определенных условиях, могут достигать 20% цены продукции. Поэтому одним из важнейших аспектов транспортной логистики является сокращение затрат, связанных с перемещением товара.

Традиционно в литературе рассматривается ряд классических транспортных задач и методов их решения.

1. Транспортная задача. Основная цель данной задачи разработать матрицу перевозок от m поставщиков к n потребителям с наименьшими суммарными затратами на транспортировку.

2. Задача о назначениях. Имеется n работ и n претендентов на данные работы. Известна производительность претендентов на каждой работе. Необходимо распределить работы среди претендентов таким образом, чтобы суммарная производительность была максимальной. Решение данной задачи предполагает выполнение условий: количество работ должно равняться количеству работников; каждому работнику может быть назначена только одна работа и наоборот.

3. Задача о коммивояжере. Имеется n городов. Коммивояжер, выехав из первого города должен объехать все города по одному разу и вернуться в исходный пункт. Известны расстояния между городами. Цель данной задачи – определить кратчайший маршрут движения.

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

Транспортная задача

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

 

a2

 

 

an n m

 

На приведенной иллюстрации используются следующие обозначения:

- а1, … , аn – объемы предложений;

- b1, …, bm – объемы спроса;

- сi,j – стоимость перевозки единицы груза из пункта i в пункт j;

- хi,j – объем перевозки единицы груза из пункта i в пункт j.

Цель задачи – найти план перевозок Х=(хi,j), минимизирующий суммарные затраты. Приведем математическую модель транспортной задачи:

при ограничениях

, i = 1, …, n,

, j = 1, … , m,

хi,j ³ 0, i = 1, …, n; j = 1, … , m.

 

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

 

Пункты предложения Пункты назначения Предложение (ед. продукции)
... m
с1,1 х1,1 с1,2 х1,2 с1,m x1,m a1
c2,1 x2,1 c2,2 x2,2 c2,m x2,m a2
n cn,1 xn,1 cn,2 xn,2 cn,m xn,m an
Спрос (ед.продукции) b1 b2 bm  

 

В соответствии с приведенной математической моделью, имеет место равенство суммарных предложения и спроса:

.

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

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

 

Пункты предложения Пункты назначения Предложение ед. продукции
... m Фиктивный
с1,1 х1,1 с1,2 х1,2 с1,m x1,m сф xф1,m a1
c2,1 x2,1 c2,2 x2,2 c2,m x2,m сф xф2,m a2
n cn,1 xn,1 cn,2 xn,2 cn,m xn,m сф xфn,m an
Спрос ед.продукции b1 b2 bm bф  

 

Стоимость доставки единицы груза из любого пункта предложения в фиктивный пункт назначения принимают равной 0: сф = 0.

Если суммарный спрос превышает суммарное предложение, то вводят фиктивный пункт предложения, который формально восполняет недостаток предложения:

 

Пункты предложения Пункты назначения Предложение ед. продукции
... m
с1,1 х1,1 с1,2 х1,2 с1,m x1,m a1
c2,1 x2,1 c2,2 x2,2 c2,m x2,m a2
n cn,1 xn,1 cn,2 xn,2 cn,m xn,m an
Фиктивный сф хфn,1 сф хфn,2   сф хфn,m аф
Спрос ед.продукции b1 b2 bm  

 

Стоимость доставки единицы груза из фиктивного пункта предложения в любой пункт назначения принимают равной 0: сф = 0.

Решение транспортных задач проводится в два этапа: первоначальный и основной. На первоначальном этапе получают допустимое базисное решение, которое также называют опорным планом перевозок. Допустимое базисное решение удовлетворяет всем условиям задачи, кроме, быть может, оптимальности. Опорный план перевозок предполагает выполнение не более чем m + n – 1 поставок (заметим, что m + n – 1 – число линейно независимых ограничений системы ограничений). Можно показать, что всегда найдется такое оптимальное решение транспортной задачи, в котором количество поставок (занятых клеток в матрице планирования) также не превосходит числа m + n – 1. Поэтому оптимальный план перевозок ищут среди опорных планов.

Для нахождения первоначального решения используют методы северо-западного угла, наименьшей стоимости, Фогеля и др. Все эти методы предполагают решение одной задачи – построение начального опорного плана. Однако качество начального решения зависит от того, какой метод был использован для его получения. Как правило, метод северо-западного угла (очень простой в применении) дает решение, более далекое от оптимального плана поставок, по сравнению с методами наименьшей стоимости и Фогеля.

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

Решение

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

На первом шаге (табл. 3.1.1) в ячейку (1,1) введем условную поставку 15 т удовлетворяющую потребность первого магазина в товаре. Предложение первого распределительного центра в данном случае уменьшится на 15 т. Первый столбец из дальнейшего рассмотрения исключаем.

Таблица 3.1.1

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
(РЦ 1) 30 (15)
(РЦ 2)  
(РЦ 3)  
Спрос 15 (15)  

 

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

 

Таблица 3.1.2

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1 15 10 30 (25)
РЦ 2  
РЦ 3  
Спрос 15 (15) 10 (10)  

 

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

Таблица 3.1.3

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1 4 10 30 (30)
РЦ 2  
РЦ 3  
Спрос 15 (15) 10 (10) 25 (20)  

 

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

Таблица 3.1.4

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1 15 10 5 30 (30)
РЦ 2   20 (20)
РЦ 3  
Спрос 15 (15) 10 (10) 25 (25)  

 

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

Таблица 3.1.5

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1 30 (30)
РЦ 2   20 (20)
РЦ 3   50 (50)
Спрос 15 (15) 10 (10) 25 (25) 30 (30) 20 (20)  

 

Количество поставок в базисном решении для данной задачи равно 7, что соответствует числу независимых ограничений (m + n – 1).

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

Z = 15*4 + 10*5 + 5*1 + 20*4 + 0*7 + 30*5 + 20*2 = 385 у.е.

Метод наименьшей стоимости

Алгоритм получения начального базисного решения

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

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

3 шаг. Вычеркивается соответствующая строка или столбец с реализованным спросом или предложением в соответствии заданными ограничениями. Если в выбранной ячейке (i,j) спрос равен предложению, то вычеркивается на выбор строка или столбец.

4 шаг. В оставшейся матрице выбирают ячейку с наименьшей стоимостью поставки единицы груза и повторяют шаги 2-4.

5 шаг. В случае полной реализации спроса и предложения процесс останавливают.

 

В качестве примера рассмотрим решение приведенной выше задачи №1 методом наименьшей стоимости. В матрице выберем ячейку (1,3) с наименьшей стоимостью поставки единицы (тонны) груза и введем условную поставку 25 т, удовлетворив тем самым спрос Магазина 3 (табл. 3.1.6). Третий столбец из дальнейшего рассмотрения вычеркиваем.

Таблица 3.1.6

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1   25 30 (25)
РЦ 2  
РЦ 3  
Спрос 25 (25)  

 

В оставшейся матрице ячейки (2,1), (3,5) имеют минимальную стоимость поставки единицы (тонны) груза. Выберем ячейку (3,5) и введем условную поставку, равную 20 т (табл. 3.1.7) и полностью удовлетворяющую спрос пятого магазина. Пятый столбец из дальнейшего рассмотрения вычеркиваем.

 

Таблица 3.1.7

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1   1 4 30 (25)
РЦ 2  
РЦ 3   50 (20)
Спрос 25 (25) 20 (20)  

 

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

Таблица 3.1.8

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1 25 4 30 (25)
РЦ 2   20 (15)
РЦ 3   50 (20)
Спрос 15 (15) 25 (25) 20 (20)  

 

Введем в ячейку (1,4) условную поставку 5 т (табл. 3.1.9), полностью реализующую предложение первого распределительного центра. Первую строку из дальнего рассмотрения вычеркиваем.

Таблица 3.1.9

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1 4 25 4 30 (30)
РЦ 2   20 (15)
РЦ 3   50 (20)
Спрос 15 (15) 25 (25) 30 (25) 20 (20)  

 

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

 

Таблица 3.1.10

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1 4 5 25 4 30 (30)
РЦ 2   20 (15)
РЦ 3   50 (30)
Спрос 15 (15) 10 (10) 25 (25) 30 (25) 20 (20)  

 

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

 

Таблица 3.1.11

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1   30 (30)
РЦ 2   20 (20)
РЦ 3   50 (50)
Спрос 15 (15) 10 (10) 25 (25) 30 (30) 20 (20)  

 

Количество поставок в базисном решении равно 7, что соответствует числу независимых ограничений (m + n – 1).

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

Z = 25*1 + 5*3 + 15*2 + 5*7 + 10*4 + 20*5 + 20*2 = 285 у.е.

Метод Фогеля

Рассмотрим шаги получения начального решения задачи методом Фогеля.

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

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

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

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

5 шаг. Соответствующая строка или столбец вычеркивается. Если значение спроса для ячейки (i.j) равно предложению, то вычеркивается строка или столбец на выбор.

6 шаг. В оставшейся матрице для каждой строки и столбца повторяются шаги 1–5.

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

 

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

Таблица 3.1.12

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Штраф Предложение
РЦ 1       3 – 1 = 2
РЦ 2     4 – 2 = 2
РЦ 3       2 – 2 = 0
Штраф 3 – 2 = 1 5 – 4 = 1 2 – 1 = 1 5 – 3 = 2 4 – 2 = 2    
Спрос    

 

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

Сумма штрафов по строкам: 2 + 2 + 0 = 4

Сумма штрафов по столбцам: 1 + 1 + 1 + 2 + 2 = 7

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

Таблица 3.1.13

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Штраф Штраф Предложение
РЦ 1       4 3 – 1 = 2 3 – 1 = 2
РЦ 2     4 – 2 = 2 4 – 2 = 2
РЦ 3     2 – 2 = 0 3 – 2 = 1 50 (30)
Штраф 3 – 2 = 1 5 – 4 = 1 2 – 1 = 1 5 – 3 = 2 4 – 2 = 2      
Спрос 20 (20)      

 

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

Максимальный штраф также находится и в строках, и в столбце.

Сумма штрафов по строкам: 2 + 2 + 1 = 5

Сумма штрафов по столбцам: 1 + 1 + 1 + 2 = 5

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

Таблица 3.1.14

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Штраф Штраф Предложение
РЦ 1 4     4 3 – 1 = 2 3 – 1 = 2 30 (30)
РЦ 2     4 – 2 = 2 4 – 2 = 2
РЦ 3     2 – 2 = 0 3 – 2 = 1 50 (30)
Штраф 3 – 2 = 1 5 – 4 = 1 2 – 1 = 1 5 – 3 = 2 4 – 2 = 2      
Штраф 3 – 2 = 1 6 – 4 = 2 4 – 2 = 2 7 – 5 = 2        
Спрос 30 (30) 20 (20)      

Сумма штрафов по строкам: 2 + 1 = 3

Сумма штрафов по столбцам: 1 + 2 + 2 + 2 = 7

Таблица 3.1.15

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Штраф Штраф Штраф Предложение
РЦ 1 4   1   4 3 – 1 = 2 3 – 1 = 2   30 (30)
РЦ 2     4 – 2 = 2 4 – 2 = 2 6 – 2 = 4
РЦ 3     2 – 2 = 0 3 – 2 = 1 4 – 3 = 1 50 (5)
Штраф 3 – 2 = 1 5 – 4 = 1 2 – 1 = 1 5 – 3 = 2 4 – 2 = 2        
Штраф 3 – 2 = 1 6 – 4 = 2 4 – 2 = 2 7 – 5 = 2          
Штраф 3 – 2 = 1 6 – 4 = 2              
Спрос 25 (25) 30 (30) 20 (20)        

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

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

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

 

Таблица 3.1.16

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Штраф Штраф Штраф Предложение
РЦ 1 4 4 3 – 1 = 2 3 – 1 = 2   30 (30)
РЦ 2   4 – 2 = 2 4 – 2 = 2 6 – 2 = 4 20 (5)
РЦ 3     2 – 2 = 0 3 – 2 = 1 4 – 3 = 1 50 (5)
Штраф 3 – 2 = 1 5 – 4 = 1 2 – 1 = 1 5 – 3 = 2 4 – 2 = 2        
Штраф 3 – 2 = 1 6 – 4 = 2 4 – 2 = 2 7 – 5 = 2          
Штраф 3 – 2 = 1 6 – 4 = 2              
Спрос 15 (15) 25 (25) 30 (30) 20 (20)        

 

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

Таблица 3.1.17

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Штраф Штраф Штраф Предложение
РЦ 1     3 – 1 = 2 3 – 1 = 2   30 (30)
РЦ 2 4 – 2 = 2 4 – 2 = 2 6 – 2 = 4 20 (5)
РЦ 3   2 – 2 = 0 3 – 2 = 1 4 – 3 = 1 50 (5)
Штраф 3 – 2 = 1 5 – 4 = 1 2 – 1 = 1 5 – 3 = 2 4 – 2 = 2        
Штраф 3 – 2 = 1 6 – 4 = 2 4 – 2 = 2 7 – 5 = 2          
Штраф 3 – 2 = 1 6 – 4 = 2              
Спрос 25 (25) 30 (30) 20 (20)        

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

Суммарные затраты на транспортировку 100 тонн груза от распределительных центров к магазинам:

Z = 30*3 + 15*2 + 5*6 + 5*4 + 25*2 + 20*2 = 260 у.е.

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

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

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

Распределительный метод

Распределительный метод, как уже отмечалось, применяется для нахождения оптимального решения транспортной задачи, для которой ранее найдено первоначальное решение (опорный план перевозок с числом занятых клеток m + n – 1). Этот метод основан на последовательном рассмотрении пустых ячеек первоначального решения и возможном введении в них поставок.

Порядок действий опишем в виде алгоритма.

1 шаг. Выбирается любая пустая ячейка в опорном плане перевозок.

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

3 шаг. Обозначить угол полученной замкнутой ломаной линии (контура) в свободной клетке знаком (+), а последующие углы попеременно знаками (-) и (+).

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

5 шаг. Если полученная сумма положительна или равна нулю, то выбирают следующую ячейку и повторяют шаги 2–4.

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

7 шаг. В других углах построенного контура поставки пересчитываются следующим образом: для ячеек, обозначенных знаком (+), размер вводимой в пустую ячейку поставки прибавляется к имеющимся в них базовым поставкам; для ячеек, обозначенных знаком (-), вводимая поставка вычитается из соответствующих базовых поставок. В результате пересчета (перераспределения груза), по крайней мере, одна из клеток, помеченная знаком (-), получит нулевую перевозку (поставку). Эту клетку следует вывести из системы поставок (из плана перевозок). Если клеток, получивших в результате пересчета нулевую перевозку, несколько, из системы поставок выводят одну – ту, которой соответствует максимальное значение стоимости перевозки единицы груза.

8 шаг. В результате выполнения шагов 6 и 7 получена новая система поставок – новый опорный план перевозок, в котором число занятых клеток опять m + n – 1. Для этого плана определяются суммарные затраты на транспортировку груза.

9 шаг. Выбирается следующая пустая ячейка в первоначальном решении и повторяются шаги 2–8.

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

Задача

Найти оптимальный план перевозок распределительным методом по данным задачи 1, используя в качестве начального решение, рассчитанное по методу наименьшей стоимости (табл. 3.1.18).

Таблица 3.1.18

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1  
РЦ 2  
РЦ 3  
Спрос  

 

Решение

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

Выберем направление обхода против часовой стрелки, поэтому следующую ячейку будем искать в первом столбце. Наиболее удаленной занятой клеткой от ячейки (1,1) является клетка (2,1). Далее контур следует продолжить в горизонтальном направлении, то есть по строке 2. В этой строке найдем наиболее далекую ячейку, содержащую поставку. Это будет ячейка (2,4). Следующую ячейку находим снова по столбцу – (1,4). Из этой ячейки по горизонтали уже можно замкнуть контур, вернувшись в исходную ячейку (1,1). Обозначим угол прямоугольника в свободной клетке знаком (+), а последующие – попеременно знаками (-) и (+).

Таблица 3.1.19

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1 (+) 5 (-)
РЦ 2   15 (-) 5 (+)
РЦ 3  
Спрос  

 

Алгебраическая сумма стоимостей транспортировки груза с учетом знаков:

D1,1 = 4 – 2 + 7 – 3 = 6 > 0

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

Испытаем свободную клетку (1,2). Построим замкнутый контур (табл. 3.1.20) и определим алгебраическую сумму стоимостей.

Таблица 3.1.20

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
РЦ 1   5 (+) 5 (-)
РЦ 2  
РЦ 3   10 (-) 20 (+)
Спрос  

 

Алгебраическая сумма стоимостей транспортировки единицы груза с учетом знаков:

D1,2 = 5 - 4 + 5 – 3 = 3 > 0

Рассмотрим ячейку (1,5). Построим замкнутый контур и определим алгебраическую сумму расстояний (табл. 3.1.21). В данном случае для примера выбрано другое направление построения контура.

Алгебраическая сумма стоимостей транспортировки единицы тонны груза с учетом знаков будет равна:

D1,5 = 4 – 2 + 5 – 3 = 4 > 0

 

Таблица 3.1.21

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предложение
(РЦ 1)   5 (-) (+)
(РЦ 2)  
(РЦ 3)   20 (+) 20 (-)
Спрос  

 

Выберем ячейку (2,2) и построим замкнутый контур (табл. 3.1.22) и определим алгебраическую сумму стоимостей.

Таблица 3.1.22

  Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5 Предл

Последнее изменение этой страницы: 2016-08-11

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...