Завдання до лабораторної роботи

ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ

 

Розподілити N кількість робітників Аi по N видів робіт Bj
так, щоб отримати максимальний ефект.

ВАРІАНТИ ЗАВДАНЬ

Номер завдання дорівнює послідній цифрі у номері залікової книжки студента.

 

№ 0	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5
№ 1	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5
№ 2	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5
№ 3	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5
№ 4	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5
№ 5	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5
№ 6	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5
№ 7	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5
№ 8	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5
№ 9	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5

 

МЕТОДИЧНІ ВКАЗІВКИ ДО ВИКОНАННЯ

ЛАБОРАТОРНОЇ РОБОТИ

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

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

у котрій

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

Виходячи з того, що всі y_ij можуть приймати значення 0 або 1, можна замінити вимогою, щоб всі y_ij були ненегативними цілими числами

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

де d_ij – продуктивність i- го робітника при виконанні їм j- ой роботи.

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

Нижче наведений результат розв'язання поставленої задачі за допомогою функції “Пошук рішення” табличного процесора EXCEL (рис. 1.1).

У верхній частині рис. 1.1 наведена таблиця з вихідними даними, а в нижній його частині – сам результат рішення, що призначає:

- першого працівника А₁ для виконання першої роботи В₁;

- другого працівника А₂ для виконання другої роботи В₂;

- третього працівника А₃ для виконання п'ятої роботи В₅;

- четвертого працівника А₄ для виконання третьої роботи В₃;

- п'ятого працівника А₅ для виконання четвертої роботи В_4.

Сумарна максимальна продуктивність всіх робітників при такому закріпленні за роботами становить 32 одиниці часу (див. клітку цільової функції В32).

При цьому клітки з Н11 по Н15 містять суми розташованих ліворуч п'яти кліток, а клітки із В16 по G16 - суми розташованих вище п'яти кліток і в клітках із В17 по G17 полічені продуктивності всіх робіт після їх найбільш успішного закріплення за працівниками. Зокрема для клітки В17 це опишеться наступною формулою - В3*В11+В4*В12+В5*В13+В6*В14+В7*В15.

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

 

 

Рис. 1.1. Результат розв'язання поставленої задачі за допомогою функції “Пошук рішення” табличного процесора EXCEL

На рис. 1.2 наведене діалогове вікно функції “Пошук рішення” табличного процесора EXCEL, де описані:

- цільова клітка В17;

- напрямок оптимізації - максимізація;

- діапазон змінюваних кліток - В11:G15;

- обмеження задачі, які задані у вигляді однієї нерівності (В11:G15 >= 0) і двох рівностей (C8:G8 = C16:G16 і Н3:Н7 = Н11:Н15).

Рис. 1.2. Діалогове вікно функції “Пошук рішення” табличного процесора EXCEL

ЛАБОРАТОРНА РОБОТА № 2. РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО КОМІВОЯЖЕРА

ВАРІАНТИ ЗАВДАНЬ

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

 

№1	M1	M2	M3	M4		№7	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4
№2	M1	M2	M3	M4		№8	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4
№3	M1	M2	M3	M4		№9	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4

 

№4	M1	M2	M3	M4		№10	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4
№5	M1	M2	M3	M4		№11	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4

 

 

№6	M1	M2	M3	M4		№12	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4

 

 

№13	M1	M2	M3	M4		№20	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4
№14	M1	M2	M3	M4		№21	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4
№15	M1	M2	M3	M4		№22	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4
№16	M1	M2	M3	M4		№23	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4
№17	M1	M2	M3	M4		№24	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4
№18	M1	M2	M3	M4		№25	M1	M2	M3	M4
M1					M1
M2					M2
M3					M3
M4					M4
№19	M1	M2	M3	M4
M1
M2
M3
M4

 

ЛАБОРАТОРНОЇ РОБОТИ

Розв'язання задачі

Представимо таблицю з вихідними даними у наступному вигляді матриці відстаней (МВ):

i	j	hi
	Х
		Х
			Х
				Х

 

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

