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

Зміст

Вступ

1Постановка завдання

2 Розв’язання завдання

3Приклад розв’язання задачі за допомогою угорського методу

Висновок

Література

Вступ

Тема контрольної роботи «Угорський метод рішення завдань про призначення».

Мета роботи: навчитися застосовувати угорський метод для рішення завдань про призначення, а саме:

- алгоритм угорського методу;

- завдання вибору.

Угорський метод є одним з найцікавіших і найпоширеніших методів рішення транспортних завдань. Основна ідея цього методу була вперше висловлена угорським математиком Е. Егерварі (звідси й назва методу) задовго до виникнення теорії лінійного програмування.

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

1 Постановка завдання

Припустимо, що єрізні роботи імеханізми, кожний з яких може виконувати будь-яку роботу, але з неоднаковою ефективністю. Продуктивність кожного i-го механізмупри виконанні j-тої роботипозначимо Cij, і = 1,...,n; j = 1,...,n. Потрібно так розподілити механізми по роботах, щоб сумарний ефект від їхнього використання був максимальний. Таке завдання називається завданням вибору або завданням про призначення.

Формально вона записується так. Необхідно вибрати таку послідовність елементів з матриці

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

2 Розв ’ язання завдання

Введемо наступні поняття.

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

Дві прямокутні матриці С и D називаються еквівалентними (C ~ D), якщо Cij ~Dijдля всіх i,j . Завдання про призначення, обумовлені еквівалентними матрицями, є еквівалентними (тобто оптимальні рішення однієї з них будуть оптимальними й для другий, і навпаки). Блок-схема алгоритму угорського методу:

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

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

результаті одержимо матрицю З₀ (З₀ ~ C), у кожному рядку й стовпці якої є, принаймні, один нуль. Описаний процес перетворення С у С₀ називається приведенням матриці.

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

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--