Розв’язання транспортної задачі методом потенціалів

Для визначення оптимального плану транспортної задачі розроблено декілька методів. Але найбільш часто використовуються метод потенціалів і метод диференціальних рент.

Загальний принцип визначення оптимального плану транспортної задачі методом потенціалів аналогічний принципу розв’язання задачі лінійного програмування симплексним методом, тобто: на початку знаходять опорний план транспортної задачі, а потім його послідовно покращують до отримання оптимального плану. Планом транспортної задачі буде матриця

Розв’язання транспортної задачі методом потенціалів - student2.ru ,

в якій спостерігається баланс по рядках і стовпцях. Це відповідає вимогам обмежень задачі. Опорний план транспортної задачі буде містити (т+п–1) базисну компоненту. Система обмежень складається з (т+п) обмежень – рівнянь, однак незалежних рівнянь (m+n–1) (вимога Розв’язання транспортної задачі методом потенціалів - student2.ru робить систему залежною).

Якщо число базисних компонент менше, ніж (т+п–1), то опорний план вироджений, тоді деякі нульові компоненти необхідно вважати базисними. Їх кількість така, що базисних усього буде (т+п–1).

Опорний план може бути визначений різними способами. Наприклад, метод північно-західного кута, метод найменших елементів, метод Фогеля. Алгоритмічно визначити опорний план – це значить знайти місця розташування додатних компонент і їх величини таким чином, щоб був баланс по рядках і стовпцях (умова плану) і їх кількість була (т+п–1) (умова опірності плану).

Метод потенціалів заснований на ідеї знаходження потенціалів (величин Розв’язання транспортної задачі методом потенціалів - student2.ru і Розв’язання транспортної задачі методом потенціалів - student2.ru ) і виборі компоненти, що вводиться в базис, якщо опорний план неоптимальний. Для цього кожному постачальнику і кожному споживачеві ставлять у відповідність певні числа Розв’язання транспортної задачі методом потенціалів - student2.ru , і Розв’язання транспортної задачі методом потенціалів - student2.ru , які називають відповідно потенціалами постачальників і споживачів.

Метод потенціалів базується на теоремах теорії потенціалів [24].

Теорема 1. Якщо план Розв’язання транспортної задачі методом потенціалів - student2.ru транспортної задачі (ТЗ) є оптимальним, то йому відповідає система з m+n чисел αi і βj, яка задовольняє умови:

–αi + βj = cij для xij > 0 Розв’язання транспортної задачі методом потенціалів - student2.ru ,

–αi + βj Розв’язання транспортної задачі методом потенціалів - student2.ru cij для xij = 0 Розв’язання транспортної задачі методом потенціалів - student2.ru .

Теорема 2. Якщо при підстановці компонент оптимального плану в систему обмежень вихідної задачі i-те обмеження перетворюється в нерівність, то i-та компонента оптимального плану ТЗ дорівнює нулеві.

З теореми 1 випливає, що для оптимальності опорного плану необхідне виконання таких умов:

а) для кожної заповненої клітинки (i, j), (xij > 0): –αi + βj = cij;

б) для кожної незаповненої клітинки (xij = 0): –αi + βj Розв’язання транспортної задачі методом потенціалів - student2.ru cij, тобто

–αi + βj –cij Розв’язання транспортної задачі методом потенціалів - student2.ru 0.

Алгоритм методу потенціалів є покроковим процесом, що складається з перевірки на оптимальність опорного плану, виродженість і перехід на повний опорний план. Процес керується ознакою оптимальності. Опишемо цей процес.

Крок 1. Звести дані в таблицю і визначити опорний план. Якщо план вироджений, то ввести нульові базисні елементи.

Крок 2. Скласти систему рівнянь для xij ≠ 0 і обчислити всі потенціали відповідно пунктів відправки і пунктів призначення αi і βj. Ці числа знаходять з системи рівнянь

–αi + βj = cij, (4.2.6)

