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

4
АННОТАЦИЯ
Пояснительная записка курсовой работы «Решение задачи о з агрузке (задача о рюкзаке), использую рекуррентные соотношения» с одержит общие сведения о задачах динамического программ ирования, о
методах их решения.
5
СОДЕРЖАНИЕ
ВВЕДЕНИЕ…………………………………………………………………… 6
1 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ…………………………. 8
1.1
Задача динамического программирования………………………..
1.2
Примеры задач динамического программиров ания……………... 12
1.3
Общая структура динамического программиров ания…………... 16
8
2 ЗАДАЧА О ЗАГРУЗКЕ…………………………………………………… 18
2.1 Общие сведения…………………………………………………………
18
2.2 Рекуррентные соотношения для процедур прямой и обратной
прогонки………………………………………………………………………
19
2.3 Решение задачи о загрузке…………………………………………….
22
2.4 Анализ чувствительности решения…………………………………..
25
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ……………………….
27
ПРИЛОЖЕНИЕ А……………………………………………………………
28
ПРИЛОЖЕНИЕ Б……………………………………………………………
36
ПРИЛОЖЕНИЕ В……………………………………………………………. 40
6
ВВЕДЕНИЕ
Работа над данным курсовым проектом позволяет закрепить зн ания по предмету «Математические методы исследования операций».
В наше время наука уделяет все большое внимание вопросам о рганизации и управления, это приводит к необходимости анализа сло жных целенаправленных процессов под углом зрения их струк туры и
организации. Потребности практики вызвали к жизни специальные м етоды, которые удобно объединять под названием «исследование оп ераций». Под этим термином понимается применение мат ематических,
количественных методов для обоснования решений во всех областях
целенаправленной человеческой деятельности.
Целью исследования операций является выявление наилучшего
способа действия при решение той или иной задачи. Главная роль при
этом отводится математическому моделированию. Для построения м атематической модели необходимо иметь стро гое представление о цели
функционирования исследуемой системы и располагать информацией
об ограничениях, которые определяют область допу стимых значений.
Цель и ограничения должны быть представлены в виде функций.
В моделях исследования операций переменные, от которых зависят ограничения и целевая функция, могут быть дискретными (ч аще
всего целочисленными) и континуальными (непрерывными). В свою
очередь, ограничения и целевая функция делятся на линейные и нел инейные. Существуют различные методы решения данны х моделей,
наиболее известными и эффективными из них являются методы лине йного программирования, когда целевая функция и все ограничения л инейные. Для решения математических моделей других типов предн азначены методы динамического программиров ания, целочисленного
7
программирования, нелинейного программирования, многокритер иальной оптимизации и методы сетевых мод елей.
Практически все методы исследования операций порождают в ычислительные алгоритмы, которые являются итерационными по своей
природе. Это подразумевает, что задача решается последов ательно
(итерационно), когда на каждом шаге (итерации) получаем решение,
постепенно сходящиеся к оптимальному решению.
Итерационная природа алгоритмов обычно приводит к объе мным
однотипным вычислениям. В этом и заключается причина того, что эти
алгоритмы разрабатываются, в основном, для реализации с помощью
вычислительной техники.
8
1 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
1.1
Задача динамического программирования
Большинство методов исследования операций связано в пе рвую
очередь с задачами вполне определенного содержания. Класс ический
аппарат математики оказался малопригодным для решения многих з адач оптимизации, включающих большое число переменных и/или
ограничений в виде неравенств. Несомненна привлек ательность идеи
разбиения задачи большой размерности на подзадачи меньшей разме рности, включающие всего по нескольких переменных, и посл едующего
решения общей задачи по частям. Именно на этой идее о снован метод
динамического программирования.
Динамическое программирование (ДП) представля ет собой математический метод, заслуга создания и развития которого принадлежит
прежде всего Беллману. Метод можно использовать для решения вес ьма широкого круга задач, включая задачи распределения ресурсов, з амены и управления запасами, задачи о загрузке. Характерным для динамического программирования является подход к решению задачи по
этапам, с каждым из которых ассоциирована одна управляемая пер еменная. Набор рекуррентных вычислительных процедур, связывающих
различные этапы, обеспечивает получение допустимого оптимального
решения задачи в целом при достижении последнего этапа.
Происхождение названия динамическое программирование, вероятно, связано с использованием методов ДП в задачах принятия реш ений через фиксированные промежутки времени (например, в з адачах
управления запасами). Однако методы ДП успешно применяются та кже для решения задач, в которых фактор времени не уч итывается. По
этой причине более удачным предста вляется термин многоэтапное
9
программирование, отражающий пошаговый характер процесса ре шения задачи.
Фундаментальным принципом, положенным в основу теории ДП,
является принцип оптимальности. По существу, он определяет пор ядок поэтапного решения допускающей декомпозицию задачи (это б олее приемлемый путь, чем непосредственное решение задачи в исходной постановке) с помощью рекуррентных вычислительных процедур.
Динамическое программирование позволяет осуществлять опт имальное планирование управляемых процессов. Под «управля емыми»
понимаются процессы, на ход которых мы можем в той или др угой
степени влиять.
Пусть предполагается к осуществлению некоторое меропри ятие
или серия мероприятий («операция»), преследующая опред еленную
цель. Спрашивается: как нужно организовать (спланировать) опер ацию
для того, чтобы она была наиболее эффективной? Для того, чтобы поставленная задача приобрела количественный, математический хара ктер, необходимо ввести в рассмотрение некоторый численный крит ерий W, которым мы будем характеризовать качество, успешность, э ффективность операции. Критерий эффе ктивности в каждом конкретном
случаи выбирается исходя из целевой направленности операции и з адачи исследования (какой элемент управления оптим изируется и для
чего).
Сформулируем общий принцип, лежащий в основе решения всех
задач динамического программирования («принцип оптимал ьности»):
«Каково бы ни было состояние системы S перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на
данном шаге плюс оптимальный выигрыш на всех последующих ш агах
был максимальным».
Динамическое программирование – это поэтапное планирование
многошагового процесса, при котором на каждом этапе оптимизируе т-
10
ся только один шаг. Управление на каждом шаге должно выбират ься с
учетом всех его последствий в будущем.
При постановке задач динамического программирования сл едует
руководствоваться следующими принципами:
1.
Выбрать параметры (фазовые координаты), характеризу ющие
состояние S управляемой системы перед каждым ш агом.
2.
Расчленить операцию на этапы (шаги).
3.
Выяснить набор шаговых управлений x i для каждого шага и
налагаемые на них ограничения.
4.
Определить какой выигрыш приносит на i-ом шаге управление
x i , если перед этим система была в состоянии S, т.е. записать
«функцию выигрыша»:
Wi  f i ( S , xi ) .
5.
Определить, как изменяется состояние S системы S под влиянием управление x i на i-ом шаге: оно переходит в новое состояние
S '   i ( S , xi ) . (1.1)
6.
Записать основное рекуррентное уравнение динамич еского
программирования, выражающее условный оптимальный в ыигрыш W i (S) (начиная с i-го шага и до конца) через уже и звестную функцию W i + 1 (S):
Wi ( S )  max f i ( S , xi )  Wi 1 ( i ( S , xi )). (1.2)
xi
Этому выигрышу соответствует условное оптимальное управл ение на i-м шаге x i (S) (причем в уже известную функцию W i + 1 (S) надо
вместо S подставить измененное состояние S '   i (S , xi ) )
7.
Произвести условную оптимизацию последнего (m-го) шага,
задаваясь гаммой состояний S, из которых можно за один шаг
дойти до конечного состояния, вычисляя для каждого из них
11
условный
оптимальный
выигрыш
по
фо рмуле
Wm ( S )  max f m ( S , x m )
xmi
8.
Произвести условную оптимизацию ( m-1)-го, (m-2)-го и т.д.
шагов по формуле (1.2), полагая в ней i=(m-1),(m-2),…, и для
каждого из шагов указать условное оптимальное упра вление
x i (S), при котором максимум достигается.
Заметим, что если состояние системы в начальный момент извес тно (а это обычно бывает так), то на первом шаге варьировать состо яние системы не нужно - прямо находим оптимальный выигрыш для
данного начального состояния S 0 . Это и есть оптимальный выи грыш за
всю операцию
W *  W1 ( S 0 )
9.
Произвести безусловную оптимизацию управления, «читая»
соответствующие
рекомендации
на
каждом
шаге.
Взять
найденное оптимальное управление на первом шаге x1*  x1 ( S 0 ) ;
изменить состояние системы по формуле (1.1); для вновь
найденного состояния найти оптимальное управление на вт ором шаге х 2 * и т.д. до конца.
Данные этапы рассматривались для аддитивных задач, в которых
выигрыш за всю операцию равен сумме выигрышей на отдельных ш агах. Метод динамического программирования применим также и к з адачам с так называемым «мультипликативным» критерием, име ющим
вид произведения:
m
W   wi
i 1
(если только выигрыши w i положительны). Эти задачи решаются
точно так же, как задачи с аддитивным критерием, с той единстве нной
разницей, что в основном уравнении (1.2) вместо знака «плюс» стави тся знак «умножения»: Wi ( S )  max f i ( S , xi ) * Wi 1 ( i ( S , xi ))
xi
12
1.2 Примеры задач динамического программирования
Задача планирования рабочей силы :
При выполнении некоторых проектов число рабочих, необх одимых
для выполнения какого-либо проекта, регулируется путем их найма и
увольнения. Поскольку как наем, так и увольнение рабочих связано с
дополнительными затратами, необходимо определить, к аким образом
должна регулироваться численность рабочих в период реализации пр оекта.
Предположим, что проект будет выполнятся в течение n недель и
минимальная потребность в рабочей силе на протяжении i-й недели
составит b i рабочих. При идеальных условиях хотелось бы на прот яжении i-й недели иметь в точности b i рабочих. Однако в зависимости
от стоимостных показателей может быть более выгодным отклонение
численности рабочей силы как в одну, так и в другую сторону от м инимальных потребностей.
Если x i – количество работающих на протяжении i-й недели, то
возможны затраты двух видов: 1) С 1 (x i - b i )-затраты, связанные с нео бходимостью содержать избыток x i - b i рабочей силы и 2) С 2 (x i - x i - 1 )затраты, связанные с необходимостью допо лнительного найма (x i - x i - 1 )
рабочих.
Элементы модели динамического программирования определяю тся
следующим образом:
1.
Этап і представляется порядковым номером недели і,
і=1,2,…n.
2.
Вариантами решения на і-ом этапе являются значения x i –
количество работающих на протяжении і-й недели.
3.
Состоянием на і-м этапе является x i - 1 – количество работающих на протяжении (і-1) –й недели (этапа).
13
Рекуррентное уравнение динамического программирования пре дставляется в виде
f i ( xi 1 )  minC1 ( xi  bi )  C 2 ( xi  xi 1 )  f i 1 ( xi ), i  1,2,..., n
xi bi
где f n1 ( xn )  0
Вычисления начинаются с этапа n при x n =b n и заканчиваются на
этапе 1.
Задача замены оборудования:
Чем дольше механизм эксплуатируется, тем выше затраты на его
обслуживание и ниже его производительность. Когда срок эксплуат ации механизма достигает определенного уровня, может оказаться б олее выгодной его замена. Задача замены оборудования, таким обр азом,
сводится к определению оптимального срока эксплуатации м еханизма.
Предположим, что мы занимаемся заменой механизмов на протяжении n лет. В начале каждого года принимается решение либо об
эксплуатации механизма еще один год, либо о замене его новым.
Обозначим через r(t) и c(t) прибыль от эксплуатации t-летнего механизма на протяжении года и затраты на его обслуживание за этот же
период. Далее пусть s(t) – стоимость продажи механизма, который
эксплуатировался t лет. Стоимость приобретения нового механизма
остается неизменной на протяжении всех лет и равна l.
Элементы модели динамического програм мирования таковы:
1. Этап і представляется порядковым номером года і, і=1,2,...n.
2. Вариантами решения на і-м этапе (т.е. для і-ого года) являются
альтернативы: продолжить эксплуатацию или заменить мех анизм в начале і-ого года.
3. Состоянием на і-м этапе является срок эксплуатации t (возраст)
механизма к началу і-ого года.
14
Пусть f i (t)-максимальная прибыль, получаемая за годы от і до n
при условии, что в начале і-ого года имеется механизм t-летнего возраста.
Рекуррентное уравнение имеет следующий вид:
r (t )  c(t )  f i 1 (t  1)(1)

