最適化アルゴリズムExample集: 線形計画問題の内点法による解法
nAG数値計算ライブラリ > 最適化アルゴリズムExample集 > 線形計画問題の内点法による解法

線形計画法-LP(内点法)

このExampleでは、nAG Optimization Modeling Suite (NOMS)の機能を用いてLPモデルを編集する方法を示しています。最初に2変数のLP問題を定式化して内点法で解き、その後新しい変数と制約を追加して再度解いています。

変数追加前

目的関数(変数追加前):

タスク
Maximize \(2x_1 + 4.5x_2\)

決定変数(変数追加前):

変数 範囲
\(x_1\) \(0 \leq x_1 < \infty\)
\(x_2\) \(0 \leq x_2 \leq 100\)

制約条件(変数追加前):

制約
1 \(1.2x_1 + 3x_2 \leq 1500\)
2 \(6x_1 + 10x_2 \leq 6000\)
3 \(40x_1 + 80x_2 \leq 16000\)

変数追加後

目的関数(変数追加後):

タスク
Maximize \(2x_1 + 4.5x_2 + 7x_3\)

決定変数(変数追加後):

変数 範囲
\(x_1\) \(0 \leq x_1 < \infty\)
\(x_2\) \(0 \leq x_2 \leq 100\)
\(x_3\) \(0 \leq x_3 \leq 50\) (新しく追加された変数)

制約条件(変数追加後):

制約
1 \(1.2x_1 + 3x_2 + 5x_3 \leq 1500\)
2 \(6x_1 + 10x_2 + 12x_3 \leq 6000\)
3 \(40x_1 + 80x_2 + 120x_3 \leq 16000\)
4 \(x_2 + x_3 \leq 100\) (新しく追加された制約)

Exampleの実行コマンド:

python -m naginterfaces.library.examples.opt.handle_add_vars_ex

ソースコード表示コマンド:

python -c "import inspect; from naginterfaces.library.examples.opt import handle_add_vars_ex; print(''.join(inspect.getsourcelines(handle_add_vars_ex)[0]))"

出力結果例:

naginterfaces.library.opt.handle_add_vars Python Example Results
Solve the first LP
 E04MT, Interior point method for LP problems
 Status: converged, an optimal solution found
 Final primal objective value  8.500000E+02
 Final dual objective value    8.500000E+02
 Primal variables:
   idx   Lower bound       Value       Upper bound
     1   0.00000E+00    2.00000E+02         inf
     2   0.00000E+00    1.00000E+02    1.00000E+02
The new variable has been added, solve the handle again
 E04MT, Interior point method for LP problems
 Status: converged, an optimal solution found
 Final primal objective value  9.000000E+02
 Final dual objective value    9.000000E+02
 Primal variables:
   idx   Lower bound       Value       Upper bound
     1   0.00000E+00    5.00000E+01         inf
     2   0.00000E+00    1.00000E+02    1.00000E+02
     3   0.00000E+00    5.00000E+01    5.00000E+01
The new constraint has been added, solve the handle again
 E04MT, Interior point method for LP problems
 Status: converged, an optimal solution found
 Final primal objective value  8.750000E+02
 Final dual objective value    8.750000E+02
 Primal variables:
   idx   Lower bound       Value       Upper bound
     1   0.00000E+00    1.50000E+02         inf
     2   0.00000E+00    5.00000E+01    1.00000E+02
     3   0.00000E+00    5.00000E+01    5.00000E+01

マニュアル:

handle_solve_lp_ipmのマニュアル

ソース:

#!/usr/bin/env python3
"``naginterfaces.library.opt.handle_add_vars`` Python Example."

# nAG Copyright 2020.

from naginterfaces.base import utils
from naginterfaces.library import opt

def main():
    """
    Example for :func:`naginterfaces.library.opt.handle_add_vars`

    nAG Optimization Modelling suite:
    adding variables to an optimization model.

    This example program demonstrates how to edit an LP model using
    the nAG Optimization Modeling Suite (NOMS) functionality.

    >>> main()
    naginterfaces.library.opt.handle_add_vars Python Example Results
    <BLANKLINE>
    Solve the first LP
    <BLANKLINE>
     E04MT, Interior point method for LP problems
     Status: converged, an optimal solution found
     Final primal objective value  8.500000E+02
     Final dual objective value    8.500000E+02
    <BLANKLINE>
     Primal variables:
       idx   Lower bound       Value       Upper bound
         1   0.00000E+00    2.00000E+02         inf
         2   0.00000E+00    1.00000E+02    1.00000E+02
    <BLANKLINE>
    The new variable has been added, solve the handle again
    <BLANKLINE>
     E04MT, Interior point method for LP problems
     Status: converged, an optimal solution found
     Final primal objective value  9.000000E+02
     Final dual objective value    9.000000E+02
    <BLANKLINE>
     Primal variables:
       idx   Lower bound       Value       Upper bound
         1   0.00000E+00    5.00000E+01         inf
         2   0.00000E+00    1.00000E+02    1.00000E+02
         3   0.00000E+00    5.00000E+01    5.00000E+01
    <BLANKLINE>
    The new constraint has been added, solve the handle again
    <BLANKLINE>
     E04MT, Interior point method for LP problems
     Status: converged, an optimal solution found
     Final primal objective value  8.750000E+02
     Final dual objective value    8.750000E+02
    <BLANKLINE>
     Primal variables:
       idx   Lower bound       Value       Upper bound
         1   0.00000E+00    1.50000E+02         inf
         2   0.00000E+00    5.00000E+01    1.00000E+02
         3   0.00000E+00    5.00000E+01    5.00000E+01
    """

    print(
        'naginterfaces.library.opt.handle_add_vars Python Example Results'
    )
    print()
    print('Solve the first LP')
    print()

    infbnd = 1.0e20

    # Initialize the Optimization model handle with the number of variables
    handle = opt.handle_init(2)

    # Define a linear objective function
    opt.handle_set_linobj(handle, cvec=[2.0, 4.5])

    # Box constraints
    opt.handle_set_simplebounds(
        handle,
        bl=[0.0, 0.0],
        bu=[infbnd, 100])

    # Set the linear constraints
    opt.handle_set_linconstr(
        handle,
        bl=[-infbnd, -infbnd, -infbnd],
        bu=[1500.0, 6000.0, 16000.0],
        irowb=[1, 1, 2, 2, 3, 3],
        icolb=[1, 2, 1, 2, 1, 2],
        b=[1.2, 3.0, 6.0, 10.0, 40.0, 80.0]
    )

    # Set some alogorithmic options
    for option in [
            'Print Options = NO',
            'Print Level = 1',
            'Task = Max',
            'Print Solution = X',
    ]:
        opt.handle_opt_set(handle, option)

    # Use an explicit I/O manager for abbreviated iteration output:
    iom = utils.FileObjManager(locus_in_output=False)

    # Solve the problem
    opt.handle_solve_lp_ipm(handle, io_manager=iom)

    # add a variable
    opt.handle_add_vars(handle, nadd=1)

    # Box Constraint on the new variable
    opt.handle_set_bound(handle, comp='X', idx=3, bli=0.0, bui=50.0)

    # Add the linear objective component
    opt.handle_set_linobj_coeff(handle, idxci=3, ci=7.0)

    # Add linear constraints coefficients
    opt.handle_set_linconstr_coeff(handle, idlc=1, icolbj=3, bij=5.0)
    opt.handle_set_linconstr_coeff(handle, idlc=2, icolbj=3, bij=12.0)
    opt.handle_set_linconstr_coeff(handle, idlc=3, icolbj=3, bij=120.0)

    print()
    print('The new variable has been added, solve the handle again')
    print()

    # Solve the problem again
    opt.handle_solve_lp_ipm(handle, io_manager=iom)

    # Add a linear constraint
    opt.handle_set_linconstr(
        handle,
        bl=[-infbnd],
        bu=[100.0],
        irowb=[1, 1],
        icolb=[2, 3],
        b=[1.0, 1.0]
    )

    print()
    print('The new constraint has been added, solve the handle again')
    print()

    # Solve the problem again
    opt.handle_solve_lp_ipm(handle, io_manager=iom)

    # Destroy the handle:
    opt.handle_free(handle)

if __name__ == '__main__':
    import doctest
    import sys
    sys.exit(
        doctest.testmod(
            None, verbose=True, report=False,
            optionflags=doctest.ELLIPSIS | doctest.REPORT_NDIFF,
        ).failed
    )

関連情報
Privacy Policy  /  Trademarks