2.3. Задача о загрузке транспортного средства

 

Переходим к следующему шагу, г = 3.

На третьем шаге в первую строку вспомогательной таблицы внесем все значения параметра х₂, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы. Получаем следующую вспомогательную таблицу:

 

 

На этом предварительный этап завершен. Приступаем к проведению этапа условной оптимизации.

Этап условной оптимизации. Данный этап непосредственно связан с вычислением функций В^(х{) и проводится в обратном по­рядке для г = 3,2,1. Поскольку в соответствии с общим принципом оптимальности Беллмана имеет место равенство В₃(х₃) = 0, то в пя­тый столбец основной таблицы, полученной при г = 3, записываем нулевые значения. При этом в шестой столбец записываются суммы соответствующих чисел из двух предшествующих столбцов, а в по­следний столбец заносится максимум из всех чисел шестого столбца для каждого строчного фрагмента отдельно. Полученные значения функции В2(х2) заносятся во вторую строку вспомогательной таблицы. Заполненные таблицы уже приведены выше. Аналогично завершается заполнение основных и вспомогательных таблиц для г = 2 и г = 1. Обратим внимание, что в основной таблице для г = 1 имеется два знака «/», показывающие, что искомый максимум достигается на двух значениях управления; это может привести к наличию нескольких оптимальных решений. Приступаем к этапу безусловной оптимизации.

Этап безусловной оптимизации. На данном этапе определя­ются оптимальное значение задачи Z* и оптимальное управление (и*, «2, «з). Поскольку начальное состояние хо = 0 задано однозначно, то Z* = Во(хо) = 96, = хо = 0. Для построения оптимального управ­ления просмотрим все заполненные основные таблицы в естественном порядке при г = 1,2,3, используя отмеченные знаками «/» строки, содержащие условно-оптимальные значения управления. Получаем такую последовательность шагов.

г = 1.

В соответствующей основной таблице условно-оптимальными явля­ются два значения управления щ = 0 и щ = 3, отмеченные знаком «/». Это означает, что задача имеет не одно, а несколько оптимальных ре­шений. Построим сначала первое решение, соответствующее и\ = 0 и х\ = 0.

г = 2.

На данном шаге из второй основной таблицы выбираем тот строч­ный фрагмент, который соответствует уже найденному на предше­ствующем шаге оптимальному значению ж* = 0. В этом фрагменте условно-оптимальным является единственное управление «2 = 0, от­меченное знаком «/»; полагаем и*₂ = 0, и в той же строке таблицы находим ж₂ = 0.

г = 3.

Из третьей основной таблицы выбираем тот строчный фрагмент, который соответствует найденному на предшествующем шаге х*₂ = 0. В этом фрагменте условно-оптимальным является единственное управ­ление «з = 2, отмеченное знаком «/»; полагаем и₃ = 2, и в той же строке таблицы находим х\ — 46.

На этом построение первого оптимального решения задачи, имею­щего вид (0,0,2), завершено. Проведем построение второго оптималь­ного решения, соответствующего — 3, проходя все основные таблицы еще раз.

i = 1_: Xq = 0, и* = 3, х[ = 33. i = 2: х\ — 33, «2 ^{= 1}, ^2 = 50. г = 3: х₂ = 50, и*₃ = 0, х*₃ = 50.

Следовательно, второе оптимальное решение имеет вид (3,1,0). Других оптимальных решений задача не имеет.

Тем самым решение задачи закончено. Учитывая экономический смысл введенных переменных и функций, формулируем окончательный ответ к задаче.

Ответ: максимум стоимости погружаемых в транспортное средство

предметов равен 96 усл. ден. ед. При этом существуют два варианта

оптимальной загрузки:

1)               погрузить 2 предмета типа Т₃\

2)               погрузить 3 предмета типа Т\ и 1 предмет типа

К постановке и решению данной задачи необходимо сделать ряд следующих замечаний.