де cij – тарифи, що стоять в заповнених клітинках таблиці умов транспортної задачі.

Оскільки кількість заповнених клітинок п+т–1, то система (4.2.6) з п+т невідомими містить п+т–1рівнянь. Оскільки кількість невідомих перевищує на одиницю кількість рівнянь, то одне з невідомих можна покласти рівним довільному числу, наприклад, αi = 0, і знайти послідовно з рівнянь (4.2.6) значення інших невідомих. Після того, як всі потенціали визначені, для кожної вільної клітинки визначають числа

αij = –αi + βj – cij.

Якщо серед чисел αij немає додатних, то знайдений опорний план є оптимальним. В противному випадку необхідно перейти до нового опорного плану. Для цього розглядають всі вільні клітинки, для яких αij > 0, і серед даних чисел вибирають максимальне. Клітинку, якій це число відповідає, необхідно заповнити.

Заповнюючи вибрану клітинку, необхідно змінити об’єми поставок, записаних в ряді інших зайнятих клітинок.

Процедура переходу від одного опорного плану до іншого виконується таким чином. Нехай вибраний деякий небазисний елемент xij, який вводиться в базис. Відмітимо його знаком “+”. Далі будується замкнений ланцюжок вершинами якого будуть базисні елементи опорного плану. Вершини ланцюжка позначаються знаком “+” і “–” по черзі, дотримуючи правила: кожний рядок і стовпець повинні мати стільки елементів, відмічених знаком “–”, скільки “+”. Серед елементів, відмічених знаком “–” вибирається мінімальний елемент. Позначимо його через θ. θ додається до елементів відмічених знаком “+” і віднімається від елементів, відмічених знаком “–”.

Крок 3. Після цієї процедури отриманий новий опорний план перевіряємо на оптимальність, тобто знову повторюємо всі дії кроку 2.

Зауважимо, що в процесі розв’язання задачі може бути отриманий вироджений опорний план. Щоб уникнути в цьому випадку зациклювання, необхідно відповідні нульові елементи опорного плану замінити малим додатним числом Е і розв’язувати задачу як невироджену. В оптимальному плані такої задачі необхідно вважати Е рівним нулю.

Приклад.Визначимо оптимальний план транспортної задачі методом потенціалів. Вхідні дані задачі запишемо у вигляді таблиці 4.6.

Таблиця 4.6

Пункти відправлення Пункти призначення Запас
В1 В2 В3 В4
А1
       
А2
       
А3
       
Потреби

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

Таблиця 4.7

Пункти відправлення Пункти призначення Запас
В1 В2 В3 В4
А1
     
А2
   
А3
 
Потреби

Складемо систему рівнянь:

Розв’язання транспортної задачі методом потенціалів - student2.ru

Нехай α1 = 0. Тоді β3 = 1, α3 = 0, β4 = 6, α2 = –2, β1 = 2, β2 = 2.

Тепер для кожної вільної клітинки визначимо числа αij = αi + βj – cij:

α11 = –α1 + β1 – c11 = 0 + 2 – 7 = –5;

α12 = –α1 + β2 – c12 = 0 + 2 – 8 = –6;

α22 = –α2 + β1 – c22 = 2 + 2 – 5 = –1;

α23= –α2 + β3 – c23 = 2 + 1 – 9 = 6;

α31= –α3 + β1 – c31 = 0 + 2 – 9 = –7;

α14= –α1 + β4 – c14 = 0 + 6 – 2 = 4.

Заключаємо знайдені числа в рамки і записуємо їх відповідно в кожну вільну клітинку таблиці 4.8.

Таблиця 4.8

Пункти відправлення Пункти призначення Запас
В1 В2 В3 В4
А1
Розв’язання транспортної задачі методом потенціалів - student2.ru Розв’язання транспортної задачі методом потенціалів - student2.ru Розв’язання транспортної задачі методом потенціалів - student2.ru
А2
Розв’язання транспортної задачі методом потенціалів - student2.ru Розв’язання транспортної задачі методом потенціалів - student2.ru
А3
Розв’язання транспортної задачі методом потенціалів - student2.ru
Потреби

