Примеры решений задач симплексным методом

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

Здесь рассмотрен пример решения в виде симплексной таблицы с использованием калькулятора. Существуют и другие формы записи симплекс-метода

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

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

План Базис В x1 x2 x3 x4 x5 x6 min
1 x3 -20 -2 -12 1 0 0 0 1.67
x4 -32 -4 -6 0 1 0 0 5.33
x5 -14 -3 0 0 0 1 0 -
x6 -42 0 -18 0 0 0 1 2.33
Индексная строка F(X1) 0 12 10 0 0 0 0 0
2 x2 1.67 0.17 1 -0.08 0 0 0 -
x4 -22 -3 0 -0.5 1 0 0 44
x5 -14 -3 0 0 0 1 0 -
x6 -12 3 0 -1.5 0 0 1 8
Индексная строка F(X2) -16.67 10.33 0 0.83 0 0 0 0
3 x2 2.33 0 1 0 0 0 -0.06 -
x4 -18 -4 0 0 1 0 -0.33 54
x5 -14 -3 0 0 0 1 0 -
x3 8 -2 -0 1 -0 -0 1 8
Индексная строка F(X3) -23.33 12 0 0 0 0 0.56 0
4 x2 2.78 -0.11 1 0.06 0 0 0 -
x4 -15.33 -4.67 0 0.33 1 0 0 3.29
x5 -14 -3 0 0 0 1 0 4.67
x6 8 -2 -0 1 -0 -0 1 -
Индексная строка F(X4) -27.78 13.11 0 -0.56 0 0 0 0
5 x2 3.14 -0 1 0.05 -0.02 0 0 66
x1 3.29 1 -0 -0.07 -0.21 -0 0 -
x5 -4.14 0 0 -0.21 -0.64 1 0 19.33
x6 14.57 0 -0 0.86 -0.43 -0 1 17
Индексная строка F(X5) -70.86 0 0 0.38 2.81 0 0 0
6 x2 2.33 -0 1 0 -0 0 -0.06 -
x1 4.5 1 -0 0 -0.25 -0 0.08 -
x5 -0.5 0 0 0 -0.75 1 0.25 0.67
x3 17 0 -0 1 -0.5 -0 1 -
Индексная строка F(X6) -77.33 0 0 0 3 0 -0.44 0
7 x2 2.33 -0 1 0 0 -0 -0.06 -
x1 4.67 1 -0 0 0 -0.33 0 4.67
x4 0.67 -0 -0 -0 1 -1.33 0.25 -
x3 17.33 0 -0 1 0 -0.67 0.83 -
Индексная строка F(X7) -79.33 0 0 0 -0 4 0.56 0

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

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




























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

и из них выберем наименьшее:

Следовательно,4-ая строка является ведущей
Разрешающий элемент равен -1.5 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 2 войдет переменная x3
Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=-1.5
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x3 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №2
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x6, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно,4-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 3 войдет переменная x6
Строка, соответствующая переменной x6 в плане 3, получена в результате деления всех элементов строки x3 плана 2 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x6 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x6 и столбец x6.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №3
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно,2-ая строка является ведущей
Разрешающий элемент равен -4.67 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 4 войдет переменная x1
Строка, соответствующая переменной x1 в плане 4, получена в результате деления всех элементов строки x4 плана 3 на разрешающий элемент РЭ=-4.67
На месте разрешающего элемента в плане 4 получаем 1.
В остальных клетках столбца x1 плана 4 записываем нули.
Таким образом, в новом плане 4 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №4
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x3, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно,4-ая строка является ведущей
Разрешающий элемент равен 0.86 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 5 войдет переменная x3
Строка, соответствующая переменной x3 в плане 5, получена в результате деления всех элементов строки x6 плана 4 на разрешающий элемент РЭ=0.86
На месте разрешающего элемента в плане 5 получаем 1.
В остальных клетках столбца x3 плана 5 записываем нули.
Таким образом, в новом плане 5 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 5, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №5
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x4, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно,3-ая строка является ведущей
Разрешающий элемент равен -0.75 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 6 войдет переменная x4
Строка, соответствующая переменной x4 в плане 6, получена в результате деления всех элементов строки x5 плана 5 на разрешающий элемент РЭ=-0.75
На месте разрешающего элемента в плане 6 получаем 1.
В остальных клетках столбца x4 плана 6 записываем нули.
Таким образом, в новом плане 6 заполнены строка x4 и столбец x4.
Все остальные элементы нового плана 6, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №6
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно,2-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x1 в план 7 войдет переменная x1
Строка, соответствующая переменной x1 в плане 7, получена в результате деления всех элементов строки x1 плана 6 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 7 получаем 1.
В остальных клетках столбца x1 плана 7 записываем нули.
Таким образом, в новом плане 7 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 7, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №7
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно,2-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Оптимальный план можно записать так:
x2 = 2.33
x1 = 4.67
x4 = 0.67
x3 = 17.33
F(X) = 79.33

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

загрузка...