線形計画法：モデル、制約、アプリケーションの目的 - 数学 - 2025

線形プログラミングは、数学的な方法であるれている最適化するために使用される（最大又は適宜最小）は、その変数、制限される関数として長い関数と制約条件が線形従属変数です。

一般に、最適化される機能は、投入量、労働力、または機械が制限されているメーカーの利益などの実際的な状況をモデル化します。

図1.線形計画法は、利益を最適化するために広く使用されています。出典：Piqsels。

最も単純なケースの1つは、最大化される線形関数の場合です。これは、決定変数と呼ばれる2つの変数にのみ依存します。次の形式にすることができます。

Z = k ₁ x + k ₂ y

k ₁およびk _2は一定。この関数は目的関数と呼ばれます。もちろん、調査のために3つ以上の変数に値する状況があり、より複雑になります。

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +…。

また、制約は、xとyで等しく線形の方程式または不等式のシステムによって数学的にモデル化されます。

このシステムのソリューションのセットは、実行可能ソリューションまたは実行可能ポイントと呼ばれます。そして、実行可能な点の中には、目的関数を最適化する少なくとも1つの点があります。

線形計画法は、第二次世界大戦直後のアメリカの物理学者で数学者のジョージダンツィヒ（1914-2005）とロシアの数学者で経済学者のレオニードカントロビッチ（1912-1986）によって独立して開発されました。

シンプレックス法として知られる問題解決法は、米国空軍、バークレー大学、スタンフォード大学で働いていたDantzigの発案によるものです。

図2.数学者George Dantzig（左）とLeonid Kantorovich（右）。出典：F. Zapata。

線形計画モデル

実用的な状況に適した線形計画モデルを確立するために必要な要素は次のとおりです。

-目的関数

-決定変数

-制限

目的関数では、達成したいことを定義します。たとえば、特定の製品の製造から得られる利益を最大化したいとします。次に、製品の販売価格に応じて「利益」機能が確立されます。

数学的には、この関数は総和表記を使用して省略して表すことができます。

Z = ∑k _i x _i

この方程式では、k _iは係数で、x _iは決定変数です。

決定変数は、制御されているシステムの要素であり、それらの値は正の実数です。提案された例では、決定変数は、最大の利益を得るために製造される各製品の数量です。

最後に、私たちは制約を持っています。これは、決定変数に関して線形方程式または不等式です。それらは既知であり、例えば製造で利用可能な原材料の量であり得る問題への制限を説明します。

制限の種類

j = 1からj = MまでのMの制限を設定できます。数学的には、制限には次の3つのタイプがあります。

1. A _j = ∑ a _ij。x _i
2. B _J ≥Σbは_IJ。x _i
3. C _J ≤ΣC _IJ。x _i

最初の制限は線形方程式タイプであり、既知の値A _jを尊重する必要があることを意味します。

残りの2つの制限は線形不等式であり、出現するシンボルが≥（以上）である場合、またはシンボルが≤である場合、既知の値B _jおよびC _jを尊重または超過できる（以下）。

モデル例

経営学から栄養学に至るまで、応用分野は非常に多様ですが、その方法を理解するために、2つの変数を持つ実際の状況の単純なモデルを以下に提案します。

地元のパティスリーは、黒い森のケーキとサクランパンケーキの2つの料理で知られています。

その準備には卵と砂糖が必要です。黒い森には9個の卵と500 gの砂糖が必要ですが、サクリパンティンには8個の卵と800 gの砂糖が必要です。それぞれの販売価格は8ドルと10ドルです。

問題は、ベーカリーが10キロの砂糖と144個の卵を持っていることを知って、利益を最大にするために、各タイプのケーキをいくつ作る必要があるのか​​ということです。

決定変数

決定変数は「x」と「y」であり、実際の値を取ります。

-x：黒い森のケーキの数

-y：サクランパンタイプのケーキ。

制限事項

制限は、ケーキの数が正の量であり、それらを調製するための原料の量が限られているという事実によって与えられます。

したがって、数学的形式では、これらの制限は次の形式を取ります。

1. x≥0
2. および≥0
3. 9x + 8y≤144
4. 0.5 x + 0.8y≤10

制約1と2は、以前に公開された非否定性の条件を構成し、発生したすべての不等式は線形です。制限3と4には、超えてはならない値があります：144個の卵と10kgの砂糖。

目的関数

最後に、目的関数は、「x」の量の黒い森のケーキと「y」の量のサクリパンチンを製造するときに得られる利益です。価格にケーキの量を掛けて、タイプごとに追加することで作成されます。これは、G（x、y）と呼ぶ線形関数です。

G = 8x + 10y

解決方法

さまざまなソリューション手法には、いくつか例を挙げると、グラフィカル手法、シンプレックスアルゴリズム、内点法などがあります。

-グラフィックまたは幾何学的方法

前のセクションのような2変数の問題がある場合、制約は、実行可能領域または実行可能領域と呼ばれる、xy平面内の多角形領域を決定します。

図3.最適化問題の解が見つかる実行可能領域。出典：ウィキメディア・コモンズ。

この領域は、制限の不等式から得られる線である制限線を使用して構築され、等号のみを使用して機能します。

利益を最適化したいベーカリーの場合、制約線は次のとおりです。

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

これらの線で囲まれた領域内のすべての点が考えられる解決策であるため、それらの数は無限にあります。実行可能領域が空であることが判明した場合を除いて、この場合、提起された問題には解決策がありません。

幸いなことに、ペストリーの問題では、実行可能領域は空ではありません。以下に示します。

図4.ペストリー問題の実行可能領域。ゲイン0の線が原点と交差しています。出典：F. Zapata with Geogebra。

最適解が存在する場合は、目的関数を使用して見つけられます。たとえば、最大利益Gを見つけようとすると、iso-profit行と呼ばれる次の行があります。

G = k ₁ x + k ₂ y→y = -k ₁ x / k ₂ + G / k ₂

この線を使用して、特定のゲインGを提供するすべてのペア（x​​、y）を取得します。そのため、Gの値に応じた線のファミリーがありますが、すべて同じ勾配-k ₁ / k ₂なので、それらは平行線。

最適なソリューション

ここで、線形問題の最適解は常に実行可能領域の極値または頂点であることを示すことができます。そう：

原点に最も近い線が、実行可能領域と共通のセグメント全体を持っている場合、無限解があると言われます。このケースは、等収益線の勾配が、領域を制限する他の線の勾配と等しい場合に発生します。

私たちのペストリーの場合、候補となる頂点はA、B、Cです。

-Dantzigのシンプレックス法

グラフィカルまたは幾何学的な方法は、2つの変数に適用できます。ただし、変数が3つある場合はさらに複雑になり、多数の変数に使用することはできません。

3つ以上の変数を持つ問題を処理する場合、目的関数を最適化する一連のアルゴリズムで構成されるシンプレックス法が使用されます。計算には、行列と単純な算術がよく使用されます。

シンプレックス法は、実行可能なソリューションを選択し、それが最適かどうかを確認することから始まります。そうであれば、問題はすでに解決されていますが、解決されていない場合は、最適化により近い解決策に向けて継続します。解が存在する場合、アルゴリズムは数回の試行でそれを見つけます。

用途

線形および非線形プログラミングは多くの分野で適用され、コストの削減と利益の増加の観点から最良の決定を行います。これは、必ずしも必要な時間を最小限にしたい場合など、時間で測定できるため、必ずしも金銭的ではありません。一連の操作を実行します。

ここにいくつかのフィールドがあります：

-マーケティングでは、特定の製品を宣伝するためのメディア（ソーシャルネットワーク、テレビ、プレスなど）の最適な組み合わせを見つけるために使用されます。

-会社や工場の担当者やスケジュールに適切なタスクを割り当てるため。

-家畜および家禽産業で最も栄養価の高い食品の選択と最低コストで。

解決された演習

-演習1

前のセクションで取り上げた線形計画モデルをグラフィカルに解きます。

解決

問題で指定された制限のシステムによって決定された値のセットをグラフ化する必要があります。

1. x≥0
2. および≥0
3. 9x + 8y≤144
4. 0.5 x + 0.8y≤10

不等式1および2によって与えられる領域は、デカルト平面の最初の象限に対応します。不等式3と4に関しては、制限線を見つけることから始めます。

9x + 8y = 144

0.5 x + 0.8y = 10→5x + 8y = 100

実行可能領域は、頂点が点A、B、C、およびDである四辺形です。

最小利益は0であるため、8x + 10y = 0の線が下限であり、等利益線の勾配は-8/10 =-0.8です。

この値は他の制限線の勾配とは異なり、実行可能領域が制限されているため、一意のソリューションが存在します。

図5.演習1のグラフィック解。実行可能領域と、その領域の頂点の1つにある解の点Cを示しています。出典：F. Zapata。

この解は、座標が次のいずれかである点A、B、またはCのいずれかを通過する勾配-0.8の線に対応します。

A（11; 5.625）

B（0; 12.5）

C（16、0）

最適なソリューション

これらの各点についてGの値を計算します。

-（11; 5.625）：G _A = 8 x 11 + 10 x 5.625 = 144.25

-（0; 12.5）：G _B = 8 x 0 + 10 x 12.5 = 125

-（16、0）：G _C = 8 x 16 + 10 x 0 = 128

最も高い利益は、11個の黒い森のケーキと5,625個のサクランパンのケーキを製造することです。この解決策は、ソフトウェアで見つかった解決策と一致します。

-演習2

ExcelやLibreOffice Calcなどのほとんどのスプレッドシートで使用できるソルバー関数を使用して、前の演習の結果を確認します。これには、線形プログラミングの最適化のためのシンプレックスアルゴリズムが組み込まれています。

解決

図6.演習1からLibre Office Calcスプレッドシートまでのソリューションの詳細。出典：F. Zapata。

図7.演習1からLibre Office Calcスプレッドシートまでのソリューションの詳細。出典：F. Zapata。

参考文献

1. 鮮やかさ。線形計画。から回復：brilliant.org。
2. エッペン、G。2000。管理科学における運用研究。5日。版。プレンティスホール。
3. Haeussler、E。1992。経営と経済学のための数学。2番目。版。Grupo社説Iberoamericana。
4. Hiru.eus。線形計画。から回復：hiru.eus。
5. ウィキペディア。線形計画。から回復：es。 wikipedia.org。