79896

Основні підходи і методи рішення транспортної задачі лінійного програмування

Дипломная

Информатика, кибернетика и программирование

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

Украинкский

2015-02-15

206.84 KB

0 чел.

25

Зміст

Вступ 2

1 Транспортна задача 3

2 Методи рішення транспортиних задач 6

2.1 Метод північно-західного кута 6

2.2 Метод мінімального елемента (мінімальної вартості) 6

2.3 Метод потенціалів розв’язання транспортної задачі 7

3 ЦІЛОЧИСЛОВІ ТА ДИСКРЕТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ 13

3.1 Задача про призначення 13

3.2 Задача про комівояжера 14

3.3 Задача про рюкзак 14

3.4 Задача про вибір транспортних засобів 15

3.5 Транспортна задача з фіксованими доплатами 16

3.6 Методи відтинання. 17

3.7 Метод гілок і меж 20

Висновки 24

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ 25



Вступ

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

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

Основною метою задачі є мінімізувати витрати на транспортування продукції споживачам.


1 Транспортна задача

Серед ЗЛП особливе місце посідає транспортна задача (ТЗ). Це пов’язано, насамперед, з її практичною значущістю, а також із тим, що специфічні властивості цієї задачі дають змогу значно спростити методи її розв’язання порівняно з тими, що застосовують до звичайних ЗЛП.

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

Математична модель задачі складається з цільової функції

множини допустимих значень, заданої нерівностями

і прямих обмежень

Якщо попит і пропозицію збалансовано, тобто виконується умова

маємо так звану закриту ТЗ. Якщо умова (1.5) не виконується, то задача називається відкритою.

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

чи

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

Закрита ТЗ має такі властивості:

1) вона завжди допустима та має розв’язок;

2) серед рівнянь-обмежень (1.2) та (1.3) лише  лінійно незалежні;

3) якщо в умовах задачі всі числа  , , та , , цілі, то оптимальний розв’язок задачі також цілочисловий.

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

Базисні розв’язки ТЗ як різновиду ЗЛП лежать у вершинах допустимої області. Це означає, що будь-який базисний розв’язок складається з додатних і нульових координат, причому додатних координат у не виродженому розв’язку рівно стільки, скільки лінійно незалежних обмежень у задачі. Якщо розв’язок вироджений, то додатних координат менше, ніж таких обмежень. Отже, із загальних властивостей ЗЛП та другої властивості ТЗ можна дійти висновку, що не вироджений базисний розв’язок ТЗ містить рівно ненульових перевезень . У виродженому розв’язку ненульових перевезень менше.

Обчислення, пов’язані з розв’язанням ТЗ, виконують у транспортних таблицях. Вони відрізняються від звичайних симплекс-таблиць тим, що в них заповнюють лише ті клітини , у яких перевезення ненульові: . Такі клітини називають зайнятими (заповненими), а інші  вільними. Зрозуміло, що не виродженому розв’язку відповідає рівно  зайнятих клітин.

Початкова транспортна таблиця містить інформацію про виробників продукції (у першому стовпці), їхні можливості (в останньому), про споживачів продукції (у першому рядку), їхні потреби (в останньому), а також про вартість перевезень , , , ,  записану в правому верхньому куті внутрішніх клітин таблиці. У центрі  клітин записують значення перевезень .

Побудувати початковий базисний розв’язок ТЗ значно простіше, ніж для звичайної ЗЛП. Опишемо два найпоширеніші та найчастіше застосовувані методи визначення початкового базисного розв’язку ТЗ.



2 Методи рішення транспортиних задач

  1.  Метод північно-західного кута

У цьому методі не використовують інформацію про вартість перевезень, а, вибираючи клітину для заповнення, орієнтуються лише на її географічне розміщення. Заповнення за цим методом починають із верхньої лівої (північно-західної) клітини. Продукцію першого виробника розподіляють так, щоб максимально задовольнити потреби першого споживача, потім другого і т. д. до повного розподілу всієї виробленої продукції. Якщо попит якогось споживача  не задоволено, то продукцію постачають від другого виробника, потім третього і т. д. до повного задоволення попиту. Зрозуміло, що якщо задоволено потреби споживачі  чи повністю розподілено продукцію виробників , то ці виробники та споживачі більше не беруть участі в розподілі. Унаслідок застосування цього методу зайняті клітини транспортної таблиці утворюють характерну східчасту форму: початок “сходів” міститься у верхньому лівому куті таблиці, а кінець – у нижньому правому. Сума перевезень в -му рядку дорівнює , а в -му стовпці .

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

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

 

  1.   Метод мінімального елемента (мінімальної вартості) 

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

