Задача про прокладання найвигіднішого шляху між двома пунктами

Задача про прокладання найвигіднішого шляху

 між двома пунктами

Розглянемо задачу: Залізнична колія, що прокладаєть­ся між двома населеними пунктами А і В, має пройти через пе­ресічену місцевість: ліси, болота, річку, пагорби тощо. Відома вартість прокладання дороги через окремі зони, на які можна розбити місцевість між цими населеними пунктами. Необхідно так прокласти дорогу, рухаючись від пункту А до пункту В, щоб сумарні витрати на її спорудження були мінімальними.

Розглянемо конкретний приклад. Прямокутна область між двома пунктами А і В розбита на зони 5-ма рядками і 4-ма стовпцями, у кожній з яких зазначена вартість прокладання залізничної колії. Будемо рухатися від лівої нижньої зони до правої верхньої лише вгору і направо. Вислов­люючись алгоритмічною мовою, вважатимемо, що задано таб­лицю A[i,j] розмірністю n*m (n=5, т=4).

5	2	8	5
1	4	6	1
3	7	5	6
10	1	5	3
3	4	2	6

Перша ознака задачі динамічного програмування полягає в тому, що загальне розв'язування задачі можна розбити на окремі етапи, на кожному з яких розглядатиметься елемент таблиці A[i,j].

Стартовим буде елемент A[5,1] : його значення не змінюється. Розглянемо сусідні для нього елементи, у які може виконуватися перехід: A[4,1] і A[5,2]. Зміна значення елемента A[4,1] залежить лише від значення A[5,1] , і вартість такого переходу становитиме 3 + 10 = 13. Зміна значення елемента A[5,2] залежить також лише від значення A[5,1] , і його значення при переході від A[5,1] вправо становитиме 3 + 4 = 7.

Наступним для розгляду елементом може бути A[4,2] . До цього елемента можна перейти двома шляхами: або від лівого елемента A[4,1] , або від нижнього A[5,2] . Вартість першого переходу становитиме 13 + 1 = 14, а другого 7 + 1 = 8. Зрозуміло, що кращим є другий перехід. Запишемо нове перераховане значення A[4,2] у таблицю .

5	2	8	5
1	4	6	1
3	7	5	6
13	8	5	3
3	74	2	6

Продовжуючи за аналогією перерахунок значень елементів таблиці, будемо розглядати ті її елементи, для яких існує перерахований лівий і нижній елементи, а для крайніх елементів - відповідно лівий або нижній. На кожному етапі новим значенням елемента A[i,j] буде менше з двох можливих варіантів. Таким чином дійдемо до останнього елемента A[1,4]. Отримане значення елемента A[1,4] буде найменшою вартістю прокладання залізничної колії від населеного пункту А до населеного пункту B.

Найчастіше в подібних задачах цікавить не лише кінцевий результат, а й шлях його отримання. Чи можна визначити послідовність переходів по таблиці, яка приводить до отримання оптимальної відповіді? А саме як треба прокласти оптимальну за вартістю залізничну колію? Для цього потрібно відновити рух по таблиці у зворотному порядку. Згадаємо, як ми потрапили в клітинку таблиці A[1,4] і отримали її нове значення. Цей перехід було виконано з одного із сусідніх елементів (лівого або нижнього), що мав менше значення. Тому і зворотний шлях треба спрямувати на цей елемент. Для нашого прикладу A[1,3] = 29, A[2,4] = 23, тому переходимо до елемента A[2,4] . Для нього сусідніми, з яких ми могли зробити перехід, є A[2,3]= 24, A[3,4]= 22. Вибираємо перехід до елемента A[3,4].

Чи завжди отримається однозначна відповідь? Стосовно ре­зультуючого оптимального значення для елемента а_пт відпо­відь буде завжди одна. А от стосовно визначення шляху, що приводить до отримання цієї відповіді, не завжди. У наведеному прикладі під час вибору найменшого еле­мента жодного разу не траплялася ситуація, коли ці значення однакові. А якщо трапиться, то отримується розгалуження у визначенні оптимального шляху: їх уже буде два. У разі повторення подібної ситуації - чотири, а далі - вісім і т. д. Для визначення хоча б одного зі шляхів можна застосувати наведені вище міркування, але якщо задача вимагає визначення всіх можливих шляхів, то необхідно орга­нізувати рекурсивний алгоритм.

