Как решать тз методом северо западного угла
Перейти к содержимому

Как решать тз методом северо западного угла

  • автор:

Сервис для решения задач по линейному программированию

Пример №4. Решение транспортной задачи линейного программирования.
Метод северо-западного угла (сбалансированная задача)

Данное решение сделано калькулятором, представленным на сайте.
Задача:

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

Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.
Решение:

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

Проверим.
Запасы поставщиков: 10 + 20 + 30 = 60 единиц продукции.
Потребность потребителей: 15 + 20 + 25 = 60 единиц продукции.

Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.

Для решения задачи необходимо выполнение следующего условия:
количество задействованных маршрутов = количество поставщиков + количество потребителей — 1.

Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.

Начинаем заполнять таблицу от левого верхнего угла и постепенно «двигаемся» к правому нижнему.
От северо-запада к юго-востоку.

Транспортная задача: метод Северо-Западного угла

Методов формирования опорного плана в транспортной задаче придумано немало, но, пожалуй, самый простой из них — метод «Северо-Западного угла» (диагональный метод). Алгоритм заполнения клеток транспортной таблицы в его случае сводится к следующему: сначала заполняется клетка в верхнем левом («северо-западном») углу, затем следующая клетка справа и т. д., пока не заполнится вся строка. Затем мы переходим ко второй строке и снова заполняем ее слева направо. И так далее.

Метод «Северо-Западного угла», в самом деле, прост и понятен, но его недостаток — низкая эффективность. Сформированный с его помощью план в большинстве случаев не является оптимальным.

Формирование опорного плана методом Северо-Западного угла

Итак, у нас имеется транспортная таблица с исходными данными.

Формирование опорного плана начинаем с внесения в верхнюю левую клетку максимально возможного объема перевозки.

Запасы на складе A1 закончились, поэтому в оставшиеся ячейки данной строки ставим прочерки. Затем переходим к следующей строке и заполняем ее ячейки слева направо.

Переходим к третьей строке и тоже заполняем ее слева направо.

Все, нами получен опорный план. Еще раз отмечу, что при методе «Северо-Западного угла» транспортная таблица просто заполняется в направлении сверху вниз и слева-направо (образно говоря, по диагонали).

Источники Показать

  1. Метод Северо-Западного угла // Циклопедия. URL: http://cyclowiki.org/wiki/Метод_северо-западного_угла (дата обращения: 2.11.2013)

© Копирование любых материалов статьи допустимо только при указании прямой индексируемой ссылки на источник: Галяутдинов Р.Р.

Если понравилась статья, поделитесь с друзьями и подпишитесь на обновления:

Нашли опечатку? Помогите сделать статью лучше! Выделите орфографическую ошибку мышью и нажмите Ctrl + Enter.

Решение транспортной задачи

Полученное решение сохраняется в файле Word (Пример решения транспортной задачи). Также автоматически генерируется шаблон решения в Excel .

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП

Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

Задачи динамического программирования

  • вычеркивания (метод двойного предпочтения);
  • северо-западного угла;
  • минимального элемента;
  • аппроксимации Фогеля.

Опорное решение транспортной задачи

Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения, используют циклы.
Циклом называется такая последовательность клеток таблицы транспортной задачи, в которой две и только соседние клетки расположены в одной строке или столбце, причем первая и последняя также находятся в одной строке или столбце. Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи , i=1,2. m; j=1,2. n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла. Приближенные методы решения транспортной задачи.
Метод вычеркивания (метод двойного предпочтения). Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждом столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным.
Метод «северо-западного угла» состоит в последовательном переборе строк и столбцов транспортной таблицы, начиная с левого столбца и верхней строки, и выписывании максимально возможных отгрузок в соответствующие ячейки таблицы так, чтобы не были превышены заявленные в задаче возможности поставщика или потребности потребителя. На цены доставки в этом методе не обращают внимание, поскольку предполагается дальнейшая оптимизация отгрузок.
Метод «минимального элемента». Отличаясь простотой данный метод все же эффективнее чем, к примеру, метод Северо-западного угла. Кроме того, метод минимального элемента понятен и логичен. Его суть в том, что в транспортной таблице сначала заполняются ячейки с наименьшими тарифами, а потом уже ячейки с большими тарифами. То есть мы выбираем перевозки с минимальной стоимостью доставки груза. Это очевидный и логичный ход. Правда он не всегда приводит к оптимальному плану.
Метод «аппроксимации Фогеля». При методе аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации. Пример №1 . Матрица тарифов (здесь количество поставщиков равно 4 , количество магазинов равно 6 ):

