Задачи вычислительные и функциональные.

Тема 1.2. Классификация задач, возникающих в практической деятельности

1. Основные понятия задачи: решение. Множество возможных решений, оптимальное решение, показатель эффективности.

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

Практические занятия.

Решение простейших однокритериальных задач. Методы решения многокритериальных задач.

***

Основные понятия задачи.

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

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

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

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

С формальной стороны задача состоит из условия и заключения, исходных (заданных) величин и искомых величин.

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

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

1. Рассматривается (анализируется) реальный объект.

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

4. Выбирается способы (компьютерные программы) которые в состоянии выполнить установленный алгоритм.

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

6. Выполняется проверка результата или отладка на реальном объекте. Проверка очень важный и ответственный момент. Способы проверки также разнообразны. Это: решение обратной задачи, решение задачи другим способом, установления соответствия полученного результата условию задачи и др.

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

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

 

Оптимальное решение, решение (вариант, выбор), которое по тем или другим признакам предпочтительнее других. (от лат. optimus наилучшее)

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

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

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

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

Показатель (значение) эффективности (относительный показатель эффективности операции, проекта, решения, процесса) определяется как частное от деления потенциального эффекта к её ресурсоемкости:

E=A:R, где E -эффективность, A - потенциальный эффект, R - ресурсоемкость.

Процедура определения эффективности является задачей идентификации.

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

Виды задач

1. Задачи простые и составные, прямые и обратные задачи. Такие задачирассматриваются в школьном курсе математики.

Задачи вычислительные и функциональные.

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

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

 

3. Задачи статические и динамические. Зависимость параметров задачи от времени.

Статическая задача – исходные значения заранее известны и не изменяются во времени или п араметры ее считаются неизменными на протяжении рассматриваемого периода,

По принятому допущению, вводимые в задачу параметры могут оставаться постоянными, не зависящими от времени,

При этом процедура принятия решения осуществляется один раз

Динамические задачи - в процессе решения параметры задачи изменяются во времени, параметры задачи являются функциями времени.

Решения осуществляется поэтапно и может быть представлено в виде процесса, зависящего от времени, в том числе непрерывно. Например, навигационная задача.

3. Детерминированные задачи и задачи в условиях неопределенности, За основу берется объем и точность исходной информации задачи

Детерминированная задача. Все параметры задачи заранее известны.

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

Задачи выбора в условиях определенности (детерминированные задачи) характеризуются наличием полной и достоверной информации о проблемной ситуации.

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

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

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

Недетерминированная задача (задачи в условиях неопределенности). Не все параметры задачи заранее известны.

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

Оптимальное решение недетерминированной задачи отыскать практически невозможно. Однако некоторое "разумное" решение отыскать можно, например, используя такие методы как:.

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

Метод экспертных оценок: собирается группа экспериментов, оценивается вероятность наступления каждого рода событий, даются свои оценки и их решения усредняются.

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

Раздел нашего курса "Исследование операций" рассматривает некоторые возможности нахождения ответов при решении таковых задач.

4. Стохастические задачи и задачи в условиях (полной) неопределенности. Задачи в условиях риска (вероятностные, или стохастические) из-за необходимости учета случайных факторов

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

Стохастическая задача. Не все параметры задачи заранее известны, но имеются статистические данные о неизвестных параметрах (вероятности, функции распределения, математические ожидания и т.д.).

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

- искусственное сведение к детерминированной задаче (неизвестные параметры заменяются их средними значениями),

- "оптимизация в среднем" (вводится и оптимизируется некоторый статистический критерий).

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

Критерий оптимальности может иметь любой вид, в том числе не формализуемый. Наиболее распространенные формализуемые критерии оптимальности заключаются в оптимизации (минимизации либо максимизации) одной либо нескольких скалярных целевых функций. Такие задачи будут рассматриваться в разделе "Линейное программирование"

5. Задачи дискретного, целостного, булева программирования.

Задачи дискретного программирования. Множество допустимых решений – дискретное множество.

