Дослідження задачі оптимізації кооперації розробників [ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати. скачати Федеральне агентство з освіти Державна освітня установа вищої професійної освіти «Самарського державного аерокосмічного УНІВЕРСИТЕТ імені академіка С.П. КОРОЛЕВА » Філія в м. Тольятті Кафедра радіоелектроніки та системотехніки Курсова робота з дисципліни «Теорія прийняття рішень» За темою: «Дослідження задачі оптимізації кооперації розробників» Реферат Математичне моделювання задачі; завдання лінійного програмування; угорський метод; пакет математичних розрахунків; ПЕР; У проекті досліджується задача лінійного цілочисельного програмування. Метою роботи є розподіл замовлень на розробку систем між організаціями, таким чином, щоб витрати на розробку всіх приладових систем були мінімальними. При вирішенні застосовуються два методи розв'язання задачі: угорський метод, на основі якого проводиться ручне обчислення рішення, а так само перебування рішення за допомогою пакету економічних рішень PER. Отримано два рішення задачі, з однаковим числом загальних витрат на виробництво всіх систем. Зміст Формулювання завдання Введення 1. Математичне моделювання задачі 2. Обгрунтування і вибір методу вирішення 3. Ручне рішення задачі (угорський метод) 4. Рішення задачі з використанням комп'ютерних засобів 5. Формулювання отриманого рішення Висновок Література Формулювання завдання Для нової конструкції літака потрібно розроблено 6 приладових систем. Є 11 організацій, кожна з яких може виконати розробку однієї (любой) приладовій системи. Оскільки витрати на розробку З i (де i-номер типу системи) при цьому неоднакові, то вони задаються табл. Потрібно так розподілити замовлення, щоб загальні витрати на розробку всіх приладових систем були мінімальними. Таблиця 1 - умову задачі 1-а система 2-а система Третя система 4-а система 5-а система 6-а система Орг 1 5 6 3 5 4 4 Орг 2 3 1 7 5 1 6 Орг 3 7 2 7 8 4 2 Орг 4 8 9 2 2 3 9 Орг 5 6 5 7 1 7 7 Орг 6 8 1 6 8 4 2 Орг 7 6 7 4 5 10 7 Орг 8 4 5 7 9 4 7 Орг 9 3 7 9 3 7 6 Орг 10 3 6 7 3 5 4 Орг 11

7

8

7

6

4

6

Введення

Мета курсового проекту:

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

Завдання:

• дослідити особливості завдання розподілу, мінімізації витрат на розробку систем;

• провести математичне моделювання даного завдання;

• розглянути всілякі методи рішення;

• вибрати метод рішення;

• протестувати рішення задачі;

• вирішити цю ж задачу за допомогою комп'ютерних засобів;

• охарактеризувати отриманий результат, зіставивши його з умовою задачі;

Актуальність:

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

1. Математичне моделювання задачі

Цей вид завдань відноситься до завдань про призначення і є задачею лінійного програмування.

Введемо наступні позначення:

Cij - вартість виробництва i-й системи j-й організацією.

Xi, j - мінлива за фактом призначення, тобто xij = 1 тільки в тому випадку, коли i-ю систему призначають на виробництво j-й організації, так як організація може як результат роботи з даного проекту представити тільки одну систему, в інших випадках мінлива xij дорівнює 0, тоді матрицю X можна з визначення її елементів назвати матрицею призначень.

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

Тоді можна записати математичну модель даної задачі:

У вищенаведеної системі:

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

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

• Рівність (3) - сума по всіх елементів у матриці призначень контролює число загальних призначень на виробництво.

• Обгрунтування і вибір методу вирішення

Основним методом вирішення завдань класу задач про призначення є угорський метод. Він складається з декількох кроків:

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

такі ж перетворення над кожним стовпцем отримаємо деяку неотрицательную матрицю С1ij. Анологичних операції здійснюємо над усіма рядками матриці С1ij. Отримали неотрицательную матрицю D, у якої в кожному рядку і кожному стовпці є 0.

2. Позначаємо (деяким знаком, наприклад "*") який-небудь нуль в першому стовпці матриці D, потім відзначаємо нуль у другому стовпці не лежить в тій же рядку що перший (якщо такий знайдеться нуль) і так далі поки не пройдемо всі стовпці матриці D . Якщо число позначених нулів дорівнює числу стовпців в матриці D (нехай буде - n), то процес пошуку оптимального рішення закінчений - місця займані зазначеними нулями відповідають n змінним xij рівним 1.Но якщо ж нулів виявилося менше, то переходимо до пункту 3.

3. Позначаємо (наприклад знаком "+" зверху) стовпці, де є нуль із зірочкою, і вважаємо ці стовпці зайнятими. Елемент матриці назвемо незайнятим, якщо він стоїть на перетині незайнятої рядки і незайнятого стовпця, інші елементи - зайняті. Якщо в матриці немає незайнятих нулів, то переходимо до пункту 6. В іншому випадку вибираємо перший з них (переглядаючи по черзі рядка зліва на право). Відзначаємо його наприклад штрихом - якщо в його рядку немає 0 *, то переходимо до пункту 5. Якщо в його рядку є нуль зі *, тоді переходимо до пункту 5.

4. Звільняємо (знімаємо знак + і вважаємо його знову незайнятим) стовпець, в якому знаходитися 0 *, що лежить в тій же рядку що і відзначений штрихом нуль. Позначаємо рядок з цими елементами як зайняту. Повертаємося до пункту 3.

5. Починаючи з тільки що зазначеного нуля зі штрихом, будуємо ланцюжок з нулів від цього 0 'за стовпцем до 0 *, від нього за рядком до 0' і т.д. поки це можливо. Ланцюжок обірветься на деякому 0 '. Знімаємо зірочки у нулів з ​​ланцюга і присвоюємо їх нулях зі штрихами - так ми отримали матрицю, де набір нулі із зірочкою став більше попереднього на 1 і є також правильним. Знімаємо всі позначки крім зірочок і повертаємося до пункту 1.

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

Так само задачу оптимального розподілу та мінімізації витрат можна вирішити за допомогою пакету економічних рішень PER.

Таким чином, дане завдання можна вирішити двома методами - угорським методом і за допомогою пакету економічних рішень PER.

• Ручне рішення задачі (угорський метод)

Дана матриця вартостей:

доповнимо її нулями до виду матриці N x N. так, поступимо за наведеним вище алгоритмом:

Наведемо її до такого виду, що вона містила хоча б по одному нульового елементу в кожному рядку і стовпці:

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

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

• 1-у систему відправити на виготовлення дев'ятий або десятий організації.

• 2-у систему - другий організації.

• Третій систему - четвертий організації.

• 4-у систему - п'ятий організації.

• 5-у систему - 2-ий організації.

• 6-у систему - 3-ої організації.

На це рішення у нас виходять витрати мінімальні і складають 10 умовних одиниць.

Розрахуємо витрати на виробництво кожної системи певною організацією, користуючись формулою розрахунку:

Причому береться при цьому розрахунку з початкової матриці, отримані результати наведені в таблиці для обох рішень:

Таблиця 2 - Результати рішення задачі на угорському методу