Список задач управления производством

Методы решения задач

Экономико – математические методы:

линейного и нелинейного программирования.

Линейное программирование при условии:

Целевая функция линейная функция своих искомых переменных,

Условия и ограничения - линейная функция искомых переменных

Нелинейное программирование:

Задачи выпуклого программирования (минимум выпуклой функции на заданном выпуклом замкнутом множестве)

Задачи квадратичного программирования (минимум квадратичной функции на выпуклом множестве)

Целочисленного (неизвестные принимают только целочисленные значения)

Параметрического (целевая функция или ограничения зависят от некоторых параметров)

Дробно – линейное программирование (целевая функция - отношение двух линейных функций)

Список задач управления производством

 

Комбинаторная задача распределения капитала. Динамическое программирование(2)

Проблема запасов(1)

Проблема последовательных решений(3)

Распределение оборудования. Теория очередей(4)

Транспортные сети(5)

Задача о назначениях бригад (6)

Транспортная задача с опорными элементами(7)

Замена оборудования при амортизации(8)

Теория пополнения запасов(9)

Теория стратегических игр(10)

Задача о управлении персоналом(12)

Линейное программирование(13)

Условия неопределённости, Выбор критерия (14)

Методы решения задач

Линейное программирование. Графический метод решения задач ЛП.

Симплекс метод

Допустимые, базисные, оптимальные решения

Двойственные задачи и решения

 

Графический метод решения задач ЛП

Основные теоремы двойственности

Параметрическая оптимизация

Специальные задачи линейного программирования

Значительная часть задач принятия решений – это задачи распределения ресурсов между объектами (продуктами)

 

Управление запасами

Когда заказать? Сколько заказать? Сколько иметь в резерве?

Системы снабжения: Децентрализованные: однокаскадные, централизованные

Многокаскадные,

Спрос: стационарный, случайный, детерминированный

Затраты: на хранение (от среднего уровня, от времени аренды склада, от остатка в конце периода), на поставки (от объёма, числа номенклатур, скорости поставок), на заказ каждой новой партии), на штрафы

Спрос с постоянной интенсивностью СПИ (μ)

Поставки c постоянной интенсивностью ППИ (λ)

Предельный запас на складе Пр ЗС: (Yпз)

Максимальный дефицит Yд

Расходы на хранение

Затраты за цикл Т ЗТ

Полный цикл - Т

 

 

│Y- - - - - - - - -

│ Yпз

 

 

λ – μ

0--------------------------*--------------*--------------------------------* --t

Y

Yпз

 

 

*

λ – μ

t1 t2 t3 t4

----------------------------*--------------------------------------- -----------------------

T T

 

 

Функция затрат за цикл (L(T)) = фиксированные расходы на запуск партии (g) +

· удельные расходы на хранение единицы продукта в единицу времени (s) *

 

 

t 1+ t 2 T

L(T) = (g) + (s) * ∫ y(t) dt – p * ∫ y (t) dt

0 t 1+ t2

 

p - удельный штраф (затраты) за дефицит единицы запаса в течение единицы времени

 

t + t Т

L(T) = g + s * ∫ y(t) dt – p* ∫ y (t) dt (1)

0 t+t

 

y (t) = (λ – μ) * t, 0 ≤ t ≤ t 1,

 

= Yпз – μ (t – t 1), t1 ≤ t ≤ t 1+ t 2+ t 3 (2)

 

= (– Yд) + (λ – μ) * (t – t1 – t2 – t3), при t1 + t2 + t3 ≤ t ≤ T.

 

 

Максимальный дефицит выражается Y д выражается через Yпз как

 

 

T – (t 1 + t2)

Y д = ---------------- * Yпз (3)

t1 + t 2

 

Yпз Y пз

Подставив t 1= ---------, и t 2 = -------, получим

λ – μ μ

 

μ

Yд = ----- * [ (λ – μ) * T – Yпз ] (4)

λ

Выполнив интегрирование функция затрат (1) с учётом линейности изменения уровня запаса:

s* λ * Yпз ² p * λ μ

L T = g + ------------------ + ------------------ * [ -----(λ – μ) * T – Yпз ] ² (5)

