- •Характеристики операционных систем фирмы Microsoft
- •Принципы системного подхода в моделировании систем.
- •Классификация видов моделирования систем
- •Мысленное моделирование:
- •Производственный эксперимент.
- •Комплексные испытания.
- •Матрица автомата
- •Исходные понятия теории принятия решений.
- •Линейное программирование
- •Алгоритм симплекс-метода
- •Замечание.
- •Транспортная задача
- •Методы построения опорных решений
- •Метод минимального элемента
- •Составим опорное решение методом минимального элемента
- •Условие оптимальности выполняется, поэтому получено оптимальное решение
- •Задачи нелинейного программирования (знлп) знлп – это задача вида
- •Метод Франка-Вульфа: Если ƒ(x1, x2, …, xn)→max и является вогнутой функцией на выпуклом множестве ω, т.Е
- •Метод штрафных функций:
- •Принятие решений в условиях риска (в условиях неопределенности Теория игр
- •Методы решения задач теории игр с нулевой суммой
- •1 По цели и характеру решаемой задачи:
- •2 Стадии приобретения знаний
- •Нейронные сети: обучение без учителя
- •Нейронные сети Хопфилда и Хэмминга
- •Продукционные модели
- •Логический вывод
- •Зависимость продукций
- •Продукционные системы с исключениями
- •Системы распознавания образов (идентификации) Понятие образа
- •Проблема обучения распознаванию образов (оро) возникла при изучении физиологических свойств мозга.
Методы построения опорных решений
Метод северо-западного угла.
Начинаем заполнение с клетки (1,1) – С-З угол, либо удовлетворяя потребность, либо исчерпывая запасы в этом пункте. Затем переходим в следующий столбец или строку, что зависит от наличия потребности и запасов, идя как бы по диагонали таблицы заканчиваем заполнение в клетке (m,n), таким образом, будет получено опорное решение.
Метод минимального элемента
Среди всех клеток выбираем клетку с наименьшим тарифом Cks и начинаем заполнение с этой клетки, либо удовлетворяя потребность, либо исчерпывая запасы (если таких клеток несколько, то заполняем все эти клетки). Затем переходим к заполнению клеток с большими по величине тарифами, пока полностью не исчерпаем запасы или не удовлетворим потребности.
Замечание: Если заполненных клеток оказалось меньше чем m+n-1, то к полученному набору дописывают в некоторых клетках «0», так чтобы общее количество заполненных клеток стало m+n-1.
Алгоритм решения транспортной задачи методом потенциалов.
Построить опорное решение транспортной задачи тремя описанными выше методами. Для каждого опорного решения найти значение целевой функции и остановится на том, для которого это значение минимально.
Найти потенциалы заполненных клеток.
Для незаполненных клеток проверить условие оптимальности. Если условие оптимальности выполняется, то полученное решение оптимально.
В противном случае выбирают клетку (k,s), для которой Uk+Vs>Cks и строим цикл транспортной таблицы, приписывая клетке знак «+» и чередуя знаки во всех остальных клетках цикла.
Проводим пересчет таблицы по следующему правилу. Необходимо выбрать число r=min xij из цикла со знаком «-». В клетках цикла, помеченных знаком «+», это число прибавляем. В клетках цикла, помеченных знаком «-», это число отнимаем. Остальные клетки цикла не изменяем и ту клетку, в которой было найдено r, не заполняем.
Возвращаемся к пункту 2.
Пример:
Составим опорное решение методом С-З угла:
|
B1 |
B2 |
B3 |
B4 |
Потребности |
A1 |
270 1 |
140 4 |
100 7 |
3 |
510 |
A2 |
5 |
6 |
90 8 |
9 |
90 |
A3 |
7 |
2 |
10 4 |
110 8 |
120 |
Запасы |
270 |
140 |
200 |
110 |
720 |
ƒ(α1)=270+560+700+720+40+880=3170
Составим опорное решение методом минимального элемента
|
B1 |
B2 |
B3 |
B4 |
Потребности |
A1 |
270 1 |
20 4 |
110 7 |
110 3 |
510 |
A2 |
5 |
6 |
90 8 |
9 |
90 |
A3 |
7 |
120 2 |
4 |
8 |
120 |
Запасы |
270 |
140 |
200 |
110 |
720 |
ƒ(α2)=270+80+770+330+720+240=2410
Поскольку, пока минимальные затраты получились при α2 начинаем реализацию метода потенциалов с этого опорного решения.
|
B1 |
B2 |
B3 |
B4 |
Потребности |
Ui |
A1 |
270 1 |
2
+ -
-
+
|
110 7 |
110 3 |
510 |
0 |
A2 |
5 |
6 |
90 8 |
9 |
90 |
1 |
A3 |
7 |
120 2 |
4 |
8 |
120 |
-2 |
Запасы |
270 |
140 |
200 |
110 |
720 |
|
Vj |
1 |
4 |
7 |
3 |
|
|
Условие оптимальности не выполняется в клетке (3;3). Производим пересчет.
|
B1 |
B2 |
B3 |
B4 |
Потребности |
Ui |
A1 |
270 1 |
130 4 |
7 |
110 3 |
510 |
0 |
A2 |
5 |
6 |
90 8 |
9 |
90 |
2 |
A3 |
7 |
10 2 |
110 4 |
8 |
120 |
-2 |
Запасы |
270 |
140 |
200 |
110 |
720 |
|
Vj |
1 |
4 |
6 |
3 |
|
|