Приведення матриці може провадитися по рядках і по стовпцях. Приведення МВ по рядках укладається в тім, що з елементів кожного рядка i віднімається найменший елемент цього рядка, позначуваний h_i. При цьому довжини всіх ГК зменшаться на суму віднятих з кожного рядка чисел, тобто на величину , залишаючись у теж час ненегативними. Тому величина , рівна в нашім випадку 15, дає деяку оцінку знизу довжин всіх ГК. Отримана оцінка може бути поліпшена шляхом повторного приведення МВ по стовпцях. При цьому з елементів кожного стовпця j наведеної по рядках МВ віднімається найменший елемент цього стовпця, позначуваний g_j . Сума віднятих при цьому чисел Уточнена оцінка знизу довжин ГК

Одержувана після приведення МВ дана у вигляді наступної таблиці:

i	j
	Х
		Х
			Х
				Х

Метод приведення МВ будемо застосовувати й далі для одержання оцінок знизу різних підмножин множини ГК.

Розглянемо тепер спосіб розбивки множини ГК на підмножини. Візьмемо деяку дугу (i, j). До першої підмножини віднесемо всі ГК, у які ця дуга входить. Позначимо цю підмножину [(i, j)]. До другої підмножини віднесемо всі ГК, у які дуга (i, j) не входить. Цю підмножину позначимо .

МВ для підмножини [(i, j)] легко одержати, якщо врахувати, що включення дуги (i, j) у ГК виключає можливість включення інших дуг, що коштують в i-ом рядку або j-ом стовпці. Отже, МВ для підмножини [(i, j)] виходить із первісної таблиці викреслюванням i-ого рядка й j-ого стовпця.

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

Тепер виникає питання: яку дугу покласти в основу розбивки множіни ГК на відповідні підмножини?

Якщо як дуга (i, j) взяти таку, у якої в наведеній таблиці , то для групи оцінка знизу зросте на d_i,j, оскільки заздалегідь відомо, що ця дуга ввійде в усі ГК. Вона може ще зрости, якщо таблиця при викреслюванні i- ого рядка й j- ого стовпця буде допускати подальше приведення. У той же час при заміні елемента d_i,j на нескінченність МВ залишиться наведеної, тобто оцінка знизу для не зросте. Отже, менше значення оцінки знизу буде для підмножини , що не бажано. Тому як дуга (i, j) треба брати таку, у якої в наведеної МВ величина

Але таких дуг трохи. Яку ж з них вибрати? Очевидно, ту, для якої збільшення оцінки для підмножини буде найбільшим, тому що при цьому вийде найбільша різниця в оцінках для підмножин [(i, j)] і .

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

Знову звернемося до нашого приклада. Для наведеної МВ значення виходять рівними:

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

 

i	j
	Х
		X
			Х

 

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

Нижче представлена наведена МВ зі збільшенням оцінки

i	j
	Х
		X
			Х

 

Для неї величини рівні

Найбільше збільшення оцінки для групи виходять для дуг (1, 4) і (4, 2), які також уводимо в намічуваний ГК, одержуючи ланцюжок (1, 4, 2, 3), для замикання якого не вистачає лише дуги (3, 1).

Отже, подальші перетворення не доречні й отриманий ГК є оптимальним з величиною шляху 17: 2 4 6 5

= 17.

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

у котрій

А тому що кожна вершина зустрічається в ГК лише один раз, що означає наявність у кожному рядку й у кожному стовпці матриці Y тільки однієї одиниці. Математично це запишеться у наступному виді

Виходячи з того, що всі y_ij можуть приймати значення 0 або 1, можна замінити вимогою, щоб всі y_ij були ненегативними цілими числами

Як бачимо, кожний ГК можна представити у вигляді матриці Y, елементи котрої y_ij задовольняють вищенаведеним співвідношенням. При этом длина ГК, яка дорівнює суме довжин складових його дуг, найдётся по формуле

де d_ij – величина відстані від i- го населеного пункту до j- ого.

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

Нижче наведений результат розв'язання поставленої задачі за допомогою функції “Пошук рішення” табличного процесора EXCEL (рис. 2.1).

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

- з першого міста у четверте (клітка F10);

- потім з четвертого міста у друге (клітка D13);

- потім з другого міста у третє (клітка E11);

- і в конце з третього міста у перше (клітка C12).

Сумарна мінімальна довжина оптимального ГК становить 17 одиниць відстані (див. клітку цільової функції В15).

