Реферат

Отчет 51 стр., 29 табл., 7 источника, 6 прил.

ПРИКЛАДНЫЕ ЗАДАЧИ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Цель работы: изучить суть метода динамического программирования, его прикладные задачи и их решения

Объект исследования: прикладные задачи метода динамического программирования

Предмет исследования: динамическое программирование

Методы решения поставленных задач: методы динамического, линейного и нелинейного программирования

Результаты работы: изучена суть метода динамического программирования, разобраны его прикладные задачи, приведены примеры и найдены решения

Содержание

Реферат…………………………………………………………...………....….….2

Введение……………………………………………………………………….…..5

1              Аналитическая часть………………………………………….......................…8

1.1 Метод динамического программирования……………………...……...8

1.2 Задача о замене оборудования……………………………...…....…….10

1.3 Распределение инвестиций.……............................................................16

1.4 Метод обратной прогонки……………………….………..………….…20

1.5 Метод прямой прогонки…………………………………………..…....24

1.6 Задача о погрузке…………………………………………………….....26

2  Практическая часть…………………………………………………….….…..34

2.1 Линейная модель оптимального планирования производства ….…..34

2.1.1 Описание задачи планирования……………………………………34

2.1.2 Основные предположения при разработке модели…………....…34

2.1.3 Математическая форма модели…………………………………....35

2.1.4 Числовые значения параметров модели…………………………..35

2.1.5 Описание порядка и результатов поиска оптимального плана.…36

2.1.6 Таблица показателей оптимального плана……………………..…36

2.2 Нелинейная модель оптимального распределения ресурсов……..…39

2.2.1 Описание задачи распределения ресурсов………………………..39

2.2.2 Математическая форма модели…………………………………….40

2.2.3 Числовые значения параметров модели…………………………...41

2.2.4 Результаты исследования модели на чувствительность……….…42

Заключение……………………………………………………………………….44

Список использованных источников …………………………………………..45

Приложение А. Расчет линейной модели…...……………………...………….46

Приложение Б. Отчет по результатам линейной модели..………...………….47

Приложение В. Отчет по устойчивости линейной модели…………….……..48

Приложение Г.  Расчет нелинейной модели……………………………...……49

Приложение Д. Результаты исследования модели на чувствительность……50

Приложение Е Отчет по устойчивости нелинейной модели…………………52

Введение

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

              Целью исследования операций является выявление наилучшего способа действия при решение той или иной задачи. Главная роль при этом отводится математическому моделированию. Для построения математической модели необходимо иметь строгое представление о цели функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений. Цель и ограничения должны быть представлены в виде функций.

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

              Существуют различные методы решения данных моделей, наиболее известными и эффективными из них являются методы линейного

программирования, когда целевая функция и все ограничения линейные. Для

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

динамического программирования, целочисленного программирования, нелинейного программирования, многокритериальной оптимизации и методы сетевых моделей.

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

Итерационная природа алгоритмов обычно приводит к объемным однотипным вычислениям.

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

Динамическое программирование в теории оптимального управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

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

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

Слово «программирование» в словосочетании «динамическое программирование» в действительности к "традиционному" программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

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

Объектом данной работы являются прикладные задачи метода динамического программирования.

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

Для достижения цели исследования необходимо решить следующие задачи:

   рассмотреть метод динамического программирования и область его применения;

   рассмотреть задачи данного метода и их применение;

   найти решение данных задач и описать процесс решения.

1              Аналитическая часть

1.1 Метод динамического программирования

Динамическое программирование — метод оптимизации, приспособленный к операциям, в которых процесс принятия ре­шения может быть разбит на этапы (шаги). Такие операции назы­ваются многошаговыми. Начало развития ДП относится к 50-м годам XX в. Оно связано с именем Р. Беллмана. Если модели линейного программирования можно использо­вать в экономике для принятия крупномасштабных плановых решений в сложных ситуациях, то модели ДП применяются при решении задач значительно меньшего масштаба, например, при разработке правил управления запасами, устанавливающими мо­мент пополнения запасов и размер пополняющего заказа; при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; при распределении дефицитных капитальных вложе­ний между возможными новыми направлениями их использова­ния; при составлении календарных планов текущего и капиталь­ного ремонта сложного оборудования и его замены; при разра­ботке долгосрочных правил замены выбывающих из эксплуатации основных фондов ит. п.

              Динамическое программирование представляет собой математический аппарат, который подходит  к решению некоторого класса задач путем их разложения на части, небольшие менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения. Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию. Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом шаге, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы

В реально функционирующих больших экономических систе­мах еженедельно требуется принимать микроэкономические решения. Модели ДП ценны тем, что позволяют на основе стан­дартного подхода с использованием при минимальном вмеша­тельстве человека принимать такие решения. И если каждое взя­тое в отдельности такое решение малосущественно, то в совокуп­ности эти решения могут оказать большое влияние на прибыль. Происхождение названия динамическое программирование, вероятно, связано с использованием методов ДП в задачах принятия решений через фиксированные промежутки времени (например, в задачах управления запасами). Однако методы ДП успешно применяются также для решения задач, в которых фактор времени не учитывается. По этой причине более удачным представляется термин многоэтапное программирование, отражающий пошаговый характер процесса решения задачи. Фундаментальным принципом, положенным в основу теории ДП, является принцип оптимальности. По существу, он определяет порядок поэтапного решения допускающей декомпозицию задачи (это более приемлемый путь, чем непосредственное решение задачи в исходной постановке) с помощью рекуррентных вычислительных процедур.

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

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

«Каково бы ни было состояние системы S перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным».

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

              1.2 Задача о замене оборудования

Замена оборудования — важная экономическая проблема. Задача состоит в определении оптимальных сроков замены старого оборудования (станков, производственных зданий и т. п.). Старение оборудования включает его физический и моральный износ, в результате чего растут производственные затраты, затраты на ре­монт и обслуживание, снижаются производительность труда, лик­видная стоимость. Критерием оптимальности являются, как пра­вило, либо прибыль от эксплуатации оборудования (задача мак­симизации), либо суммарные затраты на эксплуатацию в течение планируемого периода (задача минимизации).

При построении модели задачи принято считать, что решение о замене выносится в начале каждого промежутка эксплуатации (например, в начале года) и что в принципе оборудование можно использовать неограниченно долго.

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

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

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

              Обозначим через r(t) и c(t) прибыль от эксплуатации t-летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s(t) – стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна l.

              Элементы модели динамического программирования таковы:

1.   Этап і представляется порядковым номером года і, і=1,2,...n.

2.   Вариантами решения на і-м этапе (т.е. для і-ого года) являются

альтернативы: продолжить эксплуатацию или заменить механизм в начале і-ого года.

3.   Состоянием на і-м этапе является срок эксплуатации t (возраст) механизма к началу і-ого года.

              Пусть fi(t)-максимальная прибыль, получаемая за годы от і до n при

условии, что в начале і-ого года имеется механизм t-летнего возраста.

Рекуррентное уравнение имеет следующий вид:

(1)-если эксплуатировать механизм,

(2)-если заменить механизм.

Пример:

Найти оптимальную стратегию эксплуатации оборудования на период продолжительностью 6 лет, если годовой доход r(t) и остаточная стоимость S(t) в зависимости от возраста заданы в таблице, стоимость нового оборудования равна P = 10, а возраст оборудования к началу эксплуатационного периода составлял 1 год. Значения S(t) и r(t) даны в таблице 1.1

Таблица 1.1- Значения S(t) и r(t)

Решение:

Первый этап: условная оптимизация