2* μ*(λ – μ) 2* μ*(λ – μ) λ

 

Откуда затраты в единицу времени L ср

L ср = L T / Т =

 

1 (p + s) * λ *Yпз ² p * μ

= ----- [ g + ----------------------- ] + -------- (λ – μ) T – p Yпз (6)

Т 2* μ* (λ – μ) 2* λ

 

 

∂ L ср (p + s) * λ * Yпз

--------- = [ ------------------------ – p ] = 0 (7)

∂ Yпз T* μ *(λ – μ)

 

 

μ - интенсивность спроса

λ –интенсивность поставок

p – удельный штраф за дефицит

g – расходы на запуск заказа

s – удельные расходы на хранение единицы продукта в единицу времени

 

∂ L ср p * μ 1 (p + s) * λ *Yпз ²

--------- = ---------- (λ – μ) – ------[ g + -------------------------] = 0 (8)

∂ T 2* λ T ² 2* μ* (λ – μ)

 

Решение системы (7) и (8) даёт оптимальные Yпз (опт) и Т (опт)

 

μ

2 μ g (1 – ----)

λ

Yпз (опт) = √ --------------------- (9)

s

s (1 + ----)

p

s

2 * g (1 + --)

λ

Т (опт) = √ --------------------- (10)

μ

μ * s* (1 – ---)

λ

При этом достигается минимум затрат в единицу времени

μ

2 μ* g* s (1 – ----)

λ

L(опт) = √ ------------------------------ (11)

s

1 + -----

p

 

Следующие основные формулы теории запасов:

А) Дефицит – исключается, тогда положив p →∞ и подставив s / p = 0 в (9) – (11), получаем

 

μ 1

Yпз (опт) = = √ 2 μ g (1 – ----) ------ (12)

λ s

 

 

-----------------------

2 * g

Т (опт) = √ ---------------------

μ

μ * s* (1 – ---)

λ

 

μ

L(опт) = √ 2 μ* g* s (1 – ----)

λ

 

 

Б)Если интенсивность восполнения запаса высокая, поставка мгновенная, то положив

λ→∞, μ / λ = 0 в (9) – (11) получим:

 

------------------

2 μ g

Yпз (опт) = √ ----------------

s

s (1 + ----)

p

 

s

2 * g (1 + --)

λ

Т (опт) = √ ---------------------

μ * s*

 

-----------------------

2 μ* g* s

L(опт) = √ -----------------------

s

1 + -----

p

 

В) Если дефицит не допускается, заказы выполняются мгновенно, то подставив

λ→∞, p →∞ получим формулы Уилсона

 

 

2 μ g 2 g

Yпз (опт) = √ -----------; Т (опт) = √ ------; L(опт) = √ 2 μ* g* s

s μ * s

 

 

Yпз (опт) = экономический размер партии

 

Спрос с постоянной интенсивностью СПИ (μ)

Поставки с постоянной интенсивностью ППИ (λ)

Предельный запас на складе Пр ЗС: (Yпз)

Максимальный дефицит Yд

Расходы на хранение

Затраты за цикл Т ЗТ

Полный цикл - Т

удельные расходы на хранение единицы продукта в единицу времени (s)

фиксированные расходы на запуск партии (g)

Оптимальный размер закупочной партии - Q*

 

Функция затрат за цикл (L(T)) = фиксированные расходы на запуск партии (g) +

· удельные расходы на хранение единицы продукта в единицу времени (s)

 

 

t1 + t 2 T

L(T) = (g) + (s) * ∫ y(t) dt – p * ∫ y (t) dt

0 t 1+ t2

 

p - удельный штраф (затраты) за дефицит единицы запаса в течение единицы времени

 

 

Варианты задач управления запасами:

Детерминированный стационарный спрос

Переменная цена товара

Многономенклатурные запасы

Вероятностный спрос и мгновенные поставки

 

Методы начальных приближений

Модели определения оптимального размера закупочной партии:

1.)Модель экономического заказа

2* Годовой спрос* Затр. заказа

Q* = √ --------------------------------------------

Затр. Хранения

2.)Модель производственного заказа

