Difference between revisions of "Scilab---FOSSEE-Optimisation-Toolbox/C2/Linear-Programming-using-linprog-function/English"

From Script | Spoken-Tutorial
Jump to: navigation, search
Line 23: Line 23:
 
In this tutorial, we will learn how to:
 
In this tutorial, we will learn how to:
  
−
<ul>
+
*Solve '''linear programming''' problems using '''fot underscore linprog function''' in '''Scilab'''.
−
<li><blockquote><p>Solve '''linear programming''' problems using '''fot underscore linprog''' function in Scilab.</p></blockquote></li>
+
*Use '''fot underscore linprog function''' of '''FOSSEE Optimization Toolbox.'''
−
<li><blockquote><p>Use '''fot underscore linprog''' function of '''FOSSEE Optimization Toolbox.'''</p></blockquote></li></ul>
+
 
|-
 
|-
 
|
 
|
Line 34: Line 33:
 
To record this tutorial, I am using
 
To record this tutorial, I am using
  
−
<ul>
+
*'''Ubuntu 18.04'''
−
<li><blockquote><p>'''Ubuntu 18.04'''</p></blockquote></li>
+
*'''Scilab 6.1.0''' and
−
<li><blockquote><p>'''Scilab 6.1.0''' and</p></blockquote></li>
+
*'''FOSSEE Optimization Toolbox''' version 0.4.1.
−
<li><blockquote><p>'''FOSSEE Optimization Toolbox''' version '''0.4.1'''</p></blockquote></li></ul>
+
 
|-
 
|-
 
|
 
|
Line 48: Line 46:
 
To follow this tutorial, you should
 
To follow this tutorial, you should
  
−
<ul>
+
*Install '''FOSSEE Optimization Toolbox''' version '''0.4.1''' or above
−
<li><blockquote><p>Install '''FOSSEE Optimization Toolbox''' version '''0.4.1''' or above</p></blockquote></li>
+
*Have basic understanding of '''Scilab''' and optimization theory
−
<li><blockquote><p>Have basic understanding of '''Scilab''' and optimization theory</p></blockquote></li>
+
*If not, for relevant tutorials please visit this site.
−
<li><blockquote><p>If not, for relevant tutorials please visit this site.</p></blockquote></li></ul>
+
 
|-
 
|-
 
|
 
|
Line 58: Line 55:
 
'''Code Files'''
 
'''Code Files'''
 
|
 
|
−
<ul>
+
*The files used in this tutorial have been provided in the '''Code files''' link.
−
<li><blockquote><p>The files used in this tutorial have been provided in the '''Code files''' link.</p></blockquote></li>
+
*Please download and extract the files.
−
<li><blockquote><p>Please download and extract the files.</p></blockquote></li>
+
*Make a copy and then use them while practising.
−
<li><blockquote><p>Make a copy and then use them while practising.</p></blockquote></li></ul>
+
 
|-
 
|-
 
|
 
|
 
Show Slide
 
Show Slide
  
−
'''What is Linear Programming ?'''
+
'''What is Linear Programming?'''
−
|
+
|'''What is Linear Programming?'''
−
A '''function''' is '''linear,''' if it has a degree of one or zero.
+
*A '''function''' is '''linear,''' if it has a degree of one or zero.
−
 
+
*A '''linear program''' is a mathematical '''optimization model''' with:
−
A '''linear program''' is a mathematical '''optimization''' model with:
+
**'''Linear objective function'''
−
 
+
**'''Linear constraints'''
−
<ul>
+
−
<li><blockquote><p>'''Linear''' objective function</p></blockquote></li>
+
−
<li><blockquote><p>'''Linear''' constraints</p></blockquote></li></ul>
+
 
|-
 
|-
 
|
 
|
Line 80: Line 73:
  
 
'''Mathematical Formulation'''
 
'''Mathematical Formulation'''
−
| A '''general form''' of the '''Linear Program''' is as shown.
+
| A general form of the '''Linear Program''' is as shown.
 
|-
 
|-
 
|
 
|
Line 91: Line 84:
 
In this example, we will learn how to:
 
In this example, we will learn how to:
  
