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

Решение транспортной задачи методом северо-западного угла

Метод северо-западного угла — это определенная совокупность приемов, направленных на получение допустимого начального решения транспортной задачи.

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

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

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

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

Искомая (т. е. неизвестная) величина в транспортной задаче — это объем перевозки от поставщиков к потребителям, при котором общие затраты на транспортировку минимизируются. Данная величина может быть определена путем применения различных методов. Так, чаще всего обращаются к таким методам, как:

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

«Решение транспортной задачи методом северо-западного угла» ��
Помощь эксперта по теме работы
Решение задач от ИИ за 2 минуты
Найди решение своей задачи среди 1 000 000 ответов

Помимо этого, решение транспортной задачи можно быть также найдено в программном продукте Microsoft Office Excel.

Общее представление о методе северо-западного угла

Метод северо-западного угла представляет собой метод (правило) получения допустимого начального решения транспортной задачи. Данный метод впервые был предложен американским математиком Джорджем Бернардом Данцигом в 1951 году. Название этому методу было присвоено другими американскими экономистами — Абрахамом Чэрнсом и Уильямом Вейджером Купером.

Метод северо-западного угла предполагает проведение последовательного перебора строк и столбцов транспортной таблицы. Начинается эта работа с левого столбца и верхней строки (именно поэтому метод был назван правилом северо-западного угла: вверх таблицы рассматривался как север, а ее левая сторона — как запад).

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

Пример использования метода северо-западного угла

Для того чтобы прояснить суть метода северо-западного угла, распишем пример решения одной транспортной задачи. В качестве начальных вводных условий мы будем предполагать существование поставщиков определенной продукции (поставщик А1 с запасом в 30 кг; поставщик А2 с запасом в 40 кг; поставщик А3 с запасом в 20 кг) и потребителей этой продукции (потребитель В1 с потребностью в 20 кг, потребитель В2 с потребностью в 30 кг, потребитель В3 с потребностью в 30 кг, потребитель В4 с потребностью в 10 кг).

Распределение поставок продукции начинается с первой, «северо-западной» ячейки транспортной таблицы, где пересекаются поставщик А1 и потребитель В1. В ячейку вписывается максимальный объем, который позволяет и запас поставщика, и спрос потребителя. Этот объем соответствует минимуму между заявленными запасами поставщика А1 (30 кг) и потребностями потребителя В1 (20 кг).

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

Переходим в следующую северо-западную ячейку, которая соответствует пересечению поставщика А1 и потребителя В2. В данном случае минимум выбираем между 10 кг запасов поставщика А1 и 30 кг потребностей потребителя В2.

В ячейку записывается значение 10 кг. Запасы поставщика А1 полностью исчерпаны, поэтому ячейки соответствующей (первой) строки заполняться больше не будут.

Следующая «северо-западная» ячейка — это пересечение поставщика А2 и потребителя В2. Здесь в ячейку будет записано значение в 20 кг. После этого спрос потребителя В2 окажется полностью удовлетворенным, в связи с чем в дальнейшем ячейки второго столбца заполняться не будут.

При переходе к следующей «северо-западной» ячейке будут сопоставляться запасы поставщика А2 (20 кг) и спрос потребителя В3 (30 кг). В ячейку запишут значение 20 кг. Это будет свидетельствовать об исчерпании всех запасов у поставщика А2, поэтому вторая строка больше заполняться не будет.

Дальше предметом изучения станет сопоставление данных по поставщику А3 (запасы — 20 кг) и потребителю В3 (спрос — 10 кг). Для заполнения ячейки запишем в нем значение в 10 кг.

И наконец остается последняя ячейка, которая соответствует «столкновению» запасов поставщика А3 и потребностей потребителя В4. Согласно условиям нашего примера, они равны друг другу — по 10 кг. Следовательно, весь груз от поставщиков (продукция) должен быть распределен по потребителям. Если же на данном этапе был зафиксирован недостаток или избыток груза, то это означает, что была допущена арифметическая ошибка, или задача не была приведена к закрытому виду.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение транспортной задачи методом северо-западного угла