(k = 6,5,4,3,2,1).
 Переменной управления на k-м шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (С) или заменить (З) оборудование в начале k-го года.

 1-й шаг: k = 6. Для 1-го шага возможные состояния системы t = 1,2,3,4,5,6, а функциональные уравнения имеют вид:
 F6(t) = max(r(t), (C); S(t) - P + r(0), (З ) )
  F6(1) = max(8 ; 7 - 10 + 8) = 8 (C)
  F6(2) = max(7 ; 6 - 10 + 8) = 7 (C)
  F6(3) = max(7 ; 5 - 10 + 8) = 7 (C)
  F6(4) = max(6 ; 4 - 10 + 8) = 6 (C)
  F6(5) = max(6 ; 3 - 10 + 8) = 6 (C)
  F6(6) = max(5 ; 2 - 10 + 8) = 5 (C)

  2-й шаг : k = 5. Для 2-го шага возможные состояния системы t = 1,2,3,4,5, а функциональные уравнения имеют вид:
 F5(t) = max(r(t) + F6(t+1) ; S(t) - P + r(0) + F6(1))
  F5(1) = max(8 + 7 ; 7 - 10 + 8 + 8) = 15 (C)
  F5(2) = max(7 + 7 ; 6 - 10 + 8 + 8) = 14 (C)
  F5(3) = max(7 + 6 ; 5 - 10 + 8 + 8) = 13 (C)
  F5(4) = max(6 + 6 ; 4 - 10 + 8 + 8) = 12 (C)
  F5(5) = max(6 + 5 ; 3 - 10 + 8 + 8) = 11 (C)

  3-й шаг : k = 4. Для 3-го шага возможные состояния системы t = 1,2,3,4, а функциональные уравнения имеют вид:
 F4(t) = max(r(t) + F5(t+1) ; S(t) - P + r(0) + F5(1))
  F4(1) = max(8 + 14 ; 7 - 10 + 8 + 15) = 22 (C)
  F4(2) = max(7 + 13 ; 6 - 10 + 8 + 15) = 20 (C)
  F4(3) = max(7 + 12 ; 5 - 10 + 8 + 15) = 19 (C)
  F4(4) = max(6 + 11 ; 4 - 10 + 8 + 15) = 17 (C/ З )

  4-й шаг : k = 3. Для 4-го шага возможные состояния системы t = 1,2,3, а функциональные уравнения имеют вид:
 F3(t) = max(r(t) + F4(t+1) ; S(t) - P + r(0) + F4(1))
  F3(1) = max(8 + 20 ; 7 - 10 + 8 + 22) = 28 (C)
  F3(2) = max(7 + 19 ; 6 - 10 + 8 + 22) = 26 (C/ З )
  F3(3) = max(7 + 17 ; 5 - 10 + 8 + 22) = 25 ( З )

  5-й шаг : k = 2. Для 5-го шага возможные состояния системы t = 1,2, а функциональные уравнения имеют вид:
 F2(t) = max(r(t) + F3(t+1) ; S(t) - P + r(0) + F3(1))
  F2(1) = max(8 + 26 ; 7 - 10 + 8 + 28) = 34 (C)
  F2(2) = max(7 + 25 ; 6 - 10 + 8 + 28) = 32 (C/ З )

  6-й шаг : k = 1. Для 6-го шага возможные состояния системы t = 1, а функциональные уравнения имеют вид:
 F1(t) = max(r(t) + F2(t+1) ; S(t) - P + r(0) + F2(1))
 F1(1) = max(8 + 32 ; 7 - 10 + 8 + 34) = 40 (C)

 Результаты вычислений по уравнениям Беллмана Fk(t) приведены в таблице 1.2, в которой k - год эксплуатации, а t - возраст оборудования.

Таблица 1.2 – Результаты k и t

 В таблице выделено значение функции, соответствующее состоянию (З) - замена оборудования.

Второй этап: безусловная оптимизация

(k = 6,5,4,3,2,1)
 Безусловная оптимизация начинается с шага при k = 1. Максимальной возможный доход от эксплуатации оборудования за годы с 1-го по 7-й составляет F1(1) = 40. Этот оптимальный выигрыш достигается, если на первом году не производить замены оборудования.
 К началу 2-го года возраст оборудования увеличится на единицу и составит: t2 = t1 + 1 = 1 + 1 = 2.
 Безусловное оптимальное управление при k = 2, x2(2) = (C/З), т.е. для получения максимума прибыли за оставшиеся годы необходимо в этом году провести замену оборудования.
 

 К началу 3-го года возраст оборудования увеличится на единицу и составит: t3 = t2 + 1 = 0 + 1 = 1.
 Оптимальное управление при k = 3, x3(1) = (C), т.е. максимум дохода за годы с 3-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
 К началу 4-го года возраст оборудования увеличится на единицу и составит: t4 = t3 + 1 = 1 + 1 = 2.
 Оптимальное управление при k = 4, x4(2) = (C), т.е. максимум дохода за годы с 4-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
 К началу 5-го года возраст оборудования увеличится на единицу и составит: t5 = t4 + 1 = 2 + 1 = 3.
 Оптимальное управление при k = 5, x5(3) = (C), т.е. максимум дохода за годы с 5-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
 К началу 6-го года возраст оборудования увеличится на единицу и составит: t6 = t5 + 1 = 3 + 1 = 4.
 Оптимальное управление при k = 6, x6(4) = (C), т.е. максимум дохода за годы с 6-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.

Таким образом, за 6 лет эксплуатации оборудования замену надо произвести в начале 2-го года эксплуатации.

1.3              Распределение инвестиций

Планируется распределение начальной суммы средств e0 = 40 млн руб., причем средства выделяются кратно 10 млн руб. между тремя предприятиями П1, П2, П3. Выделение предприятию Пk средств uk приносит доход fk(uk), который задан в таблице 1.3. Определить, какое количество средств нужно выделить каждому предприятию, чтобы обеспечить максимальный суммарный доход.

Таблица 1.3 – Значения дохода предприятий

Решение.

Первый этап: условная оптимизация.

1-ый шаг. k = 3. Проведем расчеты и занесем результаты в таблицу 1.4.

Таблица 1.4 – Результаты при k=3

e2 – значение кратных распределений

u3 - значения выделенных предприятию средства

e3 = e2 - u3 – получаем вычитанием значений из первого столбца значений из второго столбца

f3(u3)- заполняется значениями из таблицы 1.3

F*3(e3)- максимальное значение для фиксированного начального состояния

u3(e3)- записывается управление из столбца e2, на котором достигается максимум в F*3(e3).

2-ый шаг. k = 2. Аналогично построим таблицу 1.5 как в 1-ом шаге.

F*2(e1)- значения берем из столбца F*3(e3) таблицы 1.3

F1(u2,e1)- значения суммы столбцов f2(u2) и F*2(e1)

Таблица 1.5 – Результаты при k=2

3-ый шаг. k = 1. Построим таблицу 1.6 аналогично 2-му шагу

Таблица 1.6- Результаты при k=1

Второй этап: безусловная оптимизация.

Из таблица 1.6 имеем F*1(e0 = 40) = 12. То есть максимальный доход всей системы при количестве средств e0 = 40 равен 12

Из этой же таблицы получаем, что 1-му предприятию следует выделить u1(e1)(e0 = 40) = 20

При этом остаток средств составит:

e1 = e0 - u1

e1 = 40 - 20 = 20

Из таблица 1.5- имеем F*2(e1 = 20) = 7. То есть максимальный доход всей системы при количестве средств e1 = 20 равен 7

Из этой же таблицы получаем, что 2-му предприятию следует выделить u2(e2) (e2 = 20) = 10

При этом остаток средств составит:

e2 = e1 - u2

e3 = 20 - 10 = 10

Последнему предприятию достается 10.

Итак, максимальный доход в количестве 40 будет получен, если:
1-му предприятию выделить 20
2-му предприятию выделить 10
3-му предприятию выделить 10
Что обеспечит максимальный доход, равный 12

1.4 Метод обратной прогонки

Между тремя предприятиями распределить 120 единиц ограниченного ресурса. Значения получаемой предприятиями прибыли в зависимости от выделенной суммы Х приведены в таблице 1.7. Найти оптимальный план распределения методом обратной прогонки.

Таблица 1.7 – Значения получаемой прибыли

Первый этап: условная оптимизация.

1-й шаг: k = 3. Предположим, что все средства в количестве x3 = 120 отданы 3-му предприятию. В этом случае максимальный доход, как это видно из таблицы 1.9, составит 58, следовательно: F3(c3) = g3(x3)

Таблица 1.8

Таблица 1.9

2-й шаг: k = 2. Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F2(c2) = max [ g2(x2) + F3(c2 - x2)]
 

Таблица 1.10

Заполняем таблицу 1.11. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x2.

Таблица 1.11

3-й шаг: k = 1. Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F1(c1) = max [ g1(x1) + F2(c1 - x1)]

Таблица 1.12

Заполняем таблицу 1.13. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x3.

Таблица 1.13

Второй этап: безусловная оптимизация.

1-й шаг: k = 1.
По данным таблицы 1.13 максимальный доход при распределении 120 между предприятиями составляет c1 = 120, F1(120) = 76. При этом 1-му предприятию нужно выделить x1 = 40.
 

2-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c2 = c1 - x1 = 120 - 40 = 80.
По данным таблицы 1.11 максимальный доход при распределении 80 между предприятиями составляет c2 = 80, F2(80) = 51. При этом 2-му предприятию нужно выделить x2 = 40.

3-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c3 = c2 - x2 = 80 - 40 = 40.
По данным таблицы 1.9 максимальный доход при распределении 40 между предприятиями составляет с1=40, F3(40)=27. При этом 3-му предприятию нужно выделить x3 = 40.
Таким образом, оптимальный план инвестирования предприятия:
x 1 = 40
x 2 = 40
x 3 = 40
который обеспечит максимальный доход, равный:
F(120) = g1(40) + g2(40) + g3(40) = 25 + 24 + 27  = 76.

