Подробное решение симплексным методом

Решим прямую задачу линейного программирования симплексным методом, с использованием калькулятора.
Определим минимальное значение целевой функции F(X) =  - x1 - 2x2 + x3 при следующих условиях-ограничений.
-x1 + 4x2 - 2x3≤6
x1 + x2 + 2x3≥6
2x1 - x2 + 2x3=4

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
-1x1 + 4x2-2x3 + 1x4 + 0x5 = 6
1x1 + 1x2 + 2x3 + 0x4-1x5 = 6
2x1-1x2 + 2x3 + 0x4 + 0x5 = 4

Введем искусственные переменные x.
-1x1 + 4x2-2x3 + 1x4 + 0x5 + 0x6+ 0x7 = 6
1x1 + 1x2 + 2x3 + 0x4-1x5 + 1x6+ 0x7 = 6
2x1-1x2 + 2x3 + 0x4 + 0x5 + 0x6 + 1x7= 4

Для постановки задачи на минимум целевую функцию запишем так:
F(X) = -1x1-2x2+x3+Mx6+Mx7 => min
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.

Из уравнений выражаем искусственные переменные:
x6 = 6-x1-x2-2x3+x5
x7 = 4-2x1+x2-2x3
которые подставим в целевую функцию:
F(X) = -x1-2x2 + x3 + M(6-x1-x2-2x3+x5) + M(4-2x1+x2-2x3) => min
или
F(X) = (-1-3M)x1+(-2)x2+(1-4M)x3+(1M)x5+(10M) => min

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

-1 4 -2 1 0 0 0
1 1 2 0 -1 1 0
2 -1 2 0 0 0 1


Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Решим систему уравнений относительно базисных переменных:

x4, x6, x7

Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,6,0,6,4)


План

Базис

B

x1

x2

x3

x4

x5

x6

x7

0

x4

6

-1

4

-2

1

0

0

0


x6

6

1

1

2

0

-1

1

0


x7

4

2

-1

2

0

0

0

1

Индексная строка

F(X0)

10M

1+3M

2

-1+4M

0

-1M

0

0


Переходим к основному алгоритму симплекс-метода.


План

Базис

B

x1

x2

x3

x4

x5

x6

x7

min

1

x4

6

-1

4

-2

1

0

0

0

-


x6

6

1

1

2

0

-1

1

0

3


x7

4

2

-1

2

0

0

0

1

2

Индексная строка

F(X1)

10M

1+3M

2

-1+4M

0

-1M

0

0

0


Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее:
min (- , 6 : 2 , 4 : 2 ) = 2
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x3 .
Строка, соответствующая переменной x3  в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=2
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3  и столбец x3 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6 x 7
6-(4 • -2):2 -1-(2 • -2):2 4-(-1 • -2):2 -2-(2 • -2):2 1-(0 • -2):2 0-(0 • -2):2 0-(0 • -2):2 0-(1 • -2):2
6-(4 • 2):2 1-(2 • 2):2 1-(-1 • 2):2 2-(2 • 2):2 0-(0 • 2):2 -1-(0 • 2):2 1-(0 • 2):2 0-(1 • 2):2
4 : 2 2 : 2 -1 : 2 2 : 2 0 : 2 0 : 2 0 : 2 1 : 2
(10M)-(4 • (-1+4M)):2 (1+3M)-(2 • (-1+4M)):2 (2)-(-1 • (-1+4M)):2 (-1+4M)-(2 • (-1+4M)):2 (0)-(0 • (-1+4M)):2 (-1M)-(0 • (-1+4M)):2 (0)-(0 • (-1+4M)):2 (0)-(1 • (-1+4M)):2



План

Базис

B

x1

x2

x3

x4

x5

x6

x7

min

2

x4

10

1

3

0

1

0

0

1

31/3


x6

2

-1

2

0

0

-1

1

-1

1


x3

2

1

-1 /2

1

0

0

0

1 /2

-

Индексная строка

F(X2)

2+2M

2-1M

11/2+2M

0

0

-1M

0

1 /2-2M