Метод реалізовано так. На першому кроці визначають мінімальний елемент матриці . Нехай це буде . Беруть . Можливі два випадки:

  1.     (можливості   виробника  менші, ніж потреби  споживача ;
  2.    (навпаки). У першому випадку нулями заповнюють увесь рядок , крім -го елемента, а в другому  увесь стовпець , крім -го елемента,  з подальших обчислень виключають виробника  (у першому випадку) чи споживача  (у другому). Із матриці  викреслюють відповідний рядок або стовпець, отримують матрицю . Коригують значення відповідних елементів векторів  та . Беруть

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

  1.  Метод потенціалів розв’язання транспортної задачі 

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

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

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

Викладемо сутність методу потенціалів.

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

2. Визначають потенціали так, щоб у кожній базисній (ненульовій) клітині виконувалась умова , тобто складають систему рівнянь

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

3. За знайденими потенціалами обчислюють відносні оцінки небазисних (нульових) клітин. Якщо для усіх цих клітин  , то даний базисний розв’язок оптимальний. Якщо ж існують небазисні клітини, для яких  , то цей розв’язок можна поліпшити, тобто перейти до іншого базисного розв’язку з меншою вартістю перевезень. Як і в звичайному симплекс-методі, зміна базису полягає в тому, щоб до базису ввести змінну, яка має «найгіршу» відносну оцінку, і вивести одну з поточних базисних змінних.

Очевидно, що до базису вводять змінну з найменшою від’ємною відносною оцінкою  . Нехай це клітина .Визначимо, яку з базисних клітин слід вивести з базису. Для цього з клітин транспортної таблиці утворимо цикл(замкнений ланцюг) так, щоб він містив клітину  (небазисну, нульову) і деякі базисні клітини. Позначимо клітини циклу так: небазисну – знаком «+», а інші(базисні) – знаком «-» чи «+», але так, щоб у кожному рядку та стовпці транспортної таблиці була однакова кількість різних знаків, що чергуються між собою. Кожну наступну клітину для позначення відповідним знаком вибирають лише в тому самому рядку чи стовпці, де вже є позначена. Починають і закінчують цикл у небазисній клітині .

Серед базисних клітин, позначених знаком «-», виберемо найменше перевезення . Збільшимо обсяг перевезень на   у клітинах, позначених знаком «+», і зменшимо на ту саму величину обсяг перевезень у клітинах, позначених знаком «-». Після такого перерозподілу вантажу одна з базисних клітин стане вільною, тобто вийде з базису, а клітина  ввійде до нього й міститиме перевезення .

4. Отриманий новий базисний розв’язок перевіряють на оптимальність. Процедура виконується доти, доки для поточного базисного розв’язку не виконається критерій оптимальності.

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

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

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

обмежень на продукцію

та прямих обмежень на перевезення

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

Така задача може виявитися нерозв’язною, якщо пропускна здатність магістралей, що ведуть до -го споживача, менша за його потреби, тобто 

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

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

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

Тут  означає максимальне значення серед елементів , що відповідають ненульовим перевезенням  (для  вважаємо) розглянутого допустимого плану перевезень. Зрозуміло, що за час  буде виконано всі перевезення. Потрібно добрати такий допустимий план, для якого цей час мінімальний.

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

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

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

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

Наприклад, граф  можна описати множиною вершин  і множиною дуг Оскільки транспортні перевезення мають певний напрямок, то пари вершин упорядковані, і граф називається орієнтованим (напрямленим).

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

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

З поняттям графу тісно пов’язане поняття мережі. Так називають граф, елементам якого поставлено у відповідність певні параметри: вершинам, дугам. На практиці величини di інтерпретують як обсяги виробництва (di > 0) чи обсяги споживання  певного однорідного продукту; – обмеження на пропускні здатності комунікацій, що пов’язують пункти . Параметром дуги може бути також вартість перевезень  одиниці продукції з пункту  в пункт .

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

Методи розв’язання транспортних (та інших) задач, що ґрунтуються на теорії графів, часто виявляються ефективнішими від розглянутих матричних.



3 ЦІЛОЧИСЛОВІ ТА ДИСКРЕТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

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

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

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

  1.   Задача про призначення

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

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

для обмежень

  1.   Задача про комівояжера

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

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

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

для обмежень

 

  1.  Задача про рюкзак

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

для обмежень

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

  1.  Задача про вибір транспортних засобів

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

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

1)  – місткість (кількість місць);

2)  – чисельність обслуги;

3)  – витрати пального за певний період часу;

4)   –  прибуток від використання -го засобу на -му маршруті.

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

Математична модель цієї задачі має такий вигляд: максимізувати

для обмежень

  1.  Транспортна задача з фіксованими доплатами

 

Вона відрізняється від звичайної ТЗ тим, що витрати на перевезення однорідного вантажу з пункту  в пункт  визначають так:

де   витрати на перевезення одиниці вантажу; j  фіксована доплата за оренду транспортних засобів.

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

Зазначені задачі поділяють на такі класи:

1) із неподільностями (про рюкзак, вибір транспортних засобів);

2) екстремальні комбінаторні (про призначення, про комівояжера);

3) із розривними цільовими функціями (транспортна з фіксованими доплатами).

Узагальнюючи наведені приклади, можна отримати таку модель задачі цілочислового програмування: максимізувати

за умов

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

  1.   Методи відтинання.

Ідея методів відтинання така. Спочатку розв’язують допоміжну ЗЛП, отриману з цілочислової задачі відкиданням умови цілочисловості. Якщо розв’язок допоміжної задачі цілочисловий, то це також розв’язок початкової (цілочислової) задачі. Якщо оптимальний розв’язок допоміжної задачі не цілочисловий, то до розв’язаної ЗЛП додають нове лінійне обмеження: воно задовольняє цілочисловим розв’язкам початкової задачі, але не задовольняє отриманому не цілочисловому розв’язку допоміжної ЗЛП. Таке додаткове лінійне обмеження визначає якусь відтинальну площину й називається правильним відтином. Нові правильні відтини додають до початкової допоміжної ЗЛП доти, доки на якомусь кроці не буде отримано розв’язок допоміжної задачі, який, очевидно, являє собою розв’язок початкової цілочислової ЗЛП.

Один із методів відтинання  метод Гоморі. Його процедура така. Нехай потрібно розв’язати задачу цілочислового програмування

                        (3.1)

де  цілочисловий вектор з невід’ємними координатами.

Разом із нею розглядають допоміжну ЗЛП

                      (3.2)

отриману з початкової задачі відкиданням умови цілочисловості змінних.

Задачу (3.2) розв’язують симплекс-методом. На останній ітерації обмеження задачі набирають вигляду

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

Позначимо як  і  відповідно цілу та дробову частини числа . Якщо число  неціле, то .

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

яке відповідає такому , що  . Правдиве таке твердження.

Теорема 3.1. Додаткове лінійне обмеження (3.3)правильний відтин для задачі цілочислового ЛП (3.1).

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

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

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

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

Процедуру зміни базису зазвичай виконують методом виключення Жордана  Гаусса. Якщо отриманий оптимальний розв’язок виявиться цілочисловим, то обчислення закінчують, а не то знову проводять правильне відтинання.

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

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

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

  1.  Метод гілок і меж

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

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

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

Якщо з кожним новим галуженням оцінка цільової функції “не погіршується”, то отриманий на певному кроці цілочисловий (дискретний) розв’язок – оптимальний розв’язок відповідної початкової задачі, а не то можливе повернення до однієї з попередніх кінцевих підмножин, що має кращу оцінку, ніж отримана на цьому етапі. Тоді процес поділу виконують для цієї підмножини.

Конкретні реалізації методу гілок і меж пов’язані з правилами поділу на підмножини (правилами галуження) та побудови оцінок (меж) значень цільової функції на них. Для задач цілочислового ЛП процедура методу гілок і меж має такий вигляд. Розглянемо частково цілочислову ЗЛП: мінімізувати

для обмежень

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

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

Вибирають  – якусь нецілу компоненту вектора . Оскільки в оптимальному розв’язку вона має бути цілою, то накладають додаткові обмеження

де   ціла частина числа .

Отже, початкова множина допустимих розв’язків розпадається на дві підмножини: одна з них містить як додаткове обмеження першу нерівність, а інша другу. Графічно це має вигляд вилучення одиничної смуги з початкової множини (рис. 3.1).

Рисунок 3.1 – Множина допустимих розв’язків

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

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

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

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



Висновки

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

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ

  1.  Партикина Т.Л., Попов И.И. Математические методы. – Петербург: ІНФА-М, 2005. – 464 с.
  2.  Таха, Хемди А. Введение в исследование методов, 7-е издание. – Москва: Издательский дом "Вильямс", 2005. – 912 с.
  3.  Леоненков А. Решение задач оптимизации в среде MS Excel –Петербург: БХВ, 2005. – 704 с.
  4.  Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. – М: Мир, 1985. – 512 с.
  5.  Акулич И.Л., Стрельчонок В.Ф. Математические методы и компьютерные технологии решения оптимизационных задач – Латвия: Рига, 2000. – 532 с.


 

А также другие работы, которые могут Вас заинтересовать

50149. Разработка для операционной системы Linux многопоточную программную имитацию работы маршрутного такси между конечными и одной промежуточной остановками 68.5 KB
  Разработать для операционной системы Linux многопоточную программную имитацию работы маршрутного такси между конечными и одной промежуточной остановками. Фиксированое число N потенциальных пассажиров случайный интервал времени пребывают где-то вне маршрута, затем появляются случайным образом на одной из остановок.
50150. Правила запису загальнорозвивальних вправ. Змiст, дозування, методичнi вказiвки 41 KB
  Стройові вправи. Загальнорозвивальні вправи. Прикладні вправи. Стройові вправи див.
50151. Нечеткая логика 67.5 KB
  Согласно заданным вариантам разработать программу на любом алгоритмическом языке, способную: А. Различать степени изменения лингвистической переменной в трех степенях – «Очень – Нормально – Слабо» Б. Изменять порог чувствительности. Улитка без ноги – медленно – быстро (о скорости)
50152. Программирование задач с использованием двумерных массивов. Ввод, вывод, упорядочивание 53 KB
  Чтобы описать массив надо сообщить компилятору: сколько в нем элементов какого типа эти элементы как они нумеруются. Пример: Вычислить суммы элементов массива по столбцам Текст программы...
50153. Визначення коефіцієнта потужності і перевірка закону Ома для кола змінного струму 84.5 KB
  Замкнути коло встановити за допомогою реостата величину струму у колі вказану на робочому місці. Виміряти потужність ватметром силу струму і напругу – відповідно амперметром та вольтметром. Прилади вимірюють діючі значення струму і напруги.
50154. Изучение сложения электрических колебаний с помощью осциллографа 416 KB
  Цель работы: Исследование различных электрических процессов при помощи осциллографа. Упрощенная блок схема осциллографа. На передней панели осциллографа применяемого в данной работе расположены экран и большое количество ручек управления: Ручки...
50155. Исследование диффузии газов 268 KB
  Колбы 1 и 2 соединены трубкой которая может перекрываться краном 6. Через краны 7 и 8 колбы подсоединены к заправочной магистрали. Краны 7 и 8 служат для подключения к магистрали соответствующей колбы. Нормальное положение крана 21 ОТКРЫТ .
50156. Хронический эпитимпанит. Характер нарушения слуха (по данным камертонального и аудиометрического исследований) 14.98 KB
  Хронический эпитимпанит - форма хронического гнойного отита, которая характеризуется воспалением антрума и аттика – надбарабанного пространства.
50157. ИЗУЧЕНИЕ СФЕРИЧЕСКИХ ЛИНЗ 169 KB
  Обеспечивающие средства: осветительная лампа оптическая скамья собирающая и рассеивающая линзы разделитель экран. Для тонких линз верна формула : 1 где d и f расстояния от предмета и его изображения до оптического центра линзы; n =nлинзы nсреды отношение абсолютного показателя преломления вещества линзы к показателю преломления окружающей среды в которой находится линза nвоздУха ≈1; R1; и R2 радиусы кривизны поверхностей ограничивающих линзу. Оптическим центром линзы называется точка проходя через которую лучи не изменяют...