--PAGE_BREAK--
2.2.Метод северо-западного угла
При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного и заканчивается в клетке неизвестного , т. е. идет как бы по диагонали таблицы перевозок.
Пример.
70
50
15
80
70
300
80
90
40
60
85
150
50
10
90
11
25
250
170
110
100
120
200
700
Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным . Первая база может полностью удовлетворить потребность первого заказчика . Полагая , вписываем это значение в клетку и исключаем из рассмотрения первый столбец. На базе остается измененный запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами ; северо-западным углом будет клетка для неизвестного . Первая база с запасом может полностью удовлетворить потребность второго заказчика . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения второй столбец. На базе остается новый остаток (запас) . В оставшейся новой таблице с тремя строками и тремя столбцами северо-западным углом будет клетка для неизвестного . Теперь третий заказчик может принять весь запас с базы . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения первую строку. У заказчика из осталась еще не удовлетворенной потребность .
Теперь переходим к заполнению клетки для неизвестного и т.д.
Через шесть шагов у нас останется одна база с запасом груза (остатком от предыдущего шага) и один пункт с потребностью. Соответственно этому имеется одна свободная клетка, которую и заполняем, положив . План составлен. Базис образован неизвестными .
Опорный план имеет вид;
2.3. Метод минимального элемента
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел и . Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Пример
Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:
2
3
4
15
11
6
10
1
8
9
3
3
4
1
2
21
10
20
10
Решение:
Задача сбалансирована.
Строим первоначальный опорный план методом минимального элемента.
1. Выясним минимальную стоимость перевозок. Первая перевозка будет осуществляться с пункта производства в пункт потребления и она составит максимально возможное число единиц продукта :. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки .Выясним минимальную стоимость перевозок (без учета столбца № 2).
2. Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта: , ;
3.
4. Четвертая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца и четвертой строки). .
5. Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца, третьей и четвертой строки). .
6. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).
Опорный план имеет вид:
2.4. Метод аппроксимации Фогеля
При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость.
Если минимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).
Пример
Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:
(Здесь мы перенесли потребности в верхнюю строку для удобства построения плана). Рассмотрим задачу, приведенную для методов северо-западного угла и минимального элемента
Решение:
Опорный план имеет вид:
продолжение
--PAGE_BREAK--
2.5. Метод потенциалов
Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj — числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij — стоимости перевозки единицы продукции между пунктами Аi и Вj:
vj[k] – ui[k] Cij, i 1, ..., m; j 1, …, п.
Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.
Приложение
Задача 1.
Решить следующую задачу на минимизацию транспортных затрат предприятия с использованием надстройки «Поиск решения» электронной таблицы Excel.
Имеются nпунктов производства и mпунктов распределения продукции. Стоимость перевозки единицы продукции из i-го пункта производства в j-ый центр потребления Cijприведена в таблице, где под строкой понимается пункт производства, а под столбцом -пункт потребления. Кроме того, в таблицах в i-й строке указан объем производства в i-м пункте, а в j-м столбце указан спрос в j-м центре потребления. Составить план перевозок по доставке требуемой продукции в пункты потребления, минимизирующий суммарные транспортные расходы. Необходимые данные для решения задачи взять из представленной ниже таблицы. Таблица1
I
.Математическая модель задачи.
1) Переменные задачи. Обозначим количество продукции, которые будут перевозиться из nпунктов производства в mпункты потребления как Xij(i=1,2,3,4,5,6; j=1,2,3,4,5). Это переменные задачи, значения которых должны быть определены в процессе решения.
В задаче содержится 6*5=30 переменных.
2) Ограничения на переменные задачи. Очевидно, что все переменные задачи не отрицательные, т.е.
Xij 0,
где i=1, 2, 3,4,5,; j=1, 2, 3, 4.
Обычно транспортная задача представляется в виде таблицы, где в ячейках помещаются переменные задачи ( Xij), а в правом верхнем углу ячейки стоят стоимости перевозки из пункта iв пункт j( Cij). В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи .
Транспортная задача, для которой суммы чисел в последнем столбце и нижней строке равны, называется сбалансированной: 15 + 25 + 5 = 45, 5 + 15 + 15 + 10 = 45. Если транспортная задача не сбалансирована, то в таблицу добавляется еще одна строка или столбец. Причем стоимости перевозки в добавленных ячейках принимаются равными нулю.
Для нашего примера транспортная задача не сбалансирована. Сумма чисел в последнем столбце равна: 14+30+20+32+16=112, а нижней строке равна: 60+10+20+10=100. Чтобы сбалансировать задачу вводим пятый столбец и добавляем туда 12. Таблица в этом случае имеет вид:
3) Целевая функция. Транспортные расходы на перевозку по доставке требуемой продукции вычисляются по формуле:
Z = CijXij = 7,3X11 + 9X12 + 3X13 +… +5X54 (1)
II
. Решение транспортной задачи в процедуре
EXCEL
“Поиск решения”
1) Ввод данных. Вводим данные таблицы 1 и 2 в ячейки EXCEL.
В ячейках B4: E7 введены стоимости перевозок (табл. 1).
В ячейках G4: G8 находится объемы производства. А в ячейках B9: F12 находится объемы потребления. Ячейки B11: F15 – рабочие (изменяемые) ячейки, в которых будут вычисляться значения переменных задачи Xij.
В ячейках G11: G15 нужно записать формулы для вычисления левых частей ограничений:
в G11 должна быть сумма ячеек B11: F11;
в G12 должна быть сумма ячеек B12: F12;
в G13 должна быть сумма ячеек B13: F13;
в G14 должна быть сумма ячеек B14: F14;
в G15 должна быть сумма ячеек B15: F15. .
Формулы для вычисления левых частей ограничений введем в ячейки B16: F16:
в C16 должна быть сумма ячеек C11: C15;
в D16 должна быть сумма ячеек D11: D15;
в E16 должна быть сумма ячеек E11: E15;
в F16 должна быть сумма ячеек F11: F15;
Целевую функцию поместим в ячейку H9:
H9: СУММПРОИЗВ (B4: F8; B12: F16).
Таблица исходных данных имеет вид :
2) Заполнение окна процедуры «Поиск решения».
целевая функция H9;
значение целевой функции: min;
изменяемые ячейки: B12:F16;
ограничения задачи :
G12:G16=G4:G8
B12:F16 = B4:F8
B12: F16 0 (1)
3) Выполнив процедуру «Поиск решения» получим следующие результаты:
Вывод:
Таким образом с предприятия А(исходный пункт 1) следует 14 ед.продукции в пункты потребления 3(пункт назначения 3); из предприятия В(исходный пункт 2) 30 ед.продукции отвести в пункт потребления 1(пункт назначения 1); из предприятия С(исходный пункт 3) 14 ед.продукции отвести в пункт потребления 1(пункт назначения 1) и 6 ед.продукции отвести в пункт потребления 3(пункт назначения 3); из предприятия D(исходный пункт 4)7,21E-07 ед.продукции отвести в пункт потребления 1(пункт назначения 1), 10 ед.продукции отвести в пункт потребления 2(пункт назначения 2), 10 ед.продукции отвести в пункт потребления 4(пункт назначения 4) и 12 ед.продукции отвести в пункт потребления 5(пункт назначения 5); из предприятия Е(исходный пункт 5) 16 ед.продукции отвести в пункт потребления 1(пункт назначения 1).
Все эти результаты видны в конечной таблице. При этом суммарная стоимость транспортных расходов составит 394,8 рублей (ячейка Н9).
Задача 2.
Найти опорный план транспортной задачи, в которой запасы на 3-х складах равны 210, 170, и 65 единиц, а потребности 4-х магазинов равны 125, 90, 130 и 100 единиц продукции. Тарифы перевозки в рублях за единицу продукции следующие:
5 8 1 2
2 5 4 9
9 2 3 1
Решение методом северо-западного угла
Опорный план имеет вид:
125 85 0 0
0 5 130 35
0 0 0 65
F(x)== 5*125+8*85+5*5+4*130+9*35+1*165=2330
Решение методом минимального элемента
Опорный план имеет вид:
0 45 130 35
125 45 0 0
0 0 0 65
F(x)== 8*45+1*130+9*35+2*125+5*45+1*65=1345
Решение методом Фогеля
Пункты
Отпр-ия
Пункты назначения
Запасы
di
5
8
1
9
210/110/0
1
1
1
7
110
100
2
5
4
9
170/45/25/0
2
1
1
1
125
25
20
9
2
3
1
65/0
1
1
65
Потр-ти
125/0
90/25/0
130
100
dj
3
3
2
1
3
2
1
3
3
7
3
3
Опорный план имеет вид:
0 0 110 100
125 25 20 0
0 65 0 0
F(x)== 1*110+9*100+2*125+5*25+4*20+2*65=895 продолжение
--PAGE_BREAK--