Построение математической модели поставленной задачи

Оглавление

 

 

Введение

 

 

В наше время в науке  уделяется все большое внимание вопросам организации и  управления, это приводит к необходимости анализа сложных целенаправленных процессов под углом зрения их структуры и организации. Потребности практики вызвали к жизни специальные методы, которые удобно объединять под названием «исследование операций». Под этим термином понимается применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Целью исследования операций является выявление наилучшего способа действия при решении  той или иной задачи. Главная роль при этом отводится математическому моделированию. Для построения математической модели необходимо иметь строгое представление о цели функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений. Цель и ограничения должны быть представлены в виде функций.

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

программирования, когда целевая функция и все ограничения линейные. Для

решения математических моделей других типов предназначены методы

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

              Итерационная природа алгоритмов  обычно приводит к объемным  однотипным вычислениям. В этом  и заключается причина того, что  эти алгоритмы разрабатываются, в основном, для реализации с  помощью вычислительной техники.

              Данный курсовой проект предусматривает  решение частного случая транспортной  задачи (задача о назначениях).

 

 

 

1. Построение математической модели поставленной задачи:

 

 

В задаче известно что фирма занимается продажей оборудования для компьютеров, в ней имеется 5 специалистов по маркетингу и 5 специалистов – техников, которых необходимо объединить в пары – команды по продаже оборудования. Также известен индекс взаимной несовместимости данных специалистов, который варьируется от 20 (выраженная враждебность) до 1 (дружеские отношения), данный индекс представлен в следующей таблице:

Транспортная таблица:
	Спец.по маркетингу:
техники	1	2	3	4	5
1	11	8	4	3	9
2	7	4	7	11	19
3	13	20	1	12	14
4	5	8	12	6	1
5	16	7	18	9	13

 

 

Пусть специалисты – техники – i(1..5), а специалисты по маркетингу – j(1..5),

А индекс взаимной совместимости 2-x сотрудников друг с другом - С, тогда получаем что 1 специалист-техник и 1 специалист по маркетингу – С11,2 специалист – техник и 1 специалист по маркетингу – С21, и т.д. ,а 5 специалист- техник и 5 специалист по маркетингу – C55.

С учетом индекса взаимной несовместимости, который дан по условию задачи, получаем ,что 1 специалист по маркетингу и 1 специалист-техник – 11С11 ,  2 специалист – техник и 1 специалист по маркетингу – 7С21, и т.д. ,а 5 специалист- техник и 5 специалист по маркетингу – 13C55.

Используя созданные величины, определим общую совместимость пар сотрудников данной фирмы.  В данной задаче необходимо найти минимизировать индекс взаимной несовместимости сотрудников, учитывая это получаем следующую целевую функцию:

11С11+7С21+13С31+5С41+16С51 +8С12+4С22+20С32+8С42+7С52+4С13+7С23+1С33+12С43+18С53 +3С14+11С24+12С34+6С44+9С54+9С15+19С25+14С35+1С45+13С55         min.

Каждый специалист техник может быть объединен в пару только с 1 специалистом по маркенигу , соответственно допустим 1 специалист по маркетингу объединяется в пару с 1 специлистом –техником, в этом случае индекс С получается = 1, а при всех остальных вариантах индекс С будет = 0.

С учетом того, что все специалисты должны быть объеденены в пары,

составим систему ограничений:

С11+С12+С13+С14+С15=1

С21+С22+С23+С24+С25=1

С31+С32+С33+С34+С35=1

С41+С42+С43+С44+С45=1

С51+С52+С53+С54+С55=1

С11+С21+С31+С41+С51=1

С12+С22+С32+С42+С52=1

С13+С23+С33+С43+С53=1

С14+С24+С34+С44+С54=1

С15+С25+С35+С45+С55=1

 

 

 

 

 

 

 

2. Описание математического метода решения

 

 

 

Решим данную задачу, как задачу о назначениях.

