線形計画とは何？わかりやすく解説 Weblio辞書

OR事典

索引トップ用語の索引ランキングカテゴリー

線形計画

読み方：せんけいけいかく
【英】：linear programming

概要

最適化問題(数理計画問題)

$\mbox{max.} \,$	$f(x) \ ( \,$ あるいは, $\min. \ f(x)) \,$
$\mbox{s.t.} \,$	$x = (x_1,x_2,\ldots,x_n) \in F, \,$

において, 目的関数 $f \,$ が線形であり, かつ, 実行可能集合 $F \,$ が線形等式と線形不等式を用いて表現されている問題.この問題への定式化, および, 解法を含めて線形計画と呼ぶ.

詳説

　線形計画（linear programming）（線形計画法, 線形計画問題）は, 複数の等式あるいは不等式で与えられる線形制約のもとで, 目的関数（objective function）と呼ばれる線形関数を最大化（または最小化）する問題である. 線形計画問題は通常以下の形式により表現される.

$\mbox{(P)} \quad \begin{array}{lll} & \mbox{max.} & {\displaystyle \sum_{j=1}^{n}c_j x_j} \\ & \mbox{s. t.} & {\displaystyle \sum_{j=1}^{n}a_{ij} x_j} \leq b_i \ (i=1,2,\ldots,m), x_1,x_2,\ldots ,x_n \geq 0. \end{array}$

ここで, $c_j (j=1,2,\ldots,n), \, b_i (i=1,2,\ldots,m),\,a_{ij} (i=1,2,\ldots,m, \ j=1,2,\ldots,n)$ は実数, $\boldsymbol{x}=(x_1,x_2,\ldots, x_m)$ は $n\,$ 個の変数からなる $n\,$ 次元ベクトルである. すべての線形計画問題は, 簡単な変換により, この形式に帰着される. 問題（P）の制約条件を満たす $\boldsymbol{x}$ を実行可能解（feasible solution）と呼び, 実行可能解のなかで目的関数を最大にするものを最適解と呼ぶ.

　実社会における多くの問題は線形計画問題として定式化できる. 線形計画の応用は, 初期の頃は, 軍事, 経済学やゲーム理論が中心であったが, 次第にその重点が産業の分野へと移行された [2, 3]. 1947年にダンツィク（G. B. Dantzig）[2] によって提案された単体法（simplex method）は, コンピュータの急速な発展と大規模な線形方程式を処理する技術の向上とあいまって, 線形計画問題に対する極めて実用的な解法となっている. しかし, 単体法は Klee-Minty [4] により, 問題の入力サイズ（変数の個数と制約の本数）に関する多項式時間解法ではないことが指摘された. カチヤン（L. G. Khachian）は楕円体法を提案し, 最初の多項式時間解法を与えた. カーマーカー法およびその後開発された内点法は, 超大規模な線形計画問題に対し, 理論および実用の両面において, 単体法より優れた解法として認められている.

　以下では, 線形計画の理論で重要な役割を果たす双対問題（dual problem）, 双対定理（duality theorem）および相補性定理（complementarity slackness theorem）について述べる.

　各々の線形計画問題（P）には, 双対問題と呼ばれる以下の線形計画問題（D）を対応させることができる:

$\mbox{(D)} \quad \begin{array}{lll} & \mbox{min.} & {\displaystyle \sum_{i=1}^{m}b_i y_i} \\ & \mbox{s. t.} & {\displaystyle \sum_{i=1}^{m}a_{ij}y_i} \geq c_j \; (j=1,2,\ldots,n), y_1,y_2,\ldots,y_m \geq 0. \end{array}$

ここで, $c_j \, (j=1,2,\ldots,n), \, b_i \, (i=1,2,\ldots,m),\, a_{ij} \, (i=1,2,\ldots,m, \ j=1,2,\ldots,n)$ は元の問題(P)で与えられたデータと同一である. 元の問題（P）は主問題, 問題（D）は主問題（P）に対する双対問題と呼ばれる. 双対問題の双対問題が主問題になることは, 問題（D）を問題（P）の形式に書き直すことにより容易に示せる. 主問題と双対問題の実行可能解について, 次のようなことが言える.

主問題の実行可能解 $\boldsymbol{x}$ と双対問題の実行可能解 $\boldsymbol{y}$ に対し, $\textstyle \sum_{j=1}^{n}c_jx_j\leq \sum_{i=1}^{m}b_i y_i$ が成り立つ.

主問題の実行可能解 $\boldsymbol{x}$ と双対問題の実行可能解 $\boldsymbol{y}$ に対し, それらの目的関数値が一致するならば, $\boldsymbol{x}$ と $\boldsymbol{y}$ はそれぞれの問題の最適解である.

さらに, 以下の双対定理と相補性定理が示すように, 主問題と双対問題のいずれか一方の最適解は, 他方の問題の最適解に関する情報を含む.

双対定理: 主問題か双対問題のいずれか一方が最適解をもつならば, 他方もまた最適解をもち, それらの目的関数値は一致する. また, いずれか一方の問題の実行可能解に対する目的関数値が有界でなければ, 他方の問題は実行可能解をもたない.

相補性定理: 主問題の実行可能解 $\boldsymbol{x}$ と双対問題の実行可能解 $\boldsymbol{y}$ がそれぞれの問題の最適解であるための必要十分条件は, 以下の2条件（i）,（ii）が成り立つことである.

$\begin{array}{lll} \mbox{(i)} & (c_j-\sum_{i=1}^{m}a_{ij}y_i)x_j=0,\ j=1,2,\ldots,n,\\ \\ \mbox{(ii)} & (\sum_{j=1}^{n}a_{ij}x_j-b_i)y_i =0,\ i=1,2,\ldots,m. \end{array}$

これらの最適性条件を次のように言い換えることができる. いずれか一方の問題の $k\,$ 番目の制約式が不等号で成り立つならば, 他方の問題において対応する変数の値はゼロになる. また, いずれか一方の問題の $k\,$ 番目の変数の値が正ならば, 他方の問題においてそれに対応する制約式は等号で成り立つ.

参考文献

[1] V. Chvátal, Linear Programming, W. H. Freeman and Company, 1983, 阪田省二郎, 藤野和建　訳, 『線形計画法』上, 下, 啓学出版.

[2] G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963.

[3] S. I. Gass, Linear Programming and Extensions, MaGram-Hill, 1975.

[4] V. Klee and G. J. Minty "How good is the simplex algorithm?" in Inequalities-III, O. Shisha, eds., Academic Press, 159-175, 1989.

「OR事典」の他の用語

線形計画：

相補性定理等質自己双対錐組合せ最適化問題線形計画自己整合障壁関数許容解許容集合

Weblio日本語例文用例辞書

索引トップ用語の索引ランキング

「線形計画」の例文・使い方・用例・文例

線形計画法という,最適化手法

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。

>> 「線形計画」を含む用語の索引
線形計画のページへのリンク

11	ケセラセラ
12	爪先立って
13	季語一覧
14	警動
15	インスパイア
16	互礼会
17	ご愛顧
18	ツイ廃
19	つまさきだち
20	邁進

21	定義
22	尽力
23	凡事徹底
24	罹患
25	真野響子
26	巳年
27	爪立ち
28	遅ればせながら
29	つま先
30	権禰宜


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

線形計画とは？わかりやすく解説

線形計画

概要

詳説

「線形計画」の例文・使い方・用例・文例

「線形計画」の関連用語

線形計画とは？ わかりやすく解説

線形計画

概要

詳説

「線形計画」の例文・使い方・用例・文例

「線形計画」の関連用語

線形計画とは？わかりやすく解説