🗊 Динамическое программирование

Категория: Информатика
Нажмите для полного просмотра!
  
  Динамическое программирование  , слайд №1  
  Динамическое программирование  , слайд №2  
  Динамическое программирование  , слайд №3  
  Динамическое программирование  , слайд №4  
  Динамическое программирование  , слайд №5  
  Динамическое программирование  , слайд №6  
  Динамическое программирование  , слайд №7  
  Динамическое программирование  , слайд №8  
  Динамическое программирование  , слайд №9  
  Динамическое программирование  , слайд №10  
  Динамическое программирование  , слайд №11  
  Динамическое программирование  , слайд №12  
  Динамическое программирование  , слайд №13  
  Динамическое программирование  , слайд №14  
  Динамическое программирование  , слайд №15  
  Динамическое программирование  , слайд №16  
  Динамическое программирование  , слайд №17  
  Динамическое программирование  , слайд №18  
  Динамическое программирование  , слайд №19  
  Динамическое программирование  , слайд №20  
  Динамическое программирование  , слайд №21  
  Динамическое программирование  , слайд №22  
  Динамическое программирование  , слайд №23  
  Динамическое программирование  , слайд №24  
  Динамическое программирование  , слайд №25  
  Динамическое программирование  , слайд №26  
  Динамическое программирование  , слайд №27  
  Динамическое программирование  , слайд №28  
  Динамическое программирование  , слайд №29  
  Динамическое программирование  , слайд №30  
  Динамическое программирование  , слайд №31  
  Динамическое программирование  , слайд №32  
  Динамическое программирование  , слайд №33  
  Динамическое программирование  , слайд №34  
  Динамическое программирование  , слайд №35  
  Динамическое программирование  , слайд №36  
  Динамическое программирование  , слайд №37  
  Динамическое программирование  , слайд №38  
  Динамическое программирование  , слайд №39  
  Динамическое программирование  , слайд №40  
  Динамическое программирование  , слайд №41  
  Динамическое программирование  , слайд №42  
  Динамическое программирование  , слайд №43  
  Динамическое программирование  , слайд №44  
  Динамическое программирование  , слайд №45  
  Динамическое программирование  , слайд №46  
  Динамическое программирование  , слайд №47  
  Динамическое программирование  , слайд №48  
  Динамическое программирование  , слайд №49  
  Динамическое программирование  , слайд №50  
  Динамическое программирование  , слайд №51  
  Динамическое программирование  , слайд №52  
  Динамическое программирование  , слайд №53  
  Динамическое программирование  , слайд №54  
  Динамическое программирование  , слайд №55  
  Динамическое программирование  , слайд №56  
  Динамическое программирование  , слайд №57  
  Динамическое программирование  , слайд №58  
  Динамическое программирование  , слайд №59  
  Динамическое программирование  , слайд №60  
  Динамическое программирование  , слайд №61  
  Динамическое программирование  , слайд №62  
  Динамическое программирование  , слайд №63  
  Динамическое программирование  , слайд №64  
  Динамическое программирование  , слайд №65  
  Динамическое программирование  , слайд №66  
  Динамическое программирование  , слайд №67  
  Динамическое программирование  , слайд №68  
  Динамическое программирование  , слайд №69  
  Динамическое программирование  , слайд №70  
  Динамическое программирование  , слайд №71  
  Динамическое программирование  , слайд №72

Содержание

Вы можете ознакомиться и скачать Динамическое программирование . Презентация содержит 72 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации


Слайд 1





Динамическое программирование
Описание слайда:
Динамическое программирование

Слайд 2





     Динамическое программирование (ДП) --особый метод, он специально приспособлен для оптимизации динамических задач, в которых операция состоит из элементов, сильно влияющих друг на друга. 
     Динамическое программирование (ДП) --особый метод, он специально приспособлен для оптимизации динамических задач, в которых операция состоит из элементов, сильно влияющих друг на друга. 
      ДП связано с именем Ричарда Беллмана, который сформулировал принцип Беллмана. Он позволяет существенно сократить перебор решений в многоэтапных нелинейных задачах.
Описание слайда:
Динамическое программирование (ДП) --особый метод, он специально приспособлен для оптимизации динамических задач, в которых операция состоит из элементов, сильно влияющих друг на друга. Динамическое программирование (ДП) --особый метод, он специально приспособлен для оптимизации динамических задач, в которых операция состоит из элементов, сильно влияющих друг на друга. ДП связано с именем Ричарда Беллмана, который сформулировал принцип Беллмана. Он позволяет существенно сократить перебор решений в многоэтапных нелинейных задачах.

Слайд 3





Экономическая задача распределения ресурсов 
  Пусть есть начальный капитал       .     
  Его можно потратить на несколько предприятий 
  
           -  количество средств вкладываемых в i-ом 
  году, в j-ое предприятие. 
  В результате получается эффект:
Описание слайда:
Экономическая задача распределения ресурсов Пусть есть начальный капитал . Его можно потратить на несколько предприятий - количество средств вкладываемых в i-ом году, в j-ое предприятие. В результате получается эффект:

Слайд 4





        В общем случае это не линейная функция.
        В общем случае это не линейная функция.
Описание слайда:
В общем случае это не линейная функция. В общем случае это не линейная функция.

Слайд 5





   Так как функция      - нелинейная, то получаем задачу нелинейного программирования. Решать её сложно, кроме того, часто         - дискретные значения. 
   Так как функция      - нелинейная, то получаем задачу нелинейного программирования. Решать её сложно, кроме того, часто         - дискретные значения. 
    Вопрос: нельзя ли решить задачу последовательно, т. е. найти оптимальное вложение для первого года, второго и т. д. т. е. провести последовательную оптимизацию. 
   В большинстве задач так нельзя, т. к. то, что мы решили оказывает влияние на последующие шаги.
Описание слайда:
Так как функция - нелинейная, то получаем задачу нелинейного программирования. Решать её сложно, кроме того, часто - дискретные значения. Так как функция - нелинейная, то получаем задачу нелинейного программирования. Решать её сложно, кроме того, часто - дискретные значения. Вопрос: нельзя ли решить задачу последовательно, т. е. найти оптимальное вложение для первого года, второго и т. д. т. е. провести последовательную оптимизацию. В большинстве задач так нельзя, т. к. то, что мы решили оказывает влияние на последующие шаги.

Слайд 6





   Например:
   Например:
   Бег на 800 метров. Каждый бегун имеет запас энергии, который он тратит на каждые 100 метров. ti – время на i – й 100 метров. 
    Σti(хi) → min; 
    Σхi ≤ х0. 
   Оказывается, на первых 100 метров бегун будет обеспечивать минимальное время.
Описание слайда:
Например: Например: Бег на 800 метров. Каждый бегун имеет запас энергии, который он тратит на каждые 100 метров. ti – время на i – й 100 метров. Σti(хi) → min; Σхi ≤ х0. Оказывается, на первых 100 метров бегун будет обеспечивать минимальное время.

Слайд 7





