Prompt Title: 최적화이론 공부

제공해주신 파일 내용에 따라 선형 계획법(Linear Programming)의 예제 문제 하나를 구체적인 수치와 함께 설명드리겠습니다.

예제 2.1-1 (Reddy Mikks Company)

Reddy Mikks 회사는 두 가지 자재(M1, M2)를 사용하여 내부용 페인트와 외부용 페인트를 생산합니다. 아래는 이 문제의 기본 데이터를 제공하는 표입니다:

• 외부용 페인트를 만들기 위해 필요한 원료 M1은 톤 당 6톤, M2는 1톤이 필요합니다.
• 내부용 페인트를 만들기 위해 필요한 원료 M1은 톤 당 4톤, M2는 2톤이 필요합니다.
• 원료 M1의 하루 최대 사용 가능량은 24톤, M2는 6톤입니다.
• 외부용 페인트의 이익은 톤 당 $5,000, 내부용 페인트의 이익은 톤 당 $4,000입니다.
• 내부용 페인트의 일일 수요는 외부용 페인트의 일일 수요를 1톤을 초과할 수 없으며, 내부용 페인트의 최대 일일 수요는 2톤입니다.

이 문제를 해결하기 위해 다음과 같은 선형 계획법 모델을 설정할 수 있습니다:

• 결정 변수: $x_1$ = 외부용 페인트의 일일 생산량 (톤), $x_2$ = 내부용 페인트의 일일 생산량 (톤)
• 목적 함수: $z = 5x_1 + 4x_2$ (최대화하고자 하는 총 일일 이익)
• 제약 조건:
  1. $6x_1 + 4x_2 \leq 24$ (원료 M1 사용 제한)
  2. $x_1 + 2x_2 \leq 6$ (원료 M2 사용 제한)
  3. $x_2 - x_1 \leq 1$ (내부용 페인트 수요 제한)
  4. $x_2 \leq 2$ (내부용 페인트 최대 수요 제한)
  5. $x_1, x_2 \geq 0$ (음수가 아닌 생산량)

이러한 모델을 사용하여 심플렉스 방법 또는 그래픽 솔버 등의 최적화 도구를 통해 최적의 생산 계획을 결정할 수 있습니다.

다음으로 예제 2.2-2 (Diet Problem) 에 대해 설명드리겠습니다.

예제 2.2-2 (Diet Problem)에서의 상황 설명:

Ozark Farms는 매일 적어도 800파운드의 특별 사료를 사용해야 합니다. 이 특별 사료는 옥수수와 콩박으로 구성되며, 다음과 같은 구성 요소를 충족해야 합니다:

• 단백질은 최소 30% 이상이어야 합니다.
• 섬유질은 최대 5% 이하여야 합니다.
• 목표는 최소 비용으로 일일 사료 혼합을 결정하는 것입니다.

이 문제를 해결하기 위한 선형 계획법 모델은 다음과 같이 설정됩니다:

• 결정 변수:

  • $x_1$ = 일일 옥수수 사용량 (파운드)
  • $x_2$ = 일일 콩박 사용량 (파운드)

• 목적 함수:

  • $z = 0.3x_1 + 0.9x_2$ (최소화하고자 하는 일일 비용)

• 제약 조건:

  1. $x_1 + x_2 \geq 800$ (일일 최소 사료 요구량)
  2. $0.09x_1 + 0.6x_2 \geq 0.3(x_1 + x_2)$ (단백질 최소량 요구 조건)
  3. $0.02x_1 + 0.06x_2 \leq 0.05(x_1 + x_2)$ (섬유질 최대량 요구 조건)
  4. $x_1, x_2 \geq 0$ (음수가 아닌 사용량)

이러한 제약 조건들을 통해 선형 계획법 모델을 구성하며, 이 모델은 최적의 사료 혼합 비율을 찾아주어 비용을 최소화하면서 영양 요구 사항을 충족시킬 수 있도록 합니다. 이 문제는 실제로 많은 농장에서 사료 비용을 최소화하고 동물의 영양 상태를 유지하는 데 사용될 수 있는 중요한 응용 예입니다.

다음으로 예제 2.4-2 (Single-Period Production Model) 에 대해 설명드리겠습니다.

예제 2.4-2 (Single-Period Production Model):

이 모델은 한 회사가 다양한 의류 제품을 생산하는 상황을 모델링합니다. 이 회사는 파카 재킷, 거위 재킷, 보온 바지, 장갑을 생산하며, 이러한 제품들은 각각 다른 부서에서 제조됩니다: 절단, 보온, 재봉, 포장. 계약에 따라 제품이 납품되지 않을 경우 벌금이 부과됩니다. 목표는 순이익을 최대화하는 최적의 생산 계획을 수립하는 것입니다.

• 제품별 요구 시간 및 이익:

  • 파카 재킷: 절단 0.3시간, 보온 0.25시간, 재봉 0.45시간, 포장 0.15시간, 단위당 이익 $30, 벌금 $15
  • 거위 재킷: 절단 0.3시간, 보온 0.35시간, 재봉 0.5시간, 포장 0.15시간, 단위당 이익 $40, 벌금 $20
  • 보온 바지: 절단 0.25시간, 보온 0.3시간, 재봉 0.4시간, 포장 0.1시간, 단위당 이익 $20, 벌금 $10
  • 장갑: 절단 0.15시간, 보온 0.1시간, 재봉 0.22시간, 포장 0.05시간, 단위당 이익 $10, 벌금 $8

• 목적 함수:

  • $\text{최대화} \, z = 30x_1 + 40x_2 + 20x_3 + 10x_4 - 15s_1 - 20s_2 - 10s_3 - 8s_4$
  • 여기서 $x_i$는 각 제품의 생산량이고, $s_i$는 각 제품의 미납품량입니다.

• 제약 조건:

  • 각 부서의 총 작업 시간은 1000시간을 넘지 않아야 합니다.
    • 절단: $0.3x_1 + 0.3x_2 + 0.25x_3 + 0.15x_4 \leq 1000$
    • 보온: $0.25x_1 + 0.35x_2 + 0.3x_3 + 0.1x_4 \leq 1000$
    • 재봉: $0.45x_1 + 0.5x_2 + 0.4x_3 + 0.22x_4 \leq 1000$
    • 포장: $0.15x_1 + 0.15x_2 + 0.1x_3 + 0.05x_4 \leq 1000$
  • 각 제품의 생산량은 수요를 초과할 수 없습니다.
    • 파카: $x_1 + s_1 = 800$
    • 거위: $x_2 + s_2 = 750$
    • 바지: $x_3 + s_3 = 600$
    • 장갑: $x_4 + s_4 = 500$

이 문제의 해결을 위해 선형 계획법을 사용하여 각 부서의 작업 시간 제약과 제품별 수요를 고려하여 최적의 생산 계획을 세울 수 있습니다. 이를 통해 최대의 순이익을 달성하며, 벌금을 최소화할 수 있습니다.

다음으로 예제 2.4-4 (Multi-Period Production Smoothing Model) 에 대한 설명을 드리겠습니다.

예제 2.4-4 (Multi-Period Production Smoothing Model):

이 문제는 회사가 4개월간의 생산 계획을 수립하여 일정한 인력을 유지하면서 수요를 충족하고자 하는 상황을 모델링합니다. 회사는 3월부터 6월까지 매월 생산량을 조절하여 비용을 최소화하려 합니다. 각 월의 수요와 관련된 변수와 비용을 고려하여 최적의 인력 조정 및 재고 관리 전략을 수립합니다.

• 수요:

  • 3월: 520단위, 4월: 720단위, 5월: 520단위, 6월: 620단위

• 생산 및 비용:

  • 고정 직원은 일정하게 10명이고, 이들은 월별로 12단위씩 생산할 수 있습니다.
  • 임시 직원을 고용하거나 해고하는 비용은 각각 인당 $200, $400입니다.
  • 재고 유지 비용은 단위당 월 $50입니다.

