Быстрая навигация по странице:
Теоретические основы метода северо-западного угла
Алгоритм метода северо-западного угла
Пример решения транспортной задачи в Excel методом северо-западного угла
Вернуться к примерам решения задач по логистике
Теоретические основы метода северо-западного угла
Логистика — это область, где оптимизация процессов транспортировки играет ключевую роль. Одна из центральных задач в этой сфере — транспортная задача, цель которой состоит в нахождении оптимального варианта распределения поставок однородной продукции с минимальными затратами.
Для решения транспортной задачи существует несколько методов: метод минимальных тарифов, метод Фогеля, метод потенциалов, симплекс-метод и др. В данном случае мы рассмотрим метод северо-западного угла и его реализацию в Microsoft Excel.
Транспортная задача формулируется в виде прямоугольной таблицы:
- строки соответствуют поставщикам с определёнными запасами товара;
- столбцы — потребителям с конкретными потребностями;
- в ячейках на пересечении строк и столбцов указываются тарифы перевозки (например, стоимость доставки единицы груза).
Метод северо-западного угла — это способ получения начального допустимого решения транспортной задачи. Он был предложен американским математиком Джорджем Бернардом Данцигом в 1951 году. Название метода связано с тем, что заполнение таблицы начинается с верхней левой ячейки ("северо-западной" точки).
Алгоритм метода северо-западного угла
1. Начинаем с ячейки в верхнем левом углу таблицы.
2. Вписываем максимально возможный объём перевозки, который не превышает ни запас поставщика, ни потребность потребителя: xij = min(aibj)
3. Если запас поставщика исчерпан, переходим к следующей строке.
4. Если потребность потребителя удовлетворена, переходим к следующему столбцу.
5. Повторяем шаги 2–4 до полного заполнения таблицы.
Важные замечания:
- метод не учитывает тарифы перевозки — он лишь формирует опорный план;
- полученное решение редко бывает оптимальным, но служит отправной точкой для дальнейшей оптимизации (например, методом потенциалов).
Пример решения транспортной задачи в Excel методом северо-западного угла
Рассмотрим пример с тремя поставщиками (Склад A1, Склад A2, Склад A3) и четырьмя потребителями (Магазин B1, Магазин B2, Магазин B3, Магазин B4):
Ресурсы поставщиков и запросы потребителей следующие:
| Поставщики | Запасы (кг) |
|---|---|
| Склад A1 | 40 |
| Склад A2 | 30 |
| Склад A3 | 20 |
| Потребители | Потребности (кг) |
| Магазин B1 | 20 |
| Магазин B2 | 30 |
| Магазин B3 | 25 |
| Магазин B4 | 15 |
Также заданы следующие транспортные тарифы:
| Магазин В1 | Магазин В2 | Магазин В3 | Магазин В4 | |
|---|---|---|---|---|
| Склад А1 | 8 | 6 | 10 | 9 |
| Склад А2 | 9 | 7 | 4 | 2 |
| Склад А3 | 3 | 4 | 2 | 5 |
Шаг 1. Подготовка таблицы в Excel
Откроем Excel и создаем таблицу, внеся следующие данные:
| Заголовки | |
|---|---|
| Ячейка | Содержимое |
| A1 | Поставщики |
| B1 | Магазин B1 |
| C1 | Магазин B2 |
| D1 | Магазин B3 |
| E1 | Магазин B4 |
| F1 | |
| Поставщики | |
| Ячейка | Значение |
| A2 | Склад A1 |
| A3 | Склад A2 |
| A4 | Склад A3 |
| Запасы | |
| Ячейка | Значение |
| F2 | 40 |
| F3 | 30 |
| F4 | 20 |
| Потребности | |
| Ячейка | Значение |
| B5 | 20 |
| C5 | 30 |
| D5 | 25 |
| E5 | 15 |
| Дополнительно | |
| Ячейка | Значение |
| A5 | Потребность |
Ввод тарифов. Ниже или рядом создаём матрицу тарифов.
| Ячейка | Значение |
|---|---|
| B8 | 8 |
| C8 | 6 |
| D8 | 10 |
| E8 | 9 |
| B9 | 9 |
| C9 | 7 |
| D9 | 4 |
| E9 | 2 |
| B10 | 3 |
| C10 | 4 |
| D10 | 2 |
| E10 | 5 |
В A8:A10 подпишим A1,A2,A3.
Теперь создаём матрицу перевозок, которую будет изменять Excel.
Используем диапазон: B2:E4
Сейчас введим в них нули.
Это будут переменные:
x11 x12 x13 x14
x21 x22 x23 x24
x31 x32 x33 x34
В результате в Excel получается следующий промежуточный итог:
Далее, применяя метод Северо-западного угла, строим опорный план. Пошагово это выглядит следующим образом:
| Шаг 1 | Выполняем расчет min(запас; потребность). Начинаем с верхней левой клетки (B2) |
| Минимум | МИН(40;20) |
| в B2 пишем | 20 |
| Остатки: | |
| Склад А1 | 20 |
| Магазин В1 | 0 |
| Шаг 2 | |
| Переходим вправо к C2 | |
| Минимум | МИН(20;30) |
| в C2 пишем | 20 |
| Остатки: | |
| A1 | 0 |
| B2 | 10 |
| Шаг 3 | |
| Переходим вниз к C3 | |
| Минимум | МИН(30;10) |
| в C3 пишем | 10 |
| Остатки | |
| A2 | 20 |
| B2 | 0 |
| Шаг 4 | |
| Переходим вправо к D3 | |
| Минимум | МИН(20;25) |
| в D3 пишем | 20 |
| Остатки | |
| A2 = | 0 |
| B3 = | 5 |
| Шаг 5 | |
| Переходим вниз к D4 | |
| Минимум | МИН(20;5) |
| в D4 пишем | 5 |
| Остатки | |
| A3 = | 15 |
| B3 = | 0 |
| Шаг 6 | |
| Переходим вправо к E4 | |
| Минимум | МИН(15;15) |
| в E4 запишем | 15 |
| Шаг 7. Проверка сумм | |
| должно выполняться: | F2:F4 = B5:E5 |
| Сумма G2:G4 = Сумма B6:E6 | |
| Шаг 8. Создаём функцию стоимости. | |
| В A12 запишем "Общая стоимость" | |
| В B12 запишем формулу СУММПРОИЗВ(B2:E4;B8:E10) |
Таким образом будет получен опорный план, не гарантирующий оптимальность решения.
Шаг 9. Используем модуль "Поиск решения"
Для открытия модуля: Данные → Поиск решения
Настройки модуля:
Целевая функция: выбрать
Установить переключатель в Минимум
Изменяемые ячейки: выбрать
Ограничения (добавляем):
1. Поставщики
G2 = 40
G3 = 30
G4 = 20
2. Потребители
B6 = 20
C6 = 30
D6 = 25
E6 = 15
3. Неотрицательность
B2:E4 >= 0
4. Метод решения:
Выбирать: Симплекс-метод
5. Запуск
Нажать: Выполнить
Настройки модуля "Поиск решения" приведены на рисунке:
в результате Excel найдёт оптимальное решение:
Как видим, оно отличается от величины затрат, которая получена первоначально методом Северо-западного угла.
Итак, получены:
оптимальные значения перевозок
минимальную стоимость в ячейке B12
Метод северо-западного угла дал начальный план, а модуль "Поиск решения" нашёл оптимальный.
Важное замечание:
Метод северо-западного угла:
быстро даёт опорное решение
не гарантирует оптимальность
Поэтому его обычно используют: Северо-западный угол → начальный план → оптимизация (Анализ данных в Excel)
Хотите заказать помощь в решении задачи по ABC - анализу в логистике? Это просто!
Необходимо сделать только три шага:
- прислать условия задач;
- согласовать сроки решения и форму оплаты;
- перевести предоплату и получить решенные задачи.
Пришлите условия задач на предварительную оценку, это бесплатно!