Принцип оптимальности Беллмана
    Принцип оптимальности Беллмана ставит вопрос о том, что такое оптимальность отдельного элемента системы с точки зрения оптимальности всей системы. Принимая решение на отдельном этапе, мы должны выбирать управление на этом этапе с прицелом на будущее, т. к. нас интересует результат в целом за все шаги.
Описание слайда:
Принцип оптимальности Беллмана Принцип оптимальности Беллмана ставит вопрос о том, что такое оптимальность отдельного элемента системы с точки зрения оптимальности всей системы. Принимая решение на отдельном этапе, мы должны выбирать управление на этом этапе с прицелом на будущее, т. к. нас интересует результат в целом за все шаги.

Слайд 8





   
   
   Беллман предложил рассматривать величину выигрыша от i-го шага и до конца, если i-ый шаг начинается с некоторого состояния S. Такую величину называют условным оптимальным выигрышем            .
   Тогда, принимая решение на i-ом шаге, мы должны выбрать Xi так, чтобы условный оптимальный выигрыш был максимальным от   i-го  шага и до конца.
Описание слайда:
Беллман предложил рассматривать величину выигрыша от i-го шага и до конца, если i-ый шаг начинается с некоторого состояния S. Такую величину называют условным оптимальным выигрышем . Тогда, принимая решение на i-ом шаге, мы должны выбрать Xi так, чтобы условный оптимальный выигрыш был максимальным от i-го шага и до конца.

Слайд 9





   Определение: оптимальность в малом понимается через оптимальность в большом.
   Определение: оптимальность в малом понимается через оптимальность в большом.
    Любой процесс имеет где-то окончание, т. е. имеет горизонт планирования. Тогда последний этап «не имеет будущего». Вот именно его можно оптимизировать только из условий данного этапа. После этого приступают к оптимизации             – го этапа. 
    Выбирают такое          , чтобы при применении этого               его внести в управление последнего шага.
Описание слайда:
Определение: оптимальность в малом понимается через оптимальность в большом. Определение: оптимальность в малом понимается через оптимальность в большом. Любой процесс имеет где-то окончание, т. е. имеет горизонт планирования. Тогда последний этап «не имеет будущего». Вот именно его можно оптимизировать только из условий данного этапа. После этого приступают к оптимизации – го этапа. Выбирают такое , чтобы при применении этого его внести в управление последнего шага.

Слайд 10


  
  Динамическое программирование  , слайд №10
Описание слайда:

Слайд 11





Функциональное уравнение Беллмана.
Назовём состоянием системы вектор координат:
Описание слайда:
Функциональное уравнение Беллмана. Назовём состоянием системы вектор координат:

Слайд 12





      Рассмотрим процесс управления системой за m 
      Рассмотрим процесс управления системой за m 
   шагов. Функция                называется выигрышем на i-ом шаге. Здесь S-состояние перед i-ым шагом, а U - управление на i-ом шаге. 
      Величина                    должна быть известна до начала динамического программирования. Если состояние перед i - ым шагом было S и мы приняли какое-то управление Ui, то система перейдёт в новое состояние 
      Эта функция должна быть так же известна.     Если эти функции не заданы, то их надо сформулировать.
Описание слайда:
Рассмотрим процесс управления системой за m Рассмотрим процесс управления системой за m шагов. Функция называется выигрышем на i-ом шаге. Здесь S-состояние перед i-ым шагом, а U - управление на i-ом шаге. Величина должна быть известна до начала динамического программирования. Если состояние перед i - ым шагом было S и мы приняли какое-то управление Ui, то система перейдёт в новое состояние Эта функция должна быть так же известна. Если эти функции не заданы, то их надо сформулировать.

Слайд 13





    Введём             - условный оптимальный выигрыш. Это выигрыш на всех этапах от i до конца, если i-ый шаг начинается с состояния S.
    Введём             - условный оптимальный выигрыш. Это выигрыш на всех этапах от i до конца, если i-ый шаг начинается с состояния S.
    Рассмотрим  m шагов. Начнём с            – го шага. Мы системой управляем оптимально, величина оптимального выигрыша 
    На i-ом шаге  - любое управление. 
   неоптимальный выигрыш, т. к. на i-ом шаге мы применяем управление Ui.
Описание слайда:
Введём - условный оптимальный выигрыш. Это выигрыш на всех этапах от i до конца, если i-ый шаг начинается с состояния S. Введём - условный оптимальный выигрыш. Это выигрыш на всех этапах от i до конца, если i-ый шаг начинается с состояния S. Рассмотрим m шагов. Начнём с – го шага. Мы системой управляем оптимально, величина оптимального выигрыша На i-ом шаге - любое управление. неоптимальный выигрыш, т. к. на i-ом шаге мы применяем управление Ui.

Слайд 14






Это функциональное уравнение Беллмана.
Описание слайда:
Это функциональное уравнение Беллмана.

Слайд 15





    Для использования уравнения Беллмана начинают с конца: 
    Для использования уравнения Беллмана начинают с конца: 
 1.
Описание слайда:
Для использования уравнения Беллмана начинают с конца: Для использования уравнения Беллмана начинают с конца: 1.

Слайд 16


  
  Динамическое программирование  , слайд №16
Описание слайда:

Слайд 17






Итак, идя от конца к началу, мы получаем последовательно:
Придя в начальное состояние W1(S), мы можем подставить S = S0 и W1(S0) = Wmax – это безусловный выигрыш.
Описание слайда:
Итак, идя от конца к началу, мы получаем последовательно: Придя в начальное состояние W1(S), мы можем подставить S = S0 и W1(S0) = Wmax – это безусловный выигрыш.

Слайд 18





Теперь необходимо получить, идя от начала к концу по цепочке, безусловно оптимальное уравнение:
Теперь необходимо получить, идя от начала к концу по цепочке, безусловно оптимальное уравнение:
Итак, в конце мы получаем:
Описание слайда:
Теперь необходимо получить, идя от начала к концу по цепочке, безусловно оптимальное уравнение: Теперь необходимо получить, идя от начала к концу по цепочке, безусловно оптимальное уравнение: Итак, в конце мы получаем:

Слайд 19





Задача распределения ресурсов.
   Это едва ли не самая распространённая операция. Под ресурсом в общем случае понимают физическую или абстрактную величину, которую система использует для производства полезного продукта. 
   Например: горючее, деньги, время, объём склада. Как правило – ресурс ограничен, поэтому встаёт задача так распределить ресурс между отдельными элементами системы, чтобы суммарный эффект был максимальным.
Описание слайда:
Задача распределения ресурсов. Это едва ли не самая распространённая операция. Под ресурсом в общем случае понимают физическую или абстрактную величину, которую система использует для производства полезного продукта. Например: горючее, деньги, время, объём склада. Как правило – ресурс ограничен, поэтому встаёт задача так распределить ресурс между отдельными элементами системы, чтобы суммарный эффект был максимальным.

