線形計画問題、解決策、およびアプリケーション[例付き]

データサイエンスには多くのアプリケーションがありますが、その中で最も顕著なものの1つは最適化です。 私たちは皆、ものを最適化することに集中する傾向があります。 最適化は、限られたリソースで最も望ましい結果を得ることに焦点を当てています。

利用可能な最適化問題にはさまざまな種類があり、小さいものもあれば、非常に複雑なものもあります。 それらを調べていると、線形計画問題と呼ばれる特定のカテゴリが見つかります。 この記事では、それらが何であるか、およびそれらにどのように取り組むことができるかについて説明しました。

あなたがオレンジまたはリンゴ、あるいはそれらの両方の特定の組み合わせを購入できる果物の売り手であるとします。 ただし、予算は5,000インドルピーしかなく、30袋しか保管できません。 今、あなたはあなたに最高の利益をもたらす方法でそれらを買わなければなりません。

現在、オレンジ1袋は500インドルピー、リンゴ1袋は750インドルピーです。オレンジ1袋の販売で100インドルピー、リンゴ1袋の販売で200インドルピーを稼ぐことができます。

この問題にはさまざまな可能性があります。 オレンジのみを購入することを選択する場合もありますが、その場合、ストレージには10個のバッグしかなく、利益は1000インドルピーになります。同様に、リンゴのみを購入し、利益として1500インドルピーを稼ぐこともできます。 2つの組み合わせを購入することもできます。

このような問題は線形計画問題と呼ばれ、詳細に説明します。 始めましょう：

線形計画法とは何ですか？

線形計画法は、線形関数を使用して複雑な関係を表現する方法です。 線形計画法の目的は、これらの関数に最適なソリューションを見つけることです。 2点間の実際の関係は非常に複雑になる可能性がありますが、線形計画法を使用してそれらを簡単に表現できます。 線形計画法は、多くの業界でアプリケーションを見つけます。

線形計画法の基礎

線形計画法の基本的な用語は次のとおりです。

制約

決定変数の制限（または制限）は、制約と呼ばれます。 ほとんどの時間の制約は、問題を解決するためのリソースに対する制限です。

決定変数

これらの変数は出力を定義します。 結果はこれらの変数に依存するため、これらを「決定変数」と呼びます。

非負の制限

線形計画問題の決定変数は、負でない値しか持つことができません。 これは、決定変数の値がゼロ以上になる可能性があることを意味します。

目的関数

目的関数は、意思決定を行う目的です。 簡単に言えば、それは線形計画問題の最終結果です。 たとえば、特定のリソースセットで得られる最大の利益を見つける場合、最大の利益は目的関数です。

線形計画問題の定式化

線形計画法を定式化して実際に適用する方法を知っておく必要があります。 あなたがおもちゃの製造業者であり、AとBの2つのおもちゃしか製造していないとします。大まかに言えば、おもちゃの製造には2つのリソースXとYが必要です。 おもちゃの要件は次のとおりです。

• 1ユニットのおもちゃAには、1ユニットのリソースXと3ユニットのリソースYが必要です。

• 1ユニットのおもちゃBには、1ユニットのリソースXと2ユニットのリソースYが必要です。

5ユニットのリソースXと12ユニットのリソースYがあります。これらのおもちゃの販売による利益率は次のとおりです。

• おもちゃAの販売単位ごとに6インドルピー
• おもちゃBの販売単位ごとに5インドルピー

最大の利益を得るために、各おもちゃを何ユニット生産しますか？

ソリューション

線形計画問題を方程式で表現しましょう。

Z = 6a + 5b

ここで、zは総利益、aは玩具Aユニットの総数、bはBユニットの総数を表します。 私たちの目的は、Z（利益）の値を最大化することです。

さて、あなたの会社はこれらのおもちゃをできるだけ多く生産したいと思うでしょうが、あなたは限られた資源しか持っていません。 リソースの制限は、この問題の制約です。 合計でしかありません

