Ім'я файлу: Застосування пофарбування графів до практичних задач в економіці
Розширення: doc
Розмір: 133кб.
Дата: 07.06.2021
скачати
Пов'язані файли:
Практические работы.pdf
lr-6_i.doc
Звіт – копія.docx

Застосування пофарбування графів до практичних задач в економіці
Різноманітні задачі логістики також можна сформулювати як задачу пофарбування графів на мові 0-1 програмування. Розглянемо загальну задачу логістики (ЗЗЛ). Нехай є N предметів, які потрібно розмістити по ящикам. Нехай кожен предмет співвідноситься деякій вершині графа G. Кожен раз, коли два предмета та не можуть бути розміщені в одному ящику, у граф G вводиться ребро . Якщо ящики мають необмежену місткість, таку, що в них можна покласти необмежену кількість предметів, то задача знаходження найменшої кількості ящиків для розміщення предметів еквівалентна задачі знаходження хроматичного числа графа G, яке може бути оцінене математичними виразами (1.1 – 1.4).

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


(1.13)

(1.14)

Тут q– це є верхня оцінка хроматичного числа , знайдена за виразами (1.5 – 1.7).

Іншим випадком є задача логістики розміщення предметів по ящикам із встановленими вартостями (ЗЛВВ). Нехай j-ий ящик має місткість та вартість . Нехай також предметам (вершинам графа) ставляться у відповідність ваги . Потрібно так розмістити предмети по ящикам, щоб:

  • виконувалися обмеження, які накладаються графом G(1.9 – 1.11);

  • виконувалися обмеження на місткість ящиків (1.14);

  • найменша вартість ящиків була мінімальною.

Тоді на мові 0-1 програмування дана задача буде мати вигляд:


(1.15)






(1.16)






(1.17)






(1.18)









У такому формулюванні задачі змінна приймає значення “1”, якщо в ящик j можна помістити предмет, і дорівнює “0” у протилежному разі. Обмеження (1.17) гарантує, що жоден із ящиків не перевантажується, а обмеження (1.18) гарантує виконання умови: якщо , тобто j-ий ящик порожній, то всі також дорівнюють нулю.

Потрібно відмітити, що чим більш загальною є задача, тим менш важливим є її аспект пофарбованості. Наприклад, в розглянутій логістичній задачі ЗЗЛ можна виділити дві підзадачі: задачу про пофарбування графа, яка відповідає обмеженням (1.9 – 1.10) та суто логістичну задачу, яка визначається обмеженням (1.17). Обмеження типу (1.11, 1.16, 1.18) носять структурний характер. Через ці два взаємоповязані аспекти загальна задача пофарбування є значно складнішою для розвязання, ніж “чиста” задача пофарбування.

У “чистому” вигляді задача пофарбування графів (ЧЗПГ), відповідно до означення 1 може бути сформульована наступним чином:


(1.19)






(1.20)






(1.21)






(1.22)









Тобто, якщо задано граф , що утворений набором вершин V та ребер E, то мета розвязування даної задачі полягає у знаходженні мінімальної кількості кольорів, згідно функціонала (1.19), такої, щоб будь-які суміжні вершини та були пофарбовані у різні кольори. Розвязком даної задачі є матриця , яка описує оптимальне розміщення кольорів у графі.

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


(1.23)

(1.24)

де L – будь-яке велике додатне число, більше ніж N. Умова (1.23) гарантує пофарбування вершин лише в один колір. Якщо вершина пофарбована у колір j, тобто , то перший член в (1.23) дорівнює “0”. Тоді і другий член повинен бути рівним “0”, щоб виконувалась нерівність, оскільки та невідємні числа. Таким чином, умова (1.24) забезпечує допустимість пофарбування, тобто якщо вершина пофарбована у колір j, то немає суміжної з вершини одного кольору. Якщо вершина пофарбована в колір, який відрізняється від j( ), то перший член в (1.23) дорівнює L. Оскільки другий член в (1.24) не може досягти значення L, то яке б не було число вершин , суміжних з вершиною , нерівність (1.24) знову виконується. Необхідно відмітити, що якщо вершини і суміжні із , а також суміжні між собою, то умова (1.24), записана для вершини , не буде забороняти пофарбувати і в один і той самий колір j. Проте, записуючи умову (1.24) для або , ми забезпечуємо пофарбування цих вершин у різні кольори.

Якщо допустити, що кожному кольору j співвідноситься штраф , вибраний таким чином, що


(1.25)

Тоді задача пофарбування вершин графа (ЗПГ) із використанням найменшої кількості кольорів може бути сформульована наступним чином:


(1.26)

(1.27)

(1.28)

Мінімізація виразу (1.26) забезпечує вірність наступної умови: колір j+1 не буде використовуватися у пофарбуванні вершин, якщо кількість кольорів від 1 до j є достатньою для допустимого пофарбування. Матриця пофарбованості графа , яка є розвязком наведеної вище задачі лінійного 0-1 програмування, визначає оптимальне пофарбування, а кількість кольорів, використаних у пофарбуванні – хроматичне число графа .

Берж замість умови (1.28) запропонував наступну:


(1.29)

де - матриця інциденцій. Тобто , якщо вершина інцидентна ребру , і у протилежному разі. Умова (1.29) відображає той факт, що не більше ніж одна із двох кінцевих вершин будь-якого ребра може бути пофарбована у колір j.

Ця умова є більш природною, ніж (1.28), але для побудови системи алгебраїчних рівнянь потрібно обмежень, тоді як для умови (1.28) лише обмежень. Оскільки число ребер звязаного графа звичайно більше числа його вершин n, то умова (1.29) з точки зору обчислень є більш громіздкою.

Розглянутий спосіб формулювання задачі пофарбованості графів на мові 0-1 програмування має багато переваг, одна з яких полягає у зведенні різноманітних задач до системи лінійних алгебраїчних рівнянь. Відповідно, такі системи можна легко розвязувати за допомогою будь-якого лінійного алгоритму, наприклад симплекс методу. У свою чергу такий підхід є переважним для дискретних систем. Звичайно, поряд із перевагами постають і недоліки. Одним із головних недоліків є введення великої кількості змінних і обмежень для представлення простих розвязків.
скачати

© Усі права захищені
написати до нас