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

Условие задачи. Транспортное средство грузоподъемностью М = 50 уел. ед. массы загружается предметами трех типов Т, T, 7 3, масса m и стоимость р уел. ден. ед. каждого из которых известны и приведены в таблице.

Тг

Т-2

Г3

m

11

17

23

р

20

36

48

Требуется найти такой вариант загрузки, при котором стоимость перевозимого груза была бы максимальной.

Замечание 1. В иной интерпретации данная задача известна как задача о рюкзаке или о ранце. При этом грузоподъемность транспортного средства аналогична вместимости ранца, а масса и стоимость погружаемых предметов имеют то же самое смысловое значение.

Замечание 2. Интуитивно может показаться, что для достижения максимума стоимости груза следует загружать транспортное средство только теми предметами, для которых отношение р/m стоимости к массе будем называть данное отношение ценностью предмета является максимальным. Это предположение действительно верно при условии, что грузоподъемность транспортного средства кратна массе предмета с максимальной ценностью. При отсутствии кратности данный принцип может нарушаться. В качестве простейшего примера можно рассмотреть значение грузоподъемности М = 7 при двух типах предметов Т и Т2 со следующими параметрами:

Тг

Т-2

m

2

3

р

5

9

Для предмета типа Т ценность р/т = 2. 5, для предмета типа Тг ценность р/т = 3. Использование предметов типа Т2 с большей ценностью позволяет погрузить два предмета общей стоимостью 18. В то же время загрузка одного предмета типа Т2 и двух предметов типа Тi дает стоимость, равную 19. Дело в том, что при отсутствии нужной кратности остается неиспользованной часть грузоподъемности, которую в некоторых случаях можно использовать более рационально. Таким образом, для решения данной задачи следует применить более точные методы, например метод ДП.

Решение. В данной задаче управляемой системой является загружаемое транспортное средство, многошаговым процессом процесс планирования погрузки предметов. Экономический эффект представляет стоимость груза, и при этом задача решается на поиск максимума. Проведем математическую формализацию поставленной задачи.

1. Число шагов N в данной задаче следует принять равным 3, соответствующим числу типов погружаемых предметов: на первом шаге планируется погрузка предметов типа 7, на втором шаге- предметов типа Т2, на третьем типа Т3.

2. В качестве фазовой переменной х, определяющей состояние системы в ходе процесса, примем суммарную массу предметов, погруженных в транспортное средство. Именно, переменная х представляет массу предметов, погруженных в транспортное средство после первого шага процесса (т. е. только предметов типа Т), хд массу предметов, погруженных после второго шага (предметов типов Т и ТД, жз массу предметов, погруженных после третьего шага процесса (предметов всех типов Т, и 7Д. Поскольку в начальный момент общая масса предметов, погруженных в транспортное средство, равна 0, то начальное состояние системы характеризуется значением то = 0. Чтобы не допустить перегруза транспортного средства, обязательно должно выполняться условие

3. В качестве управляющей переменной и примем количество предметов каждого типа, погружаемых в транспортное средство. Именно, переменная щ представляет количество предметов типа Т, погружаемых в транспортное средство на первом шаге процесса, 112 количество предметов типа ТД погружаемых на втором шаге, из количество предметов типа Тф погружаемых на третьем шаге процесса. Ясно, что все управления принимают только целочисленные значения

4. Функция процесса х» = /фх^-ьп.;), определяющая закон изменения состояния системы, для данной задачи представляется формулой

и имеет следующий смысл: суммарная масса х* предметов, погруженных в транспортное средство после шага с номером i, равна суммарной массе предметов, погруженных после предшествующего

шага, плюс масса погруженных на текущем шаге предметов, равная щ ? гщ числу предметов, умноженному на массу каждого предмета.

5. Функция Zi, определяющая частный экономический эффект на шаге процесса с номером i, для данной задачи представляется формулой

и равна произведению числа погруженных предметов и стоимости каждого предмета соответствующего типа. Результирующий экономический эффект, или целевая функция Z, определяется по формуле

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

Предварительный этап. Данный этап решения задачи проводится в естественном порядке для г = 1,2,3, причем заполняются только первая строка вспомогательной таблицы и четыре левых столбца основной таблицы.

i = 1.

Вспомогательная таблица соответствует начальному условию .го = О и имеет вид

х0

0

Во(х о)

96

Заполнение основной таблицы проводится обычным образом. Для заданного единственного допустимого значения хо = 0 выбираем все возможные значения управления щ и заносим их во второй столбец таблицы. При этом управление щ может принимать только целочисленные значения от 0 до 4 включительно, иначе возникнет перегруз. По формулам х = .хо + и ? т и z = и ? р (вытекающим из общих формул при г = 1) проводим расчет соответствующих значений переменных х и z и заносим их в третий и четвертый столбцы. Получаем основную таблицу:

Хо

их

XI

Zl

Вх(хх)

z + В

ВоЫ

0

/0

0

0

96

96

96

1

11

20

72

92

2

22

40

48

88

/3

33

60

36

96

4

44

80

0

80

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

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

XI

0

11

22

33

44

Вх(хх)

96

72

48

36

0

Для заполнения основной таблицы будем последовательно выбирать все допустимые значения xi, внесенные во вспомогательную таблицу, и проводить соответствующие расчеты. Для значения xi = 0 находим все возможные значения управления и2 (оно может принимать только значения 0, 1 и 2, иначе возникнет перегруз) и заносим их во второй столбец таблицы. По формулам х; = х*_i + щ ? mi и z; = щ ? pi, взятым для i = 2, проводим расчет значений х.д и z2 и заносим их в третий и четвертый столбцы. На этом завершается заполнение первого строчного фрагмента основной таблицы, соответствующего х — 0. Аналогично заполняются все остальные строчные фрагменты основной таблицы, которая принимает такой вид:

XI

U2

Х2

Z2

ВъЫ

Z2 + В2

Вх(хх)

0

/0

0

0

96

96

96

1

17

36

48

84

2

34

72

0

72

XI

«2

Х2

Z2

В22)