a + b 5

これで、おもちゃAとBのすべてのユニットには、それぞれ3ユニットと2ユニットのリソースYが必要になります。 また、リソースYは合計12ユニットしかないため、数学的には次のようになります。

3a + 2b 12

おもちゃAの単位の値は整数のみであることに注意してください。 これは、a->0およびb<-0の制約もあることを意味します。

これで、適切な線形計画問題が発生しました。 この例に従うことで、他の線形計画問題を定式化できます。 この例は非常に単純ですが、LPの問題は非常に複雑になる可能性があります。

読む：線形計画プロジェクトのアイデアとトピック

線形計画問題を定式化するステップ

線形計画問題を定式化するには、次の手順に従います。

• 決定変数を見つける
• 目的関数を見つける
• 制約を特定する
• 非負の制限を覚えておいてください

問題が上記の基準を満たしている場合、それは線形計画問題です。 問題のタイプを特定する作業を行うときは、この基準を念頭に置くことをお勧めします。

Rを使用した線形計画問題の解決

Rを使用している場合、線形計画問題の解決ははるかに簡単になります。 これは、Rがそのような問題を解決するために特別に設計されたさまざまな機能を備えたlpsolveパッケージを持っているためです。 データサイエンティストとしてLPの問題を解決するために、Rを頻繁に使用する可能性が高くなります。 そのため、実装をよりよく理解するのに役立つ2つの異なる例を共有しました。

例

基本的な問題から始めましょう。 組織には、販売価格が25インドルピーと20インドルピーの2つの製品があり、それぞれ製品AとBと呼ばれます。 毎日、これらの製品を生産するための1800ユニットのリソースがあります。 製品Aには20のリソース単位が必要であり、Bには12のリソース単位が必要です。 これらの製品の両方の生産時間は4分であり、組織は毎日合計8時間の労働時間を取得しています。 問題は、会社の利益を最大化するために、これらの各製品の生産量をどのくらいにする必要があるかということです。

解決：

この問題の解決は、目的関数を定義することから始めます。

max（Sales）= max（25 y 1 + 20 y 2 ）

ここで、25と20はそれぞれ製品AとBの価格であり、y1は生産された製品Aの合計単位であり、y2は生産された製品Bの合計単位です。 決定変数はy1とy2です。

ここで、問題の制約を設定します。

リソースの制約：

20年1 + 12年21800

時間の制約：

4 y 1 + 4 y 2 8 * 60

私たちは、最大の利益を得るために製造しなければならない製品の正しい数を見つけることを目指しています。

Rを使用して問題を解決する：

lpsolveを使用してこのLP問題を解決し、目的関数の設定から始めます。

> require（lpSolve）

必要なパッケージのロード：lpSolve

> Objective.in <-c（25、20）

> Objective.in

[1] 25 20

次に、制約のマトリックスを作成します。

> const <-matrix（c（20、12、4、4）、nrow = 2、byrow = TRUE）

> const

[、1] [、2]

[1、] 20 12

[2、] 4 4

> time_constraints <-（8 * 60）

> resource_constraints <-1800

> time_constraints

[1] 480

> resource_constraints

[1] 1800

次に、定義済みの方程式を作成しましょう。

> rhs <-c（resource_constraints、time_constraints）

> rhs

[1] 1800 480

>方向<-c（“ <=”、“ <=”）

>方向

[1]「<=」「<=」

必要な情報がすべて追加されたら、最適な答えを見つけ始めることができます。 パッケージの構文は次のとおりです。

lp（方向、目的、const.mat、const.dir、const.rhs）

>最適<-lp（direction =” max”、objective.in、const、direction、rhs）

>最適

成功：目的関数は2625です

>要約（最適）

長さクラスモード

方向1-なし-数値

x.count1-なし-数値

目的2-なし-数値

const.count1-なし-数値

制約8-なし-数値

int.count1-なし-数値

int.vec1-なし-数値

bin.count1-なし-数値

binary.vec 1 -none-numeric

num.bin.solns1-なし-数値

objval1-なし-数値

解決策2-なし-数値

presolve1-なし-数値

Compute.sens1-なし-数値

sens.coef.from1-なし-数値

sens.coef.to1-なし-数値

デュアル1-なし-数値

duals.from1-なし-数値

duals.to1-なし-数値

スケール1-なし-数値

use.dense 1 -none-numeric

density.col1-なし-数値

density.val1-なし-数値

density.const.nrow1-なし-数値

density.ctr1-なし-数値

use.rw 1 -none-numeric

tmp1-none-文字

ステータス1-なし-数値

上記のコードを実行すると、問題の望ましい解決策を得ることができます。

y1とy2の最適値：

y1とy2は、私たちが生産しなければならなかった製品Aと製品Bの単位であったことを思い出してください。

>optimal $ solution

[1] 45 75

最適な売上高：

得られたy1とy2の値で生成できる最大の利益は次のとおりです。

>optimal $ objval

[1] 2625

また読む：機械学習のための線形代数

線形計画法の使用

前に述べたように、線形計画法は多くの業界でアプリケーションを見つけます。 これが私たちがそれを使用するいくつかの分野です：

• 配信サービスの人気が高まるにつれ、線形計画法は最適なルートを見つけるための最も好まれる方法の1つになりました。 OlaまたはUberを利用する場合、ソフトウェアは線形計画法を使用して最適なルートを見つけます。 AmazonやFedExのような配達会社も、配達員に最適なルートを決定するためにそれを使用しています。 彼らは配達時間とコストを削減することに焦点を当てています。
• 機械学習の教師あり学習は、線形計画法の基本的な概念に基づいて機能します。 教師あり学習では、提供された入力データに従って出力を予測するための最適な数学モデルを見つける必要があります。
• 小売部門は、棚スペースを最適化するために線形計画法を使用しています。 非常に多くのブランドや製品が利用可能であるため、店舗のどこにそれらを配置するかを決定することは非常に厳しい作業です。 店舗での商品の配置は、その売上に大きな影響を与える可能性があります。 Big Bazaar、Reliance、Walmartなどの主要な小売チェーンは、製品の配置を決定するために線形計画法を使用しています。 彼らは、最大の利益を生み出すために最良の製品配置を確保しながら、消費者の関心を念頭に置く必要があります。
• 企業は線形計画法を使用してサプライチェーンを改善しています。 サプライチェーンの効率は、選択したルート、タイミングなどの多くの要因に依存します。線形計画法を使用することにより、効率を最適化するための最適なルート、タイミング、およびその他のリソースの割り当てを見つけることができます。

線形計画法とデータサイエンスの詳細

線形計画法は、データサイエンスの最も重要な概念の1つです。 また、熟練したデータサイエンティストになるために知っておくべき基本的なトピックでもあります。 すでに説明したように、この概念には多くのアプリケーションがあり、日常生活での使用例を見つけることができます。

データサイエンスとそれに関連する概念について詳しくは、ブログをご覧ください。 私たちはあなたがより多くを学ぶのを助けるために多くの貴重なリソースを持っています。 ここにあなたのさらなる読書のためのいくつかがあります：

• データサイエンティストになる主な理由
• すべてのデータサイエンティストが知っておくべきアルゴリズム
• データサイエンティストになる方法

一方、業界の専門家から学ぶためのデータサイエンスコースを受講することもできます。 ビデオ、クイズ、プロジェクトを通じてインタラクティブに学ぶことができます。 コースを受講すると、プロのデータサイエンティストになるために必要なスキルを学ぶのに役立ちます。 IIIT-BとupGradのデータサイエンスのPGディプロマをチェックしてください。これは、働く専門家向けに作成され、10以上のケーススタディとプロジェクト、実践的なハンズオンワークショップ、業界の専門家とのメンターシップ、業界のメンターとの1対1、400時間以上を提供します。トップ企業との学習と就職支援の