Имеются три пункта отправления А1, А2, А3 однородного груза и пять пунктов В1, В2, В3, В4, В5 его назначения. На пунктах А1, А2, А3 груз находится в количестве а1, а2, а3 тонн соответственно. В пункты В1, В2, В3, В4, В5 требуется доставить соответственно b1, b2, b3, b4, b5 тонн груза. Расстояние в сотнях километров между пунктами отправления и назначения приведены в матрице D.
Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными. Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах; 2) для решения задачи использовать методы северо-западного угла и потенциалов.

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

Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 130 + 55 + 80 + 65 + 135 = 465
∑ b = 130 + 75 + 65 + 60 + 75 + 60 = 465
Условие баланса соблюдается. Запасы равны потребностям.
Занесем исходные данные в распределительную таблицу.

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

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

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

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

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

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 10, а должно быть m + n — 1 = 10. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы u i , vj . по занятым клеткам таблицы, в которых u i + vj = c ij , полагая, что u 1 = 0.
u 1 + v 1 = 6; 0 + v 1 = 6; v 1 = 6
u 2 + v 1 = 2; 6 + u 2 = 2; u 2 = -4
u 3 + v 1 = 3; 6 + u 3 = 3; u 3 = -3
u 3 + v 2 = 5; -3 + v 2 = 5; v 2 = 8
u 4 + v 2 = 5; 8 + u 4 = 5; u 4 = -3
u 4 + v 3 = 4; -3 + v 3 = 4; v 3 = 7
u 5 + v 3 = 6; 7 + u 5 = 6; u 5 = -1
u 5 + v 4 = 3; -1 + v 4 = 3; v 4 = 4
u 5 + v 6 = 8; -1 + v 6 = 8; v 6 = 9
u 1 + v 5 = 4; 0 + v 5 = 4; v 5 = 4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + vj > c ij
(1;2): 0 + 8 > 6; ∆ 12 = 0 + 8 — 6 = 2
(1;6): 0 + 9 > 3; ∆ 16 = 0 + 9 — 3 = 6
(4;6): -3 + 9 > 1; ∆ 46 = -3 + 9 — 1 = 5
(5;1): -1 + 6 > 2; ∆ 51 = -1 + 6 — 2 = 3
(5;2): -1 + 8 > 5; ∆ 52 = -1 + 8 — 5 = 2
(5;5): -1 + 4 > 2; ∆ 55 = -1 + 4 — 2 = 1
Выбираем максимальную оценку свободной клетки (1;6): 3
Для этого в перспективную клетку (1;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-«, «+», «-«. Цикл приведен в таблице.

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

4. Проверим оптимальность опорного плана. Найдем потенциалы u i , vj . по занятым клеткам таблицы, в которых u i + vj = c ij , полагая, что u 1 = 0.
u 1 + v 1 = 6; 0 + v 1 = 6; v 1 = 6
u 2 + v 1 = 2; 6 + u 2 = 2; u 2 = -4
u 3 + v 1 = 3; 6 + u 3 = 3; u 3 = -3
u 3 + v 2 = 5; -3 + v 2 = 5; v 2 = 8
u 4 + v 2 = 5; 8 + u 4 = 5; u 4 = -3
u 1 + v 5 = 4; 0 + v 5 = 4; v 5 = 4
u 1 + v 6 = 3; 0 + v 6 = 3; v 6 = 3
u 5 + v 6 = 8; 3 + u 5 = 8; u 5 = 5
u 5 + v 3 = 6; 5 + v 3 = 6; v 3 = 1
u 5 + v 4 = 3; 5 + v 4 = 3; v 4 = -2

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + vj > c ij
(1;2): 0 + 8 > 6; ∆ 12 = 0 + 8 — 6 = 2
(5;1): 5 + 6 > 2; ∆ 51 = 5 + 6 — 2 = 9
(5;2): 5 + 8 > 5; ∆ 52 = 5 + 8 — 5 = 8
(5;5): 5 + 4 > 2; ∆ 55 = 5 + 4 — 2 = 7
Выбираем максимальную оценку свободной клетки (5;1): 2
Для этого в перспективную клетку (5;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-«, «+», «-«. Цикл приведен в таблице.

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

4. Проверим оптимальность опорного плана. Найдем потенциалы u i , vj . по занятым клеткам таблицы, в которых u i + vj = c ij , полагая, что u 1 = 0.
u 1 + v 5 = 4; 0 + v 5 = 4; v 5 = 4
u 1 + v 6 = 3; 0 + v 6 = 3; v 6 = 3
u 5 + v 6 = 8; 3 + u 5 = 8; u 5 = 5
u 5 + v 1 = 2; 5 + v 1 = 2; v 1 = -3
u 2 + v 1 = 2; -3 + u 2 = 2; u 2 = 5
u 3 + v 1 = 3; -3 + u 3 = 3; u 3 = 6
u 3 + v 2 = 5; 6 + v 2 = 5; v 2 = -1
u 4 + v 2 = 5; -1 + u 4 = 5; u 4 = 6
u 5 + v 3 = 6; 5 + v 3 = 6; v 3 = 1
u 5 + v 4 = 3; 5 + v 4 = 3; v 4 = -2

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + vj > c ij
(2;3): 5 + 1 > 3; ∆ 23 = 5 + 1 — 3 = 3
(2;5): 5 + 4 > 8; ∆ 25 = 5 + 4 — 8 = 1
(2;6): 5 + 3 > 5; ∆ 26 = 5 + 3 — 5 = 3
(3;5): 6 + 4 > 6; ∆ 35 = 6 + 4 — 6 = 4
(4;3): 6 + 1 > 4; ∆ 43 = 6 + 1 — 4 = 3
(4;5): 6 + 4 > 2; ∆ 45 = 6 + 4 — 2 = 8
(4;6): 6 + 3 > 1; ∆ 46 = 6 + 3 — 1 = 8
(5;5): 5 + 4 > 2; ∆ 55 = 5 + 4 — 2 = 7
Выбираем максимальную оценку свободной клетки (4;5): 2
Для этого в перспективную клетку (4;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-«, «+», «-«. Цикл приведен в таблице.

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 6) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

4. Проверим оптимальность опорного плана. Найдем потенциалы u i , vj . по занятым клеткам таблицы, в которых u i + vj = c ij , полагая, что u 1 = 0.
u 1 + v 5 = 4; 0 + v 5 = 4; v 5 = 4
u 4 + v 5 = 2; 4 + u 4 = 2; u 4 = -2
u 4 + v 2 = 5; -2 + v 2 = 5; v 2 = 7
u 3 + v 2 = 5; 7 + u 3 = 5; u 3 = -2
u 3 + v 1 = 3; -2 + v 1 = 3; v 1 = 5
u 2 + v 1 = 2; 5 + u 2 = 2; u 2 = -3
u 5 + v 1 = 2; 5 + u 5 = 2; u 5 = -3
u 5 + v 3 = 6; -3 + v 3 = 6; v 3 = 9
u 5 + v 4 = 3; -3 + v 4 = 3; v 4 = 6
u 1 + v 6 = 3; 0 + v 6 = 3; v 6 = 3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + vj > c ij
(1;2): 0 + 7 > 6; ∆ 12 = 0 + 7 — 6 = 1
(1;3): 0 + 9 > 8; ∆ 13 = 0 + 9 — 8 = 1
(1;4): 0 + 6 > 5; ∆ 14 = 0 + 6 — 5 = 1
(2;3): -3 + 9 > 3; ∆ 23 = -3 + 9 — 3 = 3
(4;3): -2 + 9 > 4; ∆ 43 = -2 + 9 — 4 = 3
Выбираем максимальную оценку свободной клетки (2;3): 3
Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-«, «+», «-«. Цикл приведен в таблице.

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 55. Прибавляем 55 к объемам грузов, стоящих в плюсовых клетках и вычитаем 55 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

4. Проверим оптимальность опорного плана. Найдем потенциалы u i , vj . по занятым клеткам таблицы, в которых u i + vj = c ij , полагая, что u 1 = 0.
u 1 + v 5 = 4; 0 + v 5 = 4; v 5 = 4
u 4 + v 5 = 2; 4 + u 4 = 2; u 4 = -2
u 4 + v 2 = 5; -2 + v 2 = 5; v 2 = 7
u 3 + v 2 = 5; 7 + u 3 = 5; u 3 = -2
u 3 + v 1 = 3; -2 + v 1 = 3; v 1 = 5
u 5 + v 1 = 2; 5 + u 5 = 2; u 5 = -3
u 5 + v 3 = 6; -3 + v 3 = 6; v 3 = 9
u 2 + v 3 = 3; 9 + u 2 = 3; u 2 = -6
u 5 + v 4 = 3; -3 + v 4 = 3; v 4 = 6
u 1 + v 6 = 3; 0 + v 6 = 3; v 6 = 3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + vj > c ij
(1;2): 0 + 7 > 6; ∆ 12 = 0 + 7 — 6 = 1
(1;3): 0 + 9 > 8; ∆ 13 = 0 + 9 — 8 = 1
(1;4): 0 + 6 > 5; ∆ 14 = 0 + 6 — 5 = 1
(4;3): -2 + 9 > 4; ∆ 43 = -2 + 9 — 4 = 3
Выбираем максимальную оценку свободной клетки (4;3): 4
Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-«, «+», «-«. Цикл приведен в таблице.

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

4. Проверим оптимальность опорного плана. Найдем потенциалы u i , vj . по занятым клеткам таблицы, в которых u i + vj = c ij , полагая, что u 1 = 0.
u 1 + v 5 = 4; 0 + v 5 = 4; v 5 = 4
u 4 + v 5 = 2; 4 + u 4 = 2; u 4 = -2
u 4 + v 2 = 5; -2 + v 2 = 5; v 2 = 7
u 3 + v 2 = 5; 7 + u 3 = 5; u 3 = -2
u 3 + v 1 = 3; -2 + v 1 = 3; v 1 = 5
u 5 + v 1 = 2; 5 + u 5 = 2; u 5 = -3
u 5 + v 4 = 3; -3 + v 4 = 3; v 4 = 6
u 4 + v 3 = 4; -2 + v 3 = 4; v 3 = 6
u 2 + v 3 = 3; 6 + u 2 = 3; u 2 = -3
u 1 + v 6 = 3; 0 + v 6 = 3; v 6 = 3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + vj > c ij
(1;2): 0 + 7 > 6; ∆ 12 = 0 + 7 — 6 = 1
(1;4): 0 + 6 > 5; ∆ 14 = 0 + 6 — 5 = 1
Выбираем максимальную оценку свободной клетки (1;2): 6
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-«, «+», «-«. Цикл приведен в таблице.

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 2) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

4. Проверим оптимальность опорного плана. Найдем потенциалы u i , vj . по занятым клеткам таблицы, в которых u i + vj = c ij , полагая, что u 1 = 0.
u 1 + v 2 = 6; 0 + v 2 = 6; v 2 = 6
u 3 + v 2 = 5; 6 + u 3 = 5; u 3 = -1
u 3 + v 1 = 3; -1 + v 1 = 3; v 1 = 4
u 5 + v 1 = 2; 4 + u 5 = 2; u 5 = -2
u 5 + v 4 = 3; -2 + v 4 = 3; v 4 = 5
u 1 + v 5 = 4; 0 + v 5 = 4; v 5 = 4
u 4 + v 5 = 2; 4 + u 4 = 2; u 4 = -2
u 4 + v 3 = 4; -2 + v 3 = 4; v 3 = 6
u 2 + v 3 = 3; 6 + u 2 = 3; u 2 = -3
u 1 + v 6 = 3; 0 + v 6 = 3; v 6 = 3

Опорный план является оптимальным.
Затраты составят:
F(x) = 6*50 + 4*20 + 3*60 + 3*55 + 3*55 + 5*25 + 4*10 + 2*55 + 2*75 + 3*60 = 1495

Пример №2 . Из трех пунктов хранения (или производства) требуется доставить однородный груз в пять пунктов потребления. Количество груза N в каждом пункте отправления, объемы потребления M, а также стоимости C перевозки единицы груза из пункта отправления A в пункт потребления B указаны в таблице.
Составить такой план перевозок, при котором общая стоимость была бы минимальной.
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов.

Решение получаем с помощью калькулятора. Максимальная стоимость в данной матрице тарифов равна 11 . Поэтому вместо прочерков достаточно указать значение в 2 раза больше заданного. Например, 22 (2*11).

Решение задачи методом северо–западного угла и потенциалов

Имеются три пункта отправления A ₁ , A₂, A ₃ однородного груза и пять пунктов B₁,B₂,B₃,B₄,B₅ его назначения. На пунктах A₁,A₂, A₃ груз находится в количестве a₁, a₂, a₃ тонн соответственно. В пункты B₁,B₂,B₃,B₄,B₅ требуется доставить соответственно b₁,b₂,b₃,b₄,b₅ тонн груза. Расстояния в сотнях километров между пунктами отправления и назначения приведены в матрице D:

Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными.
Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно–километрах; 2) для решения задачи использовать методы северо–западного угла и потенциалов.

