線形計画法とは、最適なプログラミング手法を指します。 線形計画法の概念。 線形計画問題の種類

線形計画法は、40年代から50年代に応用数学の別の分野として登場しました。 20世紀 ソビエトの科学者、ノーベル賞受賞者L.V.の作品に感謝します。 カントロヴィッチ。 1939年に彼は「数学的組織化と生産計画」という作品を発表しました。この作品では、数学を使用して、機械の最適な積載、最低コストでの材料の切断、いくつかの輸送モードでの商品の流通に関する経済的問題を解決しました。その他、要因を解決する方法を提案する8..。

L.V. カントロビッチは、最適な計画、リソースの最適な割り当て、客観的に決定された見積もりなど、広く使用されている経済的および数学的概念を最初に策定し、それらを適用できる経済学の多くの分野を示しました。

線形計画法の概念は、1949年に「シンプレックス法」と呼ばれる線形計画問題を解くためのアルゴリズムを提案したアメリカの数学者D.ダンジグによって導入されました。

線形計画法を含む数理計画法は、現在、オペレーションズリサーチの分野の1つです。 解決する問題のタイプに応じて、そのような領域は線形、非線形、離散、 動的計画法「プログラミング」という用語は、問題を解決する過程にある未知の変数が、通常、何らかの経済的対象のプログラムまたは作業計画を決定するという事実のために導入されました。

古典的な数学的分析では、条件付き極値を決定する問題の一般的な定式化が調査されます。 しかし、工業生産、運輸、農工業団地、銀行セクターの発展により、従来の数学的分析の結果は不十分であることが判明しました。 実践の必要性とコンピューター技術の開発により、複雑な経済システムの分析において最適なソリューションを決定する必要が生じています。

このような問題を解決するための主なツールは、数学的モデリングです。 同時に、最初に単純なモデルが構築され、次にその調査が実行されます。これにより、オブジェクトの統合プロパティのどれが形式スキームによってキャプチャされないかを理解できます。その後、モデル、現実へのより大きな妥当性が保証されます。 多くの場合、現実への最初の近似は、オブジェクトの状態を特徴付ける変数間のすべての依存関係が線形であるモデルです。 実践は、十分な数の経済プロセスが線形モデルによって適切に記述されていることを示しています。 したがって、線形方程式と不等式によって与えられる集合の条件付き極値を見つけることを可能にする装置としての線形計画法は、これらのプロセスの分析において重要な役割を果たします。

線形計画法は、多くの計画および制御問題を線形計画問題の形で定式化できることが確立されたという事実により、広く発展してきました。その解決策には効果的な方法があります。 専門家によると、実際に解決されるすべての最適化問題の約80〜85％は、線形計画問題に関連しています。

作成された数学的装置は、労働集約的な計算を実行するコンピュータープログラムと組み合わされて、経済科学および実践において線形計画モデルを広く使用することを可能にします。

定義1 9 . 線形計画法（LP）は数理計画法の分野であり、数学の分野であり、有限数の変数の線形関数の極値（最大値と最小値）を見つける方法を研究し、その未知数に線形制約が課せられます。

この線形関数は目的と呼ばれ、経済問題の条件と要件を表す変数間の定量的な関係を表し、方程式または不等式の形で数学的に記述される制約は、制約システムと呼ばれます。

経済プロセスの計画に関する幅広い問題は、線形計画法の問題に還元されます。線形計画法では、最良の（最適な）解決策を見つけるという問題が提起されます。

一般的な線形計画問題（LPP）は、ターゲット10と呼ばれる線形関数の極値（最大または最小）を見つけることです。

から NS 変数 NS 1 , NS 2 , …, NS NS機能制限が課せられた場合：

(3.2)

および直接制約（変数の非負性の要件）

, (3.3)

どこ NS ij , NS 私 , NS NS-与えられた定数値。

制限システム（3.2）では、「以下」、「等しい」、「以上」の記号が同時に発生する可能性があります。

より簡潔な表記のZLPの形式は次のとおりです。

,

制限付き：

;

.

ベクトル ` NS = (NS 1 , NS 2 , …, NS NS）そのコンポーネントが問題の機能的および直接的な制約を満たす 予定（また 許容できる決定）ZLP。

許容されるすべてのソリューションフォーム ドメイン 線形計画問題、または 実行可能なソリューションの範囲 （ODR）。 目的関数の最大値または最小値を提供する実行可能なソリューション NS(`NS）、問題の最適計画と呼ばれ、 NS(`NS * ）、 どこ ` NS * =(NS 1 * , NS 2 * , …, NS NS * ).

LPPを書く別の形式：

,

どこ NS(`NS * ）は最大（最小）値です NS(と, NS）セットに含まれるすべてのソリューションを引き継ぎました 可能な解決策 NS .

定義2 11 ..。 目的関数とその限界の数式は、経済問題の数学的モデルと呼ばれます。

数学モデルを作成するには、次のことを行う必要があります。

1）変数を指定します。

2）タスクの目標に基づいて目的関数を作成します。

3）問題の状態の指標とその定量的パターンを考慮に入れて、制限のシステムを書き留めます。

2.線形計画法の概念。 線形計画問題の種類

線形計画法（LP）は、数理計画法の最初で最も徹底的に研究された分野の1つです。 「数理計画法」のまさにその分野が発展し始めたセクションであったのは線形計画法でした。 分野の名前での「プログラミング」という用語は、「コンピュータのプログラミング（つまりプログラムの作成）」という用語とは何の関係もありません。 「線形計画法」の分野は、コンピューターが数学、工学、経済、その他の問題を解決するために広く使用される前から生まれました。

「線形計画法」という用語は、英語の「線形計画法」の不正確な翻訳から生じました。 「プログラミング」という言葉の意味の1つは、計画を立てること、計画を立てることです。 したがって、英語の「線形計画法」の正しい翻訳は「線形計画法」ではなく、「線形計画法」であり、これは分野の内容をより正確に反映しています。 ただし、線形計画法、非線形計画法、数理計画法などの用語。 私たちの文献では一般的に受け入れられているため、保存されます。

そのため、線形計画法は第二次世界大戦後に出現し、急速に発展し始め、数学の調和だけでなく、幅広い実用化の可能性から、数学者、経済学者、エンジニアの注目を集めました。

線形計画法は、これらのプロセスやシステムの数学的モデルを解くのに適用可能であると言えます。これは、実世界の線形表現の仮説に基づくことができます。

線形計画法は、管理や生産計画などのタスクで経済問題を解決するために使用されます。 ワークショップでの船への機器の最適な配置を決定するタスク。 商品の輸送のための最適な計画を決定するタスク（輸送問題）; 最適な人員配置などの問題で。

線形計画法（LP）の問題は、上記の説明からすでに明らかなように、線形制約の下で線形関数の最小値（または最大値）を見つけることにあります。

LP問題を解くにはいくつかの方法があります。 このホワイトペーパーでは、それらのいくつか、特に次のことを検討します。

LP問題を解くためのグラフィック手法。

シンプレックス法;

Excelスプレッドシートプロセッサを使用してLP問題を解決します。

3.非線形計画法の概念

ほとんどの工学的問題では、数学モデルの構築を線形計画問題に還元することはできません。

実際のオブジェクトまたは技術プロセスの設計問題における数学的モデルは、実際の物理的プロセス、および原則として、それらで発生する非線形プロセスを反映する必要があります。 これらのオブジェクトまたはプロセスの変数は、質量保存の法則やエネルギー保存の法則などの物理的な非線形法則によって相互接続されています。 それらは、特定のオブジェクトまたはプロセスの物理的な実現可能性を保証する制限範囲によって制限されます。 その結果、研究プロジェクトや設計問題で遭遇する数理計画問題のほとんどは、非線形計画法（NP）問題です。

本論文では、ラグランジュ乗数法として、NP問題を解く方法を検討する。

ラグランジュ乗数法を使用すると、等式制約の下で関数の最大（または最小）を見つけることができます。 この方法の主なアイデアは、条件付き極値の問題から、特定の構築されたラグランジュ関数の無条件極値を見つける問題に移ることです。

4.動的計画法

動的計画法は、分析された状況に不確実性の要因が含まれていないが、 たくさんのさまざまな結果をもたらす行動。その中で最良のものを選択する必要があります。 動的計画法は、特定のクラスの問題を、小さくて複雑でない問題に分解することによって、それらの問題の解決にアプローチします。 原則として、この種の問題はすべてを列挙することで解決できます 可能なオプションそしてそれらの中から最良のものを選択しますが、しばしばそのような列挙は非常に困難です。 このような場合、最適な意思決定を行うプロセスをステップ（ステージ）に分割し、動的計画法を使用して調査することができます。

動的計画法による問題の解決は、R.E。ベルマンによって定式化された最適性の原則に基づいて実行されます。最適な動作には、何があってもその特性があります。 元の状態システムと最初の決定、その後の決定は、最初の決定の結果として得られた状態に関連して最適な動作を決定する必要があります。

したがって、各ステップの計画は、プロセス全体の最後に得られる全体的な利点を考慮して実行する必要があります。これにより、選択した基準に従って最終結果を最適化できます。

ただし、動的計画法は普遍的な解決方法ではありません。 この方法で解決されるほとんどすべての問題は、それ自体の特性によって特徴付けられ、その解決のために最も受け入れられる方法のセットを検索する必要があります。 さらに、多くの状態で多段階の問題を解決するための大量の労力は、低次元の問題を選択するか、圧縮された情報を使用する必要につながります。

動的計画法は、次のような問題を解決するために使用されます。 需要と在庫を管理するためのルールの開発。 作成する カレンダープラン機器の現在および主要な修理とその交換。 トランスポートネットワークなどで最短距離を検索します。

最適化プロセスをnステップに分割します。 各ステップで、状態変数Sと制御変数Xの2種類の変数を定義する必要があります。変数Sは、システムがどの状態で自分自身を見つけることができるかを決定します。 このk番目ステップ。 Sに応じて、このステップで、変数Xによって特徴付けられるいくつかのコントロールを適用できます。k番目のステップでコントロールXを適用すると、結果Wk（S、Xk）が生成され、システムが新しい状態S "（S 、Xk）。k番目のステップで可能な各状態について、すべての可能な制御の中から、k番目からn番目までのステップで達成される結果が最適になるように最適な制御X * kが選択されます。この結果の数値特性は次のとおりです。ベルマン関数Fk（S）と呼ばれ、ステップ番号kとシステムSの状態に依存します。

この問題のすべての解決策は、2つの段階に分かれています。 条件付き最適化と呼ばれる最初の段階では、ベルマン関数と最適制御が、最後のステップから始まる各ステップですべての可能な状態に対して検出されます。

n番目から最初のステップまでのすべてのステップでベルマン関数と対応する最適制御が見つかった後、問題を解決する第2段階が実行されます。これは、制約なし最適化と呼ばれます。

V 一般的な見解動的計画問題は次のように定式化されます。システムを初期状態S0から最終状態Snに転送する制御X *を定義する必要があります。この制御では、目的関数F（S0、X *）が最大（最小）になります。 ） 価値。

動的計画法の数学的モデルの特徴は次のとおりです。

最適化問題は、最終的な多段階制御プロセスとして定式化されます。

目的関数は加法的であり、各ステップの目的関数の合計に等しくなります

各ステップでの制御Xkの選択は、このステップSk-1のシステムの状態にのみ依存し、前のステップには影響しません（ フィードバック);

各制御ステップ後のシステムSkの状態は、システムSk-1の前の状態とこの制御アクションXk（後遺症なし）にのみ依存し、状態方程式の形式で記述できます。

各ステップで、制御Xkは有限数の制御変数に依存し、システムSkの状態は有限数の変数に依存します。

最適制御X *は、一連の最適な段階的制御によって決定されるベクトルです。

X * =（X * 1、X * 2、...、X * k、...、X * n）、

その数によって、タスクのステップ数が決まります。

条件付き最適化。 上記のように、 この段階ベルマン関数と最適な制御は、後方掃引アルゴリズムに従って最後の状態から開始して、各ステップですべての可能な状態に対して検出されます。 オン 最後のn番目ステップ、最適制御X * nとベルマン関数Fn（S）の値を見つけることは難しくありません。

Fn（S）= max（Wn（S、Xn））、

ここで、Xnのすべての可能な値に対して最大値が求められます。

各ステップのベルマン関数を同じ関数に接続する漸化式に従って、さらに計算が実行されますが、前のステップで計算されます。

Fk（S）= max（Wk（S、Xk）+ Fk + 1（S "（S、Xk）））。（1）

この最大値（または最小値）は、kおよびSの制御変数Xのすべての可能な値に対して決定されます。

無条件の最適化。 ベルマン関数と対応する最適な制御がn番目から最初のステップまでのすべてのステップで見つかった後（最初のステップk = 1で、システムの状態は初期状態S0に等しくなります）、問題を解決する第2段階が行われて。 最適制御は最初のステップX1で見つかります。これを適用すると、システムは状態S1（S、x1 *）になり、条件付き最適化の結果を使用して、2番目のステップで最適制御を見つけることができます。 、というように、最後のn番目のステップまで続きます。

実験室での作業＃1（線形計画問題）

LP問題の特定の数学的定式化に対して、変数の非負性の追加条件を取り、次のアクションを実行します。

問題をグラフィカルに解決します。

タスクを標準形の表記法にします。

シンプレックステーブルを作成します。

問題を解く シンプレックス法 手でまたはコンピューターを使用する。

ステージングを実行する デュアルタスク LP;

以前に取得したシンプレックステーブルから双対問題の解を取得し、取得した結果を分析します。

Excelスプレッドシートでソリューションの結果を確認します。

各項目の結果をまとめたレポートを作成します。

グラフィック方式。 ソリューションポリゴンを構築するために、元のシステムを変換します

、 我々が得る

境界線を表します。

一次関数 F = f（x）は、直線c1x1 + c2x2 = constの方程式です。 f（x）= 0の目的関数のグラフを作成してみましょう。 直線3x1 + 4x2 = 0を作成するには、半径ベクトルN =（3; 4）を作成し、点0を介してそれに垂直な直線を描画します。 構築された線F = 0は、ベクトルNの方向にそれ自体と平行に移動します。

図1から、この直線は、関数Fが最大値をとる点Bで構築されたソリューションポリゴンに対するサポートになります。 点Bは、直線0.7x1 +2x2≤13.1と2.3x1 + 2x2 = 23の交点にあります。その座標を決定するために、連立方程式を解きます。

問題の最適な計画：х1= 6.187; x2 = 4.38、x1とx2の値を目的関数に代入すると、Fmax = 3 * 6.187 + 4 * 4.38 = 36.08が得られます。

したがって、36.06ドルの最大利益を得るには、6ユニットの生産を計画する必要があります。 製品P1および4ユニット。 P2製品。

LP問題の標準形。 リソース割り当ての問題を標準形で書き留めましょう。 元の制約システムに非負の変数x3≥0、x4≥0、x5≥0を追加すると、次のようになります。

LPシンプレックステーブル。 基本変数（x3、x4、x5）の場合、最初のシンプレックステーブルは次のようになります。

表1。

これは、ベースラインプランx（0）= T（無料メンバーの列）にすでに対応しています。

この方法は、線形計画問題のサポートソリューションを意図的に列挙する方法です。 これにより、有限のステップ数で、最適なソリューションを見つけるか、最適なソリューションがないことを確認できます。

1. 最適なサポートソリューションを見つける方法を示してください
2. あるサポートソリューションから別のサポートソリューションへの移行方法を示します。この方法では、目的関数の値が最適なものに近くなります。 サポートソリューションを改善する方法を示す
3. 最適なソリューションでサポートソリューションの検索をタイムリーに停止したり、最適なソリューションがないという結論に従うことができる基準を設定します。

線形計画問題を解くためのシンプレックス法のアルゴリズム

1. 問題を標準形にする
2. 「ユニットベース」で最初のサポートソリューションを見つけます（サポートソリューションがない場合、制約システムの非互換性のために問題は解決されません）
3. サポートソリューションに基づいてベクトル展開の推定値を計算し、シンプレックス法の表に記入します
4. 最適解の一意性の基準が満たされると、問題の解は終了します。
5. 一連の最適解が存在するための条件が満たされている場合、単純な列挙によってすべての最適解が見つかります

シンプレックス法を使用して問題を解決する例

シンプレックス法を使用して問題を解決します。

解決：

問題を標準形にします。

これを行うために、最初の不等式制約の左側に、係数+1の追加の変数x6を導入します。 変数x6は、係数がゼロの目的関数に含まれています（つまり、含まれていません）。

我々が得る：

初期のサポートソリューションを見つけます。 このため、自由な（未解決の）変数はゼロx1 = x2 = x3 = 0に等しくなります。

我々が得る リファレンスソリューション X1 =（0,0,0,24,30,6）、単位ベースB1 =（A4、A5、A6）。

計算します ベクトル展開の推定次の式による参照解に基づく条件：

Δk= C b X k-c k

• C b =（c 1、c 2、...、c m）は、基本変数の目的関数の係数のベクトルです。
• X k =（x 1k、x 2k、...、x mk）は、サポートソリューションに基づく対応するベクトルAkの展開ベクトルです。
• Ck-変数xkでの目的関数の係数。

基底に含まれるベクトルの推定値は常にゼロです。 サポートソリューション、拡張係数、およびサポートソリューションに基づく条件ベクトルの拡張の推定値は次のように記述されます。 シンプレックステーブル:

表の上には、推定値の計算に便利なように、目的関数の係数が書かれています。 最初の列「B」には、参照解の基礎に含まれるベクトルが含まれています。 これらのベクトルの書き込み順序は、制約方程式で許可されている未知数の数に対応します。 表「Cb」の2番目の列は、目的関数の係数と基本変数を同じ順序で記録します。 「Cb」列の目的関数係数が正しく配置されている場合、基底に含まれる単位ベクトルの推定値は常にゼロになります。

列「A0」に推定値Δkがある表の最後の行は、参照解Z（X 1）の目的関数の値を記録します。

最大の問題では、ベクトルА1とА3の推定値Δ1= -2、Δ3= -9が負であるため、初期サポートソリューションは最適ではありません。

サポートソリューションの改善に関する定理によれば、最大問題で少なくとも1つのベクトルが負の推定値を持つ場合、目的関数の値が大きくなる新しいサポートソリューションを見つけることができます。

2つのベクトルのどちらが目的関数のより大きな増分につながるかを決定しましょう。

目的関数の増分は、次の式で求められます。

次の式を使用して、1列目と3列目のパラメーターθ01の値を計算します。

l = 1でθ01= 6、l = 1でθ03= 3が得られます（表26.1）。

最初のベクトルΔZ1= -6 *（-2）= 12を基底に導入し、3番目のベクトルΔZ3= -3 *（-9）= 27を導入することにより、目的関数の増分を求めます。

したがって、最適解をより速く近似するには、最初の行でパラメーターθ03の最小値に達するため、基底A6の最初のベクトルではなくベクトルA3をサポート解の基底に導入する必要があります。 （l = 1）。

要素X13 = 2を使用してヨルダン変換を実行し、基底B2 =（A3、A4、A5）を使用して2番目のサポートソリューションX2 =（0,0,3,21,42,0）を取得します。 （表26.2）

ベクトルA2の推定値は負であるため、この解は最適ではありません。Δ2= -6。解を改善するには、サポート解の基礎にベクトルA2を導入する必要があります。

基底から導出されたベクトルの数を決定します。 これを行うには、2番目の列のパラメーターθ02を計算します。これは、l = 2の場合は7に等しくなります。したがって、基底から2番目の基底ベクトルA4を導出します。 要素x22 = 3を使用してヨルダン変換を実行すると、3番目の参照解X3 =（0.7,10,0.63.0）B2 =（A3、A2、A5）が得られます（表26.3）。

推定に含まれていないすべてのベクトルについて、正であるため、このソリューションが唯一の最適なソリューションです。

Δ1= 7/2、Δ4= 2、Δ6= 7/2。

答え： X =（0.7,10,0.63）で最大Z（X）= 201。

経済分析における線形計画法

線形計画法生産に使用される資源（固定資産、材料、労働資源）に関連する厳しい制限の条件で、最適な経済的解決策を実証することを可能にします。 経済分析でこの方法を使用すると、主に組織の活動の計画に関連する問題を解決できます。 この方法は、生産出力の最適値、および最も多くの方向を決定するのに役立ちます 有効活用生産リソースの編成に利用できます。

この方法の助けを借りて、いわゆる極値問題の解決が実行されます。これは、極値、つまり可変量の最大関数と最小関数を見つけることから成ります。

この期間は、システムのソリューションに基づいています 一次方程式分析された経済現象が線形の厳密な関数従属性によってリンクされている場合。 線形計画法は、特定の制限要因が存在する場合に変数を分析するために使用されます。

線形計画法を使用したいわゆる輸送問題の解決は非常に一般的です。 このタスクの内容は、最大のサービスが必要な場合に、車両の数、収容力、運用期間に関する既存の制限の条件で、車両の運用に関連して発生するコストを最小限に抑えることです。顧客の数。

その上、 この方法スケジューリング問題の解決に幅広い用途があります。 このタスクは、特定の組織の担当者の機能時間のそのような配分で構成されます。これは、この担当者のメンバーと組織のクライアントの両方にとって最も受け入れられるものです。

このタスクは、利用可能なスタッフの数と労働時間の資金の制限に直面してサービスを提供するクライアントの数を最大化することです。

したがって、線形計画法は、配置と使用の分析では非常に一般的です。 他の種類リソース、および組織の活動の計画と予測の過程で。

それにもかかわらず、数理計画法は、それらの間の関係が線形ではないこれらの経済現象に適用することができます。 この目的のために、非線形、動的、および凸計画法を使用できます。

非線形計画法は、目的関数または制約、あるいはその両方の非線形性に依存しています。 これらの条件下での目的関数の形式と制約の不等式は異なる場合があります。

非線形計画法は、経済分析、特に組織の活動の有効性を表す指標とこの活動の量、生産コストの構造、市況などとの関係を確立するときに使用されます。

動的計画法は、決定木の構築に基づいています。 このツリーの各層は、前の決定の結果を決定し、この決定の効果のないオプションを排除するための段階として機能します。 したがって、動的計画法には、マルチステップ、マルチステップの性質があります。 このタイプのプログラミングは、現在および将来の組織の発展のための最良のオプションを見つけるために、経済分析で使用されます。

凸計画法は、非線形計画法の一種です。 このタイプのプログラミングは、組織の活動の結果とそれによって発生するコストとの間の関係の非線形性を表現します。 凸面（別名凹面）プログラミングは凸面を分析します ターゲット機能制約の凸系（点 許容値）。 凸計画法は、コストを最小化するために経済活動の分析に使用され、凹面プログラミングは、分析された指標に反対の方法で影響を与える要因の作用に対する既存の制限の条件下で収入を最大化するために使用されます。 その結果、考慮されるタイプのプログラミングでは、凸型の目的関数が最小化され、凹型の目的関数が最大化されます。