Для этого рассмотрим транспортную таблицу, заданную в условии задачи(см       табл1)

 

Транспортная таблица:
	Спец.по маркетингу:
техники	1	2	3	4	5
1	11	8	4	3	9
2	7	4	7	11	19
3	13	20	1	12	14
4	5	8	12	6	1
5	16	7	18	9	13

 

 

 

 

 

 

Таблица 1 : исходные данные

 

1). В каждом столбце  заданной транспортной таблицы найдем наименьшее значение и вычтем его из содержимого всех ячеек этой строки матрицы (см таблицу 2)

Вычет по строкам:
	Спец.по маркетингу:
техники	1	2	3	4	5
1	8	5	1	0	6
2	3	0	3	7	15
3	12	19	0	11	13
4	4	7	11	5	0
5	9	0	11	2	6

 

 

 

 

 

 

Таблица 2 : вычет по строкам

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

Вычет по столбцам:
	Спец.по маркетингу:
техники	1	2	3	4	5
1	5	5	1	0	1
2	0	0	3	7	15
3	9	19	0	11	13
4	1	7	11	5	0
5	6	0	11	2	6

 

 

 

 

 

 

 

 

 

 

Таблица 3 : вычет по столбцам

 

 

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

Вычет по столбцам:
	Спец.по маркетингу:
техники	1	2	3	4	5
1	5	5	1	0	1
2	0	0	3	7	15
3	9	19	0	11	13
4	1	7	11	5	0
5	6	0	11	2	6

Таблица 4 : Результат вычислений

 

 

 

Т.к. Каждый специалист техник может быть объединен в пару только с 1 специалистом по маркенигу , и соответственно в каждой строке и в каждом столбце может быть только 1 вариант пары сотрудников организации, то получаем, что для того чтобы суммарный индекс несовместимости специалистов был минимальным, специалистов надо объединить в следующие пары: 1 спец. По маркетингу со 2 техником, 2 спец. По маркетингу с 5 техником, 3 спец.по маркетингу с 3 техником, 4 спец. По маркетингу с 1 техником и 5 спец. По маркетингу с 4 техником.

При данном распределении пар сотрудников в дано организации, получаем минимальный суммарный индекс несовместимости = 19  (т.к 7+7+1+3+1=19).

 

3. Алгоритм решения унифицированной задачи

 

 

Рисунок 1 (Блок-схема):

 

 

Рисунок 2 (Блок-схема продолжение):

 

 

 

 

 

Рисунок 3 (Блок- схема продолжение)

 

 

 

 

 

Рисунок 4(Блок-схема продолжение)

 

 

 

 

 

Рисунок 5 (Блок-схема продолжение)

 

 

 

 

Рисунок 6(блок-схема продолжение)

 

 

 

 

 

Рисунок 7 (блок-схема продолжение)

 

Рисунок 8(Блок-схема продолжение)

 

4. Руководство пользователя к разработанному решению

 

 

4.1 Описание  и назначение программы

Программа Назначение предназначена для решения частного случая транспортных задач- задач о назначении .Данная программа облегчает процесс решения задач о назначении, избавляя пользователя от многошаговых этапов расчета оптимального набора проектов при использовании математического метода решения.  В ходе расчета программа высчитавает содержимое таблиц , и на основе их результатов выдает пользователю оптимальный план. Пользователь может наглядно увидеть оптимальное решение задачи. Программа Назначение умеет работать с задачами размерности5*5.То есть когда в условии задачи присутствует 5 работников –например техников, и пять работников – менеджеров, которых необходимо объединить в пары. 4.2 Условия  выполнения программы Операционная Система: Windows 98 / ME / 2000 / XP / Vista / 7 Процессор: Intel Pentium II и выше ОЗУ: 64 мб и выше HDD: 2 мб свободного пространства     CD-ROM 16x Клавиатура, Мышь 4.3 Выполнение  программы Для начала работы с программой Назначение нужно запустить исполняемый файл Назначение.exe после чего появится окно программы (рис 9)