Симплексный метод решения задач линейного программирования включает определение одного

Симплексный метод является самым ранним алгоритмом решения задач LP. Это эффективная реализация решения ряда систем линейных уравнений. Используя жадную стратегию при прыжке из допустимой вершины следующей соседней вершины. Алгоритм завершается оптимальным решением. Целью этого сайта является расширение понимания процесса разработки симплексного метода. Для поиска по сайту, попробуйте Edit | Find на странице [Ctrl + f]. Введите слово или фразу в диалоговом окне. Например parameter » илиlinear » , если первое появление слова/фразы не то. Что вы ищете. Попробуйте Find Next.


МЕНЮ

  1. Введение
  2. Алгебраический метод
  3. Операции с поворотными рядами
  4. Симплексный метод

Сопутствующие Сайты:


Введение

Графический метод ограничен в решении задач LP. Имеющих одну или две переменные решения.

Однако он дает четкую иллюстрацию того. Где находятся допустимые и невыполнимые области. А также вершины. Визуальное понимание проблемы помогает более рационально мыслить. Например, мы узнали. Что: если линейная программа имеет непустую. Ограниченную допустимую область. То оптимальным решением всегда является одна вершина ее допустимой области (угловая точка). Поэтому необходимо найти все точки пересечения (вершины) и затем исследовать. Какая из всех возможных вершин дает оптимальное решение.

Теперь, используя Понятиями аналитической геометрии мы преодолеем эту ограниченность человеческого зрения. Алгебраический метод предназначен для распространения результатов графического метода на многомерную задачу LP.


Алгебраический метод:
LP-модели с многомерными решающими переменными

Мы заинтересованы в решении следующей общей задачи:

Max( или Min) C. X
при условии:
AX £ a
BX ³ b
DX = d
с, возможно, некоторыми ограниченными переменными: некоторые Xi ³ 0, некоторые Xi £ 0, и все остальные неограниченные в знаке.

Вот четырехступенчатая процедура для алгоритма алгебраического решения:

  1. Построение границ набора ограничений: Преобразуйте все неравенства (за исключением ограниченного условия для каждой переменной. Если таковые имеются) к равенствам путем добавления или вычитания слабых и избыточных переменных. Построение границы ограниченных переменных включено в следующий шаг.
  2. Нахождение всех вершин: Если число переменных (включая слабину и избыток) больше числа уравнений. То установите следующее число переменных равным нулю:
    [ (Общее количество переменных. Включая слабые и избыточные переменные) — (Количество уравнений) ]

    Переменными, которые нужно установить в ноль, являются слабина, избыток и ограниченные переменные (любые Xi ³ 0, или Xi £ 0) только. Установив эти многочисленные переменные равными нулю. Затем найдите другие переменные. Решив полученную квадратную систему уравнений.

    Обратите внимание, если Xi ³ 0, то его можно было бы записать как Xi — Si = 0, установка соответствующего Si на ноль означает Xi = 0, поэтому нет необходимости явно вводить сложение слабых и избыточных переменных. Заметим также. Что когда любой Xi является неограниченным по значению знаком. Он не добавляет ограничения.

  3. Проверьте Осуществимость: Все слабины и излишки должны быть неотрицательными и проверять наличие ограниченного условия для каждой переменной. Если таковые имеются. Каждое допустимое решение называется Основное Осуществимое Решение, которая является угловой точкой допустимой области.
  4. Выбор оптимальной угловой точки: Среди всех возможных решений (т. Е. возможных угловых точек) найдите оптимальное (если таковое имеется). Оценив целевую функцию. Может быть несколько оптимальных решений.

Помните, что линейная система AX=b имеет решение тогда и только тогда. Когда ранг A равен рангу дополненной матрицы (A,B).

Определения. Которые нужно знать:

Каждое решение любой системы уравнений называется Основное решение (BS). Те БС, которые выполнимы. Называются Основные возможные решения (BFS).
В каждом базовом решении переменные. Которые вы устанавливаете равными нулю. Называются Неосновные переменные (NBV), все остальные переменные. Вычисляемые с помощью системы уравнений. Называются Основные переменные (BV).
Обратите внимание. Что список переменных решения. Которые являются BV для оптимального решения. Легко доступен в таблице QSB optimal solution tableau.

Slack — это остаток ресурса. Излишек — это избыток производства.