Финансовый анализ онлайн

Анализ и диагностика финансово-хозяйственной деятельности предприятия:
· Оценка имущественного положения
· Анализ ликвидности и платежеспособности
· Анализ финансовой устойчивости
· Анализ рентабельности и оборачиваемости
· Анализ движения денежных средств
· Анализ финансовых результатов и многое другое

Аннуитетные платежи онлайн

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

Профессии будущего

РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса

• Задать вопрос или оставить комментарий
• Помощь в решении
• Поиск
• Поддержать проект

Правила ввода данных

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

Поиск

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

Транспортная задача. Опорное решение [ч.2]

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

Теорема 2 Свойство системы ограничений транспортной задачи

Ранг системы векторов-условий транспортной задачи равен N=m+n-1 (m – поставщики, n-потребители)

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

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

Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n – 1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равняется m+n-1, а для вырожденного опорного решения меньше m+n-1

Циклом называется такая последовательность клеток таблицы транспортной задачи (i₁, j₁),(i₁, j₂),(i₂, j₂). (i_k, j₁), в которой две и только две соседние клетки распложены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

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

Допустимое решение транспортной задачи X=(x_ij) является опорным тогда и только тогда, когда из занятых клеток таблицы нельзя образовать ни одного цикла.

Метод вычеркивания

Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.

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

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

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