Задачи целостного программирования. Множество допустимых решений – точки целочисленной решетки.

Задачи булева программирования. Множество допустимых решений - 0-1 матрицы

 

4. Однокритериальные и многокритериальные задачи, Задачи подразделяются по количеству целей (критериев) которым должны удовлетворять разрабатываемые решения.

Однокритериальные задачи ( одноцелевые) - в постановке задачи формулируется единственный критерий выбора решения,

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

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

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

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

Многокритериальные задачи (многоцелевые) - в постановке задачи формулируется более одного критерия, которые должны быть достигнуты одновременно.

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

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

В таких ситуациях имеет место так называемая целевая неопределенность, которая имеет такие особенности как:

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

2. На момент принятия решения отсутствует информация, позволяющая объективно оценить возможные последствия каждой альтернативы. Следовательно, оценка и принятие решений по многим показателям являются субъективными и полностью зависят от системы предпочтений лица, принимающего решение.

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

~ Поиска экстремума алгебраической функции-зависимости критерия от параметров системы y= ƒ(х). Для задачи с плавным изменением функции экстремум находится дифференцированием. Решение - конкретное численное значение;

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

~ Линейного программирования, когда критерий и условия, накладываемые на решение задачи, являются линейными функциями параметров (равенства или неравенства). Решение — численное значение;

~ Не линейного программирования;

~ Поиска вариантов решений методами полного или частичного перебора.

Практические занятия.

Задание 1. Расчетная задача кредитования покупки дорогостоящего объекта

Описание ситуации. Берется кредит на 5 лет для приобретения некоторого объекта (машина, квартира, дача и др.). Объект стоит X рублей (несколько сот тысяч рублей). Для кредитования имеются несколько возможностей.

Постройте расчетные таблицы по каждой из указанных возможностей кредитования и установите наиболее выгодный для Вас вариант. Значения X, P, Q, F указаны в таблице.

 

№ варианта

Xтыс. руб.

P%

Q%

F%

Возможности кредитования:

1. Кредит берется в банке № 5 г. Михайловка, ставка P% годовых. Ежемесячный платеж состоит из двух частей m=y+z. Первая часть y-постоянная и получается путем деления взятой суммы денег на число всех месяцев. Вторая часть z – начисляется на проценты за все года и делится на число всех месяцев.

2. Кредит берется в банке №10 г. Волгограде, ставка Q% годовых. (G<P). Ежемесячный платеж формируется аналогично банку Михайловки. Для погашения кредита ежемесячно надо будет ездить в Волгоград на автобусе не менее 300 рублей в один край. При этом можно воспользоваться почтой (банком) для ежемесячного перевода денег в Волгоград. При этом комиссия составляет 3%.

3. Кредит берется в Михайловке в частном банке №15 под F%. (F>P). Платеж формируется несколько иначе. Он также состоит из двух частей m=y+z. Первая часть y-постоянная и получается также путем деления взятой суммы денег на число всех месяцев. Вторая часть z – начисляется по иному. Ежемесячные проценты берутся из остаточной суммы, после выплаты за предыдущие месяцы и делится на число оставшихся месяцев.

4. По сети Интернет найдите условия кредитования в одном из банков Михайловка.

 

Задание 2. Магазин оргтехники получает товар из пяти фирм, расположенных в других городах. Установлено, что с увеличением расстояния до очередного города, цена уменьшается, но транспортные расходы увеличиваются. Составьте задачу о доставке группы товаров с не менее 10 наименований из этих городов.

Решите задачу с максимальной выгодой для магазина. Города, расстояния до них, товары, цены и другие параметры выберите в Интернете или придумайте самостоятельно, введя обозначения город-1, город-2 и т.д., товар-1, товар-2 и т.д.

 

Задание 3. Группа людей из нескольких человек (5-10) отправились в поход на несколько дней (3-5).. Составьте задачу (расчетную таблицу), включающую питание, проживание, транспорт и другие расходы.

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