Канонические уравнения. Теория Гамильтона – Якоби.

Уравнение Эйлера - Лагранжа для функционала

имеет вид:

Вводим новую переменную p = F_y'. Во многих случаях из нее можно выразить поэтому, если ввести функцию, называемую гамильтонианом:

где т.е.

то

прямым дифференцированием получаются следующие уравнения:

Так как уравнения Эйлера – Лагранжа в данном случае имеют вид: , получим:

Это гамильтонова, или каноническая форма уравнения Эйлера – Лагранжа, а переменные y и p называются каноническими переменными.

Как можно заметить, функция Гамильтона H выбрана равной левой части первого интеграла Эйлера, так как во многих задачах это выражение сохраняет постоянное значение, если функция F явно не зависит от x.

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

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

На рубеже 50 – 60-х годов 20 века были разработаны методы поиска абсолютного экстремума функционалов, позволяющие находить решение не только среди гладких кривых и не только для случаев, когда множество управлений открыто. Этими методами являются динамическое программирование и метод, основанный на так называемом "принципе максимума" Л.С. Понтрягина.

Принцип максимума

Пусть фазовые координаты некоторой управляемой системы описываются системой обыкновенных дифференциальных уравнений (в векторной форме):

(1)

причем. x₁(0)=x₁₀,…x_n(0)=x_n0.

Управления принадлежат ограниченной замкнутой области U. Необходимо из класса кусочно-непрерывных управлений выбрать такое u(t), чтобы при переводе системы из начальной точки x(0)=(x₁₀, x₂₀,…, x_n0) в заданную конечную точку x(T)=(x_1T,x_2T,…,x_nT) функционал

(2)

достигал экстремального значения.

Пусть для определенности необходимо обеспечить минимум функционалу (2). Если требуется, чтобы функционал достигал максимума, необходимо перед правой частью (2) поставить минус.

Введем дополнительную координату состояния

и, добавив к системе (1) еще одно уравнение

получим систему уравнений

(3)

Правые части системы (3) не зависят от x₀.

При введении дополнительной координаты x₀(t) размерность вектора состояний увеличивается на единицу. Обозначив новый расширенный вектор фазовых координат через ,а его производную через :

можем записать систему (3) в виде .

Введем совокупность вспомогательных, пока произвольных функций с помощью которых построим функцию

(4)

Функция Н называется функцией Гамильтона. Она имеет частные производные

(5)

Принцип максимума формулируется следующим образом.

Для того, чтобы управление u*(t), переводящее систему из x₀ в x_T, было оптимальным, т.е. доставляло минимум функционалу (2), необходимо, чтобы при любом t, 0 £ t £ T:

1) существовала непрерывная ненулевая вектор-функция составляющия которой удовлетворяют основной

(6)

и сопряженной системе уравнений

(7)

2) функция Гамильтона

,

являющаяся скалярным произведением вектора y(t) на вектор скорости перемещения точки фазовой траектории, достигала бы максимума по u при управлении u=u*(t);

3) в момент времени t=T выполнялись соотношения

Система уравнений (6) описывает движение системы, сопряженная система уравнений (7) служит для отыскания функций y(t). Учитывая (5), системы уравнений (6) и (7) можно записать в более сжатом виде:

(8)

Решение системы уравнений (8) в общем случае является трудоемким, и часто в аналитическом виде его получить не удается.

При численном методе вначале ищут решение при произвольном начальном значении y(t₀), на втором шаге определяют управление u(t), на третьем – находят траекторию x(t), исходящую из заданной начальной точки x₀ . Если эта траектория попадает (оканчивается) в требуемую точку, то решение найдено. Если нет, то снова выбирают y(t₀) и т.д.

Принцип максимума является удобным средством определения оптимального закона управления как функции времени, т.е. для отыскания оптимальных программных управлений (разомкнутые САУ), а не для отыскания управлений в виде функций от переменных состояния.

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

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

В этом случае функционал имеет вид

(9)

Пример 1. Рассмотрим задачу оптимального быстродействия на следующем примере. Пусть имеется объект с массой m=1, размерами которого можно пренебречь. Объект снабжен двигателем, при помощи которого он может перемещаться вдоль горизонтальной прямой. Сила, развиваемая двигателем, ограничена условием .

Обозначим расстояние от объекта до некоторой точки прямой, вдоль которой он перемещается, через x₁. Тогда по второму закону Ньютона можно написать .

