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

Зміст

Вступ

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

. Необхідні поняття теорії графів

. Задача про максимальний потік

.1 Постановка задачі

.2 Алгоритм Форда знаходження максимального потоку

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

.1 Зведення задачі до задачі про максимальний потік

.2 Модифікація алгоритму Форда розв’язання задачі максимізації кількості призначень у задачах розподілу

. Результати числового експерименту

Висновки

Список використаної літератури

Додатки

Текст програми

Інструкція користувача       

Вступ

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

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

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

У даній роботі розглядається задача максимізації кількості призначень у задачі розподілу. Дана задача також зводиться до задачі про максимальний потік і її розв’язок знаходиться з використанням модифікації алгоритму Форда.

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

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

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

2. Необхідні поняття теорії графів

Теорія графів виникла понад 240 років тому. Основи її розробив математик Леонард Ейлер, розв'язавши в 1736 р. відому задачу про 7 мостів. Проте лише протягом останніх часів ця теорія була докладно розроблена й почала широко використовуватися у фізиці, хімії, біології, соціології, економіці, картографіі тощо. Отримання дальших суттєвих результатів у цій галузі датують серединою ХIХ століття. Однак початок проведення активних систематичних досліджень та становлення теорії графів як окремішного авторитетного розділу сучасної математики відбулося ще майже 100 років по тому, тобто в середині ХХ століття. Саме з цього часу граф стає однією з найпоширеніших і найпопулярніших математичних моделей у багатьох сферах науки і техніки. Картинка у вигляді набору точок на площині та ліній, проведених між деякими з них, стала зручною і наочною формою зображення найрізноманітніших об’єктів, процесів та явищ.

Великою мірою це пов’язано з виникненням, бурхливим розвитком та поширенням електронних обчислювальних машин і, як наслідок, значним зростанням ролі задач дискретного характеру. Математика від "обслуговування" переважно фізики переходить до проникнення своїх методів у інші сфери людської діяльності. Із суто формальної точки зору граф можна розглядати як один з різновидів алгебраїчної системи (а саме, як модель), а отже, і всю теорію графів - як розділ сучасної алгебри. Справді, результати та методи алгебри широко використовуються в теорії графів. Однак за останні півстоліття активного інтенсивного та екстенсивного розвитку теорія графів виробила свою достатньо специфічну власну проблематику і методологію. На сьогодні теорія графів є однією зі складових математичного апарату кібернетики, важливим розділом дискретної математики. Тому теорія графів включається до навчальних програм університетів і технічних вузів як окрема дисципліна, або як розділ курсу "Дискретна математика".

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

Розглянемо на прикладі, що таке граф:

Припустимо, що ви запросили до себе у гості кількох осіб. Назвемо їх А, В, С, D, F. Деякі з них є вашими родичами, інші - співробітниками, а з деякими ви познайомилися під час літнього відпочинку і т.д.

Тому деякі з цих осіб не знайомі одна з одною. Намагаючись пригадати, хто з них з ким знайомий, ви , можливо, зобразите на папері 6 точок A, B, C, D, E, сполучивши їх лініями, якщо відповідні особи вже знайомі між собою(Рис.1)

Рис.1

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

Отже, на Рис.1 точки A, B, C, D, E, F є вершинами графа, а, наприклад, відрізки АС, CD, CE, CF - його ребра.

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

Один і той самий граф може виглядати по різному :

Рис. 2

Основні означення теорії графів

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

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

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

Взагалі, будь-який замкнений ланцюг називається циклом.

Граф називається зв'язним, якщо будь-які 2 з його вершин зв'язані якимось ланцюгом.( Рис. 3)

Рис.3

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

Відповідно, граф, в якого не побудовані усі можливі ребра, називається неповним.( Рис.4)

Рис.4

Зауважимо, що коли повний граф має n вершин, то він матиме n(n - 1)/2 ребер.

Порожнім (нульовим) називається граф без ребер(тобто, складається з ізольованих вершин).(Рис. 5)

Рис.5

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

Степінь кожної з n вершин повного графа дорівнює n - 1; степінь кожної вершини нульового графа дорівнює 0.

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

Якщо кількість ребер графа позначити через Р, а вершини буквами А1 , А2, …Аn, то сума

Р = Р(А1) + Р(А2) + …+ Р(Аn) (2.1)

дорівнюватиме кількості всіх ребер цього графа.

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

Р =½ (Р(А1) + Р(А2) + …+ Р(Аn))

Або

Р = Р(А1) + Р(А2) + …+ Р(Аn) (2.2)

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

Позначимо через Вi кількість тих вершин, степінь яких дорівнює i. Наприклад, В1 - кількість вершин, степінь яких = 1, В2 - кількість вершин, степінь яких = 2.

Користуючись такими позначеннями рівність (2.2) можна подати в такому вигляді:

Р = 1* В1 + 2*В2 + 3*В3 +…+ n *Bn              (2.3)

Машинне представлення графів

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

В теорії графів класичним способом представлення графа служить матриця інцидентності. Матриця інцидентності - це матриця А з n рядками, що відповідають вершинам, і m стовпцями, що відповідають ребрам. Для орієнтованого графу стовпець, що відповідає дузі , містить -1 в рядку, що відповідає х, 1 в рядку, що відповідає вершині у, і нулі у всіх інших рядках.

На рис. 6 зображений орієнтований граф і його матриця інцидентності.

Рис. 6

З алгоритмічною точки зору матриця інциденцій є, можливо, найбільш невдалим способом представлення графа. По-перше, він потребує mn комірок пам’яті, причому більшість цих комірок зайняті нулями. Незручний також і доступ до інформації. Відповідь на елементарне питання типу “ чи існує ребро {x,y}?”, “ до яких вершин ведуть ребра із x?” потребують в гіршому випадку перебору усіх стовпців матриці, а відповідно, m кроків.

Кращим способом представлення графа є матриця суміжності, що визначається як матриця B[] розмірності n x n, де  1, якщо існує ребро, що йде із вершини х в вершину у, і  0 - в протилежному випадку.

Орієнтований граф і його матриця суміжності зображені на рис. 7.

Рис. 7

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

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

Список інцидентності, що відповідає графу на рис. 6. , зображений на рис. 8.

Рис. 8

3. Задача про максимальний потік

3.1 Постановка задачі

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

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

                                                   (3.1)

                                  (3.2)

.                               (3.3)

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

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

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

.

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

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

3.2 Алгоритм Форда знаходження максимального потоку

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

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

Основний етап. Основний етап, який повторюється, складається з трьох дій.

. Знаходимо по таблиці шлях з  в  з пропускною здатністю більшою за нуль. Для цього стовпчик, який відповідає джерелу Е0 помічаємо символом * . Шукаємо в  -му рядку елементи , і стовпці в яких вони знаходяться, помічаємо зверху номером рядка, який розглядаємо (тобто цифрою 0). В результаті будуть виділені всі дуги () з додатною пропускною здатністю. Ці дуги можуть бути першими дугами шляху з  в .

Далі розглянемо ті рядки, номери яких співпадають з номерами помічених стовпців. В кожному такому рядку, наприклад -овому, шукаємо елементи > 0, які знаходяться в непомічених стовпцях, і помічаємо ці стовпці номером розглядуваного рядка. Таким чином, ми виділяємо ті дуги, які можуть бути другими дугами шляху з Е0 в Е. Продовжуємо аналогічний перегляд рядків, номера яких співпадають з номером помічених стовпців, до тих пір, поки:

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

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

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

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

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

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

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

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

4. Задача максимізації кількості призначень у задачах розподілу як задача про максимальний потік

4.1 Зведення задачі до задачі про максимальний потік

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

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

4.2 Модифікація алгоритму Форда розв’язання задачі максимізації кількості призначень у задачах розподілу

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

5. Результати числового експерименту

Приклад 1. На підприємстві є 5 вакансій і 4 працівники. Можливість прийняття працівників на вакансії подано таблицею

На основі цих даних побудуємо граф

На основі даного графу приходимо задачі про максимальний потік. Знайдемо результат з використанням програмної реалізації модифікованого алгоритму Форда. Приведемо покроковий процес розв’язання

Приклад 2. На підприємстві є 8 вакансій і 6 працівників. Можливість прийняття працівників на вакансії подано таблицею

Знайдемо розв’язок з використанням програмної реалізації модифікованого алгоритму Форда

теорія граф числовий максимізація

Приклад 3. На підприємстві є 6 вакансій і 6 працівників. Можливість прийняття працівників на вакансії подано таблицею

Знайдемо розв’язок з використанням програмної реалізації модифікованого алгоритму Форда

Висновки

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

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

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

Список використаної літератури

1.       Глебена МЛ. Кузка O.I. Задача про максимальний потік (методичні вказівки).- Ужгород 2007.

.         Навчальний посібник для студентів факультету кібернетики «Теорія графів» - 1998.

3.      Уилсон Р. Введение в теорию графов.- М., 1977.

.        Оре О. Теория графов.- М., 1980.

.        Головина Л.И. Графы и их применения . Математика в школе, 1965, №3.

.        Нагибин Ф.Ф. Применение графов для решения логических задач. Математика в школе , 1964, № 3.

.        Шедивы Я. Решение логических задач при помощи графов.- Математика в школе, 1967, № 6.

8.       Скляр І.В. Теорія графів у школі: задачі: посібник /Ірина Скляр. - К.:Шкільний світ, 2010. - 128с.

Додатки

Текст програми

program Project1;,in 'Unit1.pas' {Form1};

{$R *.res}.Initialize;.CreateForm(TForm1, Form1);.Run;.Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, Grids, StdCtrls, Spin, Menus;= class(TForm): TMainMenu;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TLabel;: TSpinEdit;: TStringGrid;: TLabel;: TSpinEdit;: TOpenDialog;: TSaveDialog;: TEdit;: TLabel;: TMemo;: TLabel;: TStringGrid;: TCheckBox;FormCreate(Sender: TObject);robSpinEditChange(Sender: TObject);misSpinEditChange(Sender: TObject);N3Click(Sender: TObject);N2Click(Sender: TObject);N6Click(Sender: TObject);

