Задача оптимального распределения средств на расширение производства

2. x₁₁+ x₂₁+ x₃₁ <= 32

x₁₂+ x₂₂+ x₃₂ >= 30

x₁₃+ x₂₃+ x₃₃ <= 18

x₁₄+ x₂₄+ x₃₄ = 20

3. x₁₁>= 10; x₁₂ >= 6; x₁₃ >= 4; x₁₄ >= 8;

x₂₁ >= 8; x₂₂ >= 2; x₂₃ >= 5; x₂₄ >= 3;

x₃₁ >= 5; x₃₂ >= 6; x₃₃ >= 7; x₃₄ >= 8;

x₁₁<= 15; x₂₂ <= 14; x₃₃ <= 12.

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

 

Ячейки С3:F5 изначально пустые, после выполнения решения они будут заполнены искомыми значениями.

В ячейку C6 вводим формулу =СУММ(С3:С5) и копируем её на диапазон D6:F6

В ячейку G3 вводим формулу =СУММ(С3:F3) и копируем её на диапазон G4:G5

В ячейки C7:F7 заносим знаки (<=, =, >=) ограничений на объемы финансирования по периодам

В ячейки C8:F8 вносим исходные данные по потребностям в финансах d_j

В ячейку I6 заносим данную величину общего объема финансирования B

В ячейки C12:F17 вносим исходные нижние k_ij и верхние K_ij ограничения на объем финансирования в каждом j-том периоде

В ячейки C21:F23 заносим заданные величины эффекта c_ij от вложения единицы средств в i-тое предприятие в j-том периоде

В ячейку B26 заносим формулу для целевой функции:

=СУММПРОИЗВ(C21:F23;C3:F5)

Для выполнения решения в Excel выполняем команду пункта меню Сервис ® Поиск решения. На экране появится диалоговое окно Поиска решения, в котором:

Назначаем ячейку с целевой функцией.

• Курсор помещаем в поле Установить целевую ячейку.
• Мышью указываем ячейку: B26.
• Выбирают направление целевой функции: Равной: Максимальному значению.

Назначаем ячейки для искомого результата.

• Курсор помещаем в поле Изменяя ячейки.
• Мышью указываем диапазон ячеек: $С$3:$F$5.

Вводим  ограничения и граничные условия.

• Нажимаем экранную кнопку Добавить . На экране появится диалоговое окно Добавление ограничения.
• Вводим ограничение на общую сумму финансирования: G6<=I6. Для этого:

– в поле Ссылка на ячейку: мышью указываем на ячейку G6;

– из раскрывающегося списка знаков выбираем <=;

– в поле Ограничение: мышью указываем на ячейку I6;

– нажимаем экранную кнопку Добавить .

• Аналогично вводим 4 ограничения на потребности в финансировании в каждом периоде С6<=С8, D6>=D8, E6<=E8, F6=F8
• Вводим нижние граничные условия финансирования на искомые переменные (их можно задать построчно):

C3:F3>=C12:F12, C4:F4>=C14:F14, C5:F5>=C16:F16.

• Вводим верхние ограничения на финансирование для тех переменных, для которых они заданы: С3<=С13, D4<=D15, E5<=E17

После ввода  последнего ограничения вместо Добавить нажимаем ОК.

Если при вводе ограничений  возникает необходимость в изменении  или удалении уже внесенных ограничений  или граничных условий, то это  делается с помощью экранных кнопок Изменить , Удалить.

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

В появившемся окне Результаты поиска решения сохраняем найденное решение нажатием кнопки OK .

Ниже показан уже окончательный результат таблицы после решения.

Результат оптимального решения  задачи находится в ячейках С3:F5.

Максимальный эффект в 1136 ден.ед. даст следующее распределение финансов по периодам:

В 1-ом периоде:  Предприятию 1 – 10

Предприятию 2 – 17

Предприятию 3 – 5

Во 2-ом периоде: Предприятию 1 – 58

Предприятию 2 – 14

Предприятию 3 – 58

В 3-ем периоде:  Предприятию 1 – 4

Предприятию 2 – 7

Предприятию 3 – 7

В 4-ом периоде:  Предприятию 1 – 8

Предприятию 2 – 4 

Предприятию 3 – 8

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

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

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

В процессе оптимизации управления методом динамического программирования многошаговый процесс проходится дважды. Первый раз – от конца к началу, в результате чего находятся условно-оптимальные  управления и условно-оптимальное  значение функции цели для каждого  шага, в том числе оптимальное  управление для первого шага и  оптимальное значение функции цели для всего процесса. Второй раз  – от начала к концу, в результате чего находятся уже оптимальные  управления на каждом шаге с точки  зрения всего процесса. Первый этап сложнее и длительнее второго, на втором остается лишь отобрать рекомендации, полученные на первом. Следует отметить, что понятия «конец» и «начало» можно поменять местами и разворачивать процесс оптимизации в другом направлении. С какого конца начать – диктуется удобством выбора этапов и возможных состояний на их начало.

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

В первой части курсовой работы были рассмотрены основные понятия динамического программирования, теоретические основы принципа оптимальности Беллмана, определена рекуррентную природу данного принципа, а также рассмотрели вычислительную схему Беллмана.

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

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

Во второй части была решена задача оптимального распределения  средств на расширение производства, а также решена задача оптимального распределения средств на расширение производства в среде Microsoft Excel.

 

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

1. Беллман, Р. Прикладные задачи динамического программирования / Р. Беллман, С. Дрейфус. – М.,1965. – 458 с.
2. Гринберг, А.С. Экономико-математические методы и модели: курс лекций / А.С.Гринберг, О.Б.Плющ, В.К. Шешолко. – 2-е изд., стер. – Мн.: Акад. Упр. при Президенте Республики Беларусь, 2005. – 222с. – (Система открытого образования).
3. Кожевников, Е. А. Экономико-математические методы и модели: курс лекций для студентов экон. специальностей днев. и заоч. форм обучения / авт. – сост. Е.А.Кожевников. – Гомель: ГГТУ им. П.О.Сухого, 2006. – 178 с.
4. Кузнецов,  А.В. Руководство к решению задач по математическому программированию / А. В. Кузнецов, Н. И.  Холод, Л. С. Костевич. – 2-е изд., перераб. и доп. – Мн. : Выш. Шк., 2001. – 448 с.
5. Таха, Х.А. Введение в исследование операций / Х. А. Таха. – 7-е изд.: Пер. с англ. – М., 2005. – 912 с.