Количество базовых решений: После преобразования всех неравенств в равенства пусть T = Общее число переменных. Включая слабые и избыточные переменные. E = Число уравнений и R = общее число слабых и избыточных переменных и ограниченных переменных решения. Тогда максимальное число основных решений равно:

R! / [(T — E)! (R + E — T)!]

куда? расшифровывается как факториалы. Например, 4 ! = (1)(2)(3)(4) = 24. Обратите внимание. Что по определению 0 ! = 1.

Обратите внимание. Что если E > Т или Т > R + E. То первоначальная формулировка LP может быть неправильной.

Средства защиты для корректирующих действий обсуждаются в разделе

Главный результат: Если задача LP имеет ограниченное решение(ы). То алгебраический метод порождает решение(ы).

Пример 1 : Задача Без Какой-Либо Ограниченной Переменной:

Макс. X1 + X2
при условии:
X1 + X2 ³ 10
Х1 £ 8
Х2 £ 12

Вводя переменные слабины и избытка, мы имеем:

X1 + X2 — S1 = 10
X1 + S2 = 8
X2 + S3 = 12

Для этой задачи E = 3, T = 5, R = 3, следовательно. Существует не более 3! / [2! . (3 — 2)! ] = 3 основных решения. Чтобы найти основные решения. Мы замечаем. Что есть 3 уравнения с 5 неизвестными. Устанавливая любые 2 = 5 — 3 слабых и избыточных переменных равными нулю. И решая три результирующие системы уравнений, мы имеем:

S1 S2 S3 X1 X2 X1 + X2
0 0 10 82 10
100081220*
0100-21210

Оптимальное решение S1= 10, S2 = 0, S3 = 0, X1 = 8, X2 = 12, с оптимальным значением 20.

Пример 2: Проблема С Одной Ограниченной Переменной:

Следующая проблема приписывается Андреасу Энге и Петре Хун.

Максимизировать 3X1 + X2 — 4X3
при условии:
X1 + X2 — X3 =1,
X2 ³ 2,
X1 ³ 0

После добавления избыточной переменной мы имеем:

Maximize 3X1 + X2 — 4X3
subject to:
X1 + X2 — X3 =1,
X2 — S1 = 2,

This LP problem cannot be solved by the graphical method. However, the algebraic method is general in the sense that it does not put any limitations on the dimensionality of the problem. Notice that we have two equations with one surplus variable and one restricted decision variable. The parameters for this problem are: T = 4, R = 2, and E = 2. This gives the total number of possible basic solutions: 2! / [(2!). (0!)] = 1. By setting the surplus and X1 variables to zero we get:

X1 X2 X3 S1 3X1 + X2 -4X3
0210-2*

Thus the optimal solution is X1 = 0, X2 = 2, X3 = 1, with optimal value of -2.

Example 3: The Carpenter’s Problem:

Introducing the slack and surplus variables to convert all inequalities into equalities, we have:

2X1 + X2 + S1 = 40
X1 + 2X2 + S2 = 50

Here we have 2 equations with 4 unknowns. Since the variables X1 and X2 both are restricted. We must set any two variables including these two, to zero. Solving the six resultant systems of equations, we have:

S1 S2 X1 X2 5X1 + 3X2
001020110*
0-30040infeasible
030200100
15002575
-600500infeasible
4050000

Therefore, from the above table, we see that, the optimal solution is S1= 0, S2 = 0, X1 = 10, X2 = 20, with optimal value of $110.

Example 4: A Problem With Mixed Constraints:

Min X1 + 2X2
subject to:
X1 + X2 ³ 4
-X1 + X2 £ 2
X1 ³ 0, and X2 is unrestricted in sign.

Introducing the slack and surplus variables, we have:

X1 + X2 — S1 = 4
-X1 + X2 + S2 = 2

Here we have 2 equations with 4 unknowns. Since only X1 is restricted. We must set any two of the variables S1, S2, and X1 to zero. Solving the six resultant systems of equations, we have:

X1 X2 S1 S2 X1 + 2X2
040-2infeasible
02-20infeasible
130 07*

Therefore, from the above table, we see that, the optimal solution is X1 = 1, X2 = 3, S1= 0, S2 = 0, with optimal value of 7.

Example 5: A Transportation Problem:

The goal is to find the most effective way to transport the goods. The supply and demand at each origin (e.g.; warehouse) O1, O2 and destination (e.g.; market) D1 and D2, together with the unit transportation cost are summarized in the following table.

