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

Определим максимальное значение целевой функции F(X) = 2x1 - 3x2 + 5x3 + x4 + x5 при следующих условиях-ограничений.
- 4x1 + 13x3 + x4 + 2x5=10
15x1 + 4x2 + 27x3 + x4 + x5=20
- 6x1 + x2 + 15x3 + x4 + x5=11
Введем искусственные переменные x: в 1-м равенстве вводим переменную x6; в 2-м равенстве вводим переменную x7; в 3-м равенстве вводим переменную x8;
-4x1 + 0x2 + 13x3 + 1x4 + 2x5 + 1x6 + 0x7 + 0x8 = 10
15x1 + 4x2 + 27x3 + 1x4 + 1x5 + 0x6 + 1x7 + 0x8 = 20
-6x1 + 1x2 + 15x3 + 1x4 + 1x5 + 0x6 + 0x7 + 1x8 = 11
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 2x1-3x2+5x3+x4+x5 - Mx6 - Mx7 - Mx8 → max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x6 = 10+4x1-13x3-x4-2x5
x7 = 20-15x1-4x2-27x3-x4-x5
x8 = 11+6x1-x2-15x3-x4-x5
которые подставим в целевую функцию:
F(X) = 2x1-3x2 + 5x3 + x4 + x5 - M(10+4x1-13x3-x4-2x5) - M(20-15x1-4x2-27x3-x4-x5) - M(11+6x1-x2-15x3-x4-x5) → max
или
F(X) = (2+5M)x1+(-3+5M)x2+(5+55M)x3+(1+3M)x4+(1+4M)x5+(-41M) → max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
-4 0 13 1 2 1 0 0
15 4 27 1 1 0 1 0
-6 1 15 1 1 0 0 1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x6, x7, x8,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,0,10,20,11)
Базисное решение называется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x6 10 -4 0 13 1 2 1 0 0
x7 20 15 4 27 1 1 0 1 0
x8 11 -6 1 15 1 1 0 0 1
F(X0) -41M -2-5M 3-5M -5-55M -1-3M -1-4M 0 0 0


Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (10 : 13 , 20 : 27 , 11 : 15 ) = 11/15
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (15) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x6 10 -4 0 13 1 2 1 0 0 10/13
x7 20 15 4 27 1 1 0 1 0 20/27
x8 11 -6 1 15 1 1 0 0 1 11/15
F(X1) -41M -2-5M 3-5M -5-55M -1-3M -1-4M 0 0 0 0


4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x3 .
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x8 плана 0 на разрешающий элемент РЭ=15
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (15), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6 x7 x8
10-(11 • 13):15 -4-(-6 • 13):15 0-(1 • 13):15 13-(15 • 13):15 1-(1 • 13):15 2-(1 • 13):15 1-(0 • 13):15 0-(0 • 13):15 0-(1 • 13):15
20-(11 • 27):15 15-(-6 • 27):15 4-(1 • 27):15 27-(15 • 27):15 1-(1 • 27):15 1-(1 • 27):15 0-(0 • 27):15 1-(0 • 27):15 0-(1 • 27):15
11 : 15 -6 : 15 1 : 15 15 : 15 1 : 15 1 : 15 0 : 15 0 : 15 1 : 15
(0)-(11 • (-5-55M)):15 (-2-5M)-(-6 • (-5-55M)):15 (3-5M)-(1 • (-5-55M)):15 (-5-55M)-(15 • (-5-55M)):15 (-1-3M)-(1 • (-5-55M)):15 (-1-4M)-(1 • (-5-55M)):15 (0)-(0 • (-5-55M)):15 (0)-(0 • (-5-55M)):15 (0)-(1 • (-5-55M)):15



Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x6 7/15 11/5 -13/15 0 2/15 12/15 1 0 -13/15
x7 1/5 254/5 21/5 0 -4/5 -4/5 0 1 -14/5
x3 11/15 -2/5 1/15 1 1/15 1/15 0 0 1/15
F(X1) 32/3-2/3M -4-27M 31/3-11/3M 0 -2/3+2/3M -2/3-1/3M 0 0 1/3+32/3M


Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (7/15 : 11/5 , 1/5 : 254/5 , - ) = 1/129
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (254/5) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x6 7/15 11/5 -13/15 0 2/15 12/15 1 0 -13/15 7/18
x7 1/5 254/5 21/5 0 -4/5 -4/5 0 1 -14/5 1/129
x3 11/15 -2/5 1/15 1 1/15 1/15 0 0 1/15 -
F(X2) 32/3-2/3M -4-27M 31/3-11/3M 0 -2/3+2/3M -2/3-1/3M 0 0 1/3+32/3M 0