План не оптимальний, оскільки α14 = 4 > 0. Потрібно компоненту Розв’язання транспортної задачі методом потенціалів - student2.ru ввести в базис. Побудуємо ланцюжок.

    –160 +
   
  +30 –90

Найменше з чисел в мінусових клітинках дорівнює 90. Отже, клітинка в якій знаходиться це число, стає вільною в новій таблиці 4.9. Інші числа в табл. 4.9 отримуються так: до чисел, що стоять в плюсових клітинках ланцюжка додамо числа, що знаходиться в мінусових клітинках з урахуванням потреб та запасів. Клітинка на перетині стрічки А3 і стовпця В4 стає вільною.

Після цих перетворень отримуємо новий опорний план (табл. 4.9).

Таблиця 4.9

Пункти відправлення Пункти призначення Запас
В1 В2 В3 В4
А1
Розв’язання транспортної задачі методом потенціалів - student2.ru Розв’язання транспортної задачі методом потенціалів - student2.ru
А2
Розв’язання транспортної задачі методом потенціалів - student2.ru Розв’язання транспортної задачі методом потенціалів - student2.ru
А3
Розв’язання транспортної задачі методом потенціалів - student2.ru Розв’язання транспортної задачі методом потенціалів - student2.ru
Потреби

Перевіримо цей план на оптимальність. Знову знаходимо потенціали пунктів відправки і призначення. Для цього складемо таку систему рівнянь:

Розв’язання транспортної задачі методом потенціалів - student2.ru

Покладемо α1 = 0. Отримаємо: β3 = 1, β4 = 2, α3 = 0, α2 = –6, β1 = –2, β2 = 2.

Для кожної вільної клітинки обчислимо числа:

α11 = β1 – α1 – 7 = – 2 – 0 – 7 = –9;

α12 = β2 – α1 – 8 = 2 – 0 – 8 = –6;

α22 = β2 – α2 – 5 = 2 + 6 – 5 = 3;

α23 = β3 – α2 – 9 = 1 + 6 – 9 = –2;

α31 = β1 – α3 – 9 = – 2 – 0 – 9 = –11;

α34 = β4 – α3 – 6 = 2 – 0 – 6 = –4.

В даному випадку α22 = 3 > 0, отже опорний план не є оптимальним. Побудуємо ланцюжок.

    –70 +90
+   –20
  –50 +120  

Найменше з чисел у мінусових клітинках дорівнює 20 і його запишемо у клітинку А2В2. Отже клітинка, в якій знаходилось це число, стає вільною у новій таблиці 4.10. Інші числа у таблиці 4.11 отримуються так: до числа 90 додаємо 20 і одночасно від числа 70 віднімаємо 20 і додаємо його до числа 120 та віднімаємо число 20 від 50. Після цих перетворень отримуємо новий опорний план (табл. 4.10). Перевіримо цей план на оптимальність. Знову знаходимо потенціали пунктів відправки і призначення. Для цього складемо таку систему рівнянь:

Розв’язання транспортної задачі методом потенціалів - student2.ru

Покладемо α1=0. Отримаємо: β3 = 1, β4 = 2, α3 = 1 – 1 = 0, β2 = 2 – 0 = 2,

α2 = –3, β1 = 7.

Для кожної вільної клітинки обчислимо числа:

α11 1 – α1 – c11 = 7 – 0 – 7 = –6;

α12 = β2 – α1 – c12 = 2 – 0 – 8 = –6;

α23 = β3 – α2 – c23 = 1 + 3 – 9 = –5;

α24 = β4 – α2 – c24 = 2 + 3 – 8 = –3;

α31 = β1 – α3 – c31 = 7 – 0 – 9 = –2;

