Keyword: 線形計画法
概要
本サンプルは線形計画法を行うC#によるサンプルプログラムです。 本サンプルは以下に示される制約条件を満たす目的関数を最小化する解を求めて出力します。
※本サンプルはnAG Library for .NETに含まれる関数 e04mf() のExampleコードです。本サンプル及び関数の詳細情報は e04mf のマニュアルページをご参照ください。
ご相談やお問い合わせはこちらまで
入力データ
（本関数の詳細はe04mf のマニュアルページを参照）1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| このデータをダウンロード |
e04mf Example Program Data 7 7 :Values of N and NCLIN -0.02 -0.20 -0.20 -0.20 -0.20 0.04 0.04 :End of CVEC 1.00 1.00 1.00 1.00 1.00 1.00 1.00 0.15 0.04 0.02 0.04 0.02 0.01 0.03 0.03 0.05 0.08 0.02 0.06 0.01 0.00 0.02 0.04 0.01 0.02 0.02 0.00 0.00 0.02 0.03 0.00 0.00 0.01 0.00 0.00 0.70 0.75 0.80 0.75 0.80 0.97 0.00 0.02 0.06 0.08 0.12 0.02 0.01 0.97 :End of matrix A -0.01 -0.10 -0.01 -0.04 -0.10 -0.01 -0.01 -0.13 -1.0E+25 -1.0E+25 -1.0E+25 -1.0E+25 -9.92E-02 -3.0E-03 :End of BL 0.01 0.15 0.03 0.02 0.05 1.0E+25 1.0E+25 -0.13 -4.9E-03 -6.4E-03 -3.7E-03 -1.2E-03 1.0E+25 2.0E-03 :End of BU -0.01 -0.03 0.00 -0.01 -0.10 0.02 0.01 :End of X
- １行目はタイトル行で読み飛ばされます。
- ２行目は変数の数(n)と制約の数(nclin)を指定しています。
- ３行目は目的関数の係数(cvec)を指定しています。
- ４～１０行目は線形制約行列Aを指定しています。
- １１行目は変数の下限(bl(1,..7))を指定しています。
- １２行目は線形制約の下限(bl(8,..,14))を指定しています。
- １３行目は変数の上限(bu(1,..,7))を指定しています。
- １４行目は線形制約の上限(bu(8,..,14))を指定しています。
- １５行目は変数xの実行不可能な初期値を指定しています。
出力結果
（本関数の詳細はe04mf のマニュアルページを参照）1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
| この出力例をダウンロード |
e04mf Example Program Results
Calls to E04MHF
---------------
List
Print level = 10
*** E04MFF
Parameters
----------
Problem type........... LP
Linear constraints..... 7 Feasibility tolerance.. 1.05E-08
Variables.............. 7 Optimality tolerance... 1.05E-08
Infinite bound size.... 1.00E+20 COLD start.............
Infinite step size..... 1.00E+20 EPS (machine precision) 1.11E-16
Check frequency........ 50 Expand frequency....... 5
Minimum sum of infeas.. NO Crash tolerance........ 1.00E-02
Print level............ 10 Iteration limit........ 70
Monitoring file........ -1
Workspace provided is IWORK( 17), WORK( 182).
To solve problem we need IWORK( 17), WORK( 182).
Itn Step Ninf Sinf/Objective Norm Gz
0 0.0E+00 3 1.038000E-01 0.0E+00
1 4.1E-02 1 3.000000E-02 0.0E+00
2 4.2E-02 0 3.500000E-02 0.0E+00
3 1.9E-01 0 3.090243E-02 0.0E+00
4 1.5E-01 0 2.989710E-02 0.0E+00
5 3.7E-01 0 2.725725E-02 0.0E+00
6 6.5E-01 0 2.403774E-02 0.0E+00
7 4.6E+00 0 2.359648E-02 0.0E+00
Varbl State Value Lower Bound Upper Bound Lagr Mult Slack
V 1 LL -1.000000E-02 -1.000000E-02 1.000000E-02 0.3301 .
V 2 LL -0.100000 -0.100000 0.150000 1.4384E-02 .
V 3 UL 3.000000E-02 -1.000000E-02 3.000000E-02 -9.0997E-02 .
V 4 UL 2.000000E-02 -4.000000E-02 2.000000E-02 -7.6612E-02 .
V 5 FR -6.748534E-02 -0.100000 5.000000E-02 . 3.2515E-02
V 6 FR -2.280130E-03 -1.000000E-02 None . 7.7199E-03
V 7 FR -2.345277E-04 -1.000000E-02 None . 9.7655E-03
L Con State Value Lower Bound Upper Bound Lagr Mult Slack
L 1 EQ -0.130000 -0.130000 -0.130000 -1.431 -2.7756E-17
L 2 FR -5.479544E-03 None -4.900000E-03 . 5.7954E-04
L 3 FR -6.571922E-03 None -6.400000E-03 . 1.7192E-04
L 4 FR -4.849707E-03 None -3.700000E-03 . 1.1497E-03
L 5 FR -3.874853E-03 None -1.200000E-03 . 2.6749E-03
L 6 LL -9.920000E-02 -9.920000E-02 None 1.501 -4.1633E-17
L 7 LL -3.000000E-03 -3.000000E-03 2.000000E-03 1.517 5.2042E-18
Exit E04MFF - Optimal LP solution.
Final LP objective value = 0.2359648E-01
Exit from LP problem after 7 iterations.
** e04mf returned with ifail = 0
Varbl Istate Value Lagr Mult
V 1 1 -0.01 0.3301
V 2 1 -0.1 0.01438
V 3 2 0.03 -0.091
V 4 2 0.02 -0.07661
V 5 0 -0.0674853 0
V 6 0 -0.00228013 0
V 7 0 -0.000234528 0
L Con Istate Value Lagr Mult
L 1 3 -0.13 -1.431
L 2 0 -0.00547954 0
L 3 0 -0.00657192 0
L 4 0 -0.00484971 0
L 5 0 -0.00387485 0
L 6 1 -0.0992 1.501
L 7 1 -0.003 1.517
Final objective value = 0.02359648
Exit from problem after 7 iterations.
- １５～３０行目に以下に示すプログラムのオプション引数が出力されています。
Problem type 最小化される目的関数の種類。"LP"は線形計画問題を意味します。 Linear constraints 線形制約の数。 Feasibility tolerance 実行可能解での許容可能な制約違反の最大値。 Variables 変数の数。 Optimality tolerance 最適とみなされる解に関して境界や一般制約に正しい符号がついているかどうか判断する際の許容値。 Infinite bound size 無限の境界値。この値以上の上限は+∞と見なされます。またこの値を負に反転させた値以下の下限は−∞と見なされます。 COLD start コールドスタート。初期のワーキングセットがどのように選ばれるかを示しています。変数や制約の値に基づいて初期のワーキングセットが選ばれていることを意味します。 Infinite step size 無限解へのステップと見なされる変数の変化の大きさ。 EPS (machine precision) マシンの精度。 Check frequency xの値がワーキングセットにある制約を満たしているか確認するための数値テストを行う反復の頻度。 Expand frequency 強制的に処理を進める反復の頻度。 Minimum sum of infeas 最小の実行不可能和。 Crash tolerance 初期のワーキングセットに含まれる不等式制約が下限／上限のこの範囲内にあることを示しています。 Print level 結果出力のレベル。"10"は最終解と各反復の結果を出力することを意味します。 Iteration limit 反復数の限界値。 Monitoring file モニタリング情報の生成を制御します。"-1" はモニタリング情報が生成されないことを意味します Workspace provided is 用意されているワークスペース。 To solve problem we need 問題を解くのに必要なワークスペース。 - ３３～４１行目には以下が出力されています。
Itn 反復回数。 Step 探索方向に進んだステップ幅。 Ninf 違反した制約の数。 Sinf/Objective 目的関数の値。 Norm Gz 縮小勾配のユークリッド・ノルム。 - ４４～５２行目には以下が出力されています。
Varbl 変数を示す "V"、インデックス。 State 変数の状態。"LL" は下限であることを意味し、"UL" は上限であることを意味し、"FR" は下限も上限もワーキングセットにはないことを意味します。 Value 最後の反復での変数の値。 Lower Bound 変数の下限。 Upper Bound 変数の上限。 Lagr Mult 関連する境界のラグランジュ乗数。 Slack スラック（変数の値と上限／下限の近いほうとの差） - ５５～６３行目には以下が出力されています。
L Con 線形制約を示す "L"、インデックス。 State 制約の状態。"EQ" は固定制約を意味し、"LL" は下限であることを意味し、"FR" は下限も上限もワーキングセットにはないことを意味します。 Value 最後の反復での制約の値。 Lower Bound 制約の下限。 Upper Bound 制約の上限。 Lagr Mult 関連する境界のラグランジュ乗数。 Slack スラック（制約の値と上限／下限の近いほうとの差）。 - ６７行目にLPの最終的な目的関数値が出力されています。
- ６９行目に７回の反復を行ったことが示されています。
- ７１行目にエラーを検知せずに本関数 e04mf を終了したことを示しています。
- ７３～８１行目には以下が出力されています。
Varbl 変数を示す "V"、インデックス。 IState 変数の状態。"0" はFeasibility toleranceの範囲内にあるがもワーキングセットにはないことを意味します。"1" は不等式制約の下限がワーキングセットにあることを意味し、"2" は不等式制約の上限がワーキングセットにあることを意味します。 Value 最後の反復での変数の値。 Lagr Mult 関連する境界のラグランジュ乗数。 - ８４～９２行目には以下が出力されています。
L Con 線形制約を示す "L"、インデックス。 IState 線形制約の状態。"0" はFeasibility toleranceの範囲内にあるがワーキングセットにはないことを意味します。"1" は不等式制約の下限がワーキングセットにあることを意味し、"2" は不等式制約の上限がワーキングセットにあることを意味します。"3" は等しい値がワーキングセットにあることを意味します。 Value 最後の反復での制約の値。 Lagr Mult 関連する境界のラグランジュ乗数。 - ９５行目にLPの最終的な目的関数値が出力されています。
- ９８行目に７回の反復を行って終了したことが示されています。
ソースコード
（本関数の詳細はe04mf のマニュアルページを参照）
※本サンプルソースコードは .NET環境用の科学技術・統計計算ライブラリである「nAG Library for .NET」の関数を呼び出します。
サンプルのコンパイル及び実行方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
| このソースコードをダウンロード |
// e04mf Example Program Text
// C# version, nAG Copyright 2008
using System;
using NagLibrary;
using System.IO;
namespace NagDotNetExamples
{
public class E04MFE
{
static bool defaultdata = true;
static string datafile = "";
// as a command line argument. It defaults to the named file specified below otherwise.
//
static void Main(String[] args)
{
if (args.Length == 1)
{
defaultdata = false;
datafile = args[0];
}
StartExample();
}
public static void StartExample()
{
try
{
DataReader sr = null;
if(defaultdata)
{ sr = new DataReader("exampledata/e04mfe.d");
}
else
{
sr = new DataReader(datafile);
}
double obj = 0.0;
int i, ifail, iter, j, n, nclin;
Console.WriteLine("e04mf Example Program Results");
// Skip heading in data file
sr.Reset();
sr.Reset();
n = int.Parse(sr.Next());
nclin = int.Parse(sr.Next());
double[,] a = new double[nclin, n];
double[] ax = new double[nclin];
double[] bl = new double[n + nclin];
double[] bu = new double[n + nclin];
double[] clamda = new double[n + nclin];
double[] cvec = new double[n];
double[] x = new double[n];
int[] istate = new int[n + nclin];
//
// Read cvec, a, bl, bu and x from data file
//
sr.Reset();
for (i = 1; i <= n; i++)
{
cvec[i - 1] = double.Parse(sr.Next());
}
sr.Reset();
for (i = 1; i <= nclin; i++)
{
for (j = 1; j <= n; j++)
{
a[i - 1, j - 1] = double.Parse(sr.Next());
}
}
sr.Reset();
for (i = 1; i <= n + nclin; i++)
{
bl[i - 1] = double.Parse(sr.Next());
}
sr.Reset();
for (i = 1; i <= n + nclin; i++)
{
bu[i - 1] = double.Parse(sr.Next());
}
sr.Reset();
for (i = 1; i <= n; i++)
{
x[i - 1] = double.Parse(sr.Next());
}
//
// Initialise E04.e04mf and check for error exits
//
//
E04.e04mfOptions options = new E04.e04mfOptions();
//
// Solve the problem
//
options.Set("List");
options.Set("Print level = 10");
//
E04.e04mf(n, nclin, a, bl, bu, cvec, istate, x, out iter, out obj, ax, clamda, options,
out ifail);
//
Console.WriteLine("");
if (ifail == 6)
{
Console.WriteLine(" ** An input parameter is invalid");
}
else if (ifail >= 0)
{
Console.WriteLine(" ** e04mf returned with ifail = {0, 3}", ifail);
Console.WriteLine("");
Console.WriteLine(" Varbl Istate Value Lagr Mult");
Console.WriteLine("");
for (i = 1; i <= n; i++)
{
Console.WriteLine(" V {0,3} {1,3} {2,14:g6} {3,12:g4}", i, istate[i - 1], x[i - 1], clamda[i - 1]);
}
if (nclin > 0)
{
Console.WriteLine("");
Console.WriteLine("");
Console.WriteLine(" L Con Istate Value Lagr Mult");
Console.WriteLine("");
for (i = n + 1; i <= n + nclin; i++)
{
j = i - n;
Console.WriteLine(" L {0,3} {1,3} {2,14:g6} {3,12:g4}", j, istate[i - 1], ax[j - 1], clamda[i - 1]);
}
}
Console.WriteLine("");
Console.WriteLine("");
Console.WriteLine(" Final objective value = {0,15:g7}", obj);
Console.WriteLine("");
Console.WriteLine("");
Console.WriteLine(" Exit from problem after {0,6} iterations.", iter);
}
else
{
Console.WriteLine(" ** e04mf returned with ifail = {0, 3}", ifail);
}
//
}
catch (Exception e)
{
Console.WriteLine(e.Message);
Console.WriteLine( "Exception Raised");
}
}
}
}