Замечание 3. Обратим внимание на структуру полученных опти­мальных решений. Первое решение (0,0,2) вообще не содержит пред­метов типа Т₂ с максимальной ценностью р₂/т^ = 2,12.... Второе решение (3,1,0) содержит 3 предмета типа Т\ с минимальной цен­ностью Pi/mi = 1,82.... Таким образом, оба оптимальных решения задачи далеки от того, чтобы использовать только предметы с мак­симальной ценностью.Замечание 4. Как легко видеть, целевая функция Z данной задачи возрастает при условии, что количество предметов одного типа увеличивается, а количество предметов других типов не изменя­ется. Поэтому при планировании последнего шага погрузки для i = 3 можно ограничиться рассмотрением лишь тех значений переменной «з, которые являются максимально допустимыми при фиксированном значении х₂. Это подтверждает и вид последней основной таблицы: в ней знаки «V» расположены только у максимальных в своем строч­ном фрагменте значений щ. Учитывая сказанное, объем вычислений можно несколько сократить, а первые четыре строчных фрагмента основной таблицы для г = 3, соответствующие х₂— 0, 11, 17, 22, записать в следующем виде:

 

Подчеркнем, что сказанное относится только к последнему шагу и не может быть распространено на случаи ! = 1 и г = 2, поскольку увеличение числа предметов типов Т\ или Т₂ может в силу ограни­чения по грузоподъемности привести к вынужденному уменьшению числа предметов типа Т3.

Замечание 5. Аналогично решается задача о загрузке транспорт­ного средства с дополнительным условием, что число погруженных предметов типа Т_г должно быть не менее к, , где кг — заданные целые неотрицательные числа. Для решения такой задачи вычисляется масса

7п = к\тп,\ + к₂т₂ + кзтз

требуемого набора предметов. Если т > М, то задача о загрузке с дополнительным условием решения не имеет. Если 771 = М, то ре­шение и* = к±, и*₂ = к₂, «з = кз будет являться оптимальным. Если же 771 < М, то решение сводится к рассмотрению обычной задачи о загрузке с грузоподъемностью М — т > 0.

Замечание 6. Обсудим на примере рассмотренных задач вопрос о значимости предварительного этапа метода ДП. Как уже отмечалось выше в гл. 1 и было продемонстрировано в ходе решения, на данном этапе вычисляются все допустимые значения фазовых и управляющих переменных (в частности, области определения функций Беллмана или содержащие их множества). В ряде случаев предварительный этап оказывается малоинформативным. Например, в рассмотренной выше задаче о распределении инвестиций на этом этапе помимо элемен­тарных расчетов лишь подтверждено очевидное умозаключение, что фазовые переменные х,\ и х₂ могут принимать все целочисленные зна­чения от 0 до 5 включительно. Заметим тем не менее, что никакой излишней вычислительной работы на данном этапе проведено не было, поскольку все результаты предварительного этапа были использованы на последующем этапе условной оптимизации.

Для рассматриваемой задачи о загрузке ситуация несколько меня­ется. Проведение предварительного этапа позволило нам при вычис­лении функции В₂(х₂) ограничиться рассмотрением одиннадцати зна­чений переменной Х2= 0, 11, 17, ..., 50; остальные значения являются просто нереализуемыми. Этот набор чисел представляет собой область определения функции _В₂(ж2). Без проведения предварительного этапа нам пришлось бы начинать расчеты с этапа условной оптимизации для i = 3, причем сразу бы возник вопрос: для каких значений х₂ необходимо вычислять функцию В2{х2)1 Конечно, по смыслу задачи 0 ^ X2 ^ M = 50, но в этом промежутке содержится бесконечное мно­жество чисел. Учитывая целочисленность масс предметов всех типов, мы можем сделать вывод и о целочисленности переменной Х2 и ограни­читься вычислениями В₂(х₂) только для целых чисел от 0 до 50. Таких чисел всего 51, что значительно больше 11 допустимых значений, вы­явленных на предварительном этапе. Таким образом, проведение пред­варительного этапа позволяет заметно сократить объем вычислений.

