Щербаков Б.Г., Попов А.А. Информационные технологии

Глава 2. Решение задач в условиях неопределенности

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

1. Детерминированные. В них фактор неопределенности отсутствует

2. Стохастические. Содержат фактор неопределенности

3. Нерегулярные. Содержат нерегулярный фактор неопределенности

Рассмотрим их подробнее.

§2.1 Детерминированные задачи

В этом случае условия α(х) операции полностью заранее известны

(отсутствует неопределенность), известна также ее эффективность W, которая

зависит только от них. Условия операции обозначим через вектор а. Он зависит

также и от ограничений на х и от самого вектора фазовых координат х

W=W(а,х) (1.1)

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

образом

W*=max [W(a,x)] (1.2) на множестве х

это означает, что при х=х* функция W=W* обращается в максимум

(минимум). Обобщая, можно сказать, что если х* - функция, то это типичная

вариационная задача, когда ищется не числовое значение х*, как в

классическом математическом анализе при определении экстремума, а

структура х*, которая доставляет экстремум функционалу W=W* на множестве

функций х=х*. При выборе метода поиска экстремума и связанного с ним

оптимального решения х* должны учитывается особенности функционала W и

виды ограничений а.

Если W и а линейны по х, то используют методы и алгоритмы линейного

программирования.

Если W выпуклая функция, то используют методы выпуклого

(квадратичного) программирования. Для многоэтапных операций применяют

динамическое программирование. Для определения W* разработаны пакеты

удобных численных методов.

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

трудностей при поиске оптимума показателя эффективности W*.

§2.2 Стохастические задачи

А. Стохастическая неопределенность

В этих условиях W дополнительно зависит от неизвестных факторов -

неопределенности ξ, тогда w=w(а,х, ξ). Задача поиска оптимальных решений

теряет прежний смысл и ищется х* € Х, который дает W= maxW. «Этот» х* в

общем случае хуже, чем в детерминированном случае, так как его уменьшает

неопределенность. Для решения этого типа задач разработан ряд методов,

различающихся природой ξ.

Если ξ – случайные величины (функции) с известными статистическими

характеристиками, то такие задачи называются стохастическими, а ξ –

стохастическая неопределенность. В этих условиях это лучшее что может

быть.

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

ремонта технологической линии. В этом случае неопределенность ξ –

характеризует отказы оборудования. Частоту и длительность возникновения

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

данный момент величина, то искать ее максимум бессмысленно.

Напрашивается мысль заменить ξ одним или несколькими (в зависимости

от задачи) средними значениями – математическими ожиданиями ее элементов,

тогда задача становится детерминированной и все решается.

Такой подход допустим и его используют если переменные мало

отклоняются от своего мат.ожидания (мал разброс значений), т.е. дисперсия

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

следующего примера.

Пример.

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

ее приема на другом корабле. Управление возможно как в автоматическом, так

и в ручном режиме. При выполнении этой операции возможны сбои и

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

ошибки сближения достаточно мала, а мат.ожидание равно нулю, но, тем не

менее, принять вероятность сближения W за 1 нельзя, так как это будет

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

необходимость резерва топлива на сближение, а это, в принципе, неверно.

Аналогичный пример.

В тире за попадание в десятку платят 10 рублей. Студенту надо

заработать 100 рублей. Сколько раз он должен выстрелить?

Если примем вероятность попадания W в десятку за 1, то 10 раз. Но W

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

необходимо не менее 10 выстрелов.

И, наконец, последний вариант ξ – существенно случайна, а,

следовательно, также и существенно случайная величина W. Как быть в этом

случае?

Заслуживает внимание попытка заменить не ξ его средним значением, а

вероятность W и принять W=W среднее

W=Wсредн=М [W], т.е. осредненное значение W по

условиям (а) и выбирать такое значение, при котором

М [W(а, ξ,х)]=>max

Таким образом, принимается за показатель эффективности среднее

значение W по а

W= М[W]

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

Например, рассматривается не просто «расход», «доход», «время», а их средние

значения. Такой подход применим если операция обладает свойством

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

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

этим существует класс задач, которые не обладают такими свойствами,

поэтому прием оптимизации в среднем необходимо дополнить

стохастическими ограничениями – иначе может быть катастрофический итог.

Пример.

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

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

время ожидания было минимальным и вместе с тем не превосходило заданной

величины Т

max

Если использовать оптимизацию в среднем, то получим в среднем

минимальное время обслуживания. Ясно, что при этом может быть время Т

превосходящее заданное T

max

, т.е. t>Т

max

, что недопустимо. В тоже время, так

как t случайная величина, нельзя потребовать, чтобы t ≤T

max

, т.е. жестко не

превосходило T

max

. В таких условиях требование можно записать так

P (t ≤T

max

) ≥ β,

и непременно потребовать, чтобы вероятность события t ≤ T

max

выполнялось с

возможно более высокой вероятностью. Например, если принять β=0,9999, то

такое событие будет практически достоверным. Такое введение ограничения на

время исключают решения, которые ему не удовлетворяют. Эти ограничения

называются стохастическими. Они, как правило, значительно осложняют

решение задач оптимизации.

Таким образом, необходимо обращать внимание на то, что

использование оптимизации в среднем в единичной реализации может

допустить малые значения W. Поэтому, если такой подход использовать для

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

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

избежать.

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

при котором

М [W(а, ξ,х)]=>max,

Таким образом, за показатель эффективности принимается среднее значение

W(а) и выбирается х, дающий max M[W]

§2.3 Нерегулярные задачи

При решении практических задач встречаются случаи, когда

характеристики распределения вероятностей для ξ существуют, но в данный

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

существуют. Тогда априори задаются характеристики ξ и все сводят к

решению детерминированной задачи. Это означает, что задаются их

возможными средними значениями и решают детерминированную задачу на

множестве принятых величин.

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

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

диапазону исходных данных, а не только одному из них.

В настоящее время подобные методы разрабатываются в теории игр и

статистических решений в конфликтных ситуациях, а также в задачах max min,

min max и в принципах получения гарантированного результата.

При поиске оптимальных решений в этих условиях представляют

определенный интерес адаптивные алгоритмы. Их сущность состоит в том,

что выбирают любое решение х рассматриваемой задачи и назначают в нем

свободные переменные. После чего проводят расчеты, меняя свободные

переменные, и наблюдают, как при этом меняется функция W. Таким путем

«нащупывают» изменения, которые дают рост эффективности.

При отсутствии необходимых оценок и функциональных зависимостей

привлекается метод экспертных оценок, основанный на опросе

(анкетировании) специалистов и последующей обработке полученной

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

В третьей и последующих главах рассматриваются конкретные классы

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

использованием принципов и возможностей современных информационных

технологий, и в частности широко распространенных программ имитационного

математического моделирования Mathcad.

Тесты

Что такое детерминированные задачи?

1. Содержат небольшое число случайных величин

2. Содержат случайные величины с известными характеристиками

3. Не содержат случайных величин

Что означает «условие неопределенности»?

1. Имеются случайные величины 2. Отсутствуют начальные данные

3. Отсутствует критерий 4. имеется случайная функция

Что такое стохастическая задача?

1. Случайные величины равны нулю 2. Случайные величины не равны

нулю 3. Известны не все характеристики случайных величин

4. В задаче большое число переменных

В каких случаях задачи являются нерегулярными?

1. Содержат большое число случайных величин 2. Случайные величины

взаимозависимы 3. Задачи содержат случайные переменные,

характеристики которых неизвестны

Как приближенно решаются регулярные задачи?

Случайные величины заменяются: 1. Математическим ожиданием 2.

дисперсией 3. Среднеквадратическим отклонением

Вопросы:

1. Что такое стохастические задачи?

2. Что такое стохастическое ограничение?

3. Что означает нерегулярность задачи?

Глава 3. Исследование и решение распределительных задач

В этом классе задач рассматривается ограниченное количество ресурсов,

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

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

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

можно разделить:

• по виду целевой функции - на линейные и нелинейные. Если затраты

(доход), определяемые объемом x

ресурса i, выделенного на выполнение

работы j, равны x

, то задача линейна, а в противном случае нелинейна;

• по имеющимся в наличии необходимым ресурсам - на сбалансированные

(закрытые) и несбалансированные (открытые). Если общий объем наличных

ресурсов равен общей потребности в них, то имеет место сбалансированная