α34 = β4 – α3 – c34 = 2 – 0 – 6 = –4.

В даному випадку всі αij < 0 і опорний план є оптимальний.

Таблиця 4.10

Пункти відправлення Пункти призначення Запас
В1 В2 В3 В4
А1
Розв’язання транспортної задачі методом потенціалів - student2.ru Розв’язання транспортної задачі методом потенціалів - student2.ru
А2
Розв’язання транспортної задачі методом потенціалів - student2.ru Розв’язання транспортної задачі методом потенціалів - student2.ru
А3
Розв’язання транспортної задачі методом потенціалів - student2.ru Розв’язання транспортної задачі методом потенціалів - student2.ru
Потреби

Сумарні транспортні витрати:

f = 1·50 + 2·110 + 4·120 + 5·20 + 2·30 + 1·140 = 1050.

Отже, отримуємо такий оптимальний план:

Розв’язання транспортної задачі методом потенціалів - student2.ru .

Стержневі системи

Загальні положення

Розглянемо конструкцію з плоскої шарнірно-стержневої ферми (рис. 5.1). Будемо вважати, що стержні ферми не мають попередньої напруженості, а зовнішні навантаження у вигляді сил Rк прикладені у вузлах.

Сили завантаження F2 і F3, діючі в навантаженнях па типовий елемент е2, подамо у вигляді проекцій Розв’язання транспортної задачі методом потенціалів - student2.ru , Розв’язання транспортної задачі методом потенціалів - student2.ru , Розв’язання транспортної задачі методом потенціалів - student2.ru і Розв’язання транспортної задачі методом потенціалів - student2.ru , відповідно, (рис. 5.1,а).

Зміщення вузлів елемента від їх початкового положення (без зусиль діючих на ферму) позначимо відповідно через Розв’язання транспортної задачі методом потенціалів - student2.ru , Розв’язання транспортної задачі методом потенціалів - student2.ru , Розв’язання транспортної задачі методом потенціалів - student2.ru , Розв’язання транспортної задачі методом потенціалів - student2.ru .

Розв’язання транспортної задачі методом потенціалів - student2.ru

Рисунок 5.1

Розтяг або стиск стержня незавантаженої довжини L визначається величиною Розв’язання транспортної задачі методом потенціалів - student2.ru і деформація отримається в результаті ділення цієї величини на L. Оскільки напруження дорівнює модулю Юнга Е = [Н/м2, (кГ/см2)] помноженому на деформацію, то повздовжня сила, яка прикладена до стержня (рис. 5.1, а) описується виразом

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.1)

де А – площа поперечного перерізу стержня.

Компоненти повздовжньої сили Р можуть бути прирівняні до компонент шарнірних сил:

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.1.2)

 
  Розв’язання транспортної задачі методом потенціалів - student2.ru

Рисунок 5.1, а

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.3, а)

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.3, б)

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.3, в)

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.3, г)

Одержані рівняння (5.1.3) запишемо у такому вигляді:

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.4)

Рівняння (5.1.4) є матричне рівняння для елемента е2(узагальнений закон Гука) і його квадратна матриця коефіцієнтів з множником EA/L називається матрицею жорсткості К2даного елемента [15]. Аналогічні рівняння можуть бути отримані і для інших елементів.

Рівняння (5.1.4) може бути розширене так, щоб воно включало всі вузлові зміщення системи. Для цього необхідно розширити (проасемблювати) матрицю жорсткості з використанням необхідної кількості нулів. Порядок розширеної матриці К2 дорівнює подвійному добутку кількості вузлів конструкції. Так для стержневої системи (рис. 5.1) розмірність розширеної матриці dim K=8х8.

В результаті маємо:

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.4, а)