Підсумуємо характерні особливості розглянутої задачі і ви­значимо, чому її можна вважати саме задачею динамічного програмування.

По-перше, задача була розбита на окремі етапи, яким відповідали зміни значень елементів заданої таблиці.

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

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

По-четверте, всі етапи розв'язування задачі були залежни­ми, оскільки від вибраних значень попереднього етапу залежа­ла зміна значень наступного.

Перш ніж представити програмний код описаного алго­ритму, модифікуємо наші попередні міркування. Вони стосуються крайніх лівих і нижніх еле­ментів таблиці (за винятком найлівішого нижнього елемента). Можна почати перерахунок елементів усієї таблиці саме з них, оскільки значення кожного елемента першого стовпця залежить лише від значення його нижнього сусіда, а значення кожного елемента останнього рядка - від значення його лівого сусіда. Інший вихід із цієї ситуації: доповнимо задану таблицю зна­чень фіктивним стовпцем із номером 0 та фіктивним рядком із номером (п + 1) і встановимо значення цих елементів, як мак­симально можливі для визначеного типу. Таким чином, під час обробки будь-яких елементів таблиці A[i,j] вони будуть виклю­чені з наступного розгляду.

for i := n-1 downto 1 do    {Перерахунок значень крайнього лівого стовпця.}

   іnc(A[i,1], A[і+1,1]);     {або A[i,1] := A[i,1] +A[і+1,1]} for j := 2 to m do       {Перерахунок значень}

   inc(A[n,j], A[n,j- 1])        {крайнього нижнього рядка.}

for і := n - 1 downto 1 do   {Перерахунок решти елементів таблиці}

   for j := 2 to m do             {і збільшення їх значень}

       inc(a[i, j], min(a[i + 1, j], a[i, j - 1]));

Фрагмент програми, що виводить визначений результат, пе­редбачає лише один із можливих варіантів шляхів:

writeln (a[1,m]);                      {Виведення результуючого значення.)

i := 1; j := m;                           {Ініціалізація визначення самого шляху.)

while not((i = n) and not(j = 1)) do {Поки поточний елемент таблиці не є нижнім лівим,)

   begin

       write('i=',i,'    j=',j);                     {Виведення індексів поточного елемента}

       if A[i+1,j] < A[i,j-1]                       {перехід до меншого з двох сусідніх:}

          then inc(i)                                               { нижнього }

          else dec(j)                                               { або лівого }

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

Завдання

Прямокутна область між двома пунктами А і В розбита на зони n-ма рядками і m-ма стовпцями, у кожній з яких зазначена вартість прокладання залізничної колії. Будемо рухатися від лівої нижньої зони до правої верхньої лише вгору і направо.

1. Знайти найменшу вартість прокладання залізничної колії від населеного пункту А до населеного пункту B (змінюючи дані в таблиці). (3 бали)

2. Знайти шлях для отримання найменшої вартості (з пункту В до пункту А, , наприклад: а[4,2], a[3,2], a[3,1] ). (3 бали)

3. Написати програму для визначення елементів матриці (те що в п.1). (3 бали)

4. Додати в програму визначення шляху (те що в п.2). (3 бали)

ОСНОВИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

ОСНОВИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

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

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

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

У задачах лінійного програмування розв'язки знаходяться за допомогою ітераційних кроків. Однак на кожному з таких кроків обробляється вся інформація, що описує задачу. Такі задачі виконуються за один етап, тобто є одноетапними.

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

