Исходные данные:

а) схема транспортной сети (рисунок 1.1);

б) марка автомобиля (табл. 1.1);

в) вид груза (см. табл. 1.1);

г) объем перевозок (см. табл. 1.1);

д) время работы системы (см. табл. 1.1);

е) расстояние перевозок (табл. 1.2).

Режим работы пунктов погрузки-разгрузки - односменный, начало работы - 8.00 ч.

Рисунок 1.1 - Схема транспортной сети

Таблица 1.1 - Варианты заданий

Таблица 1.2 - Расстояние перевозок, км

2. Порядок выполнения работы

Порядок исполнения работы представлен на рисунке 2.1.

Рисунок 2.1 - Порядок выполнения курсовой работы

3. Модель транспортной задачи

4. Решение транспортной задачи методом МОДИ

Последовательность решения транспортной задачи линейного программирования методом МОДИ можно представить схематически (рисунок 4.1) .

Рисунок 4.1 - Схема выполнения расчета

Задача закрепления потребителей за поставщиками груза формулируется следующим образом: имеется несколько поставщиков и получателей транспортно-однородного груза.

Расстояния перевозок представлены на рисунке 4.2. Известны объемы наличия груза у каждого поставщика и потребности в нем у каждого получателя, а также расстояния между грузоотправителями и грузополучателями.

Необходимо закрепить потребителей за поставщиками так, чтобы объем транспортной работы (в тонно-километрах) был минимальным.

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

Пусть имеется четыре грузообразующих точки А1, А2, А3, А4 из которых следует вывезти однородный груз пяти потребителям (Б1, Б2, Б3, Б4, Б5) в объеме соответственно 215, 175, 120, 480 т. При этом потребителю Б1 необходимо доставить 215 т. груза, Б2 - 175т., Б3 - 120 т., Б4 - 195т. и Б4 -285 т.

Рисунок 4.2 - Схема транспортной сети с расстоянием перевозок

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

Таблица 4.1- Расстояние между грузоотправителями и потребителями

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

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

При построении допустимого плана методом минимума по строке порядок распределения груза по клеткам матрицы следующий:

а) отыскивают клетку с минимальным расстоянием C_ij в первой строке и в ней записывают возможную загрузку;

б) если наличие груза по первой строке не исчерпано ( b_j a_i ) , то в этой же строке отыскивают следующую клетку с минимальным расстоянием и заносят в нее возможную загрузку;

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

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

Рассмотрим построение опорного плана методом минимума по строке (таблица 4.2):

а) в строке Б1 минимальное расстояние имеет клетка А2Б1. Потребность в грузе у Б1 (205 т) удовлетворяется наличием груза в пункте А2 (170 т) и А3 (35 т), после этого у грузоотправителя А3 осталось 505 т.

б) в строке Б2 минимальное расстояние имеет клетка А4Б2. Потребность в грузе у Б2 (170 т) удовлетворяется всем грузом в А4 (155 т). Остаток потребности в 15 т удовлетворяется в А1.

в) в строке Б3 минимальное расстояние имеет клетка А1Б3. Потребность в грузе у Б3 (260 т) удовлетворяется всем грузом в А1 (190т). Остаток потребности в 70т удовлетворяется наличием груза в А3, после этого у грузоотправителя А3 остается 435т.

г) в строке Б4 минимальное расстояние имеет клетка А3Б4. Потребность в грузе у Б4 (280 т) полностью удовлетворяется наличием груза в А3, после этого у грузоотправителя А3 осталось 155 т.

д) в строке Б5 потребность в грузе удовлетворяется остатками груза в пункте А3 (155 т).

Таблица 4.2 - Построение опорного плана методом минимума по строке

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

а) - вначале выбирают и отмечают знаком (х) наименьшее расстояние в каждой строке;

б) - затем это же делают по столбцам;

в) - клетки, имеющие две отметки, загружают в первую очередь, помещая в них максимально возможные объемы перевозок;

