next up previous
Next: 標準形と基準形 Up: 原理 Previous: 原理

線形計画問題

線形計画問題とは, 与えられた線形な等式および不等式制約のもとで, 線形目的関数を最大化あるいは最小化する問題である。まず例を挙げる。

例 1   パソコンショップの店主であるAさんは, ある顧客から「PC/AT互換機のシス テムを組んで欲しい」という依頼を受けた。顧客の要望は,
メモリ100MB以上, ディスク 5GB 以上, 予算はディスクとメモリを合わせて 10万円以下, 予算の範囲でメモリもディスクも可能な限りたくさん載せたい,
というものであった。

話を簡単にするため, (非現実的な仮定だが)メモリおよびディスクの大きさは 任意の正の実数値を取るものとする。メモリの価格は1MBあたり100円, ディス クの価格は1GBあたり2,500円とする。また, 顧客の依頼したパソコンは, メ モリは最大800MBまで,ディスクは無限に増設できるものとする。Aさんの店で は, メモリは1MBあたり10円, ディスクは1GBあたり200円の利益があるものとする。 Aさんとしては, 顧客の予算を目一杯使って, なるべく多くの利益をあげたい。 さて, どのような意思決定をするのが良いだろうか?

メモリの大きさを $ x$ MB, ディスクの大きさを $ y$ GBとしよう。 すると, Aさんの利益(目的関数)は,

$\displaystyle 10 x + 200 y$ (1)

となる。よって, Aさんが解くべき問題は, 「 $ 10 x + 200 y$(目的関数)を最大化すること」となる。

仮にメモリの大きさ$ x$とディスクの大きさ$ y$を勝手に設定できるなら, Aさんはいくらでもお金を儲けられることになる。だが実際には いくつか制約条件がある。それは,

というものである。これらを書き直すと,

\begin{displaymath}\begin{array}{rcl} x & \geq& 0  x &\geq& 100  x &\leq& 80...
...eq & 0  y &\geq& 5  100 x+ 2500 y &\leq& 100000 \end{array}\end{displaymath} (2)

となる。

1は, 制約条件を満たす領域の形と目的関数のようすをあらわしたものである。 制約条件を満たす領域は図中の網のかかった台形の内部である。 目的関数は図中に引かれた傾き$ -1$の一点鎖線上で一定値を 取る。この直線が図中の右上に移動するほど目的関数の値 は大きくなる。この図から, 台形の右上の頂点の部分で 目的関数が最大値を取ることがわかる。

図 1: 制約条件を満たす領域と目的関数の挙動
% latex2html id marker 6304
\includegraphics{example-tex.eps}

1は, 結局

変数$ (x,y)$, 目的関数 $ 10 x + 200 y$および 制約条件(2)が与えられたとき, 与えられた制約条件のもとで目的関数を最大化するような $ x$, $ y$を求めよ
という問題であった。これを一般化したのが線形計画問題である。

線形計画問題(一般形) $ n$個の変数 $ x_1,\ldots,x_n$に対し, $ m$個の等式あるいは不等式の 制約条件

\begin{displaymath}\begin{array}{ccl} a_{11}x_1+\ldots+a_{1n}x_n &\geq &b_1  \...
...{l1}x_1+\ldots+a_{ln}x_n &\leq &b_l  \ldots\ldots \end{array}\end{displaymath} (3)

が与えられ, かついくつかの変数に符号に関する制約条件 $ x_{i_1} \geq 0, \ldots, x_{i_r} \geq 0$, $ x_{j_1} \leq 0, \ldots, x_{j_s} \leq 0$が課されているものとする。 このとき, 制約条件(3)を満たす範囲内で, 目的関数

$\displaystyle c_1 x_1 + \ldots + c_n x_n$ (4)

を最小化(あるいは最大化)せよ。

ここに, 最小化(最大化)とは, 目的関数を最小(最大)にする$ x_1$から$ x_n$の値と その最小値(最大値)を求めることを言う。

線形計画問題の例として, 工場において一定の原料やエネルギー消費量の制約 のもとで利益を最大化するための生産計画を立てる問題などが挙げられる。 実用的な線形計画問題では, 変数および制約条件の数は極めて大きくなる。

線形計画問題の解法としてよく知られているものに, シンプレックス法と内点法がある。 シンプレックス法は1947年にG. B. Dantzigによって提案された線形計画問題の解法である。 この方法は, 幾何学的には, 凸多面体の形をした制約領域の隣接する頂点をたどりながら 解を改善する方法である。シンプレックス法は, 提案されて以降40年ほどの間, 最も効率的な線形計画問題の解法とされてきた。 これに対し, 1984年にN. Karmarkar によって提案された内点法は, 理論的な収束特性がシンプレックス法より良いばかりでなく, 極めて大規模な問題に対しては実用上の計算効率もシンプレックス法に勝るため, 提案されて以来, 爆発的に研究が進んできた。 (ただし, 規模の小さい問題ではシンプレックス法の方が圧倒的に速い)。

本実験ではシンプレックス法と内点法の双方を取り扱う。

以下ではシンプレックス法と内点法の基本について説明してゆくのだが, 説明がかなり長いので, 読者の負担を減らすために, 読まなくても実験に支障がない部分には印がつけてある。 記号 $ \blacktriangleright$が欄の左端に記載されている ところの記号 $ \blacktriangleleft$が欄の右端に記載されて いるところあいだは読み飛ばして構わない。具体的には, ページ[*]からページ[*]までと ページ[*]からページ[*]の該当部分である。


next up previous
Next: 標準形と基準形 Up: 原理 Previous: 原理
Shigeru HANBA
平成15年11月16日