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

Оглавление

Введение

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

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

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

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

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

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

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

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

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

Пусть специалисты – техники – 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 : исходные данные

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

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

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

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

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

Таблица 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 Описание  и назначение программы

Рисунок 9 : первое окно программы

Далее нужно занести исходные данные в таблицу для решения.

Кнопка "Убрать все" очищает таблицу для ввода данных. Нажатие кнопки «Тест» приводит к заполнению таблицы тестовыми данными. Нажатие кнопки «Справка» открывает текстовый документ с описанием работы программы.Нажатие кнопки «Расчет» приводит к вычислению и выводу результата. После нажатия на кнопку в таблице выводится оптимальный план решения задачи, и в диалоговом окне выводится суммарный минимальный индекс при найденном решении(Рис 10)

Рисунок 10: результат работы программы

5. Описание решения с использованием инструментальных сред

Для проверки правильности найденного решения при помощи математических методов, данная задача была решена при помощи инструментального средства Microsoft office excel. Решение было реализовано при помощи надстройки данного инструментального средства «Поиск решения».

Для решения данной задачи в excel были проделаны следующие действия:

1. Были созданы 2 таблицы (рис11) ; при этом в таблице 1 было  создано

Рисунок 11: Таблицы, созданные в excel:

6 строк и 6 столбцов, и все ячейки данной таблицы были заполнены значением 1,кроме 6 столбца и 6 строки. 2 таблица была заполнена исходными данными, по условию задачи.

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

3)Далее была произведена  настройка поиска решения следующим  образом:

Была выбрана ячейка целевой функции(см пункт 2), значение оптимизации- «минимум», в «изменяя ячейки переменных» были внесены все ячейки 1-й таблицы(Та что выше на рис 11) ,кроме ячеек 6 столбца и 6 строки, а также были заданы следующие ограничения : для каждой ячейки 6 столбца и 6 строки таблицы 1(рис 11,та что выше) допустимое значение =1;

для каждой ячейки с данными в таблице 1(рис11 та что выше) были заданы ограничения на каждое значение : >=0 и <=1(рис 12)

Рисунок 12 : настройка поиска решения

 
После этого была нажата кнопка «Найти решение», после чего был найден оптимальный план, целевая функция получилась  = 19, что совпадает с результатом, при решении этой-же задачи математическим методом.

6. Заключение

В курсовом проекте были рассмотрены следующие вопросы:

• Разработан алгоритм метода решения поставленной задачи;

• Написанная программа, пригодная для использования;

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

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

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

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

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

7. Литература

1.   Кузнецов Ю. Н. Математическое  программирование. – М.: Наука,1976.

3.   Вентцель Е. С. Элементы  динамического программирования. –  М.: Наука,1987.

3.   Беллман Р., Дрейфус  С. Прикладные задачи  динамического 

программирования. – М.: Наука,1965.

4.  Муну М. Математическое  программирование. Теория алгоритмов.  – М.:Наука,1990.

Приложения