Динамическое и линейное программирование
|[pic] |0 |50 |68 |82 |92 |100 |107 |112 |
Для заполнения таблицы 5 необходимо в таблице 4 сложить значения
функции [pic] со значениями [pic] и на каждой северо-восточной диагонали
выбрать наибольшее число (отмечено звездочкой), указав соответствующие
значение [pic]:
|Таблица 4. |
| |[pic] |0 |100 |200 |300 |400 |500 |600 |700 |
|[pic|[pic] |0 |42 |58 |71 |80 |89 |95 |100 |
|] | | | | | | | | | |
| |[pic] | | | | | | | | |
|0 |0 |0 |42* |58 |71 |80 |89 |95 |100 |
|100 |30 |30 |72* |88 |101 |110 |119 |125 | |
|200 |49 |49 |91* |107* |120 |129 |138 | | |
|300 |63 |63 |105 |121* |134* |143* | | | |
|400 |68 |68 |110 |126 |139 | | | | |
|500 |69 |69 |111 |127 | | | | | |
|600 |65 |65 |107 | | | | | | |
|700 |60 |60 | | | | | | | |
|Таблица 5. |
|[pic] |0 |100 |200 |300 |400 |500 |600 |700 |
|[pic] |0 |42 |72 |91 |107 |121 |134 |143 |
|[pic] |0 |0 |100 |200 |200 |300 |300 |300 |
Для заполнения таблицы 7 необходимо в таблице 6 сложить значения функции
[pic] со значениями [pic] и на каждой северо-восточной диагонали выбрать
наибольшее число (отмечено звездочкой), указав соответствующие значение
[pic]:
| |
|Таблица 6. |
| |[pic] |0 |100 |200 |300 |400 |500 |600 |700 |
|[pic|[pic] |0 |42 |72 |91 |107 |121 |134 |143 |
|] | | | | | | | | | |
| |[pic] | | | | | | | | |
|0 |0 |0 |42* |72* |91 |107 |121 |134 |143 |
|100 |22 |22 |64 |94* |113* |129* |143 |156 | |
|200 |37 |37 |79 |109 |128 |144* |158* | | |
|300 |49 |49 |91 |121 |140 |156 | | | |
|400 |59 |59 |101 |131 |150 | | | | |
|500 |68 |68 |110 |140 | | | | | |
|600 |76 |76 |118 | | | | | | |
|700 |82 |82 | | | | | | | |
|Таблица 7. |
|[pic] |0 |100 |200 |300 |400 |500 |600 |700 |
|[pic] |0 |42 |72 |94 |113 |129 |144 |158 |
|[pic] |0 |0 |0 |100 |100 |100 |200 |200 |
Теперь, в таблице 8, необходимо сложить значения функции [pic] со
значениями [pic], но только для значения [pic], т.е. заполнить только одну
диагональ:
|Таблица 8. |
| |[pic] |0 |100 |200 |300 |400 |500 |600 |700 |
|[pic|[pic] |0 |42 |72 |94 |113 |129 |144 |158 |
|] | | | | | | | | | |
| |[pic] | | | | | | | | |
|0 |0 | | | | | | | |158 |
|100 |50 | | | | | | |194 | |
|200 |68 | | | | | |197* | | |
|300 |82 | | | | |195 | | | |
|400 |92 | | | |186 | | | | |
|500 |100 | | |172 | | | | | |
|600 |107 | |149 | | | | | | |
|700 |112 |112 | | | | | | | |
Наибольшее число этой диагонали показывает максимально возможный
суммарный прирост прибыли всех четырех предприятий данного
производственного объединения, при общей сумме капитальных вложений в
700 денежных единиц, т.е.:
[pic] денежных единиц
причем четвертому предприятию должно быть выделено:
[pic] денежных единиц
Тогда третьему предприятию должно быть выделено (см. табл. 7.):
[pic] денежных единиц
второму предприятию должно быть выделено (см. табл. 5.):
[pic] денежных единиц
на долю первого предприятия остается:
[pic] денежных единиц
Таким образом, наилучшим является следующее распределение капитальных
вложений по предприятиям:
[pic][pic][pic][pic]
которое обеспечивает производственному объединению наибольший возможный
прирост прибыли:
[pic] денежных единиц
6. Динамическая задача управления запасами
Задача управления запасами – это задача о поддержании баланса
производства и сбыта продукции предприятия, минимизирующего расходы
предприятия на производство и хранение продукции.
Предположим, что предприятие, производящее партиями некоторую продукцию,
получило заказы на n месяцев. Размеры заказов значительно меняются от
месяца к месяцу, поэтому иногда лучше выполнять заказы сразу нескольких
месяцев, а затем хранить готовую продукцию, пока она не потребуется, чем
выполнять заказ именно в тот месяц, когда этот заказ должен быть отправлен.
Поэтому необходимо составить план производства на эти n месяцев с учетом
затрат на производство и хранение изделий.
Примем следующие обозначения:
|[pic] |Номер месяца (j=1,2,…,n) |
|[pic] |Число изделий, производимых в j-ом месяце |
|[pic] |Величина запаса к началу j-го месяца |
|[pic] |Число изделий, которые должны быть отгружены в j-ом |
| |месяце |
|[pic] |Затраты на хранение и производство изделий в j-ом |
| |месяце |
Тогда, задача состоит в том, чтобы найти план производства [pic]
компоненты которого удовлетворяют условиям материального баланса:
[pic], где [pic]
и минимизируют суммарные затраты за весь планируемый период:
[pic]
причем по смыслу задачи [pic], [pic], при [pic]
Т.к. объем произведенной продукции [pic] на этапе j может быть настолько
велик, что запас [pic] может удовлетворить спрос всех последующих этапов и
при этом не имеет смысла иметь величину запаса [pic] больше суммарного
спроса на всех последующих этапах, то переменная [pic] должна удовлетворять
ограничениям:
[pic]
Полученную задачу можно решить методом динамического программирования, для
чего необходимо определить параметр состояния [pic] и функцию состояния
[pic]:
|[pic]|Наличный запас продукции в конце k-го месяца ([pic]) |
|[pic]|Минимальные затраты за первые [pic] месяцев: [pic] |
Тогда, минимальные затраты за один первый месяц ([pic]):
[pic]
Следовательно, минимальные затраты при [pic]:
[pic], где [pic]
Если при этом функция затрат на хранение и производство изделий в j-ом
месяце имеет вид:
[pic], где
|[pic], при [pic] и [pic], при [pic] |
|[pic] |Затраты на оформление заказа (переналадку |
| |оборудования) в j-ом месяце |
|[pic] |Затраты на хранение единицы продукции, |
| |переходящей из j-го месяца в месяц j+1 |
|[pic] |Затраты на производство (закупку) [pic] единиц |
| |продукции в j-ом месяце |
то минимальные затраты за один первый месяц ([pic]):
[pic]
если ввести обозначение:
[pic]
то следовательно, минимальные затраты при [pic]:
[pic], где [pic]
Допустим, что предприятие заключило договора на поставку своей продукции
на три месяца. Исходные данные приведены в таблице 9. При этом исходный
запас товара на складе составляет две единицы, т.е [pic].
|Таблица 9. |
|Период k |1 |2 |3 |
|Спрос ([pic]) |3 |2 |3 |
|Затраты на оформление заказа |4 |2 |3 |
|([pic]) | | | |
|Затраты на хранение единицы запаса |1 |1 |1 |
|([pic]) | | | |
Предполагается, что затраты на приобретение продукции составляют 5 руб.
за каждую единицу для первых трех единиц и 7 руб. за каждую дополнительную
единицу, т.е.
[pic]
Положим [pic], тогда:
[pic]
Тогда, т.к. параметр состояния [pic] может принимать значения на отрезке:
[pic]
т.е. [pic], при этом каждому значению параметра состояния отвечает
определенная область изменения переменной [pic]:
[pic]
Однако на первом этапе объем производства не может быть меньше одной
единицы, т.к. спрос [pic], а исходный запас [pic], при этом из балансового
уравнения следует, что объем производства связан с параметром состояния
[pic] соотношением:
[pic]
т.е. каждому значению [pic] отвечает единственное значение [pic], поэтому:
[pic], тогда:
|[pic] |[pic] |[pic] |
|[pic] |[pic] |[pic] |
|[pic] |[pic] |[pic] |
|[pic] |[pic]
| |  скачать работу |
Динамическое и линейное программирование |