2* Годовой спрос* Затр. заказа

Q* =√ ------------------------------------------------------------------------------------

Затр. Хранения * (1 – годовой спрос: мощность производителя)

3) Модель заказа с резервным запасом

2* Годовой спрос* Затр. заказа Затр. Хранения + Затр.резервирования

Q* = √ -------------------------------------------- * -------------------------------------------

Затр. Хранения Затр.резервирования

 

Задача

Фирма ежегодно закупает Д = 8000 деталей по цене Ц = 10 руб./ шт. и использует на сборке

Затраты на хранение одной детали в течение года на Хр = 3 руб./шт.

Затраты на оформление заказа З = 30 руб./заказ

Годовой фонд работы за год Ф = 200 рабочих дней

Доставка заказа от поставщика Дост.= 2 рабочих дня

Производственная мощность поставщика - 10 670 деталей в год.

Затраты резервирования Рез. = 7 руб./шт. в год

Рассчитать Q*

Решение

Если все 8000 деталей закупаются одновременно на год, то общие затраты составят:

Q средн.год = (Qmax – Q min)/2 = 4000

 

Линейное программирование

Постановка задачи

Основная проблема управления – распределение ресурсов между объектами.

m – видов ресурсов.

 

Наличие каждого вида i - того ресурсов составляет b (i) (i = 1,2,…) в соответствующих единицах измерения

 

n – видов продукции

для выпуска единицы j – го вида продукции необходимо a (i, j) единиц i- го ресурса

Найти: какого вида и сколько продукции надо произвести, чтобы выпуск был наилучшим для принятого критерия оптимальности

x (i) – количество выпускаемой продукции j – того вида

 

Для каждого i- го ресурса можно записать

 

n

∑ a(i, j) * x (i) ≤ b (i)

j= 1

Левая часть неравенства – потребность в ресурсе i - того вида, правая - располагаемое количество этого ресурса.

Распространяя на m видов ресурсов, это ограничение запишем:

 

n

∑ a(i,j) * x (i) ≤ b (i) (i= 1,2, …, m) (1)

j= 1

Если номенклатура продукции ограничивается предельными значениями объёмов производства и продаж, то граничные условия в пределах допустимых объёмов имеют вид:

 

N min(j) ≤ x (j) ≤ N max(j)

Цель задачи распределения ресурсов имеет две взаимоисключающие постановки:

1) при заданных ресурсах максимизировать результат планирования

при заданном результате минимизировать получаемый результат

 

Целевые функции:

c (j) - прибыль от реализации единицы вида продукции

Прямая задача

n

max L (1) = ∑ c(j)* x (j), при ограничениях

j= 1

x (j) ≥ 0 (мир решений – реален).

n

∑ a(i,j) * x (i) ≤ b (i) (i= 1,2, …, m)

j= 1

2) двойственная задача имеет целевую функцию

n

min L (2) = ∑ b(j)* y(j) при условиях:

j= 1

m

∑ a(i,j) * y (i) ≥ c (i) (i= 1,2, …, m), при ограничениях

j= 1

y (j) ≥ 0 - цена единицы ресурса (мир цен – реален);

 

для выпуска единицы j – го вида продукции необходимо по нормам a (i, j) единиц i- го ресурса

 

Теоремы линейного программирования:

Линейная система, в которой число неизвестных равно числу уравнений, имеет одно решение

Если число неизвестных меньше числа уравнений, то решения нет и система несовместна

1)Если целевая функция принимает максимальное значение в некоторой точке допустимого множества R -1, то она принимает это значение в крайней точке реального пространства R -1.

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

2)Если задача линейного планирования содержит n переменных и m ограничений

(n ≥ m) в форме неравенств, не считая ограничений неотрицательности

x (j) ≥ 0, то в оптимальное решение входит не более чем m ненулевых компонент вектора x.

При векторной форме записи ограничения задачи ЛП записывают:

А (1) * Х (1) +... + А(n) Х(n) ≤ b.

Поскольку А(1),..., А(n) - m – мерные вектора (n ≥ m), то среди них всегда найдётся m линейно независимых векторов, образующих базис m – мерного пространства и содержащих конус, образованный векторами А(1),..., А(n).