Зовнішні сили R1, R2, R3, R4 виражаються через х, у – компоненти Розв’язання транспортної задачі методом потенціалів - student2.ru , Розв’язання транспортної задачі методом потенціалів - student2.ru ,…, Розв’язання транспортної задачі методом потенціалів - student2.ru , Розв’язання транспортної задачі методом потенціалів - student2.ru , а умова рівноваги в вузлових точках може бути визначена через ці компоненти. Наприклад, у вузлі 2 умова рівноваги в напрямку х має вигляд

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.1.5)

Ясно, що вклад в праву частину (5.1.5) дають тільки ті елементи, які включають вузол 2, але зручно записати (5.1.5) в такому вигляді:

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.1.5, а)

Аналогічне співвідношення отримується для другої компоненти вектора R2:

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.1.5, б)

Рівняння (5.1.5, а) і (5.1.5, б) можна об'єднати в матричний запис:

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.6)

Аналогічні рівняння можна записати і для інших вузлів. Підсумкова система рівнянь рівноваги запишеться так:

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.7)

Підстановка виразів типу (5.1.4) в рівняння (5.1.7) дає

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.1.8)

де К – матриця жорсткості системи, δ – вектор вузлових зміщень системи.

Формула (5.1.8) дає можливість обчислити зміщення і реакції вузлів.

Стержневі системи

Деяка сукупність стержнів, які мають певні вузли, становить стержневу систему [6]. В інженерній практиці конструкторів завжди цікавить важливе питання, чи буде стержнева система в рівновазі. На це питання дає відповідь математична модель стержневої системи, яка будується на основі системного аналізу. Всі теоретичні положення будемо розглядати на основі стержневої системи, яка зображена на рисунку 5.2.

Система складається з чотирьох стержнів: L1, L2, L3, L4, які мають відповідно площі поперечного перерізу А1, А2, А3, А4. Стержні мають вузли, які ми занумерували вузлами 1, 2, 3 та 4. Всі стержні виготовлені з одного матеріалу, модуль Юнга якого – Е.

Стержень L1 утворює з віссю ОХ кут φ1=150о, стержень L2 паралельний осі ОХ, стержень L3 утворює з віссю ОХ кут φ3=126,874о, стержень L4 утворює з віссю ОХ кут φ4=53,127о.

Розв’язання транспортної задачі методом потенціалів - student2.ru

Рисунок 5.2

Алгоритм формування математичної моделі даної системи такий:

1. Обчислюємо матриці жорсткості для кожного стержня за формулою (5.1.5):

а) стержень L1 утворює з віссю ОХ кут φ1=150о.

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.1, а)

б) стержень L2 утворює з віссю ОХ кут φ2=0о.

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.1, б)

в) стержень L3 утворює з віссю ОХ кут φ3=126,874о.

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.1, в)

г) стержень L4 утворює з віссю ОХ кут φ4=53,127о.

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.1, г)

2. Задаємо конкретні величини: Е=2×1012 кГ/см2; А1234= =0,5 дм2; L1=8 м; L2=6 м; L3=L4=5 м (округлено для спрощення подальших розрахунків). І підставляємо їх у формули 5.2.1, а; 5.2.1, б; 5.2.1, в; 5.2.1, г.

3. Формуємо дві загальні матриці реакції та зміщення вузлів. Маємо 4 вузли. Отже, маємо 8 реакцій та 8 зміщень:

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.2.2)

Найважливішою механічною властивістю стержневої системи є те, що поведінка системи описується узагальненим законом Гука:

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.3)

У формулі (5.2.3) dim R = 8×1. Тоді виникає така розмірність

dim K = 8×8. (5.2.4)

Тепер основна проблема полягає в тому, щоб отримати матрицю К знаючи 4 матриці К1, К2, К3 та К4. Цю проблему розв’язує процес асемблювання матриць.

Запишемо формулу (5.2.3) в розгорнутому вигляді:

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.2.5)

Формула (5.2.5) повинна збігатись з формулою (5.1.6) для стержня L1. А це означає, перші чотири рядки матриці К1 повинні залишатись без зміни, а решта елементів нулі. Аналогічно будемо міркувати для стержнів L2, L3 та L4.

