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
マニュアル:
ソース:
#!/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()
= 1.0e20
infbnd
# Initialize the Optimization model handle with the number of variables
= opt.handle_init(2)
handle
# Define a linear objective function
=[2.0, 4.5])
opt.handle_set_linobj(handle, cvec
# Box constraints
opt.handle_set_simplebounds(
handle,=[0.0, 0.0],
bl=[infbnd, 100])
bu
# Set the linear constraints
opt.handle_set_linconstr(
handle,=[-infbnd, -infbnd, -infbnd],
bl=[1500.0, 6000.0, 16000.0],
bu=[1, 1, 2, 2, 3, 3],
irowb=[1, 2, 1, 2, 1, 2],
icolb=[1.2, 3.0, 6.0, 10.0, 40.0, 80.0]
b
)
# 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:
= utils.FileObjManager(locus_in_output=False)
iom
# Solve the problem
=iom)
opt.handle_solve_lp_ipm(handle, io_manager
# add a variable
=1)
opt.handle_add_vars(handle, nadd
# Box Constraint on the new variable
='X', idx=3, bli=0.0, bui=50.0)
opt.handle_set_bound(handle, comp
# Add the linear objective component
=3, ci=7.0)
opt.handle_set_linobj_coeff(handle, idxci
# Add linear constraints coefficients
=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)
opt.handle_set_linconstr_coeff(handle, idlc
print()
print('The new variable has been added, solve the handle again')
print()
# Solve the problem again
=iom)
opt.handle_solve_lp_ipm(handle, io_manager
# Add a linear constraint
opt.handle_set_linconstr(
handle,=[-infbnd],
bl=[100.0],
bu=[1, 1],
irowb=[2, 3],
icolb=[1.0, 1.0]
b
)
print()
print('The new constraint has been added, solve the handle again')
print()
# Solve the problem again
=iom)
opt.handle_solve_lp_ipm(handle, io_manager
# Destroy the handle:
opt.handle_free(handle)
if __name__ == '__main__':
import doctest
import sys
sys.exit(
doctest.testmod(None, verbose=True, report=False,
=doctest.ELLIPSIS | doctest.REPORT_NDIFF,
optionflags
).failed )