4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x1 .
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x7 плана 1 на разрешающий элемент РЭ=254/5
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6 x7 x8
7/15-(1/5 • 11/5):254/5 11/5-(254/5 • 11/5):254/5 -13/15-(21/5 • 11/5):254/5 0-(0 • 11/5):254/5 2/15-(-4/5 • 11/5):254/5 12/15-(-4/5 • 11/5):254/5 1-(0 • 11/5):254/5 0-(1 • 11/5):254/5 -13/15-(-14/5 • 11/5):254/5
1/5 : 254/5 254/5 : 254/5 21/5 : 254/5 0 : 254/5 -4/5 : 254/5 -4/5 : 254/5 0 : 254/5 1 : 254/5 -14/5 : 254/5
11/15-(1/5-2/5):254/5 -2/5-(254/5-2/5):254/5 1/15-(21/5-2/5):254/5 1-(0 • -2/5):254/5 1/15-(-4/5-2/5):254/5 1/15-(-4/5-2/5):254/5 0-(0 • -2/5):254/5 0-(1 • -2/5):254/5 1/15-(-14/5-2/5):254/5
(1/3+32/3M)-(1/5 • (-4-27M)):254/5 (-4-27M)-(254/5 • (-4-27M)):254/5 (31/3-11/3M)-(21/5 • (-4-27M)):254/5 (0)-(0 • (-4-27M)):254/5 (-2/3+2/3M)-(-4/5 • (-4-27M)):254/5 (-2/3-1/3M)-(-4/5 • (-4-27M)):254/5 (0)-(0 • (-4-27M)):254/5 (0)-(1 • (-4-27M)):254/5 (1/3+32/3M)-(-14/5 • (-4-27M)):254/5



Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x6 59/129 0 -125/129 0 22/129 122/129 1 -2/43 -101/129
x1 1/129 1 11/129 0 -4/129 -4/129 0 5/129 -3/43
x3 95/129 0 13/129 1 7/129 7/129 0 2/129 5/129
F(X2) 330/43-59/129M 0 329/43+125/129M 0 -34/43-22/129M -34/43-122/129M 0 20/129+12/43M 7/129+1101/129M


Итерация №2.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x5, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai5
и из них выберем наименьшее:
min (59/129 : 122/129 , - , 95/129 : 7/129 ) = 59/151
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (122/129) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x6 59/129 0 -125/129 0 22/129 122/129 1 -2/43 -101/129 59/151
x1 1/129 1 11/129 0 -4/129 -4/129 0 5/129 -3/43 -
x3 95/129 0 13/129 1 7/129 7/129 0 2/129 5/129 134/7
F(X3) 330/43-59/129M 0 329/43+125/129M 0 -34/43-22/129M -34/43-122/129M 0 20/129+12/43M 7/129+1101/129M 0