Если обозначит скорость движения объекта через x₂ , то уравнение движения будут иметь вид

(10)

Требуется определить, как должна изменяться сила тяги двигателя u(t), чтобы за минимальное время перевести объект из заданного начального состояния (x₁₀, x₂₀) в начало координат (0, 0).

Функция Н в рассматриваемом случае имеет вид

(11)

Составим уравнения для переменных y_i (I=0, 1, 2):

откуда получим

y₀=c₀=const, y₁=c ₁=y₁(t₀)=const, y₂=c₂-c ₁t = y₂(t₀)-y₁(t-t₀)

Из (11), учитывая (10), имеем

u(t)=+1, если y₂(t)>0, (12)

u(t)=-1, если y₂(t)<0

Таким образом, оптимальным будет управление: u(t)= sign y₂(t)= sign (c₂-c₁t).

Так как функция y₂=c₂-c ₁t меняет знак не более одного раза, то оптимальное управление является кусочно-постоянной функцией, имеющей не более двух знакопостоянных интервалов.

Найденный закон изменения управления u =u(t) может быть использован для построения оптимального программного управления (разомкнутая система). Для замкнутой САУ необходимо найти закон управления не как функцию времени, а как функцию фазовых координат u =u(x)/ Для этого нужно исключить время t из выражения для u(t).

Из системы (10) имеем

При u=±1 получим: , где с – постоянная интегрирования. Таким образом, фазовые траектории представляют собой два семейства парабол, соответствующих управлениям ±1. Оптимальная же траектория должна включать кусок параболы, проходящей через точку (0,0). Этим условиям отвечают параболы , на которых и должно происходить переключение управления. Уравнение линии переключения имеет вид:

Пример2. “Мягкая посадка”.

Рассмотрим задачу “мягкой посадки” на поверхность планеты. Пренебрежем влиянием атмосферы (допустим, что это поверхность Луны), кроме того не будем учитывать зависимость силы тяжести от высоты. Тогда уравнения, связывающие высоту h над поверхностью, вертикальную скорость v и массу m, имеют вид

где μ – скорость истечения газов относительно ракеты, – “тяга”. Примем, что в начальный момент ракета имела высоту и скорость . В момент посадки и высота, и скорость должны быть нулевыми: . Определим оптимальной управление ракетой при условии наименьшего расхода топлива

Введем стандартные обозначения и, как это требуется в методе Понтрягина, дополнительную координату = , , причем Управлением является – величина, пропорциональная скорости изменения массы ракеты. Итак, уравнения имеют вид:

Построим функцию Понтрягина

где – переменные сопряженной системы

Так как, функция Понтрягина – линейная функция относительно u, то максимального значения она достигает лишь на границе области определения. Выясним, как ведет себя множитель, стоящий перед u,

Рассмотрим производную

Таким образом, нигде в нуль не обращается: m и , изменяется монотонно и не имеет ни максимума, ни минимума.

Как правило, режим работы двигателя следующий: если он включен, то тяга постоянна и равна , если выключен – тяга равна нулю. Поэтому имеет максимальное значение при

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

Чтобы эти моменты определить, проинтегрируем дифференциальные уравнения движения.

При имеем.

На следующем отрезке времени получим

Возьмем интеграл, для чего воспользуемся равенством

Отсюда

Краевое условие приводит к следующим трансцендентным уравнениям, определяющим и :

где

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

Динамическое программирование

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

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

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

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

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

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

Рассмотрим применение метода ДП для оптимизации управления в непрерывных системах.

Пусть имеется задача минимизации функционала

(1)

для системы, поведение которой описывается системой дифференциальных уравнений вида

(2)

В этих уравнениях x – точка из области допустимых значений координат состояния в данный момент времени, u – вектор управления из области допустимых управлений U. В начальный момент времени t=0, x=x₀. Момент времени Т задан.

Пусть в некоторый момент времени 0<t<T состояние системы характеризуется точкой x(t). Начиная с момента t в течение промежутка времени Dt используется некоторое произвольное управление u(t)ÎU, и система к моменту времени t+Dt переводится в состояние