Решение. Предварительный этап решения транспортной задачи сводится к определению ее типа, открытой она является или закрытой. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
Условие баланса соблюдается. Запасы равны потребностям. Итак, модель транспортной задачи является закрытой. Если бы модель получилась открытой, то потребовалось бы вводить дополнительных поставщиков или потребителей.
На втором этапе осуществляется поиск опорного плана методами, приведенными выше (наиболее распространенным является метод наименьшей стоимости).
Для демонстрации алгоритма приведем лишь несколько итераций.
Итерация №1. Минимальный элемент матрицы равен нулю. Для этого элемента запасы равны 60 , потребности 30 . Выбираем из них минимальное число 30 и вычитаем его (см. в таблице). При этом из таблицы вычеркиваем шестой столбец (потребности у него равны 0).

3 20 8 13 4 x 80
4 4 18 14 3 0 60 — 30 = 30
10 4 18 8 6 x 30
7 19 17 0 1 x 60
10 30 40 50 70 30 — 30 = 0 0

Итерация №2. Снова ищем минимум (0). Из пары (60;50) выбираем минимальное число 50. Вычеркиваем пятый столбец.

3 20 8 x 4 x 80
4 4 18 x 3 0 30
10 4 18 x 6 x 30
7 19 17 0 1 x 60 — 50 = 10
10 30 40 50 — 50 = 0 70 0 0

Итерация №3. Процесс продолжаем до тех пор, пока не выберем все потребности и запасы.
Итерация №N. Искомый элемент равен 8. Для этого элемента запасы равны потребностям (40).

3 x 8 x 4 x 40 — 40 = 0
x x x x 3 0 0
x 4 x x x x 0
x x x 0 1 x 0
0 0 40 — 40 = 0 0 0 0 0
1 2 3 4 5 6 Запасы
1 3[10] 20 8[40] 13 4[30] 100 80
2 4 4 18 14 3[30] 0[30] 60
3 10 4[30] 18 8 6 0 30
4 7 19 17 0[50] 1[10] 100 60
Потребности 10 30 40 50 70 30

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n — 1 = 9. Следовательно, опорный план является вырожденным. Строим новый план. Иногда приходится строить несколько опорных планов, прежде чем найти не вырожденный.

1 2 3 4 5 6 Запасы
1 3[10] 20 8[40] 13[30] 4 100 80
2 4 4[20] 18 14 3[10] 0[30] 60
3 10 4[10] 18 8[20] 6 0 30
4 7 19 17 0 1[60] 100 60
Потребности 10 30 40 50 70 30

В результате получен первый опорный план, который является допустимым, так как число занятых клеток таблицы равно 9 и соответствует формуле m + n — 1 = 6 + 4 — 1 = 9, т.е. опорный план является невырожденным.
Третий этап заключается в улучшении найденного опорного плана. Здесь используют метод потенциалов или распределительный метод. На этом этапе правильность решения можно контролировать через функцию стоимости F(x) . Если она уменьшается (при условии минимизации затрат), то ход решения верный. Пример №2 . Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов.

30 50 70 10 30 10
40 2 4 6 1 1 2
80 3 4 5 9 9 6
60 4 3 2 7 8 7
20 5 1 3 5 7 9

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

Кондитерская фабрика Стоимость производства одного центнера кондитерских изделий Месячная производительность кондитерских изделий
1 2 3
1 3 4 3 30
2 2 3 5 20
3 1 2 3 10
4 4 5 8 30
Месячная потребность в кондитерских изделиях 30 20 30

Примечание. Здесь предварительно можно транспонировать таблицу затрат, поскольку для классической постановки транспортной задачи сначала следуют мощности (производство), а потом потребители.

Кондитерская фабрика Стоимость производства одного центнера кондитерских изделий Месячная потребность в кондитерских изделиях
1 2 3 4
1 3 2 1 4 30
2 4 3 2 5 20
3 3 5 3 8 30
Месячная производительность кондитерских изделий 30 20 10 30

Пример №4 . На строительство объектов кирпич поступает с трех (I, II, III) заводов. Заводы имеют на складах соответственно 50, 100 и 50 тыс. шт. кирпича. Объекты требуют соответственно 50, 70, 40 и 40 тыс. шт. кирпича. Тарифы (ден. ед./тыс.шт.) приведены в таблице. Составьте план перевозок, минимизирующий суммарные транспортные расходы.

Завод Тариф, ден. ед./тыс.шт. Запасы
1 2 3 4
I 2 6 2 3 50
II 5 2 1 7 100
III 4 5 7 8 50
Потребности 50 70 40 40

Пример №5 . Транспортная задача, заданная таблицей

