{"created":"2023-07-27T07:47:14.125473+00:00","id":21797,"links":{},"metadata":{"_buckets":{"deposit":"f70c3c84-e1ef-41c2-bbd5-bc6f11b559df"},"_deposit":{"created_by":20,"id":"21797","owners":[20],"pid":{"revision_id":0,"type":"depid","value":"21797"},"status":"published"},"_oai":{"id":"oai:doshisha.repo.nii.ac.jp:00021797","sets":["4251:8393:8394:8395:8406","8:3372:3812:3823"]},"author_link":["18584","2484","15621"],"control_number":"21797","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":"2012-07-31","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"2","bibliographicPageEnd":"103","bibliographicPageStart":"99","bibliographicVolumeNumber":"53","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つとして有名な最大流問題に注目する.最大流問題とは,ネットワークにおいて2つの制約,容量制約と流量保存則のもとでフローの値が最大となるフローを見つける問題である.多くの組み合わせ最適化問題は線形計画問題(LP問題)として定式化され,最大流問題についてもLPへの定式化の方法は知られている.一方で,組み合わせ最適化問題において有名な定理,最大フロー・最小カットセット定理はネットワークにおけるフローとカットセットの双対性を表したものだと知られている.我々の研究の目的は,フローとカットセットの双対性をLP問題を通して明らかにすることである.本論文では知られている定式化とは違う新しい最大流問題の定式化を行った.実験結果によると,新しい定式化の双対問題は解として0-1ベクトルが現れ,これは最小カットセットを与えていた.この結果よりこの定式化は我々の意図するものだといえる.しかし,LP問題の双対問題を作ったのにもかかわらず,0-1ベクトルが解として現れた理由についてはまだ分かっておらず,これを今後の課題とする.","subitem_description_language":"ja","subitem_description_type":"Abstract"},{"subitem_description":"In the present paper, we focus on the maximum flow problem which is one of the well-known optimization problems on flow-networks. The maximum flow problem is the problem for finding the flow such that the flow value is maximal among the flows subject to the capacity restriction and the flow conservation laws. Many of the combinatorial optimization problems can be formulated as linear programming (LP) problems, and it is known that the maximum flow problem can be formulated as an LP problem. On the other hand, the max-flow min-cutset theorem which is one of the famous results in combinatorial optimization, suggests the duality between flows and cutsets in networks. The purpose of our study is to clarify the duality between flows and cutsets in the maximum flow problem through the LP problem. In the present paper, we give a new formulation of the maximum flow problem as an LP problem which is slightly different from the one in the references. Computational experiments show that the dual of the LP problem computes a binary vector as the optimal solution, which presents the min-cutset. This implies that our formulation in the present paper is adequate for our purpose. However, we cannot make clear the reason why the optimal solution of the dual problem of the maximum flow problem becomes the binary vector, though the dual problem is an LP problem. This remains as a future subject of study.","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.0000012832","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":"2012-08-28"}],"displaytype":"detail","filename":"023053020007.pdf","filesize":[{"value":"3.2 MB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"023053020007.pdf","url":"https://doshisha.repo.nii.ac.jp/record/21797/files/023053020007.pdf"},"version_id":"66c00a8c-05d6-47f3-b67b-247eaa005353"}]},"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":"maximum flow problem","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"linear programming problem","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"dual problem","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"max-flow min-cutset theorem","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":"The maximum flow problem and its dual","subitem_title_language":"en"}]},"item_type_id":"1","owner":"20","path":["3823","8406"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2012-08-28"},"publish_date":"2012-08-28","publish_status":"0","recid":"21797","relation_version_is_last":true,"title":["最大流問題とその双対問題"],"weko_creator_id":"20","weko_shared_id":-1},"updated":"2023-12-05T06:19:53.600479+00:00"}