Z-2 + В2

Bi(xi)

11

0

11

0

48

48

72

1

28

36

0

36

/2

45

72

0

72

22

/0

22

0

48

48

48

1

39

36

0

36

33

0

33

0

0

0

36

/1

50

36

0

36

44

0

44

0

0

0

0

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

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

х2

0

И

17

22

28

33

34

39

44

45

50

В22)

96

48

48

48

0

0

0

0

0

0

0

Заполнение основной таблицы проводим обычным образом:

х2

из

х-з

-Z3

В2 3)

Z3 + в3

в22)

0

0

0

0

0

0

96

1

23

48

0

48

/2

46

96

0

96

11

0

11

0

0

0

48

/1

34

48

0

48

17

0

17

0

0

0

48

/1

40

48

0

48

22

0

22

0

0

0

48

/1

45

48

0

48

28

0

28

0

0

0

0

33

0

33

0

0

0

0

34

0

34

0

0

0

0

39

0

39

0

0

0

0

44

0

44

0

0

0

0

45

0

45

0

0

0

0

50

0

50

0

0

0

0

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

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

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

i = 1.

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

i = 2.

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

г = 3.

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

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

г = 1:

*

х0

= 0,

«I = з,

*

хЛ

= 33.

i = 2:

*

Ху

= 33,

«2 = 1,

х2

= 50.

г = 3:

*

я2

= 50,

щ = о,

*

х3

= 50.

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

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

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

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

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

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

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

Замечание 3. Обратим внимание на структуру полученных оптимальных решений. Первое решение (0,0,2) вообще не содержит предметов тина Т-2 с максимальной ценностью Р2/ТП2 2,12.... Второе решение (3,1,0) содержит 3 предмета типа Т с минимальной ценностью ру/rrii = 1,82.... Таким образом, оба оптимальных решения задачи далеки от того, чтобы использовать только предметы с максимальной ценностью.

Замечание 4. Как легко видеть, целевая функция Z данной задачи возрастает при условии, что количество предметов одного типа увеличивается, а количество предметов других типов не изменяется. Поэтому при планировании последнего шага погрузки для г = 3 можно ограничиться рассмотрением лишь тех значений переменной «з, которые являются максимально допустимыми при фиксированном значении х2. Это подтверждает и вид последней основной таблицы: в ней знаки «/» расположены только у максимальных в своем строчном фрагменте значений из. Учитывая сказанное, объем вычислений можно несколько сократить, а первые четыре строчных фрагмента основной таблицы для i = 3, соответствующие ж 2 0, 11, 17. 22,

записать в следующем виде:

Х2

«3

х-л

23

Вз(хз)

23 + В 3

B2(x2)

0

2

46

96

0

96

96

11

1

34

48

0

48

48

17

1

40

48

0

48

48

22

1

45

48

0

48

48

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

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

требуемого набора предметов. Если m > М, то задача о загрузке с дополнительным условием решения не имеет. Если m = М. то решение будет являться оптимальным. Если

же m < М, то решение сводится к рассмотрению обычной задачи о загрузке с грузоподъемностью М — m > 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

при этом стоимость погруженных предметов равна

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

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

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

не меньше 1. По этой причине существует такое целое число А'2 (в качестве к-2 можно взять целую часть числа (ту/н^иу), для которого выполняются неравенства

Тогда вектор (0,U2 + к2:...) в силу неравенств

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

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

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

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

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >