 |
Нахождение опорного решения методом северо-западного угла.
|
|
|
|
Исходные данные занесем в упрощенную таблицу
В первом столбце указаны мощности поставщиков, в первой строке – спрос потребителей. Числа в левом верхнем углу клетки – это стоимость перевозок единицы груза от соответствующего поставщика к соответствующему потребителю, т.е. значения из данной в условии матрицы.
План перевозок будет задан, если мы укажем, сколько единиц груза должен получить каждый потребитель от каждого поставщика, т.е. если пустая таблица из трех строк и четырех столбцов будет заполнена.
Северо-западный угол таблицы – это её левый верхний угол, т.е. клетка в 1-й строке и 1-м столбце – клетка (1,1). Поэтому рассмотрим 1-го поставщика и 1-го потребителя. У поставщика А1 есть 30 единиц груза, а потребителю В1 нужно 70 единиц. Находим минимум из этих двух чисел: min (30,70) = 30. Клетка (1,1) перечеркивается по диагонали сплошной чертой (), по центру пишется найденный минимум 30. Это означает, что А1 должен поставить потребителю В1 30 единиц груза. Такие клетки в дальнейшем будем называть отмеченными.
Так как поставщик А1 израсходовал все свои 30 единиц груза, то мы исключаем его из рассмотрения. Поэтому все остальные клетки 1-й строки перечеркиваем по диагонали. Такие клетки в дальнейшем будем называть пустыми.
После первого шага наша таблица имеет следующий вид:
| 304 | ||||
Первая строка в дальнейшем не рассматривается.
Северо-западный угол этой таблицы – это клетка (2,1). Поэтому рассмотрим 2-го поставщика и 1-го потребителя. Мощность поставщика А2 равна 190 единиц. Спрос потребителя В1 – 70 единиц груза. Но 30 единиц груза он получил от поставщика А1 (об этом говорит отмеченная клетка (1,1)). Поэтому непокрытый спрос потребителя В1 равен 70–30=40. Находим минимум min (190,70-30)=40. Клетка (2,1) становится отмеченной. Мы запишем там этот минимум 40.
|
|
|
Поставщик А1(30 единиц) и А2 (40 единиц) полностью покрывают спрос потребителя В1 (70 единиц). Поэтому остальные клетки 1-го столбца объявим пустыми и в дальнейшем исключим из рассмотрения.
После второго шага таблица имеет следующий вид:
| 304 | ||||
| 403 | 1 | |||
Северо-западный угол этой таблицы – это клетка (2,2). min (190-40,120)=120.
Получаем следующую таблицу:
| 304 | ||||
| 403 | 1201 | |||
Северо-западный угол этой таблицы – это клетка (2,3). min (190-40-120,150)=30. Получаем следующую таблицу:
| 304 | ||||
| 403 | 1201 | 302 | ||
Северо-западный угол этой таблицы – это клетка (3,3). min (250, 150-30)=120. Получаем следующую таблицу:
| 304 | ||||
| 403 | 1201 | 302 | ||
| 1203 |
Осталась одна незаполненная клетка – это клетка (3,4). min (250-120,130)=130. Получаем следующую таблицу:
| 304 | ||||
| 403 | 1201 | 302 | ||
| 1203 | 1307 |
После выполнения очередного шага мы исключали из рассмотрения либо строку, либо столбец. Только на последнем шаге отпали и строка, и столбец. Поэтому для полностью заполненной таблицы должно соблюдаться следующее отношение: число отмеченных клеток = число строк +число столбцов – 1. В нашем случае это так: 6=3 + 4 – 1.
Посчитаем суммарные затраты. Для этого нужно в каждой отмеченной клетке перемножить ее числа и результаты сложить: 4*30+3*40+1*120+2*30+3*120+7*130=1690.
Нахождение опорного решения методом минимального тарифа (минимальной стоимости)
|
|
|
Согласно этому методу грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок Cij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжается до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше чем m+n-1. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми.
Нулевые поставки помещают в незанятые клетки с учетом наименьшего тарифа таким образом, чтобы в каждой строке и каждом столбце было не менее чем по одной занятой клетке.
Рассмотрим нахождение исходного опорного решения транспортной задачи на конкретном примере.
На каждом шаге будем делать поставку в клетку с наименьшей стоимостью перевозки единицы груза среди всех незаполненных клеток.
Шаг 1. Среди всех незаполненных клеток у клетки (2,2) наименьшая стоимость перевозки груза – 1. Поэтому делаем поставку в эту клетку min (190,120)=120. Исключаем 2-й столбец как полностью «удовлетворенный».
| 1201 | ||||
Шаг 2. Среди всех незаполненных клеток у клеток (1,3) и (2,3) наименьшая стоимость перевозки единицы груза – 2. Для клетки (1,3) min (30,150)=30. Для клетки (2,3) min(190-120,150)=70. Выбираем ту клетку, куда можно сделать наибольшую поставку. Так как 70>>30, то это клетка (2,3). Исключаем 2-ю строку как полностью «использованную»:
| 1201 | 702 | |||
Среди всех незаполненных клеток у клетки (1,3) наименьшая стоимость перевозки единицы груза – 2. min (30,150 – 70)=30. Исключаем 1-ю строку как полностью «использованную»:
| 302 | ||||
| 1201 | 702 | |||
И т.д. Окончательный вариант:
|
|
|
| 302 | ||||
| 1201 | 702 | |||
| 705 | 503 | 307 |
Число отмеченных клеток = число строк + число столбцов – 1: 6=3+4–1.
Стоимость перевозки равна: 2*30+1*120+2*70+5*70+3*50+7*130=1730.
3.2.1.4.Нахождение опорного плана методом Фогеля.
Метод Фогеля предусматривает введение штрафов строк (di) и штрафов столбцов (dj). Каждый штраф определяется как разность между минимальным элементом рассматриваемой строки (столбца) и следующим по величине. Вычеркнутые строки и столбцы в рассмотрение не принимают. Перевозку осуществляют в клетку, лежащую на строке (в столбце) с максимальным штрафом и имеющую минимальную стоимость перевозки. Далее при необходимости реализуют вычёркивание строк и столбцов, и все штрафы пересчитываются заново. Алгоритм заканчивается, когда все перевозки реализованы.
Шаги алгоритма представлены ниже.
Шаг 1. Рассчитываем штрафы строк и столбцов:
| Потреб. Поставки | В1 | В2 | В3 | В4 | ||
| di | ||||||
| А1 | 4 | 7 | 2 | 3 | 3-2=1 | |
| А2 | 3 | 1 | 2 | 4 | 2-1=1 | |
| А3 | 5 | 6 | 3 | 7 | 5-3=2 | |
| dj | 4-3=1 | 6-1=5 | 3-2=1 | 4-3=1 |
Максимальный штраф в столбце 2. Минимальный элемент этого столбца – 1. Загружаем его максимально возможным количеством груза – 120.
Получаем следующую таблицу:
| Потреб. Поставки | В1 | В2 | В3 | В4 | |
| А1 | 4 | 7 | 2 | 3 | |
| А2 | 3 | 120 1 | 2 | 4 | |
| А3 | 5 | 6 | 3 | 7 |
Шаг 2. Убираем столбец 2, одновременно уменьшаем количество груза у второго поставщика (строка 2) на 120 единиц и пересчитываем штрафы.
| Потреб. Поставки | В1 | В3 | В4 | ||
| di | |||||
| А1 | 4 | 2 | 3 | 3-2=1 | |
| А2 | 3 | 2 | 4 | 3-2=1 | |
| А3 | 5 | 3 | 7 | 5-3=2 | |
| dj | 4-3=1 | 3-2=1 | 4-3=1 |
Загружаем клетку с тарифом 3 в строке 3 максимально возможным количеством груза – 150, получаем таблицу:
| Потреб. Поставки | В1 | В3 | В4 | |
| А1 | 4 | 2 | 3 | |
| А2 | 3 | 2 | 4 | |
| А3 | 5 | 150 3 | 7 |
Шаг 3. Убираем отмеченный столбец, одновременно уменьшаем количество груза у третьего поставщика на 150 и пересчитываем штрафы.
| Потреб. Поставки | В1 | В4 | ||
| di | ||||
| А1 | 4 | 3 | 4-3=1 | |
| А2 | 3 | 4 | 4-3=1 | |
| А3 | 5 | 7 | 7-5=2 | |
| dj | 4-3=1 | 4-3=1 |
Загружаем клетку А3В1 70 единицами груза, получаем:
|
|
|
| Потреб. Поставки | В1 | В4 | |
| А1 | 4 | 3 | |
| А2 | 3 | 4 | |
| А3 | 70 5 | 7 |
Шаг 4. На этом шаге после исключения первого потребителя остается столбец В 4, в клетки которого загружаем оставшееся количество груза.
| Потреб. Поставки | В4 | |
| А1 | 30 3 | |
| А2 | 70 4 | |
| А3 | 30 7 |
В итоге получаем опорный план:
| Потреб. Поставки | В1 | В2 | В3 | В4 | |
| А1 | 4 | 7 | 2 | 30 3 | |
| А2 | 3 | 120 1 | 2 | 70 4 | |
| А3 | 70 5 | 6 | 150 3 | 30 7 |
Стоимость перевозки – 1500.
Кроме вышерассмотренных методов существуют и другие приёмы составления опорного плана:
· метод двойного предпочтения;
· метод минимальной стоимости по столбцу или строке и др.
|
|
|