Если же после вычеркивания останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов-условий является линейно зависимой, а решение не является опорным.

Примеры «вычеркнутого» (опорного) и «не вычеркнутого» (не опорного решений):

Логика вычеркивания:

1. Вычеркнуть все столбцы, в которых всего одна занятая клетка (5 0 0), (0 9 0)
2. Вычеркнуть все строки, в которых всего одна занятая клетка (0 15), (2 0)
3. Повторить цикл (7) (1)

Методы построения начального опорного решения

Метод северо-западного угла

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

Заполнение таблицы транспортной задачи начинается с левого верхнего угла, поэтому и называется метод северо-западного угла.

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

Составить опорное решение, используя метод северо-западного угла.

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

Пример: так как его запасы a₁ =100 меньше запросов первого потребителя b₁ =100, то в клетку (1,1) записываем перевозку x₁₁=100 и исключаем из рассмотрения поставщика.
Определяем оставшиеся неудовлетворенными запросы 1-го потребителя b 1 = 150-100=50.

150_надо-100_было=50_{осталось}
Осталось удовлетворить
запросов на 50 единиц товара

2. Распределяем запасы 2-го поставщика.
Так как его запасы a₂ = 250 больше оставшихся неудовлетворенными запросов 1-го потребителя b 1 =50, то в клетку (2,1) записываем перевозку x₂₁ =50 и исключаем из рассмотрения 1-го потребителя.
Определяем оставшиеся запасы 2-го поставщика a 2 = a₂ – b 1 = 250-50=200. Так как оставшиеся запасы 2-го поставщика равны запросам 2-го потребителя, то в клетку (2,2) записываем x₂₂=200 и исключаем по своему усмотрению либо 2-го поставщика, либо 2-го потребителя. В нашем примере мы исключили 2-го поставщика.
Вычисляем оставшиеся неудовлетворенными запросы второго потребителя b 2 =b₂-a₂=200-200=0.

