온라인 리소스의 최적 할당. 동적 프로그래밍 방법을 이용한 최적의 자원 할당. 가장 긴 공통 부분 수열 문제: 두 수열이 주어졌을 때 가장 긴 공통 부분 수열을 찾는 문제

14.03.2019

스케줄링 이론의 "참조" 문제는 가장 단순한 상황(변형)에 대한 주요 분석 결과를 얻은 S.M. Johnson의 이름을 딴 존슨 문제로 문헌에 알려진 생산 라인 스케줄링 문제입니다. 이 문제의 특정 공식은 다음과 같습니다. .

계산적 관점에서 스케줄링 이론의 문제는 매우 복잡합니다. 발생하는 어려움을 이해하고 가능한 일반적인 접근 방식을 설명하려면 먼저 가장 간단한 문제 중 일부를 고려하는 것이 바람직하며 동시에 실용적인 의미도 있습니다.

8.1.1 결정론적 순서 문제에 대한 설명

건설 및 연구 수학적 모델

가장 단순한 공식화 된 상황과 수학적 모델을 고려하는 것부터 시작하여 스케줄링 이론의 실제 실제 문제를 해결하는 특징을 점차적으로 고려해 보겠습니다.

우리는 생산 라인의 스케줄링 문제(존슨의 문제)를 해결하는 예를 사용하여 스케줄링 이론의 문제의 복잡성을 보여줄 것입니다.

Johnson 문제의 전통적인 공식화는 다음과 같습니다. 부품(제품) 처리 순서를 선택하고, 생산 라인 운영 일정을 작성(작성)하여 전체 작업을 완료하는 데 필요한 최소 총 시간을 보장해야 합니다. 즉, 최소 시간 내에 그룹을 처리합니다. 티부품은 각각 순차적으로 처리되어야 합니다. 피생산 라인을 형성하는 기계. 주어진 것으로 가정 티 ij- 처리 시간 나세부정보( 나= 1,…, 중) 에 제이-번째 머신( 제이=1,…,N).

작업의 주요 제한 사항은 다음과 같습니다.

1) 한 기계에서 다른 기계로(한 기술 작업에서 다른 기술 작업으로) 부품을 전환(이전)하는 시간은 중요하지 않으며 무시할 수 있습니다.

2) 각 부품은 엄격하게 정의된 기술 순서에 따라 처리됩니다.

3) 각 서비스(각 기계의 각 부품 처리)는 해당 기계(유지 관리에 필요함)가 여전히 이전 부품을 처리 중일 때까지, 즉 공급 대기열의 이전 부품에 대한 기술적 작업을 수행 중일 때까지 시작할 수 없습니다. (처리 시작) ;

4) 각 서비스(각 기계의 각 부품 처리)는 다음 서비스(해당 부품 처리 - 생산 라인의 다음 기계에서 기술 작업 수행)가 시작되기 전에 완전히 완료되어야 합니다. 각 노동 대상의 순차적 이동 유형.

고려중인 문제는 소규모 및 개별 생산 기계 제작 기업의 운영 일정 계획의 일반적인 작업 중 하나입니다.

그룹의 부품이 다른 경우 분명히 이 그룹에 있는 모든 부품의 총 처리 시간은 부품이 처리를 위해 시작되는 순서에 따라 달라집니다.

수학적 공식에 따르면 조합 순열 문제이므로 결과적으로 최적의 그래프 구성이 가능합니다. 전체 검색모든 옵션. 결과적으로 가공을 위해 부품을 출시하는 최적의 순서를 식별하려면 일반적으로 가능한 모든 옵션을 완전히 검색해야 합니다. 그러나 가능한 모든 옵션을 직접 검색하고 컴퓨터를 사용하여 솔루션을 얻는 것은 상대적으로 적은 수의 데이터(부품, 작업, 기계)로도 불가능합니다. 이는 미래에 첫 번째 기계의 출시 순서가 유지되는 상황으로 제한하더라도 부품이 후속 기계에 도착하면 총 옵션 수가 다음과 같기 때문입니다. 중!.

철저한 검색 방법의 부인할 수 없고 귀중한 의미는 기본적으로 항상 "손에 닿아 있다"는 것입니다. 유한한 실행 가능한 솔루션 세트의 경우, 특히 존슨 문제의 경우 이는 문제를 해결하기 위한 유한한 알고리즘이 있음을 의미합니다. 즉, 문제는 유한한 시간 내에 해결 가능합니다. 그러나 문제는 철저한 검색 방법의 경우 이 "최종" 시간이 단순한 상황에서도 용납할 수 없을 정도로 길다는 것입니다.

따라서 최적의 순서를 찾는 문제에서 부품이 10개만 있는 경우 각 일정 옵션을 구성하고 해당 기준 함수(최적 기준)의 값을 계산하는 데 1분만 소요됩니다. 그러면 완전 검색 방법(옵션 수는 10!, 즉 3,628,800개)을 사용하고 하루 24시간 근무하더라도 이 문제를 해결해야 한다는 것을 계산하는 것은 어렵지 않습니다... 거의 7년 동안. 20개의 부품(옵션 수는 20!, 즉 2.433 * 1018개의 옵션)의 경우 최신 고속 컴퓨터의 도움을 받아도 이러한 문제를 해결하는 데 77,000년 이상이 소요됩니다. 무차별 대입 방식!

부품이 다르고 첫 번째 기계의 실행 순서가 나중에 유지되지 않을 수 있는 경우, 부품이 후속 기계에 도착할 때 분명히 고려 중인 그룹의 모든 부분의 총 처리 시간은 다음 순서에 따라 달라집니다. 각 기계에서 가공을 위해 부품이 출시됩니다. 결과적으로 가능한 옵션의 총 개수는 엄청나게 증가합니다( 중!) N .

