Introductory guide on Linear Programming for (aspiring) data scientists 1

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

本帖隐藏的内容

Introduction

Optimization is the way of life. We all have finite resources and time and we want to make the most of them. From using your time productively to solving supply chain problems for your company – every thing uses optimization.

It is also a very interesting topic – it starts with simple problems, but can get very complex. For example, sharing a chocolate between siblings is a simple optimization problem. We don’t think in mathematical term while solving it. On the other hand devising inventory and warehousing strategy for an e-tailer can be very complex. Millions of SKUs with different popularity in different regions to be delivered in defined time and resources – you see what I mean!

Linear programming (LP) is one of the simplest ways to perform optimization. It helps you solve some very complex optimization problems by making a few simplifying assumptions. As an analyst you are bound to come across applications and problems to be solved by Linear Programming.

For some reason, LP doesn’t get as much attention as it deserves while learning data science. So, I thought let me do justice to this awesome technique. I decided to write an article which explains Linear programming in simple English. I have kept the content as simple as possible. The idea is to get you started and excited about Linear Programming.

Table of Content

• What is Linear Programming?
  • Basic Terminologies
  • Process to define a LP problem
    
• Solve Linear Program by Graphical Method
• Solve Linear Program using OpenSolver
• Simplex Method
• Northwest Corner Method and Least Cost Method
• Applications of Linear programming
  

1.What is Linear Programming?

Now, what is linear programming? Linear programming is a simple technique where we depict complex relationships through linear functions and then find the optimum points. The important word in previous sentence is depict. The real relationships might be much more complex – but we can simplify them to linear relationships.

Applications of linear programming are every where around you. You use linear programming at personal and professional fronts. You are using linear programming when you are driving from home to work and want to take the shortest route. Or when you have a project delivery you make strategies to make your team work efficiently for on time delivery.

Example of a linear programming problem

Let’s say a FedEx delivery man has 6 packages to deliver in a day. The warehouse is located at point A. The 6 delivery destinations are given by U, V, W, X, Y and Z. The numbers on the lines indicate the distance between the cities. To save on fuel and time the delivery person wants to take the shortest route.

So, the delivery person will calculate different routes for going to all the 6 destinations and then come up with the shortest route. This technique of choosing the shortest route is called linear programming.

In this case, the objective of the delivery person is to deliver the parcel on time at all 6 destinations. The process of choosing the best route is called Operation Research. Operation research is an approach to decision-making, which involves a set of methods to operate a system. In the above example, my system was the Delivery model.

Linear programming is used for obtaining the most optimal solution for a problem with given constraints. In linear programming, we formulate our real life problem into a mathematical model. It involves an objective function, linear inequalities with subject to constraints.

Is the linear representation of the 6 points above representative of real world? Yes and No. It is oversimplification as the real route would not be a straight line. It would likely have multiple turns, U turns, signals and traffic jams. But with a simple assumption, we have reduced the complexity of the problem drastically and are creating a solution which should work in most scenarios.

Formulating a problem – Let’s manufacture some chocolates

Example: Consider a chocolate manufacturing company which produces only two types of chocolate – A and B. Both the chocolates require Milk and Choco only.  To manufacture each unit of A and B, following quantities are required:

• Each unit of A requires 1 unit of Milk and 3 units of Choco
• Each unit of B requires 1 unit of Milk and 2 units of Choco
  

The company kitchen has a total of 5 units of Milk and 12 units of Choco. On each sale, the company makes a profit of

• Rs 6 per unit A sold
• Rs 5 per unit B sold.
  

Now, the company wishes to maximize its profit. How many units of A and B should it produce respectively?

Solution: The first thing I’m gonna do is represent the problem in a tabular form for better understanding.

	Milk	Choco	Profit per unit
A	1	3	Rs 6
B	1	2	Rs 5
Total	5	12

Let the total number of units produced of A be = X

Let the total number of units produced of B be = Y

Now, the total profit is represented by Z

The total profit the company makes is given by the total number of units of A and B produced multiplied by its per unit profit Rs 6 and Rs 5 respectively.

Profit: Max Z = 6X+5Y

which means we have to maximize Z.

The company will try to produce as many units of A and B to maximize the profit. But the resources Milk and Choco are available in limited amount.

As per the above table, each unit of A and B requires 1 unit of Milk. The total amount of Milk available is 5 units. To represent this mathematically,

X+Y ≤ 5

Also, each unit of A and B requires 3 units & 2 units of Choco respectively. The total amount of Choco available is 12 units. To represent this mathematically,

3X+2Y ≤ 12

Also, the values for units of A can only be integers.

So we have two more constraints, X ≥ 0  &  Y ≥ 0

For the company to make maximum profit, the above inequalities have to be satisfied.

This is called formulating a real-world problem into a mathematical model.

Common terminologies used in Linear Programming

Let us define some terminologies used in Linear Programming using the above example.

• Decision Variables: The decision variables are the variables which will decide my output. They represent my ultimate solution. To solve any problem, we first need to identify the decision variables. For the above example, the total number of units for A and B denoted by X & Y respectively are my decision variables.
• Objective Function: It is defined as the objective of making decisions. In the above example, the company wishes to increase the total profit represented by Z. So, profit is my objective function.
• Constraints: The constraints are the restrictions or limitations on the decision variables. They usually limit the value of the decision variables. In the above example, the limit on the availability of resources Milk and Choco are my constraints.
• Non-negativity restriction: For all linear programs, the decision variables should always take non-negative values. Which means the values for decision variables should be greater than or equal to 0.
  

Process to formulate a Linear Programming problem

Let us look at the steps of defining a Linear Programming problem generically:

• Identify the decision variables
• Write the objective function
• Mention the constraints
• Explicitly state the non-negativity restriction
  

For a problem to be a linear programming problem, the decision variables, objective function and constraints all have to be linear functions.

If the all the three conditions are satisfied, it is called a Linear Programming Problem.

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Introductory Programming Scientists Scientist Aspirin

谢谢分享

谢谢楼主分享！

thanks.