Linear Programming with MATLAB PDF

Chapter 2 Linear Programming with MATLAB Chapter 2 Linear programming (L.P) 2.1. Mathematical definition of L.P Linear programs are constrained optimization models that satisfy three requirements. 1. The decision variables must be continuous; they can take on any value withi...

Chapter 2 Linear Programming with MATLAB Chapter 2 Linear programming (L.P) 2.1. Mathematical definition of L.P Linear programs are constrained optimization models that satisfy three requirements. 1. The decision variables must be continuous; they can take on any value within some restricted range. 2. The objective function must be a linear function. 3. The left-hand sides of the constraints must be linear functions. Thus, linear programs are written in the following form: where the xj values are decision variables and cj, aij , and bi values are constants, called parameters or coefficients, that are given or specified by the problem assumptions. Most linear programs require that all decision variables be nonnegative. 1  Chapter 2 Linear Programming with MATLAB Therefore, we can transform the above linear program into matrix system form as following Min (or Max) 𝑓 𝑇 ∗ 𝑋 subject to 𝐴𝑋 ≤ 𝑏 { 𝐴𝑒𝑞 𝑋 = 𝑏𝑒𝑞 𝑙𝑏 ≤ 𝑋 ≤ 𝑢𝑏 Where 𝑥1 𝑓 𝑇 = (𝑐1 , 𝑐2 , … 𝑐𝑛 ), 𝑋 = ( 𝑥2 ), A is inequality constraint matrix, B is inequality vector, Aeq is ⋮ 𝑥𝑛 equality constraints matrix, Beq is equality vector, lb is lower bounds of X and ub is the upper bounds. Illustration examples: Example1: Optimal cutting The well-posed problem: Let’s assume that GTP (major oil works) company has in stock 2000 piping pieces ( raw materials, feedstock) with their dimensions are all of 5 meters length and 12 inch of diameter ( 2000*5*12’’). All of these pieces have to be cut into two types of pieces denoted by A=2 m and B=1.5 m, in order to manufacture valves (v) that requires 1V=3*A+2*B. Question: Establish a mathematical model (more precisely, statistical model) that expresses the posed problem in order to maximize valves production! Solution:  Step1: Establishing a synoptic diagram of our posed problem (production chain) 2000 Supply, *(5*12’’) (Procurement) Piping transport and pieces logistics Storage Cutting workshop Production factory (All cutting cases) 2  Chapter 2 Linear Programming with MATLAB  Step2: Establishing an organization table (a matrix model) Let’s designate the number of times of first type cutting, second type cutting and third type by variables X1, X2, and X3 respectively, and we denote by X4 the production sum (total production). Therefore, we have the following table: Notation A=2m B=1.5m C={0,1,0.5} X1 2 0 1m X2 0 3 0.5m X3 1 2 0m X4 3 2 / The variable c={0, 1, 0.5} called cutting scraps From the above table, it seems clear that X1 is the optimal solution, which yields indeed a contradiction. Therefore, we need a combinatorial solution between (X1, X2 and X3). The question that arises is as How many times one use of X1, X2 and X3 ?. Step 3: Establishing the mathematical linear programming Constraints 1- Constraints between cutting workshop and production By applying the principle of equilibrium that means: ''supply must be greater than or equal to demand'' then we have 2𝑥 + 1𝑥2 + 0𝑥1 ≥ 3𝑥4 { 1 ↓ ↓ ∑ 𝐴 cut in the ∑ 𝐴 Required for the workshop production 0𝑥 + 3𝑥2 + 2𝑥1 ≥ 2𝑥4 { 1 ↓ ↓ ∑ 𝐵 cut in the ∑ 𝐵 Required for the workshop production 3  Chapter 2 Linear Programming with MATLAB 2- Exhaustion stock constraint (all pieces must be cut) 𝑥1 + 𝑥2 + 𝑥3 = 2000 Objective function The objective is to minimize the piping scraps that means equivalent to maximize the production Max (the production)⟹ 𝑚𝑎𝑥(𝑥4 ) Finally, the linear programming is given as following 𝑚𝑎𝑥(𝑥4 ) Subject to 2𝑥1 + 1𝑥2 + 0𝑥1 ≥ 3𝑥4 0𝑥1 + 3𝑥2 + 2𝑥1 ≥ 2𝑥4 { 𝑥1 + 𝑥2 + 𝑥3 = 2000 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 2.2. Programming method by using MATLAB 2.2.1. Simple case (without optimization) Example: 𝟓𝒙 + 𝟐𝒚 + 𝟕𝒛 = 𝟐 { 𝟐𝒙 + 𝒚 − 𝟑𝒙 = 𝟕 𝒙 + 𝟐𝒚 + 𝒛 = 𝟒 The above system admits a unique solution because its matrix is invertible. The program Method 1: using direct method ( command window) Method 1.1: using invertible matrix method 1.2: using diagonalization 4  Chapter 2 Linear Programming with MATLAB Method 2. Using algorithm Gauss ( scrip program) 5  Chapter 2 Linear Programming with MATLAB 2.2.2. Linear Programming with Optimization  The general form ( for MATLAB) max⁡(⁡𝑜𝑟 min)⁡∑ f T ∗ X Subject to constraints 𝐴𝑋 ≤ 𝑏 … … 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑒𝑑⁡𝑖𝑛𝑒𝑞𝑢𝑎𝑙𝑖𝑡𝑦 { 𝐴𝑒𝑞 = 𝑏𝑒𝑞 … …. 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑒𝑑⁡𝑒𝑞𝑢𝑎𝑙𝑖𝑡𝑦 𝑙𝑏 ≤ 𝑋 ≤ 𝑢𝑏 … … 𝑏𝑜𝑢𝑛𝑑⁡𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠⁡𝑜𝑛⁡𝑡ℎ𝑒⁡𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛⁡𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠 Numerical example 1  Posed problem: A production company produces two types of products (P1 and P2) using three different types of raw materials (m1, m2 and m3), with the following distribution: P1 P2 Availability in stock M1 2 1 800 M2 1 2 700 M3 0 1 300 6  Chapter 2 Linear Programming with MATLAB Question: Establish an optimal production plan knowing that the unit prices of production are respectively: 4 thousand DA and 5 thousand DA.  Modelization Here, we seek to maximize the total cost (maximize the profit) We denote P1 by x1 and P2 by x2 max⁡(4𝑥1 + 5𝑥2 ) 𝑠𝑢𝑏𝑗𝑒𝑐𝑡⁡𝑡𝑜 2𝑥1 + 𝑥2 ≤ 800 𝑥1 + 𝑥2 ≤ 700 𝑥2 ≤ 300 { 𝑥1 , 𝑥2 , 𝑥3 ≥ 0  MATLAB programming( in command window: with linprog function) Remark: the linprog command is programmed only by a min objective. For this purpose, to maximize it is enough to change the sign. Numerical example 2:  Posed problem: A valve manufacturing company has in stock a quantity of 500 pieces of piping measuring (5mx12''). These must be cut into two types of pieces denoted by A=2m and B=1.5m, to manufacture valves which require 3 units of A and 2 units of B. Question: establish an optimal cutting plan.  Modelization - Here, we seek to minimize the falls (the faults) which is equivalent with to maximizing the production. - We denote by x1, X2 and X3 the numbers of cutting according to cases N°1, N°2 and N°3 respectively. - Finally, we obtain the following plan: 7  Chapter 2 Linear Programming with MATLAB Cutting case denoted A=2m B=1.5m C={0, 0.5, 1}m N°1 X1 2 0 1 N°2 X2 0 3 0.5 N°3 X3 1 2 0 Production X4 3 2 From the above table, we can establish the following mathematical model: max⁡(𝑥4 ) max⁡(𝑥4 ) 𝑠𝑢𝑏𝑗𝑒𝑐𝑡⁡𝑡𝑜 𝑠𝑢𝑏𝑗𝑒𝑐𝑡⁡𝑡𝑜 2𝑥1 + 0. 𝑥2 + 1. 𝑥3 ≥ 3𝑥4 −2𝑥1 − 0. 𝑥2 − 1. 𝑥3 + 3𝑥4 ≤ 0 ⟺ 0𝑥1 + 3. 𝑥2 + 2. 𝑥3 ≥ 2𝑥4 −0𝑥1 − 3. 𝑥2 − 2. 𝑥3 + 2𝑥4 ≤ 0 𝑥1 + 𝑥2 + 𝑥3 = 500 +𝑥1 + 𝑥2 + 𝑥3 = 500 { 𝑋≥0 𝑋≥0  MATLAB programming Remark: here, we have used the integer function (intlinprog), because the variables are integers. Finally, we will produce 166 products with this optimal solution. 8  Chapter 2 Linear Programming with MATLAB 2.3. Hydrocarbon transport programming  What is transportation problem? It is a linear program, which can be described as follows: We assume on the one hand a set of producers (or warehouse or something like suppliers (providers) and on the other hand a set of consumers (or customers), as indicated in the figure below 𝑥11 The objective is to minimize the total transport cost while respecting demand constraints and production capacities. Then the model can be defined as follows: 𝑁 𝑀 min ∑ ∑ 𝐶𝑖𝑗 𝑥𝑖𝑗 𝑥𝑖𝑗 𝑖=1 𝑗=1 Subject to 𝑀 ∑ 𝑥𝑖𝑗 ≤ 𝑝𝑖⁡⁡ ⁡𝑓𝑜𝑟⁡𝑒𝑎𝑐ℎ⁡𝑖 = 1, … 𝑁,⁡⁡⁡⁡constraints⁡on⁡production⁡capacity⁡ 𝑗=1 𝑁 ∑ 𝑥𝑖𝑗 ≥ 𝑑𝑗⁡⁡ ⁡𝑓𝑜𝑟⁡𝑒𝑎𝑐ℎ⁡𝑗 = 1, … 𝑁,⁡⁡⁡𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠⁡𝑜𝑛⁡𝑠𝑎𝑡𝑖𝑠𝑓𝑦𝑖𝑛𝑔⁡𝑑𝑒𝑚𝑎𝑛𝑑⁡ 𝑖=1 𝑥𝑖𝑗 ≥ 0 Numerical application for Hydrocarbon transport: We apply the transport model in hydrocarbon transport (in the collection network). We set the number of producers N=2 (here it concerns the wells) and the number of suppliers M=3 (here it concerns the treatment center). min 𝑓 𝑇 𝑋 ⟺ min(1⁡2⁡3⁡2⁡4⁡1) ∗ 𝑋 𝑋 𝑋 Subject to 9  Chapter 2 Linear Programming with MATLAB 𝑥11 1 1 1 0 0 0 900 𝑥12 0 0 0 1 1 1 800 𝑥13 −1 0 0 −1 0 0⁡ ≤ −500 0 −1 0 𝑥21 0 −1 0 −600 (0 0 −1 0 0 −1 ) (𝑥22) (−300) 𝑥23  Matlab programming ( first method) 10