Задача об оптимальной загрузке транспортного средства неделимыми предметами

 

 

Пусть в самолет требуется погрузить 4 вида предметов, чтобы с умма эффективностей этих предметов (например, стоимость) была

максимальна. Грузоподъемность самолета равна W; P1, P2, P3, P4, -

 

масса соответствующей единицы различных предметов;	V 1, V 2, V 3, V 4
- соответствующая эффективность каждого предмета;	-	x 1, x 2, x 3, x 4
число предметов различных видов, взятых на борт самолета.

 

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

 

Для определенности примем, что: W = 83;

P1 =24, P 2 =22, P3 =16, P4 =10, V	1= 96, V2	= 85, V3	= 50, V 4= 20

условных единиц.

 

Очевидно, что это задача целочисленного программирования. Примем для ее решения многошаговый процесс принятия решения

 

(динамическое программирование). Согласно общей схеме будем решать задачу в два этапа. На первом этапе найдем возможные оптимальные варианты планов (решений) при последовательной оптимизации по одной переменной, а на втором этапе выберем из этих “заготовок” оптимальное решение нашей задачи.

 

Первый этап. Он будет содержать4шага.

 

На шаге 1 находят возможные оптимальные варианты загрузкисамолета только предметами первого вида. Нам необходимо найти и запомнить значения x ₁ и соответствующую им максимальную стоимость груза f ₁(W) при различных возможных значениях W. В этом случае

 

максимальная эффективность груза

 

 

 

число, не превосходящее z. Зададимся значениями W с некоторым шагом и найдем для них x ₁и f ₁(W). Очевидно, если грузоподъемность самолета

 

меньше 24 ед., то ни одного предмета первого вида погрузить нельзя. При грузоподъемности от 24 до 47 ед. можно погрузить 1 ед. предмета первого вида и т.д. Результаты представим в виде таблиц. Значения W, f ₁(W)и x ₁приведены в таблице1.

 

Таблица 4.1.

 

W	f 1(W)	x 1
0..23
24..47
48..71
72..87

 

В таблицах принят более широкий предел для W - до 87 ед.

 

Проведем оптимизацию на шаге2. Рассмотрим эффективность груза, если загрузить самолет предметами первого и второго типов.

 

 

Максимум этого выражения ищут только по x ₂. Но мы не знаем, какая

 

грузоподъемность W может потребоваться для предметов второго типа. Поэтому мы должны рассмотреть выражение для f ₂(W) при различных

значений W от 0 до 83. При вычислении f (W - P ₂ x ₂) воспользуемся уже

 

полученными результатами (табл. 1).

 

Например, возьмем W = 46 ед. Для x ₂ возможны значения 0, 1, 2. Соответствующая эффективность от предметов второго вида равна 0, 85, 170, а для предметов первого вида остается грузоподъемность 46, 24, 2 ед. находим f ₁(W) = 96; 96; 0 ед. Складываем соответствующие значения

 

0+96 = 96 ед., 85+96 =181 ед., 170+0=170 ед, и выбираем наибольшее 181

ед. Оно получено при x ₂ =1. Для W =46 заносим в табл. 2 x₂ =1;

f 2(W)=181.Результаты вычисления f 2(W)и x 2	приведены в таблице 2.
				Таблица 4.2.
	W	f 2(W)		x 2
	0...21
	22...23
	24...43
	44...45
	46...47
	48...65
	66...67
	68...69
	70...71
	72...87

 

 

Из таблицы 2 следует, что при грузоподъемности транспортного средства до 21 ед. ничего в него погрузить нельзя, при грузоподъемности 22...23 ед. можно погрузить только один предмет второго типа.при грузоподъемности 24...43 ед. либо один предмет первого типа, либо один предмет второго типа. Максимальная эффективность груза будет при погрузке предметами первого типа. При грузоподъемности 44...45 ед. можно погрузить либо один предмет первого вида, либо два предмета второго вида. Большая эффективность груза будет в последнем случае, и f ₂(W)=170.При грузоподъемности46...47ед.можно погрузить один

 

предмет первого вида, до двух предметов второго вида или же по одному предмету первого и второго видов. Эффективность груза в последнем варианте максимальна...

 

Шаг 3. Будем загружать транспортное средство предметами первыхтрех видов. Требуется максимизировать по x₃

 

 

 

									Таблица 4.3.
	W			f 3(W)			x 3
	0...15
	16...21
	22...23
	24...31
	32...37
	38...39
	40...43
	44...45
	46...47
	48...63
	64...69
	70...71
	72...87
Задаемся	значением	W и для каждого	такого значения получаем
максимум	f 123поx3.	Значения	f 2(W)берут из табл. 2.Например,пусть

W = 38ед.Возможное значение x ₃= 0; 1; 2ед.и соответствующаяэффективность предметов третьего вида - 0; 50; 100 ед. На предметы первого и второго видов остается соответственно грузоподъемность 38; 22; 6 ед. По табл. 2. находим f ₂(W) = 96; 85; 0 ед. Суммарная

 

эффективность 96; 135; 100 ед. Максимальное значение эффективности при W = 38 ед. равно 135 ед. для x ₃ = 1. Результаты расчетов помещены в

 

табл. 3.

 

Шаг 4. Зададимся значением W,которое может быть занято грузомчетырех видов и вычислим x ₄, f ₄ (W) (табл. 4.). Строго говоря, здесь нам

 

достаточно было бы вычислить одну строку табл. 4 для W =83.

 

 

 

 

 

Таблица 4.4.

 

W	f 4(W)	x 4
0...9
10...15
16...21
22...23
24...33
34...37
38...39
40...45
46...47
48...57
58...63
64...69
70...71
72...81
82...87

 

 

Второй этап. Нахождение оптимального решения поставленнойзадачи. Максимальное значение f ₄(W) - это есть W ^*, соответствующее значение аргумента x ₄ - количество груза четвертого вида, который берет самолет (x ₄):

W ^*=max f ₄(W) =308; x ^*₄=1.

Масса предметов четвертого вида будет x ^*₄ P ₄ =10 ед.

 

На остальные три вида груза остается W - 10 =73 ед. При значении W = 73ед.по табл. 3получаем x ₃^*= 0;аналогично получаем x ^*₂= 0; x ₁^*= 3.

 

Если еще раз вернуться к табл. 1- 4, то увидим, что они содержат “заготовки” для оптимальной загрузки самолета любой грузоподъемности (до W =87 ед.) указанными предметами. Таким образом, мы решили не только поставленную задачу, а большой набор родственных задач. С одной стороны, это хорошо, но, с другой стороны, в памяти компьютера необходимо хранить таблицы 1- 4 на протяжении всего процесса решения. Для сложных задач последнее обстоятельство имеет существенное значение и ограничивает возможности рассмотренного метода.