{"created":"2023-07-27T07:47:33.101795+00:00","id":22133,"links":{},"metadata":{"_buckets":{"deposit":"4b0ed9e5-55e4-43d5-ad99-54a442bf744c"},"_deposit":{"created_by":20,"id":"22133","owners":[20],"pid":{"revision_id":0,"type":"depid","value":"22133"},"status":"published"},"_oai":{"id":"oai:doshisha.repo.nii.ac.jp:00022133","sets":["4251:8393:8394:8395:8403","8:3372:3812:3820"]},"author_link":["18584","2484","15621"],"item_1693811493084":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_1694490770713":{"attribute_name":"権利者情報","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"DA03974933","nameIdentifierScheme":"AID"}],"rightHolderNames":[{"rightHolderLanguage":"ja","rightHolderName":"同志社大学理工学研究所"},{"rightHolderLanguage":"en","rightHolderName":"Science and Engineering Research Institute of Doshisha University"}]}]},"item_1_biblio_info_14":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2013-04-30","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicPageEnd":"100","bibliographicPageStart":"95","bibliographicVolumeNumber":"54","bibliographic_titles":[{"bibliographic_title":"同志社大学理工学研究報告","bibliographic_titleLang":"ja"},{"bibliographic_title":"The Science and Engineering Review of Doshisha University","bibliographic_titleLang":"en"}]}]},"item_1_description_12":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"本論文では,フローネットワークにおける最適化問題の1つである,最小費用流問題に着目する.最小費用流問題とは,容量制約と需要条件を満たすフローの中で,そのコストが最小となるフローを求める問題で,実社会に広く応用されている問題である.この最小費用流問題を解くアルゴリズムとして,最も効率的であるのがネットワークシンプレックス法である.このアルゴリズムは木構造と呼ばれるものを更新し,最小費用流問題の最適解を求めるアルゴリズムであるが,更新が収束しない現象が頻繁に起こる.この現象は巡回と呼ばれ,巡回は強認容木構造をと呼ばれる特別な木構造を保つことで防ぐことができる.本論文では,この強認容木構造を保ちながら更新するための新しい方法について述べる.この新しい方法を第一閉鎖辺選択規則と呼ぶ.この方法はネットワークシンプレックス法における巡回の数学的構造をあきらかにする,重要な役割を果たす.","subitem_description_language":"ja","subitem_description_type":"Abstract"},{"subitem_description":"In the present paper, we focus on the minimum cost flow problem which is one of the well-known optimization problems on flow-networks. The minimum cost flow problem is the problem for finding the minimum cost flow which satisfies the given capacity conditions and the demand conditions. It is known to have wide applications to real fields. The network simplex algorithm is known as the most efficient algorithm for solving the minimum cost flow problem. This algorithm gives an optimal solution to the minimal cost flow problem by updating the so called tree structure, but it does not necessarily terminate in a finite number of steps, even for small networks. This infinite iteration is caused by the cycling of tree structure. It is known that the cycling in the network simplex algorithm can be prevented by maintaining a special type of the tree structure, that is called a strongly admissible tree structure. In the present paper, we give a new rule for updating the tree structure, by which the strongly admissible tree structure is maintained. We call this new rule, rule of the first blocking edge. This will play a key role in clarifying the mathematical structure of the cycling in the network simplex algorithm.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_1_description_25":{"attribute_name":"フォーマット","attribute_value_mlt":[{"subitem_description":"application/pdf","subitem_description_type":"Other"}]},"item_1_identifier_registration":{"attribute_name":"ID登録","attribute_value_mlt":[{"subitem_identifier_reg_text":"10.14988/pa.2017.0000013085","subitem_identifier_reg_type":"JaLC"}]},"item_1_publisher_15":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"同志社大学理工学研究所","subitem_publisher_language":"ja"}]},"item_1_publisher_16":{"attribute_name":"出版者（英）","attribute_value_mlt":[{"subitem_publisher":"Science and Engineering Research Institute of Doshisha University","subitem_publisher_language":"en"}]},"item_1_relation_24":{"attribute_name":"関連サイト","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_language":"ja","subitem_relation_name_text":"掲載刊行物所蔵情報へのリンク ／ Link to Contents"}],"subitem_relation_type":"isFormatOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doors.doshisha.ac.jp/opac/opac_link/bibid/SB00960326/?lang=0","subitem_relation_type_select":"URI"}}]},"item_1_select_10":{"attribute_name":"所属機関識別子種別","attribute_value_mlt":[{"subitem_select_item":"kakenhi"}]},"item_1_select_11":{"attribute_name":"所属機関識別子","attribute_value_mlt":[{"subitem_select_item":"34310"}]},"item_1_source_id_17":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"00368172","subitem_source_identifier_type":"PISSN"}]},"item_1_source_id_19":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00165868","subitem_source_identifier_type":"NCID"}]},"item_1_subject_27":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"417","subitem_subject_scheme":"NDC"}]},"item_1_text_8":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_language":"ja","subitem_text_value":"米田, 彩香 / Graduate School of Science and Engineering, Doshisha University"},{"subitem_text_language":"ja","subitem_text_value":"渡辺, 扇之介 / Graduate School of Science and Engineering, Doshisha University"},{"subitem_text_language":"ja","subitem_text_value":"渡邊, 芳英 / 同志社大学理工学部数理システム学科教授"}]},"item_1_text_9":{"attribute_name":"著者所属（英）","attribute_value_mlt":[{"subitem_text_language":"en","subitem_text_value":"Doshisha University"}]},"item_access_right":{"attribute_name":"アクセス権","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"米田, 彩香","creatorNameLang":"ja"},{"creatorName":"ヨネダ, サヤカ","creatorNameLang":"ja-Kana"},{"creatorName":"Yoneda, Sayaka","creatorNameLang":"en"}],"nameIdentifiers":[{},{}]},{"creatorNames":[{"creatorName":"渡辺, 扇之介","creatorNameLang":"ja"},{"creatorName":"ワタナベ, センノスケ","creatorNameLang":"ja-Kana"},{"creatorName":"Watanabe, Sennosuke","creatorNameLang":"en"}],"nameIdentifiers":[{},{},{}]},{"creatorNames":[{"creatorName":"渡邊, 芳英","creatorNameLang":"ja"},{"creatorName":"ワタナベ, ヨシヒデ","creatorNameLang":"ja-Kana"},{"creatorName":"Watanabe, Yoshihide","creatorNameLang":"en"}],"nameIdentifiers":[{},{},{},{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2013-05-29"}],"displaytype":"detail","filename":"023054010013.pdf","filesize":[{"value":"354.4 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"023054010013.pdf","url":"https://doshisha.repo.nii.ac.jp/record/22133/files/023054010013.pdf"},"version_id":"8492c9ce-4ce6-450e-913e-ed2dd102f819"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"最小費用流問題","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"ネットワークシンプレックス法","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"木構造","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"巡回","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"minimum cost flow problem","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"network simplex algorithm","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"tree structure","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"cycling","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"departmental bulletin paper","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"ネットワークシンプレックス法における巡回を防ぐ方法","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"ネットワークシンプレックス法における巡回を防ぐ方法","subitem_title_language":"ja"},{"subitem_title":"ネットワーク シンプレックスホウ ニオケル ジュンカイ オ フセグ ホウホウ","subitem_title_language":"ja-Kana"},{"subitem_title":"A new rule for preventing the cycling in the network simplex algorithm","subitem_title_language":"en"}]},"item_type_id":"1","owner":"20","path":["3820","8403"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2013-05-29"},"publish_date":"2013-05-29","publish_status":"0","recid":"22133","relation_version_is_last":true,"title":["ネットワークシンプレックス法における巡回を防ぐ方法"],"weko_creator_id":"20","weko_shared_id":-1},"updated":"2023-12-06T00:30:23.331143+00:00"}