-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジン https://www.msi.co.jp/nuopt/ 2022 Vol.5 ( 2022 年 9 月 7 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジンでは，数理計画法パッケージ Nuorium Optimizer をはじめとして，最適化に関する様々な情報や ご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> 数理最適化におけるパラドックス ■ <トピック> 学会出展のご案内 ■ <セミナー> オンラインセミナーのご案内 ■ < tips > 使ってみよう PySIMPLE（第 20 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> 数理最適化におけるパラドックス ****************************************************************** パラドックスという言葉をご存じでしょうか． 直感と反する結果や受け入れがたい結論が得られる事をパラドックスと 言います．有名なパラドックスとして誕生日のパラドックスやモンティ ホール問題などがあります． あまり知られていませんが，実は数理最適化の分野でもパラドックスと 呼ぶことのできる，直感に反した現象が発生します． 本記事でご紹介する例は no-wait flow-shop paradox です． flow-shop とは全てのジョブが同じ工程順序で処理されるような生産方法の ことです． 全てのジョブが異なる工程順序で処理されるような生産方法を job-shop と 呼び，こちらの方が聞き慣れている方も多いかと思います． no-wait という接頭語は，ジョブを前工程で処理した後に休むことなく 後工程で処理することを意味しています．no-wait flow-shop において， 全てのジョブが完了するまでの所要時間（メイクスパン）を最小化する 問題を no-wait flow-shop problem と呼びます． さて，メイクスパンを極力小さくするためにはどのようなデータが理想 でしょうか． 直感的には，工程に用いる機械の性能が非常に良ければ処理時間も小さく なり，全体のメイクスパンも小さくなる，と感じられるでしょう． しかし，残念ながらこの直感に反する例，つまり，機械の性能を良く してもメイクスパンが悪化する例が no-wait flow-shop problem に 存在します． 具体例が気になる方は以下の記事をご覧ください． https://www.msiism.jp/article/no-wait-flow-shop-paradox.html 他の例として輸送問題におけるパラドックス transportation paradox が あります．こちらは「供給量と需要量を増加させるとコストとなる 目的関数が減少する」という現象を指します． 供給量と需要量を増加させているので輸送量が増え，コストも増加すると いう直感に反した結果です． transportation paradox については発生する条件も研究されています． 興味のある方はぜひ調べてみてください． 皆さんの業務でも「改善したつもり」になっている例はありませんか？ 数理最適化におけるパラドックスのように，もしかすると何かしらの 制約条件やデータの性質が影響を与えている可能性があります． 直感に惑わされずにきちんとしたモデルを用意して検証してみると， 何かヒントが得られるかもしれませんね． （石橋 保身） ****************************************************************** ■ <トピック> 学会出展のご案内 ****************************************************************** 9 月 13 日～14 日に朱鷺メッセで開催される日本オペレーションズ・ リサーチ学会 2022 年秋季研究発表会（ https://orsj.org/nc2022f/ ） において，ブースを出展いたします．ブースでは Nuorium Optimizer の ご紹介をいたします． また，以下の学会等においては広告の出稿やパンフレットの配布を行って おります．ぜひご覧ください． - 電気学会 電力・エネルギー部門大会 2022 年 9 月 7 日～9 日 https://www.iee.jp/pes/b_event_r04/ - スケジューリング・シンポジウム 2022 年 9 月 16 日～17 日 http://www.scheduling.jp/symposium/2022/ - RAMP 数理最適化シンポジウム 2022 年 10 月 6 日～7 日 https://orsj.org/ramp/ramp2022/ ※ 学会の開催状況等により予定が変更になる場合がございます． （島田 直樹） ****************************************************************** ■ <セミナー> オンラインセミナーのご案内 ****************************************************************** 11 月までに開催する無料のオンラインセミナーをご紹介します． 9 月には製造系のスケジューリングに関するセミナーを開催します． 数理最適化とは何か，という基本的なところから入りますので， どなたもお気軽にご参加ください． また，定例の紹介セミナーとハンズオンセミナーも開催予定です． ハンズオンセミナーは実際に製品を動かしながら受講いただける セミナーになっています．こちらもぜひお気軽にご参加ください． [ 製造現場の業務改善に向けた数理最適化ソリューション紹介セミナー ] 2022 年 09 月 15 日 (木) 13:30～15:30 詳細とお申込み：https://www.msi.co.jp/nuopt/seminar/manufacture.html [ Nuorium Optimizer 紹介セミナー ] 2022 年 10 月 13 日 (木) 13:30～15:30 2022 年 11 月 30 日 (水) 13:30～15:30 詳細とお申込み：https://www.msi.co.jp/nuopt/seminar/introduction.html [ Nuorium Optimizer ハンズオンセミナー ] 2022 年 10 月 04 日 (火) 13:30～16:00 詳細とお申込み：https://www.msi.co.jp/nuopt/seminar/hands-on.html （池田 悠） ****************************************************************** ■ < tips > 使ってみよう PySIMPLE（第 20 回） ****************************************************************** このコーナーでは，Nuorium Optimizer の Python インターフェースである PySIMPLE のエッセンスを紹介していきます． 今回は数理最適化によく登場する 0-1 整数変数を用いたテクニックを紹介 します．0-1 整数変数は「状態の on/off」を表現するのに使われることも 多く，通常 1 を on 状態として扱います． PySIMPLE では 0-1 整数変数の宣言に専用のキーワード BinaryVariable が 用意されています． ------------------------------------------------------------------ >>> i = Element(value=[1, 2, 3], name='i') >>> z = BinaryVariable(index=i, name='z') >>> z z: z[1] z[2] z[3] ------------------------------------------------------------------ 今回は運転計画問題やスケジューリング問題でよくみられる起動・停止を 表現してみましょう．まずは準備として，各時刻での機器の稼働状態を表す 変数 z と，停止→起動となった時刻を検知する変数 zs を用意します． 挙動の確認のため，時刻 3, 4 に稼働しているとしてみましょう． ------------------------------------------------------------------ t = Element(value=range(1, 6)) # 時刻 z = BinaryVariable(index=t) # 稼働フラグ(時刻 t に稼働していたら 1) zs = BinaryVariable(index=t) # 起動フラグ(時刻 t に起動するときに 1) p = Problem() p += z[3] == 1 # 時刻 3, 4 は稼働 p += z[4] == 1 # p += z[t<(3, 4)] == 1 とも書ける p += z[1] == zs[1] # 時刻 1 は個別 t1 = t>1 p += z[t1] - z[t1-1] <= zs[t1], 'z と zs の関係定義' p += Sum(z[t] + zs[t]) # 稼働時間と起動回数は少なく p.solve(silent=True) Printf('{}: z={}, zs={}', t, z[t].val, zs[t].val) ------------------------------------------------------------------ この出力は以下となります． ------------------------------------------------------------------ 1: z=0, zs=0 2: z=0, zs=0 3: z=1, zs=1 4: z=1, zs=0 5: z=0, zs=0 ------------------------------------------------------------------ zs[3] が 1 になっており，時刻 2 → 3 の起動時刻を表現できています． 例えば，起動コストを表現したい場合は「起動コスト*zs[t]」とすればよい ことになります．停止状態の表現も同様です． 今度は機器の最低連続稼働時間を表現してみましょう．スケジューリング 問題の場合は最低連勤務働時間となります． ------------------------------------------------------------------ t = Element(value=range(1, 11)) # 時刻 i = Element(set=t.set) span = Parameter(value=5) # 最低連続稼働時間 z = BinaryVariable(index=t) # 稼働フラグ(時刻 t に稼働していたら 1) zs = BinaryVariable(index=t) # 起動フラグ(時刻 t に起動するときに 1) p = Problem() p += z[2] == 1 # 時刻 2, 9 は稼働 p += z[9] == 1 # p += z[t<(2, 9)] == 1 とも書ける p += z[1] <= zs[1] # 時刻 1 は個別 t1 = t>1 p += z[t1] - z[t1-1] <= zs[t1], 'z と zs の関係定義' it = Condition((i,t), (t-span+1<=i, i<=t)) p += Sum(zs[it(0)], it(0)) <= z[it(1)], '最低連続稼働時間制約' #p += Sum(zs[t]) <= 1 # 起動は 1 度まで p += Sum(z[t]) p.solve(silent=True) Printf('{:2}: z={}, zs={}', t, z[t].val, zs[t].val) ------------------------------------------------------------------ この出力は以下となります． ------------------------------------------------------------------ 1: z=0, zs=0 2: z=1, zs=1 3: z=1, zs=0 4: z=1, zs=0 5: z=1, zs=0 6: z=1, zs=0 7: z=0, zs=0 8: z=0, zs=0 9: z=1, zs=1 10: z=1, zs=0 ------------------------------------------------------------------ 機器が時刻 2 から 6 まで稼働しており，最低連続稼働時間を満たしている ことがわかります．最低連続稼働時間制約は「時刻 t-span+1 から t まで の間に起動したならば時刻 t は稼働していなければならない」ことを表現 しています．最低連続稼働時間制約は他にも類似ケースが考えられます． - 開始時における累積稼働時間が与えられている - 時刻 1 と最終時刻が繋がっている - 最低連続停止時間 いずれも同様に定式化が可能ですので考えてみてください． 0-1 整数変数の説明はこちら: https://www.msi.co.jp/nuopt/docs/v24/pysimple/guide/binaryvariable.html 0-1 整数変数を用いたテクニックの説明はこちら: https://www.msi.co.jp/nuopt/docs/techniques/articles/indicator-variables.html （池田 悠） ================================================================== ※ msi-ms@ml.msi.co.jp は送信専用アドレスです。 本メールにそのままご返信いただいてもご回答いたしかねます。 ※ このメールは、弊社ツールのユーザー様、過去に展示会などで お名刺等を頂いたことのある方や 当社に直接お問合せを頂いたことの ある方にお送りしています。 ※ バックナンバーはこちらから御覧頂けます。 https://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します。 ※ 今後、ご案内メールが不要な方は、誠にお手数ですが、下記 URL より 「案内停止手続き」をしてくださいますようお願いいたします。 ■ 案内停止はこちらから ■ [都合により本ページでは URL を掲載しておりません] ご登録される情報は、暗号化された通信(SSL)で保護され、プライバシーマークや ISO27001/JIS Q 27001, ISO20000-1, ISO9001の 認証を取得している 株式会社パイプドビッツによる情報管理システム「スパイラル」で安全に管理されます。 上記にアクセスができない場合には「メール不要」と明記の上、 nuopt-info@ml.msi.co.jp までご連絡いただけますと幸いです。 発行：株式会社 NTT データ数理システム << 数理システム Nuorium Optimizer >> 担当 東京都新宿区信濃町 35 番地 信濃町煉瓦館 1 階 tel : 03-3358-6681 e-mail : nuopt-info@ml.msi.co.jp ==================================================================