전송 매트릭스의 계산 순서입니다. 운송 문제에 관한 이론 자료. 운송 문제 해결을 위한 자세한 지침
이 계산기에는 다음 사항도 사용됩니다.
ZLP 해결을 위한 그래픽 방법
ZLP를 해결하기 위한 심플렉스 방법
매트릭스 게임 해결
온라인 서비스를 사용하면 매트릭스 게임의 가격(하한 및 상한)을 결정하고 가용성을 확인할 수 있습니다. 안장 포인트, 미니맥스 방법, 단순 방법, 그래픽(기하학적) 방법, 브라운 방법을 사용하여 혼합 전략에 대한 솔루션을 찾습니다.
두 변수의 함수의 극값
동적 프로그래밍 문제
운송 문제 해결의 첫 번째 단계유형(개방형 또는 폐쇄형, 균형 또는 불균형)을 결정하는 것입니다. 대략적인 방법( 참조 계획을 찾는 방법) 허용 해결의 두 번째 단계아니기 때문에 큰 숫자문제에 대해 수용 가능하지만 항상 최적은 아닌 솔루션을 얻기 위한 단계입니다. 이 방법 그룹에는 다음 방법이 포함됩니다.
- 삭제(이중 우선순위 방법);
- 북서쪽 코너;
- 최소 요소;
- 보겔 근사.
운송 문제에 대한 참조 솔루션
운송 문제에 대한 참조 솔루션양의 좌표에 해당하는 조건 벡터가 선형 독립인 허용 가능한 솔루션입니다. 확인용 선형 독립허용되는 솔루션의 좌표에 해당하는 조건 벡터, 사이클이 사용됩니다.주기전송 작업 테이블의 일련의 셀은 두 개의 인접한 셀만 동일한 행이나 열에 위치하고 첫 번째와 마지막 셀도 동일한 행이나 열에 있는 것입니다. 전송 문제 조건의 벡터 시스템은 테이블의 해당 셀에서 사이클이 형성될 수 없는 경우에만 선형 독립입니다. 따라서 전송 문제에 대해 허용되는 솔루션은 i=1,2,...,m입니다. j=1,2,...,n은 자신이 차지하는 테이블 셀에서 단일 사이클을 형성하는 것이 불가능한 경우에만 참조입니다.
운송 문제를 해결하는 대략적인 방법.
크로스아웃 방식(이중 선호 방식). 테이블의 행이나 열에 하나의 셀이 있으면 사이클에는 각 열에 2개의 셀만 있으므로 해당 셀은 어떤 사이클에도 포함될 수 없습니다. 따라서 하나의 점유된 셀을 포함하는 테이블의 모든 행을 지운 다음, 하나의 점유된 셀을 포함하는 모든 열을 지운 다음 행으로 돌아가서 행과 열을 계속 지울 수 있습니다. 삭제 결과 모든 행과 열이 지워진다면 이는 테이블의 점유된 셀에서 순환을 형성하는 부분을 선택할 수 없으며 해당 조건 벡터의 시스템이 선형 독립임을 의미합니다. 솔루션은 참조 솔루션입니다. 삭제 후에도 일부 셀이 남아 있으면 이러한 셀이 순환을 형성하고 해당 조건 벡터의 시스템은 선형 종속적이며 솔루션은 참조 솔루션이 아닙니다.
북서각 방법왼쪽 열부터 시작하여 전송 테이블의 행과 열을 순차적으로 반복하는 것으로 구성됩니다. 윗줄, 그리고 작업에 명시된 공급자의 능력이나 소비자의 요구 사항이 초과되지 않도록 테이블의 해당 셀에 가능한 최대 배송량을 기록합니다. 이 방법에서는 배송의 추가 최적화가 가정되므로 배송 가격에 주의를 기울이지 않습니다.
최소 요소 방법. 단순함이 특징 이 방법예를 들어 Northwest Angle 방법보다 훨씬 더 효과적입니다. 게다가 최소요소법은 명확하고 논리적이다. 그 본질은 전송 테이블에서 관세가 가장 낮은 셀이 먼저 채워지고 관세가 높은 셀이 채워지는 것입니다. 즉, 화물배송에 드는 비용을 최소화하면서 운송을 선택하는 것입니다. 이는 명백하고 논리적인 움직임이다. 사실, 이것이 항상 최적의 계획으로 이어지는 것은 아닙니다.
보겔 근사 방법. Vogel 근사법을 사용하면 각 반복마다 여기에 적힌 두 개의 최소 관세 간의 차이가 모든 열과 모든 행에 대해 발견됩니다. 이러한 차이점은 문제 조건 표의 특별히 지정된 행과 열에 기록됩니다. 표시된 차이 중에서 최소값이 선택됩니다. 이 차이에 해당하는 행(또는 열)에서 최소 관세가 결정됩니다. 이 반복에서 그것이 쓰여진 셀이 채워집니다.
예 1. 관세 매트릭스(여기서는 공급업체 수는 4개, 매장 수는 6개):
| 1 | 2 | 3 | 4 | 5 | 6 | 예비비 | |
| 1 | 3 | 20 | 8 | 13 | 4 | 100 | 80 |
| 2 | 4 | 4 | 18 | 14 | 3 | 0 | 60 |
| 3 | 10 | 4 | 18 | 8 | 6 | 0 | 30 |
| 4 | 7 | 19 | 17 | 10 | 1 | 100 | 60 |
| 요구사항 | 10 | 30 | 40 | 50 | 70 | 30 |
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
밸런스 조건이 충족되었습니다. 동일한 요구 사항을 충족합니다. 따라서 운송 문제 모델은 닫혀 있습니다. 모델이 공개된 경우 추가 공급자나 소비자를 소개해야 합니다.
~에 두 번째 단계참조 계획은 위에 제공된 방법을 사용하여 검색됩니다(가장 일반적인 방법은 최소 비용 방법).
알고리즘을 시연하기 위해 몇 가지 반복만 제시합니다.
반복 번호 1. 최소 행렬 요소 0과 같음. 이 요소의 경우 인벤토리는 60이고 요구 사항은 30입니다. 그중에서 최소 숫자 30을 선택하여 뺍니다(표 참조). 동시에 우리는 표에서 여섯 번째 열을 지웁니다(필요는 0과 같습니다).
| 3 | 20 | 8 | 13 | 4 | 엑스 | 80 |
| 4 | 4 | 18 | 14 | 3 | 0 | 60 - 30 = 30 |
| 10 | 4 | 18 | 8 | 6 | 엑스 | 30 |
| 7 | 19 | 17 | 0 | 1 | 엑스 | 60 |
| 10 | 30 | 40 | 50 | 70 | 30 - 30 = 0 | 0 |
반복 번호 2. 다시 우리는 최소값(0)을 찾고 있습니다. 쌍(60;50)에서 최소 숫자 50을 선택합니다. 다섯 번째 열을 지웁니다.
| 3 | 20 | 8 | 엑스 | 4 | 엑스 | 80 |
| 4 | 4 | 18 | 엑스 | 3 | 0 | 30 |
| 10 | 4 | 18 | 엑스 | 6 | 엑스 | 30 |
| 7 | 19 | 17 | 0 | 1 | 엑스 | 60 - 50 = 10 |
| 10 | 30 | 40 | 50 - 50 = 0 | 70 | 0 | 0 |
반복 번호 3. 우리는 모든 요구 사항과 소모품을 선택할 때까지 프로세스를 계속합니다.
반복 번호 N. 당신이 찾고 있는 요소는 8입니다. 이 요소의 경우 공급품은 요구 사항(40)과 같습니다.
| 3 | 엑스 | 8 | 엑스 | 4 | 엑스 | 40 - 40 = 0 |
| 엑스 | 엑스 | 엑스 | 엑스 | 3 | 0 | 0 |
| 엑스 | 4 | 엑스 | 엑스 | 엑스 | 엑스 | 0 |
| 엑스 | 엑스 | 엑스 | 0 | 1 | 엑스 | 0 |
| 0 | 0 | 40 - 40 = 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 예비비 | |
| 1 | 3 | 20 | 8 | 13 | 4 | 100 | 80 |
| 2 | 4 | 4 | 18 | 14 | 3 | 0 | 60 |
| 3 | 10 | 4 | 18 | 8 | 6 | 0 | 30 |
| 4 | 7 | 19 | 17 | 0 | 1 | 100 | 60 |
| 요구사항 | 10 | 30 | 40 | 50 | 70 | 30 |
테이블에서 점유된 셀의 수를 세어보겠습니다. 그 중 8개가 있지만 m + n - 1 = 9가 되어야 합니다. 따라서 참고 계획퇴폐적이다. 우리는 건물을 짓고 있다 새로운 계획. 때로는 비퇴화 계획을 찾기 전에 여러 참조 계획을 세워야 할 때도 있습니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 예비비 | |
| 1 | 3 | 20 | 8 | 13 | 4 | 100 | 80 |
| 2 | 4 | 4 | 18 | 14 | 3 | 0 | 60 |
| 3 | 10 | 4 | 18 | 8 | 6 | 0 | 30 |
| 4 | 7 | 19 | 17 | 0 | 1 | 100 | 60 |
| 요구사항 | 10 | 30 | 40 | 50 | 70 | 30 |
결과적으로 첫 번째 지원 계획이 얻어지며 이는 테이블의 점유된 셀 수가 9이고 공식 m + n - 1 = 6 + 4 - 1 = 9에 해당하므로 유효합니다. 참고 계획은 비퇴화.
세 번째 단계발견된 참조 계획을 개선하는 것으로 구성됩니다. 여기에서는 잠재적인 방법이나 배포 방법을 사용합니다. 이 단계에서는 비용 함수 F(x)를 통해 해의 정확성을 모니터링할 수 있습니다. 비용이 감소하면(비용 최소화 조건) 솔루션이 올바른 것입니다.
예 2. 최저관세법을 이용하여 교통문제 해결을 위한 초기 계획을 제시한다. 잠재적인 방법을 사용하여 최적성을 확인합니다.
| 30 | 50 | 70 | 10 | 30 | 10 | |
| 40 | 2 | 4 | 6 | 1 | 1 | 2 |
| 80 | 3 | 4 | 5 | 9 | 9 | 6 |
| 60 | 4 | 3 | 2 | 7 | 8 | 7 |
| 20 | 5 | 1 | 3 | 5 | 7 | 9 |
예 번호 3. 4개의 제과공장에서는 3가지 종류의 제과제품을 생산할 수 있습니다. 각 공장에서 100중량(5분)의 과자 제품을 생산하는 데 드는 비용, 생산 능력공장 (월 센트)과 제과 제품의 일일 수요 (월 센트)가 표에 표시되어 있습니다. 총 생산비용을 최소화하는 제과 생산 계획을 수립합니다.
메모. 운송 문제의 고전적 공식화에서는 용량(생산)이 먼저이고 그 다음이 소비자이기 때문에 여기에서 먼저 비용 표를 바꿀 수 있습니다.
예 번호 4. 시설 건설을 위해 벽돌은 3개(I, II, III) 공장에서 공급됩니다. 공장의 창고는 각각 50,000개, 100,000개, 50,000개입니다. 벽돌 개체에는 각각 50,000, 70,000, 40,000개, 40,000개가 필요합니다. 벽돌 관세(덴 단위/천 단위)가 표에 나와 있습니다. 총 운송 비용을 최소화하는 운송 계획을 수립하십시오.
다음과 같은 경우 문이 닫힙니다:가) a=40, b=45
나) a=45, b=40
나) a=11, b=12
닫힌 수송 문제의 조건: ∑a = ∑b
우리는 ∑a = 35+20+b = 55+b; ∑b = 60+a
우리는 다음을 얻습니다: 55+b = 60+a
a=40, b=45인 경우에만 평등이 관찰됩니다.
가장 일반적이고 인기있는 것 중 하나 최적화 문제물류 분야 – 운송 문제. 안에 클래식한 모습여기에는 최적의 값을 찾는 것이 포함됩니다( 저것들. 와 관련된 최소 비용 ) 화물 운송 계획.
예를 들어, 우리는 다음을 요구하는 소매점 체인을 가지고 있습니다. 일정량의상품. 필요한 물품을 보관하는 공급업체 창고도 많이 있습니다. 또한 각 창고마다 해당 상품의 재고량이 다릅니다. 또한 우리는 관세, 즉 각 창고에서 각 매장으로 1개의 제품을 운송하는 데 드는 비용을 알고 있습니다.
매장이 필요한 양의 물품을 수령할 수 있도록 운송 계획을 개발할 필요가 있습니다. 최저 비용으로운송을 위해. 운송 문제가 해결되어야 하는 것은 바로 그러한 경우(그리고 다른 많은 경우)입니다.
운송 문제에 관한 이론 자료
(몽게-칸토로비치 문제) - 수학 문제 선형 프로그래밍 특별한 유형검색에 대해 최적의 분포이동 비용을 최소화하면서 배터리에서 수신기까지 동종의 물체를 운반합니다.
이해의 편의를 위해 출발지로부터 물품을 운송하기 위한 최적의 계획에 대한 문제로 생각된다( 예를 들어 창고) 소비 지점 ( 예를 들어 상점), 총 운송 비용이 최소화됩니다.
다음과 같은 형식을 갖습니다.
어디: 지- 물품 운송 비용
엑스- 화물량;
씨- 화물 단위 운송 비용(관세)
ㅏ- 공급자 재고;
비- 소비자 요청;
중- 공급업체 수
N- 소비자 수.
잠재적인 방법을 활용한 교통 문제 해결을 위한 일반 계획
교통문제는 해결될 수 있다 다양한 방법, 단순 방법에서 시작하여 단순 검색, 메서드로 끝납니다. 대부분의 경우 가장 많이 사용되고 적합한 방법 중 하나는 운송 계획의 반복적인 개선입니다.
그 본질은 다음과 같습니다. 특정 참조 계획을 찾아 확인합니다. 최적성 (Z → 최소). 계획이 최적이라면 해결책을 찾은 것입니다. 그렇지 않은 경우 발견될 때까지 필요한 만큼 계획을 개선합니다. 최적의 계획.
아래는 전송 문제를 해결하기 위한 알고리즘가장 일반적인 형태로:
- 운송 테이블 구축.
- 문제를 확인하여 종료합니다.
- 기본 계획을 작성합니다.
- 퇴폐화 지원 계획을 확인하고 있습니다.
- 운송 계획의 잠재력 계산.
- 최적성을 위한 참조 계획을 확인합니다.
- 공급품 재분배.
- 최적해가 발견되면 9단계로 이동하고, 그렇지 않으면 5단계로 이동합니다.
- 상품 운송에 드는 총 비용을 계산합니다.
- 교통 그래프 구축.
운송 문제 해결을 위한 자세한 지침
1. 운송 테이블 구축
우리는 공급업체의 창고에서 사용 가능한 자재 재고를 나타내는 테이블을 구축합니다( 일체 포함), 공장의 요구사항( 비제이) 이 자료에 있습니다.
표 셀의 오른쪽 하단에 화물 운송에 대한 관세 값을 입력합니다( Cij).
모든 공급업체의 총 화물 재고를 기호로 표시하겠습니다. ㅏ, 모든 소비자의 화물에 대한 총 수요가 기호화됩니다. 비.
운송 업무~라고 불리는 닫은, 만약에 A=B. 만약에 A ≠ B, 운송 문제가 호출됩니다. 열려 있는. 언제 닫힌 문제모든 화물 공급품은 공급업체로부터 제거되고 모든 소비자 요청은 충족됩니다. 언제 열린 작업이를 해결하려면 가상의 공급자나 소비자를 소개해야 합니다.
종료 작업을 확인해 보겠습니다.
A = 10 + 20 + 30 = 60
비 = 15 + 20 + 25 = 60
A = B이므로 이 전송 문제는 종료됩니다.
3. 참고계획 수립
예비 작성( 지원) 교통 계획. 최적일 필요는 없습니다. 이것은 일종의 "초안", "스케치"일 뿐이며 이를 개선하여 점차 최적의 계획에 도달하게 됩니다.
다른 참조 계획을 찾는 방법. 가장 일반적인 것은 다음과 같습니다.
a) 북서각 방법. 보여주다
방법의 본질은 간단합니다. 전송 테이블의 셀은 순차적으로 최대값까지 채워집니다. 가능한 볼륨교통, 방향 위에서 아래로그리고 왼쪽에서 오른쪽으로. 즉, 왼쪽 상단 셀이 먼저 채워집니다( "북서쪽" 셀), 그 다음 오른쪽의 다음 항목 등입니다. 그런 다음 새 줄그리고 왼쪽에서 오른쪽으로 다시 채워주세요. 그리고 테이블이 완전히 채워질 때까지 계속됩니다.
자세한 방법 설명과 예시를 확인하실 수 있습니다.
b) 최소요소법. 보여주다
방법은 전송 테이블의 셀을 채우려면 다음을 사용하여 셀을 선택하는 것입니다. 최소한의관세 가치. 그런 다음 관세가 가장 낮은 다음 셀이 선택되고 테이블이 채워질 때까지 계속됩니다( 모든 재고와 수요가 0으로 재설정됩니다.).
c) 보겔 근사. 보여주다
방법의 기본은 찾는 것입니다. 차이점(모듈로) 각 행과 열의 최소 관세 쌍 사이. 그런 다음 행이나 열에서 가장 큰차이점은 셀을 다음으로 채웁니다. 가장 작은관세. 그런 다음 이러한 모든 작업이 다시 반복됩니다. 이 경우에만 채워진 셀이 더 이상 고려되지 않습니다.
Vogel 근사법에 대한 자세한 설명과 예제를 찾을 수 있습니다.
d) 이중 우선권 방법. 보여주다
이 방법의 핵심은 관세가 가장 낮은 셀을 행으로 표시한 다음 열로 표시한다는 것입니다. 그런 다음 셀은 다음 순서로 채워집니다. 먼저 두 개의 마크, 그 다음에는 하나로, 마지막으로 표시가 없습니다.
자세한 방법 설명과 예시를 확인하실 수 있습니다.
4. 퇴폐화 지원방안 점검
0이 아닌 운송이 기록되는 테이블의 셀을 호출합니다. 기초적인, 나머지는 (비어 있음) - 무료.
계획이라고 합니다 퇴화하다, 그 안에 있는 기본 셀의 수가 m + n -1보다 작은 경우. 문제를 해결하는 동안 퇴화 계획을 얻은 경우 누락된 셀 수에 제로 운송을 삽입하여 이러한 셀을 기본 셀로 전환하여 보충해야 합니다( 계획의 전체 잔액과 총 운송 비용은 변경되지 않습니다.). 그러나 무작위로 셀을 선택하여 계획을 보충하는 것은 불가능합니다. 계획은 비주기적이어야 합니다!
기본 셀에 주기가 포함되어 있지 않으면 계획을 비주기적이라고 합니다. 주기전송 테이블에는 닫힌 폴리라인으로 연결된 여러 셀이 있으므로 폴리라인의 인접한 두 정점이 동일한 행이나 동일한 열에 위치합니다. 아래는 루프 예:
파선에는 자체 교차점이 있을 수 있지만 주기의 셀에는 있을 수 없습니다.
기본 셀 수 = 5
m + n – 1 = 3 + 3 – 1 = 5
결과적으로 원래의 운송 계획은 퇴화되지 않습니다.
5. 운송계획의 잠재력 계산
받은 계획과 후속 개선 사항을 분석하려면 다음을 입력하는 것이 편리합니다. 추가 특성출발점과 도착점을 잠재력이라고 합니다.
이러한 교통 계획 개선 방법을 잠재적인 방법 . 운송 계획을 반복적으로 개선하는 다른 방법이 있지만 여기서는 고려하지 않습니다.
그럼 각 공급자 Ai와 각 소비자 Bj를 값으로 비교해 보겠습니다. 우이그리고 VJ따라서 계획의 모든 기본 셀에 대해 다음 관계가 충족됩니다.
Ui + Vj = Cij
운송 테이블에 추가 여분의 줄 Ui 및 Vj에 대한 열입니다.
U1=0이라고 가정하자.
그러면 V3 = C13 – U1 = 1 – 0 = 1을 찾을 수 있습니다.
V3를 알면 이제 U3를 찾을 수 있습니다.
유사하게 나머지 모든 잠재력을 계산합니다.
6. 잠재적인 방법을 활용한 계획의 최적성 확인
계획의 각 여유 셀에 대해 차이점을 계산합니다.
ΔCij = Cij - (Ui + Vj)
해당 셀의 왼쪽 하단에 결과 값을 씁니다.
계획은 최적의, 모든 차이가 ΔCij ≥ 0인 경우.
안에 이 경우계획 - 최적이 아닌(ΔC22< 0), и его следует улучшить путем перераспределения поставок.
7. 물품 재분배
가장 큰 셀을 찾아보자 절대값음의 차이 ΔCij를 사용하여 이 셀을 제외한 다른 모든 셀이 기본인 사이클을 구성합니다. 그러한 사이클 항상 존재하고 독특하다.
음의 차이가 있는 셀 ΔCij를 "+" 기호로 표시하고 다음 셀은 "-" 기호로 표시하는 식으로 하나씩 표시해 보겠습니다.
그런 다음 "-" 기호(여기서는 5)가 있는 사이클 셀에서 하중의 최소값을 찾아 "+" 기호가 있는 자유 셀에 입력합니다. 그런 다음 사이클의 모든 셀을 순차적으로 살펴보고 최소값을 빼고 추가합니다 (이 셀이 표시된 기호에 따라 마이너스는 빼고 플러스는 추가합니다).
우리는 얻는다 새로운 참조 계획운송:
m + n – 1보다 기본 셀이 더 많기 때문에 값이 0인 기본 셀을 무료로 만듭니다.
잠재적인 값과 차이 ΔCij를 다시 계산합니다.
이번에는 셀의 모든 차이 ΔCij가 양수이므로, 최적의 솔루션을 찾았습니다.
8. 최적의 해를 찾았으면 9단계로 이동하고, 그렇지 않으면 5단계로 이동합니다.
최적의 솔루션을 찾았으므로 9번 항목으로 넘어갑니다.
9. 총 물품 운송 비용 계산
계산해보자 총 배송비화물 ( 지)는 다음 공식에 따라 우리가 찾은 최적의 계획에 해당합니다.
Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110den. 단위
모든 제품에 대한 총 배송비 최적의 솔루션, 조립 110 굴. 단위
10. 교통 그래프 구축
최적의 교통계획을 찾아 시공해 드립니다. 그래프의 정점은 "창고"와 "상점"이 됩니다. 꼭지점에는 해당 매장량과 수요가 표시됩니다. 그래프의 꼭지점을 연결하는 호는 0이 아닌 운송에 해당합니다. 우리는 운송되는 화물의 양을 나타내는 각 호에 서명할 것입니다.
결과는 아래 표시된 것과 유사한 그래프가 됩니다.
이제 운송 문제가 해결되었습니다. 축하해요!
운송 문제의 실제 적용
운송 문제는 많은 경우에 사용됩니다. 이는 원료 및 공급품 공급의 최적화입니다. 제조 기업. 이는 창고에서 창고로의 상품 배송 최적화입니다. 소매 상점. 이것이 최적화다 여객 운송, 그리고 훨씬 더.
Galyautdinov R.R.
© 자료의 복사는 직접 하이퍼링크가 있는 경우에만 허용됩니다.
전송 문제라는 이름 아래 다양한 문제가 단일 수학적 모델로 결합됩니다. 이러한 문제는 선형 계획법 문제에 속하며 잘 알려진 단순 방법을 사용하여 풀 수 있습니다. 그러나 일반적인 교통 문제는 변수가 많아 단순법으로 해결하는 것이 번거롭다. 반면, 운송 문제의 제한 시스템의 매트릭스는 매우 독특하므로 이를 해결하려면, 특별한 방법. 이러한 방법은 다음과 같습니다. 단순법, 초기 지원 솔루션을 찾은 다음 이를 개선하여 최적 솔루션으로 끝나는 일련의 지원 솔루션을 얻을 수 있습니다.
운송 문제의 일반적인 특징
상태:
균질한 화물은 m개의 공급업체에 볼륨 a 1, a 2, ... a m으로 집중되어 있습니다.
이 화물은 b 1, b 2 ... b n의 양으로 n명의 소비자에게 배송되어야 합니다.
모두 다 아는 Cij, i=1,2,...m; j=1,2,...n — 각 i번째 공급자로부터 각 j번째 소비자까지 화물 단위를 운송하는 비용입니다.
모든 공급자의 재고가 전액 운송되고, 모든 소비자의 요구가 완전히 충족되며, 모든 상품 운송에 드는 총 비용이 최소화되는 운송 계획을 수립해야 합니다.
전송 작업의 초기 데이터는 테이블 형식으로 기록됩니다.
작업의 초기 데이터는 다음과 같이 표시될 수 있습니다.
- 벡터 A=(a 1 ,a 2 ,...,am m) 공급업체의 재고
- 벡터 B=(b 1 ,b 2 ,...,bn) 소비자 요청
- 비용 매트릭스:
운송 문제의 수학적 모델
운송 문제의 변수(알 수 없음)는 다음과 같습니다. x ij , i=1,2,...,m j=1,2,...,n - i번째 공급업체에서 각 j번째 공급업체까지의 운송량 소비자.
이러한 변수는 운송 매트릭스로 작성할 수 있습니다.
제품 C ij *X ij는 i번째 공급자로부터 j번째 소비자까지 상품을 운송하는 비용을 결정하므로 모든 상품을 운송하는 데 드는 총 비용은 다음과 같습니다.
문제의 조건에 따라 최소한의 총 비용이 보장되어야 합니다.
따라서 문제의 목적 함수는 다음과 같은 형식을 갖습니다. 
문제 제약 시스템은 두 개의 방정식 그룹으로 구성됩니다.
m 방정식의 첫 번째 그룹은 모든 m 공급업체의 재고가 완전히 수출된다는 사실을 설명하며 다음과 같은 형식을 갖습니다. 
n 방정식의 두 번째 그룹은 모든 n 소비자의 요구를 완전히 충족해야 하는 요구 사항을 표현하며 다음과 같은 형식을 갖습니다.
트래픽 양이 음수가 아닌 조건을 고려하면 수학적 모델은 다음과 같습니다.
운송 문제의 고려된 모델에서는 공급자의 총 재고가 소비자의 총 수요와 동일하다고 가정합니다. 즉:
이런 문제를 문제라고 부른다. 올바른 균형 , 그리고 문제 모델 닫은. 이 평등이 만족되지 않으면 문제를 문제라고 합니다. 잘못된 균형이고 문제 모델은 다음과 같습니다. 열려 있는.
예제 34.1운송 문제의 수학적 공식화는: 찾기 작업 변수 X=(xij), i=1,2,...,m; j=1,2,...,n, 제한 시스템(수학적 모델에서 2번)을 충족하고, (3), 비음성 조건(4)을 충족하고 최소값을 보장합니다. 목적함수 (1)
표 34.2에 주어진 초기 데이터를 사용하여 운송 문제의 수학적 모델을 작성하십시오.
해결책:
1. 작업 변수(교통 매트릭스)를 소개합니다.
2. 비용 매트릭스를 작성합니다.
3. 문제의 목적 함수는 행렬 C와 X의 모든 해당 요소의 곱의 합과 같습니다.
모든 운송의 총 비용을 결정하는 이 함수는 최소값에 도달해야 합니다.
4. 문제에 대한 제약 시스템을 만들어 보겠습니다.
행렬 X의 첫 번째 행에 있는 모든 배송의 합은 첫 번째 공급자의 재고와 같아야 하며, 행렬 X의 두 번째 행에 있는 운송의 합은 두 번째 공급자의 재고와 같아야 합니다. 
이는 공급업체의 재고가 전체적으로 제거됨을 의미합니다.
행렬 X의 각 열의 운송량은 해당 소비자의 요청과 동일해야 합니다.
이는 소비자의 요구가 완전히 충족되었음을 의미합니다.
운송이 부정적일 수 없다는 점도 고려해야 합니다.
답변: 따라서 고려 중인 문제의 수학적 모델은 다음과 같이 작성됩니다.
목적 함수의 최소값(1)을 제공하고 제약 조건 시스템(2)과 비음성 조건(3)을 충족하는 문제 변수를 찾습니다. 