(x+Dx)=(x+f(x, u, t)Dt

Пусть с момента времени t+Dt и до конца t=Т используется оптимальное управление u*(t). Обозначим через I*(t) минимальное значение функционала (1) при оптимальном управлении u*(t) при t£ t£Т, т.е.

Тогда при использовании управления

значение функционала (1) будет равно

При использовании на интервале (t, t+Dt) оптимального управления получим

(3)

При малых Dt с точностью до бесконечно малых более высокого порядка, чем Dt можно записать

Заменяя t на t, можно записать (3) в следующем виде:

Полученное уравнение называют функциональным уравнением Беллмана. Оно представляет собой формальную запись принципа оптимальности.

Предположим, что функция I(t) имеет частные производные по всем координатам x и по времени t. Тогда, разлагая I*(t) в ряд Тейлора, получим с точностью до бесконечно малых первого порядка

(4)

Учитывая, что Dx_i=f_i(x, u, t)Dt, получим

(5)

В силу того, что вариация uD произвольная, упростив (5), окончательно получим для произвольного момента времени t

(6)

Полученное дифференциальное уравнение в частных производных называется уравнением Беллмана.

Если функционал (1) не зависит явно от времени, т.е. , то уравнение (6) запишется в следующем виде:

(7)

От выражения (7) легко перейти к условиям принципа максимума. Выберем функции y_i(t) следующим образом:

Тогда функция Гамильтона запишется в следующем виде:

Так как , то основное условие принципа максимума совпадает с (6).

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

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

Итак, задача о кратчайшем пути. Данные приведены на рисунке. На этом рисунке квадраты (узлы) представляют собой города, а числа у стрелок (дуг) затраты на перевозку от одного города до другого. Перевозчик начинает путь из узла №1 и завершает его в узле №10.Он хочет минимизировать затраты.

Вопрос: каким маршрутом при этих требованиях он должен двигаться ?

Если полагать, что числа - это расстояния, то ищется кратчайший путь от точки 1 до точки 10. Вообще говоря, это тип задач, называемых “задачей о кратчайшем пути”, но в конкретных применениях числа над дугами могут означать любые измерения. Один из путей решения таких задач – прямое (полное) перечисление. В задаче, приведенной на рисунке всего 18 возможных маршрутов. Если есть желание, то можно составить список и увидеть, что кратчайший путь здесь 1-3-7-9-10 с ценой 59, а самый длинный 1-4-5-9-10 с ценой 88.

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

Чтобы понять, как это работает, предположим, что нам известен кратчайший путь от узла 2 до узла10, от узла 3 до узла10 и от узла 4 до узла 10, т.е.

узел	Оптимальный маршрут	цена
	2-6-8-10
	3-7-9-10
	4-7-9-10

Теперь мы можем легко определить оптимальный маршрут от 1-10, это, как ни странно, оказывается самый невыгодный маршрут из 1 в 3.

Каким образом мы рассуждали:

(1-2)+min(2-10) 8+54

Min (1-10) = min (1-3)+min(3-10) 17+42 = 59

(1-4)+min(4-10) 5+60

Следовательно, оптимальное решение – (1-3-7-9-10) с ценой 59.

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

Пусть f_n(i)-минимальная цена маршрута, если мы находимся в узле i и впереди у нас еще n шагов (стадий). Определить что такое состояние и стадия, это начало постановки задачи динамического программирования.

В нашей задаче о кратчайшем пути мы стартуем из узла 1.Кроме того, мы видим, что на всем пути нам нужно принять решение о направлении движения 4 раза.

Другими словами, наша цель найти f₄(1), т.е. минимальную цену маршрута, когда мы находимся в узле1 и нам предстоит принять 4 решения. То, что мы сделали ранее, в терминах f_n(i), это использовали f₃(2), f₃(3) и f₃(4), чтобы найти f₄(1). Перерисуем таблицу в новой терминологии:

Если Сij – цена пути от узла i до узла j, тогда:

c₁₂ + f₃(2)

f₄(1) = min c₁₃ + f₃(3) ( 1 )

c₁₄ + f₃(4)

Это и есть заготовка рекурсивного соотношения, когда минимальная цена при 4 предстоящих решениях определяется через минимальную цену при 3 предстоящих решениях. В динамическом программировании используется рекурсивное отношение, которое обычно начинается с f₁(i) для нахождения f₂(i), который в свою очередь позволяет найти f₃(i). Т.о. общая рекурсия выглядит так:

( 2 )

В этом выражении D(i)- набор всех решений, которые возможны из состояния i. Т.о. D(i) -это множество узлов достижимых за один шаг из угла 1, т.е.D(1)- это набор решений по движению в узлы 2,3 или 4. Ясно, что выражение говорит, что мы оцениваем каждое решение j, являющееся элементом D(i) и выбираем наименьшее по цене. В этих обозначениях

т.е. это укороченный вариант записи (1). Воспользуемся общим рекурсивным соотношением (2) для решения нашей задачи с самого начала.

Шаг 1. Найти f₁(i) для i=8,9. Заметим, что когда нам осталось сделать один шаг (принять одно решение), мы должны находиться или в узле 8 или узле 9. Т.к. из узлов 8 и 9 мы можем перейти только в узел 10, то в реальности проблемы выбора нет, т.е. D(8)=10 и D(9)=10. Из схемы видно, что f₁(8)=5 и f₁(9)=14. Т.е. цена самого короткого маршрута из узла 8 в узел 10 равна 5, а из узла 9 в узел 10 равна 14. Это выглядит тривиально, но это действительно первый и решающий шаг в решении задачи с помощью метода динамического программирования.

Шаг 2Здесь мы уже можем использовать выражение (2) и видеть как работает динамическое программирование. Сейчас нам нужно найти f₂(5), f₂(6) и f₂(7). В состояниях 5, 6 или 7 имеется возможность движения в узлы 8 или 9, т.е. D(5)= D(6)= D(7)={8,9}.Теперь мы можем построить вычислительную таблицу для нахождения f₂(i)

Таблица 1

i	Cij + f1 (j)
j	f2(i)	j*(i)
	23+5=28	17+14=31	28(31)	8(9)
	11+5=16	14+14=28	16(28)	8(9)
	23+5=28	5+14=19	19(28)	9(8)

В рядах таблицы возможные значения для состояния i.В колонках возможные решения (j)Т.е. в этой модели решение j, принятое в состоянии i означает движение из узла i в узел j . Ячейки таблицы - цены перехода из i в j, т.е. значения С_ij +f₁(j) для соответствующих i и j, f₂(i) -минимальное значение в каждом ряду и j*(i) -оптимальное решение принятое в каждом состоянии i. Например, если мы находимся в узле 5(i=5), минимальную цену 28, дает решение о переходе в узел 8.

Шаг 3На этом шаге воспользуемся результатами шага2, чтобы найти f₃(i), для i=2,3,4, точно таким же способом как мы использовали результаты шага 1 для нахождения f₂(i), для i=5,6,7

Таблица 2

Cij + f2 (j)
i	j	f3(i)	j*(i)
	32+28=60 32+31=63	38+16=54 38+28=66	47+19=66 47+28=75
	17+28=45 17+31=48	32+16=48 32+28=60	23+19=42 23+28=51
	52+28=80 52+31=83	47+16=63 47+28=75	41+19=60 41+28=69

Шаг4Процесс нахождения f₄(i) нам уже знаком, но мы его повторим для завершенности картины. Вот таблица:

Cij + f3(j)
i	j	f4(i)	j*(i)
	8+54=62 8+75=83	17+42=59 17+60=77	5+60=65 5+83=88

Мы снова видим, что минимальная цена маршрута от 1 до10 - 59. Чтобы найти оптимальный маршрут мы должны проделать обратный путь по нашим таблицам. Таблица 3 говорит, что мы должны двигаться из узла 1 в узел 3. Таблица 2 из узла 3 в узел 7.Таблица 1 из узла 7 в узел 9, а на шаге 1 мы знаем, что из узла 9 у нас один путь - в узел 10.Т.о. мы опять видим, что оптимальный маршрут -1-3-7-9-10 (1-4-5-9-10).

Задача о рюкзаке

Важный класс задач динамического программирования берет свое название из следующей иллюстративной ситуации. Турист может нести до 11кг продуктов в своем рюкзаке. Он должен выбрать из 4 наименований продуктов, упакованных в маркированные и запечатанные пакеты. Данные по ним приведены в таблице 4.

N	масса пакета	полезность
А
В
С
Д

Туристу надо максимизировать общую полезность набора при условии ограничения на общую массу. Например, он может выбрать 11 пакетов типа А и получить 22 единицы полезности. С другой стороны он может выбрать 3 пакета типа С и 1 пакет типа В с общим эффектом 3*6+5=23.Выбирать можно только целые пакеты.

Математическая формулировка может быть следующей:

max (2z₁+5z₂+6z₃+12z₄)

при ограничениях:z₁+2z₂+3z₃+4z₄ £ 11

z₁, z₂, z₃, z₄ ³ 0 и целые

где z₁,...,z₄ - количество пакетов типа А,...,Д, соответственно. Это модель целочисленного программирования поскольку переменные z₁-z₄ должны быть выбраны так, чтобы удовлетворить ограничения, т.е. на переменные накладываются связи. Последовательный процесс выбора переменных характерный для динамического программирования приведен в таблице 5.

	Стадия
выбранный тип продукта	Д	С	В	А
переменная	z4	z3	z2	z1
функция	f4(x)	f3(x)	f2(x)	f1(x)

Начало конец

Другими словами, сначала мы выбираем z₄, т. е. количество пакетов типа Д, затем z₃- количество пакетов типа С и т.д. Информация порожденная на стадии n содержится в функции f_n(x). В таблице 5 определены стадии, но нам нужно определить состояния, чтобы построить рекуррентное соотношение. Рассуждаем следующим образом.

Предположим, что уже выбраны z₄,z₃ и z₂.Что мы должны знать об этих решениях, чтобы выбрать z₁? Если мы ответим: "общую массу уже заложенную в рюкзак" или "оставшееся место", то значит мы готовы построить рекуррентное соотношение. Состояние в начале стадии n, будем обозначать как х, которое представляет общее количество продукта, которое еще можно положить в рюкзак.

Т.е. f_n (x) – максимальная полезность, если мы на стадии n и можем еще положить x кг.

Наша цель найти f₄(11), т.е. максимальную полезность когда мы можем выбирать из всех четырех типов продуктов и нам доступны для закладки все 11 кг.

Обозначим:w_i массу одного пакета используемого на стадии i, т.е. w₁ - масса пакета типа А. U₁- полезность одного пакета используемого на стадии i, т.е. U₁=2.

Необходимо придумать также систему учета ограничений на z_i.Предположим, например, что х=7 на стадии 3. Это означает, что мы хотим выбрать оптимальное значение для z₃- количества пакетов типа С. Т.к. масса пакета С - 3 кг (W₃=3), то мы можем взять 0,1 или 2 пакета(т.е. z₃=0,1 или 2). Большее количество превысит допустимую массу. Введем обозначение [x/w_n]- наибольшее целое меньшее или равное x/w_n.Поскольку здесь 7/3 = 2.33, то [x/w_n] = 2.Таким образом общий вид нашего рекуррентного соотношения для этой задачи имеет вид:

f_n(x) = max { u_n z_n + f_n-₁(x-w_n· z_n)}

z_n=0,1,..,[x_n/w_n]

В частности, когда n =4 и следовательно х= 11, то

f₄(11) = max {12z₄+f₃(11-4z₄)}

z₄=0,1,2

чтобы найти f₄(11) начнем с конца и найдем f₁(x),f₂(x) и f₃(x)

Шаг 1 На этом шаге мы должны решить сколько пакетов типа А мы можем положить в рюкзак в зависимости от еще пустого пространства. Т.к. масса пакета А-1 кг, то z₁*(x) = x, т.е. мы кладем один пакет типа А на каждый килограмм свободной массы. Т.к. каждый пакет типа А имеет полезность равную 2, то f₁(x)= 2x, {x=0,1,...,11}.

Шаг 2

Т.к.f₁(x) = 2x, то f₁(x-2z₂) = 2(x-2z₂) и f₂(x) = max {5z₂ + 2(x- 2z₂)} = max {2x+ z₂}

z₂=0,1...[x/2]

Ясно, что максимальное значение достигается при максимально возможном z₂, которое равно [x/2],т.е z₂*=[x/2] и f₂(x) = 2x + [x/2]

x

z2*(x)

f2(x)

Шаг 3 f₃(x) = max {6z₃ + f₂(x-3z₃)}

z=0,..,[x/3]

т.к. и

Значение в квадратных скобках тем больше, чем меньше z₃, т.е. для любого х, z₃*(x)=0 и

f₃(x) = 2x +[x/2], т.е. f₃(x) = f₂(x)

x

z3(x)

f3(x)

Шаг 4.Рекуррентное соотношение для стадии 4 мы уже сформулировали. Поскольку на этой стадии нам доступны все 11 кг емкости рюкзака, мы должны определить f₄(11) и у нашей таблицы будет одна строка.

		12z4 +	f3(11-4z4)
z4(x)				f4(11)	z4*(11)
	0+27=27	12+17=29	24+7=31