The Unit Transportation Cost Matrix
D1D2Supply
O12030200
O21040100
Demand150150300

Let Xij denotes the amount of shipment from source i to destination j. The LP formulation of the problem minimizing the total transportation cost is:

Min 20X11 + 30X12 + 10X21 + 40X22

subject to:
X11 + X12 = 200
X21 + X22 = 100
X11 + X21 = 150
X12 + X22 = 150
all Xij ³ 0

Because this transportation problem is a balanced one (total supply = total demand), therefore. All constraints are in equality form. Moreover, any one of the constraints is redundant (adding any two constraints and subtracting another one we obtain the remaining one). Let us delete the last constraint. Therefore, the problem reduces to:

Min 20X11 + 30X12 + 10X21 + 40X22

subject to:
X11 + X12 = 200
X21 + X22 = 100
X11 + X21 = 150
all Xij ³ 0

This LP problem cannot be solved by the graphical method. However, the algebraic method has no limitation on the LP dimension. Notice that we have three equations with four restricted decision variables. Setting any one of the variables in turn to zero we get:

X11 X12 X21 X22 Total Transportation Cost
0200150 -50
infeasible
2000-50150infeasible
1505001008500
5015010006500*

Thus the optimal strategy is X11 = 50, X12 = 150, X21 = 100, and X22 = 0, with a least total transportation cost of $6,500.

Example 6: A Problem With Too-few Constraints:

As our last example. Consider the following problem:

Max X1 + X2
subject to:
X1 + X2 £ 5

Introducing the slack variable we have:

X1 + X2 + S1 = 5

The parameters for this problem are: T = 3, R = 1, and E = 1. This gives the total number of possible basic solutions 1! / [(1!). (0!)] = 1. By setting the slack variable to zero we have this single equation X1 + X2 = 5 with two variables to solve. Therefore, there is no corner point, moreover. The feasible region is also unbounded. However, any arbitrary solution such as X1 = 0, X2 = 5 is optimal solution to the LP problem. With an optimal value of 5.

For a refined algebraic method visit the Solution Algorithms for LP Models Web site.

For more numerical examples. Extensions. Proofs read the following articles:

Arsham H., Affine Geometric Method for Linear Programs, Journal of Scientific Computing, Vol. 12, No. 3, 289-303, 1997.
Arsham H., Links Among a Linear System of Equations, Matrix Inversion, and Linear Program Solver Routines, Journal of Mathematical Education in Science and Technology, Vol. 29, No. 5, 764-769, 1998.


Pivoting Row Operations

Как вы помните. Алгебраический метод включает в себя решение многих линейных систем уравнений.

Когда задача LP имеет много переменных и ограничений. То решение такого количества систем уравнений вручную становится очень утомительным и даже для очень крупномасштабных задач это невыполнимая задача.

Поэтому нам нужен компьютер. Чтобы делать вычисления за нас.

Один из алгоритмических и компьютеризированных подходов к решению линейных систем уравнений известен как операции поворота Гаусса-Джордана (GJ).

The GJ pivoting will be also required later during the Simplex Method. And now is a good time to develop the habits needed at those later times.

Pivoting uses row operations (known as Gauss-Jordan row operations) to change one matrix entry (the Pivot) to «1». And then to change all other entries in the pivot’s column into Zero’s.

Once a pivot is chosen. The row operations of pivoting must be as follows:

Step 1: Make the pivot «1» by dividing the pivot’s row by the pivot number

Step 2: Make the remainder of the pivot’s Columns into Zero’s by adding to each row a suitable multiple of the Pivot Row.

Note: The number changing to «1» is called a Pivot. Is usually encircled. And cannot be zero. If it is zero. Then interchange this row with a row below it with a non-zero element in that column (if there is none. Then the conversion is impossible).

A Numerical Example: Using the Gauss-Jordan row operations. Solve the following system of equations:

2X1 + X2 + X3 = 3
X1 + 3X3 = 1
2X1 + X2 = 2

The aim is to convert the coefficients of the system of equations into the following identity matrix. The results on the RHS’s elements (?) provide the solution (if one exists).

100?
010?
001?

Step 1. Use row operations column by column;

Step 2. In each column:

a) First obtain the 1 in the appropriate row by multiplying by the reciprocal. Note: If there is a 0 in this position. Exchange rows with a row below with a non-zero element if possible.

