26492

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

Реферат

Менеджмент, консалтинг и предпринимательство

Первая категория – задачи с неделимостями. Вторая категория – комбинаторные задачи. задачи теории расписаний упорядочение планирование согласование. Третья категория – задачи сводящиеся к задачам дискретного программирования.

Русский

2013-08-18

24.47 KB

13 чел.

Принятие решений в задачах с детерминированными целочисленными параметрами.

  1.  Классификация задач принятия решений с детерминированными целочисленными параметрами.
  2.  Постановка задач для некоторых типов задач.
  3.  Схема решения задач методом ветвей и границ.

Классификация задач принятия решений.

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

Первая категория – задачи с неделимостями. Отличительной особенностью этих задач является неделимый характер искомых переменных. К этому типу задач относятся: задача планирования выпуска неделимых видов продукции и задача ограниченного объема (задача о ранце).

Вторая категория – комбинаторные задачи. К этим задачам относятся:

- задача назначения.

- задачи теории расписаний (упорядочение, планирование, согласование).

- задача коммивояжера.

- задача минимального покрытия графа.

Характерной особенностью комбинаторных задач является необходимость поиска наилучшего подмножества объектов среди структурированного конечного множества альтернатив. Структурные особенности заданного конечного множества альтернатив являются исходной предпосылкой для построения некоторого системно упорядоченного метода решения.

Третья категория – задачи, сводящиеся к задачам дискретного программирования. Сюда относятся транспортная задача и задача планирования и размещения объектов.

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

2.1 Постановка задачи планирования выпуска неделимых видов продукции

Допустим заданы 2 множества I={1,2…im}- множество производственных факторов учитываемых при решении задачи, J={1,2…jn} – множество видов конечной продукции.

Общие условия для решения этой задачи:

  1.  Продукты всегда являются неделимыми и физический смысл имеют только целые значения;
  2.  Определен ряд дополнительных условий и коэффициентов, например aij – количество производственных факторов i типа необходимых для производства единицы продукции j типа, bij – количество ресурсов i типа, находящихся в наличии для производства продукции j типа, cj – прибыль, получаемая от единицы j продукта.

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

Математическая постановка задачи.

Критерий оценки результата решений

Математическое описание ограничений

(i=1…m), xij≥0

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

2.2 Постановка задачи ограниченного объема (задача о ранце)

В общем плане задача формулируется следующим образом путешественник собираясь в поход должен выбрать набор предметов, которые в наибольшей степени будут ему полезны в походе, но они должны поместиться в ограниченный объем рюкзака. Задано множество предметов I={1,2…im}.

Общие условия:

  1.  Предметы являются неделимыми;
  2.  Для одномерной задачи определен коэффициент полезности каждого предмета ci;
  3.  Определен объем каждого предмета ai (i=1…n)

Цель задачи: определить наиболее эффективный набор предметов при условии ограничения на предельный объем ранца b.

Математическая постановка задачи

Вводится некая переменная xi которая равна 1, если i предмет включен в состав груза и xi=0, если не включен.

Критерий оптимальности решения:

Математическое описание ограничения

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

2.3 Постановка задачи о назначении

Задано множество работ

А={A1 AiAn}

Задано множество исполненных этих работ

В={B1… BjBm}

И определена матрица эффективности

C=||Cij|| , где элементы матрицы Cij задают значения эффективности выполнения i-ой работы j-ым исполнителем.

Общие условия:

  1.  Для упрощения задачи предположим, что количество работ равно количеству исполнителей
  2.  Определены ограничения. Каждая работа выполняется одним исполнителем, один исполнитель выполняет одну работу.

Цель: распределить работы по исполнителям, что бы суммарная эффективность выполненных всех работ была максимальной.

Математическая постановка:

Вводится меременная: xij=1, если i-я работа назначена j-му исполнителю,  xij=0, то работа не назначена.

Критерии оптимизации решения

Математическое описание ограничений

                                          i=1…n                               j=1…n   

В результате решения в матрице эффективности Cij в каждой строке и в каждом столбце должен быть выбран только один элемент и сумма выбранных элементов должна быть максимальной.

2.4 Постановка задачи Комивояжера.

Множество объектов сети , которые необходимо объехать бригаде тех обслуживания

А={A1 AiAn}

Общие условия

Точка нахождения бригады может быть либо на одном из углов сети , либо на отдельном узле. Задана матрица эффективности C=||Сij||

Элементы матрицы задают значения функции , затраченной при переезде бригады из пункта Аi в пункт Aj.

Заданы ограничения

Бригада выезжает в каждый пункт сети только 1 раз

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

Математическая постановка задачи

Xij=1, если бригада переезжает из Аi в Аj, Xij=0, если поездки не было.

Критерии оптимизации решения

Математическое описание решений

                                          i=1…n                               j=1…n   

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

2.5 Постановка задачи минимального покрытия графа

Задан граф, содержащий множество вершин и множество ребер.

I={ 1…in }

J ={1…jn }

В задаче каждому ребру присваивается коэффициент стоимости Cj. Взаимосвязь между вершинами и ребрами задана матрицей А=||aij|| - матрица инциденции. Элементы матрицы aij=1, если i не вершина , связанная с j ребром , aij=0 , если в противном случае. Другими словами aij=1, если j-столбец матрицы покрывает i-ую строку.

Общие условия

Покрытием графа называется такое подмножество ребер, в котором каждая вершина связана хотя бы с одним ребром , входящего в покрытие.

Покрытие называется минимальным, если содержится минимальное количество ребер.

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

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

Математическая постановка задачи.

Вводится переменная Xj=1, если j-ребро, входящее в покрытие, 0 в противоположном случае.

Коэффициент эффективности

 

Математическое описание ограничений

2.6 Постановка транспортной задачи

Задано множество поставщиков некоторого вида продукции I={1,2…im} и множество потребителей этой продукции J={1,2…jn}. Также задана матрица стоимости перевозки единицы продукции от i поставщика j потребителю .

Общие условия:

Ограничения:

  1.  Наличный запас продукции у i поставщика bi;
  2.  Требуемое количество продукции в j пункте dj.

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

Математическая постановка задачи

Математическое описание ограничений

, что означает наличные запасы продукции у i поставщика больше, чем требуется для j пункта потребления

, потребности j потребителя не больше, чем может поставить I поставщик.

Для упрощения задачи можно ввести дополнительное ограничение

это означает, что общий запас продукции у поставщиков равен потребностям потребителей.


 

А также другие работы, которые могут Вас заинтересовать

54336. Текстові формули (функції) Microsoft Excel (MICROSOFT OFFICE 2010) 263.5 KB
  Необхідно використовуючи текстові функції заповнити даними таблицю № Автор Назва книги Видавник Кількість сторінок. формат запису функції НАЙТИискомый_текст; просматриваемый_текст; начальная позиция в якості результату повертає позицію початку пошукового рядка тексту який міститься в даному рядку текста.
54337. Методичний конструктор як техніка підготовки педагогів до впровадження директивних інновацій 59.5 KB
  Цей методичний захід має бути необхідний закладу та учителям легкий у виконанні не обтяжуючий учасників заходу і водночас корисний Для цього треба не забувати про особливості навчання дорослих людей які мають свій досвід свої погляди на себе та оточуючий світ на розвиток себе в професії і суспільстві. Подруге підійдіть до розробки заходу дуже ретельно хоча на сучасному етапі саме розробка дійсно якісного методичного заходу не завжди є проблемою для цього є маса літератури з даного приводу але до технік що обираються треба...
54338. Використання методу проектів на уроках інформатики 187 KB
  Тема: Комп’ютерні презентації Проект: Я інформую Тип проекту : інформаційнотворчий. Очікуваний результат: створення презентації засобами MS PowerPoint. Порада Перед створенням презентації бажано: Визначити тему та призначення презентації Створити схему сценарій презентації Спланувати зміст усіх слайдів їх стиль. ДОДАТКОВІ ВИМОГИ ДО ЗМІСТУ ПРЕЗЕНТАЦІЇ ЗА Д.
54339. ВИКОРИСТАННЯ ПРОЕКТНИХ ТЕХНОЛОГІЙ НА УРОКАХ МАТЕМАТИКИ ЯК ЗАСІБ АКТИВІЗАЦІЇ ПІЗНАВАЛЬНОЇ ДІЯЛЬНОСТІ УЧНІВ 107.5 KB
  Дуже важливою також є структуризація змістовної частини проекту із зазначенням поетапних результатів. Необхідною складовою методики здійснення проектної діяльності є складання загальної моделі що розглядається як умовний образ схема кінцевого результату проекту. Першим із них передбачено виконання завдань навчального проекту та здійснення презентації кінцевого інтелектуального матеріального продукту безпосередньо на уроці або під час проведення серії уроків з певної теми. Водночас педагогічна функція вчителя ускладнюється порівняно з...
54340. Метод проектів на уроках інформатики 78.5 KB
  Історія виникнення методу проектів Місце методу проектів у навчальному процесі Формування проектних компетенцій Метод проектів на уроках інформатики Висновки Використані джерела Вступ Сучасну практичну діяльність людства науковотехнічний та культурний прогрес у різних сферах суспільного буття неможливо уявити без проектування і проектів. Історія виникнення методу проектів Використання у навчальновиховному процесі методу проектів не є новим для українських шкіл. Першим увів поняття метод проектів...
54341. Культура Европы в XX - начале XXI вв.: противоречия и проблемы 28.21 KB
  Таким образом процесс подготовки и проведения такого учебного занятия как комбинированный урок увлекает студентов активизирует их достаточно свободно пользоваться простыми языковыми средствами в основных видах речевой деятельности: говорении аудировании чтении и письме. ФГОУ СПО Чебоксарский техникум строительства и городского хозяйства МЕТОДИЧЕСКАЯ КАРТА ЗАНЯТИЯ Дисциплина: Английский язык Группа: С41 Преподаватель: Бутакова Л. Тема занятия: Строительство зданий и сооружений Тип и вид занятия: комбинированный Цели занятия...
54342. Методические основы использования прикладного ПО на уроках в школе 111.5 KB
  Деление на группы производят либо по способностям либо случайным образом например по партам или по алфавиту. В этом случае как правило формируются разно уровневые группы в которых быстро определяются лидеры и аутсайдеры. Гузеев предложил различать группы выравнивания поддержки и развития. Группы выравнивания состоят из учащихся с различной успеваемостью и ориентированы на достижение всех ее участников обязательного уровня образования; группы поддержки однородны по успеваемости; в группах развития ученики более высокого уровня...
54343. Дмитриу Донской. Куликовская битва 83 KB
  Что позволило Дмитрию Ивановичу открыто выступить против монголотатар и разгромить их 12 октября 1350 года у московского удельного князя Ивана родился сын которого окрестили Дмитрием. Дмитрия Московского сумели получить для своего князя ярлык. Разведка великого князя донесла что Мамай собрав войско уже три недели ждал на Дону Ягайло Литовского.
54344. Сучасний урок - джерело творчості вчителя 2.78 MB
  €œТестові завдання з геометрії. клас із використанням тестуючого комплексу MIFTests. Кожен вчитель є справжнім керівником дитячого колективу діти визнають своїх педагогів за лідерів та активно співпрацюють із ними а це означає: вчитель має власний педагогічний імідж свій особливий педагогічний почерк він – конкурентоспроможний компетентний фахівець. МАТЕМАТИКА ТА ІТК У сучасному світі потреба в комп’ютерних технологіях постійно зростає – вони необхідні і вдома і на робочому місці. Систематичне використання...