Требуется выбрать и дать техническое и экономическое
 Скачать 216.11 Kb.
|
Задача № 2Решить транспортную задачу методом потенциалов. Потребителям Б1 Б2, Б3 и Б4 требуется песок в количествах соответственно б1, б2, б3 и б4 тонн. На складах имеется следующее количество песка: A1 = a1 т, А2 = а2 т и А3 = а3 т. Требуемое и имеющееся количество песка приведено в табл.4. Расстояния между поставщиками и получателями песка приведены в табл.5. Необходимо составить план перевозок песка (план закрепления потребителей за поставщиками) так, чтобы при минимальной транспортной работе были удовлетворены запросы всех потребителей. Таблица4
Таблица5
Рассмотрим процедуру вычислений на конкретном примере. Пусть потребителям Б1, Б2, Б3 и Б4 требуется песок в количествах соответственно 30, 70, 40 и 30 тонн. На складах имеется следующее количество песка: A1 = 80 т, А2 = 50 т и А3 = 40 т. Расстояния между поставщиками и получателями песка приведены в табл.6. Необходимо составить план перевозок песка (план закрепления потребителей за поставщиками) так, чтобы при минимальной транспортной работе были удовлетворены запросы всех потребителей. Таблица6
Очевидно, что транспортная работа будет минимальной, если доставлять песок каждому потребителю с ближайшего к нему склада. В таком случае решение было бы очевидным. Однако в рассматриваемой задаче это невозможно, так как для потребителей Б1, Б2 и Б4 с суммарной потребностью в 130 т ближайшим является склад А2, где имеется лишь 50 т песка. Поэтому для полного удовлетворения потребности этих потребителей неизбежны перевозки с других складов. При этом возможны различные варианты. Составление матрицы условий. Запишем условия задачи в форме матрицы (табл.7). Таблица7
В правых верхних углах клеток, представляющих собой реальные маршруты перевозок, указаны расстояния между соответствующими пунктами. В процессе решения задачи в средней части этих клеток записывают значения хij, которые делятся на основные и не основные. Не основные хij в таблице-матрице не пишутся и считаются равными нулю. К основным относятся все хij >0, а также те из хij =0, которые записываются в матрице. Основные хij записанные в матрице, обычно называют загрузками, а клетки, в которых они находятся, -занятыми. Клетки матрицы без загрузок называют незанятыми. Составление допустимого исходного плана. Решение задачи начинается с составления допустимого плана. Производится это способом минимального элемента по строке следующим образом. Сначала планируем перевозки с первого склада, записывая их в соответствующие клетки первой строки. Производим это следующим образом. Сначала полностью удовлетворяем потребность ближайшего потребителя Б3, записав в клетку с наименьшим расстоянием 40 т. Поскольку в пункте A1 остается еще 40 т, удовлетворяем потребность следующего ближайшего потребителя Б 4, записав в соответствующую клетку нужные ему 30 т. Оставшиеся 10 т заносим в клетку A1Б1 и переходим к следующей строке матрицы. Теперь груз второго отправителя А2 планируем к перевозке ближайшим из еще неудовлетворенных потребителей, записывая соответствующие объемы в клетки второй строки последовательно, начиная с клетки с наименьшим расстоянием:, в клетку A2B1 - 20 т и в клетку А2Б2 - 30 т. Перейдя к третьей строке матрицы, видим, что остался неудовлетворенным только один потребитель Б2. Планируем ему перевозку из А3, записав в клетку А3Б2 40 т. Вычисления закончены. Полученный допустимый план представлен в табл. 8. По этому плану перевозок потребность всех потребителей удовлетворяется полностью, а транспортная работа составит Р = 10*9+40*5+30*8+20*4+30*9+40*22 = 1760 тонно- километров. 2. Проверка оптимальности плана производится с помощью индексов, которые рассчитывают прямо на матрице. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||