Слайд 20





      Рассмотрим классическую задачу распределения ресурсов.
      Рассмотрим классическую задачу распределения ресурсов.
      Имеется начальное количество ресурсов      , которые необходимо распределить между двумя отраслями. Каждая отрасль работает в течении m лет. Если в первую отрасль в  i-ый год вкладываются средства         , то доход           , если же во вторую вкладываются        , тогда доход           . Средства тратятся, принося доход, а новых средств не поступает и полученный доход не вкладывается.
Описание слайда:
Рассмотрим классическую задачу распределения ресурсов. Рассмотрим классическую задачу распределения ресурсов. Имеется начальное количество ресурсов , которые необходимо распределить между двумя отраслями. Каждая отрасль работает в течении m лет. Если в первую отрасль в i-ый год вкладываются средства , то доход , если же во вторую вкладываются , тогда доход . Средства тратятся, принося доход, а новых средств не поступает и полученный доход не вкладывается.

Слайд 21





      Нас интересует суммарный доход: 
      Нас интересует суммарный доход: 
      Суммарный выигрыш равен сумме выигрышей на каждом шаге. Состоянием системы является количество средств перед i-ым шагом. Так как новых средств не поступает, то ресурсы «тают».
      Управление        может быть записано как
Описание слайда:
Нас интересует суммарный доход: Нас интересует суммарный доход: Суммарный выигрыш равен сумме выигрышей на каждом шаге. Состоянием системы является количество средств перед i-ым шагом. Так как новых средств не поступает, то ресурсы «тают». Управление может быть записано как

Слайд 22





После i-го шага в первой отрасли остаются средства            а во второй                              
После i-го шага в первой отрасли остаются средства            а во второй                              
Эти функции называются функциями траты. Мы можем составить уравнение Беллмана. В этой задаче на i-ом шаге одно управление      и одно состояние
Описание слайда:
После i-го шага в первой отрасли остаются средства а во второй После i-го шага в первой отрасли остаются средства а во второй Эти функции называются функциями траты. Мы можем составить уравнение Беллмана. В этой задаче на i-ом шаге одно управление и одно состояние

Слайд 23





   
   
     Исследуя функции траты, получим количество средств после i-го шага:
    Задача о распределении ресурсов допускает геометрическую интерпретацию.
    Распределение на первом шаге – указание точки на гипотенузе. После этого средства тратятся
Описание слайда:
Исследуя функции траты, получим количество средств после i-го шага: Задача о распределении ресурсов допускает геометрическую интерпретацию. Распределение на первом шаге – указание точки на гипотенузе. После этого средства тратятся

Слайд 24





Распределение средств – движение внутрь треугольника. Рассмотрим частные случаи задач о распределении ресурсов.
Описание слайда:
Распределение средств – движение внутрь треугольника. Рассмотрим частные случаи задач о распределении ресурсов.

Слайд 25





Распределение по неоднородным этапам.
    Выше мы считали, что все функции одинаковы на всех этапах. Во многих задачах функции меняются от этапа к этапу: 
   Покажем, что процедура динамического программирования принципиально не меняется. Запишем уравнение Беллмана:
Описание слайда:
Распределение по неоднородным этапам. Выше мы считали, что все функции одинаковы на всех этапах. Во многих задачах функции меняются от этапа к этапу: Покажем, что процедура динамического программирования принципиально не меняется. Запишем уравнение Беллмана:

Слайд 26





Распределение ресурсов между тремя и более отраслями.
    В этом случае на каждом шаге будет уже  управлений, но одно из них может быть выражено как: 
    В этом случае, в правой части уравнения Беллмана будет две и более переменных, по которым ищется максимум, и задача усложняется.
Описание слайда:
Распределение ресурсов между тремя и более отраслями. В этом случае на каждом шаге будет уже управлений, но одно из них может быть выражено как: В этом случае, в правой части уравнения Беллмана будет две и более переменных, по которым ищется максимум, и задача усложняется.

Слайд 27





Распределение ресурсов с резервированием.
    В такой модели если средства распределяются между двумя  отраслями, то какое-то количество средств можно оставить до последующего распределения. В этом случае  задача имеет смысл даже для одной отрасли. Начальное количество средств разделяется на первом этапе на        и на               (резерв), на втором этапе подлежат разделению средства из резерва. Такую задачу можно представить как с одной отраслью реальной, а другой фиктивной (не приносящей доход и не расходующей средства).
Описание слайда:
Распределение ресурсов с резервированием. В такой модели если средства распределяются между двумя отраслями, то какое-то количество средств можно оставить до последующего распределения. В этом случае задача имеет смысл даже для одной отрасли. Начальное количество средств разделяется на первом этапе на и на (резерв), на втором этапе подлежат разделению средства из резерва. Такую задачу можно представить как с одной отраслью реальной, а другой фиктивной (не приносящей доход и не расходующей средства).

Слайд 28





   Решение такой задачи сводится к классической, задав функции дохода и трат.
   Решение такой задачи сводится к классической, задав функции дохода и трат.
   
    Подставив их в уравнение Беллмана, можно решить задачу как классическую. Задача может быть упрощена до следующей:
Описание слайда:
Решение такой задачи сводится к классической, задав функции дохода и трат. Решение такой задачи сводится к классической, задав функции дохода и трат. Подставив их в уравнение Беллмана, можно решить задачу как классическую. Задача может быть упрощена до следующей:

Слайд 29





   Задача линейного программирования с одной переменной.
   Задача линейного программирования с одной переменной.
    Пусть вид функции            не убывающий в этом случае недоиспользовать средства не выгодно. В этом случае решение допускают теоремы, обосновывающие, если:
    1.             неубывающая и выпуклая вверх, оптимальное распределение ресурсов равномерное.
    2.              возрастающая и выпуклая вниз, оптимальное решение – вложить все средства в один этап, и ничего не зарезервировать.
Описание слайда:
Задача линейного программирования с одной переменной. Задача линейного программирования с одной переменной. Пусть вид функции не убывающий в этом случае недоиспользовать средства не выгодно. В этом случае решение допускают теоремы, обосновывающие, если: 1. неубывающая и выпуклая вверх, оптимальное распределение ресурсов равномерное. 2. возрастающая и выпуклая вниз, оптимальное решение – вложить все средства в один этап, и ничего не зарезервировать.

Слайд 30





   Таким образом приходим к классической задаче. 
   Таким образом приходим к классической задаче. 
      Трата || оси Х.
Описание слайда:
Таким образом приходим к классической задаче. Таким образом приходим к классической задаче. Трата || оси Х.

Слайд 31





       Задача с резервированием в одной отрасли при параллельных функциях траты.
       Задача с резервированием в одной отрасли при параллельных функциях траты.
       Все функции траты
Описание слайда:
Задача с резервированием в одной отрасли при параллельных функциях траты. Задача с резервированием в одной отрасли при параллельных функциях траты. Все функции траты

Слайд 32


  
  Динамическое программирование  , слайд №32
Описание слайда:

