Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






I. Пример решения задачи динамического программирования



Условие задачи. На предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использования приведены в таблице 1.1.

Зная, что затраты, связанные с приобретением и установкой нового оборудования, идентичного установленному, составляют 40 у. е., а заменяемое оборудование списывается, составить такой план замены оборудования в течении 5 лет, при котором общая прибыль за данный период времени была бы максимальна.

Таблица 1.1.

  Время τ, в течение которого используется оборудование (лет)
Годовой выпуск продукции R(τ) в стоимостном выражении (у.е.)
Ежегодные затраты Z(τ), связанные с содержанием и ремонтом оборудования (у.е)

Решение. Эту задачу можно рассматривать как задачу динамического программирования, в которой в качестве системы S выступает оборудование. Состояния этой системы определяются фактическим временем использования оборудования (его возрастом) τ, то есть описываются единственным параметром τ. В качестве управлений выступают решения о замене или сохранении оборудования, принимаемые в начале каждого года. Обозначим через u1 решение о сохранении оборудования, а через u2 – решение о замене оборудования. Тогда задача будет заключаться в нахождении такой стратегии управления, определяемой решениями, принимаемыми к началу каждого года, при которой общая прибыль предприятия за пятилетку максимальна.

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

Для определения условных оптимальных решений сначала необходимо составить функциональное уравнение Беллмана.

Так как мы предположили, что к началу k-го года ( k= ) может приниматься только одно из двух решений – заменять или не заменять оборудование, -- то прибыль предприятия за k-й год составит



,

где τ(k)- возраст оборудования к началу k-го года ( k = ); uk – управление, реализуемое к началу k-го года; Cn—стоимость нового оборудования.

Таким образом, в данной задаче уравнение Беллмана имеет вид

 

(1.1)

 

Используя уравнение 1.1. найдем решение исходной задачи.

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

Поскольку в начальный момент времени установлено новое оборудование (τ(1)=0), то возраст оборудования к началу пятого года может составлять 1, 2, 3 или 4 года.

Поэтому допустимые состояния системы: τ1(5)=1; τ2(5)=2; τ3(5)=3; τ4(5)=4. Для каждого из этих состояний найдем условно оптимальное решения и соответствующие значения функции F5(5)). Учитывая уравнение 1.1. и соотношение F6(k+1))=0, т. к. рассматривается последний год расчетного периода, получаем:

 

(1.2)

Подставляя в формулу 1.2 значения переменных, находим

Значит, условно оптимальное решение – u1—оставить оборудование.

Проведем аналогичные вычисления для других допустимых состояний оборудования к началу пятого года:

Полученные результаты сводим в таблицу 1.2.

 

Таблица 1.2

Возраст оборудования τ5 (лет) Значение функции F5(5)) (у.е.) Условно оптимальное решение (u0)
u1
u1
u1
u2

Рассмотрим теперь возможные состояния оборудования к началу четвертого года. Очевидно, допустимыми состояниями являются τ1(4)=1; τ2(4)=2; τ3(4)=3. для каждого из них определяем условно оптимальное решение и соответствующее значение функции F4(4)). Для этого используем уравнение 1.1 и данные таблиц 1.1 и 1.2.



Для τ1(4)=1 имеем

 

 

Аналогично находим

 

 

 

 

Полученные результаты вычислений заносим в таблицу 1.3

Таблица 1.2

Возраст оборудования τ1(4) (лет) Значения функции F4(4)) (у.е). Условно оптимальное решение (u0)
u1
u2
u2

Определим теперь условно оптимальные решения для каждого из допустимых состояний оборудования к началу третьего года. Такими состояниями являются τ1(3)=1; τ2(3)=2. В соответствии с уравнением 1.1 и таблицами 1.1 и 1.3 имеем

 

 

 

Из последнего выражения видно, что если к началу третьего года возраст оборудования составляет 2 года, то, независимо от того, какое решение будет принято, величина прибыли будет одна и та же. Это означает, что в качестве условно оптимального решения можно выбрать любое, выберем u2. Результаты расчетов сводим в таблицу 1.4

Таблица 1.4

Возраст оборудования τ1(3) (лет) Значения функции F3(3)) (у.е). Условно оптимальное решение (u0)
u1
u2

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