Ідею розв'язування задач динамічного програмування можна представити так. Спершу розглянемо деяку умовну задачу, процес розв'язку якої можна розбити на етапи і яка на кожному з цих етапів має три варіанти відповідей v1, v2, v3. Щоб не загубити жодного кінцевого розв'язку задачі, потрібно було б на кожному  наступному, другому, етапі розв'язати задачу для кожної з цих варіантів відповідей. Якщо цей процес продовжувати далі, то на останньому, n-му, етапі ми будемо мати справу з 3^(n-1) варіантами відповідей. Оскільки розглядається задача оптимізації, яка вимагає визначення максимального чи мінімального значення серед усіх 3^(n-1) отриманих відповідей, то для скорочення цієї кількості на кожному етапі варто відкидати ті проміжні вааріанти відповідей, які не є оптимальними, а значить, і не приведуть до оптимального кінцевого результату. Отже, задачі динамічного програмування розбиваються на окремі залежні одна від одної підзадачі, а звідси випливає, що неоптимальний розв'язок однієї з підзадач у жодному разі не дасть оптимального кінцевого розв'язку.

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

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

Етапи	1	2	3	...	n
Варіанти
1	v1(1)	v1(2)=опт(v1(1), v2(1), v3(1))	v1(3)=опт(v1(2), v2(2), v3(2))		v1(n)=опт(v1(n-1), v2(n-1), v3(n-1))
2	v2(1)	V2(2)=опт(v1(1), v2(1), v3(1))	V2(3)=опт(v1(2), v2(2), v3(2))		V2(n)=опт(v1(n-1), v2(n-1), v3(n-1))
3	v3(1)	V3(2)=опт(v1(1), v2(1), v3(1))	V3(3)=опт(v1(2), v2(2), v3(2))		V3(n)=опт(v1(n-1), v2(n-1), v3(n-1))

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

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

Самостійна по ЛП

Запитання по темі “Лінійне програмування”

1.        Що розуміють під терміном «програмування» у назві математичної дисципліни «Математичне програмування»?

2.        Які задачі розв'язує така математична дисципліна, як дослідження операцій?

3.        Як математичне програмування пов'язане з дослідженням операцій?

4.        Яке відношення має математичне програмування до теорії прийняття рішень?

5.        На які два типи можна поділити всі задачі математичного програмування? Які їх характерні ознаки?

6.        Які класи задач виділяються окремо у математичному програмуванні?

7.        Як формулюється задача про використання сировини? Чому її можна віднести до задач лінійного програмуваня?

8.        Як формулюється задача про складання харчового раціону? Чому її можна віднести до задач лінійного програмування?

9.        Як формулюється задача про рюкзак? Чому її можна віднести до задач лінійного програмування?

10.     Як формулюється транспортна задача? Чому її можна віднести до задач лінійного програмування?

11.     Як формулюється загальна задача лінійного програмування?

12.     Що називають системою обмежень задачі лінійного програмування?

13.     Що називають цільовою функцією задачі лінійного програмування?

14.     Що називають допустимими розв'язками або планами задачі лінійного програмування? Скільки їх може бути? Обґрунтуйте свою відповідь.

15.     Який розв'язок задачі лінійного програмування називається оптимальним планом?

16.     Сформулюйте алгоритм геометричного розв'язування задачі лінійного програмування від двох параметрів.

17.     Виконайте алгоритм геометричного розв'язування задачі лінійного програмування від двох параметрів на власному прикладі.

18.     Які можливі випадки одержання розв'язку задачі лінійного програмування?

Тема 17. Геометрична інтерпретація розв'язування задач лінійного програмування

Геометрична інтерпретація

розв'язування задач лінійного програмування

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

Геометрично систему обмежень цієї задачі, що є системою нерівностей

2*x1 + 5*x2 <= 20

8*x1 + 5*x2 <= 40

5*x1 + 6*x2 <= 30

можна зобразити у вигляді деякої області на декартовій площині:

Оскільки розв'язки задач лінійного програмування завжди знаходяться в області невід'ємних значень, то до обмежень задач лінійного програмування потрібно дописати ще дві нерівності: x1>=0 та x2>=0. На малюнку ці дві нерівності визначають першу чверть системи координат. Координати множини точок, що належать побудованому багатокутнику, є розв'язками цієї системи, а багато­кутник називається областю допустимих розв'язків.

Для визначення цільової функції та її обмежень, побудуємо багатокутник допустимих значень OABCD. Оскільки всі нерівності містять знак <= , то багатокутник допустимих розв'язків включає і прямі.