Слайд 33





          Эти функции неубывающие.
          Эти функции неубывающие.
                                                   (1)
                                                   
                                                   (2)
         
        (2) – равенство, т.к. функция неубывающая и недоиспользование средств невыгодно. 
       Это имеет теоретическое обоснование:
       1. если функция неубывающая и выпуклая вверх, то оптимальным распределением является равномерное распределение.
       2  если функция неубывающая и выпуклая вниз, то оптимальным распределением является такое: все распределение в один этап (элемент) и ничего в другие.
Описание слайда:
Эти функции неубывающие. Эти функции неубывающие. (1) (2) (2) – равенство, т.к. функция неубывающая и недоиспользование средств невыгодно. Это имеет теоретическое обоснование: 1. если функция неубывающая и выпуклая вверх, то оптимальным распределением является равномерное распределение. 2 если функция неубывающая и выпуклая вниз, то оптимальным распределением является такое: все распределение в один этап (элемент) и ничего в другие.

Слайд 34





Распределение ресурсов «с вложением доходов в производство».
   В классической задаче считается, что полученный доход на i-ом шаге в производство не вкладывается, т. е. он отчисляется и подсчитывается как эффект. 
   Во многих задачах полученный эффект можно использовать как ресурс для следующего шага объединяя его с оставшимся ресурсом. 
   Если ресурс не деньги, то средства можно привести к единому эквиваленту с оставшимися средствами. Такая модель является развитием классической модели.
Описание слайда:
Распределение ресурсов «с вложением доходов в производство». В классической задаче считается, что полученный доход на i-ом шаге в производство не вкладывается, т. е. он отчисляется и подсчитывается как эффект. Во многих задачах полученный эффект можно использовать как ресурс для следующего шага объединяя его с оставшимся ресурсом. Если ресурс не деньги, то средства можно привести к единому эквиваленту с оставшимися средствами. Такая модель является развитием классической модели.

Слайд 35





   Так как оставшиеся средства и доход объединяются, то можно ввести единую интегральную функцию – функцию изменения средств. 
   Так как оставшиеся средства и доход объединяются, то можно ввести единую интегральную функцию – функцию изменения средств. 
                  количество оставшихся средств плюс доход после i-го шага, если вложили           
    I    
    II
           количество средств перед i-м шагом.
Описание слайда:
Так как оставшиеся средства и доход объединяются, то можно ввести единую интегральную функцию – функцию изменения средств. Так как оставшиеся средства и доход объединяются, то можно ввести единую интегральную функцию – функцию изменения средств. количество оставшихся средств плюс доход после i-го шага, если вложили I II количество средств перед i-м шагом.

Слайд 36





    Выигрыш на i-ом шаге зависит от того, как мы подсчитываем доход (эффект) от управления всеми ресурсами. Поставим задачу: максимальный доход в конце          го шага. Тогда на всех шагах                   доход = 0,
    Выигрыш на i-ом шаге зависит от того, как мы подсчитываем доход (эффект) от управления всеми ресурсами. Поставим задачу: максимальный доход в конце          го шага. Тогда на всех шагах                   доход = 0,
    На          ом шаге выигрыш 
    Подставив эти выражения в уравнение Беллмана, мы программируем задачу от начала к концу, если имеется начальное количество средств 
    Здесь функция траты:
Описание слайда:
Выигрыш на i-ом шаге зависит от того, как мы подсчитываем доход (эффект) от управления всеми ресурсами. Поставим задачу: максимальный доход в конце го шага. Тогда на всех шагах доход = 0, Выигрыш на i-ом шаге зависит от того, как мы подсчитываем доход (эффект) от управления всеми ресурсами. Поставим задачу: максимальный доход в конце го шага. Тогда на всех шагах доход = 0, На ом шаге выигрыш Подставив эти выражения в уравнение Беллмана, мы программируем задачу от начала к концу, если имеется начальное количество средств Здесь функция траты:

Слайд 37





      
      
       Частный случай: когда       и      неубывающие
       В этом случае чем больше значение доход + средства получается в конце i-го шага, тем лучшим условием это будет для проведения 
                   шага. Поэтому можно не заботиться о следующих шагах, достаточно обеспечить максимум на каждом шаге.
Описание слайда:
Частный случай: когда и неубывающие В этом случае чем больше значение доход + средства получается в конце i-го шага, тем лучшим условием это будет для проведения шага. Поэтому можно не заботиться о следующих шагах, достаточно обеспечить максимум на каждом шаге.

Слайд 38





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

Слайд 39





    Рассмотрим задачу распределения ресурсов с вложением доходов в производство и отчислением. Это наиболее общий случай. Разделим функции дохода и функции траты: 
    Рассмотрим задачу распределения ресурсов с вложением доходов в производство и отчислением. Это наиболее общий случай. Разделим функции дохода и функции траты: 
                                  и максимальный суммарный отчисленный доход + оставшиеся средства после       - го шага.
Описание слайда:
Рассмотрим задачу распределения ресурсов с вложением доходов в производство и отчислением. Это наиболее общий случай. Разделим функции дохода и функции траты: Рассмотрим задачу распределения ресурсов с вложением доходов в производство и отчислением. Это наиболее общий случай. Разделим функции дохода и функции траты: и максимальный суммарный отчисленный доход + оставшиеся средства после - го шага.

Слайд 40





         Введём функцию отчисления 
         Введём функцию отчисления 
            доход. Тогда выигрыш на каждом шаге:
Описание слайда:
Введём функцию отчисления Введём функцию отчисления доход. Тогда выигрыш на каждом шаге:

Слайд 41





      Уравнение Беллмана для го шага будет выглядеть так:
      Уравнение Беллмана для го шага будет выглядеть так:
     для              надо учесть 
     Если          то мы получаем классическую задачу.
Описание слайда:
Уравнение Беллмана для го шага будет выглядеть так: Уравнение Беллмана для го шага будет выглядеть так: для надо учесть Если то мы получаем классическую задачу.

Слайд 42





Учёт предыстории процесса.
    Мы считаем, что функции как выигрыша, так и траты зависят от состояния перед i-ым шагом, т. е. не зависят от более ранних состояний. Такие процессы называются процессами без памяти. Но иногда при рассмотрении процессов, связанных с «живыми» организациями требуется помнить всю историю происходящего. Такая задача более сложна.
Описание слайда:
Учёт предыстории процесса. Мы считаем, что функции как выигрыша, так и траты зависят от состояния перед i-ым шагом, т. е. не зависят от более ранних состояний. Такие процессы называются процессами без памяти. Но иногда при рассмотрении процессов, связанных с «живыми» организациями требуется помнить всю историю происходящего. Такая задача более сложна.

Слайд 43





       Введём расширенное состояние: 
       Введём расширенное состояние: 
              состояние за        шагов до i-го. 
        Тогда                                                
       Но задача сложна вычислительном аспекте. 
       Пусть      имеет      координат и предыстория распространяется на       шагов, тогда результат
            . Вот почему подобные задачи можно решать если                 .
Описание слайда:
Введём расширенное состояние: Введём расширенное состояние: состояние за шагов до i-го. Тогда Но задача сложна вычислительном аспекте. Пусть имеет координат и предыстория распространяется на шагов, тогда результат . Вот почему подобные задачи можно решать если .