150	200	100	100
100	100
250	50	200		250-50=200 200-200=0
200
150-100-50=0

3. Распределяем запасы 3-го поставщика.
Важно! В предыдущем шаге у нас был выбор исключать поставщика или потребителя. Так как мы исключили поставщика, то запросы 2-го потребителя все же остались (хоть и равны нулю).
Мы должны записать оставшиеся запросы равные нулю в клетку (3,2)
Это связано с тем, что если в очередную клетку таблицы (i,j) требуется поставить перевозку, а поставщик с номером i или потребитель с номером j имеет нулевые запасы или запросы, то ставится в клетку перевозка, равная нулю (базисный нуль), и после этого исключается из рассмотрения либо соответствующий поставщик, либо потребитель.
Таким образом, в таблицу заносятся только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.

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

Так как в предыдущем шаге мы исключили из рассмотрения второго поставщика, то в клетку (3,2) записываем x₃₂=0 и исключаем второго потребителя.

Запасы 3-го поставщика не изменились. В клекту (3,3) записываем x₃₃=100 и исключаем третьего потребителя. В клетку (3,4) записываем x₃₄=100. Ввиду того, что наша задача с правильным балансом, запасы всех поставащиков исчерпаны и запросы всех потребителей удовлетворены полностью и одновременно.

