Побудова опорного плану транспортної задачі методом подвійної переваги

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

  1. На першому кроці, у кожному стовпці транспортної таблиці відзначають знаком "V" комірку з найменшою вартістю.
  2. Потім те ж проробляють в кожному рядку. В результаті виконання другого кроку, деякі комірки транспортнї таблиці будуть містити відмітку "VV".
  3. На останньму кроці, у комірки з подвійними відмітками (подвійна перевага) поміщають максимально можливі обсяги перевезень, щоразу виключаючи з розгляду відповідні стовпці або рядки. Потім розподіляють перевезення по комірках з одиничною відміткою. Решта перевезення розподіляють згідно  алгоритму методу мінімального елемента.

Читати повністю

Рішення транспортної задачі методом Фогеля в середовищі програмування delphi

Delphi-проект реалізує процес знаходження опорного плану транспортної задачі використовуючи при цьому алгоритм методу Фогеля. Основна ідея даного методу полягає в знаходженні різниці (по модулю) між парою мінімальних тарифів в кожному рядку і стовпці. Потім рядок або стовпець з найбільшою різницею заповнюється в напрямку від клітини з мінімальним тарифом до клітки з максимальним. Більш детальну інформацію про метод Фогеля можна знайти за посиланням Побудова опорного плану транспортної задачі методом Фогеля.

Головне вікно розглядуваного delphi-проекту ділиться на три частини: панелі інструментів (складається з двох компонентів типу TSpinEdit та двох кнопок типу TButton), робочої області (містить транспортну таблицю) та статусного рядка, основним призначенням якого є вивід загальної вартості перевезень згідно побудованого опорного плану. Розглянемо призначення кожного з цих елементів більш детально:

  1. Поля вибору "Пункти призначення" та "Пункти відправлення" відповідають за кількість пунктів які беруть участь в перевезенні, а також розмірність транспортної таблиці.
  2. Кнопки "Знайти опорний план методом Фогеля" та "Очистити" відповідають за побудову початкового плану транспортної задачі та підготовку програми до нового прикладу відповідно.
  3. Нарисована на канві форми транспортна таблиця у комірки якої, способом введення з клавіатури, записуються тарифи на перевезення одиниці продукції, загальні потреби у товарі кожного з пунктів призначення і загальна кількість запасів кожного з пунктів відправлення.

Читати повністю

Побудова опорного плану транспортної задачі методом Фогеля

Серед розглядуваних на даному сайті методів побудови опорного плану в транспортній задачі, найчастіше застосовуються на практиці метод Фогеля. Послідовність дій при його використанні зовсім інша, ніж при заповненні транспортної таблиці методом північно-західного кута чи методом мінімального елемента. На перший погляд метод Фогеля видається набагато складнішим, проте це лише помилкове враження. Метод простий і дозволяє отримати опорний план більш наближений до оптимального рішення, ніж у випадку застосування інших методів (за винятком хіба що методу подвійної переваги). Отже, розглянемо алгоритм даного методу більш детально:

  1. На довільному кроці методу, для кожного рядка та стовпця обчислюється різниця ("штраф") між значеннями найменшої вартості та вартості, наступної за величиною. Якщо ж виявиться, що в рядку чи стовпці містятся дві комірки з однаковими мінімальними значеннями тарифів, то беремо саме їх. В такому випадку різниця буде дорівнює нулю.
  2. Обчислені штрафи записуються у додаткові рядки та стовпі транспортоної таблиці.
  3. Виокремлюємо рядок чи стовпець з найбільшим "штрафом" (якщо їх є декілька, то обираємо довільний з них).
  4. У виокремленому на попередньому кроці рядку чи стовпці, обираємо комірку з найменшою вартістю.
  5. Для обраної комірки встановлюємо величину перевезунь, аналогічно методу мінімального елемента, після чого, повторюємо всі вищеописані дії знову, тільки вже не враховуючи заповнені клітини.

Читати повністю

Програмна реалізація алгоритму LU-розкладання для знаходження власних значень несиметричної матриці

Delphi-проект призначений для розв'язку задачі на знаходження всіх власних значень несиметричної матриці і використовує для цього алгоритм методу LU-розкладання (грунтуються на приведенні заданої матриці до подібної їй матриці трикутного вигляду, більш детальна інформація про який міститься за посиланням Знаходження власних значень матриці використовуючи алгоритм LU-розкладання). Інтерфейс головної форми проекту аналогічний проектам, в яких було реалізовували інші чисельні методи розв'язку задач на власні значення (метод вичерпування на delphi, метод Крилова на delphi, степеневий метод на delphi та інші), лише з однією відмінністю — передбачено можливість задати точность обчислювального процесу.