г) - затем загружают клетки, отмеченные один раз;

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

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

Так, в табл. 4.3 в клетку А2Б5, отмеченную дважды, следует поместить 155 т груза, т.к. потребность в грузе у грузополучателя Б5 составляет 155 т., при этом у грузоотправителя А2 остается груз, равный 15 т. Все дважды отмеченные клетки загружены.

Следующая клетка, отмеченная один раз и имеющая минимальное расстояние перевозки - А3Б5,но так как потребность у Б5 удовлетворена полностью, эту клетку мы не рассматриваем. То же самое происходит с клеткой А4Б5.

Затем загружается клетка А4Б4 - 155 т, что соответствует максимальному количеству груза у грузоотправителя А4, у грузополучателя Б4 остается потребность в 125т, которая удовлетворяется полностью в следующей клетке А1Б4, при этом у грузоотправителя А1 остается груз в размере 80т.

Следующей клеткой, которая отмечена один раз и имеет минимальное расстояние перевозки среди оставшихся, является А2Б1 и в нее помещается 15 т, что соответствует остатку груза у грузоотправителя А2, после этого грузополучателя Б1 остается потребность в 190 т.

В клетку А1Б3 вносим 80 т груза по максимальной возможности в грузе грузоотправителя А1, после этого у грузополучателя Б3 остается потребность в 180 т.

Все отмеченные значками клетки загружены, но осталась неудовлетворенной потребность в грузе у грузополучателя Б1(190), что возмещается грузом грузоотправителя А3, и после этого у А3 еще остается 350 т., а у грузополучателей Б2 и Б3 еще остаются потребности в грузе в размере 170 и 180 т соответственно. Поэтому груз распределяется следующим образом: в клетке А3Б2 будет 170 т, а в клетке А3Б3-180т.

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

Таблица 4.3 - Построение опорного плана методом двойного предпочтения

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

P=Q_i*l_j(4.1)

где Q_i - количество груза, которое необходимо перевезти, т.;

l_j - расстояние перевозки, км.

Рассчитаем объем транспортной работы для опорного плана:

а) построенного методом минимума по строке

(P=170*13+35*5+15*16,5+155*15+190*14+70*19,5+280*20,5+155*515847,5ткм)

б) построенного методом двойного предпочтения

(P=15*13+190*15+170*26,5+80*14+180*19,5+125*10+155*9+155*2=15135 ткм)

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

После получения допустимого плана перевозок производится промежуточная проверка: количество груза, записанное по клеткам каждого столбца матрицы, равняется объему производства в данном столбце, а количество груза, записанное по клеткам каждой строки матрицы, равняется объему потребления в этой строке. Таким образом, ошибок в полученном плане не найдено.

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

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

_i + _j = C_ij , (4.2)

где _i - индекс в клетке вспомогательной строки ;

_j - индекс в клетке вспомогательного столбца ;

C_ij - расстояние в загруженной клетке .

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

m + n - 1 , (4.3)

где m- число столбцов в матрице ;

n - число строк в матрице .

Если количество загруженных клеток в матрице будет меньше числа (m + n - 1), то необходимо искусственно догрузить недостающее количество клеток, для этого в них записывают ноль.

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

В соответствии с правилом в клетке вспомогательного столбца ₁ записываем ноль, затем находим индекс ₂ для столбца А2 : ₂ + ₁ = С _ij ; ₁ = 0 ; ₁ + 0 = 13 , следовательно, ₂ = 13.

В столбце А2 имеем загруженную клетку А2Б5, по ней можем определить индекс строки Б5 : ₂ + ₅ = 2, 13 + ₅ = 2, следовательно ₅= - 11.

В строке Б1 находится загруженная клетка А3Б1, по ней определяем индекс столбца А3 : ₃ + ₁ = С _ij ; ₁ = 0 ; ₃ + 0 = 15, следовательно, ₃ = 15. Аналогично вышеприведенным расчетам определяем индексы строки Б2 (₂ = 11,5), строки Б3(₃= 4,5), строки Б4(₄ = 0,5), столбца А1(₁ = 9,5) и столбца А4(₄=8,5).