b) Reduce all other values in the column to zero by adding the appropriate multiple of the row containing the 1 to each row.

Let’s apply the above procedure to our numerical example.

Notations: Old Row [ ]. New Row { }. Putting these two matrices next to each other. The augmented matrix is:

Row #

Operations

Results

RHS

1

2

1

1

3

2

1

0

3

1

3

2

1

0

2

1

[1]/2

1

1/2

1/2

3/2

2

-1{1}+[2]

0

-1/2

5/2

-1/2

3

-2{1}+[3]

0

0

-1

-1

1

(-1/2){2}+[1]

1

0

3

1

2

[2]/(-1/2)

0

1

-5

1

3

(0){2}+[3]

0

0

-1

-1

1

(-3){3} + [1]

1

0

0

-2

2

(5){3} + [2]

0

1

0

6

3

[3]/(-1)

0

0

1

1

The solution is X1 = -2, X2 = 6, and X3 =1, which can be verified by substitutions.

Also visit the Web sites Solving a linear system of equations, Pivot Engine, Solve System of Linear Equations, and The Equator Module.


The Simplex Method

Симплексный метод — это еще один алгоритм решения задач LP.

Вы помните, что Алгебраический метод предоставляет все вершины, даже те. Которые не выполнимы.

Поэтому это не является эффективным способом решения задач LP с большим количеством ограничений.

Симплексный метод является модификацией Алгебраического метода. Который преодолевает этот недостаток.

Однако Симплексный метод имеет свои недостатки.

Например, он требует. Чтобы все переменные были неотрицательными (³ 0); кроме того. Все остальные ограничения должны быть в £ форма с неотрицательными правосторонними значениями (RHS).

Like the Algebraic Method. The simplex method is also a tabular solution algorithm. However, each tableau in the simplex method corresponds to a movement from one basic variable set BVS (extreme or corner point) to another. Making sure that the objective function improves at each iteration until the optimal solution is reached.

The presentation of the simplex method is not universal. In the U.S.A. professors on the West Coast enjoy solving the minimization problems. While in the East the maximization version is preferred. Even within each of these groups you will find differences in presenting the simplex rules. The following process describes all the steps involved in applying the simplex solution algorithm:

  1. Convert the LP to the following form:

    Convert the minimization problem into a maximization one (by multiplying the objective function by -1).
    All variables must be non-negative.
    All RHS values must be non-negative (multiply both sides by -1, if needed).
    All constraints must be in £ form (except the non-negativity conditions). No strictly equality or ³ constraints are allowed.
    If this condition cannot be satisfied. Then use the Initialization of the Simplex Method: Articicial-Free.

  2. Convert all £ constraints to equalities by adding a different slack variable for each one of them.
  3. Construct the initial simplex tableau with all slack variables in the BVS. The last row in the table contains the coefficient of the objective function (row Cj).
  4. Determine whether the current tableau is optimal. That is:
    If all RHS values are non-negative (called. The feasibility condition)
    If all elements of the last row. That is Cj row. Are non-positive (called. The optimality condition).

    If the answers to both of these two questions are Yes, then stop. The current tableau contains an optimal solution.
    Otherwise, go to the next step.

  5. If the current BVS is not optimal, determine. Which nonbasic variable should become a basic variable and. Which basic variable should become a nonbasic variable. To find the new BVS with the better objective function value. Perform the following tasks:
    • Identify the entering variable: The entering variable is the one with the largest positive Cj value (In case of a tie. We select the variable that corresponds to the leftmost of the columns) .
    • Identify the outgoing variable: The outgoing variable is the one with smallest non-negative column ratio (to find the column ratios. Divide the RHS column by the entering variable column. Wherever possible). In case of a tie we select the variable that corresponds to the upmost of the tied rows.
    • Generate the new tableau: Perform the Gauss-Jordan pivoting operation to convert the entering column to an identity column vector (including the element in the Cj row).

      Go to step 4.

A short discussion on the simplex method strategy: At the start of the simplex procedure; the set of basis is constituted by the slack variables. Remember that the first BVS has only slack variables in it. The row Cj presents the increase in the value of the objective function that will result if one unit of the variable corresponding to the jth column was brought in the basis. This row answers the question: Can we improve the objective function by moving to a new BVS? We will call it The Indicator Row (since it indicates if the optimality condition is satisfied).