Таблица 1.5

Возраст оборудования τ(2) (лет) Значения функции F2(2)) (у.е). Условно оптимальное решение (u0)
u1

Согласно условию задачи в начальный момент времени установлено новое оборудование (τ(1)=0), поэтому проблемы выбора решений к началу первого года не существует: оборудование будет сохранено. Значит условно оптимальное решение u1, а значение функции

 

Таким образом, максимальная прибыль предприятия может быть равной 215 у.е. Она соответствует оптимальному плану замены оборудования, который получается на основе данных таблиц 1.2-1.5, т.е. в результате реализации второго этапа вычислительного процесса, состоящего в прохождении всех рассмотренных шагов с начала первого года до начала пятого года.

Для первого года решение безальтернативно: следует сохранить оборудование. Значит, возраст оборудования к началу второго года равен 1 году. Тогда в соответствии с таблицей 1.5 оптимальным решением для второго года будет решение о сохранении оборудования. Реализация такого решения приводит к тому, что возраст оборудования к началу третьего года составит 2 года. При таком возрасте, согласно таблице 1.4 оборудование в третьем году следует заменить. После замены оборудования его возраст к началу четвертого года составит 1 год. Согласно таблице 1.3. при таком возрасте его менять не следует. Поэтому возраст оборудования к началу пятого года составит 2 года, и по таблице 1.2 менять его нецелесообразно.

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

Таблица 1.6

Оптимальное решение Годы пятилетки
Сохранить оборудование Сохранить оборудование Заменить оборудование Сохранить оборудование Сохранить оборудование

Задание к лабораторной работе №4

1. Изучить теоретический материал по решению задач динамического программирования.

2. Разработать программу, реализующую метод решения задач динамического программирования. Язык программирования выбрать по своему усмотрению.

3. Программа должна иметь удобный и простой в понимании пользовательский интерфейс. Предусмотреть вывод на экран промежуточных результатов. В качестве входных данных использовать таблицу исходных значений. В качестве выходных данных значения найденных переменных.

4. Сформулировать задачу, выбранную в соответствии с вариантом задания в терминах динамического программирования и найти ее решение с помощью разработанной программы. Вариант задания выбирается по последней цифре зачетной книжки (если последняя цифра 0, то выбирается 10 вариант).

5. По результатам лабораторной работы оформить и защитить отчет.

Варианты задания к лабораторной работе №4

Вариант1.На предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использования приведены в таблице В1.

Затраты, связанные с приобретением и установкой нового оборудования составляют 10000 у. е. Составить оптимальный план замены оборудования в течении 9 лет, максимизирующий прибыль за данный период.

Таблица В1.

  Время τ, в течение которого используется оборудование (лет)
Годовой выпуск продукции R(τ) в стоимостном выражении (тыс. у.е.)
Ежегодные затраты Z(τ), связанные с содержанием и ремонтом оборудования (тыс. у.е)

 

Вариант 2.Для увеличения объема выпуска пользующийся повышенным спросом продукции, изготовляемой предприятием, выделены капиталовложения в объеме S=100 тыс.у.е. Использование i-м предприятием xi у.е из указанных средств обеспечивает прирост выпуска продукции, определяемый значением нелинейной функции fi(xi). Составить оптимальный план распределения продукции между четырьмя предприятиями, обеспечивающий максимальное увеличение выпуска продукции. Исходные данные для xi и fi(xi) приведены в таблице В2.

Таблица В2

Объем капиталовложений xi (тыс.у.е.) Прирост выпуска продукции fi(xi) в зависимости от объема капиталовложений (тыс. у.е.)
Предприятие 1 Предприятие 2 Предприятие 3 Предприятие 4

 

Вариант 3.На склад вместимостью W=90 м3 требуется разместить n = 3 различных типов оборудования. Объем данной единицы i-го типа оборудования равен V1=24 м3, V2 -19 м3, V3=16 м3, а цена единицы данного типа оборудования равна C1=960 у.е., С2=500 у.е., С3=250 у.е. Определить, сколько оборудования каждого типа следует поместить на склад, чтобы общая стоимость складируемого оборудования была максимальна.

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

