Download presentation
Presentation is loading. Please wait.
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 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 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 より y 100 y=-2x+100 x 0(0,0) 50 ©ATSUTO NISHIO
7
② x + 2y ≦ 120 より y 100 x 2 60 y=- +60 x 0(0,0) 50 ©ATSUTO NISHIO
8
③ x ≦ 40 より y x = 40 100 60 x 0(0,0) 40 50 ©ATSUTO NISHIO
9
④ y ≦ 55 より y 100 y = 55 60 55 x 0(0,0) 40 50 ©ATSUTO NISHIO
10
⑤ x≧0 、 ⑥ y≧0 より y 100 60 55 実行可能 範囲(解) x 0(0,0) 40 50 ©ATSUTO NISHIO
11
目的関数 より y 100 2 3 z 2 y=- x+ 60 55 x 0(0,0) 40 50 ©ATSUTO NISHIO
12
最適解 実行可能範囲と目的関数の交わる(接する)点のx座標、y座標が求めるx、y。 y=-2x+100 と y=- +60 x の交点の座標
y=-2x+100 と y=- +60 の交点の座標 55 x 2 x 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 (最大利益) y x 2 100 60 55 C x 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 (何も生産しない) y 100 点 A(40,0) Z=3×40=120 60 55 E 点 E(0,55) Z=2×55=110 O x A 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 需要側供給側 Ⅰ Ⅱ Ⅲ
需要側供給側 Ⅰ Ⅱ Ⅲ 合計 A x11 c11 x12 c12 x13 c13 S1 B x21 c21 x22 c22 x23 c23 S2 D1 D2 D3 T 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
Similar presentations
© 2025 slidesplayer.net Inc.
All rights reserved.