−
<ul>
+
*Minimize the given '''function''' subject to these given constraints and bounds.
−
<li><blockquote><p>Minimize the given function subject to these given constraints and bounds.</p></blockquote></li></ul>
+
  
−
Note that the '''objective function''' and '''constraints''' are '''linear'''.
+
Note that the '''objective function''' and constraints are '''linear'''.
 
|-
 
|-
 
|
 
|
Line 100: Line 92:
  
 
'''Example'''
 
'''Example'''
−
| I have downloaded the opt_linprog.sce file to my '''Downloads''' folder.
+
| I have downloaded the '''opt_linprog.sce''' file to my '''Downloads''' folder.
 
|-
 
|-
 
| Cursor on the Scilab console.
 
| Cursor on the Scilab console.
Line 112: Line 104:
 
|-
 
|-
 
|
 
|
−
Click on Open button &gt;&gt; locate the file '''opt_linprog.sce'''.
+
Click on Open button >> locate the file '''opt_linprog.sce'''.
  
 
Click on the Ok button
 
Click on the Ok button
 
|
 
|
−
Click on the '''Open''' button on the tool-bar and locate the file '''opt_linprog.sce'''.
+
Click on the '''Open''' button on the '''toolbar''' and locate the file '''opt_linprog.sce'''.
  
 
Then click the '''Ok''' button.
 
Then click the '''Ok''' button.
Line 123: Line 115:
 
|-
 
|-
 
| Show '''opt_linprog.sce''' in scilab editor.
 
| Show '''opt_linprog.sce''' in scilab editor.
−
| Now we will see the input arguments for '''fot underscore linprog'''.
+
| Now we will see the '''input arguments''' for '''fot underscore linprog'''.
 
|-
 
|-
 
| Highlight the line with '''‘c’'''
 
| Highlight the line with '''‘c’'''
−
| '''''c''''' is a '''vector''' of '''coefficients''' in the '''objective function'''
+
| '''''c''''' is a '''vector''' of '''coefficients''' in the '''objective function'''.
 
|-
 
|-
 
| Highlight the line with '''‘A’'''
 
| Highlight the line with '''‘A’'''
−
|
+
|'''''A''''' is a '''matrix''' of '''coefficients''' of '''inequality''' constraints.
−
'''''A''''' is a '''matrix''' of '''coefficients''' of
+
−
 
+
−
'''inequality''' constraints
+
 
|-
 
|-
 
| Highlight the line with '''‘b’'''
 
| Highlight the line with '''‘b’'''
−
|
+
|'''''b''''' is a '''vector''' of the right-hand side of '''inequality''' constraints.
−
'''''b''''' is a '''vector''' of the right-hand side
+
−
 
+
−
of '''inequality constraints'''
+
 
|-
 
|-
 
| Highlight the line with '''‘Aeq’'''
 
| Highlight the line with '''‘Aeq’'''
−
| '''''‘Aeq’''''' is a '''matrix''' of '''coefficients''' of '''equality constraints'''
+
| '''''‘Aeq’''''' is a '''matrix''' of '''coefficients''' of '''equality''' constraints.
 
|-
 
|-
 
| Highlight the line with '''‘beq’'''
 
| Highlight the line with '''‘beq’'''
−
| '''''‘beq’''''' is a '''vector''' of the right-hand side of '''equality constraints'''
+
| '''''‘beq’''''' is a '''vector''' of the right-hand side of '''equality''' constraints.
 
|-
 
|-
 
| Highlight the line with '''‘lb’'''
 
| Highlight the line with '''‘lb’'''
−
| '''''‘lb’''''' is a vector of lower bounds on '''''x'''''
+
| '''''‘lb’''''' is a '''vector''' of lower bounds on '''''x'''''.
 
|-
 
|-
 
| Highlight the line with '''‘ub’'''
 
| Highlight the line with '''‘ub’'''
−
| '''''‘ub’''''' is a vector of '''upper bounds''' on '''''x'''''.
+
| '''''‘ub’''''' is a '''vector''' of '''upper bounds''' on '''''x'''''.
 
|-
 
|-
 
|
 
|
  
−
|
+
|Now we will summarize the '''output arguments'''.
−
Now we will summarize the output arguments
+
  
−
Output arguments are '''''xopt,''''' '''''fopt,''''' '''''exitflag, output,''''' '''lambda'''
+
'''Output arguments''' are '''''xopt, fopt, exitflag, output,''''' '''lambda'''
 
|-
 
|-
 
| Highlight '''‘xopt’'''
 
| Highlight '''‘xopt’'''
Line 163: Line 148:
 
|-
 
|-
 
| Highlight '''‘fopt’'''
 
| Highlight '''‘fopt’'''
−
| '''''fopt''''' is the optimal objective function value'''.'''
+
| '''''fopt''''' is the optimal '''objective function''' value.
 
|-
 
|-
 
| Highlight '''‘exitflag’'''
 
| Highlight '''‘exitflag’'''
−
| '''''exitflag''''' denotes the status of execution
+
| '''''exitflag''''' denotes the status of '''execution'''.
 
|-
 
|-
 
| Highlight '''‘output’'''
 
| Highlight '''‘output’'''
−
| '''''Output''' is a'' '''structure''' containing detailed information about the optimization.
+
| '''''Output''' is a'' '''structure''' containing detailed information about the '''optimization'''.
 
|-
 
|-
 
| Highlight '''‘lambda’'''
 
| Highlight '''‘lambda’'''
−
| '''Lambda''' is a '''structure''' containing '''Lagrange multipliers''' at the optimal solution'''.'''
+
| '''Lambda''' is a '''structure''' containing '''Lagrange multipliers''' at the optimal solution.
 
|-
 
|-
 
| Highlight the line calling ‘'''fot_linprog’'''
 
| Highlight the line calling ‘'''fot_linprog’'''
−
| We will use the '''fot underscore linprog''' function to solve the example
+
| We will use the '''fot underscore linprog function''' to solve the example.
 
|-
 
|-
 
|
 
|
 
Press '''CTRL + S'''
 
Press '''CTRL + S'''
  
−
*
+
Click on the '''Execute''' button on scilab.
  
−
Click on the Execute button on scilab.
+
Select '''File with Echo''' from the drop-down.
  
−
Select file with echo from the drop-down.
+
|Save the file by pressing '''Control''' and '''‘S’''' keys simultaneously.
−
 
+
−
Video-editor: Pls put a textbox on screen.&quot;Clear console&quot; window opens to ask are you sure you want to clear the console? - click on the yes button
+
−
|
+
−
Save the file by pressing '''Control''' and '''‘S’''' keys simultaneously.
+
  
 
To '''run''' the file, click on the '''Execute''' menu.
 
To '''run''' the file, click on the '''Execute''' menu.
  
−
Then click on '''file with echo''' from the drop down.
+
Then click on '''File with Echo''' from the dropdown.
 
|-
 
|-
 
|
 
|
Line 208: Line 189:
  
 
Highlight '''‘lambda''' values'''’'''
 
Highlight '''‘lambda''' values'''’'''
−
|
+
|Switch to the '''Scilab console''' to see the '''output'''.
−
Switch to the '''Scilab console''' to see the output.
+
  
−
Optimal solutions for the following are displayed on the '''Scilab console'''.
+
'''Optimal solutions''' for the following are displayed on the '''Scilab console'''.
  
 
'''xopt''' values
 
'''xopt''' values
Line 227: Line 207:
  
 
'''Alternate Input Arguments'''
 
'''Alternate Input Arguments'''
−
| Now we see an alternate way of passing '''input''' arguments to '''fot underscore linprog.'''
+
| Now we see an alternate way of '''pass'''ing '''input arguments''' to '''fot underscore linprog.'''
 
|-
 
|-
 
|
 
|
Line 240: Line 220:
 
'''file''' is a '''string''' stating the path of the '''mps file'''.
 
'''file''' is a '''string''' stating the path of the '''mps file'''.
  
−
'''MPS''' (Mathematical Programming System) is a file format.
+
'''MPS (Mathematical Programming System)''' is a file format.
 
|-
 
|-
 
|
 
|
Line 251: Line 231:
 
It is used to present and archive:
 
It is used to present and archive:
  
−
<ul>
+
*'''linear programming''' problems and
−
<li><blockquote><p>linear programming problems and</p></blockquote></li>
+
*'''mixed integer programming''' problems
−
<li><blockquote><p>mixed integer programming problems</p></blockquote></li></ul>
+
  
