Метод ветвей и границ
Задача для 3х станков.
Дано:
N деталей, обрабатываемых последовательно на 3-х станках. При этом существует нормативная длительность обработки на каждом из станков.
- ai – длительность обработки i-детали на 1-ом станке
- bj – на 2-ом станке
- ci – на 3-ем станке
Требуется:
Найти расписание, в котором сумма затрат времени на выполнение всех работ стремится к минимуму. C-расписание; Сn = (i1, i2, …, ik,…, in), i – номер работы в расписании, k-место работы в расписании.
Метод ветвей и границ (МВГ)
Решение описывается с помощью алгоритма МВГ, который является циклическим и состоит в построении оптимальных перестановок работ и включает 3 главных действия:
1) Решение одного или нескольких вспомогательных задач для отыскания нижней границы критерия оптимальности;
2) Выбор текущей перестановки Сk, где к=1,2,…, k, который имеет min нижнюю границу;
3)
Ветвление, продление, перестановки Сk
по правилу Сk+1
=
(Сk,
j),
Блочный алгоритм ветвей-границ:
Оптимизация решений с использованием теории статистических решений (тср)
Предположение, что отсутствует противодействие ЛПР, а неопределенность ситуации обусловлены неполным знанием действительности со стороны ЛПР.
Рассмотрим критерии и процедуры принятия решений для 2-х случаев:
Когда ЛПР неизвестны.
Когда ЛПР имеют более полную информацию по влиянию внешней среды, т.е. знает вероятности тех или иных влияний окружающей среды.
Случай 1.
- ЛПР имеет информацию о возможных состояниях внешней среды
- ЛПР не имеет информации о том состоянии, которое реализуется в настоящий момент.
Дано:
- множество состояний внешней среды: Е1, Е2,...,Еj,...Ed
- варианты возможных решений, которые выбирает ЛПР. A1, A2, Ai,...,Am.
- ЛПР может количественно оценить эффективность вариантов решений. Аi:
yij=fj(Ai), где j=1,d; i=1,m. Здесь fi — частная функция (полезность) i-ого варианта решений
Требуется:
- выбрать оптимальный вариант решения А*.
Процедура оптимального выбора решения в условиях полной неопределенности (случай 1) опирается на следующую матрицу частных эффективностей вариантов решений:
Ai\Ej |
E1 |
... |
Ej |
... |
Ed |
A1 |
y11 |
... |
y1j |
... |
y1d |
.... |
... |
... |
... |
... |
... |
Aj |
yi1 |
... |
yij |
... |
yid |
... |
.. |
... |
... |
... |
... |
An |
ym1 |
... |
ymj |
... |
ymd |
Функция fj(Ai) характеризует возможность достижения цели (возможный доход, который может быть получен) при выборе решения Ai при состоянии среды Ej
Примечания.
В некоторых задачах решений вместо функции эффективности применяют функции потерь, которая аналогичная функция эффективности.
Процедура принятия решений в данном случае строится по аналогии с решением задач векторной оптимизации путем построения обобщенного критерия оптимальности, при этом функции частной эффективности аналогичны частным критериям векторной оптимизации.
Рассмотрим возможные обобщенные критерии и правила выбора оптимального решения для случайных вариантов.
1) Критерий и правило принятия решений исходя из равнозначности влияния внешней среды — критерий Лапласа. Математическая запись выглядит следующим образом:
Рекомендация для ЛПР состоит в том, что следует выбирать тот вариант Ai, который имеет максимальную среднюю эффективность
2)Критерий и правило оптимизма.
Данное правило ориентирует ЛПР на выбор решения по максимальной эффективности. Поэтому называется правилом оптимизма.
3) Критерий и правило принятия решений оптимизма.
4) Критерий и правило пессимизма
(критерий Вальда).
5) Критерий Сэвиджа
6) Критерий взвешенного оптимизма-пессимизма (кр. Гурвица)
Пример
Выбор наилучшего проекта строительства предприятия.
-Известно 5 вариантов строительства А1, А2,...,А5. Качество этих вариантов оценивается экспертами.
Критерии:
-f1-расчетная прибыль
-f2-затраты на строительство
-f3-экологический ущерб от строительства
-f4-удволетворенность жителей района или города
Каждый из этих критериев оценивается по 5 бальной шкале
В результате была построена следующая таблица принятия решений
A\E |
E1 |
E2 |
E3 |
E4 |
1 |
2 |
3 |
4 |
5 |
6 |
A1 |
4 |
3 |
4 |
3 |
3.5 |
4 |
3 |
1 |
1 |
3.5 |
A2 |
5 |
3 |
3 |
3 |
3.5 |
5 |
3 |
3 |
1 |
4.0 |
A3 |
2 |
4 |
2 |
4 |
3.0 |
4 |
2 |
2 |
3 |
3.0 |
A4 |
5 |
3 |
2 |
3 |
3.25 |
5 |
2 |
2 |
2 |
3.6 |
A5 |
4 |
4 |
3 |
4 |
3.75 |
4 |
3 |
3 |
1 |
3.5 |
1 — правило лапласа
2 — правило оптимизма
3 — правило осторожности
4 — правил пессимизма
5 — правило Сэвиджа
6 — правило Гурвица
Окончательное решение по данному примеру выбирает ЛПР основываясь на сравнении математических схем и полученных вариантов решений