- ベストアンサー
変数数40万の0-1変数線形計画問題を解きたい
- みんなの回答 (1)
- 専門家の回答
質問者が選んだベストアンサー
どんな問題だかわからないが,試しにこんなのを書いてみた。 元ネタは https://qiita.com/samuelladoco/items/703bf78ea66e8369c455 の問題2です。 変数の数は全部で36万,目的関数および制約条件は1次関数になっています。 私の普段使っているPCだと問題作成に148秒,求解に46秒くらいかかっています。 # pulp_problem.py # coding: UTF-8 import pulp import time import numpy as np time_start = time.clock() I = np.arange(600) J = np.arange(600) c1 = np.random.randint(0,100,360000) c = c1.reshape((600,600)) problem = pulp.LpProblem("Problem-2", pulp.LpMinimize) x = {} for i in I: for j in J: x[i,j] = pulp.LpVariable("x({:},{:})".format(i,j), 0, 1, pulp.LpInteger) problem += pulp.lpSum(c[i][j] * x[i,j] for i in I for j in J), "TotalCost" for i in I: problem += sum(x[i,j] for j in J) <= 1, "Constraint_leq_{:}".format(i) for j in J: problem += sum(x[i,j] for i in I) == 1, "Constraint_eq_{:}".format(j) #print("問題の式") #print(problem) #print("--------") time_stop = time.clock() print("作成時間 = {:} (秒)".format(time_stop - time_start)) solver = pulp.solvers.PULP_CBC_CMD() time_start = time.clock() result_status = problem.solve(solver) time_stop = time.clock() print("計算結果") print("最適性 = {:}, 目的関数値 = {:}, 計算時間 = {:} (秒)" .format(pulp.LpStatus[result_status], pulp.value(problem.objective), time_stop - time_start)) #print("解 x[i,j]: ") #for i in I: # for j in J: # print("{:} = {:}, " # .format(x[i,j].name, x[i,j].value()), end="") # print("") #print("********")
関連するQ&A
- 線形計画法の解法について!
線形計画法の解き方が判らなくて困っています。 判らないこと 1.制約条件の式と計算値 2.目的関数の式と目的値 線形計画法は変数と制約条件と目的関数が与えられます。 制約条件を満足し、目的関数が最大(最小)となる変数を求めます。 線形計画法の例 変数 x y 制約条件 (A) 10x + 4y ≦ 360 (B) 4x + 5y ≦ 200 (C) 2x + 10y ≦ 300 (D) x ≧ 0 (E) y ≧ 0 目的関数 M = 7x+12y A,B,C,D,Eの条件を満足し目的関数(M)が最大となる変数x,yを求めます。
- ベストアンサー
- 数学・算数
- 線形計画問題
最近線形計画法について独学で勉強を始めたのですが いくつかの書籍を調べてもどうしても分からない点が あったのでこの場を利用させて頂きます。 頭を悩めていますのは制約条件が特殊なためです。 問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が 分母にきているのです。目的関数で分母に変数を 持つものは分数計画問題といるのを拝見した事が あるのですが上記のような例は探し方が悪いのか 見つける事ができていません。 実行可能領域は非有界ですが最小化問題のため 上記の例であると2変数なのでグラフにプロットする 事でおよそですが解は見つかりました。 しかし実際の問題は10変数以上の問題となっています ので解が求められません。 その後も実行可能領域を多面体で近似すれば良いのか 等の考察を繰り返しましたが問題が複雑になりお手上げ の状態です。 ちゃんとした解法があるのならお教え頂けるか書籍の 案内をして頂きたいです。宜しくお願いします。
- ベストアンサー
- 数学・算数
- 非線形計画法について
非線形計画法を現在勉強しています。 1. どういうときに線形でどういうときに非線形となるのか良く分かりません。 例えば、ある従属変数yを線形関数f=Σcx で表したいときにパラメータcの絶対値の和が定数bより小さくなるという制約のもとで、yとfの二乗誤差を最小化するパラメータcを求める問題を考えます。 この場合、制約条件はcについて線形ですが、最小化したいのは、yとfの二乗誤差なのでこの場合は非線形ということになるのでしょうか?それとも関数fはcに関して線形関数なので、線形計画法で解くことになるのでしょうか? 2. 以下のサイトで勉強しているのですが、このサイトにある楕円型の等高線はおそらく、従属変数yと目的関数fの誤差を表しているのだと思うのですが、なぜ「楕円」になるのですか?二乗誤差を考えるのならば、「円」になるのではと疑問で仕方ありません。 http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/nonlinear/nonlinear.htm#2.2 疑問が晴れずにもやもやしています。 回答もしくはアドバイス、よろしくお願いします。
- 締切済み
- 数学・算数
- MATLABで制約付き非線形連立方程式を解きたい。
MATLABで制約付き非線形連立方程式を解きたいです。 ただし、optimization toolboxなどのツールボックスはありません。 ツールボックスなしで、変数に上下限制約を課した非線形方程式を解く方法がございましたらご教示いただけますと幸いです。
- 受付中
- 数学・算数
- 線形計画法の解について!
線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。 問題は、以下のとおりです。 (線形計画法とシャドウ価格) 次の線形計画法の解、各制約のシャドウ価格を求めなさい。 制約条件 2x+y≦7, x+3y≦6, x≧0,y≧0 のもとで、目的関数 Z=x+y を最大化せよ。
- ベストアンサー
- 数学・算数
お礼
ありがとうございます。。 Pythonですねーー。 解ける例があるのですね!! 参考にしてみます m..m