Динамическое и линейное программирование
|
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
| |30 |20 |( |[pic]|[pic]|( |16 |34 |
| |* |14 | |[pic]|[pic]| |14 |0 |
| | |[pic] | |
Получаем четвертое базисное допустимое решение и находим новые
потенциалы, принимая [pic]:
|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] |
|p|p| | | | | | |[pic] |[pic] |
|i|i| | | | | | |[pic] |[pic] |
|c|c| | | | | | |[pic] |[pic] |
|]|]| | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
|50 |16 | | |34 | |[pic]| | |
|70 |14 |11 |45 | | |[pic]| | |
|30 | | |* |2 |28 |[pic]| | |
| |[pic|[pic|[pic|[pic|[pic| | | |
| |] |] |] |] |] | | | |
Т.к. наибольшая положительная оценка всех свободных клеток транспортной
таблицы, соответствует клетке 33, то строим цикл пересчета: 33-23-21-11-14-
34 и производим перераспределение поставок вдоль цикла пресчета:
|[pic] |[pic] |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
| |16| |34|(|[pi| |[pi|(|14| |36|
| | | | | |c] | |c] | | | | |
| |14|45| | |[pi|[pi| | |16|43| |
| | | | | |c] |c] | | | | | |
| | |* |2 | | |[pi|[pi| | |2 |0 |
| | | | | | |c] |c] | | | | |
| | |[pic] | |
Получаем пятое базисное допустимое решение и находим новые потенциалы,
опять принимая [pic]:
|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] |
|p|p| | | | | | |[pic] |[pic] |
|i|i| | | | | | |[pic] |[pic] |
|c|c| | | | | | |[pic] |[pic] |
|]|]| | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
|50 |14 | | |36 | |[pic]| | |
|70 |16 |11 |43 | |* |[pic]| | |
|30 | | |2 | |28 |[pic]| | |
| |[pic|[pic|[pic|[pic|[pic| | | |
| |] |] |] |] |] | | | |
Теперь наибольшая положительная оценка всех свободных клеток транспортной
таблицы, соответствует клетке 25, отсюда строим цикл пересчета: 25-23-33- и
производим перераспределение поставок вдоль этого цикла пресчета:
|[pic] |[pic] |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
| |43 |* |( |[pic]|[pic]|( |15 |28 |
| |2 |28 | |[pic]|[pic]| |30 |0 |
| | |[pic] | |
Получаем пятое базисное допустимое решение и снова находим новые
потенциалы, принимая [pic]:
|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] |
|p|p| | | | | | |[pic] |[pic] |
|i|i| | | | | | |[pic] |[pic] |
|c|c| | | | | | |[pic] |[pic] |
|]|]| | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
|50 |14 | | |36 | |[pic]| | |
|70 |16 |11 |15 | |28 |[pic]| | |
|30 | | |30 | | |[pic]| | |
| |[pic|[pic|[pic|[pic|[pic| | | |
| |] |] |] |] |] | | | |
Находим оценки всех свободных клеток таблицы:
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
| |Все [pic], где [pic]; [pic] |
Т.к. получили таблицу для которой нет ни одной положительной оценки,
следовательно, найдено оптимальное базисное допустимое решение:
[pic]
при котором транспортные расходы по обеспечению продуктом всех четырех
пуктов потребления будут наименьшими. При этом из второго пункта
производства товар будет вывезен не полностью, т.е. там останется остаток
продукта 28 единиц.
5. Распределение капитальных вложений
Задача о распределении капитальных вложений – это нелинейная задача
распределения ресурсов между предприятиями одного производственного
объединения или отрасли.
Предположим, что указано [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 |
| |  скачать работу |
Динамическое и линейное программирование |