4. Асемблювання матриць.

Для збереження закону Гука ми повинні зберегти матрицю К1, а решту елементів прирівняти до нуля.

Пунктиром окреслена матриця К1. Матриця К1 не містить вузла 3 та вузла 4.

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.6, а)

Матриця К2 не містить вузла 1 та вузла 4.

Отже будемо мати:

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.6, б)

Матриця К3 не містить вузла 1 та 2. Отже отримаємо:

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.6, в)

Наголосимо, що стержень L4 містить вузол 2 та 4, а не містить вузол 1 та 3. Вузлу 1 відповідають перший та другий рядки, які будуть нулями та п’ятий і шостий рядки – теж нулі. Маємо:

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.6, г)

5. Формування загальної матриці жорсткості стержневої системи відбувається за формулою (5.2.7):

R=åKi, i= Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.7)

У формулі (5.2.7) Кі – асембльовані матриці. Для нашого прикладу маємо:

К = К1234. (5.2.7, а)

Наголосимо, що при виконанні додавання перед дужкою у матрицях повинні бути однакові множники. Маємо:

Розв’язання транспортної задачі методом потенціалів - student2.ru . (5.2.7, б)

6. Граничні умови. На рисунку 5.2 маємо:

а) вузли 1 та 4 закріплені наглухо. Отже, Розв’язання транспортної задачі методом потенціалів - student2.ru ;

б) на вузол 2 діє сила Р2 = 1000 кг під кутом a = 60о, а на вузол 3 діє сила Р3 = 2000 кг під кутом b = 30о.

Знаки проекцій вибираємо згідно з рисунком 5.3 та 5.4. Маємо:

Розв’язання транспортної задачі методом потенціалів - student2.ru (кГ);

Розв’язання транспортної задачі методом потенціалів - student2.ru (кГ);

Розв’язання транспортної задачі методом потенціалів - student2.ru (кГ);

Розв’язання транспортної задачі методом потенціалів - student2.ru (кГ).

Розв’язання транспортної задачі методом потенціалів - student2.ru

Рисунок 5.3 Рисунок 5.4

За формулою (5.2.5) формулюємо матричну модель стержневої системи, зображеної на рис.5.2.

 
  Розв’язання транспортної задачі методом потенціалів - student2.ru

Розв’язання транспортної задачі методом потенціалів - student2.ru

(5.2.8)

Формула (5.2.8) становить математичну модель стержневої системи, зображеної на рис. 5.2.

1. Нам відомі реакції вузла 2 та 3. Отже, нам потрібно розв’язувати систему рівнянь:

Розв’язання транспортної задачі методом потенціалів - student2.ru (5.2.9)

2. Розглядаючи (5.2.9) як систему вигляду АХ=В та розв’язуючи її за методом Гауса маємо:

Розв’язання транспортної задачі методом потенціалів - student2.ru (см);

Розв’язання транспортної задачі методом потенціалів - student2.ru (см);

Розв’язання транспортної задачі методом потенціалів - student2.ru (см);

Розв’язання транспортної задачі методом потенціалів - student2.ru (см).

3. Враховуючи (5.2.10) обчислимо реакції нерухомих вузлів згідно з формулою (5.2.8):

а) Розв’язання транспортної задачі методом потенціалів - student2.ru знаходимо в першому порядку

Розв’язання транспортної задачі методом потенціалів - student2.ru (кГ);

б) Розв’язання транспортної задачі методом потенціалів - student2.ru знаходимо в другому порядку

Розв’язання транспортної задачі методом потенціалів - student2.ru (кГ);

в) Розв’язання транспортної задачі методом потенціалів - student2.ru знаходимо в сьомому порядку

Розв’язання транспортної задачі методом потенціалів - student2.ru (кГ);

г) Розв’язання транспортної задачі методом потенціалів - student2.ru знаходимо в восьмому порядку

Розв’язання транспортної задачі методом потенціалів - student2.ru (кГ).

4. Контроль.

Якщо знайдені розв’язки математичної моделі (5.2.8) правильно, то стержнева система повинна знаходитись у рівновазі.

Отже, повинно виконуватись дві рівності:

1. Розв’язання транспортної задачі методом потенціалів - student2.ru ;

2. Розв’язання транспортної задачі методом потенціалів - student2.ru .

Перевірка:

а) Розв’язання транспортної задачі методом потенціалів - student2.ru ;

б) Розв’язання транспортної задачі методом потенціалів - student2.ru .

Отже, для математичної моделі (5.2.8) розв’язки знайдено правильно.

Електричні системи

Основні положення

Розв’язання транспортної задачі методом потенціалів - student2.ru

Рисунок 6.1

Електрична система складається з батареї з електрорушійною силою Е, ребер провідників (провідників з опором Rk), по яких тече електричний струм Іk, та вузлів.

Приклад такої системи показано на рисунку 6.1 [14]. Нумеруємо вузли. На ребрах довільним чином задаємо напрям електричних струмів Іk.

Для формування математичної моделі застосуємо два закони Кірхгофа, які виразимо мовою матричної алгебри. Відзначимо, що вони базуються на теорії графів, тобто залежать лише від способу з'єднання вершин ребрами і від напрямку стрілок, але не залежать від величин опору (або потужностей батарей) в контурі. Зв'язки між вершинами повністю описуються матрицею інцидентності графу цього контура, яка має рядок для кожної вершини або замкнутого контура і стовпець для кожного ребра. В кожному стовпці цієї матриці два ненульових елемента +1 і –1 відмічають початкову і кінцеву вершину ребра.

Графом називають сукупність вершин (вузлів) і зв'язуючих їх ребер (ланок). Визначення графу може бути записане в такому вигляді:

Г = (У, Р, І),

де У – множина вершин; Р – множина ребер; І – інцидентор (показник способу з'єднання ребер одне з одним).

Якщо для ребер графу вказані конкретні напрямки, то граф називають направленим графом (орієнтованим або орграфом), ребра направленого графу називають дугами.

Маршрутом називають послідовність S ребер, в якій сусідні ребра інцидентні одній і тій же вершині. Термін "інцидентність" означає співвідношення об'єктів типу "проходить через..." або "знаходиться на...". На рис. 6.2 в графі послідовності (b, c, e, f, c, d) і (e, g) – маршрути, але (a, h) не маршрут, тому що ребра а і h інцидентні різним вершинам. Якщо в маршруті немає ребер, які повторюються, то маршрут називають ланцюгом. Якщо ланцюг починається і закінчується в одній і тій же самій вершині, то маємо цикл – контур. Кількість ребер в ланцюгу називають довжиною маршруту.

   
  Розв’язання транспортної задачі методом потенціалів - student2.ru

Рисунок 6.2

Зв'язним графом називають граф, у якому можна вказати маршрут, що зв'язує будь-які вершини.

Деревом зв'язного графу називають зв'язний підграф без циклів.

За допомогою матриці інцидентності А=[aі,j] може бути виражена інформація, яка міститься у графі. В цій матриці β–1 рядків і α стовпців. Кожному вузлу за винятком одного, який приймається за базовий, в матриці відповідає один рядок; а кожному ребру один стовпець. В стовпці записуються одиниці на перетині з рядками тих вузлів, якому інцидентне ребро даного стовпця. Якщо граф направлений, то знаки одиниць вказують напрям дуг: +1 відповідає рядок вузла, до якого направлене ребро, –1 рядок другого вузла. В клітинках матриці, які залишилися, записуються нулі. Наприклад, матриця інцидентності для графу рис. 6.3 у випадку, коли базовим вузлом є вузол 4, подана у таблиці 6.1.

 
  Розв’язання транспортної задачі методом потенціалів - student2.ru

Рисунок 6.3

Таблиця 6.1

Наши рекомендации