{"id":14464,"date":"2024-02-04T12:36:01","date_gmt":"2024-02-04T09:36:01","guid":{"rendered":"https:\/\/old.masarat-sy.org\/?p=14464"},"modified":"2024-02-10T13:30:28","modified_gmt":"2024-02-10T10:30:28","slug":"simplex-method","status":"publish","type":"post","link":"https:\/\/old.masarat-sy.org\/en\/simplex-method\/","title":{"rendered":"Linear Programming and the Simplex Method: Historical Evolution and Practical Applications"},"content":{"rendered":"<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">In the 1940s, during World War II, the British government enlisted the help of experts and mathematicians to study how to distribute military resources to achieve the best possible air and ground defense posture. This team of experts was initially named the Operations Research team, a term which later expanded to encompass all research and studies dealing with distribution issues and decision-making.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: left;\"><span style=\"font-size: 14pt;\"><span style=\"font-weight: 400;\">These <\/span><span style=\"font-weight: 400;\">studies and research<\/span><span style=\"font-weight: 400;\"> are a form of mathematical programming that links problems of organization, management, industry, agriculture, and transportation with mathematical variables. Specifically, linear <a href=\"https:\/\/old.masarat-sy.org\/en\/volunteering\/\" target=\"_blank\" rel=\"noopener\">programming<\/a> is a subset of mathematical programming where data is expressed using linear inequalities (first-degree relative to the variables) and assists researchers in making the right decision when aiming for the highest profit or lowest cost, known as the optimal solution.<\/span><\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: left;\"><span style=\"font-size: 14pt;\"><b>How is the optimal solution obtained<\/b><span style=\"font-weight: 400;\">?<\/span><\/span><\/p>\n<h2 style=\"text-align: left;\"><span style=\"font-size: 14pt;\"><b>The conditions necessary for a mathematical problem to be considered a linear programming<\/b><\/span><\/h2>\n<ul>\n<li style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">problem include having a specific objective (maximum profit or minimum loss), expressed through a linear function called the objective function.<\/span><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<ul>\n<li style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\"> There are decision variables, a large set of variables whose values need to be determined.<\/span><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<ul>\n<li style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">All variables are linked through linear relationship constraints, with the consideration that all variables are positive (non-negativity condition).<\/span><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h2 style=\"text-align: left;\"><span style=\"font-size: 14pt;\"><b>Formulating a Linear Programming<\/b><\/span><\/h2>\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">Problem A linear programming problem is represented in a table format with rows and columns as follows:<\/span><\/p>\n<p>&nbsp;<\/p>\n<ol style=\"text-align: left;\">\n<li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400; font-size: 14pt;\">Determine the number of variables (number of rows), with variables being X1, X2, X3, &#8230; Xn.<\/span><\/li>\n<li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400; font-size: 14pt;\">Determine the type of objective function (max for maximum profit, or min for minimum loss) and form the objective function using the variables.<\/span><\/li>\n<li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400; font-size: 14pt;\">Determine the number of constraints (number of columns), which are linear inequalities relative to the variables, including the non-negativity constraint.<\/span><\/li>\n<\/ol>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone  wp-image-14198\" src=\"https:\/\/old.masarat-sy.org\/wp-content\/uploads\/2024\/02\/358085674_831884925142036_1767094989281433673_n-300x158.jpg\" alt=\"\" width=\"942\" height=\"496\" title=\"\" srcset=\"https:\/\/old.masarat-sy.org\/wp-content\/uploads\/2024\/02\/358085674_831884925142036_1767094989281433673_n-300x158.jpg 300w, https:\/\/old.masarat-sy.org\/wp-content\/uploads\/2024\/02\/358085674_831884925142036_1767094989281433673_n-1024x538.jpg 1024w, https:\/\/old.masarat-sy.org\/wp-content\/uploads\/2024\/02\/358085674_831884925142036_1767094989281433673_n-768x403.jpg 768w, https:\/\/old.masarat-sy.org\/wp-content\/uploads\/2024\/02\/358085674_831884925142036_1767094989281433673_n.jpg 1200w\" sizes=\"(max-width: 942px) 100vw, 942px\" \/><\/p>\n<p>&nbsp;<\/p>\n<h2 style=\"text-align: left;\"><span style=\"font-size: 14pt;\"><b>The Simplex Method<\/b><\/span><\/h2>\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">\u00a0The simplex method is the primary technique for solving linear programming problems. It relies on identifying the intersection points between variables and constraints to find the optimal solution. This method requires all constraints to be less than or equal to a certain amount.<\/span><\/p>\n<p>&nbsp;<\/p>\n<h3 style=\"text-align: left;\"><span style=\"font-size: 14pt;\"><b>Steps to Solve a Linear Programming Problem Using the Simplex Method<\/b><\/span><\/h3>\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">1- Convert the problem into standard form by adding slack variables to turn inequalities into equalities.<\/span><\/p>\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">2- Set the objective function to zero (move all terms to one side).<\/span><\/p>\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">3- Form an initial table for the objective function and constraints with columns for:<\/span><\/p>\n<p style=\"text-align: left;\">\n<ul>\n<li style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\"><strong>The First Column<\/strong>: Basic Variables Column (B.V.) This column includes the slack variables that are introduced to the problem&#8217;s constraints as part of the solution process. The number of slack variables equals the number of constraints. At the bottom of this column, the objective function is placed.<\/span><\/li>\n<\/ul>\n<p style=\"text-align: left;\">\n<ul>\n<li style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\"><strong>The Second Column<\/strong>: The upper part of this column contains all the symbols of the objective function&#8217;s variables, while the coefficients of the constraints are placed in the middle part of this column. The coefficients of the objective function variables are placed in the lower part of this column.<\/span><\/li>\n<\/ul>\n<p style=\"text-align: left;\">\n<ul>\n<li style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\"><strong>The Third Column<\/strong>: Right Hand Side (RHS) Coefficients Column This column contains all the constraints of the problem and the zero value of the objective function.<\/span><\/li>\n<\/ul>\n<p style=\"text-align: left;\">\n<ul>\n<li style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\"><strong>The Fourth Column<\/strong>: Ratio Column This column is used to determine the leaving variable in the simplex method by calculating the ratio of the RHS values to the coefficients of the entering variable.<\/span><\/li>\n<\/ul>\n<p style=\"text-align: left;\">\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">4- Identify the entering variable: the variable in the column called the pivot column, taking the highest negative value for max objective functions and the highest positive value for min objective functions.<\/span><\/p>\n<p style=\"text-align: left;\">\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">5- Identify the leaving variable: this variable is in the row called the pivot row, obtained by dividing RHS coefficients by the coefficients of the pivot column, then selecting the smallest non-negative number resulting from this division.<\/span><\/p>\n<p style=\"text-align: left;\">\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">6- Determine the pivot element: the number resulting from the intersection of the pivot row and pivot column.<\/span><\/p>\n<p style=\"text-align: left;\">\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">Form a new table, replacing the leaving variable with the entering variable in the basic variables column. The coefficients of the new row are obtained by dividing each coefficient in this row by the pivot element, and the coefficients of the remaining rows are obtained by subtracting the product of the pivot element and the coefficients of the new pivot row, aiming to zero out elements above or below the pivot element.<\/span><\/p>\n<p style=\"text-align: left;\">\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">7- Extract the optimal solution: obtained from the last table<\/span><\/p>\n<ul>\n<li style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\"> when, for a max objective function, all z values are either zero or positive,<\/span><\/li>\n<li style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\"> and for a min objective function, all z values are either zero or negative.<\/span><\/li>\n<\/ul>\n<p style=\"text-align: left;\">\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">If the last table does not yield the optimal solution, repeat steps 4 through 7 until the optimal solution is achieved.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: left;\"><span style=\"font-weight: 400; font-size: 14pt;\">Linear programming is utilized in all economic problems aimed at finding the values of economic variables to achieve optimal usage in the presence of financial or technical constraints, or both. Hence, the simplex method, through a series of steps in table form requiring a number of arithmetic operations following a specific methodology, improves the solution until reaching the optimal solution.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: left;\"><span style=\"font-size: 14pt;\"><b>Author: Abdel Hamid Al-Diban, Mathematics Teacher at <\/b><a href=\"https:\/\/old.masarat-sy.org\/en\/\"><b>Masarat Initiative<\/b><\/a><\/span><\/p>\n<p style=\"text-align: left;\">\n","protected":false},"excerpt":{"rendered":"<p>In the 1940s, during World War II, the British government enlisted the help of experts and mathematicians to study how to distribute military resources to achieve the best possible air and ground defense posture. This team of experts was initially named the Operations Research team, a term which later expanded to encompass all research and [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":14195,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[55],"tags":[177,125,133,132],"class_list":["post-14464","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-blog","tag-development","tag-education","tag-research","tag-technology"],"acf":[],"_links":{"self":[{"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/posts\/14464","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/comments?post=14464"}],"version-history":[{"count":3,"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/posts\/14464\/revisions"}],"predecessor-version":[{"id":14467,"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/posts\/14464\/revisions\/14467"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/media\/14195"}],"wp:attachment":[{"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/media?parent=14464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/categories?post=14464"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/old.masarat-sy.org\/en\/wp-json\/wp\/v2\/tags?post=14464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}