Общие сведения. Решение задачи о загрузке

Решение задачи о загрузке

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

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

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

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

w1m1+w2m2+…+wnmn W,

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

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

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

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

Состояние 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. Следовательно, рекуррентное уравнение приобретает следующий вид:

Дата добавления: 2014-01-15