- •7.Формы записи задачи лп
- •8.Переход к канон.Ф.:
- •10.Геом. Интерпретация цф и ограничений задачи.
- •12. Геоминтерпр-ия задачи лп с несколькими переменными.
- •13Основная теорема лп
- •15. Построение начальн. Опорн. Плана
- •17.Переход к нехудшему опорному плану
- •18. Правила пересчёта
- •20.Призн.Неогр-ти цф на множ-ве планов.Геом.Интрепр.
- •21Прямая и двойственная задача
- •22.Основное неравенство теории двойственности и его экон. Содерж.
- •23.Критерий оптимальности Канторовича
- •27. Постановка тз по критерию стоимости.
- •28.Трансп-ная табл. Теорема о сущ-нии допуст плана.
- •29. Тз с закр. И откр.Моделью.
- •31. Правило «северо-западного угла»
- •32.Прав «миним эл-та» (наим стоим»)
- •33. Теор о потенц. Алг теор
- •35. Усложненные постановки тз.
- •41.Постр-е прав-го отсечения. Теорема о прав отсеч
- •42.Метод ветвей и границ.
- •43. Понят о дп. Принц оптим Беллмана
- •44. Вычисл схема реш задач методом дп
- •47. Задача оптим. Планирования вып-ка, сод-я и хран-я пр-ции и решение ее методом дин-го рогр-я
- •48. Задача замены оборуд
- •50.Метод множ Ланг-жа реш задач нп.Эк смысл множ Ланг-жа.
- •51.Градиент.Метод решения задачНп
47. Задача оптим. Планирования вып-ка, сод-я и хран-я пр-ции и решение ее методом дин-го рогр-я
Треб-ся опр-ть произв-ю прогр-му изгот-я пр-ции, удовл-ю спрос в каждом из месяцев план-го рериода и обеспеч-ю мин. з-ты на пр-во и хран-е прод-ции. Запас прод-ции на складе в конце план.периода должен = 0.
Рассм. период времени из Т месяцев. Введем обозначения: -запас пр-ции на складе на нач. план. периода; t- номер планового отрезка,t=1,Т; –спрос на пр-цию в каждом месяце, t=1,Т; n- номер план. отрезка времени, соотв-й обратной ном-ции месяцев; -спрос на пр-цию на n-м отр-ке; -ур-нь запаса на начало n-го отр-ка; -кол-во пр-ва пр-ции на n-м отр-ке, если ур-нь запасов на начало отр-ка = ; - ур-нь запаса на конец n-го отр-ка; – з-ты связанные с выпуском ед-ц пр-ции на n-м отр-ке и с содержанием запасов, объем кот на конец n-го отр-ка = ед-ц; –значение функции,= затратам на пр-во и хранение пр-ции за n последних месяцев, при условии, что ур-нь запасов на началоn-го месяца сост-т ед-ц. Здесь n=1,N, N=T.
Изобразим для наглядности:
t=1 t=2 … t=T
… =0 __|______|_____|_____|____|____
n=Nn=N-1 …n=1
…
… =?
З-ты на пр-во и хранение пр-ции будут состоять из затрат на пр-во и хранение:
= + h* , где h-затраты на хранение ед-цы пр-ции. В свою очередь з-ты на пр-во состоят из постоянных и переменных затрат:
= К+
Тогда получим, что = К+ ++h* . Произв-е мощности ограничены и выпускать можно не более В ед-ц пр-ции.
Складские площади также ограничены и хранить можно не более М.
Решение з-чи многошаговое. Шагом явл-ся месяц. Управление процессом будят явл-ся кол-во прод-ции в месяц.
n=0, (0)=0;
n=1,
Запас пр-ции , но он буд = любому цел неотр числу непревыш вместительность склада и спроса в месяце:
= 0;1;2;…;min( ;М), тогда объем пр-ва должен быть
Тогда суммарные з-ты в этом месяце:
)
n=1
На начало 2-го месяца ур-нь запаса может быть = 0,1.2, …., min ( ;М). Тогда кол-во выпускаемой пр-ции должно быть , т.к. спрос во 2м месяце д.б удовлетворен, но не больше min( ;М). Тогда суммарные з-ты на пр-во и хранение пр-ции за 2 месяца :
=
=min ( )+ ))=
=min ( .
В итоге получим след. Рекуррентное соотношение:
где
Поскольку ур-нь запасов на начало кажд месяца за искл 1го неизвестен, то надо учит-ть все возможные значения. По ур-ню запаса на начало периода найдем кол-во пр-ва в 1м месяце: значение ЦФ соотв-ее ее значению: . Потом однозначно определим кол-во запасов на начало 2го месяца: , и т.д
48. Задача замены оборуд
Пусть в нач.планового периода продолжит-тьюТ лет имеется оборуд. Возрасат t.Произв-ся прод-ия стоим-тьюr(t), u(t) – эксплуат-ые затр-ы, s(t) – остат-я стоим.В любое время оборуд. Можно сохр.или продать и купить новое по цене р.Fk(t) – макс. Прибыль заkлет.Необх рассм-ть процесс оптимизац. С конца планового периода.В этой зад. Сис-му составл. оборуд.Вектор управления-это решен.в моментt=0,1,2…Т,о сохранении или замене обор.Необх.проанал-ть процесс от конца к нач.Пусть k=1,t-возраст обор.
Имеем 2возможнсти: 1)Сохр-ть оборуд-е,тогда прибыль за посл.год = r(t) – u(t). 2) Продать обор.: прибыль = s(t) – p + r(0) – u(0).Решение о замене обор.возраста t следует принять,когда прибыль от нового обор.на посл.периоде больше,чем от старого,т.е:
s(t) – p + r(0) – u(0) >r(t) – u(t), тозамена
Если s(t) – p + r(0) – u(0) <= r(t) – u(t), то cохраняемстарое.
Общее функцион-е ур-ие:
F k(t)=maxr(t) – u(t) + Fk-1(t+1), сохран-е
s(t) – p + r(0) – u(0) + Fk-1(1), замена.
49.Геометр.интерп-ция з-чиНП.
Рассм.зад.вида:
max(min)F=f (x1,x2,…,xn) (1)
φi(x1,x2,…,xn) (2)
хj≥0,j=1.n.Если либо ЦФ 1,либо огр-ния 2,либо то и др.явл.нелинейн,то зад.наз-сянелинейной.В отлич. От зад.линейн.прогр-ия,она не явл.выпуклой.В рез-те реш-я эт.з-чи буд.найдена т.Х* такая,что для любой др.т-ки Х,коор-ты кот.также удовл-ют огран-ям з-чи и выпол-ся нер-во:f(x*)>f(x)(если з-ча на min,то f(x*)<f(x)).
Алгоритм реш(графич.метод):1)наход.ОДР.Если она пуста,то з-ча не имеет реш-я.2)строим гиперплоскость f(x1,x2,…,xn)=h.3)опред-им гиперпл-ть наив.(наим.)ур-ня или устанавл. неразрешимоть з-чи из-за неогранич-ти ЦФ,4)наход. Точку ОДР,через кот.проходит наивысш(наинизш) уровня и опред-м в ней значен.ЦФ.