Опорное решение
150	200	100	100
100	100
250	50	200
200	0	100	100

4. Проверяем правильность построения опорного решения.
Число занятых клеток должно быть равно N=m(поставщики)+m(потребители) – 1=3+4 – 1=6.
Применяя метод вычеркивания, убеждаемся, что найденное решение является «вычеркиваемым» (звездочкой отмечен базисный нуль).

Следовательно, векторы-условий, соответствующие занятым клеткам, линейно независимы и построенное решение действительно является опорным.

Метод минимальной стоимости

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=(c_ij).

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

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

Используя метод минимальной стоимости построить начальное опорное решение транспортной задачи.

1. Запишем отдельно матрицу стоимостей для того, чтобы было удобнее выбирать минимальные стоимости.

2. Среди элементов матрицы стоимостей выбираем наименьшую стоимость C₁₁=1, отмечаем ее кружочком. Данная стоимость имеет место при перевозке груза от 1-го поставщика 1-му потребителю. В соответствующую клетку записываем максимально возможный объем перевозки:
x₁₁ = min 1; b₁> = min =40 т.е. минимум между запасами 1-го поставщика и запросами 1-го потребителя.

2.1. Запасы 1-го поставщика уменьшаем на 40.
2.2. Исключаем из рассмотрения 1-го потребителя, так как его запросы полностью удовлетворены. В матрице C вычеркиваем 1-ый столбец.

