線形計画法(Linear Programming,LP)

Similar presentations


Presentation on theme: "線形計画法(Linear Programming,LP)"— Presentation transcript:

1 線形計画法(Linear Programming,LP)
2020/4/8 線形計画法(Linear Programming,LP) 計画を立案する際に、さまざまな制約を受ける。 たとえば、資源の利用量、製造条件、法的規制など このような制約(条件)のもとで、最適化(利益の最大化、コストの最小化など)を達成するための手法。 生産計画問題、混合問題、輸送問題など多くの適用例がある。 ©ATSUTO NISHIO

2 例題 ある会社で、2種の部品A,Bを作っている。 部品を1ロット作るために必要なそれぞれの機械の使用時間は次の表の通りである。 A B 部品
A   B 1日の使用可時間(分) 機械 M1 M2 M3 M4 2    1 1    2      1 100 120  40  55 3    2 ロット当りの利益(万円) ©ATSUTO NISHIO

3 例題 最大の利益を得るためには、毎日部品ABを1日何ロットずつ 作ればよいか? また、そのときの利益は1日いくらか? 1日Aを x ロット、Bを y ロット作るとすると、 部品 A   B 1日の使用可能時間(分) 機械 M1 M2 M3 M4 2    1 1    2      1 100 120  40  55 3    2 ロット当りの利益(万円) x   y 生産ロット数 ©ATSUTO NISHIO

4 制約条件の数式化 制約条件を数式で示すと、 M1 : 2x + y ≦ 100 M2 : x + 2y ≦ 120 (制約条件) M3 : x ≦ 40 M4 : y ≦ 55 ただし、x≧0、y≧0 (非負条件) のもとで利益 f(r)=3x+2y = Z ⇒ 最大 (目的関数) とするようなx、yを求める。 ©ATSUTO NISHIO

5 制約条件の数式化 制約条件を数式で示すと、 2x + y ≦ 100 ・・・ ① x + 2y ≦ 120 ・・・ ② x ≦ 40 ・・・ ③ y ≦ 55 ・・・ ④ x ≧ 0 ・・・・ ⑤ y ≧ 0 ・・・・ ⑥ f(r)=3x+2y ・・・・ ⑦ ©ATSUTO NISHIO

6 ① 2x + y ≦ 100 より 100 y=-2x+100 0(0,0) 50 ©ATSUTO NISHIO

7 ② x + 2y ≦ 120 より 100 60 y=-   +60 0(0,0) 50 ©ATSUTO NISHIO

8 ③ x ≦ 40 より x = 40 100 60 0(0,0) 40 50 ©ATSUTO NISHIO

9 ④ y ≦ 55 より 100 y = 55 60 55 0(0,0) 40 50 ©ATSUTO NISHIO

10 ⑤ x≧0 、 ⑥ y≧0 より 100 60 55 実行可能    範囲(解) 0(0,0) 40 50 ©ATSUTO NISHIO

11 目的関数 より 100 y=-   x+ 60 55 0(0,0) 40 50 ©ATSUTO NISHIO

12 最適解 実行可能範囲と目的関数の交わる(接する)点のx座標、y座標が求めるx、y。 y=-2x+100 と y=- +60 x の交点の座標
y=-2x+100 と y=-  +60  の交点の座標 55 0(0,0) 40 50 ©ATSUTO NISHIO

13 最適解 x 2 C 連立方程式 y=-2x+100 y=- +60 より x=26.7 y=46.7 ∴ Z=3×26.7+2×46.7
y=-2x+100  y=-   +60 より x=26.7 y=46.7 ∴ Z=3×26.7+2×46.7    =173.5 (最大利益) 100 60 55 0(0,0) 40 50 ©ATSUTO NISHIO

14 実行可能範囲(解)について 点 O(0,0) Z=0 (何も生産しない) 点 A(40,0) Z=3×40=120 E 点 E(0,55)
  Z=0 (何も生産しない) 100 点 A(40,0)   Z=3×40=120 60 55 点 E(0,55)   Z=2×55=110 0(0,0) 40 50 ©ATSUTO NISHIO

15 グラフによる解法の限界 部品数がA、Bの2種類の場合はグラフによる解法が可能であるが、部品数が3種類以上になると、軸がx、y、z、・・・となるためグラフでは解けない。 そこで 単体表(シンプレックス表)を利用する。 ©ATSUTO NISHIO

16 LPの輸送型問題への適用 c:単位あたりの輸送コスト x:輸送数量 D:需要量 S:供給量 ∑D = ∑S = T 需要側供給側 Ⅰ Ⅱ Ⅲ
    需要側供給側 合計      x11 c11      x12 c12      x13 c13 S1      x21 c21      x22  c22      x23 c23 S2 D1 D2 D3 c:単位あたりの輸送コスト     x:輸送数量    D:需要量      S:供給量   ∑D = ∑S = T ©ATSUTO NISHIO

17 制約条件 A : x11 + x12 + x13 = S1 B : x21 + x22 + x23 = S2
A : x11 + x12 + x13 = S1 B : x21 + x22 + x23 = S2 Ⅰ : x11 + x21      = D1 Ⅱ : x12 + x22      = D2 Ⅲ : x13 + x23      = D3  x11 , x12 , x13  , x21 , x22 , x23 ≧ 0 このとき  x11c11 +x12c12 +x13c13 +x21c21 +x22c22 +x23c23 = Z を最小にするような x11 , x12 , x13  , x21 , x22 , x23 を求める。 ©ATSUTO NISHIO


Download ppt "線形計画法(Linear Programming,LP)"

Similar presentations


Ads by Google