Основная модель управления запасами

 

Наиболее простой является так называемая основная модель управления запасами (модель Уилсона, система с фиксированным размером заказа)

 

Допущения модели Уилсона

 

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

интенсивность спроса ;

время поставки заказа является известной и постоянной величиной ;

каждый заказ поставляется в виде одной партии;

затраты на осуществление заказа не зависят от размера заказа;

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

- размер заказываемой партии продукции

 

 

Средний уровень запасов

 

 

 

 

- затраты на выполнение заказа

 

- число заказов в год

 

Годовые затраты на выполнение заказов

 

 

Затраты, связанные с хранением продукции

 

 

- ставка процента,

 

- цена единицы товара

 

 

 

 

 

 

 

- формула Уилсона

 

 

 

 

Если , - точка заказа;

 

Если , - точка заказа;

 

Общие сведения о численных методах оптимизации

Определение 1. Численный метод - это правило (алгоритм), в соответствии с которым вычисляется последовательность вели­чин , которая должна сходиться к реше­нию оптимизационной задачи .

Правило формирования последовательности

 

(1)

 

Вектор задает направление движения в пространстве ,

 

число - величину "шага" при переходе из точки в точку .

 

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

 

Если алгоритм за конечное число шагов приводит в точку , его называют конечношаговым, иначе - бесконечношаговым.

 

(3)

 

Алгоритм (1) относят к методам спуска

 

(2)

2.5. Алгоритмы многомерной оптимизации

 

 

(1)

 

 

Градиентные методы поиска

Методы используют информацию о градиенте це­левой функции и относятся к методам первого порядка.

(3)

дифференцируема на

 

(4)

(5)

Поскольку , то

(6)

(7)

 

Из свойства скалярного произведения

 

. (8)

- (9)

 

градиентные методы

,

(10)

Методы спуска

 

1. Простейший градиентный метод ;

2. Метод наискорейшего спуска

(11)

Из (11) следует:

 

3. Градиентный метод с дроблением шага

3.1. часто ;

 

3.2. к следующей итерации

 

 

 

Вычислительная процедура

 

1. ,

 

2. ,

 

3. ,

 

4.

 

5. Проверка условий останова: если выполняются ;

иначе к п. 2

 

Особенности методов:

· относятся к локальным методам оптимизации;

· используются для решения как одномерных, так и многомерных экстремальных задач;

· выпуклая ЦФ – метод сходится к точке минимума;

сильно выпуклая ЦФ - метод сходится к точке минимума с линейной скоростью;

невыпуклая ЦФ - метод сходится ко множеству стационарных точек

· градиентные методы относятся к методам спуска ;

· низкая скорость сходимости в окрестности точки минимума; метод чувствителен к ошибкам вычислений; градиентные методы целесообразно применять на начальном этапе оптимизационной процедуры.

 

 

Методы сопряженных направлений

 

а) - квадратичная ЦФ

(12)

 

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

 

(13)

 

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

 

Определение. Алгоритм

 

, (14)

(15)

при (13) называется методом сопряженных направлений

 

 

Утверждение

- система сопряженных направлений относительно матрицы .

Тогда (14) в случае (12) при условии (15) и произвольном за шагов обеспечивает достижение точки минимума (12), т.е.

 

Формирование системы сопряженных направлений

(16)

 

 

 

 

(17)

 

 

б) ЦФ не является квадратичной

 

1. вычислений (16), (18) ;

 

2. Проверка выполнения условий останова:

Условия выполняются Поиск завершен;

 

 

Условия не выполняются

 

Идти к п.1

 

При этом

 

(18)

 

 

Метод сопряженных градиентов (метод Ривса), метод первого порядка

 

 

в) Лемма.

 

- подпространства;

 

;

 

-

 

точки минимума функции в подпространствах

 

при поиске вдоль направления .

 

Тогда вектор сопряжен с направлением

 

 

 

Рис. 1

 

 

 

 

 

Метод Ньютона

(1)

 

Процедура поиска

(2)

 

 

Из (1) имеем

, (3)

(3) в (2)

 

 

(4)

- оптимизационный метод Ньютона

 

Особенности метода Ньютона

 

1. Трудоемкость, обусловленная вычислением и обращением матрицы Гессе на каждой итерации;

2. Выбор ;

3. Метод Ньютона сходится к точке минимума произвольной ЦФ с квадратичной скоростью, если матрица Гессе положительно определена, а располагается «достаточно близко» к .

 

Метод Ньютона с регулировкой шага:

 

(5)

 

,

Скорость сходимости – сверхлинейная;

квадратичная