이러한 조합 문제를 정면으로 해결하려면 큰 숫자다양한 부분(실제 실제 문제의 경우)은 가장 강력한 컴퓨터에서도 접근할 수 없는 것으로 밝혀졌습니다.

그러므로 방법을 개발하려면 정확한 솔루션이러한 종류의 작업을 위해서는 실행 순서(순서)에 대해 가능한 모든 옵션을 기본적으로 열거하는 것보다 더 나은 것을 제공해야 합니다.

S.조인슨 이 작업 2개 및 3개 기계(작업)와 이러한 기계에서 엄격하게 순차적으로 처리되는 임의 수의 부품에 대해 해결되었습니다(즉, 각 부품은 먼저 첫 번째 기계에서 처리된 다음 두 번째 및 세 번째 기계에서 처리됩니다). 이미 세 대의 기계의 경우 솔루션이 복잡해졌으며 이 방법(Johnson의 알고리즘)을 네 대 이상의 기계의 경우로 확장하는 것은 불가능합니다.

고려 중인 문제는 확실히 문제로 축소될 수 있습니다. 선형 프로그래밍, 그러나 변수의 수와 제한의 수가 너무 커서 현대 컴퓨터의 도움을 받아도 이 방법을 사용하여 문제를 해결하는 것은 불가능합니다. 따라서 운영 스케줄링의 실질적인 문제를 해결하기 위해 휴리스틱 방법이 제안됩니다.

발사 순서(순서)의 변형을 열거하는 양을 줄이는 일반적인 방법에 대한 문제는 잠시 제쳐두고, 기계 수가 다음과 같은 경우 존슨 문제 공식화의 특정 버전을 고려해 보겠습니다. N=2. 이 특별한 경우에는 작업 실행의 최단 기간(최단 일정 기간), 즉 그룹의 최소 총 처리 시간을 보장하는 시작 부분의 순서를 찾는 간단한 방법을 설정할 수 있습니다. 중세부정보( 중=6), 각각은 생산 라인을 구성하는 두 대의 기계(첫 번째 기계에서 먼저, 그 다음 두 번째 기계에서)에서 순차적으로 처리되어야 합니다. 처리 시간 나세부정보( 나=1,…,중) 에 제이-번째 머신( 제이=1,2) 티 ij주어진 것으로 가정되며, 원칙적으로
. 표 8.1은 고려 중인 예제의 초기 데이터를 나타냅니다.

표 8.1 – 존슨 문제와 그 해법에 대한 초기 데이터

세부, 나	처리 시간 나세부사항 ~에 제이-번째 기계, (분)	대기열, 케이
세부, 나		대기열, 케이

처리를 위해 다음과 같이 무작위로 선택된 시작 부품 순서에 대해 두 기계에서 부품을 처리하는 프로세스를 그래픽으로 설명하겠습니다. A→B→C→D→E→E(그림 8.1) (부품 번호 지정 및 처리 순서는 동일합니다).

그림 8.1 – 두 기계에서 부품 그룹을 처리하기 위한 프로세스 그래프

그림 8.1에서
- 그룹의 총 처리 시간 티세부정보( 티=6), 즉 전체 생산 주기의 지속 시간은 첫 번째 부분의 처리가 시작되는 순간부터 경과하는 시간입니다( 나=A) 첫 번째 머신( 제이=1) 마지막 부분 처리가 끝날 때까지( 나=E) 두 번째 시스템( 제이=2)는 공식 (8.1.1)을 사용하여 계산되며 고려 중인 예에서는 41분과 같습니다.

어디 - 처리 시간 나- 두 번째 기계의 번째 부분, 나= 1,…, 중;

- 두 번째 기계의 모든 부품에 대한 총 처리 시간

- 두 번째 기계의 총 가동 중지 시간(두 번째 작업의 장비)

- 처리 작업 완료 사이에 두 번째 기계의 가동 중지 시간( 나-1) 이 기계의 첫 번째 부품 및 가공 시작 나-동일 기계의 두 번째 부품(첫 번째 출시 단계의 부품)
);

- 부품 처리 시간 케이케이= 1,…, 중;

- 부품 처리 시간 케이- 두 번째 머신의 실행 큐, 케이= 1,…, 중-1;

이러한 문제 공식화와 그에 따른 경제 및 수학적 모델의 최적성 기준은 전체 생산 주기의 기간을 최소화하는 것입니다.

두 번째 기계의 모든 부품에 대한 총 처리 시간, 즉 합계이므로 는 알려져 있으며 공식 (8.1.2)에서 부품 발사 순서는 일정합니다. 가장 작은 값전체 생산 주기 동안 두 번째 작업에서 장비의 전체 가동 중지 시간(두 번째 기계의 가동 중지 시간)을 최소화해야 합니다.

이 예에서 두 번째 시스템의 가동 중지 시간은 다음과 같습니다.

우리가 고려 중인 문제를 해결하기 위해 완전 탐색 방법을 사용한다면, 중위에 표시된 것처럼 모든 부품이 첫 번째 기계에서 먼저 처리된 다음 두 번째 기계에서 각각 동일한 순서로 처리되는 경우 중! 가능한 옵션(순서), 즉 이 예에서는 6!=720개의 옵션이 있습니다.

최적의 처리 순서(순서)를 찾는 매우 간단한 알고리즘이 있습니다. 티두 기계의 부품 – Johnson의 알고리즘.

지정된 알고리즘에는 다음과 같은 주요 단계가 포함됩니다.

1) 기계 중 하나에서 처리 시간이 가장 짧은 부품이 선택됩니다. 첫 번째 반복의 예에서는 이것이 세부 사항입니다. 비;

2) 선택한 부품은 가장 짧은 처리 시간이 첫 번째 기계에 해당하는 경우 대기열의 시작 부분에 배치되고, 두 번째 기계에 해당하는 경우 대기열의 끝에 배치됩니다. 우리 예에서는 세부 사항 비대기열의 끝에 배치됩니다( 케이=6);

3) 선택된 세부사항에 해당하는 표 8.1의 라인은 추가 고려사항에서 제외됩니다(줄이 그어져 있음).

4) 기계 중 하나에서 처리 시간이 다음으로 짧은 부품을 나머지 부품 중에서 선택합니다. 두 번째 반복의 예에서는 이것이 세부 사항입니다. 안에, 세 번째 반복에서는 이것이 세부사항입니다. 이자형, 네 번째 반복에서는 다음과 같은 세부정보가 표시됩니다. ㅏ그리고 G, 마지막 반복에서 이것은 세부 사항입니다 디;

5) 선택한 부분은 2단계에서 지정한 규칙에 따라 대기열의 시작 또는 끝 부분에 더 가깝게 배치됩니다. 이 예에서는 두 번째 반복에서 해당 부분이 안에대기열 끝 근처에 배치됨( 케이=5), 부품 앞 비, 세 번째 반복에서 부품 이자형대기열의 시작 부분에 배치됩니다( 케이=1), 네 번째 반복에서 부품 ㅏ케이=4), 그리고 그 부분 G대기열의 시작 부분에 배치됩니다( 케이=2), 마지막 반복에서 부품 디대기열 끝 근처에 배치됨( 케이=3);

6) 모든 부품의 실행 순서가 결정되면 솔루션을 획득하고, 그렇지 않으면 3단계로 이동합니다.

이 알고리즘을 구현한 결과 두 기계의 작동에 대한 최적의 일정을 얻을 수 있습니다(그림 8.2). 이 예(표 8.1 참조)에서 처리를 위한 부품 시작의 최적 순서를 찾았습니다. E→G→D→A→B→B. 표 8.1의 마지막 열에는 실행 대기열 번호( 케이) 생산 라인의 각 기계에서 처리되는 해당 부품.

№ 운영

그림 8.2 – 두 기계의 최적 작동 일정 그래프

부품을 처리하기 위한 최적의 순서를 선택한 후 공식 5는 두 번째 기계의 총 가동 중지 시간을 결정합니다.
, 이는 가능한 모든 것의 최소값입니다.

(8.1.5)

그런 다음 총 생산주기의 기간은 다음 공식을 사용하여 계산됩니다.

이러한 방식으로 얻은 총 생산주기의 지속 기간 값은 주어진 조건에서 가능한 모든 것의 최소값이기도 합니다.

부품을 한 기계에서 처리한 다음 두 번째 기계에서 처리해야 하고 한 기계에서 두 개 이상의 부품을 처리할 수 없는 경우 두 기계에서 부품 처리 순서를 선택하는 문제는 1954년 S. Johnson에 의해 고려되었습니다. 이를 해결하는 방법을 존슨 알고리즘(Johnson's Algorithm)이라고 합니다.

이번 장에서는 생산 스케줄링 시스템의 운영 원리에 대해 이야기했습니다. 스케줄링의 복잡성은 다음과 관련이 있습니다. 큰 금액작업 일정 옵션. 이 문제는 계획과 장비 로딩을 분리하고, 가장 노동 집약적인 배치를 먼저 예약하고, 우선 순위를 사용하고, Johnson 알고리즘을 사용하여 해결할 수 있습니다. 최적의 솔루션을 제공하는 방법은 없습니다.

Johnson의 알고리즘을 설명하기 위해 행렬 T를 2열 행렬로 상상해 보겠습니다.

Johnson 알고리즘의 변형 중 하나에서 여러 단계로 구성된 프로세스는 두 가지 작업으로 구성된 것으로 간주되며 이 방법은 최적은 아니지만 다음을 제공합니다. 좋은 결과. 이 경우 두 단계에 걸쳐 여러 지점이 인위적으로 생성되고 각 지점에는 위에서 설명한 알고리즘이 적용됩니다. 다음으로 모든 그래프의 총 지속 시간을 계산하고 가장 작은 값을 선택합니다. 두 개의 인접한 연산을 고려하여 인위적으로 두 단계로 나누는 작업을 수행하므로 6단계의 과정에 대해 다음과 같은 그래프가 구성됩니다.

Petrovat-Sokolitsyn 방법. 원래 행렬은 Johnson 방법과 동일하지만 연산(열) 수에 대한 제한이 제거되었습니다. 이 알고리즘에는 두 개의 중간 합계와 그 차이를 계산하는 작업이 포함됩니다. 그런 다음 처리를 위한 여러 실행 배치 순서가 다음 규칙에 따라 결정됩니다.

세부특성문제를 해결하기 위한 처음 세 가지 옵션은 11장에 나와 있습니다. 첫 번째 옵션에는 작성자의 이름을 따서 Johnson 알고리즘(방법)이라고 불리는 엄격하고 효과적인 솔루션이 있다는 점을 기억해 보겠습니다. 두 번째 옵션도 특정 조건에서 Johnson 방법에 의한 솔루션으로 축소될 수 있지만 결과가 반드시 최적인 것은 아닙니다. 이 문제에 대한 엄격한 해결책은 R. Bellman에 의해 제시되었지만 이는 노동 집약적입니다. 세 번째 옵션이 가장 어렵습니다. 이를 해결하기 위한 효과적인 경험적 절차는 DS 알고리즘으로 알려져 있습니다. 이 알고리즘은 Johnson의 방법을 문제의 일반적인 경우로 확장하고 거의 최적의 솔루션을 제공합니다. 이 문제를 해결하기 위해 큐잉 이론과 컴퓨터 시뮬레이션을 사용하는 다른 접근 방식이 있습니다. 그러나 이들 모두는 노동 집약적이고 복잡하며 동시에 최적의 순서를 찾는 것을 보장하지 않습니다.

달력 최적화 문제의 두 번째 예는 그래프를 구성하는 것입니다. 가장 좋은 방법여러 연속적인 생산 단계(가공 단계)에서 제품 출시 시기를 조정하고 각 단계에서 제품에 대한 처리 시간이 다릅니다. 예를 들어, 인쇄소에서는 조판, 인쇄 및 제본 작업장의 작업을 조정해야 하며, 이는 개별 작업장마다 노동력과 기계 강도가 다르기 때문입니다. 다른 유형제품(레터헤드 제품, 단순 또는 복잡한 유형의 서적 제품, 제본 유무 등). 다양한 최적화 기준을 사용하여 문제를 해결할 수 있으며, 다양한 제한. 따라서 최소 생산 기간, 주기 문제를 해결할 수 있으므로 진행 중인 작업(백로그)의 평균 잔액 최소값은 다음과 같이 결정되어야 합니다. 다양한 작업장(가공 영역)의 처리량을 확인할 수 있습니다. 동일한 문제에 대한 또 다른 공식화도 가능합니다. 여기서 최적화 기준은 생산 시간에 부과된 제한 하에서 가용 생산 능력을 최대한 활용하는 것입니다. 개별 종제품. 이 문제(소위 존슨 문제 a)의 정확한 해결을 위한 알고리즘은 제품이 2번의 작업만 수행하는 경우와 3번의 작업에 대한 대략적인 솔루션을 위해 개발되었습니다. ~에 더작업 중에 이러한 알고리즘은 부적합하여 달력 일정 최적화 문제를 해결해야 할 필요성이 발생하기 때문에 실질적으로 가치가 떨어집니다. 도착. 다중 작업 프로세스 계획(예: 기계 공학) 1959년 E. Bowman(미국)과 1960년 A. Lurie(소련)은 선형 프로그래밍의 일반적인 아이디어를 기반으로 하며 원칙적으로 여러 연산으로 문제를 해결할 수 있는 수학적으로 엄격한 알고리즘을 제안했습니다. 그러나 현재(1965년) 이러한 알고리즘은 실제로 적용할 수 없으며 기존의 가장 강력한 전자 컴퓨터에도 계산이 너무 복잡합니다. 따라서 이러한 알고리즘은 단순화되거나 발전할 수 있는 유망한 가치를 갖습니다. 컴퓨터 기술새로운 기계에 구현될 수 있게 될 것입니다.

간략한 이론

동적 프로그래밍(동적 계획이라고도 함)은 다음을 찾는 방법입니다. 최적의 솔루션다단계 (다단계) 구조에 문제가 있습니다. 많은 경제적 과정자연스럽게 단계로 나누어집니다. 이는 모두 시간이 지남에 따라 개발된 계획 및 관리 프로세스입니다. 자연스러운 단계는 연도, 분기, 월, 10년, 주, 일 등이 될 수 있습니다. 그러나 방법은 동적 프로그래밍시간이 전혀 나타나지 않는 문제를 해결하는 데 사용할 수 있습니다. 이러한 문제의 단계 구분은 인위적으로 도입되었습니다. 따라서 동적 프로그래밍 문제의 "역동성"은 해결 방법에 있습니다.

경제적 실제에는 공식이나 해결 방법에 따라 동적 프로그래밍 문제에 속하는 여러 유형의 문제가 있습니다. 이는 시간에 따른 최적의 장기 및 현재 계획의 문제입니다. 이는 각 기간에 대해 상호 연결된 정적 모델 세트를 컴파일하거나 다단계 의사 결정 절차를 사용하여 단일 동적 최적 프로그래밍 문제를 컴파일하여 해결됩니다. 동적 프로그래밍의 문제에는 최적의 성능뿐만 아니라 생산력 배치에서 최적을 찾는 다단계 문제가 포함됩니다.

다단계 문제의 일반적인 특징.

1. 각 단계의 상태가 벡터에 의해 결정되는 시스템을 고려합니다. 그녀의 상태에 대한 추가 변화는 다음에 달려 있습니다. 이 상태그리고 시스템이 어떻게 왔는지에 의존하지 않습니다. 이러한 과정을 후유증이 없는 과정이라고 합니다.

2. 각 단계에서 시스템이 시작되는 영향을 받아 하나의 솔루션이 선택됩니다. 이전 상태새로운. 이 새로운 상태는 간격 시작 시의 상태와 간격 시작 시 취해진 결정의 함수입니다.

3. 각 단계의 행동은 특정 이득(수입, 이익) 또는 손실(비용)과 연관되어 있으며, 이는 단계(단계) 시작 시 상태와 내린 결정에 따라 달라집니다.

4. 실행 가능한 솔루션의 영역을 구성하는 상태 및 제어 벡터에 제한이 적용될 수 있습니다.

5. 모든 단계에 대한 목표 함수의 극한값을 얻으려면 각 단계에 대해 허용 가능한 제어를 찾는 것이 필요합니다.

모든 다단계 문제는 다양한 방법으로 해결될 수 있습니다. 첫째, 우리는 알려지지 않은 수량 u를 고려하고 기존 최적화 방법 중 하나를 사용하여 목적 함수의 극값을 찾을 수 있습니다. 즉, 모든 단계에서 해의 모든 요소를 한 번에 검색합니다. 이 경로가 항상 목표로 이어지는 것은 아닙니다. 특히 다음과 같은 경우에는 더욱 그렇습니다. 목적함수표 형태로 주어지거나 변수의 수가 매우 많다. 두 번째 방법은 최적화를 단계적으로 수행한다는 아이디어에 기반을 두고 있습니다. 단계적은 단계 최적화의 격리를 의미하지 않습니다. 반대로 각 단계의 제어는 모든 결과를 고려하여 선택됩니다. 일반적으로 두 번째 최적화 방법은 특히 단계 수가 많은 경우 첫 번째 최적화 방법보다 더 간단합니다. 점진적이고 단계별로 최적화한다는 아이디어가 동적 프로그래밍 방법의 핵심입니다. 일반적으로 1단계 최적화는 최적화가 더 쉽다전체 과정 전체. 비교적 여러 번 결정하는 것이 좋습니다 간단한 작업한 번 이상 - 복잡합니다.

언뜻 보면 아이디어가 사소해 보일 수 있습니다. 복잡한 문제를 최적화하는 것이 어렵다면 이를 여러 개의 간단한 문제로 나누어야 합니다. 각 단계에서 작은 문제가 최적화되는데, 이는 어렵지 않습니다. 동시에 동적 프로그래밍의 원리는 각 단계가 다른 단계와 독립적으로 독립적으로 최적화된다는 것을 전혀 의미하지 않습니다. 반대로, 모든 결과를 고려하여 점진적 제어를 선택해야 합니다.

동적 프로그래밍의 기본 원칙인 최적성 원칙과 몰입성 원칙을 공식화할 수 있습니다.

각 단계의 최적 제어는 이 단계 시작 시 시스템 상태와 제어 목표에 따라 결정됩니다. 또는 확장된 형태로 말하면, 최적 전략은 초기 상태와 초기 결정이 무엇이든 첫 번째 결정으로 인한 상태를 고려하여 최적 전략을 기반으로 후속 결정을 내려야 한다는 속성을 가지고 있습니다. 이 원리는 특정 반복 관계(R. Bellman의 함수 방정식)의 편집으로 표현되는 매우 간단한 수학적 해석을 가지고 있습니다.

동적 프로그래밍 방법을 사용할 수 있는 문제의 본질은 단계 수가 변경되어도 변하지 않습니다. 즉, 이러한 문제의 형태는 에 대해 불변입니다. 이런 의미에서 특정 프로세스는 주어진 숫자단계는 말하자면 그와 유사한 일련의 프로세스에 몰입되어 있으며 더 넓은 종류의 문제의 관점에서 고려될 수 있습니다.

이러한 원칙을 구현하면 다음 단계에서 내린 결정이 편협한 이익이 아닌 전체 프로세스와 관련하여 최선이 될 것임을 보장합니다. 이 단계. 후속 단계별 솔루션원래의 단계 문제를 해결하게 됩니다.

가산 최적성 기준(분리 가능한 목적 함수) 문제에 대한 최적성 원칙의 수학적 공식을 제시해 보겠습니다. 단순화를 위해 시스템의 초기 상태와 최종 상태가 주어진다고 가정합니다. 시스템 초기 상태의 첫 번째 단계와 제어 중에 목표 함수의 값을 다음과 같이 표시하겠습니다. -해당 값목표는 두 번째 단계에서만 기능합니다. ...., 통과 - 단계에서, ..., 통과 - 단계에서. 그것은 분명하다

제약 조건 하에서 목적 함수의 극값을 제공하는 최적의 제어를 찾는 것이 필요합니다.

이 문제를 해결하기 위해 우리는 비슷한 문제를 가족에 담급니다. 몇 가지 표기법을 소개하겠습니다. 마지막 단계, 마지막 두 단계 등에서 유사한 문제에 대한 정의 영역을 각각 정의하겠습니다. - 원래 문제의 정의 영역. 다음으로 나타내자

따라서 모든 단계에서 마지막 단계, 마지막 두 개 등의 목표 함수의 조건부 최적 값입니다.

마지막 단계부터 시작해 보겠습니다. 허락하다 - 가능한 상태스테이지 초반의 시스템. 우리는 찾는다:

마지막 두 단계에서는 다음을 얻습니다.

비슷하게:

…………………….

식 (5)는 최적성 원리를 수학적으로 표현한 것이다. 식(4) - 일반적인 모양나머지 단계에 대한 목표 함수의 조건부 최적 값을 기록합니다. 식 (1)~(5)를 함수 벨만 방정식이라고 합니다. 반복(반환) 특성이 명확하게 표시됩니다. 각 단계에서 최적의 제어를 찾으려면 이전 단계에서 조건부 최적 제어를 알아야 합니다. 따라서 함수 방정식을 순환 벨만 관계라고도 합니다.

문제 해결의 예

작업

생산조합은 회원사 중 4개 기업에 1억 단위의 대출을 제공한다. 생산을 확대하고 제품 생산량을 늘리기 위해. 각 기업에 대해 할당된 금액에 따라 생산량(금전적 측면)의 증가 가능성이 알려져 있습니다. 계산을 단순화하기 위해 할당된 금액은 2천만 화폐 단위의 배수입니다. 동시에, 우리는 기업의 생산량 증가가 다른 기업에 투자된 자금의 양에 의존하지 않으며 생산 조합의 총 생산량 증가는 각 기업에서 얻은 증가의 합과 같다고 가정합니다. 협회의.

생산조합 전체의 생산량 증가가 최대가 되도록 기업간 신용배분을 위한 최적의 해법을 찾는 것이 필요하다.

할당된 자금, 백만 화폐 단위

회사

№1

№2

№3

№4

기업의 생산량 증가, 백만 화폐 단위.

100

문제의 해결

배송 기한이 지난 경우 테스트 작업시간이 부족합니다. 언제든지 웹사이트에서 최적의 해결 방법을 사용하여 문제에 대한 긴급 솔루션을 주문할 수 있습니다.

동적 프로그래밍은 최적의 솔루션을 찾기 위한 다단계 검색입니다. 다단계 프로세스의 최적화는 R. Bellman의 최적성 원칙을 기반으로 합니다.

동적 프로그래밍의 계산은 재귀적으로 수행됩니다. 즉, 하나의 하위 문제에 대한 최적의 솔루션은 다음 하위 문제에 대한 최적의 솔루션을 찾기 위한 입력 데이터로 사용됩니다. 마지막 하위 문제를 해결한 후 원래 문제에 대한 최적의 솔루션을 얻습니다.

할당된 자금

100

1 단계

동적 프로그래밍의 계산 방식에 따라 먼저 다음과 같은 경우를 고려해 보겠습니다. 한 기업의 재건과 현대화를 위해 사용 가능한 모든 자금이 할당되었다고 가정해 보겠습니다. 할당된 금액에 해당하는 이 기업에서 가능한 최대 추가 소득으로 표시하겠습니다. 각 값은 추가 소득의 매우 구체적인(단일) 값에 해당하므로 다음과 같이 쓸 수 있습니다.

2 단계

지금 보자. 자금은 두 기업 사이에 분배됩니다. 두 번째 기업에 금액이 할당되면 추가 수입은 입니다. 규모(따라서 )에 따라 다른 기업에 남은 자금을 사용하면 추가 수입을 가능한 최대 값으로 늘릴 수 있습니다. 이 조건에서 두 기업의 총 추가 소득은 다음과 같습니다.

3단계

지금 보자. 자금은 세 기업에 분배됩니다. 세 번째 기업에 금액이 할당되면 추가 수입은 입니다. 규모(따라서 )에 따라 나머지 자금을 사용하면 추가 수입을 가능한 최대 값으로 늘릴 수 있습니다. 이 조건에서 세 기업의 총 추가 소득은 다음과 같습니다.

4단계

지금 보자. 자금은 4개 기업에 분배됩니다. 네 번째 기업에 금액이 할당되면 추가 수입은 입니다. 규모(따라서 )에 따라 나머지 자금을 사용하면 추가 수입을 가능한 최대 값으로 늘릴 수 있습니다. 이 조건에서 4개 기업의 총 추가 소득은 다음과 같습니다.

0 0 0 0 0 20 10 12 12 16 40 31 31 36 37 60 42 43 48 52 80 62 62 67 73 100 76 76 79 85

답변

4개 기업 간의 100단위 자원에 대한 최적의 분배 계획:

이 경우 총 생산 증가량은 최대 85에 도달합니다.

평균테스트 해결 비용은 700-1200 루블입니다 (그러나 전체 주문에 대해 300 루블 이상). 가격은 결정의 긴급성(하루에서 몇 시간까지)에 따라 크게 영향을 받습니다. 시험/테스트에 대한 온라인 도움말 비용은 1000 루블입니다. 티켓을 해결하기 위해.

이전에 작업 조건을 보내고 필요한 솔루션에 대한 기간을 알려준 후 채팅에서 직접 비용에 대한 모든 질문을 할 수 있습니다. 응답 시간은 몇 분입니다.

지식 기반에서 좋은 작업을 보내는 것은 간단합니다. 아래 양식을 사용하세요

연구와 업무에 지식 기반을 활용하는 학생, 대학원생, 젊은 과학자들은 여러분에게 매우 감사할 것입니다.

게시 날짜 http://www.allbest.ru/

동적 프로그래밍 방법을 이용한 자원 할당 문제

확장용 생산 능력세 기업 A, B, C에는 x 0 =8 단위의 특정 수의 추가 전력 단위가 할당됩니다. 전기는 1, 2, 3, 4, 5, 6, 7, 8 단위 형태로 방출될 수 있습니다. i번째 기업의 발전에 x i 단위의 전력을 투자함으로써 기업의 i 단위로부터 수입을 얻을 수 있습니다. 존재하다 다양한 변형 x i (k) 추가 전기 할당. 그들은 i(k), k=1,n에 소득을 가져옵니다. 가능한 옵션기업의 발전은 표 1에 나와 있습니다. 모든 기업의 총 수입은 최대여야 합니다. 즉, y=? y i (k)>최대

테이블 1. 엔터프라이즈 개발 옵션

옵션 k	기업 A	엔터프라이즈 B	엔터프라이즈 C

매우 정확한 각색 작업:

y=? ~에 나 (케이)> 최대

?엑스 나 (k)?x 0

해결책:

기업 C에 투자가 할당되는 마지막(3단계) 단계(표 2)부터 당면한 문제를 해결하기 위한 절차를 고려해 보겠습니다. 세 번째 단계의 조건부 최적 제어는 방정식에 대한 솔루션으로 모색됩니다.

g C(S 2)=최대 k f c , x C(k)?S 2 , k=1,2,3,4

테이블 2. 조건부 최적해(3단계)

상태		제어

자금 투자에는 4가지 가능성이 있습니다. 4단계 제어 x C(1) = 0 단위, x C(2) = 1 단위, x C(3) = 2 단위, x C(4) = 3 단위. 기업 C에 자금을 할당하기 전 시스템 S 2의 이론적으로 가능한 9가지 상태 - 3단계에 분배되지 않은 투자량: 0,1,2,3,4,5,6,7,8.

시스템이 S 2 =2 상태에 있다고 가정해 보겠습니다. 그러면 단계 제어 x C(2) = 1에 대해 C(2)의 수입은 3단위가 됩니다. (표 3), 단계 제어 x C(3) = 2가 이 상태에 최적이며 조건부 최대 이득 g c(S 2) = 5를 제공합니다. 시스템이 S 2 =3 상태인 경우 모든 단계 제어가 허용됩니다. x C (1) = 0 단위, x C (2) = 1 단위, x C (3) = 2 단위, x C (4) = 3 단위, 최적의 제어는 x C(4) = 3이 되며 조건부 최대 이득 g c(S 2) = 6을 제공합니다.

표 3 동적 프로그래밍 투자 분포

3단계 이전의 모든 가능한 상태는 유사하게 채워집니다. 최적의 값지표는 표에서 굵게 강조 표시되어 있습니다.

다음으로 두 번째 단계는 기업 A에 투자를 할당하는 것과 같은 방식으로 고려됩니다(표 4). 두 번째 단계에서 총 이익은 세 번째와 두 번째 단계에서 얻은 승리의 합이며 다음과 같이 제공됩니다. 비율로:

g A(S 1)=최대 k f A +g c], x A(k)?S 1, k=1,2,3,4

따라서 단계 제어 x A (2) = 1을 사용하는 상태 S 1 =3에 대해 다음을 얻습니다.

g A (S 1)=최대 k f A +g c ]

Max k 4+g c =4+5=9, 여기서 우리는 표 1에서 찾고, g c는 표 3에서 찾습니다. 모든 상태는 유사하게 채워집니다.

테이블 4. 조건부 최적해(2단계)

상태	f A +g c	제어

여기서 최적의 솔루션이 유일한 솔루션이 아닌 상황이 발생합니다. 따라서 상태 S 1 = 3에서 단계 제어 x A (2) = 1 및 x A (3) = 2가 조건부 최적이 되어 동일한 결과가 제공됩니다. gA(S1)=9를 얻습니다.

테이블 5. 무조건 최적의 솔루션(1단계)

첫 번째 단계(표 5)(기업 B에 대한 투자 할당)에는 초기 상태 S 0 =8에 해당하는 시스템의 이전 상태가 하나만 있습니다. 무조건 최적의 이득은 다음 식으로 결정됩니다.

y * = g B (S 0)= 최대 k (f A +g A) x in (k)?S 0 =x 0, k=1,2,3,4,5

최대 수입을 보장하는 무조건적인 최적의 제어는 다를 수 있습니다.

모두를 찾는 계획 최적의 옵션기업 간 투자 분포(표 6)는 그림 1에 나와 있습니다.

테이블 6. 투자의 최적 분배.

그림 1. 기업 간 최적의 투자 분배 계획

결론: 동적 프로그래밍 방법을 사용하여 자원 할당 문제를 고려한 결과 최적의 자원 할당을 위한 두 가지 옵션이 식별되었습니다.

Allbest.ru에 게시됨

...

유사한 문서

일반적 특성그리고 경제 지표연구 중인 세 기업의 활동. 선형 및 동적 프로그래밍을 사용하여 생산 계획 및 투자 분배 문제를 해결합니다. 비교 분석결과.

코스 작업, 2015년 4월 25일에 추가됨

다단계 프로세스 동적 작업. 최적성과 재발 관계의 원리. 동적 프로그래밍 방법. 생산 확대 및 생산 프로그램 계획을 위한 최적의 자금 할당 문제.

코스 작업, 2010년 12월 30일에 추가됨

동적 프로그래밍 방법과 주요 단계. 최적의 장비 교체 전략. 기업의 건설 및 운영 비용을 최소화합니다. 최적의 분포 STROYKROVLYA LLC의 자원과 PKT Khimvolokno의 투자.

코스 작업, 2015년 1월 8일에 추가됨

생산 계획의 수학적 모델. 최적의 계획 수립 생산 활동선형 프로그래밍 방법을 사용하는 기업. 발견 가장 좋은 방법계획 기간 동안 금전적 자원 분배.

논문, 2013년 8월 7일에 추가됨

방법을 이용한 운송비 계산 최소 비용. 동적 프로그래밍 과정에서 조건부 최적 동등성을 찾습니다. 선의 대수 방정식중복 시스템의 평균 비고장 시간에 대한 Kolmogorov.

코스 작업, 2011년 1월 14일에 추가됨

그래픽 방식생산 공정 최적화 문제를 해결합니다. 경제적으로 최적화된 생산 관리 문제를 해결하기 위한 단순 알고리즘을 적용합니다. 최적의 경로 프로필을 선택하기 위한 동적 프로그래밍 방법입니다.

테스트, 2010년 10월 15일에 추가됨

최적의 계획분포 돈기업 간. 투자 수익을 얻을 수 있는 각 기업에 대한 계획 개발 가장 높은 가치. 선형 및 동적 프로그래밍 방법을 사용합니다.

과정 작업, 2013년 12월 16일에 추가됨

선형 계획법 문제의 특징. 생산 계획 문제의 일반적인 공식화. 회사 자원 분배에 대한 수학적 모델 구축. 최적 솔루션의 민감도 분석. 지속가능성 보고서를 작성합니다.

프레젠테이션, 2014년 12월 2일에 추가됨

최적의 증권 포트폴리오를 찾아보세요. 문제 해결 방법을 검토합니다. 수학적 모델의 구축. 콘 프로그래밍 문제. 초기 매개변수 중 하나에 대한 초기 자본 분배 벡터의 의존성.

논문, 2017년 2월 11일에 추가됨

동적 프로그래밍 모델. 최적성 원리와 벨만 방정식. 모델링 및 구축 과정에 대한 설명 컴퓨팅 회로동적 프로그래밍. 기업의 건설 및 운영 비용을 최소화하는 문제.

DP(동적 프로그래밍)는 다단계(다단계) 구조의 문제에서 최적의 솔루션을 찾는 방법입니다.

