- •1 Методы и модели линейного программирования
- •1.1. Основные положения
- •1.2. Симплексный метод
- •1.3. Метод Гомори. Целочисленное решение
- •1.4. Двойственная задача
- •1.4.1. Анализ устойчивости двойственных оценок
- •1.5. Решение задачи линейного программирования средствами Microsoft Excel
- •1.6. Задачи с булевыми переменными
- •1.7. Варианты заданий линейного программирования
- •2.Динамическое программирование
- •2.1. Суть метода динамического программирования
- •2.2. Задача о рюкзаке. Уравнение Беллмана для задачи о рюкзаке.
- •2.3. Реализации метода динамического программирования для задачи о рюкзаке.
- •2. Двухиндексные задачи линейного программирования. Стандартная транспортная задача (тз).
- •Исходные параметры модели тз
- •1.4. Варианты заданий линейного программирования
- •3. Сетевое моделирование
- •3.1. Основные положения
- •3.2. Сетевой график и правила его построения
- •3.3 Расчет параметров сетевых графиков
- •3.4. Оптимизация сети методом время-стоимость
- •3.5 Варианты заданий сетевого планирования
- •4. Правила оформления курсового проекта
- •Библиографический список
- •Приложение 1
- •Курсовой проект
2.2. Задача о рюкзаке. Уравнение Беллмана для задачи о рюкзаке.
Задача о рюкзаке.
Рассмотрим на примере задачи о рюкзаке, что понимается под шагом, состоянием, управлением и выигрышем.
Загрузку рюкзака можно представить себе как процесс, состоящий из n шагов. На каждом шаге требуется ответить на вопрос: взять данный предмет в рюкзак, или нет? Таким образом, шаг процесса – присваивание переменной xi значения 1 или 0.
Теперь определим состояния. Очевидно, что текущее состояние процесса характеризует остаточная грузоподъемность рюкзака – вес, который остался в нашем распоряжении до конца (до полной укладки рюкзака). Следовательно, под состоянием перед i-м шагом понимается величина
si-1 = b - , i=2, . . . , n, (2.6)
при этом s0 является начальным состоянием, которому соответствует величина b – исходная грузоподъемность рюкзака.
Управление на i-м шаге означает присваивание двоичной переменной xi значения 0 или 1. Значит, на каждом шаге имеем всего два управления. Причем допустимость управления ui, устанавливающего xi=1, определяется условием
si = σ(si-1, ui) = si-1 – ai xi =b - ≥ 0 (2.7)
Далее везде вместо переменных x1, x2, . . . , xn будем использовать соответствующие управления u1, u2, . . . , un. Тогда формулы (2.6), (2.7) примут следующий вид:
si-1 = b - , i = 2, . . ., n, (2.8)
si = σ(si-1, ui) = si-1 - ai ui = b - ≥ 0 (2.9)
Шаговый выигрыш можно определить как wi = ci ui. Поэтому
W = = . (2.10)
Требуется найти оптимальное управление U* = ( , , . . . , ), при котором величина выигрыша (2.10) обращается в максимум.
Уравнение Беллмана для задачи о рюкзаке.
Пусть к началу n- шага остаточная грузоподъемность равна s. Оптимальное управление определяется следующим образом:
если s-an ≥ 0, то последний предмет можно положить в рюкзак, что соответствует оптимальному управлению Un(s) = un = 1;
иначе Un(s) = un = 0.
Ясно, что оптимальный условный выигрыш на n-ом шаге составит
Wn(s) = cn un.
Рассмотрим (n-1)-й шаг. Предположим, что остаточная грузоподъемность равна s. Если на этом шаге выбрать управление u, то на начало последнего шага остается вес s-an-1u. Тогда выигрыш двух последних шагах будет равен
cn-1u + Wn (s –an-1u).
Нужно найти такое u, при котором этот выигрыш максимален
Wn-1(s) = max {cn-1u + Wn(s –an-1u)} ,
Где максимум берется по всем допустимым управлениям – управлениям, для которых верно ограничение (2.9). Напомним, что u может принимать лишь два значения: 0 или 1.
Рассуждая далее аналогичным образом, приходим к рекуррентному уравнению
Wi(s) =max {ciu + Wi+1 (s – aiu)}, (2.11)
которое позволяет для любого i-го шага вычислить условный оптимальный выигрыш и найти соответствующее ему условное оптимальное управление Ui(s)=u*. Здесь u* - значение, при котором достигается максимум в (2.11). [6]