1.5 Метод прямой прогонки

              Решим задачу из 1.4 методом прямой прогонки. Исходные данные возьмем из таблицы 1.7

  Первый этап. Условная оптимизация.

 1-й шаг: k = 1. Предположим, что все средства в количестве x1 = 120 отданы первому предприятию.
 

 Таблица 1.14

Заполняем таблицу 1.15. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x1.

Таблица 1.15

 2-й шаг: k = 2.

 Таблица 1.16

Заполняем таблицу 1.17. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x 2.

Таблица 1.17

 Второй этап: безусловная оптимизация.

 1-й шаг: k = 3.  По данным таблицы 1.17 максимальный доход при распределении 120 между предприятиями составляет c1 = 120, F3(120) = 76. При этом 3-му предприятию нужно выделить x3 = 40.
 2-й шаг: k = 2.  Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
 c2 = c1 - x1 = 120 - 40 = 80.
 По данным таблицы 1.15 максимальный доход при распределении 80 между предприятиями составляет c2 = 80, F2(80) = 49. При этом 2-му предприятию нужно выделить x2 = 40.  На долю первого предприятия остается 40.
 Таким образом, оптимальный план инвестирования предприятия:
 x1 = 40;
 x2 = 40;
 x3 = 40;
 который обеспечит максимальный доход, равный:
  F(120) = g1(40) + g2(40) + g3(40) = 25 + 24 + 27  = 76.

1.6 Задача о загрузке

              Задача о загрузке – это задача о рациональной загрузке судна (самолета, автомашины и т.п.), которое имеет ограничения по объему или грузоподъемности.

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

Рекуррентное уравнение процедуры обратной прогонки выводится для общей задачи загрузки судна грузоподъемностью W предметов (грузов) n наименований. Пусть mi -количество предметов і-го наименования, подлежащих загрузке, ri -прибыль, которую приносит один загруженный предмет і-го наименования, wi -вес одного предмета і-го наименования.

Общая задача имеет вид следующей целочисленной задачи линейного программирования.

Максимизировать z=r1m1+r2m2+.+rnmn.

при условии, что

w1m1+w2m2+.+wnmn W,

m1,m2,.,mn 0 и целые.

              Три элемента модели динамического программирования определяются следующим образом:

1.     Этап і ставится в соответствии предмету і-го наименования, і=1,2,.n.

2.     Варианты решения на этапе і описываются количеством mi

предметов і-го наименования, подлежащих загрузке. Соответствующая прибыль равна rimi. Значение mi заключено в пределах от 0 до [W/wi], где [W/wi] – целая часть числа W/wi.

3.     Состояние xi на этапе і выражает суммарный вес

предметов, решения о погрузке которых приняты на этапах і,і+1,...n. Это

определение отражает тот факт, что ограничения по весу является единственным, которое связывает n этапов вместе.

Пусть fi(xi)-максимальная суммарная прибыль от этапов

і,і+1,...,n при заданном состоянии xi. Проще всего рекуррентное

уравнение определяется с помощью следующей двухшаговой процедуры.

              Шаг 1. Выразим fi(xi) как функцию fi+1(xi+1) в виде

где fn+1(xn+1)=0.

              Шаг 2. Выразим xi+1 как функцию xi для гарантии

того, что левая часть последнего уравнения является функцией лишь xi.

По определению xi-xi+1 представляет собой

вес, загруженный на этапе і, т.е. xi-xi+1=wimi или xi+1=xi-wimi. Следовательно, рекуррентное уравнение приобретает следующий вид:

Пример:

Самолет загружается предметами n различных типов. каждый предмет типа i имеет вес pi и стоимость ci (i=1,...,n). Максимальная грузоподъемность самолета равна W. Требуется определить максимальную стоимость груза, вес которого не должен превышать максимальной грузоподъемности самолета.

Решение:

Обозначим количество предметов типа i через xi.

при ограничениях

  .

W=83.

Найти x1,  x2, x3 , x4.

 Так как для нахождения функции fn(W) необходимо знать fn-1(W-pnxn), то при решении потребуются значения функции f(W) при значениях 0≤W≤83.

Этап 1. Пусть самолет загружают только предметами 1-го типа. Их можно загрузить в количестве [W/p1] поэтому x1=0,1,2,3.

Так как вес груза p1=24 ед., то при 0≤W≤23 в самолет нельзя погрузить ни одного предмета 1-го типа.

При 1 - 24≤W≤47 можно загрузить один предмет.