Таблица 1

Ресурсы Продукты

А, В. С. Д. Наличие в

Удельные нормы расхода запасах

-Трудовые 6 4 2 1 800

-материальные 7 9 11 5 2 000

-финансовые 3 4 5 6 12 000

 

Ограничения

Нижнее 1 - 3 - -

Верхнее 12 2 - - -

-------------------------------------------------------------------------------------------------------------------------------------------

План х1 х2 х3 х4

 

Обозначим:

F – ресурсы

R – результат их применения

 

При заданных зависимостях результата и потребных ресурсов от количества выпускаемой продукции R = R(x (j)), F = F (x(j)) обе постановки распределения ресурсов в сокращённой форме:

 

L(1) = R (x(j)) →max L(2) = F (x(j)) → min

F(x(j)) ≤ F * F(x(j)) ≤ F *

R (x(j) ≥ R*

 

где F*, R* заданные плановые величины ресурсов и результата

Пусть для продукции А, В, С, Д прибыль от реализации единицы продукции каждого вида составляет 5,6, 7 и 8 д.е. соотвественно, а суммарная прибыль от всего производства должна быть не менее 3000 д.е.

 

Тогда математическая модель задачи с учётом данных таблицы 1:

 

мax L(1) = 5x(1) + 6x(2) + 7x(3) + 8 x(4)

6x (1) + 4x(2) + 2x(3) + x(4) ≤ 800

7х(1) + 9х(2) + 11х(3) + 5 х(4) ≤ 2000

3х(1) + 4х(2) + 5х(3) + 6х(4) ≤ 12000

 

1 ≤ х(1) ≤ 12, х(2) ≤ 2, х(3) ≤ 3, х(4) ≥ 0.

Мах L (1) = 3162

 

Задача 2.Рассмотрим: х2

х1 + 4х2 ≤ 14 |

3х1 + 4х2 ≤ 18 |

6х1 + 2х2 ≤ 27 |

х1, х2 ≥ 0 |

|

|

|

|

|

|

|

!,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,х1

 

 

Нелинейное программирование

решаются методом кусочно – линейной аппроксимации, или метода множителей Лагранжа.Общего метода решения нет.

Задача

Надо изготовить 180 изделий

На первом предприятии затраты на х изделий равны [ 4* х(1) + х(1) ]

На втором [ 8 х(2) + 6 х (2) ]

 

Сколько изделий изготовить на каждом предприятии, чтобы общие затраты были минимальны?

 

Общая постановка

Max f (x(1), x(2), …, x(n)); (1)

g(i) [x(1), x(2), …, x(n) ] = b(i), (i = 1,…,m). (2)

 

Введём набор переменных λ(1), λ(2),,…, λ(m) - множители Лагранжа.

Составляем функцию Лагранжа

F (x(1), x(2), …, x(n), λ(1), λ(2),,…, λ(m)) =

(3)

= f (x(1), x(2), …, x(n) + ∑ λ(i) * [ b (i) – g (i) [ x(1), x(2), …, x(n)]

Находим частные производные

∂ F ∂ F

---------- (j = 1,…,n); ------- (i = 1,…,m)

∂ x (j) ∂ λ(i)

 

Рассматриваем систему n + m уравнений

∂ F m ∂ g(i)

--------- = ∑ λ(i) * --------

∂ x (j) i ∂ x(i) (4)

 

∂ F

------ = b (i) – g (i) [ x(1), x(2), …, x(n)]

∂ λ(i)

 

 

Продолжение решения задачи:

2 2

Min f = 4 x(1) + x(1) + 8 x (2) + x(2) (5)

 

x(1) + x(2) = 180 (6)

 

x(1),x(2) ≥ 0 (7)

Функция Лагранжа для этого примера:

2 2

F (x1,x2, λ) = 4x(1) + x(1) + 8 x(2) + x(2) + λ (180 – x (1) – x (2))

Вычисляем частные производные по х(1), х(2), λ и приравниваем их «0».

 

 

∂ F

-------- = 4 + 2х(1) – λ =0

∂ x (1)

∂ F

--------- = 8 + 2х (2) – λ =0 }

∂ x (2)

 

∂ F

------ = 180 – x(1) – x (2) = 0, отсюда (8)

∂ λ

4 + 2х(1) = 8 +2х(2) или х(1) + х(2), решая совместно (8) получаем

х(1)опт = 91, х(2) опт = 89

Используя вторые частные производные, убеждаемся, что в этой точке функция f имеет минимум

 

Задание:

Надо изготовить 200 изделий

На первом предприятии затраты на х изделий раны 4* х(1)

На втором 20 х(2) + 6 х (2))

 

Сколько изделий изготовить на каждом предприятии, чтобы общие затраты были минимальны?

 

 

Имитационное моделирование

Требования к имитационной модели:

-целенаправленность, цель – решение задачи для которого есть критерий оптимальности, введены ограничения на переменные и сформулированы зависимости между переменными,

-проста и понятна пользователю,

-гарантирует отсутствие абсурдных ответов,

-полна по возможностям решения главной задачи,

-позволяет обновлять данные,

-допускает постепенное усложнение или изменение последовательности решения.

Этапы процесса моделирования:

1. Описание проблемы

2. Анализ системы – установление границ, ограничений и показателей эффективности системы.

3. Конструирование модели – логической схемы.

4. Отбор данных для построения модели.

5. Описание модели на языке EXEL.

6. Оценка адекватности модели реальной системе.

7. Планирование эксперимента.

8. Серия испытаний – алгоритм проведения расчётов.

9. Имитация и оценка чувствительности.

10. Выводы о результатах моделирования

 

F(i) К 1

 

 

КРИТЕРИЙ ГУРВИЦА

Введём коэффициент оптимизма @

Пусть в строке а - самое маленькое число,

А - самое большое число

Вычислим для каждой строки таблицы Н:

Н= @*A + (1-@)*a

и выбираем строку для которой Н=max

Положим @=0.1, либо 0.2, либо 0.5, … 0.8,либо 0.9

Для каждого @ вычисляем Н

@ =0.1 @=0.2 @=0.5 @=0.8 @=0.9

f =2 -84 ← -47! 62 171 206

f =3 -113 -59 105 270 325

f =4 -143 -59 149 370 442

f =5 -172 -81 193 467 650!←

 

законченный пессимист абсолютный оптимист

 

КРИТЕРИЙ СЭВИДЖА

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

Для каждого столбца «R» находим наиболее благоприятный случай (максимальный элемент) и его вычитаем из всех элементов этого столбца.

Строим матрицу сожалений и искомую стратегию f(i),

 

Max min

F(i), R(J)

 

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

 

R=0 R=20 R=40 R=60 R=80 R=100

P=2 0 0 0 -135 -270 -405

P=3 -48 -48 -48 0 -135 -270

P=4 -95 -95 -95 -47 0 -135

P=5 -143 -143 -143 -95 -48 0

Минимальные значения сожалений

P=2 -405

P=3 -270

P=4 -135 ←

P=% -143

Выбор критерия - высшая форма свободы у принимающего экономические решения

Критерий выбирается на самом высоком уровне управления

Критерий Вальда max min (P,R)

p r

Критерий Гурвица max [@ max (P,R)+(1-@)min(P,R)]

p r r

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

max 1/K sum (P,R)

r

Критерий Сэвиджа max min [(P,R) - max(P,R)]

s r

 

 

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

Принцип Беллмана, процессы марковские:

Каковы бы ни были начальное состояние и начальная стратегия, последующие

решения должны быть оптимальны по отношению к состоянию предыдущего шага,

получившегося в результате предыдущего решения.

Оптимальное управление системой на каждом шаге не зависит от предыстории

процесса Такие системы называются Марковскими.

Задача

4 торговые зоны

Капиталовложения: складские помещения, магазины. торговый персонал,реклама.

 

Вложения Прибыль по торговым зонам

«А» млн руб 1 2 3 4

-----------------------------------------------------------------------------------------

0 0 0 0 0

1 0,28 0,25 0.15 0.20

2 0,45 0,41 0.25 0,33

3 0.65 0.55 0.40 0.42

4 0.78 0.65 0.50 0.48

5 0.90 0.75 0.62 0.53

6 1.02 0.80 0.73 0.56

7 1.13 0.85 0.82 0.58

8 1.23 0.88 0.90 0.60

9 1.32 0.90 0.96 0.60

10 1.38 0.90 1.00 0.60

 

Я и 2-я 1-я,2-я,и 3-я

0 0 0 0 (0,0) (0,0,0,)

1 0,28 0,15 0,28 (1,0) (1,0,0)

2 0,53 0,25 0,53 (1,1) (1,1,0)

3 0,70 0,40 0, 70 (2,1) (2,1,0)

4 0,90 0,50 0,90 (3,1) (3,1,0)

5 1,06 0,62 1,06 (3,2) (3,2,0)

6 1,20 0,73 1,21 (3,2) (3,2,1)

7 1,33 0,82 1,35 (4,3) (3,3,1)

8 1,45 0,90 1,48 (5,3) (4,3,1)

9 1,57 0,96 1,60 (6,3) (5,3,3) или

(3,3,3,)

10 1,68 1,00 1,73 (7,3) (4, 3,3)

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

 

Ф-1,2,3,4 (А) = мах [ Ф-1,2,3(А) + ф-4 (х)(А – х) ]

А Ф-1,2,3 (х) ф-3 (х) Ф-1,2,3,4 (А) Оптимальная

политика в зонах

Я,2-я,и 3-я 1-я,2-я,3-я,4-я

0 0 0 0 (0,0,0) (0,0,0,0)

1 0,28 0,20 0,28 (1,0,0) (1,0,0,0)

2 0,53 0,33 0,53 (1,1,0) (1,1,0,0)

3 0,70 0,42 0,73 (2,1,0) (1,1,0,1)

4 0,90 0,48 0,90 (3,1,0) (2,1,0,1)

Или (3,1,0,0)

5 1,06 0,53 1,10 (3,2,0,) (3,1,0,1)

6 1,21 0,56 1,26 (3,2,0) (3,2,0,1)

7 1,35 0,58 1,41 (3,3,1) (3,2,1,1)

8 1,48 0,60 1,55 (4,3,1) (3,3,1,1)

9 1,60 0,60 1,68 (5,3,1) (3,3,1,2)

Или (3,3,3) или (4.3,1,1)

10 1,73 0,60 1,81 (4,3,3) (4,3,1,2)

------------------------------------------------------------------------------------------------------------------

Методы решения задач

Экономико – математические методы:

линейного и нелинейного программирования.

Линейное программирование при условии:

Целевая функция линейная функция своих искомых переменных,

Условия и ограничения - линейная функция искомых переменных

Нелинейное программирование:

Задачи выпуклого программирования (минимум выпуклой функции на заданном выпуклом замкнутом множестве)

Задачи квадратичного программирования (минимум квадратичной функции на выпуклом множестве)

Целочисленного (неизвестные принимают только целочисленные значения)

Параметрического (целевая функция или ограничения зависят от некоторых параметров)

Дробно – линейное программирование (целевая функция - отношение двух линейных функций)

Список задач управления производством

 

Комбинаторная задача распределения капитала. Динамическое программирование(2)

Проблема запасов(1)

Проблема последовательных решений(3)

Распределение оборудования. Теория очередей(4)

Транспортные сети(5)

Задача о назначениях бригад (6)

Транспортная задача с опорными элементами(7)

Замена оборудования при амортизации(8)

Теория пополнения запасов(9)

Теория стратегических игр(10)

Задача о управлении персоналом(12)

Линейное программирование(13)

Условия неопределённости, Выбор критерия (14)

Методы решения задач

Линейное программирование. Графический метод решения задач ЛП.

Симплекс метод

Допустимые, базисные, оптимальные решения

Двойственные задачи и решения

 

Графический метод решения задач ЛП

Основные теоремы двойственности

Параметрическая оптимизация

Специальные задачи линейного программирования

Значительная часть задач принятия решений – это задачи распределения ресурсов между объектами (продуктами)

 

Управление запасами