Автор работы: Пользователь скрыл имя, 01 Октября 2013 в 22:41, курсовая работа
Целью исследования операций является выявление наилучшего способа
действия при решение той или иной задачи. Главная роль при этом отводится
математическому моделированию. Для построения математической модели
необходимо иметь строгое представление о цели функционирования исследуемой
системы и располагать информацией об ограничениях, которые определяют
область допустимых значений. Цель и ограничения должны быть представлены в
виде функций.
В моделях исследования операций переменные, от которых зависят
ограничения и целевая функция, могут быть дискретными (чаще всего
целочисленными) и континуальными (непрерывными). В свою очередь,
ограничения и целевая функция делятся на линейные и нелинейные
|ВВЕДЕНИЕ…………………………………………………………………… |6 |
|1 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ…………………………. |8 |
|Задача динамического программирования……………………….. |8 |
|Примеры задач динамического программирования……………... |12 |
|Общая структура динамического программирования…………... |16 |
|2 ЗАДАЧА О ЗАГРУЗКЕ…………………………………………………… |18 |
|2.1 Общие сведения………………………………………………………… |18 |
|2.2 Рекуррентные соотношения для процедур прямой и обратной | |
|прогонки……………………………………………………………………… |19 |
|2.3 Решение задачи о загрузке……………………………………………. |22 |
|2.4 Анализ чувствительности решения………………………………….. |25 |
|СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ………………………. |27 |
Контрольная работа содержит вопросы по N различным темам. Каждый вопрос
типа i имеет вес Vi(i=1,2,…N), а также время, отводимое на ответ Wi.
Максимально время,
которое может затратить
Требуется определить максимальное количество баллов (вес), которое может
набрать студент за отведенное время W=30. Данные приведены в таблице:
|I |Wi |Vi |
|1 [pic] 5 |2 |2 |
|2 [pic] 6 |3 |3 |
|3 [pic] 4 |1 |2 |
|4 [pic] 3 |4 |4 |
|5 |7 |6 |
|6 [pic] 6 |5 |5 |
|7 [pic] 5 |3 |4 |
|8 [pic] 7 |2 |2 |
Решить задачу, приведя ее к рекуррентным соотношениям.
Сначала рассмотрим задачу в общей постановке. Если обозначить
количество вопросов типа і через ki, то задача принимает следующий вид:
при ограничениях
ki-неотрицательные числа.
Если отбросить требования целочисленности ki, то решение задачи
нетрудно найти с помощью симплекс-метода (см. Приложение В). В самом деле,
так как остается лишь одно ограничение, базисной будет только одна
переменная, и задача сводится к выбору типа і, для которого величина viW/wi
принимает максимальное значение. Исходная задача не является задачей
линейного программирования, и для ее решения необходимо использовать метод
динамического программирования. Следует отметить, что рассматриваемая
задача может быть также решена с помощью методов целочисленного
программирования.
Каждый из трех основных элементов модели ДП определяется следующим
образом.
1. Этап j ставится в соответствии типу j, j=1,2,…,N.
2. Состояние yj на этапе j выражает суммарный вес вопросов, количество
ответов на которые приняты на этапах j,j+1,…,N; при этом y1=W и
yj=0,1,…,W при j=2,3,…,N.
3. Варианты решения kj на этапе j описываются количеством вопросов
типа j. Значение kj заключено в пределах от нуля до [W/wj], где
[W/wj]-целая часть числа (W/wj).
Пусть fi(yi)-максимальный суммарный вес вопросов, ответы на которые
приняты на этапах j,j+1,…,N при заданном состоянии yj.
Рекуррентное соотношение (для процедуры обратной прогонки) имеет
следующий вид:
Заметим, что максимальное допустимое значение kj ограничено величиной
[yj/wj]. Это позволяет автоматически исключать все не являющиеся
допустимыми варианты при заданном значении переменной состояния yj.
Решение исходной задачи (см. приложении А):
Этап 8.
Этап 7.
Этап 6.
Этап 5.
Этап 4.
Этап 3.
Этап 2.
Этап 1.
Оптимальное решение определяется теперь следующим образом. Из условия
W=30 следует, что первый этап решения задачи при y1=30 дает оптимальное
решение k1=0, которое означает, что на 0 (нуль) вопросов 1-го типа будут
даны ответы. Далее находим:
|y1=30 |k1=0 |
|y2=y1-2*k1=30 |k2=0 |
|y3=y2-4*k2=30 |k3=4 |
|y4=y3-k3=26 |k4=1 |
|y5=y4-4*k4=22 |k5=0 |
|y6=y5-7*k5=22 |k6=0 |
|y7=y6-5*k6=22 |k7=5 |
|y8=y7-3*k7=7 |k8=7 |
Соответственно оптимальным решением задачи является (0,0,4,1,0,0,5,7),
соответственно максимально количество баллов, которое студент может набрать
за отведенное время равно 46.
2.4
Анализ чувствительности
В таблице для первого этапа нам, по существу, необходимо получить
оптимальное решение лишь для y1=30, так как это последний этап, подлежащий
рассмотрению (см. Приложение А). Однако в таблицу включены вычисления для
y1=0,1,…,30, которые
позволяют провести анализ
Например, что произойдет, если время отводимое на контрольную работу
будет 20, вместо 30 (см. Приложение А)?
|Y1=20 |k1=0 |
|Y2=y1-2*k1=20 |k2=0 |
|Y3=y2-4*k2=20 |k3=4 |
|Y4=y3-k3=16 |k4=0 |
|Y5=y4-4*k4=16 |k5=0 |
|Y6=y5-7*k5=16 |k6=0 |
|Y7=y6-5*k6=16 |k7=3 |
|Y8=y7-3*k7=7 |k8=7 |
соответственно максимально количество баллов, которое студент может набрать
за отведенное время равно 34.
Что произойдет, если время отводимое на контрольную работу будет 5,
вместо 30 (см. Приложение А)?
|y1=5 |k1=0 |
|y2=y1-2*k1=5 |k2=0 |
|y3=y2-4*k2=5 |k3=0 |
|y4=y3-k3=5 |k4=0 |
|y5=y4-4*k4=5 |k5=0 |
|y6=y5-7*k5=5 |k6=0 |
|y7=y6-5*k6=5 |k7=0 |
|Y8=y7-3*k7=5 |k8=5 |
соответственно максимально количество баллов, которое студент может набрать
за отведенное время равно 10.
Что произойдет, если типов вопросов будет 4, вместо 8 (см. Приложение
Б)?
Этап 4.
Этап 3.
Этап 2.
Этап 1.
|y1=30 |k1=5 |
|y2=y1-2*k1=20 |k2=3 |
|y3=y2-4*k2=8 |k3=4 |
|y4=y3-k3=4 |k4=3 |
соответственно максимально количество баллов, которое студент может набрать
за отведенное время равно 39.
СПИСОК ИСПОЛЬЗОВАННЫХ
1. Таха Х. Введение в исследование операций.–М.: Мир,1985.
2. Кузнецов Ю.
Н. Математическое
3. Вентцель Е. С. Исследование операций. –М.: Наука,1976.
4. Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987.
5. Акоф Р., Сасиени М. Основы исследования операций. –М.: Мир,1971.
6. Вентцель Е. С. Исследование операций: задачи, принципы, методология.
–М.: Наука,1988.
7. Карманов В.
Т. Математическое
8. Зайченко Ю. П. Исследование операций. –К.: Высшая школа,1985.
9. Аоки М. Введение в методы оптимизации. –М.: Наука,1977.
10. Беллман Р., Дрейфус С. Прикладные задачи динамического
программирования. –М.: Наука,1965.
11. Муну М. Математическое программирование. Теория алгоритмов. –М.:
Наука,1990.
Решение задачи методом
Анализ чувствительности
Решение задачи симплекс-
Информация о работе Динамическое программирование (задача о загрузке)