Пример нахождения минимума функции симплексным методом

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

Решим систему уравнений относительно базисных переменных: x3,x4,x5,x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (-20,-32,-14,-42)

Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления и из них выберем наименьшее:
Следовательно,1-ая строка является ведущей
Разрешающий элемент равен -12 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 1 войдет переменная x2
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=-12
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ




























Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x3, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления и из них выберем наименьшее:
Следовательно,4-ая строка является ведущей
Разрешающий элемент равен -1.5 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 2 войдет переменная x3
Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=-1.5
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x3 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №2
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x6, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления и из них выберем наименьшее:
Следовательно,4-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 3 войдет переменная x6
Строка, соответствующая переменной x6 в плане 3, получена в результате деления всех элементов строки x3 плана 2 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x6 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x6 и столбец x6.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №3
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления и из них выберем наименьшее:
Следовательно,2-ая строка является ведущей
Разрешающий элемент равен -4.67 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 4 войдет переменная x1
Строка, соответствующая переменной x1 в плане 4, получена в результате деления всех элементов строки x4 плана 3 на разрешающий элемент РЭ=-4.67
На месте разрешающего элемента в плане 4 получаем 1.
В остальных клетках столбца x1 плана 4 записываем нули.
Таким образом, в новом плане 4 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №4
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x3, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления и из них выберем наименьшее:
Следовательно,4-ая строка является ведущей
Разрешающий элемент равен 0.86 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 5 войдет переменная x3
Строка, соответствующая переменной x3 в плане 5, получена в результате деления всех элементов строки x6 плана 4 на разрешающий элемент РЭ=0.86
На месте разрешающего элемента в плане 5 получаем 1.
В остальных клетках столбца x3 плана 5 записываем нули.
Таким образом, в новом плане 5 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 5, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №5
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x4, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления и из них выберем наименьшее:
Следовательно,3-ая строка является ведущей
Разрешающий элемент равен -0.75 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 6 войдет переменная x4
Строка, соответствующая переменной x4 в плане 6, получена в результате деления всех элементов строки x5 плана 5 на разрешающий элемент РЭ=-0.75
На месте разрешающего элемента в плане 6 получаем 1.
В остальных клетках столбца x4 плана 6 записываем нули.
Таким образом, в новом плане 6 заполнены строка x4 и столбец x4.
Все остальные элементы нового плана 6, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №6
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления и из них выберем наименьшее:
Следовательно,2-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x1 в план 7 войдет переменная x1
Строка, соответствующая переменной x1 в плане 7, получена в результате деления всех элементов строки x1 плана 6 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 7 получаем 1.
В остальных клетках столбца x1 плана 7 записываем нули.
Таким образом, в новом плане 7 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 7, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №7
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления и из них выберем наименьшее:
Следовательно,2-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Оптимальный план можно записать так: x₂ = 2.33, x₁ = 4.67, x₄ = 0.67, x₃ = 17.33
F(X) = 79.33

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