Контрольная работа: Симплекс-метод

Симплекс-метод.

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 129x1 + 192x2 + 187x3 при следующих условиях-ограничений.
5x1 + 8x2 + 8x3≤125
17x1 + 21x2 + 4x3≤276
21x1 + 10x2 + 8x3≤230
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.
5x1 + 8x2 + 8x3 + 1x4 + 0x5 + 0x6 = 125
17x1 + 21x2 + 4x3 + 0x4 + 1x5 + 0x6 = 276
21x1 + 10x2 + 8x3 + 0x4 + 0x5 + 1x6 = 230
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,125,276,230)
Базисное решение называется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x4 x5 x6
x4 125 5 8 8 1 0 0
x5 276 17 21 4 0 1 0
x6 230 21 10 8 0 0 1
F(X0) 0 -129 -192 -187 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (125 : 8 , 276 : 21 , 230 : 10 ) = 131/7
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (21) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 x5 x6 min
x4 125 5 8 8 1 0 0 155/8
x5 276 17 21 4 0 1 0 131/7
x6 230 21 10 8 0 0 1 23
F(X1) 0 -129 -192 -187 0 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=21
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (21), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6
125-(276 • 8):21 5-(17 • 8):21 8-(21 • 8):21 8-(4 • 8):21 1-(0 • 8):21 0-(1 • 8):21 0-(0 • 8):21
276 : 21 17 : 21 21 : 21 4 : 21 0 : 21 1 : 21 0 : 21
230-(276 • 10):21 21-(17 • 10):21 10-(21 • 10):21 8-(4 • 10):21 0-(0 • 10):21 0-(1 • 10):21 1-(0 • 10):21
0-(276 • -192):21 -129-(17 • -192):21 -192-(21 • -192):21 -187-(4 • -192):21 0-(0 • -192):21 0-(1 • -192):21 0-(0 • -192):21

Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4 x5 x6
x4 139/7 -31/21 0 136/21 1 -8/21 0
x2 92/7 17/21 1 4/21 0 1/21 0
x6 690/7 271/21 0 128/21 0 -10/21 1
F(X1) 17664/7 185/7 0 -1053/7 0 64/7 0
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (196/7 : 610/21 , 131/7 : 4/21 , 984/7 : 62/21 ) = 39/136
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (610/21) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 x5 x6 min
x4 196/7 -110/21 0 610/21 1 -8/21 0 39/136
x2 131/7 17/21 1 4/21 0 1/21 0 69
x6 984/7 1219/21 0 62/21 0 -10/21 1 1611/64
F(X2) 25233/7 263/7 0 -1503/7 0 91/7 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 2 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=610/21
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x3 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6
196/7 : 610/21 -110/21 : 610/21 0 : 610/21 610/21 : 610/21 1 : 610/21 -8/21 : 610/21 0 : 610/21
131/7-(196/7 • 4/21):610/21 17/21-(-110/21 • 4/21):610/21 1-(0 • 4/21):610/21 4/21-(610/21 • 4/21):610/21 0-(1 • 4/21):610/21 1/21-(-8/21 • 4/21):610/21 0-(0 • 4/21):610/21
984/7-(196/7 • 62/21):610/21 1219/21-(-110/21 • 62/21):610/21 0-(0 • 62/21):610/21 62/21-(610/21 • 62/21):610/21 0-(1 • 62/21):610/21 -10/21-(-8/21 • 62/21):610/21 1-(0 • 62/21):610/21
25233/7-(196/7 • -1503/7):610/21 263/7-(-110/21 • -1503/7):610/21 0-(0 • -1503/7):610/21 -1503/7-(610/21 • -1503/7):610/21 0-(1 • -1503/7):610/21 91/7-(-8/21 • -1503/7):610/21 0-(0 • -1503/7):610/21

Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4 x5 x6
x3 417/136 -31/136 0 1 21/136 -1/17 0
x2 427/34 29/34 1 0 -1/34 1/17 0
x6 1358/17 243/17 0 0 -16/17 -2/17 1
F(X2) 405915/136 -1069/136 0 0 3159/136 5/17 0
Итерация №2.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (- , 1219/34 : 29/34 , 7915/17 : 145/17 ) = 5143/243
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (145/17) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 x5 x6 min
x3 39/136 -31/136 0 1 21/136 -1/17 0 -
x2 1219/34 29/34 1 0 -1/34 1/17 0 1421/29
x6 7915/17 145/17 0 0 -16/17 -2/17 1 5143/243
F(X3) 298491/136 -7117/136 0 0 2331/136 5/17 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 3 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 3, получена в результате деления всех элементов строки x6 плана 2 на разрешающий элемент РЭ=145/17
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x1 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6
39/136-(7915/17 • -31/136):145/17 -31/136-(145/17 • -31/136):145/17 0-(0 • -31/136):145/17 1-(0 • -31/136):145/17 21/136-(-16/17 • -31/136):145/17 -1/17-(-2/17 • -31/136):145/17 0-(1 • -31/136):145/17
1219/34-(7915/17 • 29/34):145/17 29/34-(145/17 • 29/34):145/17 1-(0 • 29/34):145/17 0-(0 • 29/34):145/17 -1/34-(-16/17 • 29/34):145/17 1/17-(-2/17 • 29/34):145/17 0-(1 • 29/34):145/17
7915/17 : 145/17 145/17 : 145/17 0 : 145/17 0 : 145/17 -16/17 : 145/17 -2/17 : 145/17 1 : 145/17
298491/136-(7915/17 • -7117/136):145/17 -7117/136-(145/17 • -7117/136):145/17 0-(0 • -7117/136):145/17 0-(0 • -7117/136):145/17 2331/136-(-16/17 • -7117/136):145/17 5/17-(-2/17 • -7117/136):145/17 0-(1 • -7117/136):145/17

Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4 x5 x6
x3 8437/1944 0 0 1 271/1944 -59/972 31/1944
x2 3787/486 0 1 0 13/486 16/243 -29/486
x1 1358/243 1 0 0 -16/243 -2/243 17/243
F(X3) 5887591/1944 0 0 0 44149/1944 223/972 1069/1944
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4 x5 x6
x3 8437/1944 0 0 1 271/1944 -59/972 31/1944
x2 3787/486 0 1 0 13/486 16/243 -29/486
x1 1358/243 1 0 0 -16/243 -2/243 17/243
F(X4) 5887591/1944 0 0 0 44149/1944 223/972 1069/1944
Оптимальный план можно записать так:
x3 = 4661/1944
x2 = 7385/486
x1 = 5143/243
F(X) = 187•4661/1944 + 192•7385/486 + 129•5143/243 = 30281159/1944