f i (t )  
r (0)  s(t )  I  c(0)  f i 1 (l )(2)
(1)-если эксплуатировать механизм,
(2)-если заменить механизм.
Задача инвестирования:
Предположим, что в начале каждого из следующих n лет необходимо сделать инвестиции P 1 , P 2 ,…, P n соответственно. Вы имеете во зможность вложить капитал в два ба нка: первый банк выплачивает г одовой сложный процент r 1 , а второй - r 2 . Для поощрения депозитов оба
банка выплачивают новым инвесторам премии в виде процента от
вложенной суммы.
Премиальные меняются от года к году, и для і-ого года равны q i 1 и
q i 2 в первом и втором банках соответственно. Они в ыплачиваются к
концу года, на протяжении которого сделан вклад, и могут быть инв естированы в один из двух банков на следующий год. Это значит, что
лишь указанные проценты и новые деньги могут быть инвестированы в
один из двух банков. Размещенный в банке вклад должен находится
там до конца рассматриваемого периода. Необход имо разработать
стратегию инвестиции на следующие n лет.
Элементы модели динамического программирования следу ющие:
1. Этап і представляется порядковым но мером года і, і=1,2,...n
2. Вариантами решения на і-м этапе (для і-ого года) являются

суммы l i и l i инвестиций в первый и второй банк соответстве нно.
15
3. Состоянием x i на і-м этапе является сумма денег на начало і-ого
года, которые могут быть инветсированы.

