Пояснительная записка курсовой работы «Решение задачи о загрузке (задача о рюкзаке), использую рекуррентные соотношения»

Скачать 239.76 Kb.

Название	Пояснительная записка курсовой работы «Решение задачи о загрузке (задача о рюкзаке), использую рекуррентные соотношения»
страница	2/2
Дата публикации	12.12.2014
Размер	239.76 Kb.
Тип	Пояснительная записка

100-bal.ru > Математика > Пояснительная записка

1 2

Алгоритм обратной прогонки

Обозначим через f_i(z_i) максимальную прибыль, получаемую на этапах j,j+1,…,n, при заданном z_j. Рекуррентное соотношение имеет следующий вид:

Заметим, что y_j и z_j - неотрицательные целые числа. Кроме того, у_j(количество овец, проданных в конце периода j) должно быть меньше или равно z_j. Верхней границей для значений z_j, является величина 2^jk (где k- исходный размер стада), которая соответствует отсутствию продажи.

Алгоритм прямой прогонки

Обозначим через g_j(x_j) максимальную прибыль, получаемую на этапах 1,2,...,j при заданном x_j, (где x_j— размер стада к началу этапа J+1). Рекуррентное соотношение записывается в следующем виде:

- целое.

Сравнение двух формулировок показывает, что представление x_j_-1 через x_jсоздает более существенные препятствия для вычислений, чем представление z_j₊₁ через z_j.

В замене x_j_-1=(x_j+y_j)/2 подразумевается целочисленность правой части, тогда как на равенство z_j₊₁=2(z_j-y_j) такое требование не накладывается. Таким образом в случае процедуры прямой прогонки значения y_j и x_j, связанные неравенством

Y_j<=2^jk -X_j,

должны дополнительно удовлетворять условию целочисленности их полусуммы, связанному с видом зависимости х_j_-1 от x_j,. Рассмотренный пример иллюстрирует трудности вычислительного характера, которые обычно возникают при использовании алгоритма прямой прогонки.
2.3 Решение задачи о загрузке
Контрольная работа содержит вопросы по N различным темам. Каждый вопрос типа i имеет вес Vi(i=1,2,…N), а также время, отводимое на ответ Wi. Максимально время, которое может затратить студент на контрольную работу W. Требуется определить максимальное количество баллов (вес), которое может набрать студент за отведенное время W=30. Данные приведены в таблице:

I	Wi	Vi
1 5 2 6 3 4 4 3 5 6 6 7 5 8 7	2 3 1 4 7 5 3 2	2 3 2 4 6 5 4 2

Решить задачу, приведя ее к рекуррентным соотношениям.
Сначала рассмотрим задачу в общей постановке. Если обозначить количество вопросов типа і через k_i, то задача принимает следующий вид:

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

k_i-неотрицательные числа.

Если отбросить требования целочисленности k_i, то решение задачи нетрудно найти с помощью симплекс-метода (см. Приложение В). В самом деле, так как остается лишь одно ограничение, базисной будет только одна переменная, и задача сводится к выбору типа і, для которого величина v_iW/w_i принимает максимальное значение. Исходная задача не является задачей линейного программирования, и для ее решения необходимо использовать метод динамического программирования. Следует отметить, что рассматриваемая задача может быть также решена с помощью методов целочисленного программирования.

Каждый из трех основных элементов модели ДП определяется следующим образом.

Этап j ставится в соответствии типу j, j=1,2,…,N.
Состояние y_j на этапе j выражает суммарный вес вопросов, количество ответов на которые приняты на этапах j,j+1,…,N; при этом y₁=W и y_j=0,1,…,W при j=2,3,…,N.
Варианты решения k_j на этапе j описываются количеством вопросов типа j. Значение k_j заключено в пределах от нуля до [W/w_j], где [W/w_j]-целая часть числа (W/w_j).

Пусть f_i(y_i)-максимальный суммарный вес вопросов, ответы на которые приняты на этапах j,j+1,…,N при заданном состоянии y_j.

Рекуррентное соотношение (для процедуры обратной прогонки) имеет следующий вид:

Заметим, что максимальное допустимое значение k_j ограничено величиной [y_j/w_j]. Это позволяет автоматически исключать все не являющиеся допустимыми варианты при заданном значении переменной состояния y_j.

Решение исходной задачи (см. приложении А):
Этап 8.

Этап 7.

Этап 6.

Этап 5.

Этап 4.

Этап 3.

Этап 2.

Этап 1.

Оптимальное решение определяется теперь следующим образом. Из условия W=30 следует, что первый этап решения задачи при y₁=30 дает оптимальное решение k₁=0, которое означает, что на 0 (нуль) вопросов 1-го типа будут даны ответы. Далее находим:

y₁=30	k₁=0
y₂=y₁-2*k₁=30	k₂=0
y₃=y₂-4*k₂=30	k₃=4
y₄=y₃-k₃=26	k₄=1
y₅=y₄-4*k₄=22	k₅=0
y₆=y₅-7*k₅=22	k₆=0
y₇=y₆-5*k₆=22	k₇=5
y₈=y₇-3*k₇=7	k₈=7