3. В оставшейся части матрицы C минимальной стоимостью является стоимость C₁₄=2. Максимально возможная перевозка, которую можно осуществить от 1-го поставщика 4-му потребителю равна x₁₄ = min 1‘; b₄> = min = 20, где a₁ со штрихом это оставшиеся запасы первого поставщика.
3.1. Запасы 1-го поставщика исчерпаны, поэтому исключаем его из рассмотрения.
3.2. Запросы 4-го потребителя уменьшаем на 20.

4. В оставшейся части матрицы С минимальная стоимость C₂₄=C₃₂=3. Заполняем одну из двух клеток таблицы (2,4) или (3,2). Пусть в клетку запишем x₂₄ = min 2; b₄> = min =40 .
4.1. Запросы 4-го потребителя удовлетворены. Исключаем его из рассмотрения вычеркивая 4-й столбец в матрице C.
4.2. Уменьшаем запасы 2-го поставщика 80-40=40.

5. В оставшейся части матрицы C минимальная стоимость C₃₂=3. Запишем в клетку (3,2) таблицы перевозку x₃₂ = min 3; b₂> = min =60.
5.1. Исключим из рассмотрения 2-го потребителя. Из матрицы C исключаем 2-ой столбец.
5.2. Уменьшим запасы 3-го поставщика 100-60=40

6. В оставшейся части матрицы C минимальная стоимость C₃₃=6. Запишем в клетку (3,3) таблицы перевозку x₃₃ = min 3‘; b₃> = min =40
6.1. Исключим из рассмотрения 3-го поставщика, а из матрицы C 3-ю строку.
6.2. Определяем оставшиеся запросы 3-го потребителя 80-40=40.

7. В матрице C остался единственный элемент C₂₃=8. Записываем в клетку таблицы (2,3) перевозку X₂₃=40.

8. Проверяем правильность построения опорного решения.
Число занятых клеток таблицы равно N=m+n – 1=3+4 -1.
Методом вычеркивания проверяем линейную независимость векторов-условий, соответствующих положительным координатам решения. Порядок вычеркивания показан на матрице X:

Вывод: Решение методом минимальной стоимости (таблица 38.3) является «вычеркиваемым» и, следовательно опорным.

• Арифметика
  • Свойства арифметических действий
  • Формулы сокращенного умножения
  • Геометрическая прогрессия
  • Корни и степени. Свойства корней n-ой степени. Таблица корней
  • Арифметическая прогрессия. Формула суммы арифметической прогрессии
  • Модуль числа, его определение и геометрический смысл. Решение уравнений и неравенств, содержащих модуль числа
  • Логарифм и его свойства. Примеры решения логарифмов
  • Показательные уравнения: примеры и решения
  • Квадратное уравнение и решение полных и неполных квадратных управнений
  • Биквадратное уравнение и методы и примеры его решения
  • Экономико-математические методы и модели анализа
  • Метод наименьших квадратов
  • Тригонометрический круг
  • Тригонометрические формулы и тригонометрические функции
  • Решения простейших тригонометрических уравнений
  • Решение уравнений cosx= 0, 1, -1.
  • N-мерные матрицы. Умножение и сложение N-мерных матриц
  • Решение систем линейных уравнений методом Жордана-Гаусса
  • Система линейных уравнений и её виды. Матричная форма записи системы линейных уравнений
  • Линейная зависимость векторов. Базис системы векторов
  • Обратная матрица. Решение матричных уравнений. Алгоритм нахождения обратной матрицы
  • Определитель матрицы. Метод Крамера
  • Математические модели задач линейного программирования
  • Симплексный метод решения задач линейного программирования
  • Транспортная задача. Математическая модель [ч.1]
  • Транспортная задача. Опорное решение [ч.2]. Метод северо-западного угла
  • Множество и операции над множествами
  • Производная функции. Правила дифференцирования и таблица производных
  Похожие публикации:
  1. Tkinter как скрыть окно
  2. Как зайти на сетевой диск astra linux
  3. Как проходит работа программиста
  4. Как удалить people в windows 10 полностью