Criterion for entering a new variable into the BVS will cause the largest per-unit improvement of the objective function. Criterion for removing a variable from the current BVS maintains feasibility (making sure that the new RHS. After pivoting remain non-negative).

Warning: Whenever during the Simplex iterations yet get a negative RHS. It means you have selected a wrong outgoing variable. The best remedy is to start all over again.

Notice that there is a solution corresponding to each simplex tableau. The numerical of basic variables are the RHS values. While the other variables (non-basic variables) are always equal to zero.

Notice also that variables can exit and enter the basis repeatedly during the simplex algorithm.

Numerical Recipes states that the Simplex algorithm is ‘almost always’ O(max(N,M)). Which means that the number of iteration is a factor of number of variables or number of constraints. Whichever is larger.

Geometric Interpretation of the Simplex Method: The simplex method always starts at the origin (which is a corner point) and then jumps from a corner point to the neighboring corner point until it reaches the optimal corner point (if bounded). Therefore, at each one of the simplex iterations. We are searching for a better solution among the vertices of a Simplex. A simplex in an n-dimensional space is the simplest shape having n + 1 vertices. For example. A triangle is a simplex in 2-dimensional space while a pyramid is a simplex in 3-dimensional space. These movements can be seen when you correspond each simplex tableau with an specific corner point in the graphical method e.g.; the carpenter’s problem. As shown next.

A Numerical Example: The Carpenter’s Problem

Maximize 5X1 + 3X2

Subject to:
2X1 + X2 £ 40
X1 + 2X2 £ 50
and both X1, X2 are non-negative.

After adding two slack variables S1 and S2 the problem is equivalent to:

Maximize 5X1 + 3X2

Subject to:
2X1 + X2 + S1 = 40
X1 + 2X2 + S2 = 50
and variables X1, X2, S1, S2 are all non-negative.

The initial tableau is:

BVS X1 X2 S1 S2 RHS Column Ratio (C/R)
S1[2]1104040/2
S21201 5050/1
Cj5300

The solution shown by this tableau is: S1 = 40, S2 = 50, X1 = 0, and X2 = 0. This solution is the origin. Shown in our graphical method.

This table is not optimal since some of Cj elements are positive. The incoming variable is X1 and the outgoing variable is S1 (by C/R test). The pivot element is in the bracket. After pivoting, we have:

BVS X1 X2 S1 S2RHSColumn Ratio (C/R)
X111/21/202020/(1/2)=40
S20[3/2]-1/2130 30/(3/2)=10
Cj01/2-5/20

The solution to this tableau is: X1 = 20, S2 = 30, S1 = 0, and X2 = 0. This solution is the corner point (20. 0)n in our graphical method.

This table is not optimal. Since some of Cj elements is positive. The incoming variable is X2 and the outgoing variable is S2 (by C/R test). The pivot element is in the bracket. After pivoting, we have:

BVS X1 X2 S1 S2RHS
X1102/3-1/310
X201-1/32/320
Cj00-7/3-1/3

The solution to this tableau is: X1 = 10, X2 = 20, S1 = 0, and S2 = 0. This solution is the corner point (10, 20). Shown in our graphical method.

This tableau is optimal. Since all Cj elements are non-positive and all RHS are non-negative. The optimal solution is X1 = 10, X2 = 20, S1 =0, S2 = 0. To find the optimal value. Plug in this solution into the objective function 5X1 + 3X2 = 5(10) + 3(20) = $110.

Visit also the Web sites tutOR, The Simplex Place, Simplex Machine, and LP-Explorer.

Further Readings:

Maros I., Computational Techniques of the Simplex Method, Kluwer Publishers, 2002.


The Copyright Statement: The fair use. According to the 1996 Fair Use Guidelines for Educational Multimedia, of materials presented on this Web site is permitted for non-commercial and classroom purposes only.
This site may be mirrored intact (including these notices). On any server with public access. And linked to other Web pages. All files are available at http://home.ubalt.edu/ntsbarsh/Business-stat for mirroring.

Kindly e-mail me your comments. Suggestions. And concerns. Thank you.


This site was launched on 2/25/1994, and its intellectual materials have been thoroughly revised on a yearly basis. The current version is the 8th Edition. All external links are checked once a month.


Back to:

Dr Arsham’s Home Page


ЭОФ: Ó 1994-2015.