Далі для пошуку максимального розв'язку серед усіх допустимих будується опорна пряма (або пряма нульового рівня):

L = 50*x1 + 40*x2 = 0

З цього рівняння видно, що пряма проходить через початок координат. Якщо цільова функція матиме вільний член, то при побудові опорної прямої його можна проігнорувати, адже максимум лінійної функції L = b*x1 + c*x2 +d досягається при тих самих значеннях x1 та x2, що і максимум лінійної функції без вільного члена d. Щоб визначити точку - максимум або мінімум серед допустимих розв'язків, потрібно переміщувати опорну пряму паралельно самій собі в одному з напрямів. При цьому значення L2 буде або збільшуватись, або зменшуватись. Залежно від постановки вихідної задачі (у даній задачі - це пошук максимуму) визначається напрям руху опорної прямої: за вектором напряму у випадку максимізації цільової функції або проти вектора напряму при мінімізації цільової функції. Вектор напряму визначається коефіцієнтами цільової функції:  вектор a(b,c)

Для даної задачі вектор напряму матиме вигляд: вектор а(50,40). Оскільки цільову функцію цієї задачі потрібно дослідити на максимум L = 50*x1 + 40*x2 —> max, то опорну пряму потрібно переміщувати в напрямі, який вказує побудований вектор напряму (на малюнку).

Координати останньої крайньої точки багатокутника допустимих значень, яку перетне опорна лінія на своєму шляху, і будуть тими значеннями, при яких величина L2 набуде максимального значення. Для нашої задачі такою вершиною багатокутника є вершина С. Вона утворюється при перетині прямих 8*x1 + 5*x2 = 40 та 5*x1 + 6*x2 = 30. Для визначення координат цієї вершини потрібно лише розв'язати відповідну систему лінійних рівнянь:

8*x1 + 5*x2  = 40

5*x1 + 6*x2  = 30

і підставити отриманий розв'язок (приблизно x1 =3,9; x2 =1,74) у функцію. У результаті отримаємо такий розв'язок цієї задачі лінійного програмування L2 = 264,6.

Опишемо алгоритм пошуку оптимального значення задачі лінійного програмування в геометричній інтерпретації.

1.   За умовою задачі записати обмеження та цільову функцію.

2.   Побудувати багатокутник допустимих значень.

3. Побудувати опорну пряму відповідно до скоректо­ваної цільової функції: прибрати вільний член і прирів­няти до 0.

4. За коефіцієнтами цільової функції при невідомих побудувати вектор напряму і визначити напрям переміщення опорної прямої для досягнення оптимального значення цільової функції.

5. Визначити точку, в якій цільова функція набуває опти­мального значення, та рівняння прямих, на перетині яких зна­ходиться визначена точка.

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

Обов'язково потрібно розглядати такі три можливі випадки одержання розв'язку задачі лінійного програмування:

1) задача має один розв'язок, тобто опорна пряма на останньому кроці перетинає одну точку, яка є вершиною області до­пустимих розв'язків;

2) задача має безліч розв'язків, тобто опорна пряма на ос­танньому кроці перетинає відрізок, який є однією зі сторін об­ласті допустимих розв'язків;

3) розв'язок задачі відсутній, тобто опорна пряма пере­міщується в бік, де область допустимих значень не обмежена відрізком прямої, або опорна пряма переміщується в бік, про­тилежний до розміщення області допустимих значень.

Завдання

1. Розв'язати геометрично задачу про використання сировини для випадку існування одного оптимального розв'язку, ви­користавши власні вхідні дані.

2. Розв'язати геометрично задачу про використання сировини для випадку існування безлічі оптимальних розв'язків, ви­користавши власні вхідні дані.

3. Розв'язати геометрично задачу про використання сировини для випадку відсутності жодного оптимального розв'язку, використавши власні вхідні дані.

4. Розв'язати геометрично задачу про складання харчового раціону для випадку існування одного оптимального роз­в'язку, використавши власні вхідні дані.

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

6. Розв'язати геометрично задачу про складання харчового раціону для випадку відсутності жодного оптимального роз­в'язку, використавши власні вхідні дані.