Слайд 44





Задача  с мультипликативным критерием.
    До сих пор мы считали, что суммарный выигрыш равен сумме выигрыш на i-ом шаге. Но есть задачи, где общий критерий равен произведению критериальных величин на каждом шаге. В этом случае так же можно применить уравнение Беллмана.
                        но вместо этого можно взять      
                        функцию                               
     Оптимальные решения будут одинаковы ввиду многоэтапности функций.
Описание слайда:
Задача с мультипликативным критерием. До сих пор мы считали, что суммарный выигрыш равен сумме выигрыш на i-ом шаге. Но есть задачи, где общий критерий равен произведению критериальных величин на каждом шаге. В этом случае так же можно применить уравнение Беллмана. но вместо этого можно взять функцию Оптимальные решения будут одинаковы ввиду многоэтапности функций.

Слайд 45





      Но можно при вводе уравнения Беллмана учесть, что:
      Но можно при вводе уравнения Беллмана учесть, что:
   Пример: устройство состоит из  узлов. Имеется некоторое устройство      , которое может использоваться для повышения надёжности каждого узла. Необходимо так распределить ресурс, чтобы суммарная надёжность была максимальной.           надёжность каждого узла.
Описание слайда:
Но можно при вводе уравнения Беллмана учесть, что: Но можно при вводе уравнения Беллмана учесть, что: Пример: устройство состоит из узлов. Имеется некоторое устройство , которое может использоваться для повышения надёжности каждого узла. Необходимо так распределить ресурс, чтобы суммарная надёжность была максимальной. надёжность каждого узла.

Слайд 46





Операции не связанные со временем 
 Во многих задачах распределение ресурсов не связано с временными шагами. Ресурс обычно распределяется по объектам. Например, если расписать распределение ресурсов между n объектами и на каждый объект задана функция выигрыша, то такая задача эквивалентна рассмотренной нами задаче о распределении ресурсов с резервированием в одной отрасли по n шагам.
Описание слайда:
Операции не связанные со временем Во многих задачах распределение ресурсов не связано с временными шагами. Ресурс обычно распределяется по объектам. Например, если расписать распределение ресурсов между n объектами и на каждый объект задана функция выигрыша, то такая задача эквивалентна рассмотренной нами задаче о распределении ресурсов с резервированием в одной отрасли по n шагам.

Слайд 47





   Рассмотрим технику расчетов метода динамического программирования на примере.
   Рассмотрим технику расчетов метода динамического программирования на примере.
   Задача: Распределение объема строительно–монтажных  работ на объекте по кварталам планового года составляет: 2 млн. руб. на первый квартал, 5 млн. руб. на второй квартал, 3 млн. руб. на третий и 1 млн. руб. на четвертый. Подрядная организация планирует, какие производственные мощности должны быть на объекте. Работа ведется в две смены, но при необходимости может быть организована и третья смена. Если понадобится уменьшить производственные мощности на объекте, то затраты по их переброске на другие объекты составят 70 тыс. руб. на каждый млн. руб. выполняемого объема работ.
Описание слайда:
Рассмотрим технику расчетов метода динамического программирования на примере. Рассмотрим технику расчетов метода динамического программирования на примере. Задача: Распределение объема строительно–монтажных работ на объекте по кварталам планового года составляет: 2 млн. руб. на первый квартал, 5 млн. руб. на второй квартал, 3 млн. руб. на третий и 1 млн. руб. на четвертый. Подрядная организация планирует, какие производственные мощности должны быть на объекте. Работа ведется в две смены, но при необходимости может быть организована и третья смена. Если понадобится уменьшить производственные мощности на объекте, то затраты по их переброске на другие объекты составят 70 тыс. руб. на каждый млн. руб. выполняемого объема работ.

Слайд 48





    Если потребуется ввести новые производственные мощности, то затраты на это составят 100 тыс. руб. по каждому млн. руб. выполняемого объема работ. Если на объекте будут находиться неиспользованные мощности, то на каждый млн. руб. объема потери будут составлять 80 тыс. руб. При нехватке мощностей и организации дополнительной третьей смены будет дополнительно расходоваться 110 тыс. руб. Перед началом планового периода на объекте имеется столько производственных мощностей, сколько нужно для выполнения работ объемом 2 млн. руб.
    Если потребуется ввести новые производственные мощности, то затраты на это составят 100 тыс. руб. по каждому млн. руб. выполняемого объема работ. Если на объекте будут находиться неиспользованные мощности, то на каждый млн. руб. объема потери будут составлять 80 тыс. руб. При нехватке мощностей и организации дополнительной третьей смены будет дополнительно расходоваться 110 тыс. руб. Перед началом планового периода на объекте имеется столько производственных мощностей, сколько нужно для выполнения работ объемом 2 млн. руб.
    Найти оптимальное распределение производственных мощностей по кварталам планового года.
Описание слайда:
Если потребуется ввести новые производственные мощности, то затраты на это составят 100 тыс. руб. по каждому млн. руб. выполняемого объема работ. Если на объекте будут находиться неиспользованные мощности, то на каждый млн. руб. объема потери будут составлять 80 тыс. руб. При нехватке мощностей и организации дополнительной третьей смены будет дополнительно расходоваться 110 тыс. руб. Перед началом планового периода на объекте имеется столько производственных мощностей, сколько нужно для выполнения работ объемом 2 млн. руб. Если потребуется ввести новые производственные мощности, то затраты на это составят 100 тыс. руб. по каждому млн. руб. выполняемого объема работ. Если на объекте будут находиться неиспользованные мощности, то на каждый млн. руб. объема потери будут составлять 80 тыс. руб. При нехватке мощностей и организации дополнительной третьей смены будет дополнительно расходоваться 110 тыс. руб. Перед началом планового периода на объекте имеется столько производственных мощностей, сколько нужно для выполнения работ объемом 2 млн. руб. Найти оптимальное распределение производственных мощностей по кварталам планового года.

Слайд 49





      1-ый этап. Описание системы.
      1-ый этап. Описание системы.
    Обозначим производственные мощности, имеющиеся в начале i-го квартала (i=1,2,3,4). За единицу примем производственные мощности для выполнения объема работ в один млн. руб. Обозначим через         требуемое количество производственных мощностей для выполнения заданного в i-ом квартале объема работ
   (                                         ). Состояние системы
          таким образом, определяется величиной
Описание слайда:
1-ый этап. Описание системы. 1-ый этап. Описание системы. Обозначим производственные мощности, имеющиеся в начале i-го квартала (i=1,2,3,4). За единицу примем производственные мощности для выполнения объема работ в один млн. руб. Обозначим через требуемое количество производственных мощностей для выполнения заданного в i-ом квартале объема работ ( ). Состояние системы таким образом, определяется величиной

Слайд 50





      Управление          состоит, 
      Управление          состоит, 
   во-первых, в переброске производственных мощностей с рассматриваемого объекта на какие-либо другие или, наоборот, с каких-либо объектов на рассматриваемый объект, 
   во-вторых, в организации дополнительной третьей смены при нехватке производственных мощностей. 
   Затраты при оптимальном управлении должны быть минимальными. Естественным временным шагом процесса управления является квартал планового года.
