Використання комп’ютера в процесі навчання розв’язування деяких задач оптимізації

Размещено на http://www.allbest.ru/

Використання комп'ютера в процесі навчання розв'язування деяких задач оптимізації



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

Ключові слова: теорія оптимізації; екстремальна задача; функція цілі; математична модель.

Задачі на знаходження екстремумів відіграють важливу роль в розвитку математики. Проблеми відшукання найкращого серед деякої множини варіантів люди розв'язують майже завжди. Такий найкращий варіант називають оптимальним (від. лат. optimus - найкращий). Пошук реального оптимального розв'язку є, як правило, складною задачею і відноситься до екстремальних задач, в яких необхідно знайти максимум чи мінімум певних функцій від аргументів, що задовольняють наперед задані обмеження. Обидва ці поняття - максимум (maximum) і мінімум (minimum) об'єднуються єдиним терміном «екстремум» (лат. extremum - крайній). Якщо на аргументи функції накладаються певні обмеження - умови, які повинні задовільняти аргументи, тоді екстремум (екстремальне значення функції) називають умовним. Якщо ж на аргументи функції не накладаються ніякі обмеження, тоді екстремум називають безумовним. Задачі на відшукання максимуму чи мінімуму певних функцій називають екстремальними задачами.

Напрям прикладної математики, предметом якого є теорія та методи розв'язування екстремальних задач за заданих додаткових умов, називають математичним програмуванням.

На сучасному етапі математичне програмування включає в себе широке коло задач з відповідними методами розв'язування. Існує класифікація задач математичного програмування:

• Задачі лінійного програмування (задачі на знаходження мінімуму чи максимуму лінійної цільової функції на множині розв'язків системи лінійних нерівностей або лінійних рівнянь);

• Задачі дробово-лінійного програмування (задачі на знаходження мінімуму чи максимуму дробово-лінійної цільової функції (відношення двох лінійних функцій) на множині розв'язків системи лінійних нерівностей або лінійних рівнянь);

• Задачі нелінійного програмування (задачі на знаходження мінімуму чи максимуму цільової функції на множині розв'язків системи нерівностей або рівнянь, в яких цільова функція й (або) множина розв'язків системи нерівностей або рівнянь є нелінійними функціями);

• Задачі опуклого програмування (задачі на знаходження мінімуму вгнутої чи максимуму опуклої цільової функції на замкненій опуклій множині розв'язків системи рівнянь або нерівностей).

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

• Задачі квадратичного програмування (задачі на знаходження мінімуму чи максимуму квадратичної цільової функції на множині розв'язків системи лінійних нерівностей або лінійних рівнянь);

• Задачі динамічного програмування (багатокрокові оптимізаційні задачі, які в процесі розв'язування змінюються так, що на кожному кроці відшукується розв'язок деякої часткової задачі, породженої початковою);

• Задачі стохастичного програмування (оптимізаційні задачі з випадковими аргументами в цільовій функції або в функціях, за якими визначається множина допустимих розв'язків);

• Задачі цілочисельного програмування (задачі на знаходження мінімуму чи максимуму цільової функції на множині розв'язків системи нерівностей або рівнянь, де змінні мають набувати цілих значень);

• Задачі теорії ігор (задачі на знаходження оптимальної стратегії, яка за умови багатократного повторення гри забезпечує певному гравцеві максимально можливий середній виграш) [4, с. 423].

Серед прикладних задач оптимізації важливе місце займають задачі дискретного програмування (дискретної оптимізації).

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

Всі перелічені задачі математичного програмування називають також оптимізаційними. Методи дослідження та розв'язування різних типів екстремальних задач складають основи теорії оптимізації.

Значний внесок у розвиток теорії оптимізації зробили вчені: Л. В. Канторович [8], Т. Ч. Купманс, Дж. Данціг (задачі лінійного програмування), Г. Кун і А. Таккер [12] (задачі нелінійного програмування), Р. Белман [5], Л. С. Понтрягін, В. Г. Болтянский, Р. В. Гамкрелідзе, Є. Ф. Міщенко [10] (задачі динамічного програмування), Ю. М. Єрмольєв [7], Д. Б. Юдін [11] (задачі стохастичного програмування).

Для того, щоб знайти оптимальний розв'язок оптимізаційної задачі, потрібно дотримуватися певних правил, зокрема [2, с. 20-21]:

1. Здійснити постановку задачі. Під час постановки будь-якої задачі її потрібно сформулювати в термінах певної предметної галузі, де задача виникла, в результаті чого повинно бути чітко визначено мету, яку потрібно досягти в результаті розв'язування задачі.

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

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

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

5. Провести обчислення (комп'ютерний експеримент), здійснити аналіз одержаних результатів. Під час побудови математичних моделей для задач математичного програмування потрібно дотримуватися таких вимог: наочність побудови; видимість основних властивостей і відношень; доступність моделі для дослідження або відтворення; простота дослідження, відтворення; збереження даних, що пов'язані з оригіналом, та одержання нових даних на основі досліджень.

Для розв'язування задач оптимізації широко використовують сучасні програмні засоби Excel, MatLab, Maple, MathCad, Mathematika, Sage, Maxima, Графоаналізатор 1.3.

Приклад 1. Потрібно завантажити літак вантажністю 30 т трьома типами речей, причому вага одиниці першого типу речей рівна 7 тонн, другого типу речей - 9 тонн, третього типу - 12 тонн. Вартість перевезення одиниці кожного типу речей рівна 3 тис. гр. од., 4 тис. гр. од., 5 тис. гр. од. відповідно. Очевидно, максимальна кількість речей кожного типу, яку можна помістити в літак відповідно дорівнює 4 одиниці, 3 одиниці, 2 одиниці. Яку кількість кожного типу речей потрібно завантажити, щоб вартість перевезення речей була максимальна [3, с. 160]?

Розв'язування. Нехай x₁,x₂,х₃ - кількість речей кожного типу відповідно.

Тоді цільова функція матиме вигляд:

Z(x, x₂, х)⁼ 3xj + 4х + 5х ^ max

Обмеження на змінні x₁, x₂, х₃ матимуть вигляд:

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

До клітинки B8 запишемо формулу для підрахунку значень цільової функції: =B3*D3+B4*D4+B5*D5 (рис. 1).

Вирази обмежень задачі записуються в клітинки B10:B13, куди вводяться вирази функцій, які відповідають виразам обмежень на змінні.



Рис.1

Рис. 2

Рис.3



Рис.4

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

В полі "До": вибираємо перемикач "Максимум". В полі "Змінюючи значення змінних в клітинках" вказуємо діапазон клітин $В$3:$В$5 - їх вмісти можуть змінюватися в процесі пошуку розв'язку.

Отже, щоб максимально завантажити літак з дотриманням вказаних вимог, потрібно взяти 3 одиниці речей 1-го типу і 1 одиницю речей 2-го типу. Загальна вартість перевезення в такому разі становитиме 13 тис. гр. од.

Приклад 2. Розглянемо задачу на знаходження найкоротшого шляху в дорожній мережі, через яку з'єднуються 8 населених пунктів в деякому географічному районі. Мережа доріг задана у вигляді схеми (зв'язного графа), яка складається з 8 вершин і 15 дуг. Довжина дороги (км) між двома сусідніми населеними пунктами рівна для кожної дуги значенню, яке вказано поряд із цією дугою на графі [1, с. 13].

Потрібно знайти найкоротший шлях від початкового пункту 1, якому відповідає вершина v_x, до кінцевого пункту 8, якому відповідає вершина v₈.

Змінними математичної моделі даної задачі про найкоротший шлях є 15 змінних: ^X12 ' ^X13' ^Х14' ^X24' ^X25 ' ^X34' ^X36 ' ^X45 ' ^X46 ' ^X47 ' ^X57 ' ^X58' ^X67 ' ^X68 ' ^X78 , де Xj -- ознака включення в шуканий шлях ділянки шляху від населеного пункту v_i до населеного пункту Vj , і є 1, 8, j є 1, 8 .

Рис.5

Кожна із змінних х^ набуває значення 1, якщо дуга v_tv ¦ входить у вибраний шлях, і значення 0 -- в протилежному випадку (якщо дуги, наприклад v_xv₅ і т.п. не існує, тоді природно, що х₁₅ буде дорівнювати нулеві (за матрицею зв'язності). Якщо = 0 через те, що не існує ребра v_;v_y, то в цільову функцію така змінна х_і2 не входить). В розглядуваному випадку цільова функція матиме вигляд:

Z (х-) = 7 х₁₂ + 11х₁₃ +18х₁₄ + 6х₂₄ + 14х₂₅ + 4х₃₄ +13х₃₆ + + 7 х₄₅ + 5х₄₆ + 10х₄₇ + 2х₅₇ + 15х₅₈ + 3х₆₇ +12 х₆₈ + 9х₇₈.

Складемо та опишемо обмеження на значення шуканих змінних.

З населеним пунктом v₁ межують три населені пункти v₂, v₃, v₄ . Тому, лише одна із ланок дороги (v₁v₂, v₁v₃, v₄v₄) буде належати до найкоротшого шляху дорожньої мережі. Отже, одна із змінних х₁₂, х₁₃, х₁₄ набуває значення 1, інші дві набувають значень 0. Звідси, маємо рівняння х₁₂ + х₁₃ + х₁₄ = 1. Аналогічно, лише одна із ланок дороги (v₅v₈, v₆v₈, v₇v₈) належатиме до найкоротшого шляху. Тому х₅₈ + х₆₈ + х₇₈ = 1.

Якщо припустити, що ланка (ребро) v_lv₂ належить до найкоротшого шляху, тобто х₁₂ = 1, оскільки з населеним пунктом v₂ межують v , v , то лише одна із доріг v₂v₄ , v₂v₅ буде належати тому, х₁₂ - (х₂₄ + х₂₅) = 0. Так само якщо дуга vv належить до найкоротшого шляху, тобто х₁₃ = 1, тоді v₃ межує з v₄, v₆. Отже, лише одна із ланок дороги v₃v₄, v₃v₆ буде належати до найкоротшого шляху в дорожній мережі. Тому х₁₃ - (х₃₄ + х₃₆ ) = 0 .

В населений пункту v є можливість потрапити з трьох населених пунктів v , v , v . Звідси - одна із ланок дороги v^v₄, v₂v₄, v₃v₄ буде належати до найкоротшого шляху в дорожній мережі (одна із змінних х₁₄, х₂₄, х₃₄ набуває значення 1, інші - 0). Щоб виїхати з даного населеного пункту v₄, існує також три шляхи: v v , v v , v v , один з яких буде належати до найкоротшого шляху дорожньої мережі (одна із змінних х₄₅, х₄₆, х₄₇ набуває значення 1, інші - 0). Тому х₁₄ + х₂₄ + х₃₄ - (х₄₅ + х₄₆ + х₄₇) = 0 .

В населений пункту v є можливість потрапити з двох населених пунктів v , v . Звідси - одна із ланок дороги v v , v v буде належати до найкоротшого шляху в дорожній мережі (одна із змінних х₂₅, х₄₅ набуває значення 1, інша - 0). Щоб виїхати з даного населеного пункту v₅, існує також два шляхи: v v , v v , один з яких буде належати до найкоротшого шляху в дорожній мережі (одна із змінних х₅₇, х₅8 набуває значення 1, інша - 0). Тому х₂₅ + х₄₅ - (х₅₇ + х₅₈) = 0 .

В населений пункту v₆ є можливість потрапити з двох населених пунктів v₂, v₄ . Звідси - одна із ланок дороги v v , v v буде належати до найкоротшого шляху в дорожній мережі (одна із змінних набуває значення 1, інша - 0). Щоб виїхати з даного населеного пункту v₆, існує також два шляхи: v₆v₇, v₆v₈, один з яких буде належати до найкоротшого шляху в дорожній мережі (одна із змінних х₆₇, х₆₈ набуває значення 1, інша - 0). Тому х₃₆ + х₄₆ - (х₆₇ + х₆₈) = 0 .

В населений пункту v₇ є можливість потрапити з трьох населених пунктів v₄, v₅, v₆. Звідси, одна із ланок дороги v₄ v₇, v₅ v₇, v₆ v₇ буде належати до найкоротшого шляху в дорожній мережі (одна із змінних х , х , х набуває значення 1, інші - 0). Виїхати з даного населеного пункту v можливо лише одним шляхом - v v , тому він буде належати до найкоротшого шляху в дорожній мережі

(змінна x_1S набуває значення 1). Маємо рівняння: ^х47 + ^х57 + ^х67 ^х78 = ⁰ .

Таким чином, обмеження на змінні в даній задачі матимуть вигляд:

Задачу розв'язуватимемо за допомогою програмного засобу MS Excel:

0. В клітинки А2:А16 введемо індекси початкових вершин, а в клітинки В2:В16 - індекси кінцевих вершин всіх можливих дуг дорожньої мережі.

1. В клітинки С2:С16 введемо значення коефіцієнтів цільової функції.

2. В клітинку F2 введемо вираз цільової функції: =CYMMnPOH3B(C2:C16;D2:D16) - сума добутків довжин дуг та значень змінних xtj.

3. В клітинки Е2:Е9 вводимо обмеження: =СУMM(D2:D4)

де, наприклад, СУММ (D2:D4) - сума чисел, вказаних в діапазоні клітинок від D2 до D4; СУMM(D4:D5;D7) - сума всіх чисел, вказаних в діапазоні клітинок від D4 до D5 та в клітинці D7.



Рис.6

Рис.7

Рис.8



Рис.9

Далі потрібно звернутися до послуг Сервіс/Пошук розв'язку, після чого з'явиться допоміжне вікно, в якому необхідно вказати наступне:

1. В полі "Оптимізувати значення цільової функції” вказати адресу клітинки, де міститимуться результати обчислення значень цільової функції - $F$2;

2. В полі "До": вибираємо перемикач "Мінімум";

В полі "Змінюючи значення змінних в клітинках" вказуємо діапазон клітин $D$2:$D$16 - їх

Рис.10

3. вмісти можуть змінюватися в процесі пошуку розв'язку (рис. 7);

4. Вводимо обмеження на значення змінних в розділі "У відповідності з обмеженнями". Для цього необхідно натиснути кнопку "Додати", після чого відкривається допоміжне вікно "Додавання обмеження" (рис. 8).

Після натискання кнопки "Знайти розв'язок ” (рис. 7) з'являються результати обчислень.

Рис.11

Тим самим знайдений найкоротший шлях із початкового населеного пункту v до кінцевого v₈, за яким визначаються послідовні переходи між сусідніми населеними пунктами: від v до v , від v до v₄, від v₄ до v₆, від v₆ до v₇, від v₇ до v₈ (рис. 10). В такому разі загальна довжина шляху буде мінімальна і дорівнюватиме ЗО км.

Приклад 3. Розглянемо іншу задачу на знаходження найкоротших шляхів в дорожній мережі від першої вершини до всіх інших вершин - населених пунктів в деякому географічному районі.

Мережа доріг в районі задана у вигляді схеми, яка складається з 8 вершин і 16 дуг. Довжина дороги (км) між двома сусідніми населеними пунктами рівна для кожної дуги значенню, яке вказано поряд із цією дугою.

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

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

L (v.) - постійна мітка вершини vt,

L (v. ) - нова тимчасова мітка вершини v ,

L (v. ) - попередня тимчасова мітка вершини v,,

R. - довжина ребра, що з'єднує вершини v{ та vj .

Нову тимчасову мітку знайдемо за формулою

Рис.12

оптимізаційний задача математичний програмування

Дану задачу будемо розв'язувати за допомогою онлайн-сервісу для розв'язування задач оптимізації (http: //uchimatchast. ru/).

Обравши Пошук оптимального шляху (метод Дейкстри), потрібно вказати кількість вершин графа.

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

Найкоротший шлях від вершини 1 до вершини 2 - d(2)=32. Згідно формули (1), це ребро (1,2), оскільки (див. формулу (1)):

d(3)=min{d(3) ; d(2)+a(2,3)}=min{85; 32+70}=85 d(4)=min{d(4) ; d(2)+a(2,4)}=min{75; 32+да}=75 d(5)=min{d(5) ; d(2)+a(2,5)}=min{57; 32+23}=55 d(6)=min{d(6) ; d(2)+a(2,6)}=min{®; 32+да}=да d(7)=min{d(7) ; d(2)+a(2,7)}=min{®; 32+да}=да d(8)=min{d(8) ; d(2)+a(2,8)}=min{®; 32+да}=да



Найкоротший шлях від вершини 1 (через ребро (1,2)) до вершини 5 - d(5)=55. Згідно формули (1), це ребро (2,5), оскільки

d(3)=min{d(3) ; d(5)+a(5,3)}=min{85; 55+да}=85 d(4)=min{d(4) ; d(5)+a(5,4)}=min{75; 55+10}=65 d(6)=min{d(6) ; d(5)+a(5,6)}=min{®; 55+11}=66 d(7)=min{d(7) ; d(5)+a(5,7)}=min{w; 55+20}=75 d(8)=min{d(8) ; d(5)+a(5,8)}=min{®; 55+да}=да

Найкоротший шлях від вершини 1 (через ребра (1,2), (2,5)) до вершини - 4 d(4)=65. Згідно формули (1), це ребро (5,4), оскільки

d(3)=min{d(3) ; d(4)+a(4,3)}=min{85; 65+18}=83 d(6)=min{d(6) ; d(4)+a(4,6)}=min{66; 65+да}=66 d(7)=min{d(7) ; d(4)+a(4,7)}=min{75; 65+да}=75 d(8)=min{d(8) ; d(4)+a(4,8)}=min{w; 65+да}=да

Найкоротший шлях від вершини 1 (через ребра (1,2), (2,5)) до вершини - 6 d(6)=66. Згідно формули (1), це ребро (5,6), оскільки

d(3)=min{d(3) ; d(6)+a(6,3)}=min{83; 66+да}=83 d(7)=min{d(7) ; d(6)+a(6,7)}=min{75; 66+7}=73 d(8)=min{d(8) ; d(6)+a(6,8)}=min{w; 66+да}=да

Найкоротший шлях від вершини 1 (через ребра (1,2), (2,5), (5,6) до вершини - 7 d(7)=73. Згідно формули (1), це ребро (6,7), оскільки

d(3)=min{d(3) ; d(7)+a(7,3)}=min{83; 73+да}=83 d(8)=min{d(8) ; d(7)+a(7,8)}=min{w; 73+12}=85



Найкоротший шлях від вершини 1(через ребра (1,2), (2,5), (5,4)) до вершини - 3 d(3)=83. Згідно формули (1), це ребро (4,3), оскільки

d(8)=min{d(8) ; d(3)+a(3,8)}=min{85; 83+да}=85

Найкоротший шлях від вершини 1 (через ребра (1,2), (2,5), (5,6), (6,7)) до вершини - 8 d(8)=85. Згідно формули (1), це ребро (7,8), оскільки мітки інших ребер задовільняють формулу (1).

Отже, отримано найкоротші шляхи в дорожній мережі від першої вершини до всіх інших вершин - населених пунктів в деякому географічному районі (для даного графа): d(1)=1 Довжина шляху L=0 d(2)=1-2 Довжина шляху L=32 d(3)=1-2-5-4-3 Довжина шляху L=83 d(4)=1-2-5-4 Довжина шляху L=65 d(5)=1-2-5 Довжина шляху L=55 d(6)=1-2-5-6 Довжина шляху L=66 d(7)=1-2-5-6-7 Довжина шляху L=73 d(8)=1-2-5-6-7-8 Довжина шляху L=85.

Приклад 4. Задача розрахунку траєкторії літака. Літак у точці S0 має швидкість V0 та висоту Н0. Він повинен піднятися на висоту Hk і набути швидкість Vk. Потрібно мінімізувати витрати палива, якщо відомі витрати палива на збільшення швидкості від V до V2 на висоті Н = const, та відомі витрати палива на збільшення висоти від Н1 до Н2 на швидкості v = const. Дані розрахунків показано на рис. 14.

Всі прямокутники спочатку порожні. Між прямокутниками вказані цифри витрат палива на збільшення висоти (вертикальні лінії) та на збільшення швидкості (горизонтальні лінії). Початкова точка позначена як S₀, а кінцева - як S_k. Розрахунок починається з кінцевої точки S_k і переміщується у напрямку початкової точки S₀.

Алгоритм розв'язування задачі:

В кінцевому прямокутнику записуємо витрати палива “0”.



Рис.13

1. В прямокутниках B₁ та B₂ записуємо витрати палива відповідно “11” та “8", що витрачаються для досягнення кінцевої точки S_k. Можлива оптимальна траєкторія позначається стрілками, а заборонені шляхи не помічаються стрілками.

2. В точки Bi, B₂ можна попасти з точок С₁, C₂, С₃. Із прямокутника С₂ на кінцеву точку можна йти шляхом через точку B₁ (з витратами палива 7 + 11 = 18) або через точку В₂ (з витратами палива 9 + 8 =17). У прямокутнику С₂ записуємо найменші витрати палива “17”. Аналогічно знаходимо витрати палива, якщо літак рухатиметься з C_i через точку B_i (найменші витрати палива становитимуть “17”) і з С₃ через точку B₂ (найменші витрати палива становитимуть “15”). Показуємо лише однією стрілкою можливу оптимальну траєкторію руху літака через точки С₃ та B₂. Стрілка на точку B₁ не показується, бо на цьому шляху витрати палива більші.

В такий спосіб вказуються витрати палива у всіх інших прямокутниках, і отримується ряд можливих траєкторій, позначених стрілками. Оптимальна кількість палива отримується у стартовому прямокутнику S₀ - цифра "37”.

Оптимальний шлях отримується переміщенням з початкової точки S₀ відміченими шляхами у кінцеву точку S_k (оптимальний шлях показаний яскравішими стрілками).

Таким чином отримали кількість витраченого палива та оптимальний шлях.

У даній задачі визначені всі умови переміщення для початкової та кінцевої точки. Тому процес отримання оптимальної траєкторії можна було б почати з початку - з точки S₀, позначаючи у прямокутниках мінімальну витрату палива за такого переміщення. Кінцевий результат (кількість витраченого палива та оптимальна траєкторія) в даному разі не змінюється.

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

Наведений розрахунок корисний тим, що аналізуючи його, можна наочно побачити всі виконані варіанти розрахунків, у тому числі і зайві.

Дану задачу можна розв'язати за допомогою програмного засобу Графоаналізатор 1.3.

Графоаналізатор - візуальне середовище для роботи з графами. Використання Графоаналізатора не тільки надає можливість створювати і опрацьовувати графи, але візуально відображати результати виконання дій за алгоритмами. В програмному засобі реалізовано велику кількість алгоритмів для опрацювання графів. Графоаналізатор є безкоштовним і вільнопоширюваним програмним засобом, який можна завантажити з офіційного сайту програми

оптимізаційний задача математичний програмування

Рис.14



Щоб створити граф, потрібно запустити програму на виконання. В результаті з'являється форма «Створення графа», де слід обрати «Навантажений граф» (граф, у якого кожній дузі приписана її вага - деяке дійсне число). Обираємо числову номерацію вершин графа.

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

Рис. 15



Рис.16

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



Рис.17

Рис.18

В результаті з'являється нова форма з графічно поданим розв'язком та результатами роботи за алгоритмом, де видно, що для того, щоб літак з точки S₀ дістався до точки S_k оптимальною траєкторією, потрібно 37 одиниць палива.

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



Список використаних джерел

1.Динамічне та нелінійне програмування. Методичні вказівки до проведення практичних та самостійних занять з курсу“ Дослідження операцій” для студентів факультету кібернетики / [упорядн. В. I. Тюптя, В. I. Шевченко, В. К. Стрюк]. - К.: Електронне видання. Ел. бібліотека факультету кібернетики Київського національного університету імені Тараса Шевченка, 2003. - 30 с. Режим доступу: http://cyb.univ.kiev.ua/library/books/tiuptia-31.pdf

2.Жалдак М. І. Основи теорії і методів оптимізації: навчальний посібник / М. І. Жалдак, Ю. В. Триус. - Черкаси: Брама-Україна, 2005. - 608 с.

3.Кутковецький В. Я. Дослідження операцій: Навчальний посібник / В. Я Кутковецький. - Миколаїв: Вид-во МДГУ ім. П. Могили, 2003. - 260 с.

4.Наконечний С. І., Савіна С. С. Математичне програмування: навч. посіб. - К.: КНЕУ, 2003. - 452 с.

5.Беллман Р. Динамическое программирование / Р Беллман. - М.: Изд-во Иностранная литература, 1960. - 400 с.

6.Вентцель Е. С. Введение в исследование операций / Е. С. Вентцель. - М., Советское радио, 1964. - 390 с.

7.Ермольев Ю. М. Методы стохастического программирования / Ю. М. Ермольев. - М.: Наука, 1976. - 240 с.

8.Канторович Л. В. Математические методы в организации и планировании производства / Л. В. Канторович. - Л.: Изд-во ЛГУ, 1939. - 68 с.

9.Майзе Х. Иследование операций: в 2 т. / Х. Майзе, Н. Эйджин, Р. Тролл; [пер. с анг. под ред. Дж. Моудера, С. Элмагаби]. - М.: Мир, Т.1. - 1981. - 712. с.

10.Понтрягин Л. С. Математичечская теория оптимальных процесов / Л. С. Понтрягин, В. Г. Болтянський, Р. В. Гамкрелидзе, Е. Ф Мищенко. - 4-е изд. - М.: Наука, 1983. - 392 с.

11.Юдин Д. Б. Задачи и методы стохастического программирования / Д. Б. Юдин. - М.: Советское радио, 1979. - 392 с.

12.Kuhn H. W., Tucker A. W. Nonlinear Programming/ Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, Berkeley and Los Angeles, University of California Press, 1951. - р. 481-492.

Размещено на Allbest.ru

...