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

Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется m поставщиков с запасами однородного груза в количестве и n потребителей, которым этот груз должен быть доставлен в объеме . Известно , i=1,2,,…,m, j=1,2,…,n – время, за которое груз доставляется от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и наибольшее время доставки всех грузов является минимальным.

Составим математическую модель этой задачи. Обозначим - объем перевозимого груза от i-го поставщика j-му потребителю. Система ограничений задачи не отличается от системы ограничений обычной транспортной задачи. Пусть Х=( ) i=1,2,,…,m, j=1,2,…,n – некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т(Х) наибольшее значение элементов матрицы Т=( ), i=1,2,,…,m, j=1,2,…,n, соответствующих клеткам таблицы, занятым опорным решением: Т(Х)= . Таким образом, за время Т(Х) план перевозок будет выполнен полностью. Математическая модель имеет вид

Т(Х)= (26)

, i=1,2,…,m , (27)

, j=1, 2, … , n, (28)

, i=1,2,,…,m+1, j=1,2,…,n. (29)

Задача решается в следующем порядке. Находится начальное опорное решение Х₁. определяется значение целевой функции Т(Х₁)= = . Все свободные клетки, которым соответствует значения >T(X₁), исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l₁, k₁), в которой достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l₁, k₁), расставляются поочередно знаки «-» и «+» и осуществляется сдвиг на величину = . Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х₂, на котором значение целевой функции меньше, чем на Х₁. далее снова пытаются разгрузить клетку, соответствующую Т(Х₂)= = . Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.

Тема 4. Принятие решений

Вопросы:

Принятие решений при многих критериях

1.Понятие многокритериальной задачи оптимизации.

2.Оптимальность по Парето.

3.Определение обобщенного критерия.

Принятие решений при неопределенности. Основные критерии.

1.Критерий крайнего оптимизма

2.Критерий Лапласа.

3.Критерий Вальда.

4.Критерий Сэвиджа.

5.Критерий Гурвица.

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

Методы принятия решений

Задачи принятия решений по степени определенности используемой информации делятся на три группы:

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

2. Задачи в условиях вероятностной определенности (принятие решений в условиях риска);

3. Принятие решений в условиях неопределенности.

1. В детерминированных задачах вся исходная информация определена полно и однозначно.

Отсюда возможно и принятие единственно правильного решения и точное его выполнение.

2. Принятие решения в условиях вероятностной определенности и риска.

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

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

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

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

Не всегда можно пренебрегать случайностью.

Например. Мы ведем расчеты по организации в городе службы «Скорой помощи». Число вызовов и время обслуживания – это случайные величины. Заменив их средними значениями, мы определим сколько требуется машин, врачей, сотрудников, чтобы прибытие на вызов в среднем составило не более 15 минут. Но это будет в среднем.

Где гарантия, что к какому-то больному скорая помощь приедет через 15 минут, а не через час? Гарантий нет, есть условия риска.

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

3. Существует и третий тип задач:

Принятие решений в условиях неопределенности (игры с природой)

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

Такая ситуация возникает в основном по двум причинам:

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

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

Эта неопределенность информации порождает неопределенность в принимаемых решениях.

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

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

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

Первая ситуация – полная неопределенность.

Это не означает, что в задаче вообще ничего не известно.

Известны:

а) Проблема требующая решения.

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

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

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

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

Пример. В задаче имеются 4 допустимых альтернативы или стратегии А1, А2, А3, А4. Возможны 3 состояния природы П1, П2, П3. Цифры в таблице означают величину выигрыша при каждой стратегии для каждого состояния природы.