−
'''param''' is a list containing parameters to be set.
+
'''param''' is a list containing '''parameters''' to be '''set'''.
 
|-
 
|-
 
|
 
|
Line 264: Line 243:
 
The problem we just saw was directly solvable using '''fot underscore linprog. '''
 
The problem we just saw was directly solvable using '''fot underscore linprog. '''
  
−
<ul>
+
*There are cases when the '''optimal value''' is unbounded.
−
<li><blockquote><p>There are cases when the optimal value is unbounded.</p></blockquote></li>
+
*The minimum value may go to '''negative infinity''' in the absence of suitable '''constraints'''.
−
<li><blockquote><p>The minimum value may go to negative infinity in the absence of suitable constraints.</p></blockquote></li></ul>
+
 
|-
 
|-
 
|
 
|
Line 272: Line 250:
  
 
'''Unbounded Problems II'''
 
'''Unbounded Problems II'''
−
|
+
|Such problems are called '''Unbounded''' problems.
−
<ul>
+
−
<li><blockquote><p>Such problems are called Unbounded Problems.</p></blockquote></li></ul>
+
 
|-
 
|-
 
|
 
|
Line 281: Line 257:
 
'''Infeasible Problems'''
 
'''Infeasible Problems'''
 
|
 
|
−
<ul>
+
*There are instances where no solution exists for all the constraints.
−
<li><blockquote><p>There are instances where no solution exists for all the constraints</p></blockquote></li>
+
*These problems are called '''Infeasible''' problems.
−
<li><blockquote><p>These problems are called '''Infeasible Problems'''.</p></blockquote></li></ul>
+
  
 
We will see an example of these
 
We will see an example of these
  
−
constraints on Scilab.
+
constraints on '''Scilab'''.
 
|-
 
|-
 
|
 
|
Line 298: Line 273:
 
Select '''File with Echo''' option
 
Select '''File with Echo''' option
 
|
 
|
−
We will now change the previous problem
+
We will now change the previous problem to make it '''infeasible'''.
−
 
+
−
to make it '''infeasible'''.
+
  
−
<ul>
+
*Locate the line that defines '''ub'''
−
<li><blockquote><p>Locate the line that defines '''ub'''</p></blockquote></li>
+
*Change the second element of '''ub''' to 0
−
<li><blockquote><p>Change the second element of '''ub''' to 0.</p></blockquote></li>
+
*Click on the '''Execute''' menu,
−
<li><blockquote><p>Click on the '''Execute''' menu,</p></blockquote></li>
+
*Click on '''File with Echo''' from the drop down
−
<li><blockquote><p>Click on '''File with Echo''' from the drop down</p></blockquote></li></ul>
+
  
−
This will execute the '''scilab code.'''
+
This will execute the '''Scilab code.'''
 
|-
 
|-
 
|
 
|
Line 315: Line 287:
 
Highlight the message '''Primal Infeasible'''
 
Highlight the message '''Primal Infeasible'''
 
|
 
|
−
Switch to the Scilab console to see the output.
+
Switch to the '''Scilab console''' to see the '''output'''.
  
 
The '''console''' shows that the problem is '''Primal Infeasible.'''
 
The '''console''' shows that the problem is '''Primal Infeasible.'''
Line 330: Line 302:
 
In this tutorial, we have learnt how to:
 
In this tutorial, we have learnt how to:
  
−
<ul>
+
*Use '''fot underscore linprog''' function of the '''FOSSEE Optimization Toolbox'''.
−
<li><blockquote><p>Use '''fot underscore linprog''' function of the '''FOSSEE Optimization Toolbox'''.</p></blockquote></li>
+
*Solve an '''LP''' example using '''fot underscore linprog''' in '''Scilab'''.
−
<li><blockquote><p>Solve an '''LP''' example using '''fot underscore linprog''' in '''Scilab'''.</p></blockquote></li></ul>
+
 
|-
 
|-
 
|
 
|
Line 343: Line 314:
 
As an assignment:
 
As an assignment:
  
