Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами.
Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его ценность в общем случае составляет F(xJ). Имеется "рюкзак", грузоподъемность которого равна B. Требуется загрузить рюкзак имеющимися грузами таким образом, чтобы вес его был не больше заданного B, а ценность "рюкзака" была максимальной.
Составим Мат. Модель задачи. Пусть xJ - количество груза j-го вида, помещаемого в рюкзак. Тогда можно записать:
- (1) (2)
(3)
Здесь хJ могут быть и целыми числами. В общем случае это задача нелинейного программирования с сепарабельной целевой функцией, следовательно, она м. б. решена методом ДП.
Для этого погрузку "рюкзака" можно интерпретировать как N-этапный процесс принятия решений: на 1-м этапе принимается решение о том, сколько нужно взять груза 1-го вида, на 2-ом этапе - сколько груза 2-го вида и т. д. Такая интерпретация наталкивает на возможность применения для решения задачи (1) - (3) метода динамического программирования. Для этого приведем задачу (1) - (3) к виду (4) - (7) из предыдущей лекции.
Для этого введем обозначения: - вес рюкзака перед погрузкой груза j-го вида груза или вес рюкзака после погрузки грузов видов 1, 2, ..., j - 1.Очевидно, что
Y1 = 0. (4)
Текущий вес рюкзака определяется выражением
(5)
Текущий вес рюкзака в силу (2) удовлетворяет неравенству
B. (6)
Очевидно ограничения (4) - (6) эквивалентны ограничению (2), поэтому вместо модели (1) - (3) можно рассматривать модель (1), (3) - (6). Здесь ограничение (6) выводит эту модель за рамки модели (4) - (7) из предыдущей лекции. Для сведения задачи к общему виду задач динамич. программирования, запишем (6) с учетом (5):
.
Отсюда следует: ,
Или окончательно с учетом (3):
(7)
В результате исходная модель (1) - (3) свелась к эквивалентной модели вида
- (8) (9)
- (10) (11)
Задача (8)-(11) является частным случаем общей задачи динамического программирования, в которой. Здесь ограничение (9) является рекуррентным и отражает процесс загрузки рюкзака, а неравенство (10) задает область возможных значений.
Рассмотрим решение задачи (8)-(11) методом динамического программирования:
1 шаг. Вычисляется величина
(12).
В результате решения серии задач максимизации получаем точки максимума и значения.
S-тый шаг (). Вычисляются величины
(13)
В результате решения серии задач максимизации, получаем и. При s=1 решается только одна задача на максимум, т. к. значение - задано.
Для определения безусловных точек максимума, т. е. решения исходной задачи, проводим обратное движение алгоритма:
.
Отсюда:
.
Далее: . И так далее. Причем есть максимальное значение целевой функции.
Наличие условия целочисленности переменных xJ и упрощает решение задачи. В этом случае. Здесь [] указывает на то, что берется целая часть числа. Если не целые, то.
Пример:
Имеется свободный капитал в размере 4 млн. у. е. Этот капитал может быть распределен между 4-мя предприятиями, причем распределение осуществляется только целыми частями (0, 1, 2, 3 или 4 млн. у. е.). Прибыль, получаемая каждым предприятием при инвестировании в него определенной суммы, указана в таблице.
Математический загрузка инвестиция беллман
Таблица 1
Предпр. Капитал |
0 млн. у. е. |
1 млн. у. е. |
2 млн. у. е. |
3 млн. у. е. |
4 млн. у. е. |
1-е предпр. |
0 |
10 |
17 |
25 |
36 |
2-е предпр. |
0 |
11 |
16 |
25 |
35 |
3-е предпр. |
0 |
10 |
18 |
24 |
34 |
4-е предпр. |
0 |
9 |
19 |
26 |
35 |
Требуется распределить инвестиции между предприятиями из условия максимальной общей прибыли.
Построение ММ.
Обозначим: хJ- количество капиталовложений, выделенных j-тому предприятию (). Тогда прибыль, записанная в таблице, можно обозначить как FJ(xJ) (). Например, F1(0)=0; F1(1)=10; F1(2)=17 и т. д. .... F2(0)=0; F2(1)=11; F4(4)=35.
Тогда математическая модель примет вид:
ХJ?0 - целые, ()
Данная модель является частным случаем задачи о загрузке рюкзака, где N=4, В=4, аJ=1 (). Введя новую переменную yJ- израсходованные средства до выделения капиталовложений j-тому предприятию, приведем исходную модель к виду ЗДП:
; ()
Y1=0;
; ()
Решение задачи проведем в соответствии с алгоритмом динамического программирования:
1 шаг.
- 1) Зафиксируем y4=0. Тогда допустимые значения x4[0, 4-0]=[0,1,2,3,4]. 1.1 ) x4=0. Тогда F4(0)=0. 1.2 ) x4=1. F4(1)=9. 1.3 ) x4=2. F4(2)=19. 1.4 ) x4=3. F4(3)=26 1.5 ) x4=4. F4(4)=35.
Максимальное значение, и достигается оно при x4=4. Таким образом, заполняется первая строчка таблицы.
- 2) Зафиксируем y4=1. Тогда допустимые значения x4[0, 4-1]= [0,1,2,3]. 2.1 ) x4=0. Тогда F4(0)=0. 2.2 ) x4=1. F4(1)=9. 2.3 ) x4=2. F4(2)=19. 2.4 ) x4=3. F4(3)=26
Максимальное значение, и достигается оно при x4=3. Таким образом, заполняется вторая строка таблицы.
Далее аналогично фиксируем y4=2, y4=3, y4=4. Заполняем оставшиеся строки таблицы.
Таблица 2 Шага №1.
Y4 x4 |
0 |
1 |
2 |
3 |
4 | ||
0 |
0 |
9 |
19 |
26 |
35 |
35 |
4 |
1 |
0 |
9 |
19 |
26 |
- |
26 |
3 |
2 |
0 |
9 |
19 |
- |
- |
19 |
2 |
3 |
0 |
9 |
- |
- |
- |
9 |
1 |
4 |
0 |
- |
- |
- |
- |
0 |
0 |
2 шаг.
1) Зафиксируем y3=0. Тогда допустимые значения x3[0, 4-0]=[0,1,2,3,4].
1.1 ) x3=0. Тогда F3(0)=0. Определим значение второго слагаемого: при y3=0 и x3=0. Найдем y4=0+0=0. Тогда, обратившись к таблице шага 1, увидим, что. Следовательно, F3(0)+ =0+35=35. Этот результат заносим в таблицу шага 2 в ячейку, соответствующую y3=0 и x3=0.
- 1.2 ) x3=1. Аналогично: F3(1)=10. Найдем y4= y3+ x3=0+1=1. Из таблицы шага 1 определим: =. Сумма F3(1)+ =10+26=36. 1.3 ) x3=2. F3(2)=18. y4=0+2=2. ==19. Тогда F3(2)+ =18+19=37.
1.4 ) x3=3. F3(3)=24, y4=0+3=3. ==9. Тогда
F3(3)+ =24+9=33.
1.5 ) x3=4. F3(4)=34. y4=0+4=4. ==0. Тогда
F3(4)+ =34+0=34.
Максимальное значение =37, и достигается оно при x3=2. Первая строчка таблицы заполнена.
- 2) Зафиксируем y3=1. Тогда допустимые значения x3[0, 4-1]= [0,1,2,3]. 2.1 ) x3=0. F3(0)=0. y4=1+0=1. ==26. Тогда F3(0)+ =0+26=26. 2.2 ) x3=1. F3(1)=10. y4=1+1=2. ==19. Тогда F3(1)+ =10+19=29. 2.3 ) x3=2. F3(2)=18. y4=1+2=3. ==9. Тогда F3(2)+ =18+9=27. 2.4 ) x3=3. F3(3)=24 y4=1+3=4. ==0. Тогда F3(3)+ =24+0=24.
Максимальное значение, и достигается оно при x3=1. Таким образом, заполняется вторая строка таблицы.
- 3) Зафиксируем y3=2. Тогда допустимые значения x3[0, 4-2]= [0,1,2]. 3.1 ) x3=0. F3(0)=0. y4=2+0=2. f4(2) =19. F3(0)+ f4(2)=0+19=19. 3.2 ) x3=1. F3(1)=10. y4=2+1=3. =9. F3(1)+ =10+9=19. 3.3 ) x3=2. F3(2)=18. y4=2+2=3. =0. F3(2)+ =18+0=18.
Максимальное значение достигается при двух возможных значениях x3: x3=1 и x3=0. В таблицу можно занести любое из них. Таким образом, заполняется третья строка таблицы.
Далее аналогично фиксируем y3=3, y3=4. Заполняем оставшиеся строки таблицы.
Таблица 3 шага №2.
Y3 x3 |
0 |
1 |
2 |
3 |
4 | ||
0 |
35 |
36 |
37 |
33 |
34 |
37 |
2 |
1 |
26 |
29 |
27 |
24 |
- |
29 |
1 |
2 |
19 |
19 |
18 |
- |
- |
19 |
0 (или 1) |
3 |
9 |
10 |
- |
- |
- |
10 |
1 |
4 |
0 |
- |
- |
- |
- |
0 |
0 |
3 шаг.
Все вычисления производятся аналогично шагу 2. Не останавливаясь более подробно на этапах решения подзадачи данного шага, приведем получившуюся в результате таблицу.
Таблица 4 Шага №3.
Y2 x2 |
0 |
1 |
2 |
3 |
4 | ||
0 |
37 |
40 |
35 |
35 |
35 |
40 |
1 |
1 |
29 |
30 |
26 |
25 |
- |
30 |
1 |
2 |
19 |
21 |
16 |
- |
- |
21 |
1 |
3 |
10 |
11 |
- |
- |
- |
11 |
1 |
4 |
0 |
- |
- |
- |
- |
0 |
0 |
4 шаг.
Последний шаг интересен тем, что здесь решается единственная задача максимизации при заданном y1=0.
Y1=0. Следовательно x1[0, 4-0]= [0,1,2,3,4]. Выполняя все действия, аналогично предыдущим шагам, получим таблицу последнего шага, состоящую из единственной строки, соответствующей y1=0.
Таблица 5 шага №4.
Y1 x1 |
0 |
1 |
2 |
3 |
4 | ||
0 |
40 |
40 |
38 |
36 |
36 |
40 |
0 (или 1) |
Далее проводим обратное движение алгоритма:
- 1) y1=0, x1*=0, y2*= y1+ x1*=0+0=0. 2) Определяем значение x2* из таблицы шага № 3 по найденному y2*=0. Значению y2= y2*=0 соответствует значение x2(y2)=1. Следовательно, x2*=1. Далее можно определить y3*= y2*+ x2*=0+1=1. 3) Аналогично, обращаясь к таблице шага №2, найдем: x3*= x3(1)=1, y4*= y3*+ x3*=1+1=2. 4) Из таблицы шага №1 : x4*= x4(2)=2.
Окончательно имеем: первому предприятию средства не выделяются (x1*=0), второму выделяется 1 млн. у. е. (x2*=1), третьему предприятию - 1 млн. у. е. (x3*=1), и четвертому - 2 млн. у. е. (x4*=2). При этом значение целевой функции (общая прибыль по всем 4-м предприятиям) составит:
==40.
Похожие статьи
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
В начале пятилетнего периода работы предприятию выделена сумма в C руб. для приобретения нового оборудования. Стоимость одного комплекта оборудования...
-
Решение смешанной задачи для уравнения теплопроводности методом конечных разностей
Решение смешанной задачи для уравнения теплопроводности методом конечных разностей 1. Цель работы Ознакомление с методами решения смешанных задач для...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Основные понятия и обозначения Динамическое программирование как самостоятельная дисциплина сформировалась в пятидесятых годах двадцатого века. Большой...
-
Введение - Решение оптимизационных экономических задач методами линейного программирования
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Большое число экономических и планово-производственных задач связано с распределением каких-либо, как правило, ограниченных ресурсов (сырья, рабочей...
-
Во многих экономических моделях исследования операций зависимости между постоянными и переменными факторами лишь в первом приближении можно считать...
-
Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...
-
Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...
-
Экономико-математические методы и моделирование в землеустройстве позволяют решать большой круг задач, связанных с оптимизацией территориальной...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Модели линейного программирования. Основные определения Еще одним классом задач экономико-математического моделирования являются задачи линейного...
-
Линейное программирование, Общая задача линейного программирования - Экономико-математические методы
Термин "линейное программирование" впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному...
-
Календарный производственный программирование однооперационный Все существующие методы решения задач календарного планирования3 по степени достижения...
-
Необходимо найти минимальное значение целевой функции F = 4x1+18x2 > min, при системе ограничений: X1+4x2?14(1) X1+6x2?15(2) X1+x2?5(3)...
-
Провести комплексное исследование численных методов для задачи решения нелинейных уравнений. 1. Решить нелинейные уравнения А) ; Б) ; В) . 2....
-
Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе...
-
Рассматриваемая задача оптимизации ИП основывается на двухкритериальной модели Г. Марковица с незначительной корректировкой (вместо поиска долей каждого...
-
Пусть Dl, r() соответственно левые (правые) границы интервалов I, отвечающих на криволинейной трапеции ОИО значениям 0< < 1. Тогда интересующая нас...
-
По продаже системного блока компьютера на базе процессора Celeron в одном из магазинов фирмы N за месяц сложилась следующая ситуация: Цена (тыс. рублей)...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Изучение теоретических вопросов анализа чувствительности оптимального решения ЗЛП к вариациям некоторых параметров задачи и введению нового ограничения....
-
Комментарии к третьему разделу курсовой работы В третьем разделе курсовой работы студенту предлагается определить оптимальную стратегию заказа в условиях...
-
Оптимизация инвестиционного портфеля (ИП) [Дубровин и др., 2008], [Мищенко и др., 2002], [Серов, 2000] является одной из важных экономических задач,...
-
Постановка задачи - Методика решения задачи целочисленного программирования
Сформулировать по заданному 24-хзначному числу модель целочисленного программирования вида: Где все параметры модели должны быть определены из следующих...
-
Пример решения задачи симплекс-методом, Условие задачи - Математические методы и модели в экономике
Рассмотрим алгоритм симплексного метода на примере решения задачи планирования товарооборота предприятия торговли. Требуется определить оптимальную...
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач