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

Для чего нужен метод северо-западного угла? что он дает?

Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. «Качество» опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное) , а метод северо-западного угла – наихудшее.

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

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

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

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

Если существующий запас позволяет перевезти всю потребность, то

· в клетку (i,j) в качестве перевозки вписывается значение потребности ;

· j-й столбец вычеркивается, поскольку его потребность уже исчерпана;

· от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т. е. .

Если существующий запас не позволяет перевезти всю потребность, то

· в клетку (i,j) в качестве перевозки вписывается значение запаса ;

· i-я строка вычеркивается, поскольку ее запас уже исчерпан;

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

Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы.

Метод минимального элемента

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

На каждом шаге метода Фогеля для каждой i-й строки вычисляются штрафы как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом .

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

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т. е. суммой штрафов по i-й строке и j-му столбцу.

5.2. Методические рекомендации

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

Если величина фиктивных тарифов превышает максимальный из реальных тарифов задачи [], то методы минимального элемента и Фогеля позволяют получить более дешевые планы перевозок, чем в случае с нулевыми фиктивными тарифами.

Найти тремя методами опорный план ТЗ, в которой запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырех магазинов равны 125, 90, 130, 100 ед. продукции,

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

Дальнейшая оптимизация решения

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

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Программа для решения транспортной задачи

maxizenit/TransportProblemCalculator

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Данная программа решает транспортную задачу двумя методами:

Для начала решения задачи необходимо ввести команду «nw» (для метода северо-западного угла) или «min» (для метода минимального элемента). После этого необходимо ввести все необходимые данные матрицы:

• количество пунктов отправления и назначения
• цены доставки из каждого пункта отправления в каждый пункт назначения
• запасы в каждом пункте отправления
• потребности в каждом пункте назначения

После этого программа пошагово выводит каждую доставку, а затем сумму стоимостей всех доставок.

About

Программа для решения транспортной задачи

Источник

Транспортная задача

Здравствуйте, пишу решение транспортной задачи методом потенциалов по этому алгоритму https://kb.mista.ru/article.php?id=859
На моменте с вычислением потенциалов по горизонтали и вертикали не передается в функцию Вычисления нужное значение
Подскажите, как это можно исправить?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

public boolean methodPotential() { int i, j; for (i = 1; i  m; i++) { u[i] = 999; } for (j = 1; j  n; j++) { v[j] = 999; } u[1] = 0; maxIter = m * n; CalculatingByH(1); //. for (j = 1; j  n; j++) { if (v[j] == 999) { System.out.println(v[j]); System.out.println("problem with v[j]"); // ошибка тут return false; } } for (i = 1; i  m; i++) { if (u[i] == 999) { System.out.println(u[i]); System.out.println("problem with u[i]"); // ошибка тут return false; } } return true; } public void CalculatingByV(int j) { if (v[j] == 999) { System.out.println("Error another v[j]"); } for (int i = 1; i  m; i++) { if (basicYacheiki[i][j] == 0) { continue; } if (u[i] != 999) { continue; } else { u[i] = price[i][j] - v[j]; System.out.println(u[i]); // тут считает правильно, но неправильно возвращает в methodPotential CalculatingByH(i); } } } public void CalculatingByH(int i) { maxIter = maxIter - 1; if (maxIter == 0) { System.out.println("Зацикливание"); } if (u[i] == 999) { System.out.println("maxIter equals 999"); } for (int j = 1; j  n; j++) { if (basicYacheiki[i][j] == 0) { continue; } if (v[i] != 999) { continue; } else { v[j] = price[i][j] - u[i]; System.out.println(v[i]); CalculatingByV(j); } } }

Задача линейного программирования, транспортная задача
Всем привет. сижу на экзамене, помогите пожалуйста решить,сроно. заранее спасибо.

Транспортная задача
Всем здрасьте! Пишу программу для решения транспортной задачи методом северо-западного угла, через.

Транспортная задача
Не могу решить транспортную задачу В маткаде выбивает ошыбку

Транспортная задача
Здравствуйте! Возникла проблема при решении задачи, а именно в том, что известны не все.

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Aprokun/MyCourseProject

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Курсовой проект на тему «Реализация методов решения открытой и закрытой транспортной задачи»

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

• Java: основной язык реализации
• Maven: сборка проекта, подключение зависимостей
• Lombok: для упрощения кода моделей

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

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

Для реализации нахождения опорного плана применяется метод потенциалов и дальнейшее перераспределение перевозок путём циклов.

Источник