Описание слайда:
Управление состоит, Управление состоит, во-первых, в переброске производственных мощностей с рассматриваемого объекта на какие-либо другие или, наоборот, с каких-либо объектов на рассматриваемый объект, во-вторых, в организации дополнительной третьей смены при нехватке производственных мощностей. Затраты при оптимальном управлении должны быть минимальными. Естественным временным шагом процесса управления является квартал планового года.

Слайд 51





     2-й этап. Определение функций эффекта для i-го шага.
     2-й этап. Определение функций эффекта для i-го шага.
    В зависимости от применяемого управления, т.е. изменения производственных мощностей   
    на объекте, либо дополнительного использования имеющихся мощностей за счет организации третьей смены затраты определяются различным образом.
    При изменении (переброске мощностей) функцию затрат по условиям задачи можно записать следующим образом:
Описание слайда:
2-й этап. Определение функций эффекта для i-го шага. 2-й этап. Определение функций эффекта для i-го шага. В зависимости от применяемого управления, т.е. изменения производственных мощностей на объекте, либо дополнительного использования имеющихся мощностей за счет организации третьей смены затраты определяются различным образом. При изменении (переброске мощностей) функцию затрат по условиям задачи можно записать следующим образом:

Слайд 52






    а при неизменном         (сохранении уровня мощности):
     общая  функция затрат имеет вид:
Описание слайда:
а при неизменном (сохранении уровня мощности): общая функция затрат имеет вид:

Слайд 53





    3-й этап. Определение функции изменения состояния системы(производственных мощностей) на i-ом шаге.
    3-й этап. Определение функции изменения состояния системы(производственных мощностей) на i-ом шаге.
    В конце i-го шага производственные мощности должны быть равны мощностям в начале (i+1)-го шага, запишем:
Описание слайда:
3-й этап. Определение функции изменения состояния системы(производственных мощностей) на i-ом шаге. 3-й этап. Определение функции изменения состояния системы(производственных мощностей) на i-ом шаге. В конце i-го шага производственные мощности должны быть равны мощностям в начале (i+1)-го шага, запишем:

Слайд 54





     4-й этап. Запись основного рекуррентного соотношения динамического программирования.
     4-й этап. Запись основного рекуррентного соотношения динамического программирования.
    Оно имеет вид:
   
    Здесь                 и                         - затраты соответственно на i-ом и  (i+1)-м шагах.
Описание слайда:
4-й этап. Запись основного рекуррентного соотношения динамического программирования. 4-й этап. Запись основного рекуррентного соотношения динамического программирования. Оно имеет вид: Здесь и - затраты соответственно на i-ом и (i+1)-м шагах.

Слайд 55





     5-й этап. Определение оптимальных затрат на последнем четвертом шаге:
     5-й этап. Определение оптимальных затрат на последнем четвертом шаге:

     В этой формуле:
      а при неизменном       (сохранении уровня мощности):
     где         и          - производственные мощности в 3-м и  
     4-м кварталах.
Описание слайда:
5-й этап. Определение оптимальных затрат на последнем четвертом шаге: 5-й этап. Определение оптимальных затрат на последнем четвертом шаге: В этой формуле: а при неизменном (сохранении уровня мощности): где и - производственные мощности в 3-м и 4-м кварталах.

Слайд 56





    Можно предположить, что производственные мощности в третьем квартале отсутствуют или составляют 1,2,3,4,5, единиц.
    Можно предположить, что производственные мощности в третьем квартале отсутствуют или составляют 1,2,3,4,5, единиц.
    Рассчитаем условные минимальные затраты для каждого предположения, изменяя величину мощности в четвертом квартале (т.е. осуществляя различные управления).
 При      =0 и       =0,                 = 0+110(1-0) =110 тыс. руб.
               =1,                =100(1-0)+0=100 тыс.руб. 
               =2,                =100(2-0)+80(2-1)=280 тыс. руб.
Описание слайда:
Можно предположить, что производственные мощности в третьем квартале отсутствуют или составляют 1,2,3,4,5, единиц. Можно предположить, что производственные мощности в третьем квартале отсутствуют или составляют 1,2,3,4,5, единиц. Рассчитаем условные минимальные затраты для каждого предположения, изменяя величину мощности в четвертом квартале (т.е. осуществляя различные управления). При =0 и =0, = 0+110(1-0) =110 тыс. руб. =1, =100(1-0)+0=100 тыс.руб. =2, =100(2-0)+80(2-1)=280 тыс. руб.

Слайд 57





    Далее, очевидно,              что  будет расти, поэтому нет смысла продолжать расчеты. Наименьшие затраты составляют 100 тыс. руб.
    Далее, очевидно,              что  будет расти, поэтому нет смысла продолжать расчеты. Наименьшие затраты составляют 100 тыс. руб.