60 a
35 3 8
20 4 1
b 2 3

будет закрытой если:
А) a=40, b=45
Б) a=45, b=40
В) a=11, b=12
Условие закрытой транспортной задачи: ∑a = ∑b
Находим, ∑a = 35+20+b = 55+b; ∑b = 60+a
Получаем: 55+b = 60+a
Равенство будет соблюдаться только при a=40, b=45

Транспортная задача — решение методом потенциалов

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

Например, у нас есть сеть розничных магазинов, которым требуется определенное количество товаров. Также имеется ряд складов поставщиков, где требуемые товары хранятся. При этом на каждом складе различный объем запасов этих товаров. Кроме этого нам известны тарифы — затраты на перевозку 1 товара от каждого склада к каждому магазину.

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

  • теоретический материал по транспортной задаче;
  • общий план решения методом потенциалов;
  • подробный пример решения транспортной задачи;
  • практическое применение транспортной задачи.

Теоретический материал по транспортной задаче

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

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

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

где: Z — затраты на перевозку грузов;

X — объем груза;

C — стоимость (тариф) перевозки единицы груза;

A — запас поставщика;

B — запрос потребителя;

m — число поставщиков;

n — число потребителей.

Общий план решения транспортной задачи методом потенциалов

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

Суть его в следующем: находим некий опорный план и проверяем его на оптимальность (Z → min). Если план оптимален — решение найдено. Если нет — улучшает план столько раз, сколько потребуется, пока не будет найден оптимальный план.

Ниже приведен алгоритм решения транспортной задачи в самом общем виде:

  1. Построение транспортной таблицы.
  2. Проверка задачи на закрытость.
  3. Составление опорного плана.
  4. Проверка опорного плана на вырожденность.
  5. Вычисление потенциалов для плана перевозки.
  6. Проверка опорного плана на оптимальность.
  7. Перераспределение поставок.
  8. Если оптимальное решение найдено, переходим к п. 9, если нет — к п. 5.
  9. Вычисление общих затрат на перевозку груза.
  10. Построение графа перевозок.

Подробная инструкция по решению транспортной задачи

1. Построение транспортной таблицы

Заполняем транспортную таблицу с исходными данными, где указываем запасы материалов, имеющиеся на складах поставщиков (Ai), и потребности заводов (Bj) в этих материалах.

В нижний правый угол ячеек таблицы заносим значение тарифов на перевозку груза (Cij).

2. Проверка задачи на закрытость

Обозначим суммарный запас груза у всех поставщиков символом A, а суммарную потребность в грузе у всех потребителей — символом B.

Транспортная задача называется закрытой, если A = B . Если же A ≠ B , то транспортная задача называется открытой. В случае закрытой задачи от поставщиков будут вывезены все запасы груза, и все заявки потребителей будут удовлетворены. В случае открытой задачи для ее решения придется вводить фиктивных поставщиков или потребителей.

Проверим задачу на закрытость:

A = 10 + 20 + 30 = 60.

B = 15 + 20 + 25 = 60.

A = B, следовательно данная транспортная задача — закрытая.

3. Составление опорного плана

Составляет предварительный (опорный) план перевозок. Он не обязательно должен быть оптимальный. Это просто своеобразный «черновик» или «набросок», итерационно улучшая который мы постепенно придем к оптимальному плану.

Есть разные методы нахождения опорного плана. Наиболее распространены следующие:

а) Метод Северо-Западного угла Показать

Суть метода проста — ячейки транспортной таблицы последовательно заполняются максимально возможными объемами перевозок, в направлении сверху вниз и слева направо. То есть сперва заполняется самая верхняя левая ячейка («северо-западная» ячейка), потом следующая справа и т. д. Затем переходят на новую строку и вновь заполняют ее слева направо. И так пока таблица не будет заполнена полностью.

Подробное описание метода и пример можно посмотреть здесь.

б) Метод минимального элемента Показать

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

Подробное описание метода и пример можно посмотреть здесь

в) Аппроксимация Фогеля Показать

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

Подробное описание аппроксимации Фогеля и пример можно посмотреть здесь

г) Метод двойного предпочтения Показать

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

Подробное описание метода и пример можно посмотреть здесь

Выберите один из методов и пройдите по ссылке в его описании, чтобы посмотреть как в данном примере был составлен опорный план и заполнена транспортная таблица.

4. Проверка опорного плана на вырожденность

Клетки таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а остальные (пустые) — свободными.

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

Проводить пополнение плана, выбирая клетки произвольно, нельзя. План должен быть ациклическим!

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

Ломаная линия может иметь точки самопересечения, но не в клетках цикла.