Если условие целочисленности масс предметов не выполняется, что вполне может быть в реальных задачах, то ситуация усложняется. Дей­ствительно, пусть массы предметов заданы с точностью 0,1 усл. ед. (например, можно принять mi=10,8, ТП2=17,4, тз=23,7; оптимальные решения и оптимальное значение задачи при этом не изменятся). То­гда переменная х₂ как сумма масс предметов типов Т\ и Т₂ тоже обязана иметь точность представления 0,1; в промежутке от 0 до 50 такая переменная может принимать 501 значение, и число подлежа­щих рассмотрению вариантов возрастает практически на порядок. В то же время проведение предварительного этапа позволяет выявить, как и выше, всего 11 допустимых значений переменной х₂ (среди которых большинство не являются целыми, а представлены с точностью 0,1). Аналогичная ситуация возникает и в том случае, когда условие цело­численности масс сохраняется, а грузоподъемность увеличивается в 10 раз до значения M = 500.

Подчеркнем, что за сокращение объемов вычислений, обеспечивае­мое проведением предварительного этапа, приходится «платить» необ­ходимостью запоминания промежуточных значений переменных. При «ручном» счете с использованием таблиц запоминание происходит ав­томатически, при использовании ЭВМ об этом необходимо заботиться специально. При этом возникает следующая характерная альтерна-тпва: либо ускорить расчеты при увеличении объема используемой памяти, либо сократить объем памяти с неизбежным снижением ско­рости расчетов. Единого рецепта на все случаи здесь не существует, и при решении данного вопроса нужно руководствоваться конкретными обстоятельствами.

Подводя итог, можно сказать, что предварительный этап иллюстри­рует общее положение, когда за счет некоторого усложнения логики сокращается объем вычислений и время решения задачи. Кроме того, предварительный этап носит естественный характер и с методологи­ческой точки зрения, поскольку проводится по ходу многошагового процесса в отличие от этапа условной оптимизации, проводимого «от конца к началу».

Замечание 7. Другим подходом к сокращению объема вычисле­ний является попытка вычисления функций Беллмана в явном виде сразу для всех значений фазовых переменных. Для данной задачи при 1 = 3 с учетом свойства Дз (х₃) = 0 получаем:

В₂(х₂) = тах{р₃ • щ | х₃ = х₂ + т₃ • и₃},

из

где максимум берется по всем целым неотрицательным значениям «з, обеспечивающим выполнение условия х₃ м. Из этого условия следует, что

М - х₂

из ^

т₃

 Полученные выражения являются достаточно простыми, но уже для следующего шага г = 2 ситуация усложняется:

5х(ж1) = тах{р₂ • и₂ + В₂(х₂) | х₂ = + т₂ ■ и₂} =

= тах< р₂ ■ и₂ + рз

П2 ^

где максимум берется по всем целым неотрицательным значениям и₂, для которых выполняется условие

М - хг

т₂

Вычисление последнего максимума уже не является элементарной за­дачей, поскольку с ростом «2 первое слагаемое в сумме возрастает, а второе — убывает. Отметим, что усложнение вычислений функций Беллмана от шага к шагу является характерной чертой метода ДП. Тем самым и попытка решить задачу в общем виде приводит к су­щественным трудностям, многие из которых позволяет обойти пред­варительный этап метода ДП.

Замечание 8. В продолжение обсуждения рассматриваемой за­дачи о загрузке приведем дополнительные рассуждения, позволяющие в отдельных случаях уменьшить объем вычислений. Предположим, что все типы Т\, Т₂, ... погружаемых предметов упорядочены по возраста­нию их ценности, причем (для простоты) все ценности будем считать различными:

гпх т₂

Пусть (щ,и2,-..) — некоторое допустимое решение задачи, т.е. и1,112 • • ■ ■—целые неотрицательные числа, для которых выполняется ограничение по массе

т 1«1 + ГП2«2 + пг' ^ М; при этом стоимость погруженных предметов равна

Р1Щ +Р2П2+Р¹,

где через т! и р' обозначены масса и стоимость предметов, номера типов которых больше 2. Тогда при выполнении условия

-1

„ ^ I ^т 1 РГ и\ > I------------------------

\т₂ р₂

которое можно назвать условием избыточности малоценных предме­тов, данное допустимое решение не является оптимальным. Действи­тельно, из приведенного условия следует соотношение

VI , , . т_х —щ + 1 ^ —щ, Р2           т₂

показывающее, что расстояние на числовой оси между числами

Р\                                         т_х

—и\ и —«1 Р2          т₂не меньше 1. По этой причине существует такое целое число 1$2 (в ка­честве &2 можно взять целую часть числа (т\/т₂)^и1)^ ДЛЯ котороговыполняются неравенства

Р1 ^ , ^ ГП\

— Щ < К2 ^ ----------------------------- Щ.

Р2                                          т₂

Тогда вектор (0, «2 + ^2, • • •) ^в силу неравенств

Щ\ • 0 + т₂(«2 + к₂) + т' ^ т₂и₂ + т₂ —щ +т! <М

т₂

является допустимым решением и с учетом соотношений

р1 ■ О + р₂(и₂ + к₂) +р' > р2«2 + р2 —«1 + р' = р₂и₂ + р_ги 1 + р'

Р 2

дает большее значение стоимости, чем исходный вектор  ...).

Иными словами, мы показали, что погрузка слишком большого коли­чества предметов типа Т\ малой ценности не является целесообразной, что полностью соответствует интуитивным представлениям и конкре­тизирует их. Для рассматриваемой задачи

— = 1,82, — = 2,12, (Ч-ау¹ ₌ 10,93

тпх                     т₂                \т₂ р₂)

(здесь получаемые значения округлены до второго знака после за­пятой). Это означает, что погружать 11 и более предметов типа Т\ невыгодно: погрузка надлежащего числа предметов типа Т₂ в этом случае даст большее значение стоимости. Например, 12 предметов типа Т\ имеют массу 132 и стоимость 240; в то же время предметы типа Т₂ в количестве

12

т₂

имеют массу 119 < 132 и стоимость 252 > 240. Конечно, грузоподъем­ность М = 50 вообще не позволит погрузить 12 предметов типа Т\, но если принять, например, М = 250, то таких предметов можно будет погрузить

= 22.

250

ТГ

и учет условия избыточности позволит сократить число рассматри­ваемых вариантов погрузки предметов этого типа примерно вдвое. Заметим, что условие избыточности малоценных предметов типа Т\ можно обобщить и записать в виде

-1-

і> 1 [ \ ГПі Рі ) )

а также сформулировать аналогичные условия для предметов других типов. Отметим, однако, что проведенные рассмотрения устанавливаютобщие свойства оптимальных решений задачи и не имеют прямого отношения к методу ДП.

Замечание 9. В заключение раздела приведем постановку еще одной задачи, математическая формализация и решение которой про­водятся в полной аналогии с рассмотренной задачей о загрузке. Од­нородная заготовка длиной М (деревянный брус, металлический про­филь, пластиковая труба) должна быть разрезана на несколько от­дельных деталей, относящихся к одному из N типов. Длины деталей различных типов равны та их стоимости равны Рг, г = 1,2, ...,Л^Г (потерями материала при разрезании для упрощения задачи прене­брегаем). Требуется определить такой способ разреза заготовки, при котором суммарная стоимость получаемых деталей была бы макси­мальной. Данный пример показывает, что зачастую различным образом формулируемые задачи с различным экономическим содержанием мо­гут быть приведены к одной математический модели и решены одним методом.