- •Кривошеев О.И.
- •потом
- •Стоимость Sтранзакции
- •Введение в управление запасами
- •Транзакционные издержки
- •Введение в управление запасами
- •Введение в управление запасами
- •исследование ф-ии Z(Q).
- •исследование ф-ии Z(Q).
- •решить задачу управления запасами процент 0,14 1/год,
- •1.решить задачу управления запасами процент 0,14 1/год,
- •Ограничение на суммарный средний запас
- •МинимальноеH остовное дерево
- •Условная оптимизация
- •Условная оптимизация
- •Построить мин. остовное дерево
- •Сеть нефтепроводов на море…
- •Задача определения кратчайшего пути
- •кр.Пути (на неориентированном графе)
- •Алгоритм
- •2Алгоритм0
- •ОбразецОтвет:
- •самый короткий маршрут между городами T и S
- •Задача
- •Найти самый короткий маршрут
- •самый короткий маршрут между городами T и S
- •самый короткий маршрут между городами T и S
- •самый короткий
- •Найти самый короткий маршрут
- •Самый безопасный маршрут...
- •Строительство дома.
- •Строительство дома.
- •Строительство
- •Строительство
- •Строительство
- •Задача
- •Обсчитанный проект из 3х работ
- •Проект из 3х работ
- •Проект из 3х работ
- •Проект из 3х работ
- •Проект из 3х работ
- •Проект из 3х работ
- •Проект из 3х работ
- •Проект из 3х работ
- •Рассчитать время и запасы
- •Рассчитать время и запасы
- •Рассчитать время и запасы
- •Рассчитать время и запасы
- •Рассчитать время и запасы
- •Теперь обратный проход
- •Теперь обратный проход
- •Теперь обратный проход
- •Время работы
- •Поздние времена последовательно вычисляются. Например, на первом шаге позднее время может быть вычислено
- •Крит. Путь.
- •Замена оборудования
- •Крит. Путь.
- •Вероятностное дин. программирование
- •Решение:
- •Пример:
- •ответ
- •Условие:
- •Терминалы //потребители Тамбов 200 Тверь 300 Томск 120
- •Цель
- •Цель
- •Метод Северо-Западного Угла
- •Транспортная задача
- •6-ти членный цикл пересчёта
- •«Теорема».
- •Тамбов 200 Тверь 300 Томск 120 Цель
- •ОТВЕТ:
- •Операционная стоимость
- •БАЗИСНЫЙ ПЛАН: значение
- •БАЗИСНЫЙ ПЛАН: значение ЦФ/ Лучше возможно?!
- •Лучше возможно?!: Двойственная
- •Лучше возможно?!: Двойственная
- •Лучше возможно?!: Двойственная
- •Лучше возможно?!: Двойственная
- •БАЗИСНЫЙ ПЛАН ПОСТРОЕН!!!
- •Метод Северо-Западного угла
- •Переход по циклу
- •Дана сеть, cij – пропускные способности маршрутов в каждом направлении
- •Дана сеть, cij – пропускные способности маршрутов в каждом направлении
- •Дана сеть, cij – пропускные способности маршрутов в каждом направлении
- •Дана сеть, cij – пропускные способности маршрутов в каждом направлении
- •Дана сеть, cij – пропускные способности маршрутов в каждом направлении
- •Дана сеть, cij – пропускные способности маршрутов в каждом направлении
- •Дана сеть, cij – пропускные способности маршрутов в каждом направлении
- •Дана сеть, cij – пропускные способности маршрутов в каждом направлении
- •Система обслуживания с несколькими сервисами
- •Формула Литтла для связи
- •Среднее время в системе - …
- •Строительство дома.
Лучше возможно?!: Двойственная
задача и метод потенциалов
c11 c22 c21 c12?0
|
|
|
|
Владивост |
|
СПб |
||||||||
|
|
|
|
ок |
|
v 0 |
|
|
|
|
|
|||
|
|
|
|
25 |
|
(5) (0) |
|
30 (0) |
||||||
|
|
|
|
|
|
|||||||||
|
Москва |
|
|
|
|
|
10 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
0,5 |
|
||||||
u 10 |
20 |
(0) |
x11=20 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
x12 |
|
|||||||||
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
||||||
|
Хабаровск |
4 |
|
12 |
|
|||||||||
|
35 |
(30)(0) |
x21=5 |
|
|
|
|
x22 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Выбираем
небазисную
переменную
Fi 1 Fi ( c11 c22 c21 c12)( c11 c22 c21 c12) min
Лучше возможно?!: Двойственная
задача и метод потенциалов
c11 c22 c21 c12?0
u 10
u 4
|
|
|
Владивост |
|
СПб |
||||||||||||
|
|
|
ок |
|
v 0 |
|
|
|
|
|
|
|
|||||
|
|
|
25 |
|
(5) (0) |
|
|
30 (0) |
|||||||||
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Москва |
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
0,5 |
|
||||||||
20 |
(0) |
x11=20 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
x12 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Хабаровск |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
||||||||||||
|
|
|
4 |
|
|
|
|
|
12 |
|
|||||||
35 |
(30)(0) |
x21=5 |
|
|
|
|
|
|
x22 |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Выбираем
небазисную
переменную
Fi 1 Fi ( c11 c22 c21 c12)( c11 c22 c21 c12) min
потенциалы подобрали так v+u=0 на базисных переменных
u 10
u 4
|
|
|
Владивост |
|
СПб |
|||||||||||
|
|
|
ок |
|
v 0 |
|
v 8 |
|||||||||
|
|
|
25 |
|
(5) (0) |
|
|
30 (0) |
||||||||
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Москва |
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
0,5 |
|
|||||||
20 |
(0) |
x11=20 |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
x12 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Хабаровск |
4 |
|
|
|
12 |
|
||||||||||
35 |
(30)(0) |
x21=5 |
|
|
|
|
|
|
x22=30 |
|||||||
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Выбираем
небазисную
переменную
Fi 1 Fi ( c11 c22 c21 c12) c11 c22 c21 c12?0
( c11 c22 c21 c12) min
v+u=0
потенциалы есть +- пошлина производителя и импортера – не зависит от x и не меняет предпочтения задачи
|
|
|
|
Владивост |
|
СПб |
||||||||
|
|
|
|
ок |
|
v 0 |
|
|
v 8 |
|||||
|
|
|
|
25 |
|
(5) (0) |
|
30 (0) |
||||||
|
|
|
|
|
|
|||||||||
|
Москва |
|
|
0 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
0,5-(8+4) |
|
|||||||||
|
|
|
|
|
||||||||||
u 10 |
20 |
(0) |
x11=20 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||||||||
|
|
|
|
X12 |
|
|
||||||||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
u 4 |
Хабаровск |
|
|
|
|
0 |
|
|
0 |
|
||||
35 |
(30)(0) |
x21=5 |
|
|
|
|
x22=30 |
|||||||
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( c11 c22 c21 c12) *cˆ21 min
Fi 1 Fi ( c11 c22 c21 c12) Fi cˆ21
Выбираем
небазисную
переменную
(c11 v1) c22 (c21 v1) c12 . . 0 0 cˆ12 0 cˆ12
v+u=0
потенциалы есть +- пошлина производителя и импортера – не зависит от x и не меняет предпочтения задачи
|
|
|
|
Владивост |
|
СПб |
||||||||
|
|
|
|
ок |
|
v 0 |
|
v 8 |
||||||
|
|
|
|
25 |
|
(5) (0) |
|
30 (0) |
||||||
|
|
|
|
|
|
|||||||||
|
Москва |
|
|
0 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
-11,5 |
|
|||||||||
|
|
|
|
|
||||||||||
u 10 |
20 |
(0) |
x11=20 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|||||||||
|
|
|
|
X12 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
u 4 |
Хабаровск |
|
|
|
|
0 |
|
0 |
|
|||||
35 |
(30)(0) |
x21=5 |
|
|
|
|
x22=30 |
|||||||
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( c11 c22 c21 c12) *cˆ21 min
Fi 1 Fi ( c11 c22 c21 c12) Fi cˆ21
Выбираем
небазисную
переменную
(c11 v1) c22 (c21 v1) c12 . . 0 0 cˆ12 0 cˆ12
|
Владивост |
|
ок |
|
25 |
Москва |
10 |
20 |
x11 |
Хабаровск |
4 |
35 |
x21 |
СПб
30
0,5
x12
12
x22
|
|
Владивост |
СПб |
|
|
|
ок |
|
|
|
|
25 |
(5) |
30 |
Москва |
|
10 |
0,5 |
|
20 |
(0) |
x11=20 |
x12 |
|
Хабаровск |
4 |
12 |
35 |
x21 |
x22 |
|
|
Владивост |
СПб |
|
|
|
ок |
|
|
|
|
25 |
(5) (0) |
30 |
Москва |
|
10 |
0,5 |
|
|
|
|
|
|
20 |
(0) |
x11=20 |
x12 |
|
Хабаровск |
|
4 |
12 |
|
35 |
(30) |
x21=5 |
|
x22 |
|
|
Владивост |
СПб |
||
|
|
ок |
|
|
|
|
|
25 |
(5) (0) |
30 |
(0) |
Москва |
|
10 |
|
0,5 |
|
|
|
|
|
|
|
20 |
(0) |
x11=20 |
x12 |
|
|
Хабаровск |
|
4 |
12 |
|
35 |
(30)(0) |
x21=5 |
|
x22=30 |