{ Private declarations }

{ Public declarations };=array[-1..100,-1..100] of integer;=^Vet;=record:integer;:PVet;;: TForm1;,FMatr,Matr:TMatr;,m,nr,nm:integer;,QLast:Pvet;DateUtils;

{$R *.dfm}showNums;i:integer;Form1 doi:=1 to Form1.misSpinEdit.Value do.Cells[0,i]:='Місце'+inttostr(i);;i:=1 to Form1.robSpinEdit.Value do.Cells[i,0]:='Роб.'+inttostr(i);;;;TForm1.FormCreate(Sender: TObject);;;TForm1.robSpinEditChange(Sender: TObject);.ColCount:=robSpinEdit.Value+1;;;TForm1.misSpinEditChange(Sender: TObject);.RowCount:=misSpinEdit.Value+1;;;TForm1.N3Click(Sender: TObject);f:TextFile;,j:integer;SaveDialog1.Execute then(f,SaveDialog1.FileName);(f);(f,misSpinEdit.Value,' ',robSpinEdit.Value);i:=1 to misSpinEdit.Value doj:=1 to robSpinEdit.Value do(f,daniStringGrid.Cells[j,i]);;;(f);;;TForm1.N2Click(Sender: TObject);f:TextFile;,nm,i,j:integer;:string;OpenDialog1.Execute then(f,OpenDialog1.FileName);(f);(f,nm,nr);.Value:=nr;.Value:=nm;i:=1 to nm doj:=1 to nr do(f,s);.Cells[j,i]:=s;;;(f);;;getData;i,j,l:integer;:real;Form1 do:=robSpinEdit.Value;:=misSpinEdit.Value;i:=1 to nm doj:=1 to nr do(daniStringGrid.Cells[j,i],dani[i,j],l);l<>0 then[i,j]:=0;;;;;createFirstMatr;i,j:integer;:=nr+nm+1;i:=0 to n doj:=0 to n do[i,j]:=0;;;

//0-rowj:=1 to nm do FMatr[0,j]:=1;

//n-coli:=nm+1 to nm+nr do FMatr[i,n]:=1;

//danii:=1 to nm doj:=nm+1 to nm+nr do[i,j]:=Dani[i,j-nm];;;;

//--------------------------------------------------

{----------------- Quee ---------------------}QPush(inf:integer);cur:PVet;(cur);^.inf:=inf;^.next:=nil;QFirst=nil then:=cur; QLast:=cur;^.next:=cur;:=cur;;;QPop(var inf:integer):boolean;cur:PVet;QFirst=nil then:=false:=QFirst^.inf;:=QFirst;:=QFirst^.next;(cur);QFirst=nil then QLast:=nil;:=true;;;QErase;cur:Pvet;QFirst<> nil do:=QFirst;:=QFirst^.next;(cur);;:=nil;;

{----------------- /Quee ---------------------}ShowMaatr(M:TMatr; n:integer; s:string);i,j:integer;Form1.CheckBox1.Checked thenForm1 do.ColCount:=n+1;.RowCount:=n+2;i:=-1 to n doj:=0 to n do.Cells[j,i+1]:=inttostr(M[i,j]);;;;(s);;;

{------------------------ Max potik ---------}baseEtap:boolean;

//-------------------------setMark:integer;k,j:integer;:=nil; QLast:=nil;j:=0 to n do Matr[-1,j]:=-1;(0);QPop(k) doj:=1 to n do(Matr[-1,j]=-1)and(Matr[k,j]>0) then[-1,j]:=k;(j);j=n then:=j;;;;;;;:=-1;;

//-------------------------Etap3(k:integer);kn:integer;:=n;[k,kn]:=0;[kn,k]:=1;:=k;:=Matr[-1,k];kn=0;;k:integer;:=setMark;(Matr,n,'setMark');k<>-1 then(k);(Matr,n, 'etap3');;k=-1;MaxPriznach:integer;i,j,kPrizn:integer;getRob(i:integer):integer;j:integer;j:=nm+1 to nm+nr doFMatr[i,j]>0 then:=j-nm;;;;:=-1;;:=FMatr;;i:=0 to n doj:=0 to n do[i,j]:=FMatr[i,j]-Matr[i,j];;

//------------:=0;j:=0 to n do kPrizn:=kPrizn+FMatr[0,j];i:=1 to nm do FMatr[i,-1]:=getRob(i);:=kPrizn;(FMatr,n,'Rez');;

{------------------------ /Max potik ---------}TForm1.N6Click(Sender: TObject);i:integer;;;(FMatr,n,'First');.Text:=inttostr(MaxPriznach);.Clear;i:=1 to nm doFMatr[i,-1]>0 then.Lines.Add('(Місце - '+inttostr(i)+') -> (Робочий -'+inttostr(FMatr[i,-1])+')');;;TForm1.N7Click(Sender: TObject);;.

Інструкція користувача

Головна форма програми має зручний і зрозумілий інтерфейс

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

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

З використанням елемента «Виводити проміжкові результати» користувач має можливість проглядати покроково весь процес розв’язання.