0


Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее:
min (10 : 3 , 2 : 2 , - ) = 1

Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x2 .
Строка, соответствующая переменной x2  в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=2
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2  и столбец x2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:


B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

10-(2 • 3):2

1-(-1 • 3):2

3-(2 • 3):2

0-(0 • 3):2

1-(0 • 3):2

0-(-1 • 3):2

0-(1 • 3):2

1-(-1 • 3):2

2 : 2

-1 : 2

2 : 2

0 : 2

0 : 2

-1 : 2

1 : 2

-1 : 2

2-(2 • -1/2):2

1-(-1 • -1/2):2

-1 /2-(2 • -1/2):2

1-(0 • -1/2):2

0-(0 • -1/2):2

0-(-1 • -1/2):2

0-(1 • -1/2):2

1 /2-(-1 • -1/2):2

(2+2M)-(2 • (11/2+2M)):2

(2-1M)-(-1 • (11/2+2M)):2

(11/2+2M)-(2 • (11/2+2M)):2

(0)-(0 • (11/2+2M)):2

(0)-(0 • (11/2+2M)):2

(-1M)-(-1 • (11/2+2M)):2

(0)-(1 • (11/2+2M)):2

(1/2-2M)-(-1 • (11/2+2M)):2



План

Базис

B

x1

x2

x3

x4

x5

x6

x7

min

3

x4

7

21/2
 

0

0

1

11/2

-11/2

21/2

24/5
 


x2

1

-1 /2

1

0

0

-1 /2

1 /2

-1 /2

-


x3

21/2

3 /4

0

1

0

-1 /4

1 /4

1 /4

31/3

Индексная строка

F(X3)

1 /2

23/4
 

0

0

0

3 /4

-3 /4-1M

11/4-1M

0


Итерация №2.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее:
min (7 : 21/2 , - , 21/2 : 3/4 ) = 24/5

Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (21/2) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 3 войдет переменная x1 .
Строка, соответствующая переменной x1  в плане 3, получена в результате деления всех элементов строки x4 плана 2 на разрешающий элемент РЭ=21/2
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x1 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x1  и столбец x1 .
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:


B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

7 : 21/2

21/2 : 21/2

0 : 21/2

0 : 21/2

1 : 21/2

11/2 : 21/2

-11/2 : 21/2

21/2 : 21/2

1-(7 • -1/2):21/2

-1 /2-(21/2-1/2):21/2

1-(0 • -1/2):21/2

0-(0 • -1/2):21/2

0-(1 • -1/2):21/2

-1 /2-(11/2-1/2):21/2

1 /2-(-11/2-1/2):21/2

-1 /2-(21/2-1/2):21/2

21/2-(7 • 3/4):21/2

3 /4-(21/23/4):21/2

0-(0 • 3/4):21/2

1-(0 • 3/4):21/2

0-(1 • 3/4):21/2

-1 /4-(11/23/4):21/2

1 /4-(-11/23/4):21/2

1 /4-(21/23/4):21/2

(1/2)-(7 • (23/4)):21/2

(23/4)-(21/2 • (23/4)):21/2

(0)-(0 • (23/4)):21/2

(0)-(0 • (23/4)):21/2

(0)-(1 • (23/4)):21/2

(3/4)-(11/2 • (23/4)):21/2

(-3/4-1M)-(-11/2 • (23/4)):21/2

(11/4-1M)-(21/2 • (23/4)):21/2
 



Окончательный вариант симплекс-таблицы:


План

Базис

B

x1

x2

x3

x4

x5

x6

x7

4

x1

24/5

1

0

0

2 /5

3 /5

-3 /5

1


x2

22/5

0

1

0

1 /5

-1 /5

1 /5

0


x3

2 /5

0

0

1

-3 /10

-7 /10

7 /10

-1 /2

Индексная строка

F(X4)

-71/5

0

0

0

-11/10

-9 /10

9 /10-1M

-11/2-1M


Оптимальный план можно записать так:
x1 = 24/5
x2 = 22/5
x3 = 2/5
F(X) = -1•24/5 -2•22/5 + 1•2/5 = -71/5

Перейти к онлайн решению своей задачи

загрузка...