Заметим, что по определению l i =x i -l i . Следовательно,
xi  Pi  qi 1li 1  qi 1, 2 ( xi 1  li 1 )  Pi  (qi 1,i  qi 1, 2 )li 1  qi 1, 2 xi 1
где і=2,3,…n, x 1 =P 1 . Сумма денег x i , которые могут быть инвестированы, включает лишь новые деньги и премиальные проценты за и нвестиции, сделанные на протяжении (і-1)-го года.
Пусть f i (x i )- оптимальная сумма инвестиций для интервала от і-го
до n-го года при условии, что в начале і-го года имеется денежная
сумма x i . Далее обозначим через s i накопленную сумму к концу n-го
года при условии, что l i и (x i -l i )-объемы инвестиций на протяжении іго года в первый и второй банк соответственно. Обозначая  i  (1  ri ) ,
і=1,2, мы можем сформулировать задачу в следующем в иде.
Максимизировать z=s 1 +s 2 +…+s n , где
si  li 1n 1i  ( xi  li ) 2n 1i  ( 1n 1i   2n 1i )li   2n 1i xi , i  1,2,..., n  1
s n  ( 1  q n1   2  q n 2 )l n  ( 2  q n 2 ) x
Так как премиальные за n-й год являются частью накопленной д енежной суммы от инвестиций, в выражения для s n добавлены q n 1 и q n 2 .
Итак, в данном случае рекуррентное уравнение для обратной пр огонки в алгоритме динамического программирования имеет вид
f i ( xi )  max si  f i 1 ( xi 1 ) , i  1,2,..., n  1
0li  xi
где x i + 1 выражается через x i в соответствии с приведенной выше
формулой, а f n + 1 (x n + 1 )=0.
16
1.3 Общая структура динамического программирования
Отыскание оптимальной стратегии принятия набора последов ательных решений, в большинстве случаях, производится сле дующим
образом: сначала осуществляется выбор последнего во времени реш ения, затем при движении в направлении, обратном течению врем ени,
выбираются все остальные решения вплоть до исходного.
Для реализации такого метода необходимо выяснить все ситу ации,
в которых может происходить выбор последнего решения. Обычно
условия, в которых принимается решение, называют «состоянием» системы. Состояние системы – это описание системы, позволяющее, уч итывая будущие решения, предсказать ее поведение. Нет необходим ости выяснять, как возникло то ил иное состо яние или каковы были
предшествующие решения. Это позволяет п оследовательно выбирать
всего по одному решению в каждый момент времени. Независимо от
того, отыскивают оптимальные решения с помощью табличного метода
и последующего поиска или аналитическим путем, обычно быстрее и
выгоднее производить выбор по одному решению в один момент вр емени, переходя затем к следующему моменту и т.д. К сожалению, т аким методом можно исследовать не все процессы принятия решений.
Необходимым условием применения метода динамического програ ммирования является аддитивность цен всех решений, а также незав исимость будущих результатов от предыстории того или иного состо яния.
Если число решений очень велико, то можно построить относ ительные оценки состояний так, чтобы оценки, отвечающие каждой п аре последовательных решений, отличались друг от друга на постоя нную величину, представляющую собой средний «доход» на решение.
Также можно выполнять дисконтирование доходов от будущих реш е-
17
ний. Необходимость в этом иногда появляется в том случае, когда р ешение принимаются редко, скажем раз в году. Т огда уже не нужно
рассматривать последовательно 1,2,3…решения, чтобы достичь реш ения с большим номером. Вместо этого можно непосредственно опер ировать функциональным уравнением, что, как правило, дает существенную выгоду с точки зрения сокращения объема в ычислений.
18
2 ЗАДАЧА О ЗАГРУЗКЕ
2.1 Общие сведения
Задача о загрузке – это задача о рациональной загрузке судна (с амолета, автомашины и т.п.), которое имеет огра ничения по объему или
грузоподъемности. Каждый помещенный на судно груз приносит опр еделенную прибыль. Задача состоит в определении загрузки судна т акими грузами, которые приносят наибольшую суммарную пр ибыль.
Рекуррентное уравнение процедуры обратной прог онки выводится
для общей задачи загрузки судна грузоподъемностью W предметов
(грузов) n наименований. Пусть m i -количество предметов і-го наименования, подлежащих загрузке, r i -прибыль, которую приносит один загруженный предмет і-го наименования, w i -вес одного предмета і-го
наименования. Общая задача имеет вид следующей целочисленной з адачи линейного программирования.
Максимизировать z=r 1 m 1 +r 2 m 2 +…+r n m n .
при условии, что
w 1 m 1 +w 2 m 2 +…+w n m n  W,
m 1 ,m 2 ,…,m n  0 и целые.
Три элемента модели динамического программирования опред еляются следующим образом:
1.
Этап і ставится в соответствии предмету і-го наименования,
і=1,2,…n.
2.
Варианты решения на этапе і описываются количеством m i
предметов і-го наименования, подлежащих загрузке. Соответствующая прибыль равна r i m i . Значение m i заключено в
пределах от 0 до [W/w i ], где [W/w i ] – целая часть числа
W/w i .
19
3.
Состояние x i на этапе і выражает суммарный вес предметов,
решения о погрузке которых приняты на этапах і,і+1,...n.
Это определение отражает тот факт, что ограничения по весу является единственным, которое связывает n этапов вместе.
Пусть f i (x i )-максимальная суммарная прибыль от этапов і,і+1,...,n
при заданном состоянии x i . Проще всего рекуррентное уравнение
определяется с помощью следующей двухшаговой процедуры.
Шаг 1. Выразим f i (x i ) как функцию f i + 1 (x i + 1 ) в виде
f i ( xi ) 
ri mi  f i 1 ( xi 1 ), i  1,2,..., n
max
mi  0 ,1,...,[W / wi ]
xi  0 ,1,...,W
где f n + 1 (x n + 1 )=0.
Шаг 2. Выразим x i + 1 как функцию x i для гарантии того, что левая
часть последнего уравнения является функцией лишь x i . По определению x i -x i + 1 представляет собой вес, загруженный на этапе і, т.е. x i x i + 1 =w i m i или x i + 1 =x i -w i m i . Следовательно, рекуррентное уравнение
приобретает следующий вид:
f i ( xi ) 
max
ri mi  f i 1 ( xi  wi mi ), i  1,2,..., n
mi  0 ,1,...,[W / wi ]
xi  0 ,1,...,W
2.2 Рекуррентные соотношения для процедур прямой и обра тной
прогонки
Фермеру принадлежит стадо овец, н асчитывающее k голов. Один
раз в год фермер принимает решение о том, сколько овец пр одать и
сколько оставить. Прибыль от продажи одной овцы в і-м году составляет p i . Количество оставленных в i-м году овец удваивается в (1+1)-м
году. По истечении п лет фермер намеревается продать все стадо.
Этот чрезвычайно простой пример приводится для того, чтобы
наглядно продемонстрировать преимущества алгоритма обратной пр огонки по сравнению с алгоритмом прямой прогонки. Вычисл ительные
20
схемы процедур прямой и обратной прогонки обладают различной э ффективностью в случаях, когда этапы модели нумер уются в некотором
специальном порядке. Такая ситуация имеет место в приводимом пр имере, где этап j ставится в соответствие году j, т. е. этапы должны
рассматриваться в хронологическом порядке.
Сначала построим рекуррентные соотношения для процедур пр ямой и обратной прогонки, а затем проведем сравнение двух вычисл ительных схем. Важное различие между двумя формулировками неп осредственно следует из определени я состояния.
Обозначим количества оставленных и прода нных в j-м году овец
через x j и y j , соответственно. Положим Zj,=x j +y j . Из условий задачи
следует, что
z 1 =2x 0 =2k,
z j =2x j - 1 ,j=l,2, ...,n.
Состояние на этапе j можно описать с помощью переменной z j , которая выражает количество имеющихся к концу этапа j овец для распределения на этапах j+1, j+2, ..., n, или с помощью переменной x j , которая выражает количество имеющихся к началу этапа j+1 овец, обусловленное принятыми на этапах 1,2,..., j решениями. Первое определение
ориентировано
на
построение
рекуррентного
соо тношения
для процедуры обратной прогонки, тогда как второе определение пр иводит к использованию алгоритма прямой прогонки.
Алгоритм обратной прогонки
Обозначим через f i (z i ) максимальную прибыль, получаемую на этапах
j,j+1,…,n, при заданном z j . Рекуррентное соотношение имеет следу ющий вид:
f n ( z n )  maxn p n y n ,
yn  zn  2 k
f j ( z j )  maxj p j y j  f j 1 (2[ z j  y i ]), j  1,2,..., n  1
y j  z j 2 k
21
Заметим, что y j и z j - неотрицательные целые числа. Кроме т ого, у j
(количество овец, проданных в конце периода j) должно быть меньше
или равно z j . Верхней границей для значений z j , является величина 2 j k
(где k- исходный размер стада), которая соответствует о тсутствию
продажи.
Алгоритм прямой прогонки
Обозначим через g j (x j ) максимальную прибыль, получаемую на
этапах 1,2,...,j при заданном x j , (где x j — размер стада к началу этапа
J+1). Рекуррентное соотношение записывается в следующем в иде:
g1 ( x1 )  max p1 y1 ,
y1  2 k  x1
yj  xj 