4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 3 войдет переменная x5 .
Строка, соответствующая переменной x5 в плане 3, получена в результате деления всех элементов строки x6 плана 2 на разрешающий элемент РЭ=122/129
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x5 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x5 и столбец x5 .
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6 x7 x8
59/129 : 122/129 0 : 122/129 -125/129 : 122/129 0 : 122/129 22/129 : 122/129 122/129 : 122/129 1 : 122/129 -2/43 : 122/129 -101/129 : 122/129
1/129-(59/129-4/129):122/129 1-(0 • -4/129):122/129 11/129-(-125/129-4/129):122/129 0-(0 • -4/129):122/129 -4/129-(22/129-4/129):122/129 -4/129-(122/129-4/129):122/129 0-(1 • -4/129):122/129 5/129-(-2/43-4/129):122/129 -3/43-(-101/129-4/129):122/129
95/129-(59/1297/129):122/129 0-(0 • 7/129):122/129 13/129-(-125/1297/129):122/129 1-(0 • 7/129):122/129 7/129-(22/1297/129):122/129 7/129-(122/1297/129):122/129 0-(1 • 7/129):122/129 2/129-(-2/437/129):122/129 5/129-(-101/1297/129):122/129
(7/129+1101/129M)-(59/129 • (-34/43-122/129M)):122/129 (0)-(0 • (-34/43-122/129M)):122/129 (329/43+125/129M)-(-125/129 • (-34/43-122/129M)):122/129 (0)-(0 • (-34/43-122/129M)):122/129 (-34/43-22/129M)-(22/129 • (-34/43-122/129M)):122/129 (-34/43-122/129M)-(122/129 • (-34/43-122/129M)):122/129 (0)-(1 • (-34/43-122/129M)):122/129 (20/129+12/43M)-(-2/43 • (-34/43-122/129M)):122/129 (7/129+1101/129M)-(-101/129 • (-34/43-122/129M)):122/129



Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x5 59/151 0 -125/151 0 22/151 1 129/151 -6/151 -101/151
x1 3/151 1 9/151 0 -4/151 0 4/151 17/453 -41/453
x3 108/151 0 22/151 1 7/151 0 -7/151 8/453 34/453
F(X3) 41/151 0 33/151 0 -102/151 0 102/151+1M 56/453+1M -215/453+1M


Итерация №3.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai4
и из них выберем наименьшее:
min (59/151 : 22/151 , - , 108/151 : 7/151 ) = 215/22
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (22/151) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x5 59/151 0 -125/151 0 22/151 1 129/151 -6/151 -101/151 215/22
x1 3/151 1 9/151 0 -4/151 0 4/151 17/453 -41/453 -
x3 108/151 0 22/151 1 7/151 0 -7/151 8/453 34/453 153/7
F(X4) 41/151 0 33/151 0 -102/151 0 102/151+1M 56/453+1M -215/453+1M 0


4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 4 войдет переменная x4 .
Строка, соответствующая переменной x4 в плане 4, получена в результате деления всех элементов строки x5 плана 3 на разрешающий элемент РЭ=22/151
На месте разрешающего элемента в плане 4 получаем 1.
В остальных клетках столбца x4 плана 4 записываем нули.
Таким образом, в новом плане 4 заполнены строка x4 и столбец x4 .
Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6 x7 x8
59/151 : 22/151 0 : 22/151 -125/151 : 22/151 0 : 22/151 22/151 : 22/151 1 : 22/151 129/151 : 22/151 -6/151 : 22/151 -101/151 : 22/151
3/151-(59/151-4/151):22/151 1-(0 • -4/151):22/151 9/151-(-125/151-4/151):22/151 0-(0 • -4/151):22/151 -4/151-(22/151-4/151):22/151 0-(1 • -4/151):22/151 4/151-(129/151-4/151):22/151 17/453-(-6/151-4/151):22/151 -41/453-(-101/151-4/151):22/151
108/151-(59/1517/151):22/151 0-(0 • 7/151):22/151 22/151-(-125/1517/151):22/151 1-(0 • 7/151):22/151 7/151-(22/1517/151):22/151 0-(1 • 7/151):22/151 -7/151-(129/1517/151):22/151 8/453-(-6/1517/151):22/151 34/453-(-101/1517/151):22/151
(-215/453+1M)-(59/151 • (-102/151)):22/151 (0)-(0 • (-102/151)):22/151 (33/151)-(-125/151 • (-102/151)):22/151 (0)-(0 • (-102/151)):22/151 (-102/151)-(22/151 • (-102/151)):22/151 (0)-(1 • (-102/151)):22/151 (102/151+1M)-(129/151 • (-102/151)):22/151 (56/453+1M)-(-6/151 • (-102/151)):22/151 (-215/453+1M)-(-101/151 • (-102/151)):22/151



Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x4 215/22 0 -515/22 0 1 619/22 519/22 -3/11 -413/22
x1 1/11 1 -1/11 0 0 302/1661 45602/250811 1/33 -7/33
x3 13/22 0 9/22 1 0 -7/22 -7/22 1/33 19/66
F(X4) 59/11 0 -9/11 0 0 47/11 47/11+1M -45602/752433+1M -319/33+1M