Ліва частина форми містить область вхідних даних, яка складається з однієї кнопки типу TButton (кнопка "Знайти власні значення матриці" — реалізує алгоритм LU-розкладання для знаходження власних значень вхідної матриці), одного поля вибору типу TSpinEdit (поле вибору "Виберіть розмірність матриці" відповідає за число рядків та стовпців вхідної матриці), одного поля вводу типу TEdit (поле "Точність обчислень" відповідає за точність з якою необхідно знайти власні значення вхідної матриці) та таблиці TStringGrid у комірки якої, способом введення з клавіатури, записуються значення елементів вхідної матриці. Праву частину форми займає компонент типу TMemo, основним призначенням якого є вивід результату роботи програми.

Читати повністю

Знаходження власних значень матриці використовуючи алгоритм LU-розкладання

Частіше, принаймні, в несиметричному випадку, алгоритми наближеного рішення повних проблем власних значень грунтуються на приведенні заданої матриці до подібної їй матриці не діагонального, а трикутного вигляду. Найпоширенішим серед таких є алгоритм, що спирається на LU-розкладанні матриці. Розглянемо його більш детально. Для цього розглянемо квадратну матрицю  розмірності , записану у вигляді добутку , де  і  — відповідно нижня і верхня трикутні матриці, елементи яких обчислюються за наступними формулами :

Зауваження: більш детальну інформацію про обчислення елементів матриць  і  можна знайти за посиланням Розв'язок СЛАР методом LU-факторизації.

Далі, позначимо , після чого, роз'вяжемо дану рівність відносно . В результаті отримаємо . Підставами останній вираз у формулу LU-розкладання матриці , отримаємо перетворення подібності , яке говорить про подібність матриць  та  і відповідно про рівність їх власних значень. Далі, представимо матрицю  у вигляді , після чого, поклавши , отримаємо нову матрицю, подібну до матриць  і  відповідно. Продовжуючи даний процес далі, можна зробити висновок, що алгоритм знаходження власних значень згідно алгоритму LU-розкладання визначається фактично двома формулами:

Читати повністю

Обчислення подвійних інтегралів на криволінійній області інтегрування в середовищі програмування delphi

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

Головне вікно проекту ділиться на дві частини і складається з панелі інструментів (розташована в лівій частині форми і містить наступні візуальні компоненти: п'ять компонентів типу TEdit, чотири з яких відповідають за розмірність області інтегрування і в один аналітично, у вигляді формули, вказується підінтегральна функція; один компонент типу TSpinEdit призначений виключно для введення цілих чисел і відповідає за кількість частин на які розбивається область інтегрування; компонент типу TMemo, основне призначення якого є вивід результату роботи програми; дві кнопки типу TButton, одна з яких безпосередньо реалізує алгоритм методу клітин і друга — видаляє всі введені користувачем значення та готує проект до нового прикладу) та області 3D-візуалізації  методу клітин для випадку криволінійної області інтегрування.

Читати повністю

Інтерполяція періодичних функцій в середовищі програмування delphi

Програма виконує інтерполяцію періодичних таблично-заданих функцій і використовує для цього тригонометричний інтерполяційний поліном. Інтерфейс програми простий та зрозумілий у використанні (аналогічний іншим проектам, які реалізують процедуру наближення табличних функцій). Ліва частина форми містить область вхідних даних, яка складається з таблиці StringGrid у комірки якої, способом введення з клавіатури, записуються відомі знячення аргументу та функції. Праву частину форми займає компонент типу TChart, який відображає графік досліджуваної функції. І, нарешті, в нижній частині форми розташована панель інструментів, яка складається з трьох кнопок типу TButton, одного поля вибору типу TSpinEdit та одного поля вводу типу TEdit. Розглянемо призначення кожного з цих компонентів більш детально:

  1. Поле вибору "Розмірність таблиці" відповідає за число заданих вузлів інтерполяції досліджуваної функції і порядок інтерполяційного многочлена.
  2. Кнопка "Інтерполювати" призначена для побудови в компоненті TChart графіка табличної функції та вузлів інтерполяції.
  3. Кнопка "Очистити" видаляє з комірок таблиці StringGrid дані та видаляє всі точки побудованого графіка.
  4. Кнопка "Обчислити значення функції в точці" — обчислює значення функції в точці, значення якої задається в полі вводу TEdit (міститься в парвій частині панелі задач), а також відображає її на графіку (точка червоного кольору).

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

Читати повністю

Наступна сторінка »