(закрытая) распределительная задача, в противном случае она не

сбалансирована (открыта);

• по характеру изменения переменных - подразделяются на три класса:

- если все переменные при решении могут принимать любое значение из

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

будем относить к классу задач с непрерывным изменением переменных;

- если на все переменные или на их часть наложено дополнительное

требование целочисленности, то мы имеем дело с целочисленными

распределительными задачами;

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

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

(например, количество единиц продукции разных видов), то перед нами

дискретная задача оптимизации;

• по количеству экстремумов у целевой функции - на одноэкстремальные и

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

локальный оптимум целевой функции на множестве допустимых планов

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

экстремальным. При наличии в задаче многих локальных экстремумов она

называется многоэкстремальной;

• по характеру распределения ресурсов во времени - на статические и

динамические. Если распределительная задача не связана со временем или

каждое последующее распределение не зависит от всех остальных, то задача

называется статической, в противном случае - динамической.

Рассмотрим решение в системе Mathcad некоторых распределительных

задач.

§3.1 Общая задача линейного программирования (ОЗЛП)

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

Допустим, на предприятии после модернизации производства появился

свободный ресурс времени оборудования. Предлагается организовать

изготовление новых изделий нескольких наименований. Известно время,

требуемое на создание каждого изделия на каждом виде оборудования,

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

от выпуска каждого изделия.

Выявление основных особенностей и закономерностей.

Количество изделий j-го наименования, которое может производить

предприятие, обозначим за

. Зная требуемое количество каждого вида i-го

ресурса для изготовления каждого j-го типа изделия – норму расхода

количество каждого i-го ресурса

имеющегося в наличии на предприятии, -

можно записать в общем виде следующую систему неравенств:

· х

+ с

· х

+…+с

· x

+…+c

· x

≤ a

…………………………………………..

· х

+ с

· х

+…+с

· x

+…+c

· x

≤ a

…………………………………………..

· х

+ с

· х

+…+с

· x

+…+c

· x

≤ a

Критерий оптимизации – максимальная прибыль – может быть записан в

таком виде:

f(x)=P

·x

+ P

· x

+…+ P

· x

+…+P

· x

Рассмотрим на конкретном примере решение данной задачи. Пусть

система ограничений* выглядит следующим образом:

3х

+5х

+ 2х

+ 7х

≤ 15

4х

+3х

+ 3х

+ 5х

≤ 9

5х

+6х

+ 4х

+ 8х

≤ 30

Критерий оптимизации – суммарную прибыль – можно представить так:

f(x)= 40

+50

+ 30

+ 20

Решение задачи в системе Mathcad

Для решения данной задачи:

 введите целевую функцию

f(x)= 40

+50

+ 30

+ 20

;

 введите матрицу коэффициентов системы неравенств. Для чего:

- задайте имя матрицы, например М, и знак присваивания;

- нажмите комбинацию клавиш Ctrl + M. Появится диалоговое оно Insert

Matrix (вставить матрицу)

- введите в первое текстовое поле Rows (строки) число 3 (три исходных

ресурса)

- введите во второе текстовок поле Columns (столбцы) число 4 (четыре

изделия)

- щелкните по кнопке ОК. Появится шаблон матрицы

∎

∎∎

∎

∎∎

∎

∎ ∎

∎

∎∎

∎

М :=

∎

∎∎

∎

∎∎

∎

∎∎

∎

∎∎

∎

∎∎

∎

∎∎

∎

∎∎

∎

∎∎

∎

* - матрица задачи определяется шифром студента

- установите указатель мыши в метку шаблона матрицы и введите

соответствующий коэффициент системы неравенств. Аналогичным

образом заполните остальные метки шаблона матрицы:

3 5 2 7

М := 4 3 3 5

5 6 4 8

 введите вектор коэффициентов правой части системы неравенств, для

чего:

- введите имя вектора, например v, и знак присваивания

- нажмите комбинацию клавиш Ctrl + M. Появится диалоговое оно Insert

Matrix

- введите в первое текстовое поле Rows (строки) число 3 (три исходных

ресурса)

- введите во второе текстовок поле Columns (столбцы) число 1

- щелкните по кнопке ОК. Появится шаблон вектора

∎

∎∎

∎

v :=

∎

∎∎

