Исследование задачи оптимизации кооперации разработчиков

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ

УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА»

Филиал в г. Тольятти

Кафедра радиоэлектроники и системотехники

Курсовая работа по дисциплине

«Теория принятия решений»

По теме:

«Исследование задачи оптимизации кооперации разработчиков»

Реферат

Математическое моделирование задачи; задача линейного программирования; венгерский метод; пакет математических расчётов; ПЭР;

В проекте исследуется задача линейного целочисленного программирования.

Целью работы является распределение заказов на разработку систем между организациями, таким образом, чтобы затраты на разработку всех приборных систем были минимальными.

При решении применяются два метода решения задачи : венгерский метод, на основе которого производится ручное вычисление решение, а так же нахождение решения с помощью пакета экономических решений PER.

Получено два решения задачи, с одинаковым числом общих затрат на производство всех систем.

Содержание

Формулировка задачи

Введение

1. Математическое моделирование задачи

2. Обоснование и выбор метода решения

3. Ручное решение задачи (венгерский метод)

4. Решение задачи с использованием компьютерных средств

5. Формулировка полученного решения

Заключение

Литература

Формулировка задачи

Для новой конструкции самолета требуется разработать 6 приборных систем. Имеется 11 организаций, каждая из которых может выполнить разработку одной (любой) приборной системы. Поскольку затраты на разработку Сi (где i -номер типа системы) при этом неодинаковы, то они задаются табл. Требуется так распределить заказы, чтобы общие затраты на разработку всех приборных систем были минимальными.

Таблица 1 – условие задачи

1-я система

2-я система

3-я система

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.

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

    Помечаем (например знаком “+” сверху) столбцы, где есть ноль со звездочкой, и считаем эти столбцы занятыми. Элемент матрицы назовем незанятым, если он стоит на пересечении незанятой строки и незанятого столбца, остальные элементы – занятые. Если в матрице нет незанятых нулей, то переходим к пункту 6. В противном случае выбираем первый из них (просматривая поочередно строки слева на право). Отмечаем его например штрихом – если в его строке нет 0*, то переходим к пункту 5. Если в его строке есть ноль со *, тогда переходим к пункту 5.

    Освобождаем (снимаем знак + и считаем его снова незанятым) столбец, в котором находиться 0*, лежащий в той же строке что и отмеченный штрихом нуль. Помечаем строку с этими элементами как занятую. Возвращаемся к пункту 3.

    Начиная с только что отмеченного нуля со штрихом, строим цепочку из нулей от этого 0’ по столбцу к 0*, от него по строке к 0’ и т.д. пока это возможно. Цепочка оборвется на некотором 0’. Снимаем звездочки у нулей из цепочки и присваиваем их нулям со штрихами – так мы получили матрицу, где набор нуле со звездочкой стал больше предыдущего на 1 и является также правильным. Снимаем все пометки кроме звездочек и возвращаемся к пункту 1.

    Отыскиваем минимальный элемент среди незанятых элементов матрицы и вычитаем его из всех незанятых строк и прибавляем ко всем занятым столбцам. Никакие пометки при этом не снимаются. Получается эквивалентная матрица и содержащая незанятые нули. Возвращаемся к пункту 2.

Так же задачу оптимального распределения и минимизации затрат можно решить с помощью пакета экономических решений PER.

Таким образом, данную задачу можно решить двумя методами – венгерским методом и с помощью пакета экономических решений PER.

    1. Ручное решение задачи (венгерский метод)

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

дополним её нулями до вида матрицы N x N. так, поступим по приведенному выше алгоритму:

Приведем ее к такому виду, что она содержала хотя бы по одному нулевому элементу в каждой строке и столбце:

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

Таким образом оптимальным решением задачи является следующее распределение приборных систем по организациям:

    1-ю систему отправить на изготовление 9-ой или 10-ой организации.

    2-ю систему – 6-ой организации.

    3-ю систему – 4-ой организации.

    4-ю систему – 5-ой организации.

    5-ю систему – 2-ой организации.

    6-ю систему – 3-ой организации.