В нашем примере количество базисных клеток = 5; m + n — 1 = 3 + 3 — 1 = 5.

Следовательно, первоначальный план перевозок — невырожденный (5 = 5).

5. Вычисление потенциалов для плана перевозки

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

Этот метод улучшения плана перевозок называется методом потенциалов. Есть другие методы итерационного улучшения плана перевозок, но здесь мы их рассматривать не будем.

Итак, сопоставим каждому поставщику Ai и каждому потребителю Bj соответствующие величины Ui и Vj так, чтобы для всех базисных клеток плана было выполнено следующее соотношение: Ui + Vj = Cij.

Добавим к транспортной таблице дополнительную строку и столбец для Ui и Vj.

Предположим, что U1 = 0.

Тогда мы сможем найти V3 = C13 — U1 = 1 — 0 = 1.

Зная V3, мы теперь можем найти U3:

По аналогии вычисляем все оставшиеся потенциалы:

6. Проверка плана на оптимальность методом потенциалов

Для каждой свободной клетки плана вычислим разности ΔCij = Cij — (Ui + Vj ), и запишем полученные значения в левых нижних углах соответствующих ячеек.

План является оптимальным, если все разности ΔCij ≥ 0.

В данном случае план — неоптимальный (ΔC22 < 0), и его следует улучшить путем перераспределения поставок.

7. Перераспределение поставок

Найдем ячейку с наибольшей по абсолютной величине (т. е. без учета знака, по модулю) отрицательной разностью ΔCij и построим цикл, в котором кроме этой клетки все остальные являются базисными. Такой цикл всегда существует и единственен.

Отметим ячейку с отрицательной разностью ΔCij знаком «+», следующую знаком «», и так далее, поочередно.

Затем находим минимальное значение груза в ячейках цикла имеющих знак «-» (здесь это 5) и вписываем его в свободную ячейку со знаком «+». Затем последовательно обходим все ячейки цикла, поочередно вычитая и прибавляя к ним минимальное значение (в соответствии со знаками, которыми эти ячейки помечены: где минус — вычитаем, где плюс — прибавляем).

Получим новый опорный план перевозок:

Так как базисных клеток стало больше, чем m + n — 1, то базисную клетку с нулевым значением делаем свободной:

Снова вычисляем значения потенциалов и разности ΔCij:

На этот раз все разности ΔCij ячеек положительные, следовательно, найдено оптимальное решение.

8. Если оптимальное решение найдено, переходим к п. 9, если нет — к п. 5.

В нашем примере оптимальное решение найдено, поэтому переходим к пункту 9.

9. Вычисление общих затрат на перевозку груза

Вычислим общие затраты на перевозку груза (Z), соответствующие найденному нами оптимальному плану, по формуле:

То есть нужно перемножить значения объемов грузоперевозок на соответствующие им тарифы.

Zmin = 10 ⋅ 1 + 15 ⋅ 3 + 5 ⋅ 2 + 15 ⋅ 1 + 15 ⋅ 2 = 110 ден. ед.

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

10. Построение графа перевозок

Найдя оптимальный план перевозок, построим граф . Вершинами графа будут «склады» и «магазины». В вершинах укажем соответствующие объемы запасов и потребностей. Дугам, соединяющим вершины графа, будут соответствовать ненулевые перевозки. Каждую такую дугу подпишем, указав объем перевозимого груза.

В результате получится граф, аналогичный изображенному ниже:

Все, транспортная задача решена. Поздравляю!

Практическое применение транспортной задачи

Транспортная задача применяется во многих случаях. В частности:

  • оптимизация поставок сырья и материалов на производственные предприятия;
  • оптимизация доставок товаров со складов в розничные магазины;
  • оптимизация пассажирских перевозок.

Это далеко не полный перечень возможностей прикладного использования транспортной задачи.

Источники Показать

  1. Галяутдинов Р. Р. Конспект лекций по логистике
  2. Решение транспортной задачи в 1С: Предприятие 8.2 // Волшебный форум (@romix). URL: http://kb.mista.ru/article.php?id=859 (дата обращения: 29.10.2013)
  3. Транспортная задача // Википедия. URL: http://ru.wikipedia.org/wiki/Транспортная_задача (дата обращения: 29.10.2013)

© Копирование любых материалов статьи допустимо только при указании прямой индексируемой ссылки на источник: Галяутдинов Р.Р.

Если понравилась статья, поделитесь с друзьями и подпишитесь на обновления:

Нашли опечатку? Помогите сделать статью лучше! Выделите орфографическую ошибку мышью и нажмите Ctrl + Enter.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *