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()
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
)