Решить уравнение i методом потенциалов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Вычисление потенциалов для плана перевозки

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

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

Итак, сопоставим каждому поставщику A_i и каждому потребителю B_j соответствующие величины U_i и V_j так, чтобы для всех базисных клеток плана было выполнено следующее соотношение: U_i + V_j = C_ij.

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

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

Тогда мы сможем найти V₃ = C₁₃ — U₁ = 1 — 0 = 1.

Зная V₃, мы теперь можем найти U₃:

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

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

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

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

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

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

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

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

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

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

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

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)

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

Метод узловых (потенциалов) напряжений

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

Существует несколько наиболее применяемых методов расчетов для таких цепей: с помощью законов Кирхгофа, методом контурных токов, узловых потенциалов, методом эквивалентного генератора, эквивалентного источника тока, методом наложения. Для расчета более сложных цепей, например, в нелинейных схемах, могут применяться метод аппроксимации, графические методы и другие.
В данном разделе рассмотрим один из методов определения токов в цепи постоянного тока – метод узловых потенциалов.

Метод узловых потенциалов примеры решения задач

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

Рис.1. Схема постоянного тока

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

Каждый из этих узлов будет обладать своим значением потенциала относительно узла 4. Именно значения этих потенциалов для дальнейшего определения токов и находят. Соответственно, для удобства этим потенциалам присваивают номера в соответствии с номером узла, т.е. φ₁, φ₂, φ₃. Далее составляется система уравнений для оставшихся узлов 1, 2, 3.

В общем виде система имеет вид:

Использованные в этой системе уравнений буквенно-цифровые обозначения

имеют следующий смысл:

– сумма проводимостей ветвей, сходящихся в узле 1. В данном случае

– сумма проводимостей ветвей, сходящихся в узле 2. В данном случае

– сумма проводимостей ветвей, сходящихся в узле 3. В данном случае

– сумма проводимостей ветвей, соединяющих узлы 1 и 2, взятая со знаком «минус». Для этого единица и взята с отрицательным знаком:

– сумма проводимостей ветвей, соединяющих узлы 1 и 3, взятая со знаком «минус». Для этого единица и в этом случае взята с отрицательным знаком:

Аналогично находятся и остальные проводимости:

J₁₁ – узловой ток узла 1, в котором участвуют ветви, подходящие именно к этому узлу, и содержащие в своем составе ЭДС. При этом, если ЭДС ветви, входящий в узел, направлена к рассматриваемому узлу (в данном случае к узлу 1), то такой узловой ток записывается с плюсом, если от узла, то с минусом. В данном случае

В результате всех ранее приведенных вычисленных значений исходная система уравнений примет вид:

Решать данную систему можно всеми доступными методами, мы же для упрощения решим ее в пакете Mathcad:

В результате получены следующие значения потенциалов в узлах цепи:

Токи в ветвях находятся в соответствии с законом Ома. Поясним это простыми словами.

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

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

Правильность расчетов можно проверить, например, составлением баланса мощностей либо, к примеру, моделированием, схемы. Выполним моделирование в программе Multisim.

Рис.2. Моделирование в Multisim

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

Расчёт электрических цепей онлайн по методу узловых потенциалов

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

Выбор метода расчёта осуществляется в спадающем списке. Для расчёта по методу узловых потенциалов необходимо выбрать метод расчёта «МУП». Используемая методика при расчёте по методу узловых потенциалов приведена здесь .

ВНИМАНИЕ! На данный момент имеются ограничения на расчёт схем по методу узловых потенциалов. Расчёт не производится для больших схем, где имеется большое количество особых ветвей, не связанных между собой. Если расчёт не получается осуществить по методу узловых потенциалов, рекомендуем воспользоваться расчётом по законам Кирхгофа.

Пример схемы и расчёт:

Исходные данные и схема:

• E1:
  • Номер элемента: 1
  • Амплитудное значение: 100 В
  • Начальная фаза: 0
• R1:
  • Номер элемента: 1
  • Сопротивление, Ом: 1
• L1:
  • Номер элемента: 1
  • Сопротивление, Ом: 1
• C1:
  • Номер элемента: 1
  • Сопротивление, Ом: 1

После нажатия кнопки «Расчёт» на исходной схеме появляется нумерация узлов и формируется решение:

Рассчитаем схему по методу узловых потенциалов.

В данной схеме: узлов − 2, ветвей − 3, из них особых ветвей − 0. Под особыми ветвями понимаются ветви, в которых имеется только источник ЭДС.

Количество уравнений, составляемых по методу узловых потенциалов, равно $ N_\textrm<у>— 1- N_\textrm $, где $ N_\textrm <у>$ − число узлов, $ N_\textrm $ − число особых ветвей. Для данной схемы количество уравнений, составляемых по методу узловых потенциалов, равно 2 − 1 − 0 = 1.

В исходной схеме нет особых ветвей. Примем потенциал узла №1 равным нулю, т.е. $$ \underline<\varphi>_ <1>= 0 \space\textrm <В>$$

Составим уравнения для определения потенциалов остальных узлов.

Уравнение для узла №2:

Перенесём все известные слагаемые в правую часть и объединим полученные уравнения в систему. Получим:

Подставим в полученную систему уравнений численные значения и получим:

Решим систему уравнений и получим искомые потенциалы узлов:

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

Принятые направления токов:
Ток $ \underline_ <1>$ направлен от узла ‘2 у.’ к узлу ‘1 у.’ через элементы $ \underline_ <1>$, $ R_ <1>$.
Ток $ \underline_ <2>$ направлен от узла ‘1 у.’ к узлу ‘2 у.’ через элементы $ L_ <1>$.
Ток $ \underline_ <3>$ направлен от узла ‘1 у.’ к узлу ‘2 у.’ через элементы $ C_ <1>$.

Определим токи во всех ветвях, кроме особых, по закону Ома для участка цепи:

После завершения расчёта на экран также выводятся векторные диаграммы токов и напряжений.

Рекомендуемые записи

Наряду с решением электрических схем по законам Кирхгофа и методом контурных токов используется метод узловых…

В дополнение к выводу метода рассмотрим методику расчёта электрических цепей по методу узловых потенциалов. Последовательность…

На сайте появилась программа для расчёта установившихся режимов электрических цепей по законам ТОЭ. На настоящий…

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

Для отправки комментария вам необходимо авторизоваться.

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.