- 締切済み
線型計画法問題
線型計画法、についての質問なんですが。 海外の大学に通ってるので問題は英語です。 Write linear programming formulation for the shortest path problem. 誰か知ってる人がいればお願いします。できれば少し説明も添付されればありがたいです。
- ken1710
- お礼率0% (0/1)
- その他（プログラミング・開発）
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- f272
- ベストアンサー率46% (8016/17133)
関連するQ&A
- 待ち行列問題と線形計画法
数学に携わらない人に2～3分で 待ち行列と線形計画法を説明します。 しかし、どういって説明したらよいかわかりません。 専門的に説明するのではなく どんな場面でどんな感じに使うのかを説明すれば よい良いようです。 ポワソン分布と指数関数という言葉を使うことを 指定されました。 （数学にあまり詳しくないと聞いてるのに そんな言葉を指定されるんの不思議ですが…） よかったら説明のしかたを教えてください。
- ベストアンサー
- 数学・算数
- Goal Programming の原理を教えてください
線形計画法は，線形の制約条件を満たしながら，線形の目的関数を最大もしくは最小化する 問題で，シンプレックス法により解くことができるし，幾何的イメージもできるので，わかるのですが， Goal Programming（目標計画法）とはどういうものなのでしょうか？ 検索してもあまりヒットせず難しくて分かりませんでした Goal Programming の原理を教えてください
- 締切済み
- 数学・算数
- 線形計画法の問題です
Ｐ：最大化ｃ＾Ｔｘ（ｃ＾Ｔはｃの転置） 条件Ａｘ＜＝ｂ ｘ＞＝０ ただし、Ａはｍ＊ｎ行列、ｂはｍ次元ベクトル、ｃはｎ次元ベクトル、ｘはｎ次元 変数ベクトルである。ベクトルはすべて列ベクトルとし、ｃ＾Ｔはｃの転置を表す。 問題Ｐは最適解を持つと仮定し、目的関数の最大値をｆと表す。また、問題Ｐ に関連して、ｍ次元ベクトルｕをパラメータとする次の線形計画問題を考える。 Ｐ（ｕ）：最大化ｃ＾Ｔｘ－ｕ＾Ｔ（Ａｘ－ｂ） 条件ｘ＞＝０ 問題Ｐ（ｕ）の目的関数の最大値ｇ（ｕ）と表す。ただし、問題Ｐ（ｕ）が有界でない 場合はｇ（ｕ）＝無限大と定義する。以下の問いに答えなさい。 １）問題Ｐの双対問題を書きなさい ２）任意のｕ＞＝０に対して、ｇ（ｕ）＞＝ｆが成り立つことを示しなさい ３）ｍｉｎ｛ｇ（ｕ）｜ｕ＞＝０｝＝ｆが成り立つことを示しなさい。ただし、線形計画問題 に対する強双対定理を用いて良い。 以上の問題をお願いします。
- 締切済み
- 数学・算数
- 線形計画法の問題です。
「製品1および製品2の1単位あたりの利益がそれぞれ15、25である。製品1と製品2の製造数をx1、x2とする。製品1を1単位製造するために必要な材料1、材料2の使用料はそれぞれ18単位、20単位であり、製品2の使用料はそれぞれ24単位、9単位である。材料1、2の使用可能量の上限をそれぞれ120単位、80単位とするとき、利益を最大化する製造数とそのときの利益を求めよ。」 自分で解いてみたところ、シンプレックス法で解いても、グラフを書いて解いても「x1=0、x2=5のとき、利益125」という答えになったのですが、これは合っていますでしょうか？ 今まで片方の製造数が0となった問題に出会ったことがないので、不安になり質問させていただきました。 どなたか確認していただけると幸いです。どうぞよろしくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画法の問題
ダム建設用のコンクリート作成に必要な砂、および砂利の調達を担当することになりました。ダムで利用する骨材は、不要な成分である細砂を５％以下に抑え、砂を６０％含み、砂利を３５％以上含むものにしなければなりません。利用可能な採掘場は４つあり、それぞれの運搬などの単位量あたり費用、構成比（砂、砂利、細砂）は以下の表のようになっています。これらを混ぜ合わせてコンクリート用の骨材を用意します。 採掘場１ 採掘場２ 採掘場３ 採掘場４ 指定混合比 単位量あたり費用 1 4 13 15 ― 砂 0.25 0.7 0.85 0.1 60% 砂利 0.65 0.2 0.1 0.9 35%以上 細砂 0.1 0.1 0.05 0 5%以下 それぞれの採掘場から調達する比率をXi (i=1,2,3,4) として、費用を最小化する目的変数および制約条件を求めたいのです。砂利と細砂の指定混合比の合計が40%になるように基底変数を立てていけばいいと思っているのですが、そこからが良くわからないのです。線形計画法について熟知されている方ならどなたでも、教えていただきますようよろしくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画法の問題で、悩んでます。
線形計画法の問題ですが。 たとえの問題です。 ２種類の餌料「Ｘ」と「Ｙ」を牛に与える１日に必要な、 ビタミン量を確保したままで、できるだけ価格を安くしたい。 Ｘ＝５０円/ｋｇ Ｙ＝１００円/Ｋｇ ビタミン量Ｘ Ｙ －－－－－－－－－－－－ Ａ ４ １ Ｂ ２ １ Ｃ ７ １０ Ｄ １ ３ －－－－－－－－－－－－ 餌（ｋｇ) ビタミン（ｍｇ） ビタミン必要量 －－－－－－－－－－－－ Ａ １２ Ｂ １０ Ｃ ７０ Ｄ １５ －－－－－－－－－－－－ ヒントは：目的は安くすること、制約条件は必要量。 どうとくのか、式だけでも教えていただけないでしょうか？ どう、手をつけたらいいのかわかりません。
- 締切済み
- 物理学
- 線形計画法？の問題が解けません
カロリー タンパク質 製品Ａ 270 kcal 8 g 製品Ｂ 165 kcal 16 g それぞれ１００ｇにつき という成分表が与えられています。 これだけで、１日あたりの栄養を 2500 kcal、 タンパク質を 100 g 確保したい。 総重量を最小にするにはどうしたらよいか。 という問題なのですけどわかりません。 求める重量を製品Ａは x 製品Ｂは y とおいて 目的関数 P = x + y 制約式 270x + 165y >= 2500 8x + 16y >= 100 として、グラフで許容領域を書いて求めようと考えたのですが、できませんでした。 まず、グラフが書けませんでした。 割り切れない数値でごちゃごちゃしてしまいました。 それで、この答え（できれば計算式も）を教えてくれませんか。 お願いします。
- ベストアンサー
- 数学・算数
- 線形計画法の問題です
線形計画法の問題です 問題 ・原料PとQから3種類の製品A、B、Cを生産している。 ・製品Aを生産するのに、原料Pを1トン、原料Qを2トン必要 ・製品Bを生産するのに、原料Pを1トン、原料Qを3トン必要 ・製品Cを生産するのに、原料Pを2トン、原料Qを4トン必要 ・原料Pの使用可能量は10トン、原料Qの使用可能量は28トン ・製品A、B、Cの1トン当たりの利益は、30万円、20万円、４０万円 ・市場調査の結果、製品Aの需要量は、製品Bの需要量を2トンより多く上回ることはない 問1．利益を最大化する問題を線形計画問題として定式化せよ 問2．最大利益とその時の各製品の生産量 問3．原料Pの最大使用可能量が1トン減った場合、最大利益がどのように変化するか 問4．原料Qの最大使用可能量が1トン減った場合、最大利益がどのように変化するか 答１．目的関数 30x1+20x2+40x3 → MAX 制約条件 x1+x2+2x3<=10 2x1+3x2+4x3<=28 答2．最大利益 300万円 製品A 10トン 製品B 0トン 製品C 0トン 答3．最大利益は-30万円 答４．最大利益は変化しない となってしまいます。 たぶん、『・市場調査の結果・・・』を制約式に入れていないため、変な答えになっていると思います。 どなたか、模範解答を教えてください。
- ベストアンサー
- 数学・算数
- 線形計画法の問題です。
問題は以下のURLの一番下（第2問-問題3）です。 http://www.gsm.kyoto-u.ac.jp/images/education/kakomon/24sugaku.pdf 得られる利益をz、製品Aをx1トン、製品Bをx2トン生産するとし、スラック変数x3、x4を導入すると、 -3x1 - 2x2 + z=0 x1 + x2 = 7 -(1) 2x1 + 3x2 + x3 = 24 3x1 + x2 - x4 =15 x1～x4≧0 ここで(1)式より、x2 = 7 - x1なので、他の式からx2を消去すると、 -x1 + z = 14 -x1 + x3 = 3 2x1 - x4 = 8 これを掃き出し法で解こうとすると、以下の写真のようになったのですが、 この掃き出し法によって分かるのは「z = 18 + x4/2」でx4の係数が正なので、「x4 = 0のときにzが最大値18をとる」とは言えませんよね？ 図形的に考えると、おそらくz=18（x1=4、x2=3）になると思うのですが、私の計算がどこかで間違っているのでしょうか？ それともこの掃き出し法の結果から、zが最大値18をとると言えるのでしょうか？ どなたかご教授ください。どうぞよろしくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画法の解き方について
情報処理の試験勉強をしているのですが、線形計画の問題が解けなくて困っています。 どなたか教えていただけないでしょうか。 問題は以下のとおりです。 部品A～Ｃを使用して、製品Ｘ、Ｙを生産している。 表は、各製品を1個生産するために必要な部品数、各製品の１個当たりの販売利益、各部品の１日に使用可能な最大部品数を示している。 1日の販売利益を最大にするように、製品Ｘ、Ｙを生産し、すべて販売したときの販売利益は何円か。 製品Ｘ 製品Ｙ 1日に使用可能な最大部品数 部品A ２個 ４個 ２６０個 部品B ３個 ３個 ２１０個 部品C ２個 １個 １１０個 １個あたりの ３０００円 ２０００円 販売利益 ア １５００００ イ １６５０００(正解) ウ １８００００ エ １９００００ 部品の種類が２つの場合の問題は製品Ｘ、Ｙの数を求めることが出来るのですが、部品の種類が３つになるとどうやったらいいのかわかりません。 テキストなどを見てもグラフを書いて解くやりかたしか書いてなかったのですが、部品が２種類のときはグラフを書かずに式だけで解いていました。 やはり、グラフを書かないと解くことが出来ないのでしょうか？ どうか、よろしくおねがいします。
- ベストアンサー
- 情報処理技術者