• 목적 함수:

  • 총 비용을 최소화하는 것이 목표입니다. 총 비용은 인력 조정 비용, 재고 유지 비용, 고용 및 해고 비용을 포함합니다.
  • $\text{최소화} \, z = 50(I_1 + I_2 + I_3) + 200(s_1^+ + s_2^+ + s_3^+) + 400(s_1^- + s_2^- + s_3^-)$
  • 여기서 $I_i$는 월별 재고 단위, $s_i^+$는 고용된 임시 직원 수, $s_i^-$는 해고된 임시 직원 수를 나타냅니다.

• 제약 조건:

  • 각 월의 생산량과 재고는 해당 월의 수요를 충족해야 합니다.
  • $x_i + I_{i-1} = d_i + I_i$ (이전 월의 재고와 이번 월의 생산이 이번 월의 수요와 다음 월의 재고를 충족)
  • $x_i$는 고정 직원과 임시 직원의 생산량의 합으로 계산됩니다.
  • 고용 및 해고 결정은 전월 대비 이번 월의 인력 변동을 반영합니다.

이 모델은 생산량을 평활화하고, 인력 조정 및 재고 관리를 통해 비용을 최소화하는 최적의 전략을 제공합니다. 이러한 종류의 모델은 생산 계획, 자원 배분 및 재고 관리에 널리 사용됩니다.

계속해서 예제 2.4-3 (Multi-Period Production-Inventory Model) 에 대해 설명드리겠습니다.

예제 2.4-3 (Multi-Period Production-Inventory Model):

이 모델은 Acme Manufacturing Company가 6개월 동안 계약된 창문 제조를 계획하는 상황을 다룹니다. 회사는 다양한 기간 동안 예상되는 비용 변동을 고려하여, 초과 생산된 유닛을 보관하는 비용을 포함해 총 비용을 최소화하고자 합니다.

• 수요 및 비용:

  • 창문의 6개월 수요: 100, 250, 190, 140, 220, 110개
  • 각 기간별 생산 비용: $50, $45, $55, $48, $52, $50
  • 재고 보관 비용: 단위당 월 $8

• 목적 함수:

  • 총 비용을 최소화하는 것이 목표입니다. 총 비용은 생산 비용과 재고 보관 비용을 포함합니다.
  • $\text{최소화} \, z = \sum_{i=1}^{6} (p_ix_i + 8I_i)$
  • 여기서 $p_i$는 각 기간의 단위당 생산 비용, $x_i$는 각 기간의 생산량, $I_i$는 각 기간 끝에 남은 재고량입니다.

• 제약 조건:

  • 각 기간의 생산량과 재고는 해당 기간의 수요를 충족해야 합니다.
  • $x_1 + I_0 = d_1 + I_1$, $x_2 + I_1 = d_2 + I_2$, 등으로 이어집니다.
  • 초기 재고 $I_0$는 0으로 가정합니다.
  • $x_i$와 $I_i$는 모두 음수가 아니어야 합니다.

이 모델은 시간이 지남에 따라 수요 변동과 비용 변동을 고려하여 최적의 생산 및 재고 계획을 수립합니다. 비용을 최소화하면서 수요를 효과적으로 충족시키기 위한 생산 계획을 제공하여, 재고를 효율적으로 관리하고 불필요한 과잉 생산을 방지합니다. 이러한 종류의 모델은 시즌별 또는 수요 변동이 큰 제품의 생산 계획에 특히 유용합니다.

이제 예제 2.4-4 (Multi-Period Production Smoothing Model) 에 대해 자세히 살펴보겠습니다. 이 예제는 한 회사가 여러 달에 걸쳐 생산 계획을 평활화하는 문제를 다룹니다.

예제 2.4-4 (Multi-Period Production Smoothing Model):

이 모델은 회사가 3월부터 6월까지 4개월 동안 생산을 계획하면서, 일정한 인력을 유지하고, 필요에 따라 임시 직원을 고용하거나 해고하여 수요를 충족시키려고 하는 상황을 모델링합니다. 모델의 목적은 생산, 재고 유지, 고용 및 해고 비용을 포함한 총 비용을 최소화하는 것입니다.

• 수요:

  • 3월: 520단위
  • 4월: 720단위
  • 5월: 520단위
  • 6월: 620단위

• 목적 함수:

  • $\text{최소화} \, z = \text{재고 비용} + \text{고용 비용} + \text{해고 비용}$
  • 재고 비용 = $50 \times (\text{월별 재고 합계})$
  • 고용 비용 = $200 \times (\text{월별 고용된 임시 직원 수})$
  • 해고 비용 = $400 \times (\text{월별 해고된 임시 직원 수})$

• 생산 및 인력 결정 변수:

  • $x_{i}$: 월 $i$의 생산량
  • $s_{i}^{+}$: 월 $i$에 고용된 임시 직원 수
  • $s_{i}^{-}$: 월 $i$에 해고된 임시 직원 수
  • $I_{i}$: 월 $i$의 마지막에 재고량

• 제약 조건:

  • 각 월의 생산과 재고는 해당 월의 수요를 만족해야 합니다.
  • 고정 직원과 임시 직원을 통한 총 생산량은 각 월의 수요와 재고를 포괄해야 합니다.
  • 임시 직원의 숫자 변화는 고용 및 해고를 통해 조절됩니다.

이 모델은 장기간에 걸친 생산 계획을 최적화하여 비용을 최소화하는 동시에 수요 변동에 대응하도록 설계되었습니다. 이는 특히 생산량이나 수요가 계절적 또는 시장 변동성에 따라 변하는 산업에 적합한 접근 방식입니다. 이를 통해 기업은 인력 관리와 재고 수준을 최적화하여 전반적인 운영 효율성을 향상시킬 수 있습니다.

죄송합니다, 제공된 파일의 내용에서 추가적인 예제 문제에 대한 구체적인 정보는 더 이상 포함되어 있지 않습니다. 지금까지 제시된 예제 문제들이 선형 계획법을 적용한 다양한 상황들을 보여주며, 각각의 문제 설정, 목적 함수, 결정 변수, 제약 조건 등을 자세히 설명하고 있습니다.

이러한 문제들은 선형 계획법의 기본 원리와 실제 응용 사례를 이해하는 데 도움을 주며, 최적화 문제를 구조화하고 해결하는 데 필요한 접근 방식을 제공합니다. 추가적인 질문이나 더 자세히 알고 싶은 부분이 있으시면 언제든지 말씀해 주세요!

**예제 9.1-1 (프로젝트 선택 문제)**에서는 다음과 같이 5개의 프로젝트 중에서 3년 계획 기간 동안 최대의 수익을 반환할 프로젝트 조합을 선택하는 문제를 다룹니다.

프로젝트 데이터:

• 프로젝트 1: 연간 지출 $5, $1, $8 백만; 예상 수익 $20 백만
• 프로젝트 2: 연간 지출 $4, $7, $10 백만; 예상 수익 $40 백만
• 프로젝트 3: 연간 지출 $3, $9, $2 백만; 예상 수익 $20 백만
• 프로젝트 4: 연간 지출 $7, $4, $1 백만; 예상 수익 $15 백만
• 프로젝트 5: 연간 지출 $8, $6, $10 백만; 예상 수익 $30 백만

제약 조건:

• 각 연도의 사용 가능한 자금은 $25 백만입니다.

수학적 모델:

• 결정 변수: $x_j$ (프로젝트 $j$가 선택되면 1, 그렇지 않으면 0)
• 목적 함수: 최대화 $20x_1 + 40x_2 + 20x_3 + 15x_4 + 30x_5$
• 제약 조건:
  • 1년차: $5x_1 + 4x_2 + 3x_3 + 7x_4 + 8x_5 \leq 25$
  • 2년차: $1x_1 + 7x_2 + 9x_3 + 4x_4 + 6x_5 \leq 25$
  • 3년차: $8x_1 + 10x_2 + 2x_3 + 1x_4 + 10x_5 \leq 25$

이 모델은 각 연도의 예산 제한을 고려하여 총 수익을 최대화하는 프로젝트의 조합을 찾는 정수 계획 문제입니다. 프로젝트 선택은 예산 내에서 최대 수익을 창출할 수 있는 조합을 결정하는 데 중점을 둡니다.

**예제 9.1-2 (보안 전화 설치 문제)**에 대한 설명을 드리겠습니다. 이 예제에서는 캠퍼스의 주요 거리마다 필요한 최소한의 긴급 전화 설치 위치를 결정하는 문제를 다룹니다.

문제 상황:

• 특정 위치에서 긴급 전화를 설치하여 거리 A를 서비스하려고 합니다. 예를 들어, 위치 1 또는 위치 2가 선택될 수 있습니다.

수학적 모델:

• 결정 변수: $x_j$ (위치 $j$에 전화가 설치되면 1, 그렇지 않으면 0)

목적 함수:

• 최소화: 설치되는 전화기의 총 수

제약 조건:

• 모든 주요 거리가 적어도 하나의 선택된 위치에서 서비스를 받아야 합니다.
• 예시: 거리 A는 위치 1 또는 위치 2 중 하나에서 서비스를 받아야 합니다. 이를 수학적으로 표현하면 $x_1 + x_2 \geq 1$과 같이 됩니다.

이 문제는 "최소 커버링 문제"로 분류되며, 주어진 요구사항을 충족시키기 위해 필요한 최소한의 자원을 선택하는 최적화 문제입니다. 여기서는 캠퍼스 내에 필요한 긴급 전화의 최소 수를 결정하는 것이 목표입니다. 이러한 문제는 네트워크 설계, 시설 위치 결정, 자원 할당 등 다양한 분야에서 응용될 수 있습니다.

**예제 9.1-3 (전화 회사 선택 문제)**를 살펴보겠습니다. 이 문제에서는 월 평균 200분의 장거리 통화를 사용하면서 전화 서비스 비용을 최소화하려고 합니다. 사용 가능한 전화 회사는 MaBell, PaBell, 그리고 BabyBell이 있습니다.

회사 및 요금 정보:

• MaBell: 월 $16, 분당 $0.25
• PaBell: 월 $25, 분당 $0.21
• BabyBell: 월 $18, 분당 $0.22

수학적 모델:

• 결정 변수:
  • $x_1$: MaBell을 사용한 월간 통화 분수
  • $x_2$: PaBell을 사용한 월간 통화 분수
  • $x_3$: BabyBell을 사용한 월간 통화 분수

목적 함수:

• 최소화: $0.25x_1 + 0.21x_2 + 0.22x_3 + 16y_1 + 25y_2 + 18y_3$
  • 여기서 $y_j$는 회사 $j$를 사용하면 1, 아니면 0입니다.

제약 조건:

• $x_1 + x_2 + x_3 = 200$: 총 200분을 사용해야 합니다.
• 각 회사의 사용 여부를 결정하는 $y_j$는 $x_j > 0$ 일 때 1이 되어야 하며, 그렇지 않으면 0이 됩니다.

이 문제는 혼합 정수 선형 프로그래밍(MILP) 모델로 구성되어, 각 회사의 기본 요금과 사용 분당 요금을 고려하여 총 통화 비용을 최소화하는 최적의 사용 계획을 수립합니다. 이러한 모델은 다양한 서비스 제공자 중에서 가격과 서비스 요건을 최적화하여 선택할 때 유용하게 사용될 수 있습니다.

다음으로 예제 9.1-4 (작업 순서 결정 문제) 를 살펴보겠습니다. 이 문제는 한 기계에서 처리해야 할 세 가지 작업의 순서를 결정하여, 모든 작업이 기한 내 완료되도록 하거나, 늦게 완료될 경우의 벌금을 최소화하는 것입니다.

작업 및 데이터:

• 작업 1: 처리 시간 5일, 마감 기한 25일, 하루 지연당 벌금 $19
• 작업 2: 처리 시간 20일, 마감 기한 22일, 하루 지연당 벌금 $12
• 작업 3: 처리 시간 15일, 마감 기한 35일, 하루 지연당 벌금 $34

수학적 모델:

• 결정 변수:
  • $x_i$: 작업 $i$의 시작일
  • $y_{ij}$: 작업 $i$가 작업 $j$ 전에 이루어지면 1, 그렇지 않으면 0

목적 함수:

• 최소화: $19s_1 + 12s_2 + 34s_3$
  • 여기서 $s_i$는 작업 $i$가 마감일을 넘긴 일수입니다.

제약 조건:

• 각 작업은 다른 작업과 동시에 진행될 수 없습니다.
• 작업 순서 및 중복을 방지하기 위한 제약:
  • $x_1 + 5 \leq x_2$ 또는 $x_2 + 20 \leq x_1$
  • $x_1 + 5 \leq x_3$ 또는 $x_3 + 15 \leq x_1$
  • $x_2 + 20 \leq x_3$ 또는 $x_3 + 15 \leq x_2$
• 작업이 마감일을 넘기면 해당 벌금이 부과됩니다.
  • $s_i$는 작업 $i$의 완료일이 마감일을 넘긴 일수로 계산됩니다.

이 문제는 작업 순서와 관련된 최적화 문제로, 특정 자원(이 경우 기계)을 사용하여 여러 작업을 처리할 때 발생할 수 있는 지연과 그에 따른 비용을 최소화하는 방법을 찾는 데 중점을 둡니다. 이러한 유형의 모델은 제조, 프로젝트 관리, 서비스 산업 등 다양한 분야에서 응용될 수 있습니다.

이제 **예제 9.2-1 (Branch and Bound 알고리즘 사용 예제)**를 살펴보겠습니다. 이 예제에서는 정수 선형 프로그래밍 문제를 해결하기 위해 Branch and Bound 방법을 사용합니다.

문제 설명:

정수 제약 조건을 가진 최적화 문제에서, 두 변수 $x_1$과 $x_2$를 사용하여 최대화 문제를 해결하려고 합니다.

수학적 모델:

• 목적 함수: 최대화 $5x_1 + 4x_2$
• 제약 조건:
  • $x_1 + x_2 \leq 6$
  • $10x_1 + 6x_2 \leq 45$
• 변수 제약: $x_1, x_2$는 정수이며, 음수가 아니어야 합니다.

Branch and Bound 알고리즘 설명:

1. LP Relaxation: 먼저, 정수 제약 조건을 완화하여 일반 선형 프로그래밍 문제로 풀어 최적의 연속적인 솔루션을 찾습니다. 이때, 얻은 솔루션은 정수일 필요가 없습니다.
2. Branching: 솔루션이 정수 조건을 만족하지 않으면, 분기를 생성합니다. 예를 들어, $x_1$의 최적 솔루션 값이 정수가 아니라면, $x_1$의 값을 둘러싼 두 개의 새로운 문제(예: $x_1 \leq 3$ 및 $x_1 \geq 4$)를 생성하여 분기합니다.
3. Bounding: 각 분기에서 문제를 다시 풀어보고, 이전에 얻은 최적 값보다 더 좋은 결과를 얻을 수 있는지 확인합니다. 만약 얻은 솔루션이 최적 솔루션보다 나쁘거나, 더 이상 개선할 수 없다면 그 분기를 버립니다.

예제의 해결:

이 예제에서는 먼저 LP를 풀어 $x_1$과 $x_2$의 최적 솔루션을 얻습니다. 만약 이 솔루션이 정수가 아니면, Branch and Bound를 사용하여 가능한 모든 경우의 수를 탐색하고, 가장 좋은 정수 솔루션을 찾아냅니다. 이 방법은 더 이상 개선할 가능성이 없을 때까지 반복됩니다.

이 방식은 복잡한 정수 최적화 문제에서 정수 솔루션을 찾기 위한 효율적인 방법을 제공하며, 다양한 산업 및 연구 분야에서 중요한 도구로 활용됩니다.

계속해서 예제 9.2-1 (Branch and Bound 알고리즘) 에 대해 더 자세히 살펴보겠습니다. 이 예제에서는 이전 설명에 이어서 Branch and Bound 알고리즘의 구체적인 구현 단계를 논의합니다.

Branch and Bound 알고리즘의 진행:

1. 초기화: 최적화 문제의 정수 제약을 완화하여, 선형 프로그래밍(LP) 문제로 풉니다. 이 과정에서 최초의 최적 솔루션을 얻습니다. 예를 들어, $x_1$과 $x_2$의 최적 연속 솔루션이 얻어집니다.

2. 분기 생성: 솔루션 중 정수가 아닌 값을 가진 변수를 선택하여, 해당 변수에 대한 분기를 생성합니다. 분기는 변수의 값이 될 수 있는 가장 가까운 정수보다 작거나 크도록 두 개의 새로운 문제를 만듭니다.

3. Bounding과정: 각 분기에서 새로운 LP 문제를 풀고, 그 결과를 이용해 현재까지의 최적값과 비교합니다. 만약 새로운 솔루션이 이전의 최적 솔루션보다 나쁘거나 동일하다면, 해당 분기는 더 이상 탐색하지 않고 버립니다.

4. 최적 솔루션 결정: 가능한 모든 분기를 탐색한 후, 최적의 정수 솔루션을 결정합니다.

예제 상세:

• 초기 LP 솔루션에서 $x_1$과 $x_2$의 값이 정수가 아닌 경우, $x_1 \leq 3$과 $x_1 \geq 4$로 문제를 분기합니다.
• 각 분기에서 문제를 다시 풀어 최적 솔루션을 찾습니다. 이 경우, $x_1 \leq 3$의 분기가 $x_1 = 3$과 $x_2 = 2$로 최적 솔루션이 계산될 수 있습니다.
• 만약 $x_1 \geq 4$ 분기가 더 나은 솔루션을 제공하지 않는다면, $x_1 = 3$과 $x_2 = 2$를 최종 솔루션으로 선택합니다.

이 예제는 Branch and Bound 알고리즘이 복잡한 정수 프로그래밍 문제에서 어떻게 효과적인 해결책을 제공할 수 있는지 보여줍니다. 이 방법은 계산 비용이 높을 수 있지만, 많은 실제 문제에서 정확한 최적 솔루션을 얻는 데 필수적입니다.

이 파일에서 다루는 다음 예제는 제공된 내용에 따라 더 이상 포함되어 있지 않습니다. 그동안 제공된 예제들을 통해 다양한 유형의 정수 프로그래밍 문제와 그 해결 방법에 대해 살펴보았습니다. 이러한 문제들은 주로 최적화 이론을 바탕으로 실제 세계의 복잡한 결정 문제를 수학적 모델로 표현하고 해결하는 방법을 제공합니다.

추가적인 설명이나 다른 내용에 대해 더 알고 싶으시면 언제든지 질문해 주세요!

시설 입지 문제 (Facility Location Problem) 예제에서는 제조업체 Y가 세 지역의 소비자에게 제품을 공급하기 위한 최적의 생산 공장 위치와 각 공장에서 각 고객까지의 운송량을 결정하는 문제를 다룹니다. 이 문제는 총 비용(고정비용 + 운송비용)을 최소화하는 것을 목표로 합니다.

문제 상세:

• 공장 위치와 공급 능력:
  • 공장 1: 최대 공급량 1800단위
  • 공장 2: 최대 공급량 1400단위
  • 공장 3: 최대 공급량 1300단위
• 고객 및 수요량:
  • 고객 1: 수요량 800단위
  • 고객 2: 수요량 800단위
  • 고객 3: 수요량 1600단위
• 운송 비용:
  • 공장 1에서 각 고객까지: $10, $15, $12
  • 공장 2에서 각 고객까지: $17, $14, $20
  • 공장 3에서 각 고객까지: $15, $10, $11
• 고정비용:
  • 공장 1: $12,000
  • 공장 2: $11,000
  • 공장 3: $12,000

수학적 모델:

• 결정 변수:
  • $x_{ij}$: 공장 $i$에서 고객 $j$로의 운송량
  • $y_i$: 공장 $i$가 선택되면 1, 아니면 0
• 목적 함수:
  • 최소화 $\sum_{i=1}^{3} 12000y_i + \sum_{i=1}^{3} \sum_{j=1}^{3} t_{ij}x_{ij}$
    • 여기서 $t_{ij}$는 공장 $i$에서 고객 $j$로의 단위 운송 비용입니다.
• 제약 조건:
  • 각 공장의 운송량은 해당 공장의 공급 능력을 초과할 수 없습니다:
    • $\sum_{j=1}^{3} x_{ij} \leq q_i y_i$ (여기서 $q_i$는 공장 $i$의 최대 공급량)
  • 각 고객의 수요를 만족해야 합니다:
    • $\sum_{i=1}^{3} x_{ij} \geq d_j$ (여기서 $d_j$는 고객 $j$의 수요량)
  • $x_{ij} \geq 0$, $y_i \in \{0, 1\}$

이 문제는 고정 비용과 변동 비용(운송 비용)을 고려하여 최소 총비용으로 공급망을 구성하는 최적의 입지 및 할당 계획을 수립하는 복합 최적화 문제입니다. 이러한 유형의 문제는 공급망 관리, 네트워크 설계, 도시 계획 등 다양한 분야에서 매우 중요합니다.

시설 입지 문제(Facility Location Problem)의 구체적인 수치와 함께 모델을 자세히 설명하겠습니다.

공장과 고객 정보:

• 공장들:
  • 공장 1: 최대 공급량 1800단위, 고정 비용 $12,000
  • 공장 2: 최대 공급량 1400단위, 고정 비용 $11,000
  • 공장 3: 최대 공급량 1300단위, 고정 비용 $12,000
• 고객 및 수요:
  • 고객 1: 수요량 800단위
  • 고객 2: 수요량 800단위
  • 고객 3: 수요량 1600단위

운송 비용 ($):

• 공장 1에서 고객까지:
  • 고객 1: $10, 고객 2: $15, 고객 3: $12
• 공장 2에서 고객까지:
  • 고객 1: $17, 고객 2: $14, 고객 3: $20
• 공장 3에서 고객까지:
  • 고객 1: $15, 고객 2: $10, 고객 3: $11

수학적 모델 설명:

결정 변수:

• $x_{ij}$: 공장 $i$에서 고객 $j$로 운송되는 제품의 단위 수
• $y_i$: 공장 $i$가 활성화되면 1, 아니면 0

목적 함수:

• 총 비용을 최소화하는 것:
  $$\text{Minimize} \quad Z = 12000y_1 + 11000y_2 + 12000y_3 + (10x_{11} + 15x_{12} + 12x_{13} + 17x_{21} + 14x_{22} + 20x_{23} + 15x_{31} + 10x_{32} + 11x_{33})$$

제약 조건:

• 각 공장의 운송량은 해당 공장의 최대 공급량을 초과할 수 없습니다:

  $$x_{11} + x_{12} + x_{13} \leq 1800y_1$$
  $$x_{21} + x_{22} + x_{23} \leq 1400y_2$$
  $$x_{31} + x_{32} + x_{33} \leq 1300y_3$$

• 각 고객의 수요량은 충족되어야 합니다:

  $$x_{11} + x_{21} + x_{31} \geq 800$$
  $$x_{12} + x_{22} + x_{32} \geq 800$$
  $$x_{13} + x_{23} + x_{33} \geq 1600$$

• 비음수성과 이진성:

  $$x_{ij} \geq 0, \quad y_i \in \{0, 1\}$$

이 문제는 공급망 최적화의 일부로, 운송 비용과 고정 비용을 동시에 고려하여 공장 위치와 운송 계획을 최적화합니다. 각 공장의 활성화 여부는 고정 비용과 연관되어 있으며, 각 고객에게 필요한 제품을 최소 비용으로 제공하기 위해 어떤 공장을 사용할지 결정하는 것이 중요합니다. 이러한 최적화 문제는 복잡한 공급망에서 효율적인 운영 계획을 수립하는 데 매우 중요합니다.