Соответственно оптимальным решением задачи является (0,0,4,1,0,0,5,7), соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 46.
2.4 Анализ чувствительности решения
В таблице для первого этапа нам, по существу, необходимо получить оптимальное решение лишь для y₁=30, так как это последний этап, подлежащий рассмотрению (см. Приложение А). Однако в таблицу включены вычисления для y₁=0,1,…,30, которые позволяют провести анализ чувствительности решения.

Например, что произойдет, если время отводимое на контрольную работу будет 20, вместо 30 (см. Приложение А)?

Y₁=20	k₁=0
Y₂=y₁-2*k₁=20	k₂=0
Y₃=y₂-4*k₂=20	k₃=4
Y₄=y₃-k₃=16	k₄=0
Y₅=y₄-4*k₄=16	k₅=0
Y₆=y₅-7*k₅=16	k₆=0
Y₇=y₆-5*k₆=16	k₇=3
Y₈=y₇-3*k₇=7	k₈=7

соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 34.

Что произойдет, если время отводимое на контрольную работу будет 5, вместо 30 (см. Приложение А)?

y₁=5	k₁=0
y₂=y₁-2*k₁=5	k₂=0
y₃=y₂-4*k₂=5	k₃=0
y₄=y₃-k₃=5	k₄=0
y₅=y₄-4*k₄=5	k₅=0
y₆=y₅-7*k₅=5	k₆=0
y₇=y₆-5*k₆=5	k₇=0
Y₈=y₇-3*k₇=5	k₈=5

соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 10.
Что произойдет, если типов вопросов будет 4, вместо 8 (см. Приложение Б)?

Этап 4.

Этап 3.

Этап 2.

Этап 1.

y₁=30	k₁=5
y₂=y₁-2*k₁=20	k₂=3
y₃=y₂-4*k₂=8	k₃=4
y₄=y₃-k₃=4	k₄=3

соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 39.

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

Таха Х. Введение в исследование операций.–М.: Мир,1985.
Кузнецов Ю. Н. Математическое программирование. –М.: Наука,1976.
Вентцель Е. С. Исследование операций. –М.: Наука,1976.
Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987.
Акоф Р., Сасиени М. Основы исследования операций. –М.: Мир,1971.
Вентцель Е. С. Исследование операций: задачи, принципы, методология. –М.: Наука,1988.
Карманов В. Т. Математическое программирование. –М.:Наука,1986.
Зайченко Ю. П. Исследование операций. –К.: Высшая школа,1985.
Аоки М. Введение в методы оптимизации. –М.: Наука,1977.
Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. –М.: Наука,1965.
Муну М. Математическое программирование. Теория алгоритмов. –М.: Наука,1990.

ПРИЛОЖЕНИЕ А

Решение задачи методом динамического программирования

ПРИЛОЖЕНИЕ Б

Анализ чувствительности решения

ПРИЛОЖЕНИЕ В

Решение задачи симплекс-методом

1 2

Похожие:

	Пояснительная записка к курсовой работе по дисциплине «Методика профессионального обучения» Бланк задание Вы получаете у преподавателя. Образец бланка задания представлен в приложении методических указаний к выполнению курсовой...		Методическая разработка решения задач С2 на егэ по математике. Разработана... Были последовательны и логичны, ключевые моменты решения обоснованы, а математические термины и символы использованы корректно. Задача...
	Пояснительная записка Цели и задачи освоения дисциплины Обязательный... Цель дисциплины – углубленное изучение правовых основ предпринимательской деятельности, предметного соотношения экономики и права,...		Пояснительная записка к курсовой работе на тему: “Цифровой диктофон” ...
	Пояснительная записка программы. Миссия школы, цели и задачи Задача: продолжить знакомство с творчеством Г. Х. Андерсена и со сказкой как жанром литературного произведения		Методические рекомендации по выполнению курсовой работы по дисциплине... Решение этой задачи позволяет выявить недочеты в системе управления финансами предприятия и резервы повышения его эффективности
	Курсовой проект по учебной дисциплине ...		Рекомендации по написанию курсовой работы При подготовке курсовой... Затем студент приступает к сбору информации. Первоначальное представление о теме и структуре работы можно составить по учебникам,...
	Методические указания по подготовке, написанию, оформлению и защите... Цели и задачи выполнения курсовой и выпускной квалификационной (дипломной) работы		Пояснительная записка к курсовой работе по дисциплине «Разработка... Курсовой проект содержит: страниц –20, источников – 5, рисунков – 6, таблиц – 2
	Пояснительная записка к курсовой работе по дисциплине «Разработка... Курсовой проект содержит: страниц –22, источников – 5, рисунков – 6, таблиц – 2		Пояснительная записка Цели и задачи Основные направления работы
	Курсовая работа 6 вариант задачи и требования, предъявляемые к курсовой... «Экономика предприятия». Кроме того, при подготовке курсовой работы используются знания, полученные при изучении других курсов, таких...		Курсовой работы. Составитель: доцент Корляков А. С. Екатеринбург... Курсовая работа самостоятельная работа студента, выполняемая в соответствии с типовой программой учебного процесса по подготовке...
	Отчетной работы) Курсовой проект (вид работы) По дисциплине «Теория антикризисного управления» Титульный лист курсовой работы (проекта), контрольной работы, домашнего задания, реферата, отчета о практике		Методические указания к выполнению курсовой работы по дисциплине... Рассматриваются вопросы, связанные с условиями и порядком выполнения курсовой работы. Даны общие требования к курсовой работе, выбору...

Школьные материалы