На это решение у нас получаются затраты минимальны и составляют 10 условных единиц.

Рассчитаем затраты на производство каждой системы определенной организацией, пользуясь формулой расчета :

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

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

Организация

Система

Затраты 1е решение

Затраты 2е решение

2

5

1

1

3

6

2

2

4

3

2

2

5

4

1

1

6

2

1

1

9

1

3

0

10

1

0

3

Суммарные затраты

10

Таким образом, оба решения дают одинаковые суммарные затраты.

    1. Решение задачи с использованием компьютерных средств

Компьютерное решение задачи производится с помощью пакета экономических решений PER, имеющего доступный DOS-интерфейс. Решение задачи осуществляется в соответствии со следующим алгоритмом:

    Вызвать программу;

    Выбрать тип решаемой задачи ( в данном случае задача о назначении):

Рисунок 1 – выбор типа решаемой задачи

    В главном меню выбрать пункт «Ввод новой задачи»:

Рисунок 2 – Ввод новой задачи

    Задать признак оптимизации– максимизировать/минимизировать, ввести количество объектов и заданий:

Рисунок 3 – задание признаков оптимизации

    Ввести необходимые числовые данные задачи:

Рисунок 4 – ввод данных в программу

    Выбрать в главном меню пункт «Решение задачи»:

Рисунок 5 – команда решения задачи

    Выбрать просмотр решения задачи:

Рисунок 6 – выходные данные

Из приведенного выше решения следует, что для распределения работ с минимальными затратами:

    организация 2 (объект 02) должна разрабатывать систему 5 (задание Т5)

    организация 3 (объект 03) должна разрабатывать систему 6 (задание Т6)

    организация 4 (объект 04) должна разрабатывать систему 3 (задание Т3)

    организация 5 (объект 05) должна разрабатывать систему 4 (задание Т4)

    организация 6 (объект 06) должна разрабатывать систему 2 (задание Т2)

    организация 9 (объект 09) должна разрабатывать систему 1 (задание Т1)

    1. Формулировка полученного решения

Для того, чтобы общие затраты на разработку всех приборных систем были минимальными, требуется распределить их между организациями-изготовителями следующим образом :

Таблица 3 – Результаты решения задачи с помощью PER

Организация

Система

Затраты

2

5

1

3

6

2

4

3

2

5

4

1

6

2

1

9

1

3

Суммарные затраты

10

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

Заключение

Задача линейного целочисленного программирования решена двумя способами. Машинное решение произведено с помощью пакета экономических решений PER , ручное решение задачи произведено по венгерскому методу решения задач распределения. Получено два решения с одинаковым искомым результатом. Ручной метод решения позволяет найти все ответы.

Решение, полученное с помощью компьютерных средств:

Организация

Система

Затраты

2

5

1

3

6

2

4

3

2

5

4

1

6

2

1

9

1

3

Суммарные затраты

10

Решение, полученное при ручном вычислении:

Организация

Система

Затраты 1е решение

Затраты 2е решение

2

5

1

1

3

6

2

2

4

3

2

2

5

4

1

1

6

2

1

1

9

1

3

0

10

1

0

3

Суммарные затраты

10

Таким образом, при выполнении курсового проекта были получены навыки применения на практике методов решения задач оптимального распределения задач, рассмотрено несколько методов решения подобных задач. Подобные навыки могут быть применены в различных сферах деятельности, таких как экономика, линейное программирование, менеджмент и др.

Литература

    Зайченко Ю.П. «Исследование операций», Киев 1979г.

    Старинова О.Л. - Лекции по предмету « Системный анализ и методы оптимизации», ТФ СГАУ 2009 г.

    Ляшенко И.М. «Линейное и нелинейное программирование»

    Вагнер Г. «Основы исследования операций»,1972 г.

    Таха Х. «Введение в исследование операций», 1986 г.