−
<ul>
+
*Solve the same example that we '''executed''', with this additional constraint.
−
<li><blockquote><p>Solve the same example that we executed, with this additional constraint.</p></blockquote></li>
+
*The optimal value will be -0.5714 and optimal solution will be 0.2857 and 0.8571
−
<li><blockquote><p>The optimal value will be -0.5714 and optimal solution will be 0.2857 and 0.8571</p></blockquote></li>
+
*These are the optimal values of '''x1''' and '''x2'''
−
<li><blockquote><p>These are the optimal values of '''x1''' and '''x2'''</p></blockquote></li></ul>
+
 
|-
 
|-
 
|
 
|
Line 399: Line 369:
  
 
'''Acknowledgment'''
 
'''Acknowledgment'''
−
| '''Spoken Tutoria'''l and FOSSEE projects are funded by '''MoE, the Government of India'''.
+
| '''Spoken Tutorial''' and '''FOSSEE projects''' are funded by '''MoE, the Government of India'''.
 
|-
 
|-
 
|
 
|

Revision as of 18:53, 1 November 2021

Title of script: Linear Programming using fot_linprog function

Author: Rupak Rokade, Siddharth Agarwal, Georgey John and Mankrit Singh

Keywords:Scilab console, FOSSEE Optimization Toolbox, Linear Programming, OR, Operations Research, fot_linprog, constraints, input, output, video tutorial.


Visual Cue Narration

Show Slide

Title Slide

Hello and welcome to the spoken tutorial on “Linear Programming using fot underscore linprog function”.

Show Slide

Learning Objectives

In this tutorial, we will learn how to:

  • Solve linear programming problems using fot underscore linprog function in Scilab.
  • Use fot underscore linprog function of FOSSEE Optimization Toolbox.

Show Slide

System requirement

To record this tutorial, I am using

  • Ubuntu 18.04
  • Scilab 6.1.0 and
  • FOSSEE Optimization Toolbox version 0.4.1.

Show Slide

Pre-requisites

https://spoken-tutorial.org

To follow this tutorial, you should

  • Install FOSSEE Optimization Toolbox version 0.4.1 or above
  • Have basic understanding of Scilab and optimization theory
  • If not, for relevant tutorials please visit this site.

Show Slide

Code Files

  • The files used in this tutorial have been provided in the Code files link.
  • Please download and extract the files.
  • Make a copy and then use them while practising.

Show Slide

What is Linear Programming?

What is Linear Programming?
  • A function is linear, if it has a degree of one or zero.
  • A linear program is a mathematical optimization model with:
    • Linear objective function
    • Linear constraints

Show Slide

Mathematical Formulation

A general form of the Linear Program is as shown.

Show Slide

Example

We will now solve this example to illustrate the use of fot underscore linprog.

In this example, we will learn how to:

  • Minimize the given function subject to these given constraints and bounds.

Note that the objective function and constraints are linear.

Show Slide

Example

I have downloaded the opt_linprog.sce file to my Downloads folder.
Cursor on the Scilab console. I have opened the Scilab console.
Type editor >> press Enter.

In the Scilab console, type editor and press Enter.

Editor window opens.

Click on Open button >> locate the file opt_linprog.sce.

Click on the Ok button

Click on the Open button on the toolbar and locate the file opt_linprog.sce.

Then click the Ok button.

opt_linprog.sce file opens in the editor.

Show opt_linprog.sce in scilab editor. Now we will see the input arguments for fot underscore linprog.
Highlight the line with ‘c’ c is a vector of coefficients in the objective function.
Highlight the line with ‘A’ A is a matrix of coefficients of inequality constraints.
Highlight the line with ‘b’ b is a vector of the right-hand side of inequality constraints.
Highlight the line with ‘Aeq’ ‘Aeq’ is a matrix of coefficients of equality constraints.
Highlight the line with ‘beq’ ‘beq’ is a vector of the right-hand side of equality constraints.
Highlight the line with ‘lb’ ‘lb’ is a vector of lower bounds on x.
Highlight the line with ‘ub’ ‘ub’ is a vector of upper bounds on x.
Now we will summarize the output arguments.

Output arguments are xopt, fopt, exitflag, output, lambda

Highlight ‘xopt’ xopt is the optimal value of x.
Highlight ‘fopt’ fopt is the optimal objective function value.
Highlight ‘exitflag’ exitflag denotes the status of execution.
Highlight ‘output’ Output is a structure containing detailed information about the optimization.
Highlight ‘lambda’ Lambda is a structure containing Lagrange multipliers at the optimal solution.
Highlight the line calling ‘fot_linprog’ We will use the fot underscore linprog function to solve the example.

Press CTRL + S

Click on the Execute button on scilab.

Select File with Echo from the drop-down.

Save the file by pressing Control and ‘S’ keys simultaneously.

To run the file, click on the Execute menu.

Then click on File with Echo from the dropdown.

Change the window to Scilab console

Highlight Optimal solution

Highlight ‘xopt values’

Highlight ‘fopt value’

Highlight ‘exitflag value’

Highlight ‘output values’

Highlight ‘lambda values’

Switch to the Scilab console to see the output.

Optimal solutions for the following are displayed on the Scilab console.

xopt values

fopt value

exitflag

output and

lambda.

Show Slide

Alternate Input Arguments

Now we see an alternate way of passing input arguments to fot underscore linprog.

Show Slide

Alternate Input Arguments

Highlight ‘file’

Highlight ‘MPS’

file is a string stating the path of the mps file.

MPS (Mathematical Programming System) is a file format.

Show Slide

Alternate Input Arguments

Highlight ‘param’

It is used to present and archive:

  • linear programming problems and
  • mixed integer programming problems

param is a list containing parameters to be set.

Show Slide

Unbounded Problems I

The problem we just saw was directly solvable using fot underscore linprog.

  • There are cases when the optimal value is unbounded.
  • The minimum value may go to negative infinity in the absence of suitable constraints.

Show Slide

Unbounded Problems II

Such problems are called Unbounded problems.

Show Slide

Infeasible Problems

  • There are instances where no solution exists for all the constraints.
  • These problems are called Infeasible problems.

We will see an example of these

constraints on Scilab.

Switch to the scilab editor.

Replace the value.

Click on the Execute menu

Select File with Echo option

We will now change the previous problem to make it infeasible.

  • Locate the line that defines ub
  • Change the second element of ub to 0
  • Click on the Execute menu,
  • Click on File with Echo from the drop down

This will execute the Scilab code.

Switch to the Scilab Console

Highlight the message Primal Infeasible

Switch to the Scilab console to see the output.

The console shows that the problem is Primal Infeasible.

Show Slide

Summary

This brings us to the end of this tutorial.

Let us summarise.

In this tutorial, we have learnt how to:

  • Use fot underscore linprog function of the FOSSEE Optimization Toolbox.
  • Solve an LP example using fot underscore linprog in Scilab.

Show Slide

Assignment

Highlight the constraint

As an assignment:

  • Solve the same example that we executed, with this additional constraint.
  • The optimal value will be -0.5714 and optimal solution will be 0.2857 and 0.8571
  • These are the optimal values of x1 and x2

Show Slide

About Spoken Tutorial Project

The video at the following link summarises the Spoken Tutorial project.

Please download and watch it.

Show Slide

Spoken Tutorial Workshops

The Spoken Tutorial Project Team conducts workshops and gives certificates.

For more details, please write to us

Show Slide

Answers for THIS Spoken Tutorial

Please post your timed queries in this forum.
Show Slide: FOSSEE Forum Please post your general and technical queries on Scilab in this forum.

Show Slide

Textbook Companion project

The FOSSEE team coordinates the Textbook Companion project.

We give Certificates and Honorarium to the contributors.

For more details, please visit this site..

Show Slide

Lab Migration

The FOSSEE team coordinates the Lab Migration project.

For more details, please visit this site.

Show Slide

Acknowledgment

Spoken Tutorial and FOSSEE projects are funded by MoE, the Government of India.

Show Slide

Thank you

This is Mankrit Singh, a FOSSEE intern 2021, IIT Bombay signing off

Thanks for joining.

Contributors and Content Editors

Mankrits, Nancyvarkey

Retrieved from "https://script.spoken-tutorial.org/index.php?title=Scilab---FOSSEE-Optimisation-Toolbox/C2/Linear-Programming-using-linprog-function/English&oldid=55668"