Методи розв’язування задач про призначення

Размещено на http://www.allbest.ru/

Методи розв'язування задач про призначення



Реферат

Курсова робота: загальний обсяг роботи - 37 сторінок, 5 рисунків, 36 таблиць, 1 додаток на 1 сторінці, 19 джерел літератури.

Об'єктом дослідження є процес знаходження розв'язків задачі про призначення.

Предметом дослідження є методи розв'язування задач про призначення.

Мета даної роботи - проаналізувати методи розв'язання задачі про призначення та обґрунтувати їх практичну реалізацію.

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

Значимість даної роботи полягає в дослідженні основних методів розв'язування задач про призначення.

В даній роботі проаналізовано угорський метод та метод Мака розв'язування задач про призначення, а також реалізовано задачу про призначення в середовищі MS Excel.

БУЛЕВЕ ПРОГРАМУВАННЯ, Задача про призначення, метод Мака, Оптимізація, угорський метод.



Зміст

Вступ

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

1.1 Економічна інтерпретаціязадачі про призначення

1.2 Загальна постановка задачі про призначення

Розділ 2. Методи розв'язування задачі про призначення

2.1 Угорський метод розв'язування задачі про призначення

2.2 Модернізований угорський метод

2.3 Метод Мака

Розділ 3. Розв'язування задачі про призначення

3.1 Розв'язування задачі угорським методом

3.2 Розв'язування задачі методом Мака

3.3 Розв'язування задачі про призначення в середовищі MSExcel

Висновки

Список використаних джерел

Додаток



Вступ

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

Мета даної роботи - проаналізувати методи розв'язання задачі про призначення та обґрунтувати їх практичну реалізацію.

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

- Визначення ідеї методів розв'язування задачі про призначення;

- Побудова економіко-математичної моделі задачі про призначення;

- Дослідження напрямів практичного застосування задач про призначення;

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

Об'єктом дослідження є процес знаходження розв'язків задачі про призначення.

Предметом дослідження є методи розв'язування задач про призначення.

У роботі використано такі методи дослідження:

1) економіко-математичного моделювання - при побудові моделі задачі про призначення,

2) метод порівняння - порівняння задачі про призначення та транспортної задачі, а також методів розв'язування задач про призначення,

3) метод системного аналізу - усі елементи в системі вважаються взаємопов'язаними та сприймаються цілісно.



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

1.1 Економічна інтерпретаціязадачі про призначення

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

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

Уперше задача про призначення булла розглянута в геометричній формі Гаспаром Монжем у 1784 році. Проте на початку ХХ століття булла встановлена некоректність розв'язку Монжа. Наступні кроки в розв'язанні задачі про призначення зроблені Кенігом і Егерварі в першій третині XX століття. Кеніг і Егерварі розглядали цю задачу як задачу пошуку досконалого паросполучення мінімальної ваги у зваженому дводольному графі. Їх роботи стали основою для угорського методу, розробленого Куном у 50-х роках минулого століття. У 1947 році Данциг запропонував симплекс-метод для розв'язання загальної задачі лінійного програмування, до якої легко зводиться задача про призначення. Задача про призначення, поставлена Данцигом і Фалкерсоном, може також розглядатися як задача про максимальний потік мінімальної вартості. У 1961 році Басакер і Гоуен опублікували алгоритм для її розв'язання. Цей алгоритм для загальної задачі, як і алгоритм симплекс-методу, має експоненціальну складність, а для задачі про призначення ? поліноміальну. Поліноміальний алгоритм для задачі про максимальний потік мінімальної вартості, заснований на алгоритмі Клейна, що був опублікований у 1967 році, вперше запропонований у 1987 році Гольбергом і Тар'яном[10].

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

Таблиця 1.1

Ресурси	Об'єкти	Критерії ефективності
Працівники Грузові машини Верстати Екіпажи Комівояжер	Робочі місця Маршрути Ділянки Рейси Міста	Час Витрати Кількість переробленої продукції Час простою Товарообіг

1.2 Загальна постановка задачі про призначення

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

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

Вихідні параметри моделі задачі про призначення:

1. n - кількість ресурсів, m - кількість робіт.

2. ai=1 - одинична кількість ресурсу Ai (i=1,2,…,n), наприклад: один працівник;один транспортний засіб; одна наукова тема і т.д.

