Динамическое и линейное программирование
Категория реферата: Рефераты по математике
Теги реферата: оформление титульный реферата, шпаргалки по гражданскому праву
Добавил(а) на сайт: Пыстогов.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Задача о распределении капитальных вложений – это нелинейная задача
распределения ресурсов между предприятиями одного производственного
объединения или отрасли.
Предположим, что указано [pic] пунктов, где требуется построить или
реконструировать предприятия одной отрасли, для чего выделена определенная
сумма. При этом известен прирост мощности или прибыли для каждого
предприятия, в зависимости от суммы капитальных вложений в это предприятие.
Требуется найти такое распределение капитальных вложений между
предприятиями, которое максимизирует суммарный прирост мощности или прибыли
всей отрасли.
Примем следующие обозначения:
|[pic] |Номер предприятия (j=1,2,…,n) |
|[pic] |Общая сумма капитальных вложений |
|[pic] |Сумма капитальных вложений в j-ое предприятие |
|[pic] |Прирост мощности или прибыли j-го предприятия, если |
| |оно получит xj денежных единиц капитальных вложений |
Тогда, задача состоит в том, чтобы найти такие значения
[pic], [pic], …, [pic], при которых значение суммарного прироста прибыли
или мощности всей отрасли:
[pic] было бы наибольшим, при ограничении общей суммы: [pic], причем будем считать, что все переменные [pic] принимают только целые неотрицательные значения, т.е.:
[pic]=0 или 1, или 2, или 3, …; [pic]
Эту задачу можно решить методом динамического программирования. Для этого
необходимо ввести параметр состояния [pic] и функцию состояния [pic]:
|[pic]|Некоторое количество предприятий, для которых |
| |определяется параметр и функция состояния ([pic]) |
|[pic]|Сумма капитальных вложений, выделяемая нескольким |
| |предприятиям ([pic]) |
|[pic]|Максимальный прирост прибыли или мощности на первых |
| |[pic] предприятиях, если они вместе получат [pic] |
| |капитальных вложений |
Тогда, если из [pic] денежных единиц k-ое предприятие получит [pic]
денежных единиц, то остаток [pic] денежных средств необходимо распределить
между предприятиями от первого до [pic] так, чтобы был получен максимальный
прирост прибыли или мощности [pic]. Следовательно, прирост прибыли или
мощности k предприятий будет равен [pic] и нужно выбрать такое значение
[pic] между 0 и [pic], чтобы увеличение прибыли или мощности k предприятий
было бы максимальным, т.е.:
[pic], где [pic].
Если же k=1, то:
[pic]
Допустим, что производственное объединение состоит из четырех предприятий
(n=4). Общая сумма капитальных вложений равна 700 денежных единиц (b=700), при этом суммы выделяемые предприятиям кратны 100 денежным единицам.
Значения функций [pic] приведены в таблице 3:
|Таблица 3. |
|[pic] |0 |100 |200 |300 |400 |500 |600 |700 |
|[pic] |0 |42 |58 |71 |80 |89 |95 |100 |
|[pic] |0 |30 |49 |63 |68 |69 |65 |60 |
|[pic] |0 |22 |37 |49 |59 |68 |76 |82 |
|[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]
Рекомендуем скачать другие рефераты по теме: конспекты 9 класс, реферат великая.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата