수업 일정은 학교 생활의 리듬, 학생과 교사의 업무 및 휴식을 규제합니다.
전체 교육 과정의 효과는 주로 품질에 달려 있습니다.

수업 자격 및 학교 시간표

학교의 교육 체제는 학생의 기능적 능력에 부합해야 합니다. 범위, 내용 및 조직 교육 과정휴식시간 동안 피로가 완전히 사라지는 신체상태를 보장해야 한다.

학생들의 기능적 능력 측면에서 수업을 평가하는 주요 기준은 난이도와 지루함입니다. 피로는 수행의 변화를 특징으로 하며, 과목의 난이도는 수행의 수준, 즉 숙달 정도에 따라 특징을 갖는다. 교육 자료. 따라서 일정을 계획할 때 두 가지 요소를 동일하게 고려해야 합니다.

법적 측면에서 학교 일정 작성 문제는 현대 데이터를 기반으로 한 일정에 대한 새로운 위생 요구 사항에 반영됩니다. 과학적 연구생체리듬학 정신적 성과및 물체 I.G의 난이도 테이블. Sivkova. 그러나 일정을 짜는 학교의 교감에게는 그 과목이 얼마나 어려운지 아는 것뿐만 아니라 특정 과목의 수업이 학생들의 건강에 미치는 피곤한 영향의 강도를 상상하는 것도 중요합니다. . 불행히도 난이도 테이블 I.G. Sivkova는 주로 학생의 건강에 영향을 미치는 과목의 지루함과 같은 훈련 구성 요소를 고려하지 않습니다.

현대 연구는 과목의 지루함과 난이도 사이의 관계에 대한 통찰력을 제공하지만 일부 과목에서는 이러한 지표가 크게 다릅니다. 이러한 표현을 사용하면 두 가지 지표를 하나로 결합할 수 있습니다(항목의 허용 가능성). 따라서 테이블 I.G. Sivkov, 우리는 학습의 어려움과 지루함의 구성 요소와 각 학습의 특성을 고려한 과목 수용 가능성의 척도인 대안을 제안할 수 있습니다. 교육 기관그리고 각 학년별 커리큘럼입니다.

수용성 척도는 “순위별 항목” 열로 구성되며, 방법의 난이도와 지루함을 진단한 결과 순위를 획득한 항목이 포함되어 있습니다. 전문가 평가– 해당 알고리즘은 부록 1에 나와 있습니다. 제안된 규모는 구조는 일정하지만 내용은 가변적입니다(표 1 참조).

1 번 테이블

대략적인 품목 허용 범위

표 1에서 볼 수 있듯이 척도는 5개의 난이도 그룹으로 구성되어 있다. 각 그룹에는 점수가 있습니다. 이는 척도의 일정한 구성 요소이며 변경되지 않습니다. 진단 결과에 따라 각 그룹의 내용(항목 집합)이 변경될 수 있습니다. 이는 척도의 가변 부분을 나타냅니다.

평균적으로 중고등 학교상트페테르부르크의 No. 618에서는 다음과 같은 품목 허용 범위를 받았습니다(표 2 참조).

표 2

품목 허용 척도

스케줄링 알고리즘

각 교육 기관마다 과목에 대한 수용 가능성이 다르기 때문에 독자는 주어진 일대일 척도를 복사해서는 안 됩니다. 학교 교과목의 난이도와 지루함 정도를 전문가 평가 방법을 통해 진단해 보는 것이 바람직하다.

또한, 일정을 짤 때, 수업 중 다양한 수업에서 다양한 수업에 참여하는 학생들의 성적 수준을 순위로 매긴 표를 참고하는 것이 합리적입니다(부록 2 참조).

우리는 현실적인 위생 요건을 고려하여 생리학적 기반의 일정을 만들기 위한 알고리즘을 만들었습니다. 이 알고리즘은 2~3학년 학급 수가 많은 학교와 상대적으로 규모가 작은 교육 기관 모두에서 교육 일정을 만드는 데 사용할 수 있습니다. 이 알고리즘은 컴퓨터 프로그램을 사용하지 않고 일정을 작성하는 전문가를 위한 것입니다.

자동화된 프로그램을 사용하는 경우 제안된 알고리즘을 기반으로 자동화된 프로그램을 사용하여 객체를 단계별로 배열하는 것이 좋습니다. 실습에서 알 수 있듯이 이러한 프로그램은 다음의 경우 보조 도구로만 사용할 수 있습니다.

• 물체의 초기 배열 후 수동 마무리;
• 정보를 저장하고 인쇄합니다.

개체의 자동 배포(프로그램은 일반적으로 40~70%로 정렬) 후에는 정렬되지 않은 나머지 개체를 전달하는 것뿐만 아니라 수업 일정에 대한 위생 요구 사항을 고려하는 것이 거의 불가능합니다. , 또한 "단순히 정렬하기 위한 것"이라는 원칙에 따라 객체의 자동 배열을 크게 변경(최대 60%)합니다.

따라서 현실적으로 실현 가능한 위생 및 교육적 요구 사항과 교육 기관의 특성을 고려하여 컴퓨터 프로그램을 사용하여 합리적인 일정을 만드는 경우 위에서 제안한 알고리즘을 사용하여 과목을 단계적으로 배열해야 합니다. 이 경우 개체 그룹을 배열하는 각 단계는 위의 요구 사항에 중점을 두고 수동 마무리로 끝나야 합니다. 이를 통해보다 합리적인 일정을 만들고 가능하다면 필요한 모든 조건을 고려할 수 있습니다.

일정 변경 절차

학교 일정 조정 알고리즘

학기 중에 일정을 변경해야 하는 경우가 자주 발생하는데, 테이블 레이아웃을 사용하여 작업해야 합니다. 일정을 변경하려면 다음 계산과 재배열을 수행해야 합니다.

제안된 일정 생성 방법은 평소보다 시간이 더 걸리지 않지만 일정을 올바르게 생성할 수 있습니다. 즉:

• 보다 합리적인 학교 일정을 만들기 위해 자신만의 과목 수용 가능성(난이도 및 지루함) 척도를 만드세요.
• 학교 부국장의 관점에서 필요한 정보를 충분히 많이 유지하십시오.
• 매일 수업을 균등하게 배분합니다(7번째 수업을 너무 많이 하지 마세요).
• 학생들은 매일 같은 시간에 수업을 시작하므로 동일한 리듬으로 학습할 수 있도록 첫 번째 수업부터 모든 수업을 시작합니다.
• 학생의 주간 수행 역학에 따라 수업일의 난이도를 조절합니다.
• 교사 작업의 리듬을 유지하고 유리한 작업 환경을 조성할 수 있도록 사실상 "창"이 없거나 최소한의 수로 수업을 준비합니다.
• 서로 다른 방향의 합리적으로 대체되는 개체;
• 필요한 이중 수업을 합리적으로 준비합니다.
• 생산 요구에 따라 일정을 신속하게 변경하고 조정합니다.

또한 이 방법에는 상당한 양의 종이 공백(추가 테이블, 특히 학교에 2학년 및 3학년 수업이 많은 경우(30개 이상))이 필요하지 않습니다.

특정 교육기관의 역량에 맞는 수준 높은 일정을 준비하기 위해서는 각 과목별 난이도와 지루함을 스스로 진단하는 것이 필요하다. 어떤 과목이 어렵고 지루한지 그들보다 더 잘 말할 수 있는 사람은 없기 때문에 학생들은 이 경우 전문가가 되어야 합니다.

학교 일정의 위생 평가 기준

1. 수업수 초등학교 – ______.

2. 수업 수 메인 및 고등학교 – ___________.

3. 수업에 사용된 총 교실 – ___________.

4. 귀하의 교육 기관에 대한 수용 규모의 가용성:

5. 학교 커리큘럼의 과목 수용 범위를 고려하면 다음과 같습니다.

6. 학생들을 위한 일일 수업 분포:

7. 모든 수업은 첫 번째 수업으로 학습을 시작합니다.

8. 다양한 방향과 복잡성의 주제를 합리적으로 교체:

9. 일정에 따른 학생 성과 준수(주간 역학):

10. 교사를 위한 합리적인 수업 배치:

11. 최대 금액하루에 선생님의 수업:

a) 최대 4회 ​​수업 –____ 교사 대상 – ______(%);

b) 5회 및 6회 수업 - ____ 교사 - _____ (%);

c) 7회 이상 - ___ 교사 - ___ (%).

12. 사용 가능한 체계적인 날짜(교사 수 표시):

a) 주당 최대 24시간의 업무량 –____ 교사의 경우

b) 주당 25~30시간의 작업량 - ___ 교사의 경우;

c) 주당 30시간 이상의 작업량 – ___ 교사용.

1. 5학년부터 11학년까지의 사물 이름이 적힌 세트를 준비하세요.
2. 학생들에게 과목 이름 카드와 답안지 세트를 제공합니다.
3. (일기를 사용하여) 이 수업에서 공부하는 과목의 이름이 적힌 카드를 선택하도록 제안합니다.
4. 물체의 "난이도" 개념을 명확히 합니다.
5. 순위별로 각 과목의 난이도를 독립적으로 결정하도록 제안합니다. 주제의 난이도를 내림차순으로 카드를 배치합니다(카드를 위에서 아래로 놓습니다. 즉, 가장 어려운 주제가 있는 카드가 맨 위에 있고, 아래가 덜 어려운 카드입니다.)
6. 답안지에 결과 항목 배열을 기록하십시오.
7. 그런 다음 사물의 “지루함”에 대한 개념을 분석하고 명확하게 합니다.
8. 유사한 순위 절차를 수행하고 결과 정렬을 답안지에 기록합니다.
9. 답안지를 수집하고 처리합니다(아래 요약표 양식 참조).

– 어디에: mk – 평점한 수업의 주제에서;

n - 연구 중인 병렬 클래스 수

또는 다음 공식으로:

– 여기서: Mk – 한 과목의 과목 점수 합계;

n – 연구에 참여하는 동일한 병렬 학생의 수.

예를 들어 7학년 병렬에는 5개 학급이 있고 130명이 진단에 참여했습니다. 병렬로 러시아어 포인트의 합은 469였습니다. 숫자를 공식으로 대체합니다.

수요일 비. pr. = (469/130) = 3.61 – 7학년 러시아어 평균 점수는 3.61이었고, 아이들은 이 과목을 상당히 어렵다고 인식합니다.

같은 방법으로 피험자별 피로도 평균점수를 별도로 계산한다.

그런 다음 각 과목의 평균 합격 점수를 찾습니다. 이를 위해 평균 난이도 점수와 평균 지루함 점수라는 두 가지 지표를 합산한 다음 그 결과를 2로 나눕니다. 이를 통해 해당 과목의 평균 수용성 점수가 제공됩니다.

얻은 데이터를 기반으로 특정 교육 기관의 과목 자격에 대한 개별 표가 각 평행선에 대해 작성됩니다.

응답 처리를 위한 피벗 테이블 양식

부록 2

주간 학습시간 순위
다양한 수업에서 학생들의 성취도 수준에 따라

1 – 가장 유리한 시간 10 - 가장 불리합니다.

6–7 – 수행 수준 감소(수업 진행에 불리한 시간).

8–10 – 낮은 수준의 성과(수업 진행에 불리한 시간)

교사의 주간 업무량 분포표

부록 3

수업일정표의 레이아웃을 실행하는 기술

레이아웃을 완성하려면 다음을 준비해야 합니다.

• 판지 4장(두께 1–2 mm, 높이 – 42 cm, 너비 – 22 cm, 행 높이 – 0.8 cm, 열 너비 – 1 cm)*;
• 밀도가 200g/cm2이고 크기가 판지 시트와 유사한 색종이(연한 색상이 바람직함) 4장;
• 넓은 투명 테이프;
• 판지를 폴더에 붙이기 위한 lederin(종이 비닐)(너비 4~5cm, 길이 49~50cm의 리본)
• PVA 접착제(“silakra”와 같이 매우 강함).

레이아웃 실행 알고리즘

1. 판지 시트를 "조개 껍질"에 붙입니다.

2. 일정을 만드는 데 필요한 모든 정보를 색종이 한 장에 놓습니다(1번 판지에 놓습니다). 예: p.의 표 27.

3. 다음 두 장의 색종이에 각 시트에 3일씩, 하루에 7셀씩 격자를 그립니다(판지의 두 번째와 세 번째 시트에 배치).

4. 4번째 시트에는 일자로 나누지 않고 연속된 격자를 그립니다. (셀의 크기는 비슷합니다.)

5. 세포를 절단할 때 찢어지지 않도록 완성된 시트를 테이프로 덮습니다.

6. 셀에 0.5~0.6cm 크기의 슬릿을 만듭니다.

7. 종이 시트를 골판지 시트의 측면을 따라 완성된 "조개 껍질"에 붙입니다. 레이아웃이 준비되었습니다.

8. 수업 문자(5번째 A, 7번째 "G" 등)로 다색 태그를 별도로 제작합니다. 주 5일 또는 6일 수업량에 따른 수량 + 수업이 나누어지는 수업의 경우 추가 하위 그룹으로. 태그 크기: 너비 – 8mm; 높이 - 15mm.

9. 각 교사의 주간 업무량을 계산하기 위해 성적표가 없는 모든 색상의 태그를 준비합니다. 치수: 폭 5mm; 높이 12-14mm.

이 레이아웃은 필요한 모든 정보가 항상 부국장의 눈앞에 있기 때문에 사용하기 편리합니다. 폴더로 접을 수 있어 휴대가 간편합니다. 이 경우 태그는 슬롯에 고정됩니다.

일정 작성에 필요한 정보

____________ * 판지 시트의 치수는 개별적입니다. 왜냐하면... 각 학교마다 교사 수와 근무 시간(주 5일 및 6일)이 다릅니다. 우리는 주 6일 수업과 교사가 50~55명인 학교를 기준으로 일정 규모를 제안합니다.

Schweik 자신이 깨뜨린 침묵이 지배했습니다.
- ... 군복무에는 규율이 있어야 합니다. 규율이 없으면 누구도 그 원인에 대해 손가락 하나 까딱하지 않을 것입니다. 우리 중위 Makovets는 항상 이렇게 말했습니다. “바보들아, 징계는 필요하다. 규율이 없으면 원숭이처럼 나무에 오르게 될 것입니다. 병역그는 당신을 두뇌 없는 바보로 만들 것입니다!” 글쎄요, 그렇지 않나요? 예를 들어 찰스 광장에 사각형이 있고 각 나무에는 아무런 규율도 없이 한 명의 군인이 앉아 있다고 상상해 보십시오. 정말 겁이 나요.
야로슬라프 하셰크좋은 군인 슈바이크의 모험

수업 일정은 분야(과목), 교사(교사), 청중 및 학생 그룹(하위 그룹, 스트림)의 공간과 시간의 조합입니다.

문제의 공식화

간단히 말씀드리겠습니다.

• 수업 중에는 참가자가 결석할 수 있습니다. 예를 들어 부서 회의, 학생은 원칙적으로 오지 않거나 학생이 출근했습니다. 군부(자체 일정이 있습니다) 이러한 유형의 수업에는 규율, 교사 및 청중이 없습니다.
• 일반적으로 연속성(창 없음)은 학생에게 꼭 필요한 요구 사항이며 교사에게는 바람직합니다.
• 한 학기/반학기 단위로 주별, 2주별, 분자/분모(홀수주/짝수주)로 일정을 편성할 수 있습니다. 월별 일정도 있습니다.
• 클래스는 수동 모드(즉, 편집기)에서 설정할 수 있어야 합니다. 예를 들어 학회나 큰 상사 부부, 심지어는 그냥 좋은 사람의 직업까지.
• 수업에 참여하는 모든 참가자에 대한 금지 시스템이 있어야합니다. 예를 들어, 이제 거의 모든 교사가 부업으로 돈을 벌거나 (그렇지 않으면 살아남을 수 없습니다) 교실 기금이 교수진간에 나누어지고 점심 식사 후에 교실의 일부에서 수업을 열 수 없습니다.
• 선생님들의 세련된 소망이 존재해서 한 분은 하루에 5교시를 줘서 다른 날은 여유를 갖게 하고, 다른 한 분은 하루에 2교시 이상 안 줘서 피곤해지고, 강의가 있으면 한 학급은 꼭 2학년이나 3학년.
• 다른 건물의 수업은 수업 간 쉬는 시간보다 전환하는 데 더 많은 시간이 필요합니다. 움직임을 최소화하는 조건도 자연스럽다.

결론. 성명서에서 볼 수 있듯이 일정이 완전히 편집된 후에만 일정의 품질을 평가할 수 있습니다. 따라서 유전자 알고리즘을 사용하면 원하는 문제에 대한 솔루션을 구성하고 어떤 의미에서는 좋은 솔루션 중 하나를 얻을 수도 있습니다. 동시에 유전자 알고리즘은 처음에는 매우 빠르게 최적의 알고리즘으로 수렴하므로 입력 데이터의 양에 실질적으로 제한이 없습니다.

사진은 여기에서 찍은 것입니다.

유전 알고리즘

순전히 수사적으로 유전자 알고리즘의 주요 단계를 반복하겠습니다.

1. 모집단 내 개인에 대한 목표 기능(피트니스) 설정
2. 초기 모집단 만들기
3. (사이클 시작)
   1. 번식(교배)
   2. 돌연변이
   3. 모든 개인에 대한 목적 함수의 값을 계산합니다.
   4. 새로운 세대의 형성(선택)
   5. 중지 조건이 충족되면 루프가 종료되고 그렇지 않으면 루프가 시작됩니다.

유전자 알고리즘을 사용할 때 가장 흔히 발생하는 오류는 유전자 선택에 있습니다. 종종 선택된 유전자는 단순히 해결책 그 자체일 뿐입니다. 유전자의 선택은 유전자 알고리즘을 만들 때 가장 중요하고 창의적인 요소입니다. 개인적으로 저는 유전자의 선택은 다음 두 가지 기본 요건을 충족해야 한다고 믿습니다.

1. 유전자 세트를 기반으로 원하는 문제에 대한 솔루션을 신속하고 명확하게 구성해야 합니다.
2. 교배되면 자손이 물려받아야 합니다. 캐릭터 특성부모.

코멘트. 유전자 세트는 문제에 대한 (아마도 최적의) 솔루션 전체 세트를 제공해야 합니다. 원칙적으로 일대일을 요구할 필요는 없으며, 솔루션 공간에 유전자를 매핑하는 것만으로도 충분합니다. ~에(추측).

스케줄링 알고리즘

유전자 자체, 이를 기반으로 솔루션을 구성하는 알고리즘, 교배 및 돌연변이에 대해서만 설명하겠습니다.

숙련된 파견자가 일정을 잡는 방법. 경험이 있다는 단어는 배치 담당자가 이미 일정을 한 번 작성했으며 병목 현상을 알고 있음을 의미합니다. 예를 들어 대규모 스트리밍 청중이나 컴퓨터 수업이 부족합니다. 첫 번째 과정은 스트리밍 강의가 많고 동시에 컴퓨터 수업의 하위 그룹 수업, 영어/처음부터 영어/독일어/프랑스어 등이 있기 때문에 당국에서는 어떤 경우에도 첫 번째 과정에 창문이 없고 하루에 2개 이상의 강의가 있었고, 날짜도 균등하게 찼습니다. 따라서 숙련된 파견자는 먼저 "협소한 수업", 요청에 따라 당국의 수업, 특히 성가신 교사의 수업을 준비합니다. 그리고 정해진 수업을 뼈대 삼아 빠르게 일정을 완성한다. 어떤 의미에서 이 과정을 모방해 봅시다.

일부 수업은 이미 우리 일정에 포함되어 있으며 나머지 수업은 순차적으로 번호가 매겨집니다. 여기서는 원칙적으로 직업 순서만 중요하지만 직업 번호 배열을 게놈으로 간주하겠습니다. 일정을 구성하기 위해 순차적으로 학급 번호를 추출하고 선택한 학급을 일정에 올려 필요한 요구 사항을 충족하고 학생, 교사, 청중을 위한 목적 함수를 최대화합니다(채용 기준도 있음).
필요한 요구 사항을 충족할 수 없는 경우 해당 게놈을 가진 개인은 생존 불가능한 것으로 간주되어 폐기될 수 있습니다. 일정을 생성할 수 없는 경우 목적 함수에서 필요한 요구 사항을 페널티로 대체할 수 있습니다.

횡단은 여러 가지 방법으로 구성될 수 있습니다. 예를 들어 그중 하나입니다. 다음과 같은 유전자를 가지자

3 1 2 5 6 4 7
2 3 5 7 1 4 6

여기에서 활동 3이 두 유전자 모두에서 위치 2까지 발생하고 예를 들어 위치 2에서 위치 5까지 1개의 활동에 대한 간격이 있음을 볼 수 있습니다. 다음 기호를 만들어보자

_ * * * * _ _ 1회 레슨
* * * _ _ _ _ 2과의 경우
* * _ _ _ _ _ 3과의 경우
_ _ _ _ _ * _ 4과의 경우
_ _ * * _ _ _ 5과의 경우
_ _ _ _ * * * 6과의 경우
_ _ _ * * * * 7과의 경우

여기서 별표는 자손의 직업 번호에 대한 가능한 위치를 나타냅니다. 이러한 부모의 자녀로서 하나 이상의 가능한 솔루션 중에서 선택할 수 있습니다. 후손의 유전자를 선택하는 데에는 항상 해결책이 있습니다. 예를 들어 두 부모 모두가 이를 만족시킵니다. 가능한 위치 세트를 통해 테이블을 다시 작성해 보겠습니다.

1개 위치(2, 3)
2위(1, 2, 3)
3번째 위치(1, 2, 5)
4번째 위치(1, 5, 7)
5위치(1, 6, 7)
6위(4, 6, 7)
7위치(6, 7)

솔루션을 구성하려면 다음 알고리즘을 사용할 수 있습니다. 먼저 덜 일반적인 클래스 수를 입력하겠습니다. 오름차순으로 정렬하면,
1번 4
2배 3.5
3번 2, 6
4번 1, 7
따라서 먼저 레슨 4를 6번째 위치에 배치하고, 그 다음 레슨 3 또는 5를 각각 (1, 2) 또는 (3, 4) 위치에 배치합니다. 각 단계에서 성냥 상자를 던질 수 있습니다. 결과적으로 교차 알고리즘에 대해 예를 들어 다음 단계를 얻을 수 있습니다.

* * * * * 4 *
3 * * * * 4 *
3 * * 5 * 4 *
3 * * 5 * 4 6
3 * 2 5 * 4 6
3 * 2 5 7 4 6
3 1 2 5 7 4 6

올바른 시퀀스가 ​​구성되지 않을 수 있으므로 알고리즘을 반복할 수 있도록 단순 재귀 형태로 알고리즘을 구성하는 것이 좋습니다. 일부 검색을 구성합니다.

돌연변이는 직업 번호를 무작위로 재배열함으로써 매우 간단하게 구성될 수 있습니다.

결론

이것은 어떤 의미에서 대학에서 수업을 예약하고 부서의 작업량을 계산하기 위한 내 게시물 프로그램의 연속입니다.

나는 다시 다음 해결책(스케치)을 제안합니다.

• PyQt 또는 PySide의 GUI
• PosgreSQL DBMS(여기서 약 80%가 준비되어 있음) 일정 자체 외에도 애플리케이션 및 교사 작업량, 커리큘럼 등도 포함되어 있습니다(이 목적을 위해 하나 이상의 주제를 게시할 예정입니다)
• CherryPy+Cheetah의 웹 인터페이스(그러나 이에 대해서는 논의할 수 있음)
• ODFPY를 통해 OpenDocument 형식(GOST R ISO/IEC 26300-2010. Gosstandart of Russia(06/01/2011))으로 보고서(일정, 교육 과제 카드 등) 내보내기
• 나에게 스케줄링 알고리즘을 알려줘(이 주제는 그것에 관한 것임)
• 나에게서 생산
• 관심 있는 분들은 공통핵심에 대해 연구해 보세요.
• 관심 있는 사람들을 위해 자신의 대학에 적응하고 모든 것을 유연하게 변경할 수 있는 능력이 있으면 삶은 계속되고 공무원은 잠들지 않습니다.

응답해주신 모든 분들께 감사드립니다. 이 주제에 대해 논의한 후 정리가 가능할 것입니다.

최근 여기에 수업 스케줄링이라는 주제가 등장했는데, 저는 대학의 스케줄링 알고리즘을 구축한 경험, 아니 오히려 제가 사용한 휴리스틱에 대해 좀 더 이야기하고 싶었습니다.

얼마 전인 2002년, 저는 한 대학(MESI 야로슬라블 분교)에서 '경제 응용정보학'을 전공하고 졸업할 때, 선택의 과제에 직면했습니다. 명제. 제안된 주제 목록은 우울했고 대부분 지루한 데이터베이스 개발이었습니다. 원칙적으로 나는 머리가 제안한대로 기존 개발 중 일부를 기초로 삼을 수 있습니다. 학과인데 피가 끓고 있어서 흥미롭고 새로운 일을 하고 싶었어요. 특히 저는 대학의 IT 서비스 분야에서 근무하고 Yaroslavl 회사의 제품인 KIS UZ 시스템(교육 기관 관리 통합 정보 시스템)을 담당했기 때문에 일정 관리 주제를 관리자에게 제안했습니다. KIS UZ는 좋았지만 스스로 일정을 만들 수는 없었습니다. 또한 이를 통해 유용한 일을 하겠다는 목표를 추구했지만 이를 구현하려는 시도가 없다는 것이 밝혀졌습니다. 아마도 Habré에 게시하면 누군가에게 도움이 될 것입니다.

따라서 가능한 한 최선을 다해 주간 수업 일정을 작성하도록 컴퓨터를 가르쳐야했습니다. 검색 공간의 규모를 깨닫고 최선의 옵션을 찾는 목표를 설정하지 않았습니다. 먼저 클래스가 무엇인지, 무엇이 좋고 무엇이 나쁜지 결정해야 합니다. 다음 입력 데이터가 있는 다음 모델이 선택되었습니다.
- 일주일의 일수
- 하루 수업 횟수
- 교사 목록
- 그룹, 하위 그룹 및 스레드 목록
- 특정 유형별 청중 수
- 일련의 작업(활동) 그룹:

• 수업
• 선생님
• 스트림 또는 그룹
• 청중 유형
• 이 수업 그룹의 수업 수
• 감독이 이 활동을 특정 시간에 "단단히" 설정하고 싶다면

이 과정에서는 시간표, 즉 일정에 따라 수업을 배열해야 합니다. 일정을 평가하는 데에는 그룹과 교사의 일정에 포함된 "창"의 수, 그룹과 교사의 요일별 수업 균등 분배 등 4가지 매개변수가 포함됩니다. 이러한 매개변수의 중요성은 감독이 설정합니다. 처음에는 목적함수에서 계층구조를 분석하는 방법을 적용하고 싶었지만 이러한 매개변수의 쌍별 비교를 도입해야 했기 때문에 선형함수를 사용했습니다.

강의실은 단순화하여 일정에서 제외하여 제한하였고, 검색 시 특정 시간의 무료 강의실 수를 고려하여 검색하였습니다. 시간에 맞춰 일정을 생성한 뒤 관객을 배치했다. 일반적으로 이것은 내가 설명한 간단한 모델입니다. 유전자 알고리즘을 조금 실험해보고 낮에는 라이브러리를 기반으로 프로그램을 스케치했지만 결과가 마음에 들지 않아 두 번 생각하지 않고 다른 알고리즘으로 전환했습니다. 내 생각엔 근거 없는 접근 방식 때문에 나쁜 결과가 나온 것 같은데, 아마도 GA 측면에서 모델을 코딩하는 데 실패했을 가능성이 높습니다. 나는 분기 및 바인딩 방법에 대해 생각하기 시작했습니다. 검색 공간은 트리로, 레벨은 직업을 나타내고 분기는 시간 그리드 요소를 나타냅니다. 일정은 트리 루트에서 매달린 꼭지점 중 하나까지의 경로로 간주됩니다. 그 과정에서 분기 과정에서 교사의 바쁜 정도, 그룹, 평가 등 다양한 기준에 따라 우회 가능성과 타당성을 확인합니다. 자연스럽게 깊이 나무를 우회합니다. 각 레벨에는 현재 작업을 위한 여유 그리드 셀이 있습니다. 감독이 특정 시간 동안 주어진 작업을 "엄격하게" 할당하면 특정 시간에 해당하는 하나의 분기가 구축됩니다. 또한 지점을 통과하면 상한선의 추정치가 발견됩니다(또한 무료 청중이 있는지 모니터링됩니다) 이런 유형의), 그리고 상한의 추정치가 현재 발견된 최상의 일정의 추정치보다 높으면(그리고 이 유형의 무료 청중이 있는 경우) 분기를 따라 이동하고, 그렇지 않으면 다음 분기로 이동합니다. 분기 및 경계 방법에서 핵심이자 중요한 점은 상한 추정치를 찾는 알고리즘입니다. 더 이상 고민하지 않고 현재 불완전한 일정을 평가하고 현재 발견된 최적의 일정과 비교했습니다. 더 나아가서 불완전한 일정의 추정치가 더 나빠질 것이므로 이미 최적의 일정의 추정치보다 더 나쁘면 분기가 거부됩니다. 그래서 모든 것을 프로그래밍하고 데이터를 준비한 후 (실제 데이터를 기반으로 시스템에서 가져옴) 저녁에 실행하고 집에갔습니다. 아침에 출근하면 UZ CIS에서 찾아낸 10억개의 스케줄 중 베스트를 올렸는데 눈물 없이는 볼 수 없었다. 나는 실망하고 낙담했으며 다음에 무엇을 해야 할지 몰랐습니다. 저녁에는 친구들과 맥주를 마시러 갔는데 지금은 정류장에 서서 술에 취해 막차를 기다리고 있는데 머리 속에는 나무들, 가지들, 경계들, 추정들만... 그러다가 새벽이 온다. 나에게는 어떻게든 각 수준에서 분기를 결정할 때 분기를 정렬하고 다른 옵션보다 가장 좋은 일정에 포함될 가능성이 높은 옵션이 먼저 가도록 해야 합니다. 하지만 어떻게 해야 할까요? 벌써 두 번째 담배를 피우고 있을 때 이런 생각이 들었습니다. 먼저, 일정의 주제별로 자신만의 이상적인 일정을 수립하고, 각 지점별로 이러한 일정에 포함되는 정도를 계산하여 정렬하는 것이 필요합니다. 아침에는 평소보다 더 빨리 출근하면서 머릿속에 기술적인 세부 사항을 그리며 점심 시간에는 휴리스틱이 내장되었고 결과는 UZ CIS에서 상당히 괜찮아 보였고 남은 근무일 절반 동안 미소를 지었습니다. .

추신. 나중에 PageRank에 대해 들었을 때 이런 휴리스틱과 비슷한 것이 있다고 생각했습니다.

여기서 읽은 내용의 대부분은 말도 안되는 내용입니다. 그럼에도 불구하고 어떤 곳에서는 상식적인 생각이 있는 것 같은데 아쉽게도 그런 곳은 그리 많지 않습니다.ㅋ 스케줄링 이론의 문제를 진지하게 연구하는 곳에서는 이 문제를 받아들일 생각조차 하지 마세요. 이보다 더 나은 글을 쓰고 싶은 사람이라면 Hu의 책을 읽어볼 것을 적극 권장합니다. T. "정수 프로그래밍 및 네트워크의 흐름" 또한 N.M.의 최적화 이론에 대한 VMiK 강의를 읽어 볼 가치가 있을 것입니다. Novikova(인터넷 어디에 있는지 기억이 나지 않습니다). 지금은 최적화 이론 문제에 대해 적극적으로 연구하고 있으므로 이 주제에 관심이 있는 사람이라면 누구나 언제든지 기꺼이 이야기를 나눌 수 있습니다. 쓰다 [이메일 보호됨].

소개. 8

1. 기술 분야에 대한 설명. 10

1.1. 스케줄링 문제의 공식화. 10

1.1.1. 스케줄링 문제의 일반적인 공식화. 10

1.1.2. 교육 세션 일정에 적용되는 일정 작성 작업 공식화. 열하나

1.2. 기존 소프트웨어 분석...12

1.3. 문제의 공식화. 15

2. 자동 스케줄링 시스템의 수학적 모델 개발 및 실제 구현. 16

2.1. 대학 시간표의 수학적 모델. 16

2.1.1. 표기법. 16

2.1.2. 변수. 18

2.1.3. 제한. 19

2.1.4. 대상 기능. 21

2.2. 문제 해결 방법. 22

2.2.1. 완전 정수 알고리즘. 23

2.2.2 직접 정수 프로그래밍 알고리즘. 28

2.2.3. 초기 허용 기준을 얻는 기술. 32

2.3. 시스템의 실제 구현 특징 .. 36

2.3.1. 모델 선택. 36

2.3.2. 입력정보에 대한 설명입니다. 39

2.3.3. 작업에 대한 정보 지원 개발. 41

2.3.4. 제한 형성의 특징 수학적 모델작업 예약. 44

2.4. 프로그램의 결과.. 45

2.5. 얻은 결과 분석. 49

결론... 50

문학. 51

부록 1. 스케줄링 시스템용 소프트웨어 제품의 기능. 52

부록 2. 자동 스케줄링 문제를 해결하기 위한 방법의 소프트웨어 모듈 목록. 61

소개

대학 전문가 훈련의 질, 특히 과학적, 교육적 잠재력 활용의 효율성은 교육 과정의 조직 수준에 따라 어느 정도 달라집니다.

이 프로세스의 주요 구성 요소 중 하나인 수업 일정은 업무 리듬을 조절하고 교사의 창의적 성과에 영향을 미치므로 제한된 노동 자원(교직원)의 사용을 최적화하는 요소로 간주될 수 있습니다. 일정 개발 기술은 노동집약적인 기술적 과정, 컴퓨터를 이용한 기계화, 자동화의 대상일 뿐만 아니라 최적의 관리를 위한 행위로 인식되어야 한다. 따라서 이는 명백한 경제적 이익이 있는 대학에서 최적의 수업 일정을 개발하는 문제입니다. 교육 과정에 참여하는 사람들의 관심사가 다양하기 때문에 일정을 만드는 작업은 여러 기준을 따릅니다.

일정 작성 작업은 해당 프로그램의 사용이 종료되는 학기 초에 수업을 기계적으로 배포하는 기능을 구현하는 일종의 프로그램으로만 간주되어서는 안 됩니다. 더 많은 경제적 효과 효과적인 사용노동 자원은 이러한 노동 자원을 관리하는 노력의 결과로만 달성될 수 있습니다. 여기서 일정은 이러한 관리를 위한 도구일 뿐이며, 최대한 활용하려면 최적의 일정을 생성하는 수단뿐만 아니라 일부 입력 데이터가 변경되는 경우 최적성을 유지하는 수단도 프로그램에 결합해야 합니다. 일정을 작성할 당시에는 일정한 것으로 간주되었습니다. 또한 시스템에서 발생하는 프로세스에 대한 일부 통계 정보가 축적되지 않으면 이러한 복잡한 시스템의 최적 제어가 불가능합니다. 따라서 최적의 일정을 만드는 작업은 복잡한 교육 과정 관리 시스템의 일부일뿐입니다.

이 문제의 다중 기준 특성과 수학적 모델이 구축된 객체의 복잡성으로 인해 모델을 크게 복잡하게 하지 않고 스케줄링 알고리즘의 기능을 향상시키기 위해 객체에 대한 진지한 수학적 연구가 필요하며 결과적으로 양을 늘리지 않아도 됩니다. 사용된 메모리의 양과 문제를 해결하는 데 필요한 시간입니다.

1. 기술 분야 설명 1.1. 스케줄링 문제의 공식화

일반적인 공식화에서 스케줄링 이론의 문제는 매우 매력적인 것으로 간주되지만, 솔루션을 향한 작은 진전이라도 달성하는 것은 일반적으로 엄청난 어려움과 관련됩니다. 많은 우수한 전문가들이 스케줄링 이론의 문제를 다루었음에도 불구하고 지금까지 어느 누구도 중요한 결과를 얻을 수 없었습니다. 일반적으로 그러한 결과를 얻으려는 실패한 시도는 게시되지 않으며 이는 부분적으로 문제가 명백한 공식화 단순성으로 인해 많은 연구자의 관심을 계속 끌고 있다는 사실에 부분적으로 기인합니다.

1.1.1. 스케줄링 문제의 일반적인 공식화

가장 일반적인 공식에서 스케줄링 작업은 다음과 같습니다. 특정 리소스 세트 또는 서비스 제공 장치의 도움으로 특정 고정 작업 시스템을 수행해야 합니다. 목표는 작업 및 리소스의 속성과 이에 부과된 제한 사항을 고려하여 필요한 효율성 척도를 최적화하거나 최적화하는 경향이 있는 작업을 정렬하기 위한 효과적인 알고리즘을 찾는 것입니다. 효율성의 주요 척도는 일정 기간과 시스템 내 작업의 평균 체류 시간입니다. 이러한 문제의 모델은 순서 결정의 기초가 되는 모든 정보가 미리 알려져 있다는 점에서 결정론적입니다.

1.1.2. 교육 세션 일정에 적용되는 일정 작성 작업 공식화.

일반 스케줄링 이론은 모든 서비스 장치(또는 프로세서)가 주어진 시간에 하나 이상의 작업을 수행할 수 없다고 가정합니다. 이는 작업을 분배할 때 교실을 프로세서로 간주하는 경우 교육 수업 일정을 잡는 데 충분하지 않습니다. 따라서 어떤 경우에는 여러 스트림에 대한 일반 강의와 같이 동시에 두 개 이상의 그룹으로 구성된 수업이 하나의 강의실에서 진행될 수 있습니다.

따라서 일반 일정 이론을 훈련 일정으로 전환할 때 다음과 같은 가정이 이루어졌습니다.

모든 프로세서(즉, 교육 일정의 경우 교실)에는 특정 숫자 C ≥ 1의 용량이 있습니다. 프로세서의 용량은 주어진 시간에 동시에 "처리"할 수 있는 작업 수를 결정합니다. 프로세서의 비단일성과 관련하여 프로세서가 청중이 아니라 교사이고 작업이 그가 함께 일하는 하나 이상의 교육 그룹의 흐름인 경우 옵션을 고려하는 것이 흥미로울 것입니다.

배포 작업 세트에는 스터디 그룹과의 교사 교육 세션이 포함됩니다.

시스템의 시간 모델은 이산적입니다. 전체 분포는 특정 시간 간격에 걸쳐 주기적으로 반복되는 것으로 가정됩니다.

모든 작업은 동시에 완료되며 이는 시간 간격의 이산화 단위로 간주됩니다.

과제는 스터디 그룹과 교사라는 개체에 속합니다.

결과적으로 교육 세션 예약 문제의 공식화는 다음과 같습니다. “주어진 강의실 세트에 대해(이 경우 강의실은 교육 세션이 진행되는 광범위한 공간(컴퓨터실에서 체육관)) 및 주어진 시간 간격 세트(즉, 기본적으로 수업 또는 훈련 쌍)를 사용하여 선택된 최적성 기준이 가장 좋은 모든 개체(교사 및 훈련 그룹)에 대한 훈련 세션 분포를 구성합니다."

1.2. 기존 소프트웨어 분석

현재 수업 일정 관리 시스템을 위한 소프트웨어 시장 부문은 다양한 소프트웨어 제품으로 대표됩니다. 표 1은 나에게 알려진 것 중 일부만을 보여줍니다.

객관적인 이유로 대학(대규모 주립 대학을 의미)의 일정 관리 시스템은 반드시 다음과 같은 여러 기본 기능을 구현해야 합니다.

교사의 희망을 고려합니다.

필수 청중 확보

원하는 청중 지정

건물 간 전환을 설명합니다.

모든 분야에 대한 스트림으로 그룹을 결합합니다.

하위 그룹으로 나누기

일정을 작성한 후 필요한 경우 교사를 교체하거나 수업 시간을 변경하십시오.

또한 소프트웨어 제품의 기능에 대한 각 대학의 특정 요구 사항도 있습니다.

제 생각에는 러시아 시장에서 가장 인기 있는 소프트웨어 제품의 기능이 부록 1에 나와 있습니다.

위 목록에서 아마도 "Methodist" 프로그램만이 대학의 일정 관리에 필요한 소프트웨어 제품의 기능과 어느 정도 일치할 것입니다. 이러한 상황은 오늘날 학교 교육이 대학 교육보다 (교육 과정을 조직한다는 의미에서) 더 "표준화"되어 있다는 사실로 쉽게 설명됩니다. 이러한 표준화는 상대적으로 저렴한 가격에 대량의 제품 사본을 판매함으로써 소프트웨어 판매 및 개발 회수를 위한 큰 잠재 시장으로 이어집니다.

대학의 경우, 일정 관리 시스템에 대한 수요는 아마도 학교보다 훨씬 높을 것입니다. 그러나 각 개별 대학의 교육 과정 구성이 매우 특수하기 때문에 문제는 복잡해집니다. 통합 소프트웨어를 만드는 것은 불가능하며, 타사 개발자로부터 특화된 제품을 만드는 데 드는 비용은 터무니없이 높은 것으로 나타났습니다. 또한 전제 조건은 교사 교체 또는 수업 시간 변경 가능성을 전제로하는 "정해진"일정의 존재입니다. 지금까지 이 작업을 매우 간단하게 수행할 수 있는 소프트웨어 제품은 없습니다(Methodist에는 일부 기능이 있지만).

1.3. 문제의 공식화.

이 작업의 목적은 자동 일정 관리 문제를 효과적으로(주어진 시간 범위 내에서, 주어진 최적 수준으로) 해결하고 유연성(사소한 변경)을 가질 수 있도록 하는 대학 일정의 수학적 모델을 만드는 것이었습니다. 입력 정보가 ​​변경된 경우) 특정 내에서 시스템을 조정합니다. 실질적인 문제. 문제를 다소 단순화하기 위해, 첫 단계몇 가지 설계 가정이 이루어졌습니다.

일정은 하루에 두 쌍 이하로 구성됩니다(저녁 수업에 매우 적합함).

모든 쌍은 한 건물에 보관됩니다.

문제는 선형 프로그래밍 측면에서 발생합니다.

모델의 더 이상 분해는 수행되지 않습니다.

모든 모델 계수와 원하는 변수는 정수입니다.

제기된 문제는 정수 선형 계획법의 보편적인(계수의 정수 값과 무관한) 방법 중 하나로 해결되어야 합니다.

2. 자동 스케줄링 시스템의 수학적 모델 개발 및 실제 구현 2.1. 대학 일정의 수학적 모델

선형 프로그래밍 측면에서 대학 일정의 수학적 모델을 구축해 보겠습니다. 표기법을 소개하고 변수와 제약 조건을 정의해 보겠습니다.

2.1.1. 명칭

대학에는 R 스트림으로 결합된 N개의 스터디 그룹이 있습니다. r – 스트림 번호, r = 1, ..., R, k r – 스트림 r의 연구 그룹 번호, k r = 1, ..., G r.

그룹을 스레드로 나누는 것은 다음 원칙에 따라 수행됩니다.

1. 두 그룹의 동일한 강의실 자금을 강의에 사용한다는 것은 자동으로 이들을 하나의 스트림에 배치하는 것을 의미합니다(스터디 그룹의 모든 강의가 함께 진행되는 것으로 가정).

2. 대학의 교육 과정 단위인 그룹(또는 그 일부)은 다양한 스트림에 포함될 수 있지만 각 스트림에는 한 번만 포함될 수 있습니다.

3. 스레드 수에는 제한이 없습니다.

수업은 평일에 1시간 30분 간격으로 진행되며, 이를 쌍으로 부르겠습니다.

다음을 나타내자:

t – 요일의 근무일 수, t Є T kr, 여기서

T kr – 그룹 k r의 근무일 수 세트;

j – 쌍 번호, j = 1 ,…, J;

J – 총 쌍 수.

주중 각 스터디그룹 k r stream r에서는 커리큘럼에 따라 W kr 수업이 진행되며, 그 중 S r 강의와 Q kr 실습이 진행됩니다. 다음을 나타내자:

s r – 스트림 r에 대한 강의 수업 목록의 분야 수, s r = 1,…,S r ;

q kr – 그룹 k r의 실습 수업 목록에 있는 분야 번호, q kr = 1,…, Q kr.

스트림의 모든 그룹에 대한 강의가 동시에 동일한 교실에서 진행된다고 가정합니다. 그런 다음 일주일 동안 특정 분야에서 두 개 이상의 수업을 진행하는 경우 해당 분야는 제공되는 횟수만큼 강의 또는 실습 목록에 언급됩니다. 과정각 스레드 또는 그룹에 대해.

교사

p를 교사의 번호(이름)라고 하고, p = 1,…, P라고 합니다. 부울 값과 다음을 소개하겠습니다.

교사의 교육량은 수업 일정을 작성하기 전에 계획되며, 그 결과 이 ​​단계에서 가치가 부여되는 것으로 간주될 수 있습니다. 각 교사 p, p = 1,…,P에 대해 그의 수업량도 지정됩니다(주당 N p 시간).

청각 기금

각 스트림의 수업은 특정 교실에서만 진행될 수 있습니다. (예를 들어, 컴퓨터 과학의 실습 수업은 디스플레이 수업에서만 열릴 수 있습니다.) 하자:

(A 1 r ) – 스트림 r에 대한 강의를 위한 청중 세트;

(A 2 r) – 스트림 r에 대한 실습 교육을 위한 강의실 세트;

A 1 r – 세트의 요소 수 (A 1 r);

A 2 r – 세트의 요소 수 (A 2 r);

A 1 r + A 2 r – 집합 합집합의 청중 수 (A 1 r )∩(A 2 r ).

관객 기금은 일정이 시작되기 전에 결정되므로 세트를 제공하는 것으로 간주할 수 있습니다.

2.1.2. 변수

일정을 계획하는 작업은 아래에 구성된 제한 사항의 충족과 특정 목적 함수.

다음과 같은 필수 부울 변수를 소개하겠습니다.

=

저녁 수업 그룹을 예약하는 경우 J=2. 모든 형태의 학습에 대한 모델의 일반화는 669페이지를 참조하세요.

2.1.3. 제한

각 그룹 k r에 대해 모든 유형의 교실 작업은 주중에 완료되어야 합니다.

각 강의 s r 및 실습 q kr은 각각 모든 스트림 r 및 모든 그룹 k r에 대해 하루 t에 한 번만 열릴 수 있습니다.

변수가 모든 유형의 활동을 구현 시간과 연결하는 경우 제품은 그리고 그 시간을 선생님의 이름과 연관시키세요.

매일 t와 각 쌍 j에서 교사 p는 한 스트림이나 한 그룹에서 한 분야의 한 수업만 가르칠 수 있습니다.

마지막으로, 각 수업의 매일 강의 및 실습 수업 수는 대학에서 사용할 수 있는 수업 자금을 초과해서는 안 됩니다.

또한 모든 교차 집합 집합(A 1 r) 및 (A 2 r)에 대해 다음 조건을 충족해야 합니다.

제시된 관계는 일정을 작성할 때 항상 고려되는 무조건적인 제한 사항을 소진합니다. 그러나 우선 "상위" 또는 "하위" 주에 특정 유형의 작업을 수행하는 것과 같은 특정 조건이 있을 수 있습니다(예: 주당 1시간). 그 외는 제외되지 않습니다 특별한 조건, 그러나 모델을 단순화하기 위해 고려되지 않았습니다.

2.1.4. 목적 함수

과학적, 교육적, 방법론적 작업을 완벽하게 수행하고 수업을 준비하려면 대학 교사에게 자유 시간이 있어야합니다. 이 조건은 충분하지는 않지만 필요합니다. 분명히 그는 학생과의 수업 사이의 "창"과 같은 "비정형"모드가 아니라 가능하다면 완전히 자유로운 근무일에 자유 시간을 가져야합니다. 이는 교사가 수업을 하는 날 수업량을 최대화하는 것과 동일합니다((5) 참조). 그러나 동시에 교사는 창의적인 잠재력이 다르기 때문에 자유 시간에 대한 불평등한 주장을 가지고 있습니다. 따라서 교사의 해당 상태를 고려해야 하는 가중치 계수를 도입할 필요가 있습니다. 학업 학위직위, 직위, 과학 및 사회 활동 등 어떤 경우에는 전문가 평가를 바탕으로 다른 요소를 고려한 개별 가중치 계수를 사용하는 것이 가능합니다.

따라서 우리는 모든 교사의 수업이 없는 일수를 최대화하는 형태로 수업 일정의 질에 대한 기준을 선택할 것입니다. 이는 고정된 근무 주의 길이를 고려할 때 교실 부하.

교사 p의 t일에 교실 부하 값에 대한 표현식을 고려해 보겠습니다.

여기서 M은 임의의 양수로 충분합니다. 큰 숫자; - 원하는 부울 변수.

(10)에서 if , then = 1, if , then = 0이 됩니다.

추가 제한(10)에서 위의 최적화 기준의 실질적인 의미를 고려하고 교사 상태의 가중치 계수를 도입하여 필요한 최적성 기준을 얻습니다.

도입된 목적 함수만이 가능한 것은 아닙니다. 다른 목적 함수를 도입한다고 해서 문제 해결을 위한 수학적 모델과 방법의 한계가 바뀌지는 않지만 계산 결과에 큰 영향을 미칠 수 있습니다.

2.2. 문제 해결 방법

주어진 제약 시스템 하에서 이전 단락에 제시된 선형 목적 함수를 최대화하는 문제는 선형 정수 부울 프로그래밍 문제입니다. 문제의 초기 데이터의 이산적 특성으로 인해 모든 제약 계수가 정수이기 때문입니다. 또한 수학적 모델의 필수 변수는 두 개의 값만 사용할 수 있습니다. 현재로서는 이러한 유형의 문제를 해결하기 위한 몇 가지 가능한 방법이 있습니다.

B – 정렬된 인덱싱 및 수정된 표시 방법은 원래 모델의 라그랑지안 분해를 기반으로 하여 각각 해결된 여러 단선 문제로 설명되며, 인덱싱 또는 수정된 표시를 정렬하는 방법으로 각각 해결됩니다. 불행하게도 각 방법의 연산 수는 다항식 추정을 허용하지 않습니다. 또한, 방법의 집합 테이블(중간 값)의 차원은 해결되는 문제의 차원이 증가함에 따라 급격하게 증가하는데, 이는 우리의 경우에는 허용되지 않습니다. 특정 수학적 모델에 대한 분해 알고리즘을 변경하면 테이블 크기가 줄어들 수도 있지만 이러한 알고리즘은 아직 존재하지 않습니다.

이러한 점에서 정수 선형 계획법 문제의 경우 단순 방법의 수정에서 설명한 풀이 방법이 선택되었습니다. 안에 일반적인 경우단순 방법의 연산 수는 다항식 추정을 허용하지 않습니다(연산 수가 O(e n)인 문제 클래스도 표시됨). 그러나 우리 문제의 경우 평균 연산 수는 다음을 허용합니다. 다항식 추정: O(n 3 m 1/(n-1 )) (n – 변수 수; m – 제한 수).

2.2.1. 완전 정수 알고리즘

이 알고리즘을 완전 정수라고 부르는 이유는 원본 테이블이 정수 요소로 구성되어 있으면 알고리즘으로 생성된 모든 테이블에는 정수 요소만 포함되기 때문입니다. 이중 심플렉스 방법과 마찬가지로 알고리즘은 이중 허용 테이블에서 시작됩니다. a i 0(i = 1 ,..., n+m; a i 0은 목적 함수의 계수)이 음이 아닌 정수이면 문제가 해결됩니다. 어떤 문자열 a에 대해 i가 0인 경우

정수 선형 계획법 문제를 제시해 보겠습니다.

최대화하다

조건 하에서

조건 (12)는 다음과 같이 쓸 수 있습니다.

t=0(즉, 원본 테이블)의 경우 모든 aij가 정수이고 열(j = 1,...,n)이 사전식으로 양수라고 가정합니다. 그런 다음 모든 열은 계산 전반에 걸쳐 사전순으로 양수를 유지합니다.

생성 문자열에서 추가 제약 조건을 얻는 방법을 제시하기 전에 숫자의 새로운 표현을 소개합니다. [x]는 x보다 크지 않은 가장 큰 정수를 나타냅니다. 임의의 숫자 y(양수 또는 음수) 및 양수에 대해 다음과 같이 쓸 수 있습니다.

여기서 (r y는 y를 로 나눌 때 음수가 아닌 나머지입니다). 특히, . 따라서 이면 r = 1입니다. 이면 r = 0입니다.

도입된 추가 부등식은 문제(12)의 모든 정수 해에 대해 충족되어야 합니다. 0이 포함된 t-테이블(행 인덱스 생략)의 일부 방정식을 고려해보세요.

여기서 x는 벡터의 해당 구성 요소이고 현재 기본이 아닌 변수입니다. 위에서 소개한 표현(14)을 사용하여 x, a 0 및 a j를 표현할 수 있습니다.

식 (16)과 (17)을 (15)에 대입하고 용어를 재배열하면 다음을 얻습니다.

, 및 변수 x 및 는 음수가 아니어야 한다는 요구 사항을 따르므로 방정식 (18)의 왼쪽은 항상 음수가 아닙니다. 중괄호로 묶인 오른쪽 표현식을 살펴보세요. 이 표현식의 계수는 정수이며 변수에는 정수 요구 사항이 적용됩니다. 따라서 괄호 안의 전체 표현식은 정수여야 합니다. 이를 s로 표시해 보겠습니다. 즉:

.

정수 약한 변수 s는 음수가 아닙니다. 실제로 s가 음수라면, 즉 -1, -2, ... 값을 취하고 를 곱하면 방정식 (18)의 오른쪽 전체가 음수가 되고 왼쪽은 음수가 아닙니다.

와 의 두 가지 경우를 생각해 봅시다. 및 . (15)의 x에 대한 표현식을 방정식 (19)로 대체하면 다음을 얻습니다.

문제 (12)에 대한 정수 해를 얻으려면 방정식 (21)이 충족되어야 합니다. 방정식 (21)에서 0인 경우에 유의하십시오. 따라서 식 (21)은 단순법의 선행선으로 사용될 수 있다. 특히 행 (21)의 선행 요소가 –1과 같도록 항상 충분히 큰 값을 선택할 수 있으며, 이는 테이블의 무결성을 유지합니다. 적절한 것을 선택하는 것은 알고리즘의 수렴 속도에 영향을 미칩니다. 먼저 알고리즘 자체에 대해 설명하겠습니다. 초기 솔루션으로, 제약 조건 xn + m+1 =M – x 1 - - … - xn 0(여기서 M은 충분히 큰 상수)을 추가하고 다음을 수행하여 얻을 수 있는 이중 실행 가능한 솔루션을 취하는 것이 필요합니다. 추가된 행과 사전순으로 최소 열을 리더로 사용하여 한 번의 반복을 수행합니다. 알고리즘은 다음 단계로 구성됩니다.

0 단계. 방정식 (13)에서 이중으로 허용되는 행렬 A 0으로 시작합니다. 그 요소는 정수입니다(행렬 A 0에는 정수가 아닌 요소도 포함될 수 있습니다. 이에 대한 내용은 306페이지를 참조하세요).

Step 1. i 0 0 (i=1, ..., n+m)인 행 중에서 문제가 해결됩니다.

Step 2. 선택(선택 규칙은 추후 설명)을 선택하고 표 하단에 추가 라인을 작성합니다.

이 줄이 선행 줄로 선택되었습니다.

3단계. 이중 단순 방법 단계를 수행하고 추가 선을 지우고 1단계로 돌아갑니다.

알고리즘의 유한성에 대한 증명은 303-304페이지를 참조하세요.

선택 규칙은 다음과 같이 공식화됩니다.

0단계. 숫자 v가 있는 행이 생성되도록 합니다.

1단계. vj가 있는 열 중에서 사전순으로 최소 열을 라 하겠습니다.

2단계. 각각에 대해 vj는 (사전순으로 더 작은) 가장 큰 정수입니다.

3단계. a(행 v가 생성됨)를 가정합니다. 그 다음에

.

4단계. vj에 넣기

위에서 설명한 선택 규칙을 사용하면 테이블의 이중 유효성을 유지하면서 선행 요소를 -1로 만들 수 있으며 동시에 null 열은 사전순으로 최대한 줄어듭니다.

2.2.2 직접 정수 프로그래밍 알고리즘

정수 프로그래밍 알고리즘에 적용될 때 "직접"이라는 용어는 연속적으로 "개선 가능한" 솔루션을 얻음으로써 최적의 솔루션으로 이어지는 방법을 나타냅니다. 이러한 각 해는 선형 제약 조건과 정수 조건을 모두 충족한다는 점에서 유효합니다. 알고리즘의 장점 중 하나는 최적의 솔루션을 얻기 전에 계산을 중단하고 얻은 최상의 솔루션을 근사치로 사용할 수 있다는 것입니다. 또한 직접 알고리즘을 이중 알고리즘과 함께 사용하여 이중 실행 가능한 솔루션을 생성하는 단계에서 직접 실행 가능한 솔루션을 생성하는 단계로 이동할 수 있는 다양한 복합 알고리즘을 생성할 수 있습니다.

직접 알고리즘의 자연스러운 선례는 전체 정수 Gomori 알고리즘입니다. 왜냐하면 이 알고리즘의 프로세스는 이중으로 실행 가능한 정수 해의 시퀀스를 생성하기 때문입니다. 완전 정수 Gomori 알고리즘은 쌍대 심플렉스 방법을 수정한 것임을 기억해야 합니다. 이 알고리즘의 주요 차이점은 선행 문자열이 선행 요소가 -1인 Gomori 컷이라는 것입니다. 이 컷은 생성 문자열에서 얻어지며, 이는 이중 심플렉스 방법에서 가능한 선행 문자열 중 하나로 정의됩니다. 이러한 컷을 선행 행으로 사용하면 반복 후 테이블의 이중 유효성과 무결성이 유지됩니다.

테이블의 직접 허용성과 무결성을 유지하는 알고리즘을 얻는 방식으로 심플렉스 방법을 유사하게 수정할 수 있다는 것이 밝혀졌습니다. 계산 절차를 설명하려면 다음 정수 계획법 문제를 고려하십시오.

최대화하다

단순 방법의 반복에서 열이 선행 행으로 선택되고 행 v가 선행 행이라고 가정합니다. a가 0보다 큰 모든 행 I에 대해. 심플렉스 방법에서 가우스 제거 절차를 수행하기 전에 v 행에서 얻은 Gomori 컷오프를 테이블에 추가합니다.

여기서 J는 (22)에서 비기본 변수의 인덱스 집합이고, sk는 새로운(기본) 약한 변수이고 불확정(일시) 양의 상수입니다.

= a vs 로 설정하면 컷오프(23)는 두 개가 됩니다. 중요한 속성. 첫째로,

이는 컷오프(23)를 선행 행으로 사용하면 테이블의 직접적인 유효성이 보존된다는 것을 의미합니다. 둘째, 즉 선행 요소는 1입니다(클립이 선행 문자열로 사용되는 경우). 단일 선행 요소가 있는 단순 테이블의 변환이 단순 테이블 요소의 무결성을 유지한다는 것을 (기본 변수 변경 공식을 검토하여) 쉽게 확인할 수 있습니다.

이러한 아이디어는 정수 프로그래밍에서 직접 알고리즘의 기초가 되었습니다.

0단계. a i 0 0 (i 1)과 모든 요소 a 0 j , a ij 및 a i 0이 정수인 원주형 테이블로 시작합니다.

1단계. 조건 a 0 j 0 (j 1)을 확인합니다. 만족하면 현재 기본 솔루션이 최적입니다. 그렇지 않은 경우 2단계로 이동하세요.

2단계. 0이 0인 선행 열 s를 선택합니다. 이 행은 Gomori 컷의 생성기 역할을 합니다.

3단계. 생성 라인에서 고모리 컷을 가져와 테이블 하단에 추가합니다. 문제 제약 조건에 방정식 (23)을 추가합니다. 여기서 .

4단계. cut (23)을 선행 행으로 사용하여 테이블을 변환합니다. (23)의 약한 변수 sk는 비기본 변수가 됩니다. 1단계로 돌아갑니다.

알고리즘의 유한성에 대한 증명은 346-353페이지를 참조하세요.

생성 문자열을 선택하는 것이 간단한 작업이 아니기 때문에 생성 문자열 역할을 할 수 있는 문자열이 여러 개 있어야 할 것 같습니다. 예비논증에서는 생성선으로 심플렉스법의 선행선을 사용하였다. 이 선은 항상 선행 요소가 1인 선행 선인 컷오프를 생성합니다. 분명히 테이블에는 동일한 속성을 가진 컷을 얻을 수 있는 다른 행이 있습니다. 컷오프가 다음 공식에 따라 구해진다고 가정해 보겠습니다.

조건에 따라 결정되는 곳

조건 (25)를 만족하는 행의 집합으로 집합 V(s)를 정의해 보겠습니다.

다음 두 규칙은 유효한 생성 문자열 선택 규칙의 예입니다.

규칙 1.

1. 각 행의 인덱스가 적어도 한 번 표시되도록 행 인덱스의 순차적인 유한 목록을 구성합니다. 2로 가세요.

2. 목록이 비어 있거나 V(s)의 인덱스가 포함되어 있지 않으면 1로 돌아갑니다. 그렇지 않으면 목록에서 첫 번째 인덱스 v V(s)를 찾습니다. v 행을 생산으로 선택합니다. 목록의 인덱스 v와 이전의 모든 인덱스를 출력합니다. 3으로 가세요.

3. 2.에서 가져온 문자열 v를 v V(s)까지 생성하는 것으로 일관되게 선택합니다. v V(s)가 되면 2로 돌아갑니다.

규칙 2.

1. V t(s)를 다음에 대응하는 집합 V(s)로 설정합니다. t번째 테이블. V t (s)에 두 개 이상의 요소가 포함된 경우: V t (s) = (v 1, v 2, ..., v k +2), 생성기로 일련의 V 1에서 다음과 같은 행을 선택합니다. (s 1), V 2 (s 2), ..., V t (s) 선은 다른 선보다 더 일찍 (늦지 않게) 나타나고 V t (s)까지 유지되었습니다. 2로 가세요.

2. 1.에서 가져온 문자열 v를 까지 일관되게 선택합니다. 일단 1로 돌아갑니다.

2.2.3. 초기 허용 기준을 얻기 위한 기술

위의 각 방법은 선형 계획법 문제가 직접적으로 또는 이중적으로 가능한 경우에만 해결될 수 있습니다. 이러한 허용 가능성은 원래 문제에 초기 허용 가능한 근거가 있음을 의미합니다. 문제가 직접적으로나 이중적으로 모두 가능한 경우 결과 솔루션이 최적입니다. 대부분의 경우 문제를 제기한 후 직접적으로나 이중적으로나 허용되지 않는 것으로 판명됩니다. 따라서 우리는 초기 허용 기준을 얻기 위한 알고리즘을 제시합니다.

선형 계획법 문제를 정식 형식으로 작성해 보겠습니다.

최소화하다

조건 하에서

필요한 경우 해당 방정식에 –1을 곱하여 모든 b i를 음수가 아닌 값으로 만들 수 있습니다. 그런 다음 인공 변수로부터 초기 기초를 형성하는 방식으로 각 방정식에 인공 변수를 추가할 수 있습니다(인공 변수는 음수가 아니어야 합니다).

불평등을 방정식으로 바꾸는 데 사용되는 약한 변수로부터 인공 변수를 파생할 수 있습니다. 실제로 선형 계획법 문제의 초기 제약 조건이 부등식의 형태로 제공되면 다음과 같습니다.

그런 다음 각 부등식에 약한 변수를 추가하면 다음을 얻습니다.

b i 0이면 si를 초기 기본 변수로 사용할 수 있습니다.

인위적인 변수와 약한 변수 s i 의 차이점은 다음과 같습니다. 문제에 대한 최적의 솔루션에서는 원래 문제에는 그러한 변수가 없으므로 모든 인공 변수는 0과 같아야 합니다. 반면에 최적의 솔루션에서는 약한 변수가 양수 값을 가질 가능성이 높습니다. 인공변수가 0이 되기 위해 목적함수는 다음과 같이 표현될 수 있다.

여기서 M i는 충분히 큰 양수입니다. 이 방법의 아이디어는 인위적인 변수에 분명히 높은 가격이 부여된다는 사실에 해당합니다. 이 방법을 사용하면 최적해에서 인공 변수의 값이 0이 됩니다.

초기 허용 기준을 얻는 또 다른 방법이 있습니다. 이 방법에서도 첫 번째와 마찬가지로 초기 기본변수로 인위적인 변수를 사용한다. 인공 변수의 합인 새로운 목적 함수가 고려됩니다. 제약조건 중 하나로 z-방정식을 사용하여 최소화하는 것이 필요합니다. 원래 방정식 시스템에 실행 가능한 해가 있는 경우 모든 인공 변수는 0이 되어야 합니다. 따라서 최소값은 0이 되어야 합니다. 이면 원래 방정식 시스템에는 허용되는 해가 없습니다. 이면 목적함수를 생략하고 z를 최소화하기 위한 초기 실현 가능 기초로 최적의 기초 형태를 사용할 수 있습니다. 문헌에서는 이 방법을 2단계 심플렉스 방법이라고 합니다. 방법의 첫 번째 단계에서는 를 최소화하여 허용 가능한 기저를 찾고, 두 번째 단계에서는 z를 최소화하여 최적의 기저를 얻습니다.

다음 선형 계획법 문제를 예로 들어 보겠습니다.

최소화하다

조건 하에서

여기서 모든 b i는 음수가 아닙니다.

인공 변수와 새로운 목적 함수를 도입하면 다음과 같은 문제가 발생합니다.

최소화하다

,

조건 하에서

-form에서 b i를 포함하는 모든 방정식을 빼면 다음을 얻습니다.

-지

여기서 시스템 (26)은 대각선입니다. 단순 방법의 첫 번째 단계는 조건 하에서 최소화로 구성됩니다(26). z의 부호에는 제한이 없습니다. 계산 과정에서 인공 변수가 기본이 아닌 변수가 되고 -형식의 계수가 양수이면 변수 자체와 해당 열 벡터가 추가 계산에서 제외됩니다.

2.3. 시스템의 실제 구현 기능

실제로 수학적 모델에 정의된 형태의 정보로 작업하는 것은 그리 편리하지 않습니다. 그러므로 우선 데이터를 정리하는 방법이나 데이터 모델을 결정해보자.

2.3.1. 모델 선택

데이터 모델은 시스템 프로세스의 자동화와 관련된 개체 및 개체의 관계에 대한 설명을 형식화하는 방법 및 수단에 대한 일련의 합의입니다. 모델의 종류와 그에 사용되는 데이터 구조의 종류는 해당 모델을 지원하는 DBMS나 데이터 처리 응용프로그램이 생성되는 프로그래밍 시스템 언어에서 사용되는 데이터를 정리하고 처리하는 개념을 반영한다.

이 문제를 해결하기 위해서는 보조 정보의 양을 최소화하고 데이터에 대한 다중 사용자 액세스가 근본적으로 가능하며 보장되는 데이터 모델을 만드는 것이 필요합니다. 높은 레벨데이터 보호.

현재 데이터 모델을 형성하는 데에는 계층적, 네트워크 및 관계형의 세 가지 주요 접근 방식이 있습니다.

계층적 조직 방법

계층적 데이터베이스는 순서가 지정된 트리 집합으로 구성됩니다. 보다 정확하게는 동일한 유형의 트리에 대한 여러 인스턴스의 순서가 지정된 세트에서 나온 것입니다. 트리 유형은 하나의 "루트" 레코드 유형과 0개 이상의 하위 트리 유형(각각 트리 유형임)의 정렬된 세트로 구성됩니다. 일반적으로 트리 유형은 계층적으로 구성된 레코드 유형의 모음입니다.

조상과 자손 사이의 연결 무결성은 자동으로 유지됩니다. 기본 규칙: 부모 없이는 자식이 존재할 수 없습니다. 동일한 계층 구조에 속하지 않는 레코드 간의 유사한 참조 무결성 유지 관리는 지원되지 않습니다.

네트워크 구성 방법

데이터 구성에 대한 네트워크 접근 방식은 계층적 접근 방식의 확장입니다. 계층 구조에서 하위 레코드에는 정확히 하나의 상위 항목이 있어야 합니다. 네트워크 데이터 구조에서 자식은 원하는 수의 조상을 가질 수 있습니다.

네트워크 데이터베이스는 레코드 집합과 이러한 레코드 간의 연결 집합, 보다 정확하게는 데이터베이스 스키마에 지정된 레코드 유형 집합의 각 유형 인스턴스 집합과 데이터베이스 스키마의 각 유형 인스턴스 집합으로 구성됩니다. 주어진 연결 유형 세트.

관계 유형은 조상과 자손이라는 두 가지 유형의 레코드에 대해 정의됩니다. 관계 유형 인스턴스는 상위 레코드 유형의 인스턴스 하나와 하위 레코드 유형의 순서가 지정된 인스턴스 세트로 구성됩니다. 상위 레코드 유형 P와 하위 레코드 유형 C가 있는 지정된 링크 유형 L의 경우 다음 두 조건이 충족되어야 합니다.

1. P 유형의 각 인스턴스는 L 인스턴스 하나만의 조상입니다.

2. C의 각 인스턴스는 최대 하나의 L 인스턴스의 하위 항목입니다.

관계형 조직 방식

계층적 및 네트워크 유형의 데이터 모델의 주요 단점은 다음과 같습니다.

1. 사용하기가 너무 어렵습니다.

2. 물리적 조직에 대한 지식이 실제로 필요합니다.

3. 신청 시스템은 이 조직에 따라 다릅니다.

4. 데이터베이스에 대한 액세스 구성에 대한 세부 정보로 인해 논리가 과부하되었습니다.

관계형 데이터 모델에 대한 가장 일반적인 해석은 거의 모든 책에서 이를 다양한 개선을 통해 재현한 Data의 해석인 것 같습니다. Date에 따르면 관계형 모델은 관계형 접근 방식의 다양한 측면을 설명하는 세 부분, 즉 구조적 부분, 조작 부분, 전체적인 부분으로 구성됩니다.

모델의 구조적 부분은 관계형 데이터베이스에 사용되는 유일한 데이터 구조가 정규화된 n항 관계임을 나타냅니다.

모델의 조작 부분은 관계형 데이터베이스를 조작하기 위한 두 가지 기본 메커니즘, 즉 관계 대수와 관계 미적분을 확인합니다. 첫 번째 메커니즘은 주로 고전 집합 이론(일부 개선 포함)을 기반으로 하며, 두 번째 메커니즘은 1차 술어 계산의 고전 논리 장치를 기반으로 합니다. 관계형 모델의 조작 부분의 주요 기능은 특정 관계형 데이터베이스 언어의 관계성에 대한 척도를 제공하는 것입니다. 언어가 관계형 대수 또는 관계형 계산보다 표현력이 뛰어나고 강력하다면 관계형이라고 합니다.

마지막으로, 관계형 데이터 모델의 필수 부분은 모든 관계형 DBMS에서 지원해야 하는 두 가지 기본 무결성 요구 사항을 수정합니다. 첫 번째 요구 사항은 엔터티 무결성 요구 사항이라고 합니다. 두 번째 요구 사항은 참조 무결성 요구 사항입니다.

시스템의 수학적 모델과 데이터 구성 방법, 시중에 판매되는 소프트웨어에 대한 예비 분석을 마친 후(계층적 구성 및 네트워크 구성 방법은 데이터 구성에 대한 객체 지향 접근 방식을 제안하며 오늘날에는 이러한 DBMS가 있습니다. 예를 들어 Jasmin 또는 Informix Dynamic Server), 그러나 개발 당시에는 사용할 가능성이 없었고 동시에 매우 "강력한" 관계형 DBMS(예: Oracle 8i)가 선택되었습니다. 데이터 저장을 구성하는 관계형 방법을 선호합니다.

2.3.2. 입력 정보에 대한 설명

문제를 해결하는 데 필요한 모든 정보는 스케줄링 문제를 해결하기 위한 방법의 반복을 시작하기 전에 지정됩니다. 단순화를 위해 지정된 정보는 일정이 준비되는 기간 동안 일정하다고 가정합니다.

작업의 어느 정도 일반성을 잃지 않으면서 문제의 제한 및 해결에 필요한 특정 입력 데이터 세트를 결정하는 동시에 시스템의 모든 실제 구현에 공통되는 특정 입력 데이터 세트를 결정할 수 있습니다. 작업의 특성(특정 대학 내 실제 구현의 경우 수학적 모델을 비교적 쉽게 적용할 수 있는 가능성)으로 인해 입력 정보 문서의 형식이 개발되지 않았습니다. 입력 정보에 대한 자세한 내용은 표 2에 설명되어 있습니다.

표 2. 입력 정보 세부 내용 설명

세부정보 이름	디테일의 특징
입력 서류	유형	최대. 길이	정확성
성, 이름, 교사의 후원; 교사의 연락 전화번호 학위; 학문적 인 명칭; 그룹 이름; 그룹 구성원 수 가르치는 과정의 제목; 수업 시간 청중 수; 관객정보 교사가 가르치는 과목의 이름 주제를 읽는 그룹의 번호입니다. 주제를 읽는 청중에 대한 정보입니다.

이 데이터 외에도 수학적 모델에는 프로그래밍 방식으로 입력 정보를 분석한 후 얻을 수 있는 몇 가지 추가 데이터가 필요합니다.

2.3.3. 작업에 대한 정보 지원 개발

정보 및 논리적 데이터 모델(ILM)의 후속 형식화 및 구축을 위한 정보의 구성 및 구조를 결정하기 위해 소스 정보를 분석합니다. 위의 수학적 모델과 주제 영역 설명의 추가 정보를 통해 문서에 포함된 상호 관련된 정보에서 세부 사항의 역할을 결정할 수 있습니다. 이 분석을 바탕으로 데이터 정규화에 대한 권장 사항 및 요구 사항에 따라 세부 사항의 기능적 종속성을 설정한 후 정규화 자체를 수행합니다. 정규화의 목적은 데이터 중복을 줄이는 것입니다(반드시 제거하는 것은 아님). 그러나 때때로 프로그램 효율성을 향상시키기 위해 일부 데이터 중복이 의도적으로 생성됩니다. 데이터베이스 정규화의 세 가지 형태를 정의해 보겠습니다.

테이블은 첫번째에 있어요 정상적인 형태(1NF) 기본 키가 있는 경우 모든 속성은 단순 데이터 유형이며 중복 속성이 없습니다. 1NF를 준수하려면 속성 도메인은 원자 값이어야 하며 중복된 속성 그룹이 없어야 합니다. 모든 중복 속성 그룹을 새 테이블로 이동해야 합니다.

테이블이 제1정규형이고 키가 아닌 모든 속성이 기본 키에 완전히 기능적으로 종속되는 경우 테이블은 제2정규형(2NF)입니다. 즉, 2NF에서 모든 키가 아닌 속성은 기본 키의 필드에 완전히 종속되어야 합니다. 열쇠).

테이블이 2NF이고 전이적 종속성이 없는 경우 테이블은 3NF(제3정규형)입니다. 전이적 종속성은 키가 아닌 속성 간의 기능적 종속성입니다. 동일한 테이블의 키가 아닌 다른 속성에 기능적으로 종속된 키가 아닌 속성은 전이적 종속성을 생성하므로 다른 테이블로 이동해야 합니다.

결과적인 기능적 종속성은 매우 사소하며 분명히 수학적 모델을 따릅니다. 추가 설명그들은 주어지지 않습니다. 또한 다음 프레젠테이션에서는 중간 정규화 수준이 생략되었습니다. 따라서 우리는 데이터베이스의 최종 정보학적 모델만을 제시합니다(그림 1 참조).

그림 1. 수업 예약 작업을 위한 데이터베이스의 정보학적 모델

2.3.4. 일정 문제의 수학적 모델의 제약 조건 형성의 특징

스케줄링 문제의 수학적 모델의 제약 조건 (1) – (7)을 작성하는 것은 간단한 SQL 쿼리를 사용하여 해결할 수 있는 매우 사소한 작업이며 입력 정보에 대한 사전 분석이 필요하지 않습니다. 그러므로 우리는 형식 (8)의 제한 사항에 대해서만 더 자세히 설명하겠습니다.

시스템의 수학적 모델에서 읽혀지는 주제는 특정 청중이 아니라 특정 청중 집합에 "연결"되어 있습니다. 특정 청중 번호의 배치는 작업이 해결된 후에 이루어집니다. 형식 (8)의 제한은 청중 세트가 교차하는 경우에만 의미가 있습니다. 시스템의 수학적 모델에서는 제한의 형태로 모든 고유한 교차 쌍을 고려하는 것이 제안되었습니다. 이러한 교차점의 수가 많아지면 최적화 알고리즘의 속도에 부정적인 영향을 미치는 많은 추가 제한이 발생할 수 있습니다. 그러나 추가 제한 횟수는 크게 줄일 수 있습니다.

교차 집합의 선형 배열의 경우를 고려해 보겠습니다(그림 2 참조).

그림 2. 선형 교차 세트

수업을 진행하기 위한 교실 세트 배열의 경우, 양식 (8)의 총 제한 수는 n-1이 됩니다. 여기서 n은 세트 수입니다. 위에서 설명한 교차 집합의 배열은 선형이라고 할 수 있습니다. 이 경우 n개의 교차 집합이 마치 일렬로 배열되어 있기 때문입니다. 집합이 임의의 방식으로 서로 교차하는 경우를 고려해 볼 수 있습니다(그림 3 참조).

그림 3. 임의로 교차하는 집합

이 경우 형식 (8)의 제한 수는 세트의 선형 배열의 경우와 유사하게 이러한 제한을 형성하여 줄일 수 있습니다. 이를 위해서는 예를 들어 A와 교차하는 집합 B와 D가 하나의 집합이라고 가정하고, 이러한 집합의 교차 영역을 집합 A와 결정한 다음 결과로 동일한 작업을 수행해야 합니다. 교차 영역.

이에 대한 자세한 내용은 210페이지를 참조하세요.

2.4. 프로그램 결과

시스템을 실제로 구현하는 동안 시스템의 "핵심"을 작성하는 작업(문제 해결 방법 및 제한 사항 형성 절차)에 특별한 주의를 기울였습니다. 모든 기능을 갖춘 상용 제품을 작성하는 것이 목표가 아니었기 때문에 인터페이스 부분은 커널을 테스트하고 알고리즘의 적용 가능성의 한계를 판단할 목적으로 작성되었으므로 최소한의 기능만 포함하고 입력 데이터 전처리 모듈을 포함하지 않습니다. .

시스템 코어와 인터페이스는 Delphi 6.0으로 작성되었습니다. 제약 조건을 해결하기 위한 방법과 알고리즘은 객체 지향 기술을 사용하여 작성되므로 향후 다양한 알고리즘 상호 작용의 무결성을 침해하지 않고 이를 시스템의 추가 수정에 쉽게 캡슐화할 수 있습니다. 문제 해결을 위한 객체 메소드 텍스트는 부록 2에 나와 있습니다. 데이터베이스는 Oracle 8i DBMS에서 구현되었으며 이에 대한 쿼리는 PL/SQL 언어로 수행됩니다.

초기 작업 데이터는 요청 양식을 사용하여 데이터베이스 테이블에 입력됩니다. 이러한 형태 중 하나가 그림 1에 나와 있습니다. 삼.

그림 3. 초기 데이터 입력 양식

문제풀이 결과 얻은 데이터로는 문제풀이 직후 수업일정을 표시하기에는 부족하여 데이터 후처리 모듈을 작성하였다. 최종 수업일정은 표 형태로 표시되며, 그 예가 그림 1에 나와 있습니다. 4.

쌀. 4. 수업일정 예시

문제를 해결하기 위한 알고리즘은 다양한 소스 데이터 샘플에서 테스트되었습니다. 테스트는 Intel Pentium 350MHz 프로세서가 장착된 컴퓨터에서 수행되었으며 Oracle 8i DBMS는 듀얼 프로세서 서버에 설치되었습니다. 2 CPU Intel Pentium II 350MHz, RAM 384MB; 통신 채널로는 최대 100Mbit/s의 대역폭을 갖는 LAN이 사용되었습니다. 테스트 소스 데이터로 1999/2000년 ChSU 저녁 교육의 그룹, 교사 및 읽기 과목에 대한 실제 데이터를 사용했습니다. 학년, 무작위로 생성된 초기 데이터(읽을 수 있는 주제는 수업의 청중에게 무작위로 할당됨)입니다. 평균적으로 원본 데이터의 테스트된 각 차원에 대해 5~10개의 테스트가 수행되었습니다. 그 결과, Table 2와 같은 데이터를 얻었다. Figure 5는 평균 문제 해결 시간이 읽은 과목 수와 그룹 수에 미치는 영향을 그래프로 나타낸 것이다.

2.5. 얻은 결과 분석

얻은 데이터를 분석함으로써 솔루션 알고리즘과 수학적 모델의 기능, 단점 및 적용 영역에 대한 몇 가지 결론을 도출할 수 있습니다.

첫째, 사용된 수학적 모델에는 선형 정수 모델로 인해 존재하는 "추가" 제한이 포함되어 있습니다. 또한 스트림에서 읽은 각 주제(스트림은 하나의 그룹으로 구성될 수 있음)에는 12(야간 학생의 경우)가 할당됩니다. 변수는 각각 부울 변수입니다. 둘째, 입력 데이터가 증가할수록 문제 해결에 소요되는 시간이 급격히 증가한다. 이는 모델의 변수 수와 제한 사항이 급격히 증가하여 발생하며, 그 결과 배열의 차원이 증가하고 그에 따라 문제를 해결하는 데 필요한 시간이 늘어납니다. 셋째, 수학적으로 공식화된 문제는 건물 간 전환을 고려하지 않고 저녁 학생들의 일정을 만드는 작업만 다루고 있습니다. 회계 추가 요구 사항문제의 제약 조건 수가 증가하여 솔루션 알고리즘의 속도에 부정적인 영향을 미칩니다.

문제의 차원이 커질수록 문제 해결에 소요되는 시간의 최소값과 평균값의 차이가 커지는 것에 주목해보자. 이 차이는 문제의 초기 실행 가능한 기본 솔루션이 얼마나 "성공적으로"(최적에 가장 가까운) 발견되었는지에 해당합니다. 따라서, 초기의 실행 가능한 기본 솔루션을 "성공적으로" 찾음으로써 문제를 해결하는 데 필요한 시간을 크게 줄일 수 있습니다. 그러한 해결책을 찾으려면 휴리스틱 및 분해 알고리즘을 사용하는 것이 가장 좋습니다.

결론 작업 과정에서 건물 간 전환이 없는 야간 교육의 경우 대학 일정의 수학적 모델을 구축하고 문제 해결 방법을 선택했으며 문제의 초기 데이터를 저장하는 모델을 개발했습니다. 소스 데이터 저장 모델, 모델의 수학적 공식화를 위한 알고리즘, 해결 방법은 소프트웨어 모듈 형태로 구현되었습니다. 알고리즘의 속도는 이기종 초기 데이터 세트에서 테스트되었으며, 그 결과 알고리즘의 기능과 적용 영역이 결정되었습니다.

테스트 결과, 문제해결 알고리즘의 연산 속도는 입력 정보의 양과 초기에 허용되는 기본해에 크게 의존하므로 휴리스틱 및 분해 알고리즘에 비해 현저히 떨어지는 것으로 나타났습니다. 그러나 경험적 솔루션의 경우 해당 솔루션의 최적성(또는 전역 최대값 달성)은 가능한 모든 옵션을 완전히 검색해야만 입증될 수 있습니다(이 경우 알고리즘의 실행 시간은 다음과 같습니다. 매우 길기 때문에) 따라서 휴리스틱 알고리즘의 반복은 특정 중요도(국지적인지 전역적인지 말할 수 없음)에 도달하면 중지됩니다. 이러한 알고리즘의 솔루션은 최적에 가까울 수 있지만 최적은 아닙니다. 이 경우 전역 최대값을 달성하려면 작업에서 고려한 솔루션 방법을 사용할 수 있습니다. 설명된 솔루션 방법을 여러 번 반복하면 최적값을 얻을 수 있기 때문입니다.

문학

1. 라고샤 B.A., 페트로파블로프스카야 A.V. 대학의 수업 일정을 최적화하기 위한 일련의 모델 및 방법 // 경제 및 수학. 행동 양식. 1993. T. 29. 이슈. 4.

2. Hu T. 네트워크의 정수 프로그래밍 및 흐름. M.: 미르, 1979.

3. 레베데프 S.S. Benders의 부분 정수 선형 프로그래밍 방법 수정 // Economics and Math. 행동 양식. 1994. T. 30. 이슈. 2.

4. Lebedev S.S., Zaslavsky A.A. 용법 특별한 방법정수 일반화 전송 문제를 해결하기 위한 분기 및 경계 // 경제 및 수학. 행동 양식. 1995. T. 31. 이슈. 2.

5. Zaslavsky A.A. 정수 선형 계획법의 일반적인 문제에서 변수 계층화 전략 사용 // 경제 및 수학. 행동 양식. 1997. T. 33. 이슈. 2.

6. 레베데프 S.S. 정수 선형 프로그래밍의 인덱싱 순서 지정 방법 // Economics and Math. 행동 양식. 1997. T. 33. 이슈. 2.

7. Lebedev S.S., Zaslavsky A.A. 부울 프로그래밍 문제에 대한 수정된 표시 방법 // 경제 및 수학. 행동 양식. 1998. T. 34. 이슈. 4.

8. Zaslavsky A.A. 배낭 문제 해결을 위한 결합 방법 // 경제와 수학. 행동 양식. 1999. T. 35. 이슈. 1.

부록 1. 스케줄링 시스템용 소프트웨어 제품의 기능.

와 함께 AUTOR-2+ 시스템은 수업 일정을 빠르고 편리하게 작성하고 학년 내내 유지하도록 설계되었습니다.
ㅏ VTOR-2+는 범용 시스템입니다. 모든 교육 기관을 위해 설계된 여러 버전의 프로그램이 있습니다.

중등 및 전문(수학, 언어 등) 학교, 학교, 체육관,

기술 학교, 학교 및 대학;

하나의 학술 건물을 갖춘 대학;

여러 학술 건물(건물 간 이동 포함)이 있는 대학.

ㅏ VTOR-2+를 사용하면 일정 작성자의 복잡한 작업을 최대한 단순화하고 자동화할 수 있습니다. 이 시스템을 사용하면 편리하고 시각적인 문서 형식으로 쉽게 작성, 편집 및 인쇄할 수 있습니다.

수업 일정(스터디 그룹)

교사의 일정;

강의실(사무실) 일정

교육 계획

관세.

ㅏ VTOR-2+는 멋진 디자인과 친절한 서비스를 제공합니다. 이 프로그램은 배우기 매우 쉽습니다. 프로그램 작업의 모든 기능과 방법을 설명하는 자세한 설명서가 있습니다.
피이 프로그램은 4Mb RAM(또는 그 이상)을 갖춘 486DX로 시작하는 모든 IBM 호환 컴퓨터에서 실행되며 하드 드라이브에서 약 1Mb를 차지합니다. 운영 체제: MS DOS 또는 WINDOWS 95/98.
안에작동 시간은 크기에 따라 다릅니다. 교육 기관그리고 컴퓨터 파워. 중간 규모 학교(30개 학급, 60명 교사, 2교대)의 전체 일정 계산 및 최적화는 Celeron-400 컴퓨터에서 약 15분 정도 소요됩니다.

피이 프로그램은 일정을 구성하고 최적화하기 위한 독특하고 매우 강력한 알고리즘으로 구별됩니다. 결과적으로 생성된 자동 일정에는 수동 수정이 거의 필요하지 않습니다. 즉, 매우 복잡하고 엄격한 제한이 있어도 가능한 모든 수업이 자동으로 배치됩니다. 원본 데이터에 해결 불가능한 모순이 있는 경우 특수 분석 장치를 사용하여 이를 감지하고 제거할 수 있습니다.

ㅏ VTOR-2+를 사용하면 다음을 수행할 수 있습니다.

일정에서 "창"을 최적화합니다.

수업과 교사 모두에게 필요한 요일/시간 범위를 고려하세요.

수업 특성, 과목별, 교사별, 수업 수용 능력 등을 고려하여 교실(강당)에 수업을 배치하는 것이 가장 좋습니다.

업무의 성격과 정규 직원과 시간제 직원 모두의 희망 사항을 고려합니다.

수업을 진행할 때 여러 수업(스터디 그룹)을 스트림으로 연결("쌍")하는 것은 쉽습니다.

외국어, 체육, 노동, 컴퓨터 과학(및 기타 과목) 수업을 진행할 때 수업을 원하는 수의 하위 그룹(최대 10개!)으로 나눕니다.

(주요 과목 외에) 특별 과정과 선택 과목을 소개합니다.

일정의 통일성과 노동 강도를 최적화합니다.

2. "일정" 시스템 버전 4.0 모스크바 – LinTech

"일정"프로그램은 학교 일정 작성에 중점을두고 있으며 일부 예약이 있어야만 대학에서 사용할 수 있습니다. 스케줄링은 초기 데이터 입력 단계에서 결정되는 일련의 조건 프레임워크 내에서 이루어집니다. 가능한 조건의 전체 목록은 다음과 같습니다.

- 에 대한최대 레슨 횟수는 제한되어 있습니다. 하루에 허용되는 최대 수업 횟수;

- 아르 자형일정 기간 동안 교사의 업무량을 균일하게 분배합니다.

- 아르 자형일정 기간 동안 수업 부하를 균등하게 분배합니다.

- 에게교사 일정의 모니터링 창;

- 피이 프로그램은 학급이 임의로 통합되고 분할될 수 있다는 사실을 고려합니다(학급은 스트림으로 결합되거나 더 작은 하위 그룹으로 분할될 수 있으며, 이러한 하위 그룹은 차례로 더 큰 그룹으로 결합하기 위한 기초가 될 수 있습니다. 예: 학교에서 아니요 . . 1859 2 개의 상급반이 있지만 각 수업에는 전문화를위한 2 개의 하위 그룹이 있으며 일반 과목 수업은 전체 수업을 동시에 진행하고 전문화 과목은 별도로 진행됩니다. 그러나 전문화를위한 하위 그룹이 너무 작기 때문에 교사가 충분하지 않은 경우 일부 과목에서는 하위 그룹 11a와 11b를 결합할 수도 있습니다(예: 외국어). 이로 인해 수업 일정의 연속성을 보장하기가 어렵습니다(일정의 연속성을 보장해야 함) 각 하위 그룹에 대해);

- N여러 교대조의 존재 - 이 경우 개별 수업은 첫 번째 교대조의 그룹보다 늦게 도착해야 하며, 또한 두 교대조에 근무하는 교사가 있는 경우 교사 일정의 창을 제어하는 ​​것이 더 어려워집니다. 경우에 따라 이러한 교사의 일정에서 수업은 교대 교차점을 중심으로 "계약"되어야 합니다.

- 유교사를 청중과 연결하는 조건 - 개별 교사는 모든 수업을 진행하는 "자신의"청중을 가지고 있습니다.

- N"부동" 교대 근무의 존재 - 첫 번째 수업의 시작 시간이 정확하게 결정되지 않은 경우 관련 수업, 교사, 청중의 공개에 따라 동적으로 형성됩니다.

- 에게개체(수업, 교사, 청중)의 일정이 허용되는 작업 범위(시간 제한 맵) 내에 있는지 모니터링합니다. 예를 들어, 교사의 경우 시간 제한 맵은 일반적으로 방법론적 날짜, 때로는 개별 수업 번호를 나타냅니다. 한마디로 주어진 개체의 참여로 수업을 설정할 수 없는 위치가 표시됩니다.

- N'외국어/컴퓨터공학', '컴퓨터공학/노동' 등 복합과목 존재 - 수업이 하위 그룹으로 나누어지는 경우

- 유과목을 교실에 연결하는 조건 - 개별 과목의 수업 진행은 엄격하게 정의된 교실 또는 교실 목록(체육, 노동 등)에서만 가능합니다.

- 와 함께일부 과목에서는 수업에 참석하는 것이 전체 수업이 아니라 그 하위 그룹이라는 사실을 고려하여 일정을 남깁니다. 현재 다른 하위 그룹이 학교를 돌아다니는 것을 방지하기 위해 이러한 수업은 엄격하게 수업 일정의 첫 번째 또는 마지막 수업으로만 이루어질 수 있습니다.

- “안에평행 유지” - 일부 교사의 경우 수업을 진행하려면 장기적인 준비(예: 화학 수업)가 필요하다는 사실을 고려해야 합니다. 이 경우 교사의 일일 일정에 따른 수업은 블록으로 배열하려고 합니다. 예를 들어 첫 번째 5학년, 다음 7학년 -y 등과 같은 평행선을 사용하거나 요일 간에 배포할 때 서로 다른 날에 서로 다른 병렬로 수업을 배포합니다.

- 그리고때로는 일정을 작성할 때 일부 과목의 경우 일정이 미리 알려져 있다는 뉘앙스를 고려해야 합니다. 이 경우 이러한 수업은 이동 불가능(고정)으로 도입됩니다.

- 에게수업 일정 중 어느 날에 해당하는 과목의 금지된 조합을 통제하는 것은 바람직하지 않습니다. 신체 문화"와 "노동"이 같은 날 수행되었습니다.

- 안에필수 과목 순서 조건 충족 - 예를 들어 물리-천문학 등과 같이 수업이 특정 순서로 진행되어야 하는 수업 그룹의 설치를 보장해야 하는 경우

- N교실과 연결된 수업의 존재 - 특수 교실이 필요한 수업을 제외하고 이러한 수업의 대부분의 수업이 이 교실에서 진행됩니다.

- N개별 과목의 수업을 두 개의 연속 수업(“쌍”, “스파크”)으로 배열해야 할 필요성이 있으며, 이 조건은 엄격할 수 있으며(어떤 경우에도 수업의 “스파크”를 분리하지 않음) 바람직할 수 있습니다(경우에 따라) 두 클래스를 이동할 수 없으며 "스파크"가 깨질 수 있습니다.)

일부 과목에서는 단일 수업에만 배치가 허용된다는 사실이 고려됩니다.

3. “메소디스트” 시스템

두 가지 버전으로 제공됩니다.

가상 버전.

자동 예약 모듈 없이 사용할 수 있습니다. 가상 버전의 특징:

교사, 교실, 수업(그룹), 학과, 건물 목록에서 빠른 검색

목록에서 발견된 각 요소에 대한 참조 정보를 얻습니다(청중 수용 인원, 모든 강당 건물 X, 교사의 주소 및 전화번호, 부서 목록, 훈육 시간, 교사의 교육 부하 등).

모든 학문 분야에서 주 사이에 시간을 재분배하는 제어 및 능력. 여러 떼;

가능한 데이터 입력 오류 자동 확인(총 시간 및 수업 유형 일치, 교사를 하위 그룹에 할당하지 않음, 학습 그룹 및 교사의 시간 예산, 스트림 그룹의 시간 불일치 등)

체계적인 저장 가능성(및 빠른 탐색) 추가(예약에는 필요하지 않음) 정보: 교사, 스터디 그룹 큐레이터 사진( 담임선생님), 학부모위원회 대표, 직위, 학업 학위 및 청중을 담당하는 직함에 대한 데이터, ...

요인(스트림의 모든 그룹, 교사 X의 모든 분야, 주별 작업량 및 수업 유형을 나타냄)의 조합에 대한 완전한 정보를 신속하게 얻습니다. 컴퓨터 수업에서 가르칠 수 있는 분야, 모든 교사의 수업, 시리아 그룹의 휴일 목록 등);

변경 사항(교실, 교사, 그룹/하위 그룹의 점유율 등)의 정확성을 확인하여 완료된 일정을 보고, 인쇄하고 편집할 수 있는 기능

언제든지 준비된 데이터에 대한 일정 생성 모듈을 주문할 수 있습니다.

일정은 설정 변경, 제어, 편집 등의 기능을 통해 컴퓨터에서 생성됩니다. (시간, 규율, 교사 등을 변경할 가능성 없음...)

소스 데이터에서 사소한(최대 10%) 변경이 필요한 경우(오류, 갑작스러운 추가 발견), 적은 비용으로 일정 생성 모듈을 다시 주문할 수 있습니다.

언제든지 표준 버전으로 전환할 수 있습니다.

감리교 - 표준.

가상 버전의 기능 외에도 다음이 포함됩니다.

자동 스케줄링 모듈;

티칭 부하의 분배 및 제어;

규율 순서를 엄격하게 준수합니다(강의 - 2시간, 실습 - 4시간, 실험실...).

모든 유형의 교육 기관에 대한 일정 만들기: 주간 또는 학기(1~23주)

그룹(클래스)을 스트림으로 결합하거나 하위 그룹으로 나누는 방법을 설명합니다.

특수 교실 배정(컴퓨터 수업, 어학실, 수영장 등)

교사 및 교실 고용 회계(시간제 근무, 공통 교육 기반 사용)

건물 간 전환 시간을 고려합니다.

주말 및 공휴일 - 일반 및 개별 연구 그룹(국가, 종교, 공휴일);

"수동" 수정 가능성과 함께 수업의 "실패한 할당"(교실이 바쁘고 교사가 바람직하지 않은 요일에 할당됨) 이유 표시

일정의 반복적인 자동 "개선" 가능성

일정을 작성할 때 고려되는 요소의 중요성을 변경할 가능성

교사의 우선순위를 도입할 가능성 - 교사 개인의 희망사항이 고려되는 정도

"Methodist" 기능의 제한 사항:

다중 교대 일정은 하루 최대 수업 수인 7회로 제한됩니다.

수업은 항상 첫 번째 레슨/페어로 시작됩니다(필요한 경우 첫 번째 레슨에 "무료 레슨"을 할당할 수 있음).

변경 시점은 고려되지 않습니다(예: 건물 간 이동 가능성 확인).

수업의 "난이도 수준"은 일주일 내내 합리적인 분배를 위해 고려되지 않습니다(비록 간접적으로 수행하는 것은 가능하지만).

수업 시간은 일정합니다(중학교 30분 수업, 고등학교 45분 수업 일정을 만드는 것은 불가능합니다).

부록 2. 자동 스케줄링 문제를 해결하기 위한 방법의 소프트웨어 모듈 목록

MyArray 유형 = 실수 배열의 배열;

MyArray_X = longint 배열;

절차 Step_Dual_simplex(var a:MyArray; m,n,i1,j1:integer);

(Dual Simplex 방식의 한 단계를 수행하고,

선행 요소 - a)

var i,j:정수;

b,b1:실수 배열;

길이 설정(b,m);길이 설정(b1,n);

i:=0에서 m-1까지 do b[i]:=a;

i:=0에서 n-1까지 do b1[i]:=a;

i:=0 ~ m-1 do의 경우

j:=0 ~ n-1의 경우 시작합니다.

(i=i1)이고 (j=j1)이면 a:=1/b

(i=i1)이면 a:=b1[j]/b

if (j=j1) then a:=-b[i]/b

그렇지 않으면 a:=a-b[i]*b1[j]/b;

i:=0에서 n-1까지 do a:=0;a:=-1;

마무리(b); 마무리(b1);

함수 Lexikogr_few(a:MyArray; m,n:integer;i,i1:integer):boolean;

(첫 번째 열은 두 번째 열보다 사전순으로 더 작습니다.)

Lexikogr_few:=false;

(a=a) 및 (j

function Find_nu(a:MyArray;m,n:integer; i,i1:integer):longint;

(i는 사전순으로 최소 열의 인덱스입니다)

(a=a) 및 (j

if (j 0) then Find_nu:=Round(Int(a/a));

절차 Full_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer);

(선형 정수 문제에 대한 완전 정수 알고리즘

프로그램 작성,

Hu T. "정수 프로그래밍 및 네트워크의 흐름", pp. 300-309,

a는 비유하자면 다음과 같이 크기가 m+n+2*n+1인 행렬입니다.

우리는 최대값을 찾아야 한다

z= - 10x1 - 14x2 - 21x3

2x1 + 2x2 + 7x3 >= 14

8x1 + 11x2 + 9x3 >= 12

9x1 + 6x2 + 3x3 >=10,

이 프로시저는 원하는 솔루션인 처음 m개의 구성 요소인 벡터 X를 반환합니다.

벡터의 마지막 구성요소 = 1이면 해가 존재하지 않거나 = 무한대입니다.

var i,i1:정수;

while (i =0) do Inc(i); (문자열 생성)

while (j =0) do Inc(j);

for i1:=1 to n-1 do if (a

최소 열)

(알파 선택)

(Writeln(i," ",j);readln;)

i1:=1 ~ n-1의 경우

j1:=Find_nu(a,m,n,j,i1);

(j1>0) 및 (-a/j1>alfa)이면 alfa:=-a/j1;

(writeln(alfa," ",i," ",j);readln;)

(고모리 컷을 받음)

i1:=0에서 n-1까지의 경우 a>0이면 a:=round(Int(a/alfa))를 수행합니다.

a:=round(Int(a/alfa));

Frac(a/alfa)0이면 a:=a-1;

Step_Dual_simplex(a,m,n,m-1,j);

(i>=m-1) 또는 (j>=n)까지;

for i:=0 ~ m-1 do x[i]:=round(a);

j>=n이면 x:=1 else x:=0;

절차 Step_One_Simplex(var a:MyArray; m,n,i:integer);

var i1,i2:정수;

(직정 정수법의 한 단계(생산 라인이 마지막 라인입니다)

i - 열 생성))

i1:=0 ~ m-2의 경우 a:=a/(-a);

i2:=0에서 n-1까지 do

i1:=0 ~ m-2의 경우

i2i이면 a:=a+a*a;

절차 Direct_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer);

(정수 선형 계획법 문제에 대한 직접 정수 알고리즘,

Hu T. "정수 프로그래밍 및 네트워크의 흐름", pp. 344-370,

a는 비유적으로 m+n+3*n+1 크기의 행렬입니다.

극대화할 필요가 있다

z = x1 + x2 + x3

4x1 + 5x2 + 2x3

그러면 행렬 a는 다음과 같습니다.

10 1 1 1 - 이 줄에서 첫 번째 숫자는 기본이 아닌 변수의 대략적인 최대 합계입니다.

0 0 0 0 - 고모리 자르기용 끈,

알고리즘은 a>=0일 때만 작동합니다.

벡터 X를 반환합니다 - 단위 행렬 대신 원하는 솔루션을 반환합니다.

마지막 구성 요소에 단위가 포함되어 있으면 계산에 오류가 있습니다.)

var i,j,i1,j1:정수;

b,b1,b2:바이트 배열;

길이 설정(b,m);길이 설정(b1,m);

i:=0에서 m-1까지 do b1[i]:=0;

(최적성 조건 확인)

j:=1 ~ n-1의 경우 a인 경우 수행

bool이 시작되는 동안

(생성 컬럼 검색)

부울:=false;j1:=0;

j:=1 ~ n-1의 경우 시작합니다.

a>0이면

i:=0 ~ m-3의 경우 do a:=a/a;

bool이 아니면 j1:=j;bool:=true를 시작하고, else if Lexikogr_few(a,m,n,j,j1)

(생성 문자열 검색)

j:=1에서 n-1까지 do

a>0이면

i:=0 ~ m-3의 경우 do a:=a*a;