∎

∎∎

∎

- поставьте указатель мыши в метку шаблона вектора и введите

соответствующий коэффициент правой части системы неравенств:

15 15

v :=

30 30

Аналогичным образом заполните остальные метки шаблона вектора. Для

решения задачи в системе Mathcad:



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

например:

:=0

 введите ключевое слово Given (Дано)

 введите систему неравенств в матричном виде:

М · х ≤ v

 введите граничные условия:

х ≥ 0

 введите имя искомого вектора оптимальных параметров, например

xopt, знак присваивания и имя встроенной функции,

обеспечивающей максимизацию целевой функции – maximize

xopt := Maximize (f, x)

Далее определяются искомые оптимальные параметры:

 выведите искомые оптимальные значения. В нашей задаче они

будут такими:

xopt := 3

0 ∎

∎∎

∎

 определите максимальную прибыль:

f (xopt) = 150 ∎

∎∎

∎

На рис представлено решение данной задачи с использованием блока

Given – maximize.

При анализе результатов решения этой задачи видно, что предприятие в

данных условиях должно выпускать только второе изделие в количестве трех

единиц. При этом будет получена максимальная прибыль равная 150 единицам.

§3.2 Задачи о назначении

Рассматриваемую задачу «о назначении», отнесем, также как и ОЗЛП, к

так называемым, «распределительным задачам».

Рассмотрим пример.

Как правило, рассматривается ограниченная величина ресурсов, которых

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

максимального эффекта.

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

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

эффект. Например, минимум затрат, минимальное время на изготовление или

проектирование какой-либо системы и т.д.

Распределительные задачи можно разделить на группы:

• по виду целевой функции – на линейные и нелинейные. Линейные, если

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

Нелинейная – в противном случае.

• в зависимости от объемов необходимых ресурсов – на

сбалансированные и несбалансированные.

• по характеру изменения фазовых координат – с непрерывными

фазовыми координатами, целочисленными ФК

• по количеству экстремумов целевой функции

• по характеру изменения ресурсов во времени – на статические и

динамические

В конструкторском бюро требуется разработать проект системы

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

Примем, что система состоит из n блоков Б(j), к их проектированию может

быть привлечено n групп конструкторов К(i). Будем считать, что нам

известно время, затрачиваемое i-ой группой конструкторов на разработку

j-ого блока. i=1,2,..,n j=1,2,..,n. Требуется определить какие группы

конструкторов должны разрабатывать тот или иной блок, чтобы

суммарное время проектирования (подготовки эскизного проекта системы

управления) было минимальным. Исходной информацией является

матрица затрат (матрица – задание).

За основу принимается матрица задачи-примера

50 30 20

= 20 40 40

40 70 50

см.рис 3.2.1.

Элементы матрицы-задания

- две последние цифры шифра студента

= 40+первая из двух последних цифр шифра

= 50+вторая из двух последних цифр шифра

Остальные цифры остаются без изменения

Матрица-задание

Решение задачи состоит из следующих основных этапов:

Выявление основных особенностей, взаимосвязей и количественных

закономерностей

Введем переменные X(i,j), которые равны 1, если i-я группа разрабатывает

j-й блок, и 0, если она не разрабатывает. Сформулируем ограничения:

1. Каждая группа может разрабатывать только один блок. Это ограничение

можно записать в таком виде:

∑

1j)X(i,

, (i = 1, 2, ..., m) (1)

2. Каждый блок может проектироваться только одной группой. Это

ограничение можно записать так:

∑

1j)X(i,

, (j = 1, 2, ..., m) (2)

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

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

Обозначим через Y(i,j) себестоимость разработки j-го блока i-ой группой.

Тогда критерий оптимизации Y – условная себестоимость разработки всех

блоков -запишется в таком виде:

∑∑

= =

j)j)X(i,Y(i,Y

(3)

Совокупность ограничений (1), (2) и целевой функции (3) образует

математическую модель типичной экстремальной комбинаторной задачи. Ее

решение представляет собой некоторую перестановку чисел, причем

Б(1) Б(2) Б(3)

К(1)

30 70

К(2)

20 а

К(3)

40 70 а

Щербаков Б.Г., Попов А.А. Информационные технологии

Подождите немного. Документ загружается.