線形計画法

ホーム > 製品 > nAG数値計算ライブラリ > サンプルソースコード集 > 線形計画法 (C言語/C++)

Keyword: 線形計画法

概要

本サンプルは線形計画法を行うC言語によるサンプルプログラムです。本サンプルは以下に示される制約条件を満たす目的関数を最小化する解を求めて出力します。

線形計画法のデータ　

※本サンプルはnAG Cライブラリに含まれる関数 nag_opt_lp() のExampleコードです。本サンプル及び関数の詳細情報は nag_opt_lp のマニュアルページをご参照ください。
ご相談やお問い合わせはこちらまで

オプション・パラメータ

（本関数の詳細はnag_opt_lp のマニュアルページを参照）

このオプション・パラメータをダウンロード

nag_opt_lp (e04mfc) Example Program Optional Parameters

Following options for e04mfc are read by e04xyc.

begin e04mfc

 print_level = Nag_Soln /* Print solution only */
 ftol = 1e-10           /* Set feasiblity tolerance */

end

１行目はタイトル行で読み飛ばされます。
５行目はパラメータの開始を示しています。
７～８行目にe04xycによって読み込まれる、e04mfcに渡すオプショナル引数を指定しています。

print_level 結果出力のレベル。"Nag_Soln"は最終解を出力することを意味します。

ftol 実行可能解での許容可能な制約違反の最大値。
１０行目はパラメータの終わりを示しています。

出力結果

（本関数の詳細はnag_opt_lp のマニュアルページを参照）

この出力例をダウンロード

nag_opt_lp (e04mfc) Example Program Results

Parameters to e04mfc
--------------------

Linear constraints............   5    Number of variables...........   3

prob....................    Nag_LP    start...................  Nag_Cold
ftol....................  1.05e-08    reset_ftol..............         5
fcheck..................        50    crash_tol...............  1.00e-02
inf_bound...............  1.00e+25    inf_step................  1.00e+25
max_iter................        50    machine precision.......  1.11e-16
optim_tol...............  1.72e-13    min_infeas.............. Nag_FALSE
print_level......... Nag_Soln_Iter
outfile.................    stdout

Memory allocation:
state...................       Nag
ax......................       Nag    lambda..................       Nag

Results from e04mfc:
-------------------

  Itn Jdel  Jadd   Step    Ninf  Sinf/Obj    Bnd  Lin  Nart  Nrz  Norm Gz

   0   0     0    0.0e+00   1   1.9369e+02    0    1    2     0   1.96e+01
   1   2 A   6 L  5.0e-01   0   7.2049e-01    0    2    1     0   4.00e-02
   2   6 L   8 L  1.1e+01   0  -2.2109e+02    0    2    1     0   4.98e-01
   3   1 A   7 L  5.4e+02   0  -3.5500e+02    0    3    0     0   0.00e+00

Final solution:

  Varbl State    Value      Lower Bound  Upper Bound    Lagr Mult    Residual

 V   1    FR   7.50000e+01  -7.5000e+01   None       0.000e+00   1.500e+02
 V   2    FR  -2.50000e+02  -1.0000e+03   None       0.000e+00   7.500e+02
 V   3    FR  -1.00000e+01  -2.5000e+01   None       0.000e+00   1.500e+01

   LCon  State    Value     Lower Bound  Upper Bound    Lagr Mult    Residual

 L   1    EQ  -4.21428e-13   0.0000e+00   0.0000e+00   -1.300e-01  -4.214e-13
 L   2    FR  -4.20000e+02  -6.0000e+02   None       0.000e+00   1.800e+02
 L   3    FR   1.50000e+03   0.0000e+00   None       0.000e+00   1.500e+03
 L   4    LL  -5.00000e+02  -5.0000e+02   None       2.500e-01   5.684e-14
 L   5    LL  -1.00000e+03  -1.0000e+03   None       2.300e-01   1.137e-13

Exit after 3 iterations.

Optimal LP solution found.

Final LP objective value =  -3.5500000e+02

Re-solve problem with output of iteration results suppressed and ftol = 1.0e-10.

Optional parameter setting for e04mfc.
--------------------------------------

Option file: e04mfce.opt

print_level set to Nag_Soln
ftol set to 1.00e-10

Parameters to e04mfc
--------------------

Linear constraints............   5    Number of variables...........   3

prob....................    Nag_LP    start...................  Nag_Cold
ftol....................  1.00e-10    reset_ftol..............         5
fcheck..................        50    crash_tol...............  1.00e-02
inf_bound...............  1.00e+25    inf_step................  1.00e+25
max_iter................        50    machine precision.......  1.11e-16
optim_tol...............  1.72e-13    min_infeas.............. Nag_FALSE
print_level.........      Nag_Soln
outfile.................    stdout

Memory allocation:
state...................       Nag
ax......................       Nag    lambda..................       Nag

Final solution:

  Varbl State    Value      Lower Bound  Upper Bound    Lagr Mult    Residual

 V   1    FR   7.50000e+01  -7.5000e+01   None       0.000e+00   1.500e+02
 V   2    FR  -2.50000e+02  -1.0000e+03   None       0.000e+00   7.500e+02
 V   3    FR  -1.00000e+01  -2.5000e+01   None       0.000e+00   1.500e+01

   LCon  State    Value     Lower Bound  Upper Bound    Lagr Mult    Residual

 L   1    EQ   3.59843e-13   0.0000e+00   0.0000e+00   -1.300e-01   3.598e-13
 L   2    FR  -4.20000e+02  -6.0000e+02   None       0.000e+00   1.800e+02
 L   3    FR   1.50000e+03   0.0000e+00   None       0.000e+00   1.500e+03
 L   4    LL  -5.00000e+02  -5.0000e+02   None       2.500e-01   0.000e+00
 L   5    LL  -1.00000e+03  -1.0000e+03   None       2.300e-01   1.137e-13

Exit after 2 iterations.

Optimal LP solution found.

Final LP objective value =  -3.5500000e+02

６行目に線形制約の数、変数の数が出力されています。

８～１５行目に以下に示すプログラムのオプション引数が出力されています。

prob	最小化される目的関数の種類。"Nag_LP"は線形計画問題であることを意味します。
start	初期のワーキングセットがどのように選ばれるかを示しています。"Nag_Cold"は変数や制約の値に基づいて初期のワーキングセットが選ばれていることを意味します。
ftol	実行可能解での許容可能な制約違反の最大値。
reset_ftol	問題を解くためにこの反復数を超えた反復が必要な場合に、新たに反復が開始されます。
fcheck	この反復回数の時に現在の解がワーキングセットにある制約を満たしているか確認されます。
crash_tol	初期のワーキングセットに含まれる不等式制約が下限／上限のこの範囲内にあることを示しています。
inf_bound	無限の境界。この値以上の上限は+∞と見なされます。またこの値を負に反転させた値以下の下限は−∞と見なされます。
inf_step	無限解へのステップと見なされる変数の変化の大きさ。
max_iter	最適化フェーズの最大反復数。
machine precision	マシンの精度。
optim_tol	境界値や制約に正しい符号がついているかを判断するのに使用される許容値。
min_infeas	制約に対して実行可能解がない場合、実行不可能性を最小化すべきかを指定するフラグ。 "Nag_FALSE" を指定した場合、問題が実行不可能とわかり次第ルーチンは終了します。
print_level	結果出力のレベル。"Nag_Soln_Iter"は最終解と各反復の結果を出力することを意味します。
outfile	結果が出力されるファイル名。

１７～１９行目には、オプション引数state、ax、lambdaに必要なメモリがnAGライブラリの関数によって自動的に割り当てられたことを示しています。

２４～２９行目には以下が出力されています。

Itn	反復回数
Jdel	ワーキングセットから削除される制約のインデックス。"A"は人為的制約、"L"は下限を意味します。
Jadd	ワーキングセットに追加される制約のインデックス。"L"は下限を意味します。
Step	探索方向に進んだステップ幅
Ninf	違反した制約の数
Sinf/Obj	制約違反の大きさの加重和（xが実行可能でない場合）もしくは目的関数の値（xが実行可能な場合）
Bnd	現在のワーキングセットの簡易境界制約の数
Lin	現在のワーキングセットの一般線形制約の数
Nart	ワーキングセットの人為的制約の数
Nrz	目的関数が最小化される部分空間の次元
Norm Gz	縮小勾配のユークリッド・ノルム

３３～３７行目には以下が出力されています。

Varbl	変数を示す"V"、インデックス
State	変数の状態。FRは下限も上限もワーキングセットにはないことを意味します。
Value	最後の反復での変数の値
Lower Bound	下限
Upper Bound	上限
Lagr Mult	関連する境界制約のラグランジュ乗数
Residual	残差（変数の値と上限／下限の近いほうとの差）

３９～４５行目には以下が出力されています。

LCon	線形制約を示す"L"、インデックス
State	制約の状態。EQは固定制約を意味し、LLは下限であることを意味し、FRは下限も上限もワーキングセットにはないことを意味します。
Value	最後の反復での制約の値
Lower Bound	下限
Upper Bound	上限
Lagr Mult	関連する境界制約のラグランジュ乗数
Residual	残差（制約の値と上限／下限の近いほうとの差）

４７行目に３回の反復を行ったことが示されています。
４９行目にLPの最適解が見つかったことが示されています。
５１行目にLPの最終的な目的関数値が出力されています。
５３行目に反復の結果を出力せずに、ftolを1.0e-10にして再度LP問題を解くことが示されています。
５８行目にオプション・パラメータ用のファイルe04mfce.optが読み込まれていることが示されています。
６０行目にprint_levelに"nAG_Soln"が設定されていることが示されています。
６１行目にftol に1.0e-10が設定されていることが示されています。
６６行目に線形制約の数、変数の数が出力されています。
６８～７９行目にプログラムのオプション引数が出力されています。

８３～８７行目には以下が出力されています。

Varbl	変数を示す"V"、インデックス
State	変数の状態。FRは下限も上限もワーキングセットにはないことを意味します。
Value	最後の反復での変数の値
Lower Bound	下限
Upper Bound	上限
Lagr Mult	関連する境界制約のラグランジュ乗数
Residual	残差（変数の値と上限／下限の近いほうとの差）

８９～９５行目には以下が出力されています。

LCon	線形制約を示す"L"、インデックス
State	制約の状態。EQは固定制約を意味し、LLは下限であることを意味し、FRは下限も上限もワーキングセットにはないことを意味します。
Value	最後の反復での制約の値
Lower Bound	下限
Upper Bound	上限
Lagr Mult	関連する境界制約のラグランジュ乗数
Residual	残差（制約の値と上限／下限の近いほうとの差）

９７行目に２回の反復を行ったことが示されています。
９９行目にLPの最適解が見つかったことが示されています。
１０１行目にLPの最終的な目的関数値が出力されています。

ソースコード

（本関数の詳細はnag_opt_lp のマニュアルページを参照）

※本サンプルソースコードはnAG数値計算ライブラリ（Windows, Linux, MAC等に対応）の関数を呼び出します。
サンプルのコンパイル及び実行方法

このソースコードをダウンロード

/* nag_opt_lp (e04mfc) Example Program.
 *
 * CLL6I261D/CLL6I261DL Version.
 *
 * Copyright 2017 Numerical Algorithms Group.
 *
 * Mark 26.1, 2017.
 */

/* This sample linear program (LP) is a portfolio investment problem
 * (see Chapter 7, pp 258--262 of ``Numerical Linear Algebra and
 * Optimization'', by Gill, Murray and Wright, Addison Wesley, 1991).
 * The problem involves the rearrangement of a portfolio of three
 * stocks, Glitter, Risky and Trusty, so that the net worth of the
 * investor is maximized.
 * The problem is characterized by the following data:
 *                           Glitter     Risky        Trusty
 * 1990 Holdings                75       1000           25
 * 1990 Priceshare($)           20          2          100
 * 2099 Priceshare($)           18          3          102
 * 2099 Dividend                 5          0            2
 *
 * The variables x[0], x[1] and x[2] represent the change in each of
 * the three stocks.
 */

#include <nag.h>
#include <stdio.h>
#include <nag_stdlib.h>
#include <nag_string.h>
#include <nage04.h>

#define A(I, J) a[(I) *tda + J]

int main(void)
{
  const char *optionsfile = "e04mfce.opt";
  Integer exit_status = 0;
  Nag_Boolean print;
  Integer n, nbnd, nclin, tda;
  Nag_E04_Opt options;
  double *a = 0, bigbnd, *bl = 0, *bu = 0, *cvec = 0, objf, *x = 0;
  Nag_Comm comm;
  NagError fail;

  INIT_FAIL(fail);

  printf("nag_opt_lp (e04mfc) Example Program Results\n");
  /* Set the actual problem dimensions.
   * n      = the number of variables.
   * nclin  = the number of general linear constraints (may be 0).
   */
  n = 3;
  nclin = 5;
  nbnd = n + nclin;
  if (n >= 1 && nclin >= 0) {
    if (!(x = nAG_ALLOC(n, double)) ||
        !(cvec = nAG_ALLOC(n, double)) ||
        !(a = nAG_ALLOC(nclin * n, double)) ||
        !(bl = nAG_ALLOC(nbnd, double)) || !(bu = nAG_ALLOC(nbnd, double)))
    {
      printf("Allocation failure\n");
      exit_status = -1;
      goto END;
    }
    tda = n;
  }
  else {
    printf("Invalid n or nclin.\n");
    exit_status = 1;
    return exit_status;
  }

  /* Define the value used to denote ``infinite'' bounds. */
  bigbnd = 1e+25;

  /* Objective function:  maximize  5*X[0] + 2*X[2], or equivalently,
   * minimize -5*X[0] - 2*X[2].
   */
  cvec[0] = -5.0;
  cvec[1] = 0.0;
  cvec[2] = -2.0;

  /* a  = the general constraint matrix.
   * bl = the lower bounds on  x  and  A*x.
   * bu = the upper bounds on  x  and  A*x.
   * x  = the initial estimate of the solution.
   *
   * A nonnegative amount of stock must be present after rearrangement.
   * For Glitter:  x[0] + 75 >= 0.
   */
  bl[0] = -75.0;
  bu[0] = bigbnd;

  /* For Risky:    x[1] + 1000 >= 0.0 */
  bl[1] = -1000.0;
  bu[1] = bigbnd;

  /* For Trusty:   x[2] + 25 >= 0.0 */
  bl[2] = -25.0;
  bu[2] = bigbnd;

  /* The current value of the portfolio must be the same after
   * rearrangement, i.e.,
   *  20*(75+x[0]) + 2*(1000+x[1]) + 100*(25+x[2]) = 6000, or
   *  20*x[0] + 2*x[1] + 100*x[2] = 0.
   */
  A(0, 0) = 20.0;
  A(0, 1) = 2.0;
  A(0, 2) = 100.0;
  bl[n] = 0.0;
  bu[n] = 0.0;

  /* The value of the portfolio must increase by at least 5 per cent
   * at the end of the year, i.e.,
   * 18*(75+x[0]) + 3*(1000+x[1]) + 102*(25+x[2]) >= 6300, or
   * 18*x[0] + 3*x[1] + 102*x[2] >= -600.
   */
  A(1, 0) = 18.0;
  A(1, 1) = 3.0;
  A(1, 2) = 102.0;
  bl[n + 1] = -600.0;
  bu[n + 1] = bigbnd;

  /* There are three ``balanced portfolio'' constraints.  The value of
   * a stock must constitute at least a quarter of the total final
   * value of the portfolio.  After rearrangement, the value of the
   * portfolio after is  20*(75+x[0]) + 2*(1000+x[1]) + 100*(25+x[2]).
   *
   * If Glitter is to constitute at least a quarter of the final
   * portfolio, then  15*x[0] - 0.5*x[1] - 25*x[2] >= 0.
   */
  A(2, 0) = 15.0;
  A(2, 1) = -0.5;
  A(2, 2) = -25.0;
  bl[n + 2] = 0.0;
  bu[n + 2] = bigbnd;

  /* If Risky is to constitute at least a quarter of the final
   * portfolio, then  -5*x[0] + 1.5*x[1] - 25*x[2] >= -500.
   */
  A(3, 0) = -5.0;
  A(3, 1) = 1.5;
  A(3, 2) = -25.0;
  bl[n + 3] = -500.0;
  bu[n + 3] = bigbnd;

  /* If Trusty is to constitute at least a quarter of the final
   * portfolio, then  -5*x[0] - 0.5*x[1] + 75*x[2] >= -1000.
   */
  A(4, 0) = -5.0;
  A(4, 1) = -0.5;
  A(4, 2) = 75.0;
  bl[n + 4] = -1000.0;
  bu[n + 4] = bigbnd;

  /* Set the initial estimate of the solution.
   * This portfolio is infeasible.
   */
  x[0] = 10.0;
  x[1] = 20.0;
  x[2] = 100.0;

  /* Initialize options structure to null values. */
  /* nag_opt_init (e04xxc).
   * Initialization function for option setting
   */
  nag_opt_init(&options);
  options.inf_bound = bigbnd;

  /* Solve the problem. */
  /* nag_opt_lp (e04mfc), see above. */
  fflush(stdout);
  nag_opt_lp(n, nclin, a, tda, bl, bu, cvec,
             x, &objf, &options, &comm, &fail);
  if (fail.code != NE_NOERROR) {
    printf("Error from nag_opt_lp (e04mfc).\n%s\n", fail.message);
    exit_status = 1;
    goto END;
  }

  /* Re-solve the problem with some additonal options. */

  printf("Re-solve problem with output of iteration results");
  printf(" suppressed and ftol = 1.0e-10.\n");

  /* Read additional options from a file. */
  print = Nag_TRUE;
  /* nag_opt_read (e04xyc).
   * Read options from a text file
   */
  fflush(stdout);
  nag_opt_read("e04mfc", optionsfile, &options, print, "stdout", &fail);
  if (fail.code != NE_NOERROR) {
    printf("Error from nag_opt_read (e04xyc).\n%s\n", fail.message);
    exit_status = 1;
    goto END;
  }

  /* Reset starting point */
  x[0] = 0.0;
  x[1] = 0.0;
  x[2] = 0.0;

  /* Solve the problem again. */
  /* nag_opt_lp (e04mfc), see above. */
  nag_opt_lp(n, nclin, a, tda, bl, bu, cvec,
             x, &objf, &options, &comm, &fail);
  if (fail.code != NE_NOERROR) {
    printf("Error from nag_opt_lp (e04mfc).\n%s\n", fail.message);
    exit_status = 1;
    goto END;
  }

  /* Free memory allocated by nag_opt_lp (e04mfc) to pointers in options. */
  /* nag_opt_free (e04xzc).
   * Memory freeing function for use with option setting
   */
  nag_opt_free(&options, "all", &fail);
  if (fail.code != NE_NOERROR) {
    printf("Error from nag_opt_free (e04xzc).\n%s\n", fail.message);
    exit_status = 1;
    goto END;
  }

END:
  nAG_FREE(x);
  nAG_FREE(cvec);
  nAG_FREE(a);
  nAG_FREE(bl);
  nAG_FREE(bu);

  return exit_status;
}

print_level	結果出力のレベル。"Nag_Soln"は最終解を出力することを意味します。
ftol	実行可能解での許容可能な制約違反の最大値。

C言語によるサンプルソースコード : 使用関数名：nag_opt_lp (e04mfc)

概要

オプション・パラメータ

出力結果

ソースコード