Итерация №4.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (- , - , 13/22 : 9/22 ) = 14/9
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (9/22) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x4 215/22 0 -515/22 0 1 619/22 519/22 -3/11 -413/22 -
x1 1/11 1 -1/11 0 0 302/1661 45602/250811 1/33 -7/33 -
x3 13/22 0 9/22 1 0 -7/22 -7/22 1/33 19/66 14/9
F(X5) 59/11 0 -9/11 0 0 47/11 47/11+1M -45602/752433+1M -319/33+1M 0


4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 5 войдет переменная x2 .
Строка, соответствующая переменной x2 в плане 5, получена в результате деления всех элементов строки x3 плана 4 на разрешающий элемент РЭ=9/22
На месте разрешающего элемента в плане 5 получаем 1.
В остальных клетках столбца x2 плана 5 записываем нули.
Таким образом, в новом плане 5 заполнены строка x2 и столбец x2 .
Все остальные элементы нового плана 5, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6 x7 x8
215/22-(13/22 • -515/22):9/22 0-(0 • -515/22):9/22 -515/22-(9/22 • -515/22):9/22 0-(1 • -515/22):9/22 1-(0 • -515/22):9/22 619/22-(-7/22 • -515/22):9/22 519/22-(-7/22 • -515/22):9/22 -3/11-(1/33 • -515/22):9/22 -413/22-(19/66 • -515/22):9/22
1/11-(13/22-1/11):9/22 1-(0 • -1/11):9/22 -1/11-(9/22-1/11):9/22 0-(1 • -1/11):9/22 0-(0 • -1/11):9/22 302/1661-(-7/22-1/11):9/22 45602/250811-(-7/22-1/11):9/22 1/33-(1/33-1/11):9/22 -7/33-(19/66-1/11):9/22
13/22 : 9/22 0 : 9/22 9/22 : 9/22 1 : 9/22 0 : 9/22 -7/22 : 9/22 -7/22 : 9/22 1/33 : 9/22 19/66 : 9/22
(-319/33+1M)-(13/22 • (-9/11)):9/22 (0)-(0 • (-9/11)):9/22 (-9/11)-(9/22 • (-9/11)):9/22 (0)-(1 • (-9/11)):9/22 (0)-(0 • (-9/11)):9/22 (47/11)-(-7/22 • (-9/11)):9/22 (47/11+1M)-(-7/22 • (-9/11)):9/22 (-45602/752433+1M)-(1/33 • (-9/11)):9/22 (-319/33+1M)-(19/66 • (-9/11)):9/22



Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x4 108/9 0 0 138/9 1 24/9 14/9 4/27 -16/27
x1 2/9 1 0 2/9 0 1/9 1/9 1/27 -4/27
x2 14/9 0 1 24/9 0 -7/9 -7/9 2/27 19/27
F(X5) 7 0 0 2 0 4 4+1M 1M -3+1M


1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x4 108/9 0 0 138/9 1 24/9 14/9 4/27 -16/27
x1 2/9 1 0 2/9 0 1/9 1/9 1/27 -4/27
x2 14/9 0 1 24/9 0 -7/9 -7/9 2/27 19/27
F(X6) 7 0 0 2 0 4 4+1M 1M -3+1M

Оптимальный план можно записать так:
x1 = 2/9
x2 = 14/9
x4 = 108/9

F(X) = 1•108/9 + 2•2/9 -3•14/9 = 7

Скачать шаблон в Excel

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

загрузка...