Таблица 4.4 - Построение оптимального плана

После определения вспомогательных индексов находим в матрице потенциальные клетки.

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

_i + _j C_ij . (4.5)

Рассматриваем последовательно незагруженные клетки матрицы (см. табл. 4.4). Находим две потенциальные клетки: А2Б2 и А4Б2. Для клетки А2Б2 сумма индексов ₂ + ₂ = 13+11,5=24,5, а расстояние - 21, величина потенциала равна 3,5 (24,5-21=3,5).

Для клетки А4Б2 потенциал равен 5 (8,5 +11,5 -15 = 5). Величины потенциала записывают в левых верхних углах потенциальных клеток со знаком «+».

Величина потенциала показывает, что если перераспределить загрузку в потенциальные клетки, то на каждую тонну перемещенного груза может быть получена экономия в расстоянии перевозок по 3,5 км для клетки А2Б2 и 5 км для клетки А4Б2 .

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

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

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

Движение при построении контура совершается строго под прямым углом. В таблице 4.4 получили шестиугольный контур с вершинами в клетках А4Б2, А3Б2, А3Б3, А1Б3, А1Б4 и А4Б4.

Вершины контура обозначаются попеременно знаками «+» и «-», начиная с потенциальной (А4Б2), которой присваивается знак «-» . Потом из всех клеток, обозначенных знаком «+», выбирается наименьшая цифра загрузки (в А1Б3).

Это количество груза (80 т) вычитается из загрузки, указанной в клетках со знаком «+», и прибавляется к загрузке в клетках со знаком «-». Полученные цифры записывают в новую матрицу (таблица 4.5), куда без изменений переносят загрузки тех клеток, которые не являются вершинами контура.

Таблица 4.5 - Оптимальный план закрепления потребителей за поставщиками

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

В матрице (см. таблицу 4.5) потенциальными являются клетки А2Б2 (+3,5) и А2Б4 (+3,5), следовательно, от них необходимо избавиться тем же способом. Так как потенциалы равны, выбираем для вершины контура клетку А2Б2. Новая матрица представлена в таблице 4.6

Таблица 4.6 - Построение другого варианта оптимального плана

При проверке другого улучшенного плана на оптимальность, была найдена клетка А3Б5 с потенциалом +2,5. В таблице 4.7 представлена матрица, построенная после избавления от этой потенциальной точки.

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

Рассматриваем последовательно незагруженные клетки матрицы, где записан оптимальный план, и находим потенциальные клетки равные нулю (см. табл. 4.7). Такая клетка одна: А2Б4. Для нее сумма индексов ₂ + ₄ = 12+3=15, а расстояние 15, величина потенциала равна 0.

Таблица 4.7 - Второй оптимальный план

Составляется контур возможных перемещений и определения величин загрузок, подлежащих перемещению для клетки А2Б4. Контур строится следующим образом: от клетки А2Б4 ведется прямая линия по строке до загруженной клетки, которой, в свою очередь, должна соответствовать еще одна загруженная клетка под прямым углом, и так до тех пор, пока линия не замкнется в исходной клетке.

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

Вершины контура обозначаются попеременно знаками «+» и «-», начиная с потенциальной (А2Б4), которой присваивается знак «-» . Потом из всех клеток, обозначенных знаком «+», выбирается наименьшая цифра загрузки. Это количество груза (75 т) вычитается из загрузки, указанной в клетках со знаком «+», и прибавляется к загрузке в клетках со знаком «-». Полученные цифры записывают в новую матрицу (таблица 4.8), куда без изменений переносят загрузки тех клеток, которые не являются вершинами контура.

Построенный план (см таблицу 4.8) проверяем на оптимальность. Для этого находим индексы вспомогательных строки и столбца и ищем в данном плане потенциальные клетки.

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

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

Таблица 4.8 - Третий оптимальный план