DP 문제의 일반적인 공식을 제시하겠습니다. 통제된 프로세스가 고려됩니다(기업 간 자금 분배, 수년간의 자원 사용 등). 제어의 결과, 시스템(제어 객체)은 초기 상태에서 상태로 전이된다. . 통제가 다음과 같이 분류될 수 있다고 가정해보자.
단계. 각 단계에서 허용되는 여러 컨트롤 중 하나가 선택됩니다.
, 시스템을 세트의 상태 중 하나로 전환
. 세트의 요소
그리고 특정 작업의 조건에 따라 결정됩니다. 시스템 상태의 순서는 그림 1에 표시된 상태 그래프로 표시할 수 있습니다. 3.1.

모든 단계 N효과가 달성됩니다
. 총 효과는 각 단계에서 얻은 효과의 합이라고 가정해 보겠습니다. 그런 다음 DP 문제는 다음과 같이 공식화됩니다. 허용 가능한 제어를 결정합니다.
, 상태에서 시스템을 전송합니다. 상태에서
, 목표 함수
가장 큰(가장 작은) 값을 취합니다. 즉,

DP 방법에 의한 문제 해결은 미국 과학자 R. Bellman이 공식화한 최적성 원칙을 기반으로 수행됩니다. 여러 단계의 결과로 시스템 상태가 무엇이든 다음 단계에서 다음과 함께 제어할 수 있도록 선택해야 합니다. 최적의 제어모든 후속 단계에서 이 단계를 포함하여 나머지 모든 단계에서 최적의 승리로 이어졌습니다.

다음으로 나타내자
단계로부터의 구간에 대한 목적 함수의 조건부 최적값 N마지막까지
- 이전 단계를 포함하는 경우 N번째 단계에서 시스템은 세트의 상태 중 하나였습니다.
, 그리고 N번째 단계에서는 이러한 컨트롤이 세트에서 선택되었습니다.
, 조건부 최적 값으로 목적 함수를 제공한 다음
( N+1 )번째부터
-번째 단계가 포함됩니다.

수용된 표기법에서 Bellman 최적성 원리는 다음과 같이 수학적 형식으로 작성될 수 있습니다.

평등(3.1)은 동적 프로그래밍의 주요 함수 방정식이라고 합니다. 각각 특정 작업방정식은 특별한 형태를 가지고 있습니다.

DP 방법의 계산 절차는 조건부 최적화와 무조건적 최적화의 두 단계로 나뉩니다.

무대에서 가정 어구 최적화함수 방정식에 따라 마지막 단계부터 시작하여 각 단계에서 가능한 모든 상태에 대해 최적의 제어가 결정됩니다.

무대에서 무조건적인 최적화단계는 처음부터 시작되는 것으로 간주됩니다. 초기상태부터 알려진 최적의 제어는 세트에서 선택됩니다 . 선택된 최적의 제어 시스템을 매우 특정한 상태로 만듭니다. . 초기 상태이기 때문에 두 번째 단계가 시작될 때 알 수 있으므로 두 번째 단계에서 최적의 제어를 선택하는 것이 가능해집니다. 등. 따라서 상호 연결된 무조건적 최적화 솔루션 체인이 구축됩니다.

3.1. 최적의 자원 할당 문제

주요 생산품의 재건과 현대화를 위해 협회에 일정량의 물적 자원을 할당하도록 합니다. 엑스. 사용 가능 N배포가 필요한 기업 이 리소스. 다음으로 나타내자
할당이 국가 경제에 가져오는 이익 제이- 기업
자원 단위. 이윤폭은 할당된 자원량과 기업 모두에 따라 결정된다고 가정합니다. 또한 기업이 받는 이익은 동일한 단위로 측정되며 총 이윤협회는 개별 기업의 이익으로 구성됩니다. 협회의 총이익이 최대가 되는 최적의 기업간 자원배분 방안을 찾는 것이 필요하다.

당면한 작업은 다단계 작업으로 간주되어야 합니다.

무대에서 조건부 최적화하나의 기업(예를 들어 첫 번째 기업), 두 개의 기업을 함께 투자하는 것(첫 번째와 두 번째), 세 개의 기업을 함께 투자하는 것(첫 번째, 두 번째, 세 번째) 등을 고려하고 마지막으로 모든 기업에 투자하는 것의 효율성을 고려하겠습니다. N함께하는 기업. 이 작업은 함수의 가장 큰 값을 결정하는 것입니다.
제공
.

이 문제에 대해 다음과 같은 함수 방정식으로 이어지는 벨만 재발 관계식(3.1)을 사용하겠습니다.
:

기능은 다음과 같습니다
할당 시 첫 번째 기업의 최대 이익을 결정합니다. 엑스자원 단위, 기능
첫 번째 기업과 두 번째 기업을 할당할 때 함께 최대 이익을 결정합니다. 엑스자원 단위, 기능
첫 번째, 두 번째, 세 번째 기업을 할당할 때 함께 최대 이익을 결정합니다. 엑스자원 단위 등, 그리고 마지막으로 기능
기업을 할당할 때 모든 기업의 최대 이익을 함께 결정합니다. 엑스자원 단위.

무대에서 무조건적인 최적화기업 간 자원 배분을 위한 최적의 계획이 결정됩니다.

예제 3.1.

수요가 많은 제품의 생산량을 늘리기 위해 생산 협회의 4개 기업에 5천만 루블의 자금이 할당되었습니다. 각 기업에는 0, 10, 20, 30, 40 또는 5천만 루블을 할당할 수 있습니다. 동시에 각 기업의 생산량은 매년 증가하고 있습니다.
투자에 따라 알려지고 표에 나와 있습니다. 3.1.

표 3.1

할당된 자금의 양 엑스(백만 루블)	할당된 자금의 양에 따라 연간 제품 생산량 증가(백만 루블)
할당된 자금의 양 엑스(백만 루블)