동적 프로그래밍의 경우 의사 결정. 좋아요, 수학은 아름답습니다. 모든 것이 주어지지 않는 작업은 어떻습니까? 계단 오르기
동적 프로그래밍
1. 동적 프로그래밍. 기본 개념............................2
2. 동적 프로그래밍 방식의 본질..................................................4
3. 동적 프로그래밍 방법을 이용한 문제 해결의 예..........................................................................7
사용된 소스 목록.......................................................11
1. 동적 프로그래밍. 기본 개념.
동적 프로그래밍(DP)컴퓨터 시스템 이론에서 복잡한 문제를 더 간단한 하위 작업으로 나누어 해결하는 방법입니다. 이는 복잡도가 원래 문제보다 약간 덜한 중첩 하위 문제 집합처럼 보이는 최적의 하위 구조 문제에 적용됩니다. 이 경우 "순진한" 방법에 비해 계산 시간을 크게 줄일 수 있습니다.
동적 프로그래밍의 핵심 아이디어는 매우 간단합니다. 일반적으로 주어진 문제를 해결하려면 문제의 개별 부분(하위 작업)을 해결한 다음 하위 작업에 대한 솔루션을 하나의 일반 솔루션으로 결합해야 합니다. 이러한 하위 작업 중 다수는 동일한 경우가 많습니다. 동적 프로그래밍 방식은 각 하위 문제를 한 번만 해결하여 계산 횟수를 줄이는 것입니다. 이는 반복되는 하위 작업 수가 기하급수적으로 많은 경우에 특히 유용합니다.
동적 프로그래밍은 특정 종류의 문제를 여러 부분으로 나누어 더 작고 덜 복잡한 문제를 해결하는 수학적 기술입니다. 동시에, 독특한 특징은 동적 프로그래밍이라는 용어의 출현을 결정하는 고정된 간격, 기간에 따라 단계적으로 문제를 해결한다는 것입니다. 동적 프로그래밍 방법은 시간 요소를 고려하지 않은 문제를 해결할 때도 성공적으로 사용된다는 점에 유의해야 합니다. 일반적으로 수학적 장치는 단계별 또는 단계별 프로그래밍으로 표현될 수 있습니다. 동적 프로그래밍 방법에 의한 문제 해결은 R. E. Bellman이 공식화한 최적성 원칙을 기반으로 수행됩니다. 최적의 동작은 시스템의 초기 상태와 초기 솔루션이 무엇이든 후속 솔루션이 최적의 동작을 결정해야 한다는 특성을 갖습니다. 초기 솔루션의 결과로 얻은 상태에 상대적입니다.
따라서 전체 프로세스가 완료되면 얻을 수 있는 전반적인 이점을 고려하여 각 단계의 계획을 수행해야 하며, 이를 통해 선택한 기준에 따라 최종 결과를 최적화할 수 있습니다.
따라서 넓은 의미의 동적 프로그래밍은 각 단계에서 제어되는 매개변수를 변경하여 프로세스의 진행에 영향을 미치고 각 단계에서 시스템 상태를 변경함으로써 프로세스를 최적으로 제어하는 것입니다.
일반적으로 동적 프로그래밍은 선형 및 비선형 문제를 모두 해결할 때 상업 활동에 사용할 수 있을 만큼 이해하기 쉽고 간단한 조화로운 이론입니다.
동적 프로그래밍은 최적 프로그래밍의 한 분야입니다. 의사결정 과정을 여러 단계(단계)로 나누는 작업에 적용되는 구체적인 방법과 기법이 특징입니다. 동적 프로그래밍 방법은 방정식 또는 부등식 시스템으로 표현되는 변수와 목적 함수 간의 특정 연결을 사용하여 주어진 최적성 기준으로 변형 최적화 문제를 해결하는 데 사용됩니다. 이 경우 선형 계획법으로 해결되는 문제와 마찬가지로 등식 또는 부등식의 형태로 제한이 주어질 수 있습니다. 그러나 선형 프로그래밍 문제에서 기준 함수와 변수 간의 종속성이 반드시 선형인 경우 동적 프로그래밍 문제에서는 이러한 종속성이 비선형일 수도 있습니다. 동적 프로그래밍은 프로세스나 시스템의 역학과 관련된 문제와 리소스 할당과 같은 정적 문제를 해결하는 데 모두 사용될 수 있습니다. 이는 제어 문제를 해결하기 위한 동적 프로그래밍의 범위를 크게 확장합니다. 그리고 옵션의 다음 단계로 이동할 때 조사되는 영역과 수를 제한함으로써 달성되는 솔루션 프로세스 단순화 가능성은 이러한 방법 세트의 장점을 증가시킵니다.
그러나 동적 프로그래밍에는 단점도 있습니다. 우선, 단일한 보편적인 해결 방법은 없습니다. 이 방법으로 해결되는 거의 모든 문제는 고유한 특성을 갖고 있으며 이를 해결하려면 가장 적절한 방법을 검색해야 합니다. 또한, 여러 상태의 다단계 문제를 해결하는 데 따른 대용량 및 복잡성으로 인해 저차원 문제를 선택하거나 압축된 정보를 사용해야 할 필요성이 발생합니다. 후자는 옵션을 분석하고 상태 목록을 처리하는 방법을 사용하여 달성됩니다.
연속시간 프로세스의 경우 동적 프로그래밍은 이산 솔루션 체계의 제한 버전으로 간주됩니다. 이 경우 얻은 결과는 L. S. Pontryagin 또는 Hamilton-Jacobi-Bellman의 최대 방법으로 얻은 결과와 거의 일치합니다.
동적 프로그래밍은 단계별 접근 방식을 통해 최적의 검색이 가능한 문제를 해결하는 데 사용됩니다. 예를 들어 새로운 사용 영역 간에 부족한 자본 투자를 분배합니다. 보충 시점과 보충 주문 규모를 설정하는 수요 또는 재고 관리 규칙 개발 제품 수요 변동 상황에서 생산 일정 조정 및 고용 균등화를 위한 원칙 개발; 장비의 현재 및 주요 수리 및 교체에 대한 일정 계획 작성 운송 네트워크에서 최단 거리를 검색합니다. 상업적 운영 등의 개발 순서 형성
동적 프로그래밍 방법의 본질.
동적 프로그래밍 방법은 다음을 기반으로 합니다. 최적성 원리, 미국 수학자 Richard Bellman은 1957년에 공식화했습니다. "최적의 행동은 최초의 초기 상태와 결정이 무엇이든 후속 결정은 첫 번째 결정의 결과인 상태와 관련하여 최적의 행동을 구성해야 한다는 특성을 가지고 있습니다."
최적성 원칙의 물리적 본질은 현재 솔루션 선택의 오류가 미래에 수정될 수 없다는 것입니다.
다음과 같은 일반적인 문제가 고려됩니다. 일부 프로세스가 발생하는 특정 물리적 시스템이 있습니다. N단계. 프로세스의 효율성은 일부 지표로 특징 지어집니다. 여라고 불리는 이기다. 총 이득을 보자 여모든 N프로세스 단계는 개별 단계의 이득으로 구성됩니다.
어디 내가- 승리 나-번째 단계. 만약에 여이 속성을 가지고 있습니다. 가산 기준.
문제의 프로세스는 제어된 프로세스입니다. 과정과 결과에 영향을 미치는 일부 매개변수를 선택할 수 있으며, 각 단계에서 일부 솔루션이 선택되며, 이에 따라 이 단계의 승리가 결정됩니다. 이 솔루션은 단계 제어. 모든 단계 제어 세트는 프로세스 전체의 제어를 나타냅니다. 문자로 나타내자 유, 및 단계 컨트롤 - 문자 포함. 그 다음에
일반적인 경우 단계 제어는 숫자가 아니지만 일반적으로 벡터, 함수 등입니다.
동적 프로그래밍 모델에서 각 단계의 프로세스는 다음 중 하나의 상태에 있습니다. 에스상태 집합 에스. 각 상태는 일부 단계 제어와 연관되어 있다고 믿어집니다. 이러한 통제는 프로세스의 이전 기록에 대해 주어진 상태에서 선택된 통제가 프로세스의 다음 상태를 완전히 결정하는 것과 같습니다. 일반적으로 두 가지 특별한 조건이 있습니다. 에스 0 - 초기 및 승- 최종.
따라서 각 상태에 허용 가능한 단계 제어 세트가 주어지고 각 단계 제어가 해당됩니다. 
- 프로세스가 시작되는 상태 나야?단계 제어를 사용한 결과 유. 프로세스를 초기 상태로 유지 에스 0 . 선택은 프로세스를 상태로 만듭니다 에스 1 = σ( 에스 0 ,유 1) 선택 - 진술 에스 2 = σ( 에스 1 ,유 2) 등 결과는 일련의 쌍으로 구성된 프로세스 궤적입니다.
최종 상태로 끝납니다. 일관성을 위해 하나의 상태만 포함되어 프로세스를 동일한 최종 상태로 유지한다고 가정할 수 있습니다. 허용 가능한 상태 및 통제 세트는 다음과 같습니다.
유한하고 우리를다양한 에스교차하지 마십시오.
일반적으로 동적 프로그래밍 문제는 다음과 같이 공식화됩니다. 이득(2.1)이 최대가 되는 프로세스 궤적을 찾습니다.
최대 이득을 달성하는 제어를 호출합니다. 최적의 제어. 일련의 단계 컨트롤로 구성됩니다.
이 컨트롤로 얻을 수 있는 최대 게인은 다음과 같이 표시됩니다. W최대:
W최대= 최대 유{여(유)}. (2.5)
배낭 문제의 예를 사용하여 단계, 상태, 제어 및 보상이 무엇을 의미하는지 생각해 보겠습니다.
배낭을 싣는 것은 다음으로 구성된 과정으로 생각할 수 있습니다. N단계. 각 단계에서 다음 질문에 답해야 합니다. 이 물건을 배낭에 넣어야 할까요, 말아야 할까요? 따라서 프로세스 단계는 변수에 할당됩니다. x 나는값은 1 또는 0입니다.
이제 상태를 정의해 보겠습니다. 분명히 프로세스의 현재 상태는 배낭의 잔여 운반 능력, 즉 배낭이 완전히 수납될 때까지 우리가 처분할 수 있는 무게로 특징지어집니다. 그러므로 이전 상태에서는 나-단계는 수량으로 이해됩니다.
(2.6)
여기서 에스 0은 값이 해당하는 초기 상태입니다. 비- 배낭의 초기 운반 능력.
관리 대상 나-번째 단계는 이진 변수에 대한 할당을 의미합니다. x 나는값은 0 또는 1입니다. 이는 각 단계마다 두 개의 컨트롤만 있음을 의미합니다. 또한, 통제의 허용 가능성 너 나, 확립 x 나는= 1, 조건에 따라 결정됨
(2.8)
스텝 게인은 다음과 같이 정의할 수 있습니다. 그렇기 때문에
(2.10)
게인값(2.10)이 최대가 되는 최적의 제어를 찾는 것이 필요하다.
3. 동적 프로그래밍 방법을 사용하여 문제를 해결하는 예입니다.
운동. 투자자는 5,000den의 금액으로 자금을 할당합니다. 세 기업 사이에 배포되어야 하는 단위입니다.
Bellman 최적성 원칙을 사용하여 각 기업이 x,000에 투자할 경우 최대 총 이익을 제공하는 기업 간 투자 분배 계획을 수립해야 합니다. 단위 p;(x)천 이익을 가져옵니다. 단위 (i=1, 2 및 3) 다음 데이터에 따르면:
해결책. 문제의 수학적 모델을 만들어 보겠습니다.
1. 단계 수는 3입니다.
2. 특정 단계 이전에 사용 가능한 자금의 양과 각 단계의 시스템 상태를 특성화합시다.
3. i번째 단계(i=1,2,3)에서 x i를 선택합니다 - i번째 기업에 투자된 자금의 양.
4. i번째 단계의 이익 p i (xi)는 i번째 기업이 자금 xi를 투자하여 가져오는 이익입니다. 전체적으로 승리하여 총 이익 W를 표시하면 W=p 1 (x 1)+ p 2 (x 2)+ p 3 (x 3)입니다.
5. 천만덴의 자금이 있는 경우 단위 그리고 i번째 기업에 x천의 돈이 투자되었습니다. 단위를 초과하면 추가 투자를 위해 (s-x) 천 달러가 남습니다. 단위 따라서 i번째 단계에서 시스템이 상태 s에 있고 컨트롤 x가 선택되었다면 (i+1)번째 단계에서 시스템은 상태 (s-x)에 있게 됩니다. 새로운 상태는 f i (s, x) = s-x 형식을 갖습니다.
6. 마지막 (i=3) 단계에서 최적의 통제는 사용 가능한 자금의 양에 해당하며 이득은 마지막 기업이 가져온 수입과 같습니다: x 3(s) = s, W 3(s) = p 3 (들).
7. 벨만의 최적성 원리에 따르면, 각 단계의 제어는 이 단계의 보수를 포함하여 프로세스가 끝날 때까지 남은 모든 단계의 보수의 합이 최적이 되도록 선택해야 합니다. 주요 기능 방정식은 다음과 같은 형식을 취합니다.
W 2 (s) = 최대( 피 2(x) + W 3 (s -엑스))
표를 작성할 결과를 바탕으로 단계별 최적화를 수행해 보겠습니다.
| 에스 | 나는=3 | 나는=2 | 나는=1 | |||
| x 3(들) | W3(들) | x 2(들) | W2(들) | xi(들) | 나는 (들) | |
| 4,27 | 4,27 | |||||
| 7,64 | 7,64 | |||||
| 10,25 | 10,97 | |||||
| 15,93 | 15,93 | |||||
| 16,12 | 19,26 | 19,26 |
표의 첫 번째 열에는 시스템의 가능한 상태가 기록되어 있으며, 맨 윗줄에는 마지막 단계부터 시작하여 각 단계에서 최적의 제어 및 보수를 갖는 단계 수가 포함되어 있습니다. 마지막 단계 i=3의 경우 함수 방정식의 형식은 x 3 (s)=s, W3(s)=p3(s)이므로 i=3에 해당하는 테이블의 두 열은 다음과 같이 자동으로 채워집니다. 소스 데이터 테이블.
단계 i=2에서 주요 함수 방정식은 다음과 같은 형식을 갖습니다.
W 2 (s) = max(p 2 (x) + W 3 (s - x))
따라서 이 단계에서 최적화를 수행하기 위해 i=3 단계에서 다양한 상태 s에 대한 테이블을 채웁니다.
| 에스 | 엑스 | sx | p2(x) | W3(s-x) | p2(x)+W3(s-x) | W2(들) |
| 4,27 | 4,27 | 4,27 | ||||
| 3,33 | 3,33 | |||||
| 7,64 | 7,64 | 7,64 | ||||
| 3,33 | 4,27 | 7,6 | ||||
| 4,87 | 4,87 | |||||
| 10,25 | 10,25 | 10,97 | ||||
| 3,33 | 7,64 | 10,97 | ||||
| 4,87 | 4,27 | 9,14 | ||||
| 5,26 | 5,26 | |||||
| 15,93 | 15,93 | 15,93 | ||||
| 3,33 | 10,25 | 13,58 | ||||
| 4,87 | 7,64 | 12,51 | ||||
| 5,26 | 4,27 | 9,53 | ||||
| 7,34 | 7,34 | |||||
| 16,12 | 16,12 | 19,26 | ||||
| 3,33 | 15,93 | 19,26 | ||||
| 4,87 | 10,25 | 15,12 | ||||
| 5,26 | 7,64 | 12,9 | ||||
| 7,34 | 4,27 | 11,61 | ||||
| 9,49 | 9,49 |
단계 i=1에서 주요 함수 방정식은 다음과 같은 형식을 갖습니다.
W x (s) = 최대( p x (x) + W 2 (s - x))
첫 번째 단계 이전의 시스템 상태는 s=5이므로 이 단계에서 최적화를 수행하기 위해 표를 작성하겠습니다.
| 에스 | 엑스 | sx | 파이(x) | W2(s-x) | 파이(x)+W2(s-x) | Wi(들) |
| 19,26 | 19,26 | 19,26 | ||||
| 3,22 | 15,93 | 19,15 | ||||
| 3,57 | 10,97 | 14,54 | ||||
| 4,12 | 7,64 | 11,76 | ||||
| 4,27 | 8,27 | |||||
| 4,85 | 4,85 |
최고 당첨값은 19.26임을 알 수 있다. 이 경우 첫 번째 단계에서 최적 제어는 x 1 (s 1)=0 (s 1 =5), 두 번째 단계에서 x 2 (s 2) =1 (s 2 =s 1 -x 1 =5) 입니다. ) 그리고 세 번째 단계에서는 x 3 (s 3) =4 (s 3 =s 2 -x 2 =4)입니다.
이는 (0, 1, 4)가 기업 간 투자 배분을 위한 최적의 계획임을 의미한다.
따라서 19.26천의 가장 큰 총 이익을 얻습니다. 단위에는 1,000den을 투자해야 합니다. 단위 두 번째 기업과 4,000개의 굴로. 단위 제3의 기업에.
사용된 소스 목록
1. Bellman R., 동적 프로그래밍, trans. 영어에서, M., 1960
2. Boltyansky V.G., 최적 제어의 수학적 방법, M., 1966
동적 프로그래밍(DYNAMIC PROGRAMMING)은 다단계 문제를 해결하는 이론과 방법을 다루는 최적 제어 섹션입니다. 최적 제어 문제에서는 가능한 제어 중에서 소위 목적 함수(프로세스의 일부 수치적 특성)의 극한(최소 또는 최대) 값을 달성하는 것이 추구됩니다. 동적 프로그래밍에서 다단계는 다단계 프로세스 구조 또는 제어가 일반적으로 서로 다른 시점에 해당하는 여러 연속 단계(단계)로 분할된다는 사실로 이해됩니다. 때때로 다단계 성격은 프로세스의 본질에서 비롯되지만 동적 프로그래밍 방법을 사용할 가능성을 보장하기 위해 인위적으로 도입될 수도 있습니다. 동적 프로그래밍에서 프로그래밍은 의사결정(계획)을 의미하며, "동적"이라는 단어는 시간의 필수적인 역할과 작업 순서를 나타냅니다. 동적 프로그래밍 방법은 운영 연구에 사용되는 방법의 필수적인 부분이며 최적 계획 문제(예: 최적 자원 할당 문제, 재고 관리 이론, 장비 교체 문제)와 많은 기술 문제(예: 예를 들어, 최적의 도로 배치 문제에서 순차적 화학 공정의 제어 문제).
일부 시스템 X를 관리하는 프로세스가 m개의 단계(단계)로 구성되어 있다고 가정합니다. i번째 단계에서 제어 y i는 시스템을 (i - 1)번째 단계 이후의 상태 x i-1에서 새로운 상태 x i로 전환합니다. 이 경우 함수 f i (x, y)가 주어지고 x i-1, y i 값에 의해 이 함수로부터 새로운 상태가 결정되므로 x i = fi (x i-1, y i), i = 1, 2,..., m. 따라서 제어 y 1, y 2, ..., y m은 시스템을 초기 상태 x 0 ∈ X 0에서 최종 상태 x m ∈ X m으로 전환합니다. 여기서 X 0 및 X m은 다음의 허용 가능한 초기 및 최종 상태 세트입니다. 시스템 X.
동적 프로그래밍 문제의 가능한 공식화 중 하나는 다음과 같습니다. 초기 상태 x 0이 주어지면 시스템 X가 허용 가능한 최종 상태가 되고 동시에 주어진 목적 함수 F(x)가 되도록 컨트롤 y 1, y 2, ..., y m을 선택해야 합니다. 0, y 1, x 1,.., y m, x m)이 최대값 F*에 도달했습니다. 즉,
여기서 최대값은 모든 컨트롤 y 1, ..., y m에 적용되며 x m ∈ X m입니다.
동적 프로그래밍에서는 일반적으로 목적 함수가 가법적이라고 가정합니다. 고려된 예에서 이는 다음을 의미합니다.
또한 동적 프로그래밍에서는 문제에 여파가 없다고 가정합니다. 즉, 단계 i에서 이루어진 결정(제어)은 시간 i의 시스템 상태 x i에만 영향을 미칩니다. 위에서 언급한 제한 조건은 모두 약화될 수 있지만 방법이 상당히 복잡해집니다.
동적 프로그래밍은 R. Bellman이 공식화한 최적성 원칙을 기반으로 합니다. 일부 컨트롤 y 1, y 2, ..., y k를 선택하면 궤도 x 0, x 1, ..., x k 상태가 되며 프로세스를 완료해야 합니다(예: y k+1, ). .., y m (따라서 x k+1 , ..., x m).
프로세스의 마지막 부분이 최대 기능 달성 측면에서 최적이 아닌 경우
그러면 전체 프로세스가 최적이 아닐 것입니다. Bellman의 최적성 원리를 사용하면 다음과 같은 동적 프로그래밍의 기본 함수 관계를 얻을 수 있습니다. Ωm(x) = 0이라고 하면,
k = 1, 2, ..., m, 여기서 최대값은 k 단계에서 허용되는 모든 제어 y에 적용됩니다. Ω k에 대한 Ω k-1의 의존성을 결정하는 관계를 벨만 방정식이라고 합니다. 이러한 함수의 의미는 매우 명확합니다. 단계 k-1의 시스템이 상태 x에 있으면 Ω k-1(x)는 함수 F k의 가능한 최대 값입니다. 함수 Ω k-1 (x)의 구성과 동시에 조건부 최적 제어 y k (x)가 각 단계에서 발견됩니다. 즉, 시스템의 상태 x에 대해 가능한 모든 가정에서 최적 제어 값이 발견됩니다. k-1 단계. 최종 최적 제어는 양 Ω 0 (x 0) = F*, y 1, x 1, y 2, ..., y m, x m을 순차적으로 계산하여 찾습니다.
동적 프로그래밍의 도움으로 특정 x 0에 대해 하나의 특정 문제가 해결되지 않지만 모든 초기 상태에 대해 동일한 유형의 모든 유사한 문제가 한 번에 해결됩니다. 동적 프로그래밍의 수치적 구현은 많은 양의 정보를 기억해야 하기 때문에 매우 복잡하므로 일반적인 문제(예: 항공기의 최적 비행 모드 결정)를 반복적으로 해결해야 하는 경우 동적 프로그래밍을 사용하는 것이 좋습니다. 날씨 변화에 따라). 일반적으로 동적 프로그래밍 문제는 이산 프로세스에 대해 공식화되지만 경우에 따라 동적 프로그래밍은 연속 매개변수를 사용하여 동적 문제를 해결하는 데에도 사용됩니다.
동적 프로그래밍은 변형 계산의 많은 문제에 대한 새로운 접근 방식을 제공했습니다. 동적 프로그래밍의 중요한 부분은 확률론적 동적 프로그래밍 문제, 즉 시스템 상태와 대상 함수가 무작위 요인의 영향을 받는 문제로 구성됩니다.
동적 프로그래밍에 대한 엄격한 정당화는 L. S. Pontryagin과 그의 학생들이 제어된 프로세스의 수학적 이론에 대해 수행한 결과에서 나옵니다.
문학: Bellman R. 동적 프로그래밍. 엠., 1960; 최적 프로세스의 수학적 이론. 엠., 1961; Howard R. A. 동적 프로그래밍 및 Markov 프로세스. 엠., 1964; Hedley J. 비선형 및 동적 프로그래밍. 엠., 1967; Hedley J., Whitin T. 재고 관리 시스템 분석. 엠., 1969.
동적 프로그래밍 섹션은 다음 계산기로 표시됩니다.
- 투자배분 문제. 4개 기업의 생산 재건 및 현대화를 위해 자금이 C = 80 den으로 할당되었습니다. 단위 각 기업에 대해 할당량에 따라 생산량 증가 가능성이 f i (x) (i = 1, 4)로 알려져 있습니다.
동적 프로그래밍 문제에서 경제적인 프로세스는 시간(또는 여러 기간)에 따라 달라지므로 전체 프로세스의 최적 개발을 보장하는 여러 가지 최적의 솔루션(각 단계마다 순차적으로)이 발견됩니다. 동적 프로그래밍은 제어된 프로세스와 시간 종속 프로세스를 최적으로 계획할 수 있는 수학적 장치입니다. 최적화를 단계별로 수행하는 것을 다단계 의사결정 프로세스라고 합니다. 개발 과정에 영향을 미칠 수 있는 경우 경제 프로세스를 통제라고 합니다.
DP(동적 프로그래밍) 방법은 순차 최적화 원칙을 기반으로 합니다. 즉, 원래의 고차원 최적화 문제에 대한 솔루션이 일련의 작은 차원 최적화 문제에 대한 솔루션으로 대체됩니다. DP 방법을 적용하기 위한 주요 조건은 의사 결정 프로세스를 여러 유사한 단계 또는 단계로 나눌 수 있다는 것입니다. 각 단계는 별도로 계획되지만 다른 단계에서 얻은 결과를 고려합니다. 예를 들어, 몇 년 동안의 산업 활동이나 장비 제어에 사용되는 일련의 테스트 등이 있습니다. 일부 프로세스(작업)는 자연스럽게 여러 단계로 구분되지만, 다음과 같이 나누어야 하는 작업도 있습니다. 예를 들어 목표물에 미사일을 유도하는 과정과 같이 인위적으로 단계를 밟습니다.
이 원칙은 모든 단계에서 선택된 제어가 국부적으로 최고가 아니라 프로세스 전체의 관점에서 최고임을 보장합니다. 왜냐하면 이 제어는 다음 단계의 결과를 고려하여 선택되기 때문입니다.
고려해 봅시다 동적 프로그래밍 문제에 대한 일반적인 설명.
다단계 의사결정 과정을 다음과 같이 나누어 보자. N단계. 시스템의 초기 상태를 ε 0으로 표시하고, ε 1, ε 2, … ε로 표시하겠습니다. N– 첫 번째, 두 번째 이후의 시스템 상태 N-번째 단계. 일반적으로 국가는
ε 케이– 벡터(ε 케이 1 , …, ε k 초).
관리다단계 프로세스에서는 일련의 솔루션(제어 변수)이 호출됩니다. 너 = (너 1 , ..., 너 너) 모든 단계에서 촬영 케이상태 ε에서 시스템을 전송합니다. 케이-1 = (ε 케이- 1 1 , …, ε 케이 -1 에스) 상태 ε 케이 = (ε 케이 1 , …, ε k 초).
경제 과정에서 관리는 각 단계의 자금 분배 및 재분배로 구성됩니다. 예를 들어, 모든 기업의 제품 생산은 장비 구성, 원자재 공급량, 자금 조달 금액 등의 변경에 따라 결정되기 때문에 통제된 프로세스입니다. 처음에 내린 일련의 결정 연간 기획기간, 기업에 원자재 공급, 장비 교체, 자금조달 금액 등을 관리한다. 최대 생산량을 얻으려면 가장 쉬운 방법은 가능한 최대 자금을 투자하고 장비를 최대 용량으로 사용하는 것 같습니다. 그러나 이로 인해 장비가 빠르게 마모되고 결과적으로 생산량이 감소하게 됩니다. 따라서 제품 출시는 바람직하지 않은 영향을 방지하는 방식으로 계획되어야 합니다. 장비가 마모되면, 즉 일정 기간에 걸쳐 장비를 보충할 수 있는 조치를 취하는 것이 필요합니다. 후자는 초기 생산량 감소로 이어지지만 향후 생산량 확대 가능성을 제공한다. 따라서 경제적인 생산 과정은 여러 단계(단계)로 구성되며 각 단계는 그 발전에 영향을 미치는 것으로 간주할 수 있습니다.
통제된 프로세스의 단계(단계)의 시작은 결정이 내려지는 순간(자본 투자 금액, 특정 유형의 장비 교체 등에 대한)으로 간주됩니다. 단계는 일반적으로 사업 연도로 이해됩니다.
일반적으로 모든 단계에서 제어됩니다. 너일부 제한 사항이 적용됩니다. 이러한 제한 사항을 충족하는 컨트롤을 호출합니다. 허용됩니다.
성과지표라고 가정하면 케이프로세스의 세 번째 단계는 이 단계의 초기 상태에 따라 달라집니다. 케이-1 및 이 단계의 제어에서 너, 우리는 전체 다단계 프로세스의 목적 함수를 다음 형식으로 얻습니다. 
.
이제 동적 프로그래밍 문제를 공식화해 보겠습니다.: “허용 가능한 통제 세트를 결정합니다( 유 1 , …, 너), 시스템을 초기 상태 ε 0에서 최종 상태 ε으로 전환 N효율성 지표를 최대화하거나 최소화합니다. 에프».
기능의 최대(최소)를 달성하는 제어 에프~라고 불리는 최적의 제어 유 * = (유 1* ,…, 너 *).
통제변수인 경우 너이산 값을 취하면 DP 모델이 호출됩니다. 이산적인. 만약 변수 너지속적으로 변경되면 DP 모델이 호출됩니다. 마디 없는.
상태 매개변수의 수에 따라 에스및 제어 변수의 수 아르 자형구별 짓다 1차원적인그리고 다차원 DP 작업.
작업의 단계 수는 다음과 같습니다. 결정적인또는 끝없는.
응용 동적 프로그래밍 문제
- 시설 건설 계획의 문제.
이 수업에서는 동적 프로그래밍의 개념과 그 출현의 역사적 측면을 검토합니다. 동적 프로그래밍 문제와 그 해결 방법의 몇 가지 예를 고려합니다.
"동적 프로그래밍"의 개념은 1940년대 Richard Bellman이 한 문제에 대한 답을 "이전의" 다른 문제를 해결한 후에만 얻을 수 있는 문제에 대한 해결책을 찾는 과정을 설명하기 위해 처음 사용했습니다.
따라서 미국의 수학자이자 수학과 컴퓨터 기술 분야의 선도적인 전문가 중 한 명인 그는 - 리처드 에른스트 벨만- 동적 프로그래밍의 아버지가 되었습니다.
나중에 이 개념의 공식화는 Bellman 자신에 의해 현대적인 형태로 개선되고 개선되었습니다.
프로그래밍이라는 단어는"동적 프로그래밍"의 맥락에서 실제로는 프로그래밍에 대한 고전적인 이해(프로그래밍 언어로 코드 작성)를 의미합니다. 그것과 사실상 아무 관련이 없습니다. "프로그래밍"이라는 단어는 "최적화"라는 단어와 동의어인 "수학적 프로그래밍"이라는 문구와 동일한 의미를 갖습니다.
그렇기 때문에 프로그램들문제에 대한 해결책을 얻기 위한 최적의 작업 순서로 사용됩니다.
일반적으로 시작하려면, 동적 프로그래밍의 비공식적 정의다음과 같이 들릴 수도 있습니다:
동적 프로그래밍조합론, 최적화 및 특정 속성(하위 작업에 대한 공동 최적 속성)이 있는 기타 문제의 일부 문제를 해결할 수 있는 기술 또는 방법입니다.
최적화 문제, 일반적으로 하나 또는 다른 목적 함수를 최대화하거나 최소화하는 작업과 관련됩니다(예: 시스템이 중단되지 않을 확률 최대화, 예상 이익 최대화 등).
조합 문제, 일반적으로 특정 속성을 갖는 개체가 몇 개 있는지 또는 속성을 제공하는 조합 개체가 몇 개 있는지에 대한 질문에 대답합니다.
즉, DP는 모든 문제를 해결하는 것이 아니라 특정 하위 작업 클래스의 일부만 해결합니다. 그러나 이 하위 작업 클래스는 프로그래밍, 수학, 언어학, 통계, 게임 이론, 경제학, 컴퓨터 과학 등 다양한 지식 분야에서 사용됩니다.
동적 프로그래밍을 사용하여 문제를 해결하려면 다음이 필요합니다. 공최적의 성질에 대해서는 이후 강의에서 논의할 것입니다.
하위 문제의 최적성 속성에 대한 비공식적 설명은 다이어그램을 사용하여 설명할 수 있습니다.
DP를 사용하여 해결하고 싶은 문제가 있습니다. 문제를 해결할 계획을 찾아보세요. 이 문제가 복잡해서 당장 해결할 수 없다고 가정해 보겠습니다. 작은 하위 문제를 가져와 먼저 해결합니다(x1의 경우). 그런 다음 이 작은 솔루션 x1을 사용하고 이 솔루션의 구조를 변경하지 않고 x1과 x2의 다음 문제를 해결합니다. 등.
쌀. 1.1. 하위 문제의 최적 속성에 대한 비공식적 설명
비공식적인 설명이 더 자세히 논의됩니다.
동적 프로그래밍을 사용하여 해결된 문제의 예
먼저 최적화 문제(작업 1-5)를 고려하세요.
- 최적 길이의 경로
- 기계 교체(비용 최소화)
- 포트폴리오 교환
- 최적 생산(물류)을 위한 계획 수립
- 게임(확률적 또는 비확률적)
- 그래프와 트리
- 코인 교환 문제 또는 거스름돈 반환 방법의 수
예:그래프 형태로 제시된 로드맵이 있습니다. 우리의 목표: 요점에서 벗어나는 것 ㅏ가리키다 비. 이는 거리나 소비되는 연료를 최소화하는 방식으로 수행되어야 합니다.
목적 함수여기서 거리는 ㅏ~ 전에 비. 저것들. 우리의 목표는 거리를 최소화하는 것입니다.
그리고 무엇입니까? 선택 변수? 최단 경로를 찾기 위해서는 매번 결정을 내려야 합니다. 저것들. 각 지점이나 교차로에서 어디로 방향을 틀지, 직진할지 결정을 내려야 합니다.
중요한:이 문제에서 동적 프로그래밍을 사용하여 해결된 문제의 일반적인 구조를 이미 볼 수 있습니다. 각 문제에는 목적 함수와 선택 변수가 있습니다..
예:우리는 매년 낡은 차를 1년 더 운전하고 낡은 차에 대한 유지 관리 비용을 부담할지, 아니면 차를 팔고 새 차를 구입할지(구매 비용도 부담할지) 결정을 내립니다.
목적 함수:비용 최소화(오래된 자동차를 유지 관리하거나 새 자동차를 구입하는 데 드는 비용).
선택 변수:매년 자동차를 판매할지 아니면 보유할지 결정을 내려야 합니다.
예:증권 거래소에서 플레이하고 모든 회사의 주식을 구매합니다.
목적 함수:극대화 평균소득이 있기 때문에 증권 거래소에서 수입은 확률적으로 획득됩니다. 그것은 확률적인 통계적 과정입니다.
선택 변수:어떤 종류의 투자 포트폴리오가 있을 것인가: 주식 수와 매수해야 할 회사.
예:가구를 만드는 공장이 있어요. 공장은 해당 수량의 특정 가구(의자, 테이블, 캐비닛 등)를 생산할 수 있는 특정 수의 근로자를 고용합니다.
목적 함수: 이익 극대화.
선택 변수:충분한 노동력을 갖기 위해 몇 개의 의자나 테이블을 만들어야 하는지 선택합니다.
예:다양한 게임 참여
목적 함수:승리 확률을 최대화하거나 평균 승리를 최대화하는 등
여기서 선택 변수는 특정 게임에 따라 다릅니다.
문제 1~5는 최적화 문제의 예입니다.
조합론:
예:임무는 특정 수의 잎을 가진 나무가 몇 개인지 결정하는 것입니다. 또는 그러한 작업을 해결하기 위해 얼마나 많은 그래프가 존재하는지 등.
예:다양한 명칭의 동전이 있는데, 어떤 방법으로 거스름돈을 돌려줄 수 있나요?
이것은 나중에 자세히 논의할 동적 프로그래밍 문제에 대한 간략한 설명입니다.
동적 프로그래밍의 개념
DP 하위 문제의 최적성에 대한 비공식적 설명입니다.
고려해 봅시다 비공식 DP 아이디어.
이제 가구 제조 공장의 예를 들어보겠습니다.
을 위한 이익 극대화 목표를 달성하려면 다음과 같은 많은 하위 작업을 해결해야 합니다.
- 생산할 의자 수 - 변수 X1,
- 생성할 테이블 수 - 변수 X2,
- 고용할 근로자 수 - 변수 X3,
- ... Xn.
하위 문제가 너무 많아서 이러한 문제를 해결하는 방법을 이해하기가 어렵습니다. 대개, 하나의 작은 문제를 해결하는 것이 큰 문제를 해결하는 것보다 쉽습니다.작은 것들로 구성되어 있습니다.
이에 DP는 다음과 같이 제안한다.
- 변수 X1을 사용하여 하나의 하위 작업을 수행하고 지금은 나머지 하위 작업을 잊어버립니다.
- 첫 번째 하위 작업에 대한 최적의 솔루션을 찾은 후 두 변수 X1 및 X2에 대한 하위 작업을 가져와서 해결합니다. 첫 번째 하위 작업에 대해 이미 찾은 솔루션을 사용합니다..
- 변수 X1과 X2가 나타나는 더 큰 하위 작업에 대한 솔루션을 얻습니다. 그런 다음 얻은 솔루션을 사용하여 X1, X2 및 X3을 다루는 하위 작업을 수행합니다.
- 그래서 우리는 전체 일반적인 문제에 대한 해결책을 얻을 때까지 계속합니다.
예를 들어, 한 공장에서는 의자만 생산합니다. 이사는 의자 판매를 통해 최대 이익을 얻는 임무를 맡고 있습니다.
DP의 공식적인 아이디어
종종 문제가 발생할 때 겉보기에 최적인 해결책은 다음과 같습니다. 가능한 모든 옵션을 시도. 그러나 이러한 옵션이 너무 많아 결과적으로 컴퓨터 메모리에 과부하가 걸리기 때문에 이 방법이 항상 허용되는 것은 아닙니다.
또한 다음과 같은 질문이 발생할 수 있습니다. 예를 들어 최소값이나 최대값을 찾으려면 도함수를 찾지 않는 이유는 무엇입니까? 아니면 La Grange 집합이나 다른 수학적 분석 방법을 사용하지 않겠습니까? 많은 자금을 보유하고 있는데 DP가 필요한 이유는 무엇입니까?
사실은 다음과 같습니다.
동적 프로그래밍은 주어진 문제를 별도의 부분(하위 작업, 단계)으로 나누고 이러한 하위 작업을 해결한 다음 이러한 솔루션을 하나의 공통 솔루션으로 결합하여 문제를 해결한다는 아이디어를 기반으로 합니다. 대부분의 하위 작업은 정확히 동일합니다.
더 복잡한 문제를 해결할 때 작은 하위 문제를 다시 해결하지 않고 이 하위 문제에 대해 이미 해결된 답을 사용하는 것이 중요합니다.
그래프로 보면 다음과 같습니다. 
중요한:이러한 이유로 작업을 하위 작업과 이러한 하위 문제를 한 번만 해결하세요(!), 전체 계산 수를 줄입니다. 이는 동적 프로그래밍에 내재된 보다 최적의 방법입니다.
도함수, 라그랑주 집합 등의 문제를 풀 때 연속함수를 사용하여 작업합니다. DP 문제를 풀 때 주로 이산 함수를 사용하여 작업하므로 여기서 연속 함수 사용에 대해 이야기하는 것은 부적절합니다.
이러한 이유로, 전부는 아니지만 많은 문제에서 수학적 분석을 사용하는 것은 허용되지 않습니다.
DP를 사용하여 문제를 해결하는 간단한 예
동적 프로그래밍을 사용하여 문제를 해결하는 옵션을 고려해 보겠습니다.
예: n 숫자의 합을 계산해야 합니다: 1 + 2 + 3 + ... + n
이 문제의 예상되는 "난이도"는 무엇입니까? 즉, 한 번에 많은 수의 숫자를 가져와 답을 얻어야 한다는 것입니다.
DP 아이디어를 문제에 적용하고 간단한 하위 작업으로 나누어 해결해 보겠습니다.
(DP에서는 항상 초기 조건이나 조건을 먼저 결정하는 것이 필요합니다)
- 첫 번째 요소의 합부터 시작하겠습니다. 첫 번째 요소를 선택하세요.
F(1) = 1 - 이제 첫 번째 요소에 대한 솔루션을 사용하여 문제를 해결합니다.
F(2) = F(1) + 2 = 1 + 2 = 3, 즉 첫 번째 요소의 합을 취하고 두 번째 요소를 추가해야 합니다. - F(3) = F(2) + 3 = 6
- 계속해서 유추하여 목적 함수를 얻습니다.
F(n) = F(n-1) + An
그래서 우리는 순서를 결정하고 하위 작업을 식별한 다음 이전 작업에 대한 솔루션을 기반으로 각 작업을 해결했습니다.
DP가 여전히 (인위적으로) 부당하게 사용되는 간단한 예는 DP 아이디어의 원리를 보여줍니다.
또 다른 예를 살펴보겠습니다.
예: n개의 계단이 있는데 앞에 사람이 있고 뒤에 사람이 있다 1
단계는 다음 단계로 올라갈 수도 있고 한 단계를 뛰어넘을 수도 있습니다. 질문: 그가 마지막 단계에 도달할 수 있는 방법은 몇 가지입니까? 
해결책:
가장 간단한 옵션(하위 작업)을 고려해 보겠습니다.
i 단계의 예를 살펴보겠습니다.
i 단계에 어떻게 도달할 수 있나요?
- i-1 단계에서 i-1 방식으로 i-1 단계에 도달할 수 있습니다.
- i-2 단계에서 i-2 방식으로 i-2 단계에 도달할 수 있습니다.
예를 들어, 가는 방법 4단계:
저것., 총 방법 수 i 단계로 이동:
f(ai) = f(ai-1) + f(ai-2)
초기값을 결정해보자, 문제 해결을 시작합니다.
1로 시작하면 공식은 피보나치 수열을 찾는 것과 같습니다.
우리는 문제가 본질적으로 조합적(즉, 어떤 일을 수행하는 방법의 수)이라는 것을 일부 반복 시퀀스를 계산하는 것으로 축소했다는 것을 알 수 있습니다.
연습 1:재귀를 사용하여 처음 10개 단계(기본적으로 피보나치 수열의 처음 10개 숫자)에 대한 예제를 구현합니다.
코드를 완성하세요:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | var c: 정수 ; 절차 getKolSposob(i, n: 정수) ; writeln 시작(i+ n, " " ) ; Inc(c); if ... then getKolSposob(...,... ) end ; 시작 c: = 1 ; getKolSposob(0 , 1 ) ; 끝. |
var c:정수; 절차 getKolSposob(i,n: 정수); writeln(i+n," ")을 시작합니다. Inc(c); if ... then getKolSposob(...,...) end; 시작 c:=1; getKolSposob(0,1); 끝.
작업 2:
15번째 유형의 통합 상태 시험 작업 솔루션(그래프. 경로 수 찾기)