При цьому клітки з G10 по G13 містять суми розташованих ліворуч чотирьох кліток, а клітки із С14 по F14 - суми розташованих вище чотирьох кліток і в клітках із С15 по F15 полічені мінімальні відстані дуг ГК. Зокрема для клітки С15 це опишеться наступною формулою - С3*С10+С4*С11+С5*С12+С6*С13.

Клітка із цільовою функцією В15 містить суму чотирьох кліток розташованих праворуч від її, що означає сумарну мінімальну довжину ГК.

 

 

Рис. 2.1. Результат розв'язання поставленої задачі за допомогою функції “Пошук рішення” табличного процесора EXCEL

На рис. 2.2 наведене діалогове вікно функції “Пошук рішення” табличного процесора EXCEL, де описані:

- цільова клітка В15;

- напрямок оптимізації - мінімізація;

- діапазон змінюваних кліток - C10:F13;

- обмеження задачі, які задані у вигляді однієї нерівності (C10:F1# >= 0) і двох рівностей (C7:F7 = C14:F14 і G3:G6 = G10:G13).

Рис. 2.2. Діалогове вікно функції “Пошук рішення” табличного процесора EXCEL

ТРАНСПОРТНИХ ПЕРЕВЕЗЕНЬ

ВАРІАНТИ ЗАВДАНЬ

 

Варіант завдання вибирається наступним чином:

- відстані l_ij - по останній цифрі залікової книжки (табл. 3.1);

- значення a_i та b_j - по передостанній цифрі залікової книжки (табл. 3.2).

- для всіх варіантів прийняти m = 3; n = 5.

Таблиця 3.1

 

№

l 11

l 12

l 13

l 14

l 15

l 21

l 22

l 23

l 24

l 25

l 31

l 32

l 33

l 34

l 35

 

Таблиця 3.2

 

№	а1	а2	а3	b1	b2	b3	b4	b5
0,3,6,9 1,4,7 2,5,8,

ЛАБОРАТОРНОЇ РОБІТИ

 

 

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

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

Таблиця 3.3

Складання опорного плану перевезень

ВАРІАНТИ ЗАВДАНЬ

 

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

 

 

ЛАБОРАТОРНОЇ РОБОТИ

На рис. 4.1 зображена мережа з 7 вершинами і 11 ланками. Поруч із відповідною вершиною у дужках числом зі знаком плюс показаний обсяг виробництва, а обсяг споживання, відповідно, числом зі знаком мінус. Вартість перевезення вантажу вписана в кожну дугу. Також на рис. 4.1 подані розподіли вантажопотоків і потенціалів.

Рис. 4.1. Приклад ТМ без Рис. 4.2. Приклад ТМ з

обмежень на пропускні здатності обмеженнями на пропускні здатності

Перший спосіб – Ордена А. показаний у табл. 4.1. Кожній вершині мережі виділяється рядок і стовпець. Таким чином у нашому випадку, таблиця складається із семи рядків і семи стовпців. Вона завжди повинна бути квадратною. У клітинках головної діагоналі таблиці 4.1, 2.2 і т. д. вартість перевезення дорівнює 0, тому що вихідних і одночасно вхідних дуг до тієї самої вершини бути не може.

Для вершин, з'єднаних між собою ланкою, у клітинках таблиці на перетинанні відповідних рядків і стовпців проставлена вартість транспортування цією ланкою. Інші клітинки заблоковані більшими, порівняно з вартостями перевезень, числами (у табл. 4.1 це незаповнені клітинки).

Для зручності розрахунку до значення обсягу виробництва (споживання) до кожної вершини додається яке-небудь позитивне число. У табл. 4.1 це число 9. Таким чином, обсяг виробництва у вершині 1 буде 7+9=16, у транзитній вершині 2 – 9, так само як і обсяг споживання і т. д. Потім ТЗ розв'язують будь-яким відомим методом. У табл. 4.1 показаний остаточний результат рішення задачі – значення оптимального плану перевезень вантажу виділені курсивом, а на рис. 4.3 – результат розв'язання за допомогою Excel-таблиці.

Таблиця 4.1

Методом Ордена

			2		1		4
			2
			6
			6

Рис. 4.3. Розв'язання мережевої ТЗ без обмежень на пропускні здатності за допомогою Excel-таблиці

Другий спосіб – спосіб Вагнера Ш.М. Він зручніший для мереж з обмеженнями пропускної здатності. Така мережа зображена на рис. 4.2, де представлений також і оптимальний план перевезень. У табл. 4.2 показано приведення цієї мережі до матричної форми.

Таблиця 4.2

ВАРІАНТИ ЗАВДАНЬ

 

Додати до структури транспортної мережі (рис. 5.1) транспортний вузол з наведеної нижче карти.

ЛАБОРАТОРНОЇ РОБОТИ

Класичними задачами на графах є задачі про побудову найкоротших шляхів та їх сукупностей у вигляді відповідних дерев чи контурів. Однією з таких задач є пошук найкоротшого шляху між двома заданими вузлами: s (джерелом) і t (стоком). Розглянемо розв'язання цієї задачі на конкретному прикладі, який узятий з електронного атласу України:

Задана сітка у вигляді змішаного зваженого графа з 9 вузлами і 13 дугами, початкові дані мають наступний вигляд у Excel -таблиці(див. рис. 5.1).

Треба визначити найкоротший шлях від вузла –джерела міста Київа до вузла-стоку міста Суми в следующей математической постановке:

- знайти вектор Х = (х₁, х₂, … х₁₃), де елемент х_i = 1, якщо відповідна дуга належить найкоротшому шляху, і 0 у противному випадку; і – порядковий номер дуги (і = 1, 2,..., 13);

- щоб загальна довжина шляху , де d_i – довжина і -ої дуги;

- за умови збереження балансу потоків для кожного j -го вузла (j = 1, 2,..., 9): F_вих (x_i) - F_вх (x_i) = 0, де F_вих (x_i), F_вх (x_i) – сума потоків на вході та виході кожного j -го вузла; для вузла-джерела F_вих (x_i) - F_вх (x_i) = 1; для вузла –стока F_вих (x_i) - F_вх (x_i) = -1;

- при всіх x_i ≥ 0.

Рис. 5.1. Топологія сітьової транспортної задачі

Для цього в Excel -таблиці (далі просто таблиці) для всіх дуг визначити діапазон для невідомих Х (Дуга) і обчислити значення цільової функції за формулою = СУММПРОИЗВ(Дуга; Довжина), а для всіх вузлів обчислити суми вхідних (Вхід) і вихідних (Вихід) потоків, їх алгебраїчну суму (Вихід-Вхід), задати колонку правих частин обмежень (Обмеження).

Для обчислення потоку у вузлах використовується функція обчислення суми величин, координати яких задовольняють визначеній умові (тобто, якщо певні величини належать відповідній множині). В Excel таку процедуру виконує функція СУММЕСЛИ(аргументи). Наприклад, сума вхідних потоків вузла визначається за формулою = СУММЕСЛИ(всі кінці дуг; вузол; потоки), тобто, підсумовуються потоки по тих дугах, кінці яких співпадають з поточним вузлом. За формулою = СУММЕСЛИ(всі початки дуг; вузол; потоки) підсумовуються вихідні потоки.

На рис. 5.2 показане розв'язання поставленої задачи за допомогою команди Пошук рішення в середовищі Excel - програми, з котрого видно, що ветор Х = (0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1), а це, у свою чергу означає, що найкоротший шлях з міста Києва в місто Суми пройде послідовно через міста Березань, Пирятин і Гадач і складе 378 км.

Рис. 5.2. Розв'язання задачі про найкоротший шлях на мережі

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

Результат рішения цієї задачі вказує величину максимального загального потоку, який може пропустити вся мережа, потоки та їх напрямки по окремих дугах. Розглянемо розв’язання задачі про максимальний потік у мережі на конкретному прикладі, який також узятий з електронного атласу України у вигляді зваженого графа з 6 вузлами і 11 дугами (топологія розглянутого графа збігається з топологією графа на рис. 5.1, де максимальний потік знаходився методом дерев), початкові дані мають наступний вигляд у Excel -таблиці (див. рис. 5.3).

Рис. 5.3. Розв'язання задачі про максимальний потік у сітці

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