При       =1 и       =0,                =70 (1-00+110(1-0)=180
            =1,                =0+0=0,
              =2,                   =100(2-1)+80(2-1)=180 и т.д. 
При         =2 и         =0,                   =70(2-0)+110(1-0)=250
               =1,                =70(2-1)+0=70
                =2,                =0+80(2-1)=80 и т.д.
Описание слайда:
Далее, очевидно, что будет расти, поэтому нет смысла продолжать расчеты. Наименьшие затраты составляют 100 тыс. руб. Далее, очевидно, что будет расти, поэтому нет смысла продолжать расчеты. Наименьшие затраты составляют 100 тыс. руб. При =1 и =0, =70 (1-00+110(1-0)=180 =1, =0+0=0, =2, =100(2-1)+80(2-1)=180 и т.д. При =2 и =0, =70(2-0)+110(1-0)=250 =1, =70(2-1)+0=70 =2, =0+80(2-1)=80 и т.д.

Слайд 58





При         =3 и         =0,                   =70(3-0)+110(1-0)=320
При         =3 и         =0,                   =70(3-0)+110(1-0)=320
                 =1                 =70(3-1)+0=140
                =2,                   =70(3-2)+80(2-1)=150
                 =3,                   =0+80(3-1)=160 и т.д. 
При          =4 и          =0,                =70(4-0)+110(1-0)=390
                 =1,                  =70(4-1)+0=210
                 =2,                  =70(4-2)+80(2-1) 220 и т.д.
При          =5 и        =0,                 =70(5-0)+110(1-0)=450
                 =1,                 =70(5-1)+0=280
                 =2,                 =70(5-2)+80(2-1)=290 и т.д.
Описание слайда:
При =3 и =0, =70(3-0)+110(1-0)=320 При =3 и =0, =70(3-0)+110(1-0)=320 =1 =70(3-1)+0=140 =2, =70(3-2)+80(2-1)=150 =3, =0+80(3-1)=160 и т.д. При =4 и =0, =70(4-0)+110(1-0)=390 =1, =70(4-1)+0=210 =2, =70(4-2)+80(2-1) 220 и т.д. При =5 и =0, =70(5-0)+110(1-0)=450 =1, =70(5-1)+0=280 =2, =70(5-2)+80(2-1)=290 и т.д.

Слайд 59





   Отберем все минимальные (условно-оптимальные) значения затрат в четвертом квартале и соответствующие им величины производственных мощностей (управления) в таблицу 1.
   Отберем все минимальные (условно-оптимальные) значения затрат в четвертом квартале и соответствующие им величины производственных мощностей (управления) в таблицу 1.
Описание слайда:
Отберем все минимальные (условно-оптимальные) значения затрат в четвертом квартале и соответствующие им величины производственных мощностей (управления) в таблицу 1. Отберем все минимальные (условно-оптимальные) значения затрат в четвертом квартале и соответствующие им величины производственных мощностей (управления) в таблицу 1.

Слайд 60





    6-й этап. Определение условно-оптимальных затрат, а также соответствующих им управлений на третьем, втором и первом этапах процесса.
    6-й этап. Определение условно-оптимальных затрат, а также соответствующих им управлений на третьем, втором и первом этапах процесса.
    Для третьего квартала(предпоследний шаг процесса) рекуррентное соотношение имеет вид:
     
    где
    и
Описание слайда:
6-й этап. Определение условно-оптимальных затрат, а также соответствующих им управлений на третьем, втором и первом этапах процесса. 6-й этап. Определение условно-оптимальных затрат, а также соответствующих им управлений на третьем, втором и первом этапах процесса. Для третьего квартала(предпоследний шаг процесса) рекуррентное соотношение имеет вид: где и

Слайд 61





    Предположим, что производственные мощности во втором квартале могут иметь уровень от 0 до 5 единиц. Рассчитаем затраты при этих предположениях. Значения                 будем брать из таблицы1.
    Предположим, что производственные мощности во втором квартале могут иметь уровень от 0 до 5 единиц. Рассчитаем затраты при этих предположениях. Значения                 будем брать из таблицы1.
При         =0 и         =0,                 =0+110(3-0)+100=430
                =1,                =100(1-0)+110(3-1)+0=320
                =2,                 =100(2-0)+110(3-2)+70=380  и т.д.
При        =1 и        =0,                 =70(1-0)+110(3-0)+100=500
               =1,                =0+110(3-1)+0=220
                =2,                 =100(2-1)+110(3-2)+70=280 и т. д.
Описание слайда:
Предположим, что производственные мощности во втором квартале могут иметь уровень от 0 до 5 единиц. Рассчитаем затраты при этих предположениях. Значения будем брать из таблицы1. Предположим, что производственные мощности во втором квартале могут иметь уровень от 0 до 5 единиц. Рассчитаем затраты при этих предположениях. Значения будем брать из таблицы1. При =0 и =0, =0+110(3-0)+100=430 =1, =100(1-0)+110(3-1)+0=320 =2, =100(2-0)+110(3-2)+70=380 и т.д. При =1 и =0, =70(1-0)+110(3-0)+100=500 =1, =0+110(3-1)+0=220 =2, =100(2-1)+110(3-2)+70=280 и т. д.

Слайд 62





При        =2 и        =0,                 =70(2-0)+110(3-0)+100= 670
При        =2 и        =0,                 =70(2-0)+110(3-0)+100= 670
               =1,                =70(2-1)+110(3-1)+0=290 
               =2,                =0+110(3-2)+70=180 
               =3,                =100(3-2)+0+140=240 и т.д.
При        =3 и        =0,               =70(3-0)+110(3-0)+100=640 
               =1,                =70(3-1)+110(3-1)+0=360 
               =2,                =70(3-2)+110(3-2)+70=250 
               =3,                =0+0+140=140 
               =4,                =100(4-3)+80(4-3)+210=390 и т.д.
    Далее, учитывая, что начинать с        =0 нет смысла, продолжим расчеты.
Описание слайда:
При =2 и =0, =70(2-0)+110(3-0)+100= 670 При =2 и =0, =70(2-0)+110(3-0)+100= 670 =1, =70(2-1)+110(3-1)+0=290 =2, =0+110(3-2)+70=180 =3, =100(3-2)+0+140=240 и т.д. При =3 и =0, =70(3-0)+110(3-0)+100=640 =1, =70(3-1)+110(3-1)+0=360 =2, =70(3-2)+110(3-2)+70=250 =3, =0+0+140=140 =4, =100(4-3)+80(4-3)+210=390 и т.д. Далее, учитывая, что начинать с =0 нет смысла, продолжим расчеты.

Слайд 63





При        =4 и       =2,                =70(4-2)+110(3-2)+70=320
При        =4 и       =2,                =70(4-2)+110(3-2)+70=320
                =3,                 =70(4-3)+0+140=210
                =4,                 =0+80(4-3)+210=290 и т.д.
При        =5 и       =2,                =70(5-2)+110(3-2)+70=390
                =3,                 =70(5-3)+0+140=280
                =4,                 =70(5-4)+80(4-3)+210=380 и т.д.
    Отберем все минимальные(условно-оптимальные) значения затрат в третьем квартале и соответствующие им величины производственных мощностей в 3-м и 4-м кварталах в таблицу2.
Описание слайда:
При =4 и =2, =70(4-2)+110(3-2)+70=320 При =4 и =2, =70(4-2)+110(3-2)+70=320 =3, =70(4-3)+0+140=210 =4, =0+80(4-3)+210=290 и т.д. При =5 и =2, =70(5-2)+110(3-2)+70=390 =3, =70(5-3)+0+140=280 =4, =70(5-4)+80(4-3)+210=380 и т.д. Отберем все минимальные(условно-оптимальные) значения затрат в третьем квартале и соответствующие им величины производственных мощностей в 3-м и 4-м кварталах в таблицу2.

Слайд 64


  
  Динамическое программирование  , слайд №64
Описание слайда:

Слайд 65





      Второй квартал(предпоследний процесс),
      Второй квартал(предпоследний процесс),
      где
      и
Описание слайда:
Второй квартал(предпоследний процесс), Второй квартал(предпоследний процесс), где и

Слайд 66





При      =0 и       =0,                 =0+110(5-0)+320=870
При      =0 и       =0,                 =0+110(5-0)+320=870
              =1,                =100(1-0)+110(5-1)+220=760 
              =2,                =100(2-0)+110(5-2)+180=710
              =3,                =100(3-0)+110(5-3)+140=660
              =4,                =100(4-0)+110(5-4)+70=720 и т.д.
При       =1 и       =2,              =100(2-1)+110(5-2)+180=610
              =3,                =100(3-1)+110(5-3)+140=560 
              =4,                =100(4-1)+110(5-4)+210=620 и т.д.
При       =2 и        =2,              =0+110(5-2)+180=510 
              =3,                =100(3-2)+110(5-3)+140=460
              =4,                =100(4-2)+110(5-4)+210=520 и т.д.
Описание слайда:
При =0 и =0, =0+110(5-0)+320=870 При =0 и =0, =0+110(5-0)+320=870 =1, =100(1-0)+110(5-1)+220=760 =2, =100(2-0)+110(5-2)+180=710 =3, =100(3-0)+110(5-3)+140=660 =4, =100(4-0)+110(5-4)+70=720 и т.д. При =1 и =2, =100(2-1)+110(5-2)+180=610 =3, =100(3-1)+110(5-3)+140=560 =4, =100(4-1)+110(5-4)+210=620 и т.д. При =2 и =2, =0+110(5-2)+180=510 =3, =100(3-2)+110(5-3)+140=460 =4, =100(4-2)+110(5-4)+210=520 и т.д.

Слайд 67





При        =3 и        =2,               =70(3-2)+110(5-2)+180=610
При        =3 и        =2,               =70(3-2)+110(5-2)+180=610
               =3,               =0+110(5-3)+140=360
               =4,                =100(4-3)+110(5-4)+210=420 и т.д.
При        =4 и         =2,               =70(4-2)+110(5-2)+180=650
               =3,                =70(4-3)+110(5-3)+140=430 
               =4,                =0+110(5-4)+210=320
               =5,                =100(5-4)+0+280=380
При        =5 и         =3,               =70(5-3)+110(5-3)+140=500
               =4,                 =70(5-4)+110(5-4)+210=390 
               =5,                 =0+0+280=280
Описание слайда:
При =3 и =2, =70(3-2)+110(5-2)+180=610 При =3 и =2, =70(3-2)+110(5-2)+180=610 =3, =0+110(5-3)+140=360 =4, =100(4-3)+110(5-4)+210=420 и т.д. При =4 и =2, =70(4-2)+110(5-2)+180=650 =3, =70(4-3)+110(5-3)+140=430 =4, =0+110(5-4)+210=320 =5, =100(5-4)+0+280=380 При =5 и =3, =70(5-3)+110(5-3)+140=500 =4, =70(5-4)+110(5-4)+210=390 =5, =0+0+280=280

Слайд 68





     Отберем оптимальные затраты и соответствующие производственные мощности в таблицу 3.
     Отберем оптимальные затраты и соответствующие производственные мощности в таблицу 3.
Описание слайда:
Отберем оптимальные затраты и соответствующие производственные мощности в таблицу 3. Отберем оптимальные затраты и соответствующие производственные мощности в таблицу 3.

Слайд 69





     Для первого квартала:
     Для первого квартала:
     где
     и
      Поскольку        задано по условиям задачи, найдем условно-оптимальные задачи только при    
          =2.
Описание слайда:
Для первого квартала: Для первого квартала: где и Поскольку задано по условиям задачи, найдем условно-оптимальные задачи только при =2.

Слайд 70





При        =2 и       =0,              =70(2-0)+110(2-0)+660=1020
При        =2 и       =0,              =70(2-0)+110(2-0)+660=1020
               =1,               =70(2-1)+110(2-1)+560=740  
               =2,               =0+0+460=460
               =3,               =100(3-2)+80(3-2)+360=540 и т.д.
   Таким образом, условно-оптимальные затраты на первом этапе процесса составляют 460 тыс. руб. при управлении       =2.
Описание слайда:
При =2 и =0, =70(2-0)+110(2-0)+660=1020 При =2 и =0, =70(2-0)+110(2-0)+660=1020 =1, =70(2-1)+110(2-1)+560=740 =2, =0+0+460=460 =3, =100(3-2)+80(3-2)+360=540 и т.д. Таким образом, условно-оптимальные затраты на первом этапе процесса составляют 460 тыс. руб. при управлении =2.

Слайд 71





    7-ой этап. Определение безусловно-оптимальных затрат управлений.
    7-ой этап. Определение безусловно-оптимальных затрат управлений.
    Для затрат в первом квартале оптимальным является управление      =2. Поскольку       = затраты в первом квартале равны 0. во втором квартале оптимальным управлением является       
          =3, затраты составляют 320 тыс. руб. В третьем квартале оптимальным также является управление       =3, а затраты соответственно составляют 0. Наконец,  в четвертом квартале оптимально управление        =1, при котором затраты составляют 140 тыс. руб. Общая сумма затрат составит 460 тыс. руб.
Описание слайда:
7-ой этап. Определение безусловно-оптимальных затрат управлений. 7-ой этап. Определение безусловно-оптимальных затрат управлений. Для затрат в первом квартале оптимальным является управление =2. Поскольку = затраты в первом квартале равны 0. во втором квартале оптимальным управлением является =3, затраты составляют 320 тыс. руб. В третьем квартале оптимальным также является управление =3, а затраты соответственно составляют 0. Наконец, в четвертом квартале оптимально управление =1, при котором затраты составляют 140 тыс. руб. Общая сумма затрат составит 460 тыс. руб.

Слайд 72





    Таким образом. Оптимальное распределение производственных мощностей на строящемся объекте соответствует следующему плану подрядной организации: в первом квартале используются имеющиеся мощности, рассчитанные на объем 2 млн. руб. строительно-монтажных работ; во втором квартале производственные мощности на объекте увеличиваются на одну условную единицу, этот их уровень не изменяется и в третьем квартале, а в четвертом  - две условные единицы производственных мощностей перебрасываются с рассматриваемого объекта на другие. Затраты по управлению производственными мощностями по этому плану будут минимальны и составят 460 тыс. руб.
    Таким образом. Оптимальное распределение производственных мощностей на строящемся объекте соответствует следующему плану подрядной организации: в первом квартале используются имеющиеся мощности, рассчитанные на объем 2 млн. руб. строительно-монтажных работ; во втором квартале производственные мощности на объекте увеличиваются на одну условную единицу, этот их уровень не изменяется и в третьем квартале, а в четвертом  - две условные единицы производственных мощностей перебрасываются с рассматриваемого объекта на другие. Затраты по управлению производственными мощностями по этому плану будут минимальны и составят 460 тыс. руб.
Описание слайда:
Таким образом. Оптимальное распределение производственных мощностей на строящемся объекте соответствует следующему плану подрядной организации: в первом квартале используются имеющиеся мощности, рассчитанные на объем 2 млн. руб. строительно-монтажных работ; во втором квартале производственные мощности на объекте увеличиваются на одну условную единицу, этот их уровень не изменяется и в третьем квартале, а в четвертом - две условные единицы производственных мощностей перебрасываются с рассматриваемого объекта на другие. Затраты по управлению производственными мощностями по этому плану будут минимальны и составят 460 тыс. руб. Таким образом. Оптимальное распределение производственных мощностей на строящемся объекте соответствует следующему плану подрядной организации: в первом квартале используются имеющиеся мощности, рассчитанные на объем 2 млн. руб. строительно-монтажных работ; во втором квартале производственные мощности на объекте увеличиваются на одну условную единицу, этот их уровень не изменяется и в третьем квартале, а в четвертом - две условные единицы производственных мощностей перебрасываются с рассматриваемого объекта на другие. Затраты по управлению производственными мощностями по этому плану будут минимальны и составят 460 тыс. руб.



Похожие презентации
Mypresentation.ru
Загрузить презентацию