Предприятие стремится найти оптимальный план производства продукции в течении четырех месяцев, потребности в товарах в эти месяцы: 2000, 3000, 3000, 2000 единиц товара. Запасы к началу планируемого периода равны 2000 изделий. В каждом месяце предприятие может производить не более 4000 изделий. Одновременно на складе может хранится не более 4000 изделий. Затраты, связанные с производством 1000, 2000, 3000 и 4000 изделий составляют соответственно 13, 15, 17 и 19 у.е., а затраты обусловленные хранением 1000 изделий равны 1у.е. Определить такой план производства продукции, при котором общая сумма затрат на ее производство и хранение была бы минимальна, а спрос на необходимые изделия был бы удовлетворен современно и полностью.

Вариант 5.На предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использования приведены в таблице В5.

Затраты, связанные с приобретением и установкой нового оборудования составляют 20000 у. е. Составить оптимальный план замены оборудования в течении 9 лет, максимизирующий прибыль за данный период.

Таблица В5.

  Время τ, в течение которого используется оборудование (лет)
Годовой выпуск продукции R(τ) в стоимостном выражении (тыс. у.е.)
Ежегодные затраты Z(τ), связанные с содержанием и ремонтом оборудования (тыс. у.е)

 

Вариант 6.Для увеличения объема выпуска пользующийся повышенным спросом продукции, изготовляемой предприятием, выделены капиталовложения в объеме S=200 тыс.у.е. Использование i-м предприятием xi у.е из указанных средств обеспечивает прирост выпуска продукции, определяемый значением нелинейной функции fi(xi). Составить оптимальный план распределения продукции между четырьмя предприятиями, обеспечивающий максимальное увеличение выпуска продукции. Исходные данные для xi и fi(xi) приведены в таблице В6.

Таблица В6

Объем капиталовложений xi (тыс.у.е.) Прирост выпуска продукции fi(xi) в зависимости от объема капиталовложений (тыс. у.е.)
Предприятие 1 Предприятие 2 Предприятие 3 Предприятие 4

 

Вариант 7.На склад вместимостью W=180 м3 требуется разместить n = 3 различных типов оборудования. Объем данной единицы i-го типа оборудования равен V1=48 м3, V2 -38 м3, V3=32 м3, а цена единицы данного типа оборудования равна C1=870 у.е., С2=700 у.е., С3=350 у.е. Определить, сколько оборудования каждого типа следует поместить на склад, чтобы общая стоимость складируемого оборудования была максимальна.

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

Предприятие стремится найти оптимальный план производства продукции в течении четырех месяцев, потребности в товарах в эти месяцы: 2000, 3000, 4000, 3000 единиц товара. Запасы к началу планируемого периода равны 3000 изделий. В каждом месяце предприятие может производить не более 4000 изделий. Одновременно на складе может хранится не более 3500 изделий. Затраты, связанные с производством 1000, 2000, 3000 и 4000 изделий составляют соответственно 12, 14, 16 и 18 у.е., а затраты обусловленные хранением 1000 изделий равны 2 у.е. Определить такой план производства продукции, при котором общая сумма затрат на ее производство и хранение была бы минимальна, а спрос на необходимые изделия был бы удовлетворен современно и полностью.

Вариант 9.На предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использования приведены в таблице В9.

Затраты, связанные с приобретением и установкой нового оборудования составляют 15000 у. е. Составить оптимальный план замены оборудования в течении 8 лет, максимизирующий прибыль за данный период.

Таблица В9.

  Время τ, в течение которого используется оборудование (лет)
Годовой выпуск продукции R(τ) в стоимостном выражении (тыс. у.е.)
Ежегодные затраты Z(τ), связанные с содержанием и ремонтом оборудования (тыс. у.е)

Вариант 10.На склад вместимостью W=200 м3 требуется разместить n = 3 различных типов оборудования. Объем данной единицы i-го типа оборудования равен V1=36 м3, V2 -26 м3, V3=20 м3, а цена единицы данного типа оборудования равна C1=930 у.е., С2=600 у.е., С3=400 у.е. Определить, сколько оборудования каждого типа следует поместить на склад, чтобы общая стоимость складируемого оборудования была максимальна.


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!