1 - 48≤W≤71 можно загрузить два предмета.

1 - 72≤W≤83 можно загрузить три предмета.

Найденные значения W, f1(W), и x1 запишем в виде таблицы 1.18

Таблица 1.18

.

x2=0,1,2,3

Этап 2. Пусть самолет загружают предметами 1-го и 2-го типов. Так как p2=22 ед., то[W/p2]=[83/22].  x2=0,1,2,3. Величину грузоподъемности разбиваем на интервалы, учитывая значения p1 и p2.

0≤W≤23 - в самолет нельзя предметы ни 1-го ни 2-го типов. На оставшихся интервалах количество предметов находят с помощью таблицы 1.19 и формулы функционального уравнения (3):

.

Таблица 1.19

1)               46≤W≤47,

x2=2.

2)               68≤W≤69,

x2=2.

3)               70≤W≤71,

x2=1.

Этап 3.

              Таблица 1.20

 x2=2, x3=1, x1=0.

Этап 4.

              Таблица 1.21

x4=0, x3=1, x2=0, x1=2.

В результате, максимальную прибыль мы получим если возьмем 2 предмета первого типа и один предмет третьего типа. И максимальная прибыль будет равна 242

2  Практическая часть

2.1  Линейная модель оптимального планирования производства

2.1.1 Описание задачи планирования

Рассмотрим следующую экономическую ситуацию. Предприятие выпускает продукцию n видов, потребляя ресурсы m видов. Предполагаются известными: матрица А норм потребления ресурсов (матрица имеет m строк и n столбцов); вектор В принадлежит R^m лимитов ресурсов (вектор имеет m строк); вектор Р коэффициентов дохода от реализации продукции рассматриваемым предприятием (вектор имеет n столбцов). Требуется найти сбалансированный по ресурсам план выпуска продукции, дающий максимальный доход предприятию.

2.1.2 Основные предположения при разработке модели

В данном случае предполагаются выполненными условия "линейной" экономики: затраты ресурсов и прибыль предприятия при выпуске продукции пропорционально возрастают по каждому изделию в отдельности; нормы расходов ресурсов и показатель прибыли по каждому изделию не зависят от масштабов производства в целом. Кроме того, предполагается, что руководство предприятия при планировании номенклатуры выпускаемых изделий и их объемов руководствуется исключительно интересами получения максимальной прибыли. Считаем, что спрос на изделия неограничен, а "портфель заказов" формируется на основе оптимального плана.

2.1.3 Математическая форма модели

Перейдем к формированию условий модели планирования. Пусть неотрицательный вектор x принадлежит R в степени n - план предприятия, тогда ограничение по ресурсам записывается в виде, представленный в формуле 2.4:

А*х<=В                                                                                                                                            (2.4)

Условие неотрицательности компонентов плана имеет вид в формуле 2.5:

x>=0                                                                                                                                                          (2.5)

Записываем    целевую     функцию    задачи     планирования.    Условие максимизации прибыли примет вид в формуле 2.6:

Z = Р*х -> (стремится к) max                                                                                                  (2.6)

Задачи с условиями типа (2.4) - (2.6) называются задачами производственного планирования. В общем случае они записываются c помощью задач выпуклого программирования. В данном случае (2.4) - (2.6) является задачей линейного программирования.

2.1.4  Числовые значения параметров модели

В данном варианте задачи планирования выбраны: число n равное 8 и число m равное 10. Данные вектора коэффициентов целевой функции, матрицы ограничений и значений вектора лимитированных ресурсов приведены в таблицах 2.1 - 2.3 соответственно:

Таблица 2.1 - Задание вектора коэффициентов целевой функции

Таблица 2.2 - Задание матрицы норм потребления ресурсов

Таблица 2.3 - Задание вектора лимита ресурсов

2.1.5  Описание порядка и результатов поиска оптимального плана

После ввода данных, определим вектор x (плана предприятия), т.к. мы еще не знаем оптимального вектора выпуска, заполним его, к примеру, цифрами 10 (т.е. первоначально планируется выпускать по 10 единиц каждого товара), далее следует найти вектор R=A11·x1+A12·x1+..+Anm·xn, для того чтобы в дальнейшем использовать его при вводе ограничений по ресурсам. Определяем прибыль при первоначальном плане по формуле Z= P1·x1+P2·x2+..+Pn·xn. Затем в функции «Поиск решения» указываем какое значение мы хотим максимизировать (в данном случае это значение прибыли Z), и вводим ограничения: 1) R1<В1, R2<B2,…,Rm<Bm (ограничения по ресурсам) 2) вектор x > 0 (неотрицательность ресурсов). Вычисляем оптимальный план выпуска, дающий максимальную прибыль.

Вектор x в данном примере имеет следующие значения, приведенные в таблице 2.4:

Таблица 2.4 – Значения вектора х

Максимальная прибыль при оптимальном плане выпуска равна 1440,39 ед.

2.1.6 Таблица показателей оптимального плана. Результаты исследования модели на чувствительность

Для проведения исследования модели на чувствительность необходимо после запуска поиска решения на выполнение в окне "Результаты поиска решения" выделить два типа отчетов: "Результаты" и "Устойчивость".

Отчет по результатам состоит из трех таблиц:

1) таблицы А.1 – А.3 содержит информацию о целевой функции;

2) приложение Б содержит информацию о значениях переменных, полученных в результате решения задачи;

3) приложение В показывает результаты оптимального решения для ограничений и для граничных условий (см. Приложение A-В).

Если ресурс используется полностью (то есть ресурс дефицитный), то в графе "Статус" соответствующее ограничение указывается как "связанное"; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается "не связан". В графе "Значение" приведены величины использованного ресурса.

Для граничных условий в графе "Разница" показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием. Так, если на ресурс наложено ограничение типа ≥, то в графе "Разница" дается количество ресурса, на которое была превышена минимально необходимая норма. Если на ресурс наложено ограничение типа ≤, то в графе "Разница" дается количество ресурса, которое не используется при реализации оптимального решения.

Таким образом, на таблице А.1 отчета по результатам видим, что мы увеличили доход предприятия с 0 до 1440,39 ед. На таблице А.2 показаны, как изменились исходные значения плана предприятия (предполагалось выпускать 10 ед. каждой продукции). Анализируя таблицу 3, можно сказать, что большинство ресурсов дефицитные («связанные»), используются в полном объеме. То есть мы нашли сбалансированный по ресурсам план выпуска продукции, дающий максимальный доход предприятию.

2.2  Нелинейная модель оптимального распределения ресурсов

2.2.1  Описание задачи распределения ресурсов

Задача распределения ресурсов рассматривается для n предприятий. Центр осуществляет управление этими промышленными предприятиями, выпускающими однотипную продукцию. Обозначим через Рi объем продукции, выпускаемой предприятием i, i=1,. ..,n. Результат функционирования центра определяется результатами функционирования отдельных производителей, т.к. центр сам не производит продукции.

Считаем, что величина продукции, произведенной i-ым предприятием, определяется объемом фондов Fi и количеством рабочей силы Li, согласие производственной функции Кобба – Дугласа, представленной в формуле 2.7:

Pi=di*(Fi)^ki*(Li)^(1-ki),                                                                                                  (2.7)

где i=1,..,n

В выражении (4) di и ki характеристики предприятия i (i=1,.. .,n ), удовлетворяющие условиям: di > 0 и О ki 1,i=1,...,n..

Пусть wi - ставка заработной платы на предприятии i. Тогда доля дохода предприятия i в общей сумме прибыли объединения определится по формуле 2.8:

Gi =ci*Pi-wi*Li , i=1,. . .,n                                                                        (2.8)

Если  величина  фондов   предприятия фиксирована, то объем продукции Pi однозначно определяется количеством рабочей силы Li.

Центр влияет на работу предприятий распределением дополнительного ресурса, который полностью находиться в его распоряжении. Если предприятие i получит дополнительный ресурс в количестве Vi, то оно сможет произвести продукцию в объеме, найденном по формуле 2.9:

Pi=di*(Fi+Vi)^ki*(Li)^(1-ki),i=i,...,n                                                                        (2.9)

Задача центра состоит в распределении имеющегося в его распоряжении ресурса В, т. е. в определении оптимальных значений величин Vi, i=i,...,n, обеспечивающих максимум суммарной прибыли объединения в целом.

2.2.2  Математическая форма модели

В данной задаче считаем, что используется схема централизованного планирования, в рамках которой центр рассчитывает оптимальное распределение ресурсов, оптимальные величины рабочей силы при заданных параметрах модели. Конкретно центр изменяет Vi и Li, i = i,...,n, из условий, представленных в формулах 2.9.1, 2.9.2, 2.9.3:

z = max (G1 + G2 + ,..., + Gn)              (2.9.1)

V1+V2+,..,.+Vп = B                                                                (2.9.2)

Vi, Vimin, Li,   i=1,...,n                                                 (2.9.3)

2.2.3 Числовые значения параметров модели

В данном варианте задачи оптимального распределения ресурсов выбрано число n (число предприятий) равное 10 и объем распределяемого ресурса 100 ед. Коэффициенты целевой функции и ограничения приведены в таблицах 2.5-2.7.

Таблица 2.5 - Параметры ci и wi целевой функции (6) ( i - индекс предприятия)

Таблица 2.6 - Параметры di и ki производственной функции (5)

Таблица 2.7 - Параметры Fi и Vi min целевой функции (6) (i - индекс предприятия)

После ввода данных, определим величины Vi и Li (значения объема  ресурса и рабочей силы), т.к. мы еще не знаем оптимального объема  ресурса и рабочей силы заполним их, к примеру, цифрами 10, далее следует найти величины Pi и Gi (значений объемов выпускаемой продукции и доли дохода) по формулам 2.9.4 и 2.9.5:

Pi = di ·(Fi)ki · (Li)1-ki,       где i=1,2,..,10                                  (2.9.4)

Gi  = ci·Pi - wi·Li ,              где i=1,2,...,10                                  (2.9.5)

А также найдем объем оптимальных значений дополнительного ресурса, просуммировав все значения величины Vi. После этого нужно посчитать прибыль, которая получается при первоначальном плане, просуммировав все значения Gi. Затем в функции «Поиск решения», укажем значение, которое мы хотим максимизировать (в данном случае это значение суммы всех величин Gi), и введем ограничения:

1) Vi=>Vi min

2) величина Li=>0

3) Величина оптимального объема дополнительного ресурса не должна превышать 100 ед.

Посчитаем оптимальные значения объема  ресурса и рабочей силы, дающие максимальную прибыль. В таблице 2.8 приведены оптимальные значения объема  ресурса и рабочей силы, которые получились после решения задачи:

Таблица 2.8 – Оптимальные значения объема ресурса и рабочей силы

Оптимальный объем дополнительного ресурса равен 83,23 ед. Суммарная прибыль предприятий равна –  4026,30 ед.

2.2.4  Результаты исследования модели на чувствительность

Результаты исследования модели на чувствительность приведены в Приложении Г - Е.

В отчете по результатам мы видим, что ресурс оказался недефицитным (неполное использование ресурса).

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

Для улучшения плановых показателей необходимо неиспользуемый ресурс в количестве 17.77 распределить по другим предприятиям. Таким образом, можно увеличить суммарную прибыль предприятий.

Заключение

Динамическое программирование- мощнейший инструмент для прогнозировании производства, и приятия решений связанных с выбором оптимальной стратегии производства, направленной на получение максимальной прибыли при минимальных затратах. Данный метод и его прикладные задачи особенно востребованы в текущее время, т.к. позволяют найти оптимальные решения в любой ситуации.

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

В процессе проектирования данной курсовой работы, поставленные цели были успешно достигнуты.

Задания были решены в Microsoft Excel с помощью Сервис\Поиск_решения. Подробное решение задач можно увидеть в Приложении.

Список использованных источников

1.                  Беллман Р., Дрейфус С., -Прикладные задачи метода динамического программирования.- М., 1965.- 460с.

2.                  Грешилов А.А. Прикладные задачи метода динамического программирования.-М.: Изд-во МГТУ, 1990.-180с.

3.                  Кремер Н.Ш., Питько Б.А. Исследование операций в экономике- М.: ЮНИТИ, 2003.-407с.

4.                  АстафуровВ.Г.,  Колодникова Н. - Компьютерное учебное пособие, раздел “Анализ на чувствительность с помощью двойственной задачи”,  Томск-2002.

5.                  Берюхова Т.Н. Банк производственных задач в расчетах на ЭВМ: учебное пособие. – М.: ТюмИИ, 1992. – 124с.

6.                  Кузнецов А.В. Математическое программирование: учебное пособие для вузов. – М.: Высшая школа, 1976. – 352с.

7.                  Орлов А.И. Эконометрика. Учебник. - М.: Экзамен, 2002. – 576 с.

Приложение А

Расчет линейной модели

Таблица 1 - Задание вектора коэффициентов целевой функции

Таблица 2 - Задание матрицы норм потребления ресурсов

Таблица 3 - Задание вектора лимита ресурсов

Приложение Б

Отчет по результатам линейной модели