g j ( x j )  max
p
y

g
(
), j  2,3,..., n,

j
j
j

1
y j 2 j k  x j
2


 xj  yj 

 - целое.
2


Сравнение двух формулировок показывает, что представл ение
x j- 1 через x j создает более существенные препятствия для вычисл ений, чем представление z j + 1 через z j .
В замене x j - 1 =(x j +y j )/2 подразумевается целочисленность правой
части, тогда как на равенство z j + 1 =2(z j -y j ) такое требование не
накладывается. Таким образом в случае процедуры пр ямой прогонки значения y j и x j , связанные неравенством
Y j <=2 j k -X j ,
должны дополнительно удовлетворять условию целочисленности их
полусуммы, связанному с видом зависимости х j - 1 от x j ,. Рассмотренный пример иллюстрирует трудности вычислительного характера, к оторые обычно возникают при использовании алгоритма прямой пр огонки.
22
2.3 Решение задачи о загрузке
Контрольная работа содержит вопросы по N различным темам.
Каждый вопрос типа i имеет вес Vi(i=1,2,…N), а также время, отвод имое на ответ Wi. Максимально время, которое может затратить студент на контрольную работу W. Требуется определить максимальное
количество баллов (вес), которое может набрать студент за отведенное
время W=30. Данные приведены в таблице:
I
Wi
Vi
1  5
2
2
2  6
3
3
3  4
1
2
4  3
4
4
5
7
6
6  6
5
5
7  5
3
4
8  7
2
2
Решить задачу, приведя ее к рекуррентным соотношениям.
Сначала рассмотрим задачу в общей постановке. Если обозн ачить
количество вопросов типа і через k i , то задача принимает следующий
вид:
max z  v1k1  v2 k 2  ...  vn k n
при ограничениях
w1k1  w2 k 2  ...  wn k n  W
k i -неотрицательные числа.
Если отбросить требования целочисленности k i , то решение задачи нетрудно найти с помощью симплекс -метода (см. Приложение В). В
самом деле, так как остается лишь одно ограничение, б азисной будет
23
только одна переменная, и задача сводится к выбору типа і, для которого величина v i W/w i принимает максимальное значение. Исходная задача не является задачей линейного программирования, и для ее реш ения необходимо использовать метод динамического программиров ания. Следует отметить, что рассматриваемая з адача может быть также
решена с помощью методов целочисленного про граммирования.
Каждый из трех основных элементов модели ДП определяется
следующим образом.
1. Этап j ставится в соответствии типу j, j=1,2,…,N.
2. Состояние y j на этапе j выражает суммарный вес вопросов, к оличество ответов на которые приняты на этапах j,j+1,…,N; при
этом y 1 =W и y j =0,1,…,W при j=2,3,…,N.
3. Варианты решения 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 .
Рекуррентное соотношение (для процедуры обратной прого нки)
имеет следующий вид:
f N ( yN ) 
f i ( yi ) 
max
v k  f
k j  0 ,1,...,[ y j / w j ],
y j  0 ,1,...,W
j
max
v N k N 
k N  0 ,1,...,[ y N / wN ],
y N  0 ,1,...,W
j
j 1
j
( y  w j k j ), j  1,2,..., N  1
Заметим, что максимальное допустимое значение k j ограничено
величиной [y j /w j ]. Это позволяет автоматически исключать все не я вляющиеся допустимыми варианты при заданном значении переме нной
состояния y j .
Решение исходной задачи (см. приложении А):
Этап 8.
f 8 ( y8 )  max2 * k 8 ), max k 8  30 / 2  15  7  max k 8  7
Этап 7.
f 7 ( y 7 )  maxv7 k 7  f 8 ( y 7  3 * k 7 ), max k 7  30 / 3  10  5  max k 7  5
24
Этап 6.
f 6 ( y 6 )  maxv6 k 6  f 7 ( y 6  5 * k 6 ), max k 6  30 / 5  6  6  max k 6  6
Этап 5.
f 5 ( y 5 )  maxv5 k 5  f 6 ( y 5  7 * k 5 ), max k 5  30 / 7  4, max k 5  4
Этап 4.
f 4 ( y 4 )  maxv 4 k 4  f 5 ( y 4  4 * k 4 ), max k 4  30 / 4  7  3  max k 4  3
Этап 3.
f 3 ( y 3 )  maxv3 k 3  f 4 ( y 3  1 * k 3 ), max k 3  30 / 1  30  4  max k 3  4
Этап 2.
f 2 ( y 2 )  maxv 2 k 2  f 3 ( y 2  4 * k 2 ), max k 2  30 / 4  7  6  max k 2  6
Этап 1.
f1 ( y1 )  maxv1 k1  f 2 ( y1  2 * k1 ), max k1  30 / 2  15  5  max k1  5
Оптимальное решение определяется теперь следующим обр азом.
Из условия W=30 следует, что первый этап решения задачи при y 1 =30
дает оптимальное решение k 1 =0, которое означает, что на 0 (нуль) в опросов 1-го типа будут даны ответы. Далее находим:
y 1 =30
y 2 =y 1 -2*k 1 =30
y 3 =y 2 -4*k 2 =30
y 4 =y 3 -k 3 =26
k 1 =0
k 2 =0
k 3 =4
k 4 =1
y 5 =y 4 -4*k 4 =22
y 6 =y 5 -7*k 5 =22
k 5 =0
k 6 =0
y 7 =y 6 -5*k 6 =22
k 7 =5
y 8 =y 7 -3*k 7 =7
k 8 =7
Соответственно
оптимальным
решением
задачи
является
(0,0,4,1,0,0,5,7), соответственно максимально количество баллов, к оторое студент может набрать за отведенное время рав но 46.
25
2.4 Анализ чувствительности решения
В таблице для первого этапа нам, по существу, необходимо пол учить оптимальное решение лишь для y 1 =30, так как это последний
этап, подлежащий рассмотрению (см. Приложение А). Однако в табл ицу включены вычисления для y 1 =0,1,…,30, которые позволяют провести анализ чувствительности решения.
Например, что произойдет, если время отводимое на контрол ьную работу будет 20, вместо 30 (см. Приложение А)?
Y 1 =20
Y 2 =y 1 -2*k 1 =20
Y 3 =y 2 -4*k 2 =20
Y 4 =y 3 -k 3 =16
k 1 =0
k 2 =0
k 3 =4
k 4 =0
Y 5 =y 4 -4*k 4 =16
Y 6 =y 5 -7*k 5 =16
k 5 =0
k 6 =0
Y 7 =y 6 -5*k 6 =16
k 7 =3
Y 8 =y 7 -3*k 7 =7
k 8 =7
соответственно максимально количество баллов, которое студент м ожет набрать за отведенное время равно 34.
Что произойдет, если время отводимое на контрол ьную работу
будет 5, вместо 30 (см. Приложение А)?
y 1 =5
y 2 =y 1 -2*k 1 =5
y 3 =y 2 -4*k 2 =5
y 4 =y 3 -k 3 =5
k 1 =0
k 2 =0
k 3 =0
k 4 =0
y 5 =y 4 -4*k 4 =5
y 6 =y 5 -7*k 5 =5
k 5 =0
k 6 =0
y 7 =y 6 -5*k 6 =5
k 7 =0
Y 8 =y 7 -3*k 7 =5
k 8 =5
26
соответственно максимально количество баллов, которое студент м ожет набрать за отведенное время равно 10.
Что произойдет, если типов вопросов будет 4, вместо 8 (см. Пр иложение Б)?
Этап 4.
f 4 ( y 4 )  max4 * k 4 ), max k 4  30 / 4  7  3  max k 4  3
Этап 3.
f 3 ( y 3 )  maxv3 k 3  f 4 ( y 3  1 * k 3 ), max k 3  30 / 1  30  4  max k 3  4
Этап 2.
f 2 ( y 2 )  maxv 2 k 2  f 3 ( y 2  4 * k 2 ), max k 2  30 / 4  7  6  max k 2  6
Этап 1.
f1 ( y1 )  maxv1 k1  f 2 ( y1  2 * k1 ), max k1  30 / 2  15  5  max k1  5
y 1 =30
y 2 =y 1 -2*k 1 =20
y 3 =y 2 -4*k 2 =8
y 4 =y 3 -k 3 =4
k 1 =5
k 2 =3
k 3 =4
k 4 =3
соответственно максимально количество баллов, которое студент м ожет набрать за отведенное время равно 39.
27
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Таха Х. Введение в исследование операций. –М.: Мир,1985.
2. Кузнецов
Ю.
Н.
Математическое
программирование.
–М.:
Наука,1976.
3. Вентцель Е. С. Исследование операций. –М.: Наука,1976.
4. Вентцель Е. С. Элементы динамического программирования. –М.:
Наука,1987.
5. Акоф
Р.,
Сасиени
М.
Основы
исследования
операций.
–М.:
Мир,1971.
6. Вентцель Е. С. Исследование операций: задачи, принципы, метод ология. –М.: Наука,1988.
7. Карманов
В.
Т.
Математическое
программирование.
–
М.:Наука,1986.
8. Зайченко Ю. П. Исследование операций. –К.: Высшая школа,1985.
9. Аоки М. Введение в методы оптимизации. –М.: Наука,1977.
10.
Беллман Р., Дрейфус С. Прикладные задачи динамического пр о-
граммирования. –М.: Наука,1965.
11.
Муну М. Математическое программирование. Теория алгоритмов.
–М.: Наука,1990.
28
ПРИЛОЖЕНИЕ А
Решение задачи методом динамического программирования
29
30
31
32
33
34
35
36
ПРИЛОЖЕНИЕ Б
Анализ чувствительности решения
37
38
39
40
ПРИЛОЖЕНИЕ В
Решение задачи симплекс-методом