3. bj=1 - одинична кількість роботи Bj (j=1,2,…,m),наприклад: одна посада; один маршрут; одна лабораторія.

4. cij - характеристика якості виконання роботи Bj за допомогою ресурсу Ai. Наприклад, компетентність i-го працівника при роботі на j-й посаді; час, за який i-ий транспортний засіб перевезе вантаж по j-му маршруту; ступінь кваліфікації i-ої лабораторії при роботі над j-ою науковою темою.

Шукані параметри:

1. xij - факт призначення або непризначення ресурсуAi на роботуBj :

xij=

2. L(x) - загальна (сумарна) характеристика якості розподілу ресурсів по роботах[2, с. 95]

Математична модель задачі про призначення:

= (1.1)

(1.2) - (1.4) - система обмежень. (1.2) - обмеження на виконання однієї роботи не більше ніж одним працівником; (1.3) - обмеження на виконання одним працівником не більше однієї роботи; (1.4) - обмеження на булевість змінних [17].

У деяких випадках, наприклад, коли cij - це компетентність, досвід роботи або кваліфікація працівників, умова задачі може потребувати максимізації цільової функції, на відміну від (1.1). У цьому випадку цільову функцію L(x) заміняють на L1(x)=-L(x) і розв'язують задачу з цільовою функцією L1(x)>min, що рівносильно розв'язанню задачі з цільовою функцією L(x)>max[3, с.227].

У таблиці 1.2 представлено загальний вигляд транспортної матриці задачі про призначення[7,с 51].



Таблиця 1.2

Ресурси, Ai	Роботи, Bj	Кількість ресурсів
	B1	B2	…	Bm
A1	c11	c12	…	c1m	1
A2	c21	c22	…	c2m	1
…	…	…	…	…	…
An	cn1	cn2	…	cnm	1
Кількістьробіт	1	1	…	1	=

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

n = m,

.

При цьому умова xij?{0,1} означає виконання вимоги цілочисельності змінних xij. Це пов'язано з тим, що потужності всіх джерел і стоків дорівнюють одиниці, звідки випливає, що в припустимому цілочисельному рішенні значеннями змінних можуть бути тільки 0 та 1. Як окремий випадок класичної транспортної задачі, задачу про призначення можна розглядати як задачу лінійного програмування (ЗЛП). Тому в даномувипадку використовують термінологію і теоретичні результати лінійного програмування. У задачі про призначення змінні xij, можуть приймати значення 0 або 1.

При цьому, відповідно до (1.2) - (1.4), в будь-якому припустимому рішенні лише n змінних можуть приймати значення 1. Отже, будь-яке припустиме базисне рішення задачі про призначення буде виродженим, так що алгоритм розв'язання транспортної задачі застосувати можливо, але неефективно.[1. с. 46-47]

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

Квадратні матриці С=|||| та D=|||| ( i , j =1,..., n ) будемо називати еквівалентними, якщо елементи однієї з них одержуються з елементів другої шляхом додавання певних чисел до кожного рядка і кожного стовпця. Ці числа можуть бути різними для різних рядків та стовпців. Отже, матриці С та D еквівалентні, якщо, наприклад,

(1.5)

Теорема 1. Оптимальні розв'язки задач про оптимальні призначення з еквівалентними матрицями витрат співпадають.

Доведення. Нехай матриця С еквівалентна матриці (1, j1), (2, j2),...,( n , jn) -- оптимальні призначення у задачі з матрицею витрат С, тобто i-й виконавець призначається на виконання j-ї роботи, (і, j=1,..., n ). Припустимо, що це призначення не є оптимальним у задачі з матрицею витрат D .

Нехай ( 1 , j1'), (2, j2'),...,( n , jn') -- оптимальні призначення у задачі з матрицею витрат D , причому

В силу (1.5) звідсимаємо

Або

Проте

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

що протирічить тому, що для задачі з матрицею витрат С призначення ( i , ji ), i= 1,..., n , є оптимальним.

Оскільки властивість еквівалентності матриць є взаємною, то оптимальні призначення у задачі з матрицею витрат С співпадають з оптимальними призначеннями у задачі з матрицею витрат D . Доведення завершене.

Доведена теорема дозволяє, якщо це необхідно, переходити від даної задачі про оптимальні призначення до задачі з еквівалентною матрицею витрат. Тому вихідну задачу завжди можна звести до задачі про оптимальні призначення з матрицею витрат, яка має лише невід'ємні елементи. Оскільки найменше можливе значення суми n елементів такої матриці, очевидно, дорівнює нулю, то наша задача зводиться до вибору у матриці витрат, або еквівалентнійїй, n нульових елементів, по одному в кожному рядку і кожному стовпці. В цьому, власне, полягає неформальний зміст алгоритму угорського методу, що викладається нижче, де матриці, еквівалентні вихідній матриці витрат С, називаються просто матрицями витрат. [11, с. 104-105]

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

Cпецифіка задачі про призначення дозволяє розв'язати її більш простими методами, ніж узагальненими методами для задач лінійного програмування. Одними з таких методів є угорський метод та метод Мака[6].



Розділ 2. Методи розв'язування задачі про призначення

2.1 Угорський метод розв'язування задачі про призначення

Сутність угорського методу

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

Метод був вперше запроваджений в 1955 році Гарольдом Куном у його статті "Угорський метод для задачі про призначення" на основі праць угорських математиків Денеша Кьоніга та Ейгена Егерварі (що і дало назву методу). В 1957 році Джеймс Манкрес переглянув алгоритм і дійшов висновку, що він є (строго) поліномним. З того часу алгоритм більш відомий як алгоритм Куна-Манкреса або задача про призначення Макреса. Лестер Рандольф Форд молодший та Делберт Рей Фулкерсон розширили метод до загальних транспортних задач. У 2006 році було відкрито, що Карл Густав Якобі розв'язав задачу про призначення в 19 сторіччі, а його розв'язок було опубліковано посмертно в 1890 році латинською мовою[16].

Алгоритм угорського методу складається з попереднього етапу і не більше, ніж (п-2) послідовно виконуваних ітерацій. Кожна ітерація пов'язана з еквівалентними перетворюваннями матриці, отриманої внаслідок проведення попередньої ітерації, а також з вибором в ній максимального числа незалежних нулів. Кінцевим результатом ітерації є збільшення числа незалежних нулів на одиницю. Як тільки число незалежних нулів досягне n, то проблему набору вирішено, а оптимальний варіант призначення визначається позиціями незалежних нулів в останній матриці [12].

Алгоритм угорського методу

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

Далі розглядають i-тий рядок отриманої матриці, розшукують її мінімальний елемент і з кожного елемента цього рядка віднімають мінімальний. Цю процедуру повторюють із усіма рядками. У результаті одержимо матрицю С0 (С0~ C), у кожному рядку й стовпці якої є, принаймні, один нуль. Описаний процес перетворення С у С0 називається приведенням матриці.

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

(k+1)-а ітерація. Припустимо, що k-та ітерація вже проведена й у результаті отримана матриця Ск . Якщо в ній є рівно n нулів із зірочкою, то процес рішення закінчується. У противному випадку переходимо до (k+1) -ої ітерації.

Кожна ітерація починається першим і закінчується другим етапом. Між ними може кілька разів проводитися пари етапів: третій - перший. Перед початком ітерації знаком '+' виділяють стовпці матриці Ск , які містять нулі із зірочками.

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

1) рядок, що містить невиділений нуль, містить також і нуль із зірочкою;

2) цей рядок не містить нуля із зірочкою.

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

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

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

Цей процес за кінцеве число кроків закінчується одним з наступних результатів:

1) всі нулі матриці Ск виділені, тобто перебувають у виділених рядках або стовпцях. При цьому переходять до третього етапу;

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

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

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

Далі над елементами ланцюжка, що знаходяться на непарних місцях ( 0' ) ставимо зірочки, знищуючи їх над парними елементами (0* ). Потім знищуємо всі штрихи над елементами Ск і знаки виділення '+'. Кількість незалежних нулів буде збільшено на одиницю. На цьому (k+1)-а ітерація закінчена.

Третій етап. До цього етапу переходять після першого, якщо всі нулі матриці Ск виділені. У такому випадку серед невиділених елементів Ск вибирають мінімальний і позначають його h (h>0). Далі віднімають h із всіх елементів матриці Ск , розташованих у невиділених рядках і додають до всіх елементів, розташованим у виділених стовпцях. У результаті одержують нову матрицю С' k , еквівалентну Ск . Помітимо, що при такому перетворенні, всі нулі із зірочкою матриці Ск залишаються нулями й у С' к , крім того, у ній з'являються нові невиділені нулі. Тому переходять знову до першого етапу. Завершивши перший етап, залежно від його результату або переходять до другого етапу, або знову повертаються до третього етапу.

Після кінцевого числа повторень черговий перший етап обов'язково закінчиться переходом на другий етап. Після його виконання кількість незалежних нулів збільшиться на одиницю й (k+1)-а ітерація буде закінчена[13,14,18].

Блок-схема реалізації угорського методу представлена в додатку А.

2.2 Модернізований угорський метод

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

Якщо кількість виділених нулів дорівнює розмірності матриці, тобто, n, - задача вирішена.

Якщо ні - переходимо до третього етапу класичного методу[4].



2.3 Метод Мака

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

Виділити в кожному рядку по одному мінімальному елементу. Стовпці, у яких немає виділених елементів називаються вільними, а інші-зайнятими[19].

Алгоритм методу Мака

Крок 1. Перевірка оптимальності плану. Якщо в таблиці немає жодного вільного стовпця, то отримане рішення є оптимальним, інакше перейти до кроку 2.

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

Крок 3. Для всіх рядків, у яких є виділені елементи в позначених * (зірочкою) стовпцях, знайти різницю між мінімальним елементом серед непозначених * (зірочкою) стовпців ai і мінімальним елементом серед позначених * стовпців bi (Di = ai - bi).

Крок 4. Знайти мінімальну різницю D=min{Di} серед знайдених на кроці 3 різниць.

Крок 5. Перетворити поточну таблицю, додавши до всіх елементів усіх позначених * стовпців D. Непозначені стовпці залишаються без змін.

Крок 6. Елемент ai у непозначеному стовпці який використовувався для розрахунку мінімальної різниці виділити підкресленням як альтернативний (тепер він має ту ж вартість, що й елемент bi у позначеному стовпці).

Крок 7. Якщо альтернативний елемент ai, отриманий на кроці 6, знаходиться у зайнятому стовпці, то позначити цей стовпець * і перейти до кроку 3, інакше перейти до кроку 8.

Крок 8. У вільний стовпець в клітку з альтернативним елементом показати стрілочкою перенесення по рядку виділеного елементу в альтернативну клітину.

Крок 9. Якщо стовпець, з якого було перенесено виділений елемент, став вільним, перейти до кроку 8, інакше перейти до кроку 10.

Крок 10. Кінець даної ітерації. Перетворити таблицю, зробивши виділеними відповідні альтернативні елементи. Прибрати всі позначки * і підкреслення та перейти до кроку 1[8,9].



Розділ 3. Розв'язування задачі про призначення

3.1 Розв'язування задачі угорським методом

Розглянемо ситуацію, яку можна записати у вигляді задачі про призначення. Студент Тарас, у зв'язку зі станом здоров'я, пропустив майже цілий семестр. П'ятеро студентів вирішили йому допомогти у підготовці до іспитів. Кожен студент може допомогти в підготовці до одного іспиту. Ефективність допомоги виражена в балах, які студенти отримали за поточну успішність під час поточного семестру, представлена у таблиці 3.1.

Таблиця 3.1

Студент Дисципліна	Петро	Оля	Юра	Юля	Катя
Дослідження операцій	48	36	43	45	39
Дискретний аналіз	40	41	49	38	32
Маркетинг	47	47	44	48	40
СППР	50	46	38	36	41
ПСЕП	43	35	32	34	25

Потрібно так закріпити предмети за студентами, щоб Тарас склав іспити з найкращим з можливих сумарним результатом.

Математична модель задачі

F=48x11+36x12+43x13+45x14+39x15+40x21+41x22+49x23+38x24+32x25+47x31+

+47x32+44x33+48x34+40x35+50x41+46x42+38x43+36x44+41x45+43x51+35x52+

+32x53+34x54+25x55>max

Поетапний розв'язок задачі

Таблиця вихідних умов (табл. 3.2).

Таблиця 3.2

С=	48	36	43	45	39
	40	41	49	38	32
	47	47	44	48	40
	50	46	38	36	41
	43	35	32	34	25

У таблиці 3.2 n=m, тому її можна розв'язати угорським методом.

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

Таблиця 3.3

С=	2	11	6	3	2
	10	6	0	10	9
	3	0	5	0	1
	0	1	11	12	0
	7	12	17	14	16

Далі розглядають i-тий рядок таблиці 3.3, розшукують в ній мінімальний елемент і з кожного елемента цього рядка віднімають мінімальний. Отримують таблицю 3.4, яка еквівалентна таблиці 3.2:

Таблиця 3.4

С=	0	9	4	1	0
	10	6	0	10	9
	3	0	5	0	1
	0	1	11	12	0
	0	5	10	7	9

Відзначаємо систему незалежних нулів:

Таблиця 3.5

С0=	0*	9	4	1	0
	10	6	0*	10	9
	3	0*	5	0	1
	0	1	11	12	0*
	0	5	10	7	9

Якщо кількість 0* дорівнює n, тоді задачу можна вважити розв'язаною. У цій задачі 0*<n, тому переходять до (к+1)-ої ітерації.

Зауваження. Перед початком кожної ітерації знаком '+' виділяють стовпці, які містять нулі із зірочками(табл. 3.6).

Таблиця 3.6

С0=	0*	9	4	1	0
	10	6	0*	10	9
	3	0*	5	0	1
	0	1	11	12	0*
	0	5	10	7	9
	+		+		+



Перший етап. У таблиці 3.6 виділяють штрихом нуль, який знаходиться одночасно у невиділеному стовпці та у рядку з нулем із зірочкою. З нуля з зірочкою і з стовпця, в якому він знаходиться, знімають виділення. Відмічають рядок, в якому знаходиться нуль зі штрихом (табл.. 3.7).

Таблиця 3.7

С1=	0*	9	4	1	0
	10	6	0*	10	9
	3	0*	5	0?	1	+
	0	1	11	12	0*
	0	5	10	7	9
	+		+		+

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

Третій етап. Серед невиділених елементів матриці вибирають мінімальний і позначають його h (h>0). Далі віднімають h із всіх елементів матриці, розташованих у невиділених рядках і додають до всіх елементів, розташованим у виділених стовпцях. У результаті одержують нову матрицю С'1(табл.. 3.8), еквівалентну С1 . У даній задачі h=1.

Таблиця 3.8

С'1=	0*	8	4	0	0
	10	5	0*	9	9
	4	0*	6	0?	2
	0	0	11	11	0*
	0	4	10	6	9

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



Таблиця 3.9

С?1=	0*	8	4	0?	0	+
	10	5	0*	9	9
	4	0*	6	0?	2	+
	0	0?	11	11	0*	+
	0?	4	10	6	9
			+

Другий етап. Будують ланцюжок з нулів матриці С1? : вихідний нуль зі штрихом, нуль із зірочкою, розташований в одному стовпці з першим нулем зі штрихом в одному рядку з попереднім нулем із зірочкою й т.д.

Далі над елементами ланцюжка, що знаходяться на непарних місцях ( 0' ) ставимо зірочки, знищуючи їх над парними елементами (0* ). Потім знищуємо всі штрихи над елементами С1 і знаки виділення '+'. Перша ітерація закінчена. Отримали матрицю С2 (табл. 3.10)

Таблиця 3.10

С2=	0	8	4	0*	0
	10	5	0*	9	9
	4	0*	6	0	2
	0	0	11	11	0*
	0*	4	10	6	9

Після цієї ітерації кількість незалежних нулів стало дорівнювати 5 (розмірності матриці 5) і тому алгоритм закінчує роботу. Шукані елементи призначення відповідають позиціям незалежних нулів матриці С2 (тобто 0*).

L(x) = 43+47+49+45+41=225

Відповідь. Щоб Тарас склав іспити з максимально можливим результатом, одногрупники повинні допомагати йому в підготовці у такій відповідності:

Петро - ПСЕП;

Оля - маркетинг;

Юра - дискретний аналіз;

Юля - дослідження операцій;

Катя - СППР.

3.2 Розв'язування задачі методом Мака

Постановка задачі така ж сама, як і в розділі 3.1, але коефіцієнти цільової функції записуємо зі знаком ?-?, тому що задача на максимум.

Покроковий розв'язок задачі

Матриця вихідних умов разом з виділеними мінімальними елементами у рядках (табл. 3.11).

Таблиця 3.11

-48	-36	-43	-45	-39
-40	-41	-49	-38	-32
-47	-47	-44	-48	-40
-50	-46	-38	-36	-41
-43	-35	-32	-34	-25

Перша ітерація

Крок 1. В таблиці немає вільних стовпців, тому заданий план не єоптимальний.

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

Таблиця 3.12

-48	-36	-43	-45	-39
-40	-41	-49	-38	-32
-47	-47	-44	-48	-40
-50	-46	-38	-36	-41
-43	-35	-32	-34	-25
*

Крок 3. Знаходимо мінімальний елемент серед позначених по рядках (bi), та мінімальний елемент серед непозначених по рядках (ai). Знаходимо різницю ai - bi(табл. 3.13).

Таблиця 3.13

ai - bi						bi
-45-(-48)=3	-48	-36	-43	-45	-39	-48
	-40	-41	-49	-38	-32
	-47	-47	-44	-48	-40
-46-(-50)=4	-50	-46	-38	-36	-41	-50
-35-(-43)=8	-43	-35	-32	-34	-25	-43
	*

Крок 4. Мінімальна різниця = 3.

Крок 5. Додаємо до усіх елементів першого стовпця число 3 (табл. 3.14).

Таблиця 3.14

-45	-36	-43	-45	-39
-37	-41	-49	-38	-32
-44	-47	-44	-48	-40
-47	-46	-38	-36	-41
-40	-35	-32	-34	-25
*

Крок 6. Виділяємо елемент таблиці a1, як альтернативний (він має тепер таку саму вартість як елемент b1) (табл. 3.15).

Таблиця 3.15

-45	-36	-43	-45	-39
-37	-41	-49	-38	-32
-44	-47	-44	-48	-40
-47	-46	-38	-36	-41
-40	-35	-32	-34	-25
*

Крок 7. Елемент a1 pнаходиться у рядку разом з виділеним елементом. Позначаємо стовпець 4 *(зірочкою) та вертаємося до кроку 3.

Крок 3?. Повторюємо аналогічні дії.

Таблиця 3.16

-43-(-45)=2	-45	-36	-43	-45	-39	-45
	-37	-41	-49	-38	-32
-47-(-48)=1	-44	-47	-44	-48	-40	-48
-46-(-47)=1	-47	-46	-38	-36	-41	-47
-35-(-40)=5	-40	-35	-32	-34	-25	-40
	*			*

Крок 4?. Мінімальна різниця = 1, причому у двох рядках. Обираємо довільну, наприклад, у третьому рядку.

Крок 5?. Додаємо до елементів 1 та 4 стовпців одиничку.

Таблиця 3.17

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*			*

Крок6?. Виділяємо елемент таблиці a3.

Таблиця 3.18

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*			*

Крок 7?. Елемент a3 знаходиться у вільному стовпці, тому переходимо до кроку 8.

Крок 8. Елемент a3 виділяємо, а з елементу b3 виділення знімаємо.

Таблиця 3.19

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*

Крок 9. Стовпець 4 став вільним.

Крок 10. Кінець першої ітерації.

Друга ітерація

Крок 1.

Таблиця 3.20

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25

Крок 2.

Таблиця 3.21

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*

Крок 3.

Таблиця 3.22

-44-(-44)=0	-44	-36	-43	-44	-39	-44
	-36	-41	-49	-37	-32
	-43	-47	-44	-47	-40
-46-(-46)=0	-46	-46	-38	-35	-41	-46
-35-(-39)=4	-39	-35	-32	-33	-25	-39
	*

Крок 4. Мінімальна різниця 0 в четвертому рядку.

Крок 5.

Таблиця 3.23

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25

Крок 6.

Таблиця 3.24

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25

Крок 7 . Елемент b1 знаходиться у вільному стовпці.

Крок 8.



Таблиця 3.25

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25

Крок 9. Стовпець 1 залишився зайнятим.

Крок 10. Кінець другої ітерації.

Третя ітерація

Виконують аналогічні дії, що і в попередніх ітераціях.

Кроки 1-6.

Таблиця 3.26

	-44	-36	-43	-44	-39
	-36	-41	-49	-37	-32
	-43	-47	-44	-47	-40
-46-(-46)=0	-46	-46	-38	-35	-41	-46
-35-(-39)=4	-39	-35	-32	-33	-25	-39
	*

Крок 7.

Таблиця 3.27

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*

Кроки 3?-6?.



Таблиця 3.28

	-44	-36	-43	-44	-39
	-36	-41	-49	-37	-32
-47-(-47)=0	-43	-47	-44	-47	-40	-47
-41-(46)=5	-46	-46	-38	-35	-41	-46
-35-(-39)=4	-39	-35	-32	-33	-25	-39
	*	*

Крок 7? .

Таблиця 3.29

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*	*

Кроки 3?-6??.

Таблиця 3.30

-43-(44)=1	-44	-36	-43	-44	-39	-44
	-36	-41	-49	-37	-32
-44-(-47)=3	-43	-47	-44	-47	-40	-47
-41-(-45)=5	-46	-46	-38	-35	-41	-46
-32-(-39)=7	-39	-35	-32	-33	-25	-39
	*	*		*

Крок 7?

Таблиця 3.31

-43	-35	-43	-43	-39
-35	-40	-49	-36	-32
-42	-46	-44	-46	-40
-45	-45	-38	-34	-41
-38	-34	-32	-32	-25
*	*		*

Кроки 3???- 6???

Таблиця 3.32

...

-39-(-43)=4	-43	-35	-43

Подобные документы

• Задачі багатокритеріальної оптимізації в дослідженні операцій

  Постановка задачі багатокритеріальної оптимізації та її та математична модель. Проблеми і класифікація методів вирішення таких задач, способи їх зведення до однокритеріальних. Метод послідовних поступок. Приклад розв'язування багатокритеріальної задачі.
  
  курсовая работа [207,3 K], добавлен 22.12.2013
  

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

  Постановка та описання алгоритму розв’язання задачі про оптимальне призначення, формулювання вимог. Обґрунтування вибору засобів програмування. Розробка структури програми та системи її візуалізації, тестування та верифікація, оцінка ефективності.
  
  курсовая работа [1,1 M], добавлен 12.05.2013
  

• Метод Крамера

  Розробка програмного забезпечення для розв'язку системи лінійних рівнянь за формулами Крамера, головні особливості мови Turbo Pascal. Методи розв'язування задачі, архітектура програми та її опис. Контрольний приклад та результат машинного експерименту.
  
  курсовая работа [47,7 K], добавлен 23.04.2010
  

• Симплексний метод розв'язування задач лінійного програмування

  Початковий опорний план, перехід від одного до іншого. Оптимальний розв’язок, його головні критерії. Знаходження опорного плану задачі, складання симплексної таблиці. Приклад оформлення першої та другої таблиці для розв’язку задач лінійного програмування.
  
  лекция [479,7 K], добавлен 10.10.2013
  

• Метод Жордана Гаусса

  Розробка програмного забезпечення для розв'язку системи лінійних рівнянь за формулами Гаусса, головні особливості мови Turbo Pascal. Методи розв'язування задачі, архітектура програми та її опис. Контрольний приклад та результат машинного експерименту.
  
  курсовая работа [40,3 K], добавлен 23.04.2010
  

• Інформаційно-довідкова система

  Методи, засоби та алгоритми розв'язування задачі. Розробка інтерфейсу програми для забезпечення діалогу: ком'ютер - користувач при роботі з базою даних довідкової системи навчальних закладів. Програма та її опис, призначення. Логічна структура програми.
  
  курсовая работа [234,8 K], добавлен 14.03.2010
  

• Розробка програми розв’язання нелінійних рівнянь методом Ньютона

  Виконання "ручного" розв'язування рівняння методом Ньоютона. Розробка програми на мові С#, яка реалізує введення вихідних даних, розв'язання заданого рівняння, виведення результатів у зручній формі на екран. Визначення початкового наближення кореня.
  
  лабораторная работа [120,9 K], добавлен 19.01.2022
  

• Метод "Стрілянини"

  Метод розв’язків рівнянь більш високих порядків. Вибір методу розв'язання задачі Коші. Методи розв'язання крайових задач розглядаються на прикладі звичайного диференціального рівняння другого порядку. Вибір методу інструментальних засобів вирішення задач.
  
  курсовая работа [132,0 K], добавлен 03.12.2009
  

• Числові методи

  Розв’язання системи рівняння методом Гауса за схемою з частковим вибором головного елементу. Рішення задачі Коші методом Рунге-Кутта. Знаходження моментів кубічних сплайнів методом прогонки. Розв’язування системи нелінійних рівнянь методом Ньютона.
  
  контрольная работа [252,3 K], добавлен 04.06.2010
  

• Розв’язування математичних задач за допомогою мови логічного програмування Prolog

  Огляд переваг та недоліків мови Пролог, історія її створення. Числення предикатів як математична основа її функціонування. Порівняльна характеристика середовищ програмування Prolog. Алгоритми розв’язування математичних задач за допомогою цієї мови.
  
  курсовая работа [504,5 K], добавлен 23.12.2014
  

• Розв’язання алгебраїчних рівнянь. Методи простих ітерацій та Ньютона

  Види рівнянь та методи їх розв’язань. Чисельні методи уточнення коренів, постановка задачі. Рішення нелінійного рівняння методом простих та дотичних ітерацій. Використання програмних засобів. Алгоритми розв’язку задач. Програми мовою С++, їх тестування.
  
  курсовая работа [232,2 K], добавлен 12.02.2013
  

• Задачі цілочисельного програмування та спеціальні методи знаходження їх оптимальних розв'язків

  Приклади застосування цілочисельних задач лінійного програмування у плануванні та управлінні виробництвом, геометрична інтерпретація їх розв’язків на площині. Завдання складання розкладу занять на математичному факультеті. Математична модель розкладу.
  
  дипломная работа [933,1 K], добавлен 23.09.2012
  

• Розфарбування графів як математична модель прикладних задач

  Відомості з теорії графів, методи отримання точних розв'язків задачі їх розфарбування. Алгоритм розфарбування графу методом неявного перебору. Комп'ютерна реалізація розв’язку задачі розфарбування графів. Типові задачі та існуючі програмні продукти.
  
  курсовая работа [335,6 K], добавлен 15.06.2015
  

• Математичне моделювання економічних систем

  Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.
  
  контрольная работа [385,2 K], добавлен 04.06.2009
  

• Програма переводу з однієї системи числення у іншу

  Розробка програмного забезпечення для розв’язування задачі обчислювального характеру у середовищі Turbo Pascal 7.0. Розгляд систем числення. Практична реалізація задачі переводу чисел з однієї системи числення у іншу. Процедура зворотного переводу.
  
  курсовая работа [112,2 K], добавлен 23.04.2010
  

• Методи дослідження операцій

  Основні визначення дослідження операцій. Модель "затрати-випуск" В.В. Леонтьєва. Загальний вигляд задачі лінійного програмування. Розв'язання за допомогою симплекс-методу. Економічна інтерпретація основної та спряженої задач. Поліпшення плану перевезень.
  
  учебное пособие [1,1 M], добавлен 27.12.2010
  

• Чисельне розв’язання задач оптимального керування

  Дискретизація задачі із закріпленим лівим і вільним правим кінцем. Необхідні умови оптимальності. Ітераційний метод розв’язання дискретної задачі оптимального керування з двійним перерахуванням. Оптимальне стохастичне керування. Мінімаксне керування.
  
  контрольная работа [221,8 K], добавлен 19.12.2010
  

• Угорський метод рішення завдань про призначення

  Нульові елементи матрицi та процес за кінцеве число кроків. Угорський метод один з найцікавіших і найпоширеніших методів рішення транспортних завдань. Застосовування угорських методiв для рішення завдань про призначення. Алгоритм та завдання вибору.
  
  контрольная работа [357,6 K], добавлен 20.11.2010
  

• Моделювання та розрахунок задачі пружності методом скінченних елементів за допомогою пакету Femlab 3.3

  Пакети і комплекси програм, які реалізують метод скінчених елементів. Femlab 3.3 - потужне інтерактивне середовище для моделювання і розв'язування наукових і технічних проблем. Вибір варіаційного принципу. Чисельна реалізація математичних моделей.
  
  дипломная работа [1,8 M], добавлен 11.09.2014
  

• Побудова емпіричної формули методом найменших квадратів

  Вибір емпіричної формули. Метод оберненої матриці. Розв’язування систем лінійних рівнянь на ПК. Вибір двох апроксимуючих функцій. Розрахунки у середовищі MS Excel для лінійної функції, для квадратичної функції та у середовищі MS Visual Studio (